Вычисление приоритетов и квантов времени

Вычисление приоритетов и квантов времени

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

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Определение приоритетов

Из книги Время - деньги. Создание команды разработчиков программного обеспечения автора Салливан Эд


ТЕМА НОМЕРА: Кванты ради квантов

Из книги Журнал «Компьютерра» № 23 от 20 июня 2006 года автора Журнал «Компьютерра»

ТЕМА НОМЕРА: Кванты ради квантов Автор: Леонид Левкович-МаслюкОдин из самых захватывающих сюжетов современной физики — попытки нащупать пути построения квантового компьютера (КК). Погоня за довольно призрачной целью сводит воедино трудносовместимые вещи. С одной


1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени

Из книги Искусство программирования для Unix автора Реймонд Эрик Стивен

1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени "В ранние мини-компьютерные времена Unix" вынесенная в заголовок идея была довольно радикальной (машины тогда работали


Динамическое планирование приоритетов

Из книги Основы AS/400 автора Солтис Фрэнк

Динамическое планирование приоритетов В предыдущих разделах мы рассмотрели более понятную, но упрощенную модель диспетчеризации задач в AS/400. Со времен первой System/38 в структуру задач было внесено множество изменений для удовлетворения требований различных приложений и


Дмитрий Плесконос: Развитие Интернета - один из приоритетов

Из книги Компьютерра PDA 20.03.2010-26.03.2010 автора Журнал «Компьютерра»

Дмитрий Плесконос: Развитие Интернета - один из приоритетов Автор: Опубликовано 22 марта 2010 годаИсполнительный вице-президент ОАО «Вымпелком» по развитию бизнеса на массовом рынке Дмитрий Плесконос ответил на вопросы читателей "Компьютерры" о доступе в Интернет,


1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени

Из книги Искусство программирования для Unix автора Реймонд Эрик Стивен

1.6.13. Правило экономии: время программиста стоит дорого; поэтому экономия его времени более приоритетна по сравнению с экономией машинного времени "В ранние мини-компьютерные времена Unix" вынесенная в заголовок идея была довольно радикальной (машины тогда работали


8 Расстановка приоритетов

Из книги Тайм-менеджмент для системных администраторов автора Лимончелли Томас

8 Расстановка приоритетов В этой главе описывается процесс расстановки приоритетов «снизу вверх». Вначале я уточню то, чего поверхностно коснулся в главе 5, - расстановка приоритетов в сегодняшнем списке дел. Затем я собираюсь обсудить приоритеты более крупных проектов.


Расстановка приоритетов в списке дел

Из книги Программирование на языке Ruby [Идеология языка, теория и практика применения] автора Фултон Хэл

Расстановка приоритетов в списке дел Итак, вы сидите за рабочим столом, и перед вами список сегодняшних дел. Десятки пунктов. Как вы определите, с чего начать?Этот раздел посвящен расстановке приоритетов в этом списке. В разных ситуациях приходится использовать разные


7.7. Вычисление промежутка времени, прошедшего от точки отсчета

Из книги QNX/UNIX [Анатомия параллелизма] автора Цилюрик Олег Иванович

7.7. Вычисление промежутка времени, прошедшего от точки отсчета По разным причинам может понадобиться перейти от внутреннего (традиционного) представления времени к стандартному. В системе время хранится как число секунд, прошедших с точки отсчета.Метод класса Time.at


7.17. Вычисление разности между двумя моментами времени

Из книги Введение в QNX/Neutrino 2. Руководство по программированию приложений реального времени в QNX Realtime Platform автора Кёртен Роб

7.17. Вычисление разности между двумя моментами времени Можно вычислить интервал между двумя моментами времени. В результате вычитания одного объекта Time из другого получаем число секунд:today = Time.local(2000,11,10)yesterday = Time.local(2000,11,9)cliff = today - yesterday # 86400 секунд.И снова оказывается


Определение протокола защиты от инверсии приоритетов

Из книги Linux программирование в примерах автора Роббинс Арнольд

Определение протокола защиты от инверсии приоритетов int pthread_mutexattr_setprotocol( pthread_mutexattr_t* attr, int protocol);int pthread_mutexattr_getprotocol( pthread_mutexattr_t* attr, int* protocol);Эти функции устанавливают/считывают протокол, который реализуется мьютексом для защиты от инверсии приоритетов. Переменная protocol


Наследование приоритетов

Из книги Разработка ядра Linux автора Лав Роберт

Наследование приоритетов Одним из интересных моментов в операционных системах реального времени является феномен инверсии приоритетов.Инверсия приоритетов наблюдается, например, в случае, когда поток с низким приоритетом потребляет все процессорное время, в то время


Массивы приоритетов

Из книги автора

Массивы приоритетов Каждая очередь выполнения содержит два массива приоритетов (priority arrays): активный и истекший. Массивы приоритетов определены в файле kernel/sched.c в виде описания struct prio_array. Массивы приоритетов — это структуры данных, которые обеспечивают O(1)-планирование.


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

Из книги автора

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


Инверсия приоритетов

Из книги автора

Инверсия приоритетов Независимо от причины мы всегда находим способы избежать выполнения работы. Мы убеждаем себя, что у вас есть более срочная задача, и занимаемся ей. Это называется инверсией приоритетов: вы искусственно повышаете приоритет задачи, чтобы отложить