Базовые дисциплины планирования

Ниже приводятся описания некоторых базовых дисциплин планирования. Эти дисциплины достаточно просты в реализации и хорошо исследованы методами как аналитического (например, [12]), так и имитационного (например, [27]) моделирования. Мы называем их базовыми, поскольку в реальных системах они служат основой для построения более сложных и гибких модификаций и комбинаций, для которых аналитические модели построить, как правило, невозможно.

FCFS (first come - first serve - первым пришел - первым обслуживается) - простейшая дисциплина, работа которой понятна из ее названия. Это дисциплина без вытеснения, то есть, процесс, выбранный для выполнения на ЦП, не прерывается, пока не завершится (или не перейдет в состояние ожидания по собственной инициативе). Как дисциплина без вытеснения, FCFS обеспечивает минимум накладных расходов. Среднее потерянное время при применении этой дисциплины не зависит от длительности процесса, но штрафное отношение при равном потерянном времени будет большим для коротких процессов. Поэтому дисциплина FCFS считается лучшей для длинных процессов. Существенным достоинством этой дисциплины, наряду с ее простотой, является то обстоятельство, что FCFS гарантирует отсутствие бесконечного откладывания процессов: любой поступивший в систему процесс в конце концов будет выполнен независимо от степени загрузки системы.

На рисунке 2.2 показан пример планирования по дисциплине FCFS для трех процессов - A, B и C. На временной диаграмме каждый прямоугольник представляет интервал времени, в течение которого процесс находится в системе. Над верхним левым углом такого прямоугольника указан идентификатор процесса, а в скобках - его длительность. Незатемненные участки соответствуют активному состоянию процесса, затемненные - состоянию ожидания. Процесс A поступает в момент времени 0 и требует для выполнения 6 единиц процессорного времени. ЦП в этот момент свободен, и процесс A сразу же активизируется. В момент времени 2 поступает процесс B, требующий 11 единиц. Поскольку ЦП занят процессом A, процесс B ожидает в очереди готовых процессов до момента 6, когда процесс A закончится и освободит ЦП.
Только после этого процесс B начинает выполняться. Пока процесс B выполняется, поступают еще два процесса: C - в момент времени 8 и D - в момент 10, которые ждут завершения процесса B. Когда процесс B завершится, ЦП будет отдан процессу C, поступившему раньше, а процесс D остается в ожидании. В линейке, расположенной под временной шкалой, указаны идентификаторы процессов, активных в данный момент времени. Читатель может сам определить показатели эффективности планирования - для каждого процесса и усредненные. Следует, однако, предупредить, что к усредненным показателям надо относиться с осторожностью, так как достоверными могут считаться только результаты, полученные на статистически значимой выборке.

Рис.2.2. Планирование процессов по дисциплине FCFS

RR (round robin - карусель) - простейшая дисциплина с вытеснением. Процесс получает в свое распоряжение ЦП на некоторый квант времени Q (в простейшем случае размер кванта фиксирован). Если за время Q процесс не завершился, он вытесняется из ЦП и направляется в конец очереди готовых процессов, где ждет выделения ему следующего кванта, и т.д. Показатели эффективности RR существенно зависят от выбора величины кванта Q. RR обеспечивает наилучшие показатели, если длительность большинства процессов приближается к размеру кванта, но не превосходит его. Тогда большинство процессов укладываются в один квант и не становятся в очередь повторно. При величине кванта, стремящейся к бесконечности, RR вырождается в FCFS. При Q, стремящемся к 0, накладные расходы на переключение процессов возрастают настолько, что поглощают весь ресурс ЦП. RR обеспечивает наилучшие показатели справедливости: штрафное отношение P на большом участке длительностей процессов t остается практически постоянным. Только на участке t < Q штрафное отношение начинает изменяться и при уменьшении t от Q до 0 возрастает экспоненциально. Потерянное же время M существенно растет с увеличением длительности процесса.

На рисунке 2.3 показаны примеры планирования по дисциплине RR с разными величинами кванта Q=1 (рис.2.3.а) и Q=4 (рис.2.3.б).

Рассмотрим подробнее работу на начальном временном участке рис.2.3.а. Процесс A поступает в момент времени 0 и получает квант времени ЦП. К моменту окончания кванта в очереди уже есть процесс B. Процесс A отправляется в очередь, а следующий квант получает процесс B. В момент времени 2 процесс B направляется в очередь, а из очереди выбирается процесс A. В этот же момент поступает новый процесс - C. Этот процесс ставится в конец очереди, а первым в очереди стоит процесс A, поэтому следующий квант отдается процессу A и т.д. Предоставляем читателю самостоятельно закончить рассмотрение этого примера, а также примера, показанного на рис. 2.3.б.

Рис.2.3. Планирование процессов по дисциплине RR

