Разработка ядра 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) для проведения быстрого поиска в битовой маске. Эта функция называется sched_find_first_bit. Для многих аппаратных платформ существует машинная инструкция нахождения первого установленного бита в заданном машинном слове[22]. Для таких систем нахождение первого установленного бита является тривиальной операций и сводится к выполнению этой инструкции несколько раз.

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

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

Пересчет квантов времени

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

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

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

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

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

}

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

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