, каждый бит этого поля соответствует одному значению приоритета в системе. В самом начале значения всех битов равны 0. Когда задача с определенным приоритетом становится готовой к выполнению (то есть значение статуса этой задачи становится равным
TASK_RUNNING
), соответствующий этому приоритету бит поля
bitmap
устанавливается в значение 1. Например, если задача с приоритетом, равным 7, готова к выполнению, то устанавливается бит номер 7. Нахождение задания с самым высоким приоритетом в системе сводится только лишь к нахождению самого первого установленного бита в битовой маске. Так как количество приоритетов неизменно, то время, которое необходимо затратить на
эту операцию поиска, постоянно и не зависит от количества процессов, выполняющихся в системе. Более того, для каждой поддерживаемой аппаратной платформы в ОС Linux должен быть реализован быстрый алгоритм поиска первого установленного бита (find first set) для проведения быстрого поиска в битовой маске. Эта функция называется s
ched_find_first_bit
. Для многих аппаратных платформ существует машинная инструкция нахождения первого установленного бита в заданном машинном слове [22] . Для таких систем нахождение первого установленного бита является тривиальной операций и сводится к выполнению этой инструкции несколько раз.
22
Для аппаратной платформы x86 используется инструкция
bsfl
, а для платформы PPC — инструкция
cntlzw
.
Каждый массив приоритетов также содержит массив очередей, представленных структурами
struct list_head
. Этот массив называется queue. Каждому значению приоритета соответствует своя очередь. Очереди реализованы в виде связанных списков, и каждому значению приоритета соответствует список всех процессов системы, готовых к выполнению, имеющих это значение приоритета и находящихся в очереди выполнения данного процессора. Нахождение задания, которое будет выполняться следующим, является простой задачей и сводится к выбору следующего элемента из списка. Все задания с одинаковым приоритетом планируются на выполнение циклически.
Массив приоритетов также содержит счетчик
nr_active
, значение которого соответствует количеству готовых к выполнению заданий в данном массиве приоритетов.
Пересчет квантов времени
Во многих операционных системах (включая и более старые версии ОС Linux) используется прямой метод для пересчета значения кванта времени каждого задания, когда все эти значения достигают нуля.
Обычно это реализуется с помощью цикла по всем задачам в системе, например, следующим образом.
for (каждого задания в системе) (
пересчитать значение приоритета
пересчитать значение кванта времени
}
Значение приоритета и другие атрибуты задачи используются для определения нового значения кванта времени. Такой подход имеет некоторые проблемы.
• Пересчет потенциально может занять много времени. Хуже того, время такого расчета масштабируется как О(n), где n — количество задач в системе.
• Во время пересчета должен быть использован какой-нибудь тип блокировки для защиты списка задач и отдельных дескрипторов процессов. В результате получается высокий уровень конфликтов при захвате блокировок.
• Отсутствие определенности в случайно возникающих пересчетах значений квантов времени является проблемой для программ реального времени.
• Откровенно говоря, это просто нехорошо (что является вполне оправданной причиной для каких-либо усовершенствований ядра Linux).
Новый планировщик ОС Linux позволяет избежать использования цикла пересчета приоритетов. Вместо этого в нем применяется два массива приоритетов для каждого процессора: активный (active) и истекший (expired).
Активный массив приоритетов содержит очередь, в которую включены все задания соответствующей очереди выполнения, для которых еще не иссяк квант времени. Истекший массив приоритетов содержит все задания соответствующей очереди, которые израсходовали свой квант времени. Когда значение кванта времени для какого-либо задания становится равным нулю, то перед тем, как поместить это задание в истекший массив приоритетов, для него вычисляется новое значение кванта времени. Пересчет значений кванта времени для всех процессов проводится с помощью перестановки активного и истекшего массивов местами. Так как на массивы ссылаются с помощью указателей, то переключение между ними будет выполняться так же быстро, как и перестановка двух указателей местами. Показанный ниже код выполняется в функции
schedule
.
struct prio_array array = rq->active;
if (!array->nr_active) {
rq->active = rq->expired;
rq->expired = array;
}
Упомянутая перестановка и есть ключевым, моментом O(1)-планировщика. Вместо того чтобы все время пересчитывать значение приоритета и кванта времени для каждого процесса, O(1)-планировщик выполняет простую двухшаговую перестановку массивов. Такая реализация позволяет решить указанные выше проблемы.
Функция
schedule
Все действия по выбору следующего задания на исполнение и переключение на выполнение этого задания реализованы в виде функции
schedule
. Эта функция вызывается явно кодом ядра при переходе в приостановленное состояние (sleep), a также в случае когда какое-либо задание вытесняется. Функция
schedule
выполняется независимо каждым процессором. Следовательно, каждый процессор самостоятельно принимает решение о том, какой процесс выполнять следующим.
Функция
schedule
достаточно проста, учитывая характер тех действий, которые она выполняет. Следующий код позволяет определить задачу с наивысшим приоритетом.
struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array *array;
int idx;
prev = current;
array = rq->active;
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, struct task struct, run_list);
Вначале осуществляется поиск в битовой маске активного массива приоритетов для нахождения номера самого первого установленного бита. Этот бит соответствует готовой к выполнению задаче с наивысшим приоритетом. Далее планировщик выбирает первое задание из списка заданий, которое соответствует найденному значению приоритета. Это и есть задача с наивысшим значением приоритета в системе, и эту задачу планировщик будет запускать на выполнение. Все рассмотренные операции показаны на рис. 4.2.
Рис. 4.2. Алгоритм работы О(1)-планировщика операционной системы Linux
Если полученные значения переменных
prev
и
next
не равны друг другу, то для выполнения выбирается новое задание (
next
). При этом для переключения с задания, на которое указывает переменная
prev
, на задание, соответствующее переменной next, вызывается функция
context_switch
, зависящая от аппаратной платформы. Переключение контекста будет рассмотрено в одном из следующих разделов.