Роберт Лав - Разработка ядра Linux
Интерфейсы для вывода энтропии
Для получения случайных чисел внутри ядра экспортируется один интерфейс.
void get_random_bytes(void *buf, int nbytes);
Эта функция сохраняет nbytes случайных байтов в буфере памяти, на который указывает параметр buf. Функция возвращает данные, даже если оценка энтропии равна нулю. Для ядра это не так критично, как для пользовательских криптографических программ. Случайные данные мало используются в ядре, в основном они нужны сетевой подсистеме для генерации стартового номера последовательности сегментов при соединении по протоколу TCP.
Код ядра может выполнить следующий код для получения случайных данных размером в одно машинное слово.
unsigned long rand;
get_random_bytes(&rand, sizeof(rand));
Для программ, которые выполняются в пространстве пользователя, предоставляется два символьных устройства: /dev/random и /dev/urandom. Первое устройство, /dev/random, используется, когда необходимы гарантированно случайные данные для криптографических приложений с высоким уровнем безопасности. Это устройство выдает только то количество битов данных, которое соответствует оценке энтропии в ядре. Когда оценка энтропии становится равной нулю, операция чтения устройства /dev/random блокируется и не возвращает данные, пока значение энтропии не станет существенно положительным. Устройство /dev/urandom не имеет последней возможности, а в остальном работает аналогично. Оба устройства возвращают данные из одного и того же пула.
Чтение из обоих файлов выполняется очень просто. Ниже показана функция пользовательской программы, которая служит для считывания одного машинного слова случайных данных.
unsigned long get_random(void) {
unsigned long seed = 0;
int fd;
fd = open("/dev/urandom", O_RDONLY);
if (fd == -1) {
perror("open");
return 0;
}
if (read(fd, &seed, sizeof(seed)) < 0) {
perror("read");
seed = 0;
}
if (close(fd))
perror("close");
return seed;
}
Можно также считать $bytes байтов в файл $file, используя программу dd.
dd if=/dev/urandom of=$file count=1 bs=$bytes
Приложение В
Сложность алгоритмов
В компьютерных и связанных с ними дисциплинах полезно выражать сложность, или масштабируемость, алгоритмов с помощью количественных значащих характеристик (в отличие от менее наглядных характеристик, таких как быстрый или медленный). Существуют различные методы представления масштабируемости. Один из наиболее часто используемых подходов — это исследование асимптотического поведения алгоритмов. Асимптотическое поведение — это поведение алгоритма при достаточно больших значениях входных параметров или, другими словами, при стремлении входных параметров к бесконечности. Асимптотическое поведение показывает, как масштабируется алгоритм, когда его входные параметры принимают все большие и большие значения. Исследование масштабируемости алгоритмов, т.е. изучение свойств алгоритма при больших значениях входных параметров, позволяет смоделировать поведение алгоритма по отношению к тестовым задачам и лучше понять особенности этого поведения.
Алгоритмы
Алгоритм — это последовательность действий, возможно, с одним входом или более и, в конечном счете, с одним результатом или выходом. Например, подсчет количества людей в комнате представляет собой алгоритм, для которого люди, находящиеся в комнате, являются входными данными, а количество людей в комнате — выходными данными. Операции замещения страниц в ядре Linux или планирование выполнения процессов — это тоже примеры алгоритмов. Математически алгоритм аналогичен функции (или, по крайней мере, может быть смоделирован с помощью функции). Например, если мы обозначим алгоритм подсчета людей в комнате буквой f, а количество людей, которых необходимо посчитать, буквой x, то функцию подсчета количества людей можно записать следующим образом.
y=f(x)
В этом выражении буквой y обозначено время подсчета количества людей в комнате.
Множество О
Полезным обозначением асимптотического поведения функции является верхняя граница — функция, значения которой всегда больше значений изучаемой функции. Говорят, что верхняя граница некоторой функции растет быстрее, чем рассматриваемая функция. Специальное обозначение "большого-O" используется для описания этого роста. Это записывается как f(x) ∈ О(g(x)) и читается так: f принадлежит множеству "O-большого" от g. Формальное математическое определение имеет следующий вид.
Если f(x) принадлежит множеству большого O(g(x)) , то ∃c и x', такие что f(x)≤c∙g(x), ∀x>x'
Это означает, что время вычисления функции f(x) всегда меньше времени вычисления функции g(x), умноженного на некоторую константу, и это справедливо всегда, для всех значений x, больших некоторого начального значения х'.
Другими словами, мы ищем функцию, которая ведет себя не лучше, чем наш алгоритм в наихудшей ситуации. Можно посмотреть на результаты того, как ведет себя функция при очень больших значениях входных параметров, и понять, как ведет себя алгоритм.
Множество большого-тета
Когда говорят об обозначении большого-О, то чаще всего имеют в виду то, что Дональд Кнут (Donald Knuth) описывал с помощью обозначения "большого-тета". Обозначение "большого-О" соответствует верхней границе. Например, число 7 — это верхняя граница числа 6, кроме того, числа 9, 12 и 65 — это тоже верхние границы числа 6. Когда рассматривают рост функции, то обычно наиболее интересна наименьшая верхняя граница или функция, которая моделирует как верхнюю, так и нижнюю границу[100]. Профессор Кнут описывает это с помощью обозначения большого-тета следующим образом.
Если f(x) принадлежит множеству большого-тета от g(x), то g(x) является одновременно и верхней и нижней границей f(x)
Можно также сказать, что функция f(x) порядка функции g(x). Порядок, или множество "большого-тета" алгоритма, — один из наиболее важных математических инструментов изучения алгоритмов.
Следовательно, когда говорят об обозначении большого-О, то чаще всего имеют в виду наименьший возможный вариант "большого-О" — "большое-тета". Об этом не нужно особо волноваться, если, конечно, нет желания доставить удовольствие профессору Кнуту.
Объединяем все вместе
Вернемся снова к подсчету количества людей в комнате. Допустим, что можно считать по одному человеку за секунду. Следовательно, если в комнате находится 7 человек, то подсчет займет 7 секунд. Очевидно, что если будет n человек, то подсчет всех займет n секунд. Поэтому можно сказать, что этот алгоритм масштабируется, как O(n). Что если задача будет состоять в том, чтобы станцевать перед всеми, кто находится в комнате? Поскольку, независимо от того, сколько человек будет в комнате, это займет одно и то же время, значит, этот алгоритм масштабируется, как O(1). В табл. В.1 показаны другие часто встречающиеся характеристики сложности.
Таблица В.1. Значения масштабируемости алгоритмов во времени
O(g(x)) Название 1 Постоянная (отличная масштабируемость) log(n) Логарифмическая n Линейная n² Квадратичная n³ Кубическая 2ⁿ Показательная, или экспоненциальная (плохо) n! Факториал (очень плохо)Как масштабируется алгоритм представления всех людей в комнате друг другу? Какая функция может промоделировать этот алгоритм? Для представления одного человека необходимо 30 секунд, сколько времени займет представление 10 человек друг другу? Что будет в случае 100 человек?
