Роберт Лав - Разработка ядра Linux

Каждая очередь выполнения содержит два массива приоритетов ( 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 ched_find_first_bit(). Для многих аппаратных платформ существует машинная инструкция нахождения первого установленного бита в заданном машинном слове [22] Для аппаратной платформы x86 используется инструкция bsfl , а для платформы PPC — инструкция cntlzw . . Для таких систем нахождение первого установленного бита является тривиальной операций и сводится к выполнению этой инструкции несколько раз.

Каждый массив приоритетов также содержит массив очередей, представленных структурами struct list_head. Этот массив называется queue. Каждому значению приоритета соответствует своя очередь. Очереди реализованы в виде связанных списков, и каждому значению приоритета соответствует список всех процессов системы, готовых к выполнению, имеющих это значение приоритета и находящихся в очереди выполнения данного процессора. Нахождение задания, которое будет выполняться следующим, является простой задачей и сводится к выбору следующего элемента из списка. Все задания с одинаковым приоритетом планируются на выполнение циклически.

Массив приоритетов также содержит счетчик nr_active, значение которого соответствует количеству готовых к выполнению заданий в данном массиве приоритетов.

Во многих операционных системах (включая и более старые версии ОС Linux) используется прямой метод для пересчета значения кванта времени каждого задания, когда все эти значения достигают нуля.

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

for (каждого задания в системе) (

пересчитать значение приоритета

пересчитать значение кванта времени

}

Значение приоритета и другие атрибуты задачи используются для определения нового значения кванта времени. Такой подход имеет некоторые проблемы.

• Пересчет потенциально может занять много времени. Хуже того, время такого расчета масштабируется как О(n) , где n — количество задач в системе.