I-02
.pdfСтраница 21 из 26 |
ПЛАНИРОВАНИЕ ПРОЦЕССОВ |
ограниченности, являются неактивными. По мере разгрузки очереди 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 в противном случае.
Страница 22 из 26 |
ПЛАНИРОВАНИЕ ПРОЦЕССОВ |
Квота обслуживания назначается:
8*dt для ВМ статуса Q1;
64*dt для ВМ статуса Q2;
512*dt для ВМ статуса Q3.
Таким образом, диалоговые ВМ имеют меньшие кванты, чем недиалоговые, но получают их чаще.
Очередность предоставления ЦП диспетчируемым ВМ определяется связанным с каждой ВМ приоритетным числом (чем оно меньше, тем выше приоритет ВМ). Начальное значение приоритетного числа определяется временем поступления ВМ в систему. Таким образом, та ВМ, сеанс на которой начался раньше, имеет более высокий приоритет. В дальнейшем планировщик формирует динамическую добавку к приоритетному числу, которая может его существенно изменять. Величина добавки зависит от поведения ВМ, которое мы рассмотрим, обращаясь к схеме на рисунке 2.11, где показана схема движения ВМ между ЦП и очередями планировщика.
Рисунок 2.11 Планирование виртуальных машин в ОС VM/370
Страница 23 из 26 |
ПЛАНИРОВАНИЕ ПРОЦЕССОВ |
Из диспетчируемых ВМ в очереди 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. Таким образом, ВМ
Страница 24 из 26 |
ПЛАНИРОВАНИЕ ПРОЦЕССОВ |
может попасть в очередь E2 либо по исчерпанию квоты обслуживания, либо по выполнению операций ОС. При постановке в очередь E2 приоритетное число перевычисляется с учетом:
старого приоритета;
эффективности использования ВМ памяти;
времени пребывания ВМ в очередях;
штрафа, накладываемого на ВМ, если она превысила среднее время использования процессора.
Те ВМ, которые 6 раз переходили из очереди E2 в очередь RUNLIST, минуя очередь E1, получают статус чисто пакетных и добавка к приоритетному числу для них в 8 раз больше, чем для диалоговых.
Всякий раз, когда какая-либо ВМ покидает очередь RUNLIST, ОС пытается пополнить последнюю из очередей неактивных ВМ. Возможность пополнения очереди RUNLIST определяется эффективностью управления памятью в соответствии с политикой "размера рабочего набора", рассматриваемой в следующей главе.
В современных версиях VM сохранились основные черты приведенного алгоритма, но развитие аппаратных средств мейнфреймов и передача им некоторых задач управления производительностью позволили значительно его упростить.
2.4. Другие уровни планирования
Выше мы сосредоточились только на краткосрочном планировании. Методы, рассмотренные нами, могут применяться и на других уровнях планирования. Не всегда, правда, можно провести четкую границу между уровнями планирования. Те или иные методы вычисления приоритета доступа к другим (кроме ЦП) ресурсам могут использоваться для формирования динамической добавки к приоритету процесса в очереди готовых процессов или/и влиять на параметры дисциплины планирования (как мы видели для ОС
Страница 25 из 26 |
ПЛАНИРОВАНИЕ ПРОЦЕССОВ |
VM/370, где в планировании ВМ учитываются и соображения управления памятью).
В тех случаях, когда среднесрочное планирование осуществляется отдельными планировщиками соответствующих ресурсов, применяются обычно базовые дисциплины планирования без вытеснения, поскольку планируемые ресурсы часто не являются повторно используемыми. Дисциплина SJR применяется обычно к тем ресурсам, которые являются для системы узким местом, для повышения пропускной способности; дисциплина FCFS – в тех случаях, когда крайне важно избежать бесконечного откладывания. При среднесрочном планировании ведущую роль играют соображения предупреждения тупиков, рассматриваемые нами в главе 4.
Долгосрочное планирование может также рассматриваться как вариант среднесрочного: новый процесс ожидает получения ресурсов (а таким ресурсом может быть и свободная запись в системной таблице процессов). В явном виде долгосрочное планирование выполняется в системах пакетной обработки и на уровне не процессов, а заданий. Пакетное задание (batch job) – единица работы с точки зрения пользователя. Задание подразумевает выполнение одного или нескольких процессов. В долгосрочном планировании ведущую роль играют внешние приоритеты, назначаемые пользователем и администратором. Дисциплины обслуживания очереди заданий могут меняться в зависимости от характеристик потока задач, решаемых системой, от привилегий работающих в системе пользователей, от времени суток. Так, для вычислительных центров, работавших в пакетном режиме, было характерным обслуживание в дневное время коротких заданий по дисциплине SJN – чтобы обслужить максимальное число пользователей в течение рабочего дня, а в ночное время – счет длинных заданий, выбираемых по дисциплине FCFS – чтобы обеспечить минимальные потери процессорного времени.
КОНТРОЛЬНЫЕ ВОПРОСЫ
Страница 26 из 26 |
ПЛАНИРОВАНИЕ ПРОЦЕССОВ |
1.Какие требования предъявляются к дисциплинам планирования процессов? Назовите те пары требований, которые кажутся вам взаимоисключающими.
2.Если ОС применяет дисциплину планирования с абсолютными приоритетами, то каким образом может получить процессор низкоприоритетный процесс?
3.Каковы показатели эффективности планирования процессов? Поясните их смысл для пользователя. Какие характеристики процессов являются существенными с точки зрения планирования?
4.В чем состоят достоинства, дисциплины FCFS, обеспечивающие ее частое применение?
5.Дисциплина планирования RR обеспечивает практически постоянное значение показателя P(t) на широком диапазоне значений t, но на краях этого диапазона значение P(t) резко возрастает. Объясните причину этого.
6.Предложите различные варианты обслуживания очередей на разных уровнях для дисциплины MLFB и обоснуйте их.
7.С каким из базовых алгоритмов планирования вы можете связать алгоритм полураспада, применяемый в Unix?
8.По какой причине процесс, готовый к выполнению может быть исключен из очереди претендентов на выполнение?
9.Должен ли приоритет процесса в очереди на выполнение использоваться и в других очередях? Приведите соображения "за" и "против".
10.В чем преимущества и недостатки вытесняющих дисциплин планирования по сравнению с кооперативными?