Диспетчеризация задач с использованием динамических приоритетов

При выполнении программ, реализующих какие-нибудь задачи контроля и управ­ления (что характерно, прежде всего, для систем реального времени), может слу­читься такая ситуация, когда одна или несколько задач не могут быть реализова­ны (решены) в течение длительного промежутка времени из-за возросшей нагрузки в вычислительной системе. Потери, связанные с невыполнением таких задач, могут оказаться больше, чем потери от невыполнения программ с более высоким прио­ритетом. При этом оказывается целесообразным временно изменить приоритет «аварийных» задач (для которых истекает отпущенное для них время обработки). После выполнения этих задач их приоритет восстанавливается. Поэтому почти в лю­бой операционной системе реального времени (ОС РВ) имеются средства для дина­мического изменения приоритета (dynamic priority variation) задачи. Есть такие сред­ства и во многих операционных системах, которые не относятся к классу ОС РВ.

Рассмотрим, например, как реализован механизм динамических приоритетов в опе­рационной системе UNIX, которая, как известно, не относится к ОС РВ. Операцион-

66__________________________________________ Глава 2. Управление задачами

ные системы класса UNIX относятся к мультитерминальным диалоговым системам. Основная стратегия обслуживания, применяемая в UNIX-системах, — это равенство в обслуживании и обеспечение приемлемого времени реакции системы. Реализует­ся эта стратегия за счет дисциплины диспетчеризации RR с несколькими очередями и механизма динамических приоритетов. Приоритет процесса вычисляется следую­щим образом [39]. Во-первых, в вычислении участвуют значения двух полей деск­риптора процесса — p_nice и р_сри. Первое из них назначается пользователем явно или формируется по умолчанию с помощью системы программирования. Второе поле формируется диспетчером задач (планировщиком разделения времени) и на­зывается системной составляющей или текущим приоритетом. Другими словами, каждый процесс имеет два атрибута приоритета. С учетом этого приоритета и рас­пределяется между исполняющимися задачами процессорное время: текущий при­оритет, на основании которого происходит планирование, и заказанный относи­тельный приоритет (называемый nice number, или просто nice).

Схема нумерации текущих приоритетов различна для различных версий UNIX. Например, более высокому значению текущего приоритета может соответствовать более низкий фактический приоритет планирования. Разделение между приори­тетами режима ядра и задачи также зависит от версии. Рассмотрим частный слу­чай, когда текущий приоритет процесса варьируется в диапазоне от 0 (низкий при­оритет) до 127 (наивысший приоритет). Процессы, выполняющиеся в режиме задачи, имеют более низкий приоритет, чем в режиме ядра. Для режима задачи приоритет меняется в диапазоне 0-65, для режима ядра — 66-95 (системный диа­пазон). Процессы, приоритеты которых лежат в диапазоне 96-127, являются про­цессами с фиксированным приоритетом, не изменяемым операционной системой, и предназначены для поддержки приложений реального времени.

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

После завершения системного вызова перед возвращением в режим задачи ядро восстанавливает приоритет режима задачи, сохраненный перед выполнением сис­темного вызова. Это может привести к понижению приоритета, что, в свою оче­редь, вызовет переключение контекста.

Текущий приоритет процесса в режиме задачи p_priuser, как мы только что отмеча­ли, зависит от значения относительного приоритета p_nice и степени использова­ния вычислительных ресурсов р_сри:

p_priuser = а х p_nice - b x p_cpu

Задача планировщика разделения времени — справедливо распределить вычис­лительный ресурс между конкурирующими процессами. Для принятия решения о

Диспетчеризация задач с использованием динамических приоритетов______________ 67

выборе следующего запускаемого процесса планировщику необходима информа­ция об использовании процессора. Эта составляющая приоритета уменьшается обработчиком прерываний таймера каждый тик. Таким образом, пока процесс вы­полняется в режиме задачи, его текущий приоритет линейно уменьшается.

Каждую секунду ядро пересчитывает текущие приоритеты процессов, готовых к за­пуску (приоритеты которых меньше некоторого порогового значения; в нашем примере эта величина равна 65), последовательно увеличивая их за счет последо­вательного уменьшения отрицательного компонента времени использования про­цессора. Как результат, эти действия приводят к перемещению процессов в более приоритетные очереди и повышению вероятности их последующего выполнения.

Возможно использование следующей формулы:

p_cpu = p_cpu/2

