Разработка ядра Linux

Лав Роберт

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

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.

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

Для реализации такой эвристики в ядре Linux предусмотрен изменяемый показатель того, как соотносится время, которое процесс проводит в приостановленном состоянии, со временем, которое процесс проводит в состоянии готовности к выполнению. Значение этого показателя хранится в поле

sleep

_avg структуры

task_struct

. Диапазон значений этого показателя лежит от нуля до значения

MAXSLEEP_AVG

, которое по умолчанию равно 10 мс. Когда задача становится готовой к выполнению после приостановленного состояния, значение поля

sleep_avg

увеличивается на значение времени, которое процесс провел в приостановленном состоянии, пока значение

sleep_avg

не достигнет

MAXSLEEP_AVG

. Когда задача выполняется, то в течение каждого импульса таймера (timer tick) значение этой переменной уменьшается, пока оно не достигнет значения 0.

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

sleep_avg

. Несмотря на все сказанное, надбавка и штраф применяются к значению параметра nice, так что пользователь также может влиять на работу системного планировщика путем изменения значения параметра nice процесса.

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

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

task_timeslice

возвращает новое значение кванта времени для данного задания. Расчет просто сводится к масштабированию значения приоритета в диапазон значений квантов времени. Чем больше значение приоритета задачи, тем большей продолжительности квант времени получит задание в текущем цикле выполнения. Максимальное значение кванта времени равно

MAX_TIMESLICE

, которое по умолчанию равно 200 мс. Даже задания с самым низким приоритетом получают квант времени продолжительностью

MIN_TIMESLICE

, что соответствует 10 мс. Задачи с приоритетом, используемым по умолчанию (значение параметра nice, равно 0 и отсутствует надбавка и штраф за интерактивность), получают квант времени продолжительностью 100 мс, как показано в табл. 4.1.

Таблица 4.1. Продолжительности квантов времени планировщика

Тип задания	Значение параметра nice	Продолжительность кванта времени
Вновь созданное	То же, что и у родительского процесса	Половина от родительского процесса
Минимальный приоритет	+19	5 мс (MIN_TIMESLICE)
Приоритет по умолчанию	0	100 мс (DEF_TIMESLICE)
Максимальный приоритет	– 20	800 мс (MAX_TIMESLICE)

Для интерактивных задач планировщик оказывает дополнительную услугу: если задание достаточно интерактивно, то при исчерпании своего кванта времени оно будет помещено не в истекший массив приоритетов, а обратно в активный массив приоритетов. Следует вспомнить, что пересчет значений квантов времени производится путем перестановки активного и истекшего массивов приоритетов: активный массив становится истекшим, а истекший — активным. Такая процедура обеспечивает пересчет значений квантов времени, который масштабируется по времени как O(1). С другой стороны, это может привести к тому, что интерактивное задание станет готовым к выполнению, но не получит возможности выполняться, так как оно "застряло" в истекшем массиве. Помещение интерактивных заданий снова в активный массив позволяет избежать такой проблемы. Следует заметить, что это задание не будет выполняться сразу же, а будет запланировано на выполнение по кругу вместе с другими заданиями, которые имеют такой же приоритет. Данную логику реализует функция

scheduler_tick

, которая вызывается обработчиком прерываний таймера (обсуждается в главе 10, "Таймеры и управление временем"), как показано ниже.

struct task_struct *task = current;

struct runqueue *rq = this_rq;

if (!--task->time_slice) {

 if (!TASK_INTERACTIVE(task) || EXPIRED_STARVING(rq))

enqueue_task(task, rq->expired);

 else

enqueue_task(task, rq->active);

}

Показанный код уменьшает значение кванта времени процесса и проверяет, не стало ли это значение равным нулю. Если стало, то задание является истекшим и его необходимо поместить в один из массивов. Для этого код вначале проверяет интерактивность задания с помощью макроса

TASK_INTERACTIVE

. Этот макрос на основании значения параметра nice рассчитывает, является ли задание "достаточно интерактивным". Чем меньше значение nice (чем выше приоритет), тем менее интерактивным должно быть задание. Задание со значением параметра nice, равным 19, никогда не может быть достаточно интерактивным для помещения обратно в активный массив. Наоборот, задание со значением nice, равным -20, должно очень сильно использовать процессор, чтобы его не поместили в активный массив. Задача со значением nice, используемым по умолчанию, т.е. равным нулю, должна быть достаточно интерактивной, чтобы быть помещенной обратно в активный массив, но это также отрабатывается достаточно четко. Следующий макрос,

EXPIRED_STARVING

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