Операционные системы. Управление ресурсами

         

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


Как мы отмечали выше, в реальных ОС при планировании процессорного времени применяются модификации и/или комбинации базовых алгоритмов, обеспечивающие большую эффективность и гибкость. Можно утверждать, что в реальных ОС применяются почти исключительно комбинированные методы, учитывающие как внешние приоритеты, так и поведение процесса, и степень загрузки ЦП, и, возможно, других ресурсов системы. Можно также утверждать, что дисциплины планирования без вытеснения в ОС общего назначения бесперспективны. Доживающая свой век 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. Единицей планирования ЦП в этой ОС является виртуальная машина (ВМ). Планировщик ВМ определяет последовательность использования ЦП виртуальными машинами и длительность этого использования. Последовательность определяется положением ВМ в очередях планировщика, длительность - величиной кванта и частотой его получения.

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


  • равномерное (на некотором интервале времени) использование ЦП всеми ВМ;
  • обеспечение гарантированного времени ответа при заданной загрузке системы;
  • соблюдение нормативов потерь на страничный обмен (о страничном обмене - см. главу 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, где показана схема движения ВМ между ЦП и очередями планировщика.



  • выполнение операции в/в на реальном ВУ
  • исчерпан квант dt
  • привилегированная команда или в/в без реального ВУ или страничный отказ
  • завершение в/в на реальном ВУ
  • исчерпана квота обслуживания dT ?
  • завершение операции ОС VM

    Рис.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/ESA сохранились основные черти приведенного алгоритма, но развитие аппаратных средств System/390 и передача им некоторых задач управления производительностью позволили значительно его упростить.




    Содержание раздела