Использование приоритетов

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

В данной главе рассматривается планирование в вычислительных системах на базе одного процессора. Эта ограниченная ситуация позволяет определить и прояснить многие вопросы, связанные с планированием. Глава начинается с рассмотрения трех типов планирования: долгосрочного, среднесрочного и краткосрочного. В основном материал главы посвящен вопросам краткосрочного планирования. Будут представлены в сравнении различные алгоритмы планирования.

Глава 10. Многопроцессорное планирование и планирование реального времени

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

ГЛАВА 9

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

9.1. Типы планирования процессора

9.2. Алгоритмы планирования

9.3. Традиционное планирование UNIX

9.4. Резюме, ключевые термины и контрольные вопросы

9.5. Рекомендуемая литература

9.6. Задачи

Приложение А. Время отклика Приложение Б. Очереди

На рис. 9.1 функции планирования привязаны к диаграмме переходов состояния процесса (впервые показанной на рис. 3.6,6). Долгосрочное планирова­ние осуществляется при создании нового процесса и представляет собой решение о добавлении нового процесса к множеству активных в настоящий момент процессов. Среднесрочное планирование является частью свопинга и представляет собой решение о добавлении процесса к множеству по крайней мере частично расположенных в основной памяти (и, следовательно, доступных для выполнения) процессов. Краткосрочное планирование является решением о том, какой из готовых к выполнению процессов будет выполняться следующим. На рис. 9.2 диаграмма переходов реорганизована таким образом, чтобы показать вложен­ность функций планирования.

Планирование оказывает большое влияние на производительность системы, поскольку именно оно определяет, какой процесс будет выполняться, а какой — ожидать выполнения. На рис. 9.3 показаны очереди, включенные в диаграмму переходов состояний процесса.¹ По сути планирование представляет собой управление очередями с целью минимизации задержек и оптимизации производительности системы.

¹ Для простоты восприятия на рис. 9.3 новые процессы показаны как непосредственно становящиеся в очередь готовых к выполнению, в то время как на рис. 9.1 и 9.2 видно, что новый процесс может быть как в состоянии готовности, так и приостановленным.

Долгосрочное планирование

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

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

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

Решение о том, какое из заданий должно быть добавлено в систему, может основываться на простейшем принципе "первым поступил — первым обслужен''; кроме того, для управления производительностью системы может использоваться и специальный инструментарий. Используемые в последнем случае критерии могут включать приоритет заданий, ожидаемое время выполнения и требования для работы устройств ввода-вывода. Например, если заранее доступна детальная информация о процессах, планировщик может пытаться поддерживать в системе смесь из процессов, ориентированных на вычисления и загружающих процессор, и процессов с высокой интерактивностью ввода-вывода и малой загрузкой процессора. Принимаемое решение может также зависеть от того, какие именно ресурсы ввода-вывода будут запрашиваться процессом.

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

Среднесрочное планирование

Среднесрочное планирование является частью системы свопинга, вопросы которого рассматривались в главах 3, "Описание процессов и управление ими", 7, "Управление памятью", и 8, "Виртуальная память". Обычно решение о за­грузке процесса в память принимается в зависимости от степени многозадачности; кроме того, в системе с отсутствием виртуальной памяти среднесрочное планирование также тесно связано с вопросами управления памятью. Таким образом, решение о загрузке процесса в память должно учитывать требования к памяти выгружаемого процесса.

Краткосрочное планирование

Рассматривая частоту работы планировщика, можно сказать, что долгосрочное планирование выполняется сравнительно редко, среднесрочное — несколько чаще. Краткосрочный же планировщик, известный также как диспетчер (dispatcher), работает чаще всего, определяя, какой именно процесс будет выполняться следующим. Краткосрочный планировщик вызывается при наступлении события, которое может приостановить текущий процесс или предоставить возможность прекратить выполнение данного процесса в пользу другого. Вот некоторые примеры таких событий:

• прерывание таймера;

