Второе издание
 Скачать 3.09 Mb.
|
|
Пересчет квантов времени Во многих операционных системах (включая и более старые версии ОС Linux) используется прямой метод для пересчета значения кванта времени каждого зада- ния, когда все эти значения достигают нуля. 4 Для аппаратной платформы х86 используется инструкция bsfl, а для платформы РРС — инструк- ция cntlzw. Планирование выполнения процессов 75 Обычно это реализуется с помощью цикла по всем задачам в системе, например, следующим образом. 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)-планировщика. Вместо того чтобы все время пересчитывать значение приоритета и кванта времени для каждого процесса, О(1)-планировщик выполняет простую двухшаговую перестанов- ку массивов. Такая реализация позволяет решить указанные выше проблемы. 76 Глава 4 Функция 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_ist); Вначале осуществляется поиск в битовой маске активного массива приоритетов для нахождения номера самого первого установленного бита. Этот бит соответству- ет готовой к выполнению задаче с наивысшим приоритетом. Далее планировщик выбирает первое задание из списка заданий, которое соответствует найденному зна- чению приоритета. Это и есть задача с наивысшим значением приоритета в систе- ме, и эту задачу планировщик будет запускать на выполнение. Все рассмотренные операции показаны на рис. 4.2. schedule() Бит 0 приоритет 0 sched_find_first_set() Бит 7 приоритет 7 Список всех готовых к выполнению задач а соответствии с их приоритетами Массив приоритетов длиной 140 бит Бит 139 приоритет 139 Запуск первого процесса в списке Рис. 4.2. Алгоритм работы О(1)-планировщка операционной системы Linux Планирование выполнения процессов 77 Список готовых к выполнению заданий, имеющих приоритет 7 Если полученные значения переменных prev и next не равны друг другу, то для выполнения выбирается новое задание (next). При этом для переключения с за- дания, на которое указывает переменная prev, на задание, соответствующее пере- менной next, вызывается функция context_switch (), зависящая от аппаратной платформы. Переключение контекста будет рассмотрено в одном из следующих раз- делов. В рассмотренном коде следует обратить внимание на два важных момента. Во- первых, он очень простой и, следовательно, очень быстрый. Во-вторых, количество процессов в системе не влияет на время выполнения этого кода. Для нахождения наиболее подходящего для выполнения процесса не используются циклы. В действи- тельности никакие факторы не влияют на время, за которое функция schedule () осуществляет поиск наиболее подходящего для выполнения задания. Время выпол- нения этой операции всегда постоянно. Вычисление приоритетов и квантов времени В начале этой главы было рассмотрено, как приоритет и квант времени исполь- зуются для того, чтобы влиять на те решения, которые принимает планировщик. Кроме того, были рассмотрены процессы, ограниченные скоростью ввода-вывода и скоростью процессора, а также было описано, почему желательно поднимать при- оритет интерактивных задач. Теперь давайте рассмотрим код, который реализует эти соображения. Процессы имеют начальное значение приоритета, которое называется nice. Это значение может лежать в диапазоне от -20 до 19, по умолчанию используется зна- чение 0. Значение 19 соответствует наиболее низкому приоритету, а значение -20 — наиболее высокому. Значение параметра nice хранится в поле s t a t i c _ p r i o струк- туры t a s k _ s t r u c t процесса. Это значение называется статическим приоритетом, потому что оно не изменяется планировщиком и остается таким, каким его указал пользователь. Планировщик свои решения основывает на динамическом приорите- те, которое хранится в поле prio. Динамический приоритет вычисляется как функ- ция статического приоритета и интерактивности задания. Функция effective_prio () возвращает значение динамического приоритета за- дачи. Эта функция исходит из значения параметра пicе для данной задачи и вычисля- ет для этого значения надбавку или штраф в диапазоне от -5 до 5, в зависимости от интерактивности задачи. Например, задание с высокой интерактивностью, которое имеет значение параметра nice, равное 10, может иметь динамический приоритет, равный 5. И наоборот, программа со значением параметра nice, равным 10, которая достаточно активно использует процессор, может иметь динамический приоритет, равный 12. Задачи, которые обладают умеренной интерактивностью, не получают ни надбавки, ни штрафа, и их динамический приоритет совпадает со значением па- раметра nice. Конечно, планировщик по волшебству не может определить, какой процесс яв- ляется интерактивным. Для определения необходима некоторая эвристика, которая отражает, является ли процесс ограниченным скоростью ввода-вывода или скорос- тью процессора. Наиболее выразительный показатель — сколько времени задача на- ходится в приостановленном состоянии (sleep). Если задача проводит большую часть времени в приостановленном состоянии, то она ограничена вводом-выводом. Если задача больше времени находится в состоянии готовности к выполнению, чем в при- 78 Глава 4 остановленном состоянии, то эта задача не интерактивна. В экстремальных случаях, если задача большую часть времени находится в приостановленном состоянии, то она полностью ограничена скоростью ввода-вывода; если задача все время готова к выполнению, то она ограничена скоростью процессора. Для реализации такой эвристики в ядре Linux предусмотрен изменяемый пока- затель того, как соотносится время, которое процесс проводит в приостановлен- ном состоянии, со временем, которое процесс проводит в состоянии готовности к выполнению. Значение этого показателя хранится в поле sleep_avg структуры t a s k _ s t r u c t . Диапазон значений этого показателя лежит от нуля до значения MAX_SLEEP_AVG, которое по умолчанию равно 10 мс. Когда задача становится гото- вой к выполнению после приостановленного состояния, значение поля sleep_avg увеличивается на значение времени, которое процесс провел в приостановленном состоянии, пока значение sleep_avg не достигнет MAX_SLEEP_AVG. Когда задача выполняется, то в течение каждого импульса таймера (timer tick) значение этой пе- ременной уменьшается, пока оно не достигнет значения 0. Такой показатель является, на удивление, надежным. Он рассчитывается не толь- ко на основании того, как долго задача находится в приостановленном состоянии, но и на основании того, насколько мало задача выполняется. Таким образом, задача, которая проводит много времени в приостановленном состоянии и в то же время постоянно использует свой квант времени, не получит большой прибавки к прио- ритету: показатель работает не только для поощрения интерактивных задач, но и для наказания задач, ограниченных скоростью процессора. Этот показатель также устойчив по отношению к злоупотреблениям. Задача, которая получает повышенное Значение приоритета и большое значение кванта времени, быстро утратит свою над- бавку к приоритету, если она постоянно выполняется и сильно загружает процес- сор. В конце концов, такой показатель обеспечивает малое время реакции. Только что созданный интерактивный процесс быстро достигнет высокого значения поля sleep_avg. Несмотря на все сказанное, надбавка и штраф применяются к значению параметра nice, так что пользователь также может влиять на работу системного пла- нировщика путем изменения значения параметра nice процесса. Расчет значения кванта времени, наоборот, более прост, так как значение ди- намического приоритета уже базируется на значении параметра nice и на интерак- тивности (эти показатели планировщик учитывает как наиболее важные). Поэтому продолжительность кванта времени может быть просто выражена через значение динамического приоритета. Когда создается новый процесс, порожденный и роди- тельский процессы делят пополам оставшуюся часть кванта времени родительского процесса. Такой подход обеспечивает равнодоступность ресурсов и предотвращает возможность получения бесконечного значения кванта времени путем постоянного создания порожденных процессов. Однако после того, как квант времени задачи ис- сякает, это значение пересчитывается на основании динамического приоритета за- дачи. Функция task_timeslice () возвращает новое значение кванта времени для данного задания. Расчет просто сводится к масштабированию значения приоритета в диапазон значений квантов времени. Чем больше значение приоритета задачи, тем большей продолжительности квант времени получит задание в текущем цикле выполнения. Максимальное значение кванта времени равно MAX_TIMESLICE, кото- рое по умолчанию равно 200 мс. Даже задания с самым низким приоритетом полу- чают квант времени продолжительностью MIN_TIMESLICE, что соответствует 10 мс. Планирование выполнения процессов 79 Задачи с приоритетом, используемым по умолчанию (значение параметра nice, равно О и отсутствует надбавка и штраф за интерактивность), получают квант времени про- должительностью 100 мс, как показано в табл. 4.1. Таблица 4.1. Продолжительности квантов времени планировщика Значение параметра nice Тип задания Продолжительность кванта времени Вновь созданное То же, что и у родительского Половина от родительского процесса процесса Минимальный приоритет +19 5 мс (MIN_TIMESUCE) Приоритет по умолчанию 0 100 мс (DEF_TIMESLICE) Максимальный приоритет -20 800 мс (MAX_TIMESLICE) Для интерактивных задач планировщик оказывает дополнительную услугу: если задание достаточно интерактивно, то при исчерпании своего кванта времени оно будет помещено не в истекший массив приоритетов, а обратно в активный массив приоритетов. Следует вспомнить, что пересчет значений квантон времени произво- дится путем перестановки активного и истекшего массивов приоритетов: активный массив становится истекшим, а истекший— активным. Такая процедура обеспечива- ет пересчет значений квантов времени, который масштабируется по времени как O(1). С другой стороны, это может привести к тому, что интерактивное задание станет готовым к выполнению, но не получит возможности выполняться, так как оно "застряло" в истекшем массиве. Помещение интерактивных заданий снова в ак- тивный массив позволяет избежать такой проблемы. Следует заметить, что это зада- ние не будет выполняться сразу же, а будет запланировано на выполнение по кругу вместе с другими заданиями, которые имеют такой же приоритет. Данную логику реализует функция s c h e d u l e r _ t i c k (), которая вызывается обработчиком преры- ваний таймера (обсуждается в главе 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); } Показанный код уменьшает значение кванта времени процесса и проверяет, не стало ли это значение равным нулю. Если стало, то задание является истекшим и его необходимо поместить в один из массивов. Для этого код вначале проверяет ин- терактивность задания с помощью макроса ТАSK_INTERACTIVE (). Этот макрос на основании значения параметра nice рассчитывает, является ли задание "достаточно интерактивным". Чем меньше значение nice (чем выше приоритет), тем менее инте- рактивным должно быть задание. Задание со значением параметра nice, равным 19, никогда не может быть достаточно интерактивным для помещения обратно в актив- 80 Глава 4 ный массив. Наоборот, задание со значением nice, равным -20, должно очень сильно использовать процессор, чтобы его не поместили в активный массив. Задача со зна- чением nice, используемым по умолчанию, т.е. равным нулю, должна быть достаточно интерактивной, чтобы быть помещенной обратно в активный массив, но это также отрабатывается достаточно четко. Следующий макрос, EXPIRED_STARVING ( ) , про- веряет, нет ли в истекшем массиве процессов, особенно нуждающихся в выполнении (startving), когда массивы не переключались в течение достаточно долгого времени. Если массивы давно не переключались, то обратное помещение задачи в активный массив еще больше задержит переключение, что приведет к тому, что задачи в ис- текшем массиве еще больше будут нуждаться в выполнении. Если это не так, то за- дача может быть помещена обратно в активный массив. В других случаях задача по- мещается в истекший массив, что встречается наиболее часто. Переход в приостановленное состояние и возврат к выполнению Приостановленное состояние задачи (состояние ожидания, заблокированное состояние, sleeping, blocked) представляет собой специальное состояние задачи, в ко- тором задание не выполняется. Это является очень важным, так как в противном случае планировщик выбирал бы на выполнение задания, которые не "хотят" вы- полняться, или, хуже того, состояние ожидания должно было бы быть реализовано в виде цикла, занимающего время процессора. Задачи могут переходить в приоста- новленное состояние по нескольким причинам, но в любом случае— в ожидании наступления некоторого события. Событием может быть ожидание наступления некоторого момента времени, ожидание следующей порции данных при файловом вводе-ныводе или другое событие в аппаратном обеспечении. Задача также может переходить в приостановленное состояние непроизвольным образом, когда она пытается захватить семафор в режиме ядра (эта ситуация рассмотрена в главе 9, "Средства синхронизации в ядре"). Обычная причина перехода в приостановленное состояние — это выполнение операций файлового ввода-вывода, например задание вызывает функцию r e a d () для файла, который необходимо считать с диска. Еще один пример— задача может ожидать на ввод данных с клавиатуры. В любом случае ядро ведет себя одинаково: задача помечает себя как находящуюся в приостанов- ленном состоянии, помещает себя в очередь ожидания (wail queue), удаляет себя из очереди выполнения и вызывает функцию s c h e d u l e d для выбора нового процесса на выполнение. Возврат к выполнению (wake up) происходит в обратном порядке: задача помечает себя как готовую к выполнению, удаляет себя из очереди ожидания и помепгает себя в очередь выполнения. Как указывалось в предыдущей главе, с приостановленным состоянием связаны два значения поля состояния процесса: TASK_INTERRUPTIBLE и TASK_UNINTERRUPTIBLE. Они отличаются только тем, что в состоянии TASK_UNINTERRUPTIBLE задача игно- рирует сигналы, в то время как задачи в состоянии TASK_INTERRUPTIBLE возвраща- ются к выполнению преждевременно и обрабатывают пришедший сигнал. Оба типа задач, находящихся в приостановленном состоянии, помещаются в очередь ожида- ния, ожидают наступления некоторого события и не готовы к выполнению. Приостановленное состояние обрабатывается с помощью очередей ожидания (wait queue). Очередь ожидания— это просто список процессов, которые ожидают Планирование выполнении процессов 81 наступления некоторого события. Очереди ожидания в ядре представляются с по- мощью типа данных wait_queue_head_t. Они могут быть созданы статически с по- мощью макроса DECLARE_WAIT_QUEUE_HEAD () или выделены динамически с после- дующей инициализацией с помощью функции i n i t _ w a i t q u e u e _ h e a d (). Процессы помещают себя в очередь ожидания и устанавливают себя в приостановленное со- стояние. Когда происходит событие, связанное с очередью ожидания, процессы, на- ходящиеся в этой очереди, возвращаются к выполнению. Важно реализовать пере- ход в приостановленное состояние и возврат к выполнению правильно, так чтобы избежать конкуренции за ресурсы (race). Существуют простые интерфейсы для перехода в приостановленное состояние, и они широко используются. Однако использование этих интерфейсов может при- вести к состояниям конкуренции: возможен переход в приостановленное состоя- ние после того, как соответствующее событие уже произошло. В таком случае задача может находиться в приостановленном состоянии неопределенное время. Поэтому рекомендуется следующий метод для перехода в приостановленное состояние в ре- жиме ядра. /* пусть q — это очередь ожидания (созданная в другом месте), где мы хотим находиться в приостановленном состоянии */ DECLARE_WAITQUEUE(wait, current) ; add_wait_queue(q, &wait); set_current_State(TASK_INTERRUPTIBLE); /* или TASK_UNINTERRUPTIBLE */ /* переменная condition характеризует наступление события, которого мы ожидаем */ while (!condition) schedule() ; set_current_state(TASK_RUNNING); remove_wait queue(q, &wait); Опишем шаги, которые должна проделать задача для того, чтобы поместить себя в очередь ожидания. • Создать элемент очереди ожидания с помощью макроса DECLARE_WAITQUEUE (). • Добавить себя в очередь ожидания с помощью функции add wait_queue () . С помощью этой очереди ожидания процесс будет возвращен в состояние го- товности к выполнению, когда условие, на выполнение которого ожидает про- цесс, будет выполнено. Конечно, для этого где-то в другом месте должен быть код, который вызывает функцию wake_up () для данной очереди, когда про- изойдет соответствующее событие. • Изменить состояние процесса в значение TASK_INTERRUPTIBLE или TASK_ UNINTERRUPTIBLE. • Проверить, не выполнилось ли ожидаемое условие. Если выполнилось, то больше нет необходимости переходить в приостановленное состояние. Если нет, то вызвать функцию schedule (). • Когда задача становится готовой к выполнению, она снова проверяет выпол- нение ожидаемого условия. Если условие выполнено, то производится выход 82 Глава 4 из цикла. Если нет, то снова вызывается функция schedule () и повторяется проверка условия. • Когда условие выполнено, задача может установить свое состояние в значе- ние TASK_RUNNING и удалить себя из очереди ожидания с помощью функции remove_wait_queue(). Если условие выполнится перед тем, как задача переходит в приостановленное состояние, то цикл прервется и задача не перейдет в приостановленное состояние по ошибке. Следует заметить, что во время выполнения тела цикла код ядра часто может выполнять и другие задачи. Например, перед выполнением функции sched- ule () может возникнуть необходимость освободить некоторые блокировки и захва- тить их снова после возврата из этой функции; если процессу был доставлен сигнал, то необходимо возвратить значение -ERESTARTSYS; может возникнуть необходи- мость отреагировать на некоторые другие события. Возврат к выполнению (wake up) производится с помощью функции wake_up (), которая возвращает все задачи, ожидающие в данной очереди, в состояние готов- ности к выполнению. Вначале вызывается функция try_to_wake_up () , которая устанавливает поле состояния задачи в значение TASK_RUNNING, далее вызывается функция activate_task () для добавления задачи в очередь выполнения и устанав- ливается флаг need_resched в ненулевое значение, если приоритет задачи, которая возвращается к выполнению, больше приоритета текущей задачи. Код, который от- вечает за наступление некоторого события, обычно вызывает функцию wakeup () после того, как это событие произошло. Например, после того как данные прочи- таны с жесткого диска, подсистема VFS вызывает функцию wake_up () для очереди ожидания, которая содержит все процессы, ожидающие поступления данных. Важным может быть замечание о том, что переход в приостановленное состоя- ние часто сопровождается ложными переходами к выполнению. Это возникает по- тому, что переход задачи в состояние выполнения не означает, что событие, которо- го ожидала задача, уже наступило: поэтому переход в приостановленное состояние должен всегда выполняться в цикле, который гарантирует, что условие, на которое ожидает задача, действительно выполнилось (рис. 4.3). |