Читать «Разработка ядра Linux» онлайн - страница 49
Роберт Лав
Массивы приоритетов
Каждая очередь выполнения содержит два kernel/sched.c
в виде описания struct prio_array
. Массивы приоритетов — это структуры данных, которые обеспечивают O(1)-планирование. Каждый массив приоритетов содержит для каждого значения приоритета одну очередь процессов, готовых к выполнению. Массив приоритетов также содержит
struct prio_array {
int nr_active; /* количество заданий */
unsigned long bitmap[BITMAP_SIZE]; /* битовая маска приоритетов */
struct list_head queue[MAX_PRIO]; /* очереди приоритетов */
};
Константа MAX_PRIO
— это количество уровней приоритета в системе. По умолчанию значение этой константы равно 140. Таким образом, для каждого значения приоритета выделена одна структура struct list_head
. Константа BITMAP_SIZE
— это размер массива переменных, каждый элемент которого имеет тип unsigned long
. Каждый бит этого массива соответствует одному действительному значению приоритета. В случае 140 уровней приоритетов и при использовании 32-разрядных машинных слов, значение константы BITMAP_SIZE
равно 5. Таким образом, поле bitmap
— это массив из пяти элементов, который имеет длину 160 бит.
Все массивы приоритетов содержат поле bitmap
, каждый бит этого поля соответствует одному значению приоритета в системе. В самом начале значения всех битов равны 0. Когда задача с определенным приоритетом становится готовой к выполнению (то есть значение статуса этой задачи становится равным TASK_RUNNING
), соответствующий этому приоритету бит поля bitmap
устанавливается в значение 1. Например, если задача с приоритетом, равным 7, готова к выполнению, то устанавливается бит номер 7. Нахождение задания с самым высоким приоритетом в системе сводится только лишь к нахождению самого первого установленного бита в битовой маске. Так как количество приоритетов неизменно, то время, которое необходимо затратить на эту операцию поиска, постоянно и не зависит от количества процессов, выполняющихся в системе. Более того, для каждой поддерживаемой аппаратной платформы в ОС Linux должен быть реализован быстрый алгоритм ched_find_first_bit()
. Для многих аппаратных платформ существует машинная инструкция нахождения первого установленного бита в заданном машинном слове. Для таких систем нахождение первого установленного бита является тривиальной операций и сводится к выполнению этой инструкции несколько раз.