• прерывания ввода-вывода;

• вызовы операционной системы;

• сигналы.

АЛГОРИТМЫ ПЛАНИРОВАНИЯ

Критерии краткосрочного планирования

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

Наиболее распространенные критерии могут быть классифицированы в двух плоскостях. Во-первых, мы можем разделить их на пользовательские и системные. Пользовательские критерии связаны с поведением системы по отношению к отдельному пользователю или процессу. В качестве примера можно привести время отклика в интерактивной системе. Время отклика представляет собой ин­тервал между передачей запроса и началом ответа на него. Его пользователь ощущает непосредственно, и, само собой, продолжительность интервала очень интересует его. Мы намерены создать стратегию планирования, обеспечивающую качественный сервис для пользователей? В таком случае для времени отклика следует установить порог, например в 2 секунды. Тогда цель механизма планирования должна заключаться в максимизации количества пользователей, среднее время отклика для которых не превышает 2 секунд.

Системные критерии ориентированы на эффективность и полноту использования процессора. В качестве примера можно привести пропускную способность, которая представляет собой скорость завершения процессов. Это, безусловно, эффективная мера производительности системы, которая должна быть максимизирована. Однако она в большей степени ориентирована на производительность системы, а не на обслуживание пользователя, так что и удовлетворять она будет системного администратора, а не пользователей системы.

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

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

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

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

Таблица 9.2. Критерии планирования

Использование приоритетов

Во многих системах каждому процессу присвоен некоторый приоритет, и планировщик всегда должен среди процессов выбирать тот, у которого приоритет наибольший. На рис. 9.4 показано использование приоритетов. Для большей ясности диаграмма упрощена и игнорирует существование нескольких очередей заблокированных или приостановленных процессов (ср. с рис. 3.5,а). Вместо одной очереди готовых к исполнению процессов у нас имеется их множество, упорядоченное по убыванию приоритета: RQ0, RQ1, ..., RQn, т.е.

Приоритет[RQi]> Приоритет[RQj] при i<j.²

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

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

Альтернативные стратегии планирования

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

w — время, затраченное к этому моменту системой (ожидание и выполнение);

е — время, затраченное к этому моменту на выполнение;

s — общее время обслуживания, требующееся процессу, включая е (обычно эта величина оценивается или задается пользователем).

² В UNIX и многих других системах большие значения приоритетов соответствуют процессам с низким приоритетом; если не указано иное, мы придерживаемся именно этого соглашения. Некоторые системы, такие, как OS/2 или Windows, используют обратное соглашение: большее значение указывает на более высокий приоритет.

Например, выбор функции max[w] определяет стратегию "первым поступил — первым обслужен" (first-come-first-served — FCFS).

Режим решения определяет, в какие моменты времени выполняется функция выбора. Режимы решения подразделяются на две основные категории.

• Невытесняющие. В этом случае находящийся в состоянии выполнения процесс продолжает выполнение до тех пор, пока он не завершится или пока не окажется в заблокированном состоянии ожидания завершения операции ввода-вывода или запроса некоторого системного сервиса.

• Вытесняющие. Выполняющийся в настоящий момент процесс может быть прерван и переведен операционной системой в состояние готовности к выполнению. Решение о вытеснении может приниматься при запуске нового процесса по прерыванию, которое переводит заблокированный процесс в состояние готовности к выполнению, или периодически — на основе прерываний таймера.

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

При описании различных стратегий планирования в качестве примера мы будем использовать набор процессов из табл. 9.4. Будем рассматривать их как пакетные задания со временем обслуживания, равным общему времени выполнения. Эти же процессы можно рассматривать как непрерывные процессы, требующие циклического чередования работы процессора и устройств ввода-вывода. Тогда время обслуживания будет представлять собой процессорное время, требующееся в одном цикле. В любом случае в рамках модели с очередями эта величина соответствует времени обслуживания.¹

Таблица 9.4. Пример планирования процессов