В этом правиле проявляется недостаток нивелирования приоритетов при повы­шении загрузки системы. Происходит это потому, что в таком случае каждый про­цесс получает незначительный объем вычислительных ресурсов и, следовательно, имеет малую составляющую р_сри, которая еще более уменьшается благодаря фор­муле пересчета величины р_сри. В результате загрузка процессора перестает ока­зывать заметное влияние на приоритет, и низкоприоритетные процессы (то есть процессы с высоким значением nice number) практически «отлучаются» от вычис­лительных ресурсов системы.

В некоторых версиях UNIX для пересчета значения р_сри используется другая формула:

p_cpu = p_cpu х (2 х load)/(2 х load + 1)

Здесь параметр load равен среднему числу процессов, находившихся в очереди на выполнение за последнюю секунду, и характеризует среднюю загрузку системы за этот период времени. Этот алгоритм позволяет частично избавиться от недостатка планирования по формуле p_cpu = p_cpu/2, поскольку при значительной загрузке системы уменьшение р_сри при пересчете будет происходить медленнее.

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

Аналогичные механизмы имеют место и в таких операционных системах, как OS/2 или Windows NT/2000/XP. Правда, алгоритмы изменения приоритета задач в этих системах иные. Например, в Windows NT/2000/XP каждый поток выполнения имеет базовый уровень приоритета, который лежит в диапазоне от двух уровней

68__________________________________________ Глава 2. Управление задачами

ниже базового приоритета процесса, его породившего, до двух уровней выше этого приоритета, как показано на рис. 2.4. Базовый приоритет процесса определяет, сколь сильно могут различаться приоритеты потоков этого процесса и как они соотно­сятся с приоритетами потоков других процессов. Поток наследует этот базовый приоритет и может изменять его так, чтобы он стал немного больше или немного меньше. В результате получается приоритет планирования, с которым поток и на­чинает исполняться. В процессе исполнения потока его приоритет может откло­няться от базового.

Рис. 2.4. Схема динамического изменения приоритетов в Windows NT/2000/XP

На рисунке также показан динамический приоритет потока, нижней границей ко­торого является базовый приоритет потока, а верхняя зависит от вида работ, ис­полняемых потоком. Например, если поток обрабатывает текущие результаты опе­раций ввода пользователем своих данных, диспетчер задач Windows поднимает его динамический приоритет; если же он выполняет вычисления, то диспетчер за­дач постепенно снижает его приоритет до базового. Снижая приоритет одной за­дачи и поднимая приоритет другой, подсистемы могут управлять относительной приоритетностью потоков внутри процесса.

Для определения порядка выполнения потоков диспетчер задач использует систе­му приоритетов, направляя на выполнение задачи с высоким приоритетом раньше задач с низким приоритетом. Система прекращает исполнение, или вытесняет (preempts), текущий поток, если становится готовым к выполнению другой поток с более высоким приоритетом.

Имеется группа очередей — по одной для каждого приоритета. В операционных системах Windows NT/2000/XP используется один и тот же диспетчер задач. Он поддерживает 32 уровня приоритета. Задачи делятся на два класса: реального вре­мени и переменного приоритета. Задачи реального времени, имеющие приорите­ты от 16 до 31, — это высокоприоритетные потоки, используемые программами,

Диспетчеризация задач с использованием динамических приоритетов______________ 69

критическими по времени выполнения, то есть требующими немедленного вни­мания системы (по терминологии Microsoft).

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

Большинство задач в системе относятся к классу переменного приоритета с уров­нями приоритета (номером очереди) от 1 до 15. Эти очереди используются зада­чами с переменным приоритетом (variable priority), так как диспетчер задач для оптимизации отклика системы корректирует их приоритеты по мере выполне­ния. Диспетчер приостанавливает исполнение текущей задачи, после того как та израсходует свой квант времени. При этом если прерванная задача — это поток переменного приоритета, то диспетчер задач понижает приоритет этого потока выполнения на единицу и перемещает в другую очередь. Таким образом, прио­ритет задачи, выполняющей много вычислений, постепенно понижается (до зна­чения его базового приоритета). С другой стороны, диспетчер повышает при­оритет задачи после ее освобождения из состояния ожидания. Обычно добавка к приоритету задачи определяется кодом исполнительной системы, находя­щимся вне ядра операционной системы, однако величина этой добавки зависит от типа события, которого ожидала заблокированная задача. Так, например, поток, ожидавший ввода очередного байта с клавиатуры, получает большую добавку к значению своего приоритета, чем поток ввода-вывода, работавший с дисковым накопителем. Однако в любом случае значение приоритета не мо­жет достигнуть 16.

В операционной системе OS/2 схема динамической приоритетной диспетчериза­ции несколько иная, хоть и похожа¹. В OS/2 также имеется четыре класса задач. И для каждого класса задач имеется своя группа приоритетов с интервалом значе­ний от 0 до 31. Итого, 128 различных уровней и, соответственно, 128 возможных очередей готовых к выполнению задач (потоков).

