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

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

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

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

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

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

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

p_priuser - a*p_nice - b*р_cpu

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

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

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

р_cpu = р__cpu/2

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

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

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

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

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

Аналогичные механизмы имеют место и в таких ОС, как OS/2 или Windows NT. Правда, алгоритмы изменения приоритета задач в этих системах иные. Напри­мер, в Windows NT каждый поток (тред) имеет базовый уровень приоритета, ко­торый лежит в диапазоне от двух уровней ниже базового приоритета процесса, его породившего, до двух уровней выше этого приоритета, как показано на рис. 2.4. Базовый приоритет процесса определяет, сколь сильно могут различаться при­оритеты потоков процесса и как они соотносятся с приоритетами потоков дру­гих процессов. Поток наследует этот базовый приоритет и может изменять его так, чтобы он стал немного больше или немного меньше. В результате получает­ся приоритет планирования, с которым поток и начинает исполняться. В процес­се исполнения потока его приоритет может отклоняться от базового.

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

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

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

Существует группа очерёдей – по одной для каждого приоритета. Windows NT поддерживает 32 уровня приоритетов; потоки делятся на два класса: реального времени и переменного приоритета. Потоки реального времени, имеющие при­оритеты от 16 до 31 – это высокоприоритетные потоки, используемые про­граммами с критическим временем выполнения, то есть требующие немедленно­го внимания системы (по терминологии Microsoft).

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

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

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

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

Следующий класс задач имеет название приоритетного. Поскольку к этому клас­су относят задачи, которые выполняют по отношению к остальным задачам роль сервера (о модели клиент–сервер, по которой строятся современные ОС с мик­роядерной архитектурой, см. в разделе «Микроядерные операционные системы», глава 5), то его ещё иногда называют серверным. Приоритет таких задач должен быть выше, это будет гарантировать, что запрос на некоторую функцию со сторо­ны обычных задач выполнится сразу, а не будет дожидаться, пока до него дойдет очередь на фоне других пользовательских приложений.

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

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

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

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

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

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

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