SJN (shortest job next - самая короткая работа - следующая) - невытесняющая дисциплина, в которой наивысший приоритет имеет самый короткий процесс. Для того, чтобы применять эту дисциплину, должна быть известна длительность процесса - задаваться пользователем или вычисляться методом экстраполяции. Для коротких процессов SJN обеспечивает лучшие показатели, чем RR, как по потерянному времени, так и по штрафному отношению. SJN обеспечивает максимальную пропускную способность системы - выполнение максимального числа процессов в единицу времени, но показатели для длинных процессов значительно худшие, а при высокой степени загрузки системы активизация длинных процессов может откладываться до бесконечности. Штрафное отношение слабо изменяется на основном интервале значений t, но значительно возрастает для самых коротких процессов: такой процесс при поступлении в систему имеет самый высокий приоритет, но вынужден ждать, пока закончится текущий активный процесс.

Пример планирования по этой дисциплине показан на рисунке 2.4. Поступивший в момент времени 0 процесс A захватывает ЦП. Процесс B, поступивший в момент 1, вынужден ждать освобождения ЦП процессом A, хотя процесс B и более короткий. К моменту 6 - освобождения ЦП - из двух имеющихся в очереди процессов (B и C) выбирается более короткий процесс B.

Процесс C получает ЦП только в момент времени 9, когда заканчивается процесс B. Когда в момент времени 16 процесс C освобождает ЦП, из двух имеющихся в очереди процессов выбирается более короткий процесс E, хотя он поступил позже, чем процесс D.

Рис.2.4. Планирование процессов по дисциплине SPN

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

Рассмотрим пример, представленный на рисунке 2.5. Процесс A поступает в систему первым и успевает использовать единицу времени ЦП прежде, чем в систему приходит процесс B. Процесс B требует 3 единицы процессорного времени, а процессу A осталось использовать еще 5 единиц. Процесс A вытесняется, ЦП отдается процессу B. При освобождении ЦП в очереди уже есть и процесс C, но его длительность больше, чем остаток времени процесса A, поэтому процесс C получает ЦП только в момент времени 9, когда процесс A завершится. Процесс C успевает использовать только одну единицу времени ЦП, когда приходит короткий процесс E и вытесняет процесс C из ЦП. Выполнение C вновь откладывается до освобождения ЦП, которое происходит в момент 14. В момент 17 приходит процесс D. Его длительность (6) меньше, чем полная длительность процесса C (7), но к этому времени процесс C уже использовал 4 единицы времени ЦП, и для завершения ему необходимо еще только 4 единицы, поэтому процесс D не вытесняет процесс C.

Рис.2.5. Планирование процессов по дисциплине PSPN

HPRN (highest penalty ratio next - с наибольшим штрафным отношением - следующий) - дисциплина без вытеснения, обеспечивающая наилучшие показатели справедливости. Это достигается за счет динамического переопределения приоритетов. Всякий раз при освобождении ЦП для всех готовых процессов вычисляется текущее штрафное отношение:

p[i]=(w[i]+t[i]) / t[i]

где i - номер процесса; w[i] - время, затраченное процессом на ожидание; t[i] - длительность процесса - предзаданная или прогнозируемая. Для только что поступившего процесса p[i]=1. ЦП отдается процессу, имеющему наибольшее значение p[i]. Для коротких процессов HPRN обеспечивает примерно те же показатели справедливости, что и SJN, для длинных - более близкие к FCFS. На большом диапазоне средних длительностей процессов показатели, обеспечиваемые HPRN, представляют среднее между SJN и FCFS и слабо зависят от длительности. Еще одно достоинство HPRN - в том, что во времени ожидания может учитываться (с некоторыми весовыми коэффициентами) и ожидание в других очередях и, таким образом, выполняется более комплексный учет загрузки системы. Существенным недостатком метода является необходимость перевычисления штрафного отношения для всех процессов при каждом переключении, что плохо согласуется с общей политикой минимизации накладных расходов в дисциплинах без вытеснения.

В примере, показанном на рисунке 2.6, под временной шкалой даны текущие значения штрафного отношения для процессов-претендентов в те моменты времени, когда выполняется переключение. Так, в момент времени 6 два процесса - B и C - претендуют на использование ЦП. Текущее штрафное отношение для процесса B составляет:

p[B]=(5+3)/3=2.33,

а для процесса C:

p[C]=(3+7)/7=1.43;

следовательно, ЦП отдается процессу B. Аналогичные вычисления производятся в моменты времени 9 и 16.

Рис.2.6. Планирование процессов по дисциплине HPRN

SRR (selfish RR - эгоистичный RR) - метод с вытеснением, дающий дополнительные преимущества выполняемым процессам, что позволяет повысить пропускную способность. Все процессы разделяются на две категории - новые и выбранные. Новыми считаются те процессы, которые не получили еще ни одного кванта времени ЦП, все остальные процессы - выбранные. При поступлении в систему каждому процессу дается некоторый приоритет P0, одинаковый для всех процессов, который в дальнейшем возрастает.

В конце каждого кванта времени пересчитываются приоритеты всех процессов, причем приоритеты новых процессов возрастают на величину dA, а выбранных - на величину dB. ЦП отдается процессу с наивысшим приоритетом, а при равенстве приоритетов - тому, который раньше поставлен в очередь. Показатели дисциплины существенно зависят от выбранного соотношения между dA и dB. При dB/dA=1 дисциплина вырождается в обыкновенную RR, при dB >> dA - в FCFS. Собственно дисциплина SRR обеспечивается в диапазоне значений 0<dB/dA<1.

Рассмотрим работу дисциплины на примере, показанном на рисунке 2.7. Параметры дисциплины в этом примере:

P0=0; dA=2; dB=1; Q=1.

Рис.2.7. Планирование процессов по дисциплине SRR

Под временной шкалой здесь показаны текущие значения приоритетов процессов. Процесс A при поступлении получает приоритет 0. Поскольку на этот момент других процессов нет, процесс A начинает выполняться. Получив ЦП, процесс A попадает в категорию выбранных, поэтому при окончании кванта в момент 1 приоритет процесса A возрастает на 1. В момент 1 поступает процесс B, ему присваивается начальный приоритет 0, на текущий момент это ниже, чем приоритет A, поэтому ЦП остается у процесса A. По прошествии еще одного кванта, к моменту времени 2 приоритет процесса A увеличивается еще на 1 и становится равным 2, но приоритет процесса B, как нового, увеличивается на 2 и становится равным приоритету A. По принципу RR ЦП отдается процессу B, как дольше ожидающему. Процесс B теперь также становится выбранным и в дальнейшем его приоритет растет медленнее. Поступающий позже новый процесс C имеет нулевой начальный приоритет и вынужден ждать 3 кванта, пока его приоритет не сравняется с приоритетами выбранных процессов. Аналогичным образом происходит обслуживание и остальных поступающих процессов.

FB (foreground-background - передний-задний планы) - очередь готовых процессов расщепляется на две подочереди - очередь переднего плана и очередь заднего плана. Очереди обслуживаются по дисциплине RR, но очередь переднего плана имеет абсолютный приоритет: пока в ней есть процессы, очередь заднего плана не обслуживается.

Новый процесс направляется в очередь переднего плана. Если процесс использовал установленное число N квантов в очереди переднего плана, но не завершился, он переводится в очередь заднего плана.

Обобщение дисциплины FB на n очередей с номерами 0, 1, ..., n-1 и с абсолютными приоритетами, убывающими при возрастании номера очереди, носит название MLFB (multiply level feed back - многоуровневые очереди с обратной связью). Расщепление очереди готовых процессов на две и более подочереди обеспечивает селекцию процессов по длительности - более длинные процессы попадают в очереди с большими номерами и, соответственно, с меньшими приоритетами. Дисциплина MLFB очень эффективна для систем, работающих в интерактивном режиме.

На рисунке 2.8 показаны примеры работы MLFB для N=1. Под временной шкалой показаны состояния процессов в каждый момент времени: "а" - для активного процесса и номер очереди - для неактивного. Процесс A поступает в очередь 0 и, поскольку ЦП свободен, сразу же выбирается из нее на выполнение. После использования одного кванта времени ЦП процесс A переводится в очередь 1. В этот момент (момент 1) в очередь 0 поступает процесс B. Поскольку очередь 0 имеет более высокий приоритет, чем очередь 1, на выполнение выбирается процесс B. Процесс B после использования кванта (момент 2) попадает также в очередь 1. Поскольку в момент времени 2 очередь 0 пуста, обслуживается очередь 1, из нее выбирается процесс A, который был поставлен в эту очередь раньше, чем процесс B. После этого кванта (момент 3) процесс A переходит в очередь 2, а в очереди 0 появляется новый процесс C, которому и будет отдан следующий квант. После этого кванта (момент 4) процесс C будет направлен в очередь 1. На этот момент времени мы имеем 3 процесса: процесс A в очереди 2, процесс B в очереди 1 и процесс C в очереди 1. Обслуживается очередь 1, процесс B попал в эту очередь раньше, он получает следующий квант и т. д.

Рис.2.8. Планирование процессов по дисциплине MLFB

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

наряду с предпочтительным обслуживанием высокоприоритетной очереди предоставлять (но с меньшей частотой) кванты времени и очередям с низкими приоритетами;
выполнять обратное перемещение процесса в очередь с меньшим номером после того, как процесс прождал установленный интервал времени в низкоприоритетной очереди;
установить размер кванта зависящим от номера очереди, например: Q[n]=q*n или Q[n]=q*2n; поскольку в очереди с большими номерами попадают более длинные процессы, их обслуживание с большим квантом позволит сэкономить расходы на переключение;
обслуживать разные очереди по разным дисциплинам (например: RR - для первой очереди, FCFS - для второй).

Содержание раздела