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

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

• установить размер кванта зависящим от номера очереди, например:

Q[n]=q*n или Q[n]=q*2

; поскольку в очереди с большими

номерами попадают более длинные процессы, их обслуживание с

большим квантом позволит сэкономить расходы на переключение;

• обслуживать разные очереди по разным дисциплинам (например: RR –

для первой очереди, FCFS – для второй).

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

Как мы отмечали выше, в реальных ОС при планировании

процессорного времени применяются модификации и/или комбинации

базовых алгоритмов, обеспечивающие большую эффективность и

гибкость. Можно утверждать, что в реальных ОС применяются почти

исключительно комбинированные методы, учитывающие как внешние

приоритеты, так и поведение процесса, и степень загрузки ЦП, и,

возможно, других ресурсов системы. Можно также утверждать, что

дисциплины планирования без вытеснения в ОС общего назначения

бесперспективны. Доживающая свой век Windows 3.x и Mac OS –

последние из современных ОС, применяющая кооперативную

многозадачность.

По-видимому, в ближайшее время наиболее интенсивно будут

применяться и развиваться интерактивные ОС и ОС, обеспечивающие

режим клиент/сервер, поэтому современные ОС применяют дисциплины,

отдающие предпочтение обменным процессам. Для таких ОС достаточно

типичной можно считать следующую макросхему определения

приоритетов процессов в очереди к ЦП. Наивысший абсолютный

приоритет имеют системные процессы, которые не могут вытесняться.

Далее следуют системные процессы, которые могут быть вытеснены.

Наконец, низший приоритет имеют пользовательские процессы.

Пользовательские процессы в свою очередь могут делиться на классы.

Типовое деление включает в себя три класса:

• с высоким приоритетом – процессы реального времени;

• со средним приоритетом – интерактивные процессы;

• с низким приоритетом – счетные (пакетные) процессы.

Внутри каждого класса предусматривается еще несколько градаций

приоритета, которые могут назначаться пользователем. Наконец, ОС

может формировать еще динамическую добавку к приоритету, зависящую

от истории выполнения процесса, текущего состояния ресурсов и т.д. Эта

добавка может повышать или снижать приоритет процесса внутри класса,

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

Динамическая составляющая совершенно необходима для процессов

класса с нормальным приоритетом (интерактивных), так как их поведение

во время выполнения наиболее трудно предсказать. Процессы других

классов ОС может планировать и по статическим приоритетам.

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

можно свести к следующим:

• приоритет процесса, долгое время находящегося в состоянии

ожидания, повышается;

• приоритет процесса, часто выполняющего операции ввода-

вывода, повышается;

• приоритет процесса, чаще получающего внешние сообщения и

прерывания, повышается;

• если приоритет процесса не повышается, он убывает.

Ниже мы рассматриваем два примера динамического вычисления

приоритетов. Еще раз подчеркнем, что рассматриваемые нами алгоритмы

относятся только к пользовательским процессам: системные процессы

имеют абсолютный и более высокий приоритет.

ОС Unix [33] – система многопользовательская и многозадачная,

ориентированная, прежде всего, на интерактивную работу – дает пример

изящного алгоритма динамического вычисления приоритетов,

называемого иногда "алгоритмом полураспада" – модификацию

дисциплины 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 "тикам" таймера.

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

Поскольку Unix не накладывает ограничений на количество

процессов, порождаемых одним пользователем, для ОС может оказаться

более важным справедливое распределение ЦП не между процессами, а

между пользователями. Эта задача решается незначительной

модификацией алгоритма. С каждым процессом связывается еще и

групповой счетчик процессорного времени G[i]. Этот счетчик с каждым

"тиком" таймера увеличивается на 1 как в активном процессе, так и во всех

процессах, принадлежащих тому же пользователю. В конце кванта G[i]

также "полураспадается", а приоритетное число вычисляется как

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

ОС VM/370 [28] демонстрирует нам значительно более сложный (но

и более гибкий) пример планирования, рассчитанный на одновременное

выполнение задач разных типов. Этот алгоритм можно рассматривать как

некоторую версию дисциплины MLFB. Единицей планирования ЦП в этой

ОС является виртуальная машина (ВМ). Планировщик ВМ определяет

последовательность использования ЦП виртуальными машинами и

длительность этого использования. Последовательность определяется

положением ВМ в очередях планировщика, длительность – величиной

кванта и частотой его получения.

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

• равномерное (на некотором интервале времени) использование

ЦП всеми ВМ;

• обеспечение гарантированного времени ответа при заданной

загрузке системы;

• соблюдение нормативов потерь на страничный обмен (о

страничном обмене – см. главу 3).

Для выполнения этих требований планировщик периодически

вычисляет затраты на страничный обмен и среднее время использования

ЦП одной ВМ, а также постоянно ведет для каждой ВМ учет

использованного ею процессорного времени и времени пребывания в

очередях.

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

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

состояний, показанных на рисунке 2.10.

Непланируемыми называются ВМ, ожидающие завершения операции

ввода-вывода на реальном внешнем устройстве или какого-либо другого

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

планировщика.

Планируемые – все остальные ВМ – могут быть активными или

неактивными. Активной является ВМ, попавшая в очередь на

обслуживание RUNLIST. Размер этой очереди ограничен соображениями

эффективности страничного обмена. Все ВМ, не попавшие в эту очередь

из-за ее ограниченности, являются неактивными. По мере разгрузки

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

Активные ВМ, в свою очередь, подразделяются на диспетчируемые и

недиспетчируемые. Диспетчируемые ВМ – это те, которые полностью

готовы получить ЦП. Недиспетчируемой является ВМ, для которой:

• моделируется выполнение привилегированной команды;

• или моделируется выполнение операции ввода-вывода без

связи с реальным устройством (см. главу 6);

• или обрабатывается страничный отказ.

Кроме этой, основной классификации, планируемые ВМ

подразделяются на диалоговые, недиалоговые и чисто пакетные. Для

некоторых статусов ВМ установлены следующие обозначения:

• Q1 – диалоговые активные;

• Q2 – недиалоговые активные;

• Q3 – пакетные активные;

• E1 – диалоговые неактивные;

• E2 – недиалоговые неактивные.

Все активные ВМ находятся в очереди RUNLIST, но статус ВМ

влияет на ее положение в очереди. Для неактивных ВМ существуют две

разные очереди: очередь E1 и очередь E2.

При пополнении очереди RUNLIST абсолютный приоритет имеет

очередь E1, ВМ из очереди E2 переводятся в RUNLIST только, если

очередь E1 пуста.

Новые ВМ (не показано на рисунке) вначале поступают в очередь

RUNLIST, а при ее заполнении – в очередь E2. При попадании ВМ в

очередь RUNLIST ей назначается размер кванта dt и квота обслуживания

dT – интервал времени ЦП, который ВМ может использовать, планируясь

из очереди RUNLIST. Начальное значение кванта устанавливается равным

фиксированному значению dt

, в дальнейшем оно может быть изменено

по таким правилам:

• квант сохраняется равным dt

, если на предыдущем кванте не

было прерывания по вводу-выводу,

• квант назначается равным 4*dt

в противном случае.

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

• 8*dt для ВМ статуса Q1;

• 64*dt для ВМ статуса Q2;

• 512*dt для ВМ статуса Q3.

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

недиалоговые, но получают их чаще.

Очередность предоставления ЦП диспетчируемым ВМ определяется

связанным с каждой ВМ приоритетным числом (чем оно меньше, тем

выше приоритет ВМ). Начальное значение приоритетного числа

определяется временем поступления ВМ в систему. Таким образом, та ВМ,

сеанс на которой начался раньше, имеет более высокий приоритет. В

дальнейшем планировщик формирует динамическую добавку к

приоритетному числу, которая может его существенно изменять. Величина

добавки зависит от поведения ВМ, которое мы рассмотрим, обращаясь к

схеме на рисунке 2.11, где показана схема движения ВМ между ЦП и

очередями планировщика.

Рисунок 2.11 Планирование виртуальных машин в ОС VM/370

Из диспетчируемых ВМ в очереди RUNLIST выбирается ВМ с

высшим приоритетом, и ей выделяется квант времени ЦП – dt. ВМ может

освободить ЦП по одной из следующих причин:

• ВМ запрашивает операцию ввода-вывода, выполняющуюся на

реальном внешнем устройстве (1 на рисунке 2.11), такая ВМ

становится непланируемой и исключается из очередей

планировщика;

• ВМ исчерпала квант времени ЦП (2 на рисунке 2.11) – для этого

случая проверяется, исчерпала ли ВМ квоту обслуживания dT (5

на рисунке 2.11); если квота не исчерпана, ВМ возвращается в

очередь RUNLIST, но ее приоритетное число несколько

увеличивается; если же квота исчерпана, ВМ получает статус

недиалоговой и направляется в очередь E2;

• ВМ запрашивает операцию, которую моделирует для нее ОС VM

без использования реального внешнего устройства, или для ВМ

обрабатывается страничный отказ (3 на рисунке 2.11), такая ВМ

переводится в состояние ожидания (устанавливается

соответствующий бит в ее виртуальном PSW), она остается в

очереди RUNLIST, но становится недиспетчируемой.

ВМ, ставшие непланируемыми, ожидают в других очередях ОС,

которые не имеют отношения к планировщику. Когда завершается

операция ввода-вывода для такой ВМ (4 на рисунке 2.11), эта ВМ получает

статус диалоговой и направляется в очередь E1. При этом приоритетное

число ВМ перевычисляется с учетом:

• старого приоритета;

• времени предыдущего ухода ВМ из очереди RUNLIST;

• времени, потерянного ВМ в очередях планировщика.

Новое значение приоритета определяет порядок выборки ВМ из

очереди E1 в очередь RUNLIST и сохраняется за ВМ при переводе ее в

очередь RUNLIST.

ВМ, получившие статус недиспетчируемых, ожидают, когда ОС

переведет их виртуальное PSW из состояния ожидания в состояние счета

(6 на рисунке 2.11). После этого такая ВМ переводится в очередь E2.

Таким образом, ВМ может попасть в очередь E2 либо по исчерпанию

квоты обслуживания, либо по выполнению операций ОС. При постановке

в очередь E2 приоритетное число перевычисляется с учетом:

• старого приоритета;

• эффективности использования ВМ памяти;

• времени пребывания ВМ в очередях;

• штрафа, накладываемого на ВМ, если она превысила среднее

время использования процессора.

Те ВМ, которые 6 раз переходили из очереди E2 в очередь RUNLIST,

минуя очередь E1, получают статус чисто пакетных и добавка к

приоритетному числу для них в 8 раз больше, чем для диалоговых.

Всякий раз, когда какая-либо ВМ покидает очередь RUNLIST, ОС

пытается пополнить последнюю из очередей неактивных ВМ.

Возможность пополнения очереди RUNLIST определяется

эффективностью управления памятью в соответствии с политикой

"размера рабочего набора", рассматриваемой в следующей главе.

В современных версиях VM сохранились основные черты

приведенного алгоритма, но развитие аппаратных средств мейнфреймов и

передача им некоторых задач управления производительностью позволили

значительно его упростить.

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

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

Методы, рассмотренные нами, могут применяться и на других уровнях

планирования. Не всегда, правда, можно провести четкую границу между

уровнями планирования. Те или иные методы вычисления приоритета

доступа к другим (кроме ЦП) ресурсам могут использоваться для

формирования динамической добавки к приоритету процесса в очереди

готовых процессов или/и влиять на параметры дисциплины планирования

(как мы видели для ОС VM/370, где в планировании ВМ учитываются и

соображения управления памятью).

В тех случаях, когда среднесрочное планирование осуществляется

отдельными планировщиками соответствующих ресурсов, применяются

обычно базовые дисциплины планирования без вытеснения, поскольку

планируемые ресурсы часто не являются повторно используемыми.

Дисциплина SJR применяется обычно к тем ресурсам, которые являются