Разработка ядра Linux (Второе издание)

Лав Роберт

Эти три функции добавляют передаваемые данные в пул энтропии, вычисляют оценку энтропии добавляемых данных и увеличивают оценку энтропии пула на вычисленное значение.

Все эти экспортируемые интерфейсы используют внутреннюю функцию

add_timer_randomness

для ввода данных в пул. Эта функция вычисляет интервалы времени между успешными событиями одного типа и добавляет эти значения в пул. Например, интервалы времени между успешными прерываниями жесткого диска достаточно случайны, особенно если измерять достаточно точно. Самые младшие биты — это обычно электрический шум. После того как эта функция вводит данные в пул, она вычисляет количественную характеристику того, насколько эти данные случайны. Это делается путем вычисления отклонения первого, второго и третьего порядка от предыдущего момента времени и изменения этих отклонений первого, второго и третьего

порядка. Наибольшее из этих отклонений, округленное до 12 бит, используется в качестве оценки энтропии.

Интерфейсы для вывода энтропии

Для получения случайных чисел внутри ядра экспортируется один интерфейс.

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] . Профессор Кнут описывает это с помощью обозначения большого-тета следующим образом.

100

Если интересно, то нижняя граница описывается с помощью обозначения большого-омега. Определение аналогично определению множества большого-О, за исключением того, что значения функции g(x) должны быть меньше значений функции f(x) или равны им.