Операционные системы. Управление ресурсами
Планирование процессов в реальных системах
Как мы отмечали выше, в реальных ОС при планировании процессорного времени применяются модификации и/или комбинации базовых алгоритмов, обеспечивающие большую эффективность и гибкость. Можно утверждать, что в реальных ОС применяются почти исключительно комбинированные методы, учитывающие как внешние приоритеты, так и поведение процесса, и степень загрузки ЦП, и, возможно, других ресурсов системы. Можно также утверждать, что дисциплины планирования без вытеснения в ОС общего назначения бесперспективны. Доживающая свой век 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) |
Планирование осуществляется, исходя из таких требований:
- равномерное (на некотором интервале времени) использование ЦП всеми ВМ;
- обеспечение гарантированного времени ответа при заданной загрузке системы;
- соблюдение нормативов потерь на страничный обмен (о страничном обмене - см. главу 3).
Для выполнения этих требований планировщик периодически вычисляет затраты на страничный обмен и среднее время использования ЦП одной ВМ, а также постоянно ведет для каждой ВМ учет использованного ею процессорного времени и времени пребывания в очередях.
С точки зрения планировщика ВМ может находиться в одном из состояний, показанных на рисунке 2.10.
 Рис.2.10. Состояния виртуальных машин в ОС VM/370 |
Планируемые - все остальные ВМ - могут быть активными или неактивными. Активной является ВМ, попавшая в очередь на обслуживание RUNLIST. Размер этой очереди ограничен соображениями эффективности страничного обмена. Все ВМ, не попавшие в эту очередь из -за ее ограниченности, являются неактивными. По мере разгрузки очереди RUNLIST, она пополняется из очередей неактивных ВМ. Активные ВМ, в свою очередь, подразделяются на диспетчируемые и недиспетчируемые. Диспетчируемые ВМ - это те, которые полностью готовы получить ЦП. Недиспетчируемой является ВМ, для которой:
- моделируется выполнение привилегированной команды;
- или моделируется выполнение операции ввода-вывода без связи с реальным устройством (см. главу 6);
- или обрабатывается страничный отказ.
Кроме этой, основной классификации, планируемые ВМ подразделяются на диалоговые, недиалоговые и чисто пакетные. Для некоторых статусов ВМ установлены следующие обозначения:
- Q1 - диалоговые активные;
- Q2 - недиалоговые активные;
- Q3 - пакетные активные;
- E1 - диалоговые неактивные;
- E2 - недиалоговые неактивные.
Все активные ВМ находятся в очереди RUNLIST, но статус ВМ влияет на ее положение в очереди. Для неактивных ВМ существуют две разные очереди - очередь E1 и очередь E2.
При пополнении очереди RUNLIST абсолютный приоритет имеет очередь E1, ВМ из очереди E2 переводятся в RUNLIST только, если очередь E1 пуста.
Новые ВМ (не показано на рисунке) вначале поступают в очередь RUNLIST, а при ее заполнении - в очередь E2. При попадании ВМ в очередь RUNLIST ей назначается размер кванта dt и квота обслуживания dT - интервал времени ЦП, который ВМ может использовать, планируясь из очереди RUNLIST. Начальное значение кванта устанавливается равным фиксированному значению dt0, в дальнейшем оно может быть изменено по таким правилам:
- квант сохраняется равным dt0, если на предыдущем кванте не было прерывания по вводу-выводу,
- квант назначается равным 4*dt0 в противном случае.
Квота обслуживания назначается:
- 8*dt для ВМ статуса Q1;
- 64*dt для ВМ статуса Q2;
- 512*dt для ВМ статуса Q3.
Таким образом, диалоговые ВМ имеют меньшие кванты, чем недиалоговые, но получают их чаще.
Очередность предоставления ЦП диспетчируемым ВМ определяется связанным с каждой ВМ приоритетным числом (чем оно меньше, тем выше приоритет ВМ). Начальное значение приоритетного числа определяется временем поступления ВМ в систему. Таким образом, та ВМ, сеанс на которой начался раньше, имеет более высокий приоритет. В дальнейшем планировщик формирует динамическую добавку к приоритетному числу, которая может его существенно изменять. Величина добавки зависит от поведения ВМ, которое мы рассмотрим, обращаясь к схеме на рисунке 2.11, где показана схема движения ВМ между ЦП и очередями планировщика.
 Рис.2.11. Планирование виртуальных машин в ОС VM/370 |
- ВМ запрашивает операцию ввода-вывода, выполняющуюся на реальном внешнем устройстве (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/ESA сохранились основные черти приведенного алгоритма, но развитие аппаратных средств System/390 и передача им некоторых задач управления производительностью позволили значительно его упростить.