Задачи, имеющие самые высокие значения приоритета, называются критически­ми по времени (time critical). В этот класс входят задачи, которые мы в обиходе называем задачами реального времени, то есть для них должен быть обязательно предоставлен определенный минимум процессорного времени. Наиболее часто встречающимися задачами этого класса являются задачи коммуникаций (напри­мер, задача управления последовательным портом, на который приходят биты по коммутируемой линии с подключенным модемом, или задачи управления сете­вым оборудованием). Если такие задачи не получат управление в нужный момент времени, то сеанс связи может прерваться.

'' Как известно, одно время компания Microsoft принимала активное участие в разработке OS/2 со­вместно с IBM. Поэтому после прекращения совместных работ над этой операционной системой и начале нового проекта многие решения из OS/2 были унаследованы в варианте OS/2 ver. 3.0, назван­ной впоследствии Windows NT.

70__________________________________________ Глава 2. Управление задачами

Следующий класс задач имеет название приоритетного. Поскольку к этому клас­су относят задачи, которые выполняют по отношению к остальным задачам функ­ции сервера (о модели клиент-сервер, по которой строятся современные операци­онные системы с микроядерной архитектурой, см. главы 9 и 10), то его еще иногда называют серверным. Приоритет таких задач должен быть выше, поскольку это позволяет гарантировать, что запрос на некоторую функцию со стороны обычных задач выполнится сразу, а не будет дожидаться, пока до него дойдет очередь на фоне других пользовательских приложений.

Большинство задач относят к обычному классу, его еще называют регулярным (regular), или стандартным. По умолчанию система программирования порожда­ет задачу, относящуюся именно к этому классу.

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

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

OS/2 самостоятельно изменяет приоритет выполняющихся программ независимо от уровня, установленного самим приложением. Этот механизм называется повы­шением приоритета (priority boost). Операционная система изменяет приоритет задачи в трех случаях [26].

- Повышение приоритета активной задачи (foreground boost). Приоритет задачи автоматически повышается, когда она становится активной. Это снижает вре­мя реакции активного приложения на действия пользователя по сравнению с фоновыми программами.

- Повышение приоритета ввода-вывода (Input/Output boost). По завершении операции ввода-вывода задача получает самый высокий уровень приоритета ее класса. Таким образом обеспечивается завершение всех незаконченных опера­ций ввода-вывода.

- Повышение приоритета «забытой» задачи (starvation boost). Если задача не по­лучает управление в течение достаточно долгого времени (этот промежуток вре­мени задает оператор MAXWAIT в файле CONFIG.SYS¹), диспетчер задач OS/2 вре­менно присваивает ей уровень приоритета, не превышающий критический. В результате переключение на такую «забытую» программу происходит быст­рее. После выполнения приложения в течение одного кванта времени его при-

' Строка MAXWAIT = 1 означает, что приоритет задачи при переключении на нее будет поднят до максимального не позже чем через одну секунду.

Контрольные вопросы и задачи__________________________________________ 71

оритет вновь снижается до остаточного. В сильно загруженных системах этот механизм позволяет программам с остаточным приоритетом работать хотя бы в краткие интервалы времени. В противном случае они вообще никогда бы не получили управление.

Если нет необходимости использовать метод динамического изменения приори­тета, то с помощью оператора PRIOPITY = ABSOLUTE в файле CONFIG.SYS можно ввести дисциплину абсолютных приоритетов; по умолчанию оператор PRIOPITY имеет зна­чение DYNAMIC.

Контрольные вопросы и задачи

1. Перечислите и поясните основные функции операционных систем, которые
связаны с управлением задачами.

2. В чем заключается основное различие между планированием процессов и дис­
петчеризацией задач?

3. Что такое стратегия обслуживания? Перечислите известные вам стратегии об­
служивания.

4. Какие дисциплины диспетчеризации задач вы знаете? Поясните их основные
идеи, перечислите достоинства и недостатки.

5. Расскажите, какие дисциплины диспетчеризации следует отнести к вытесняю­
щим, а какие — к не вытесняющим.

6. Как можно реализовать механизм разделения времени, если диспетчер задач
работает только по принципу предоставления процессорного времени задаче с
максимальным приоритетом?

7. Что такое «гарантия обслуживания»? Как ее можно реализовать?

8. Опишите механизм динамической диспетчеризации, реализованный в UNIX-
системах.

9. Сравните механизмы диспетчеризации задач в операционных системах Windows
NT и OS/2. В чем они похожи друг на друга и в чем заключаются основные
различия?