Индекс
НазадОглавлениеВперед


Глава 2
Планирование процессов

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

2.1. Дисциплины планирования - требования, показатели, классификация

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


Рис.2.1. Представление планирования процессов в виде системы массового обслуживания

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

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

Потерянное время:

  M = T - t; 
определяет время, в течение которого процесс находился в системе, но не выполнялся.

Отношение реактивности:

  R = t / T; 
показывает долю процессорного времени (времени выполнения) в общем времени реакции.

Штрафное отношение:

  P = T / t; 
показывает, во сколько раз общее время выполнения процесса превышает необходимое процессорное время.

Средние значения величин T, M, R, P и могут служить количественными показателями эффективности. Реальные системы, как правило, ориентированы на конкретные характеристики процессов, в частности, на определенные диапазоны значений t, поэтому указанные показатели удобно рассматривать как функции длительности процесcа: T(t), M(t), R(t), P(t).

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

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

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

С точки зрения реализации дисциплины планирования подразделяются прежде всего на дисциплины вытесняющие (preemptive) и невытесняющие (non-preemptive), иначе - кооперативные (cooperative). Для первых возможно прерывание активного процесса и лишение его ресурса ЦП по инициативе планировщика, для вторых - нет. Дисциплины с вытеснением выполняют более частые переключения процессов, следовательно, имеют большие накладные расходы. Но в большинстве случаев только дисциплины с вытеснением могут обеспечить требуемые показатели справедливости обслуживания.

Другие размерности классификации дисциплин связаны со способами определения и реализации приоритетов процессов. Различают приоритеты:

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

Пусть процесс использовал S единиц времени ЦП до перехода в ожидание ввода-вывода. Тогда прогноз на следующий интервал времени ЦП, который понадобится процессу, может быть сделан так:

  E' = W1 * E + W2 * S 
где E - прогноз, сделанный на предыдущем интервале для текущего интервала, W1 и W2 - весовые коэффициенты, подбираемые так, что:
  W1 + W2 = 1 
При изменении соотношения весовых коэффициентов в сторону увеличения W2 прогноз становится более реактивным (более чувствительным к изменению поведения процесса), в обратную сторону - более инерционным.

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

Ниже приводятся описания некоторых базовых дисциплин планирования. Эти дисциплины достаточно просты в реализации и хорошо исследованы методами как аналитического (например, [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, например, такие:

2.3. Планирование процессов в реальных системах

Как мы отмечали выше, в реальных ОС при планировании процессорного времени применяются модификации и/или комбинации базовых алгоритмов, обеспечивающие большую эффективность и гибкость. Можно утверждать, что в реальных ОС применяются почти исключительно комбинированные методы, учитывающие как внешние приоритеты, так и поведение процесса, и степень загрузки ЦП, и, возможно, других ресурсов системы. Можно также утверждать, что дисциплины планирования без вытеснения в ОС общего назначения бесперспективны. Доживающая свой век Windows 3.x - последняя из современных ОС, применяющая кооперативную многозадачность.

По-видимому, в ближайшее время наиболее интенсивно будут применяться и развиваться интерактивные ОС и ОС, обеспечивающие режим клиент/сервер, поэтому современные ОС применяют дисциплины, отдающие предпочтение обменным процессам. Для таких ОС достаточно типичной можно считать следующую макросхему определения приоритетов процессов в очереди к ЦП. Наивысший абсолютный приоритет имеют системные процессы, которые не могут вытесняться. Далее - системные процессы, которые могут быть вытеснены. Наконец, низший приоритет имеют пользовательские процессы. Пользовательские процессы, в свою очередь, могут делиться на классы. Типовое деление включает в себя три класса:

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

Общие закономерности в динамическом вычислении приоритетов можно свести к следующим:

Ниже мы рассматриваем два примера динамического вычисления приоритетов. Еще раз подчеркнем, что рассматриваемые нами алгоритмы относятся только к пользовательским процессам - системные процессы имеют абсолютный и более высокий приоритет.

ОС Unix [24] - система многопользовательская и многозадачная, ориентированная прежде всего на интерактивную работу - дает пример изящного алгоритма динамического вычисления приоритетов, называемого иногда "алгоритмом полураспада" - модификацию дисциплины RR. С каждым i-ым процессом связано некоторое приоритетное число P[i]. Чем оно меньше, тем выше приоритет процесса. Каждый новый процесс получает некоторое исходное значение приоритетного числа - P0, одинаковое для всех процессов. Кроме того, с каждым процессом связан счетчик процессорного времени U[i] с исходным значением 0. Процесс с наименьшим значением P[i] получает квант времени ЦП (при равенстве приоритетных чисел ЦП отдается процессу, ожидающему дольше). За время кванта интервальный таймер выдает несколько сигналов-прерываний. По каждому такому прерыванию счетчик U[i] активного (только активного!) процесса увеличивается на 1. Использование ЦП процессом заканчивается при истечении кванта или при переходе процесса в ожидание. При этом модифицируются счетчики процессорного времени всех (в том числе и неактивных) процессов:

  U[i] = U[i] / 2 
и для всех процессов перевычисляются приоритетные числа:
  P[i] = P0 + U[i] / 2.

На рисунке 2.9 показан пример работы алгоритма полураспада для случая трех одновременно поступивших процессов A, B, C. Для этого примера мы задались начальным значением приоритетного числа P0=16 и размером кванта, равным 16 "тикам" таймера.

Поскольку Unix не накладывает ограничений на количество процессов, порождаемых одним пользователем, для ОС может оказаться более важным справедливое распределение ЦП не между процессами, а между пользователями. Эта задача решается незначительной модификацией алгоритма. С каждым процессом связывается еще и групповой счетчик процессорного времени G[i]. Этот счетчик с каждым "тиком" таймера увеличивается на 1 как у активного процесса, так и у всех процессов, принадлежащих тому же пользователю. В конце кванта G[i] также "полураспадается", а приоритетное число вычисляется, как:

  P[i] = P0 + U[i] / 2 + G[i] / 2. 


Рис.2.9. Пример применения алгоритма полураспада (Q=16; P0=16)

ОС VM/370 [19] демонстрирует нам значительно более сложный (но и более гибкий) пример планирования - рассчитанный на одновременное выполнение задач разных типов. Этот алгоритм можно рассматривать как некоторую версию дисциплины MLFB. Единицей планирования ЦП в этой ОС является виртуальная машина (ВМ). Планировщик ВМ определяет последовательность использования ЦП виртуальными машинами и длительность этого использования. Последовательность определяется положением ВМ в очередях планировщика, длительность - величиной кванта и частотой его получения.

Планирование осуществляется, исходя из таких требований:

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

С точки зрения планировщика ВМ может находиться в одном из состояний, показанных на рисунке 2.10.


Рис.2.10. Состояния виртуальных машин в ОС VM/370

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

Планируемые - все остальные ВМ - могут быть активными или неактивными. Активной является ВМ, попавшая в очередь на обслуживание RUNLIST. Размер этой очереди ограничен соображениями эффективности страничного обмена. Все ВМ, не попавшие в эту очередь из -за ее ограниченности, являются неактивными. По мере разгрузки очереди RUNLIST, она пополняется из очередей неактивных ВМ. Активные ВМ, в свою очередь, подразделяются на диспетчируемые и недиспетчируемые. Диспетчируемые ВМ - это те, которые полностью готовы получить ЦП. Недиспетчируемой является ВМ, для которой:

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

Все активные ВМ находятся в очереди RUNLIST, но статус ВМ влияет на ее положение в очереди. Для неактивных ВМ существуют две разные очереди - очередь E1 и очередь E2.

При пополнении очереди RUNLIST абсолютный приоритет имеет очередь E1, ВМ из очереди E2 переводятся в RUNLIST только, если очередь E1 пуста.

Новые ВМ (не показано на рисунке) вначале поступают в очередь RUNLIST, а при ее заполнении - в очередь E2. При попадании ВМ в очередь RUNLIST ей назначается размер кванта dt и квота обслуживания dT - интервал времени ЦП, который ВМ может использовать, планируясь из очереди RUNLIST. Начальное значение кванта устанавливается равным фиксированному значению dt0, в дальнейшем оно может быть изменено по таким правилам:

Квота обслуживания назначается:

Таким образом, диалоговые ВМ имеют меньшие кванты, чем недиалоговые, но получают их чаще.

Очередность предоставления ЦП диспетчируемым ВМ определяется связанным с каждой ВМ приоритетным числом (чем оно меньше, тем выше приоритет ВМ). Начальное значение приоритетного числа определяется временем поступления ВМ в систему. Таким образом, та ВМ, сеанс на которой начался раньше, имеет более высокий приоритет. В дальнейшем планировщик формирует динамическую добавку к приоритетному числу, которая может его существенно изменять. Величина добавки зависит от поведения ВМ, которое мы рассмотрим, обращаясь к схеме на рисунке 2.11, где показана схема движения ВМ между ЦП и очередями планировщика.


  1. выполнение операции в/в на реальном ВУ
  2. исчерпан квант dt
  3. привилегированная команда или в/в без реального ВУ или страничный отказ
  4. завершение в/в на реальном ВУ
  5. исчерпана квота обслуживания dT ?
  6. завершение операции ОС VM
Рис.2.11. Планирование виртуальных машин в ОС VM/370

Из диспетчируемых ВМ в очереди RUNLIST выбирается ВМ с высшим приоритетом, и ей выделяется квант времени ЦП - dt. ВМ может освободить ЦП по одной из следующих причин:

ВМ, ставшие непланируемыми, ожидают в других очередях ОС, которые не имеют отношения к планировщику. Когда завершается операция ввода-вывода для такой ВМ (4 на рис.2.11), эта ВМ получает статус диалоговой и направляется в очередь E1. При этом приоритетное число ВМ перевычисляется с учетом:

Новое значение приоритета определяет порядок выборки ВМ из очереди E1 в очередь RUNLIST и сохраняется за ВМ при переводе ее в очередь RUNLIST.

ВМ, получившие статус недиспетчируемых, ожидают, когда ОС переведет их виртуальное PSW из состояния ожидания в состояние счета (6 на рис.2.11). После этого такая ВМ переводится в очередь E2. Таким образом, ВМ может попасть в очередь E2 либо по исчерпанию квоты обслуживания, либо по выполнению операций ОС. При постановке в очередь E2 приоритетное число перевычисляется с учетом:

Те ВМ, которые 6 раз переходили из очереди E2 в очередь RUNLIST, минуя очередь E1, получают статус чисто пакетных и добавка к приоритетному числу для них в 8 раз больше, чем для диалоговых.

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

В VM/ESA сохранились основные черти приведенного алгоритма, но развитие аппаратных средств System/390 и передача им некоторых задач управления производительностью позволили значительно его упростить.

2.4. Другие уровни планирования

Выше мы сосредоточились только на краткосрочном планировании. Методы, рассмотренные нами, могут применяться и на других уровнях планирования. Не всегда, правда, можно провести четкую границу между уровнями планирования. Те или иные методы вычисления приоритета доступа к другим (кроме ЦП) ресурсам могут использоваться для формирования динамической добавки к приоритету процесса в очереди готовых процессов или/и влиять на параметры дисциплины планирования (как мы видели для ОС VM/370, где в планировании ВМ учитываются и соображения управления памятью).

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

Долгосрочное планирование может также рассматриваться как вариант среднесрочного: новый процесс ожидает получения ресурсов (а таким ресурсом может быть и свободная запись в системной таблице процессов). В явном виде долгосрочное планирование выполняется в системах пакетной обработки и на уровне не процессов, а заданий. Пакетное задание (batch job) - единица работы с точки зрения пользователя. Задание подразумевает выполнение одного или нескольких процессов. В долгосрочном планировании ведущую роль играют внешние приоритеты, назначаемые пользователем и администратором. Дисциплины обслуживания очереди заданий могут меняться в зависимости от характеристик потока задач, решаемых системой, от привилегий работающих в системе пользователей, от времени суток. Так, для вычислительных центров, работавших в пакетном режиме, было характерным обслуживание в дневное время коротких заданий по дисциплине SJN - чтобы обслужить максимальное число пользователей в течение рабочего дня, а в ночное время - счет длинных заданий, выбираемых по дисциплине FCFS - чтобы обеспечить минимальные потери процессорного времени.

Контрольные вопросы

  1. Какие требования предъявляются к дисциплинам планирования процессов? Назовите те пары требований, которые кажутся Вам взаимоисключающими.
  2. Если ОС применяет дисциплину планирования с абсолютными приоритетами, то каким образом может получить процессор низкоприоритетный процесс?
  3. Каковы показатели эффективности планирования процессов? Поясните их смысл для пользователя. Какие характеристики процессов являются существенными с точки зрения планирования?
  4. В чем состоят достоинства, дисциплины FCFS, обеспечивающие ее частое применение?
  5. Дисциплина планирования RR обеспечивает практически постоянное значение показателя P(t) на широком диапазоне значений t, но на краях этого диапазона значение P(t) резко возрастает. Объясните причину этого.
  6. Предложите различные варианты обслуживания очередей на разных уровнях для дисциплины MLFB и обоснуйте их.
  7. С каким из базовых алгоритмов планирования Вы можете связать алгоритм полураспада, применяемый в Unix?
  8. По какой причине процесс, готовый к выполнению может быть исключен из очереди претендентов на выполнение?
  9. Должен ли приоритет процесса в очереди на выполнение использоваться и в других очередях? Приведите соображения "за" и "против".
  10. В чем преимущества и недостатки вытесняющих дисциплин планирования по сравнению с кооперативными?

НазадОглавлениеВперед
Индекс