Читать «Разработка ядра Linux» онлайн - страница 50

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

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

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

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

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

for (каждого задания в системе) (
 пересчитать значение приоритета
 пересчитать значение кванта времени
}

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

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

• Во время пересчета должен быть использован какой-нибудь тип блокировки для защиты списка задач и отдельных дескрипторов процессов. В результате получается высокий уровень конфликтов при захвате блокировок.

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