Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем

Подождите немного. Документ загружается.

откладывания процессов: любой поступивший в систему процесс будет в

конце концов выполнен независимо от степени загрузки системы.

На рисунке 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=0 дисциплина вырождается в обыкновенную RR, при dB/dA>=1

– в 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 (multiplylevel 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,

например, такие:

• наряду с предпочтительным обслуживанием высокоприоритетной

очереди предоставлять (но с меньшей частотой) кванты времени и

очередям с низкими приоритетами;

• выполнять обратное перемещение процесса в очередь с меньшим

номером после того, как процесс прождал установленный интервал

времени в низкоприоритетной очереди;