Каждая очередь выполнения содержит два массива приоритетов (priority arrays): активный и истекший. Массивы приоритетов определены в файле >kernel/sched.c в виде описания >struct prio_array. Массивы приоритетов — это структуры данных, которые обеспечивают O(1)-планирование. Каждый массив приоритетов содержит для каждого значения приоритета одну очередь процессов, готовых к выполнению. Массив приоритетов также содержит битовую маску приоритетов (priority bitmap), используемую для эффективного поиска готового к выполнению задания, у которого значение приоритета является наибольшим в системе.
> 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 должен быть реализован быстрый алгоритм поиска первого установленного бита (find first set) для проведения быстрого поиска в битовой маске. Эта функция называется s
