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

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

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

}

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

• Пересчет потенциально может занять много времени. Хуже того, время такого расчета масштабируется как О(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(). Эта функция вызывается явно кодом ядра при переходе в приостановленное состояние (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(), зависящая от аппаратной платформы. Переключение контекста будет рассмотрено в одном из следующих разделов.

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

В начале этой главы было рассмотрено, как приоритет и квант времени используются для того, чтобы влиять на те решения, которые принимает планировщик. Кроме того, были рассмотрены процессы, ограниченные скоростью ввода-вывода и скоростью процессора, а также было описано, почему желательно поднимать приоритет интерактивных задач. Теперь давайте рассмотрим код, который реализует эти соображения.

Процессы имеют начальное значение приоритета, которое называется nice. Это значение может лежать в диапазоне от -20 до 19, по умолчанию используется значение 0. Значение 19 соответствует наиболее низкому приоритету, а значение -20 — наиболее высокому. Значение параметра nice хранится в поле static_prioструктуры task_structпроцесса. Это значение называется статическим приоритетом, потому что оно не изменяется планировщиком и остается таким, каким его указал пользователь. Планировщик свои решения основывает на динамическом приоритете, которое хранится в поле prio. Динамический приоритет вычисляется как функция статического приоритета и интерактивности задания.

Функция effective_prio()возвращает значение динамического приоритета задачи. Эта функция исходит из значения параметра nice для данной задачи и вычисляет для этого значения надбавку или штраф в диапазоне от -5 до 5, в зависимости от интерактивности задачи. Например, задание с высокой интерактивностью, которое имеет значение параметра nice , равное 10, может иметь динамический приоритет, равный 5. И наоборот, программа со значением параметра nice, равным 10, которая достаточно активно использует процессор, может иметь динамический приоритет, равный 12. Задачи, которые обладают умеренной интерактивностью, не получают ни надбавки, ни штрафа, и их динамический приоритет совпадает со значением параметра nice .