Файл: Debian Таненбаум Бос.pdf

2.4. Планирование   

181

Рис. 2.20. Пики активного использования центрального процессора чередуются с периодами 

ожидания завершения операций ввода-вывода: а — процесс, ограниченный скоростью 

вычислений; б — процесс, ограниченный скоростью работы устройств ввода-вывода

ограниченными скоростью вычислений

, а вторые — процессами, ограниченными 

скоростью работы устройств ввода-вывода

. Процессы, ограниченные скоростью 

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

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

Когда планировать?

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

182  

 Глава 2. Процессы и потоки 

процессов выполнять, родительский или дочерний. Поскольку оба процесса находят-
ся в состоянии готовности, вполне естественно, что планировщик должен принять 
решение, то есть вполне обоснованно выбрать выполнение либо родительского, либо 
дочернего процесса.

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

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

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

Если аппаратный таймер обеспечивает периодические прерывания с частотой 50 или 
60 Гц или с какой-нибудь другой частотой, планировщик должен принимать решения 
при каждом прерывании по таймеру или при каждом k-м прерывании. По реакции на 
прерывания по таймеру алгоритмы планирования можно разделить на две категории. 
Неприоритетный

 алгоритм планирования выбирает запускаемый процесс, а затем про-

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

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

2.4. Планирование   

183

Категории алгоритмов планирования

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

 пакетную;

 интерактивную;

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

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

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

Задачи алгоритма планирования

Чтобы создать алгоритм планирования, нужно иметь некое представление о том, с чем 
должен справиться толковый алгоритм. Некоторые задачи зависят от среды окружения 
(пакетная, интерактивная или реального времени), но есть и такие задачи, которые 
желательно выполнить в любом случае. Вот некоторые задачи алгоритма планирова-
ния, которых следует придерживаться при различных обстоятельствах и которые нам 
вскоре предстоит рассмотреть:

 Все системы:

•  равнодоступность — предоставление каждому процессу справедливой доли 

времени центрального процессора;

184  

 Глава 2. Процессы и потоки 

•  принуждение к определенной политике — наблюдение за выполнением уста-

новленной политики;

•  баланс — поддержка загруженности всех составных частей системы.

 Пакетные системы:

•  производительность — выполнение максимального количества заданий в час;

•  оборотное время — минимизация времени между представлением задачи и ее 

завершением;

•  использование центрального процессора — поддержка постоянной загружен-

ности процессора.

 Интерактивные системы:

•  время отклика — быстрый ответ на запросы;

•  пропорциональность — оправдание пользовательских надежд.

 Системы реального времени:

•  соблюдение предельных сроков — предотвращение потери данных;

•  предсказуемость — предотвращение ухудшения качества в мультимедийных 

системах.

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

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

Другой общей задачей является поддержание максимально возможной задействован-
ности всех составных частей системы. Если центральный процессор и все устройства 
ввода-вывода смогут быть постоянно задействованы, то будет произведен больший 
объем работы в секунду, чем при простое каких-нибудь компонентов. К примеру, 
в пакетной системе планировщик управляет тем, чье задание поместить в память для 
выполнения. Одновременное размещение в памяти части процессов, ограниченных 
скоростью вычислений, и части процессов, ограниченных скоростью работы устройств 
ввода-вывода, будет более разумным решением, чем загрузка и выполнение сначала 
всех заданий, ограниченных скоростью вычислений, а затем, когда их выполнение 
завершится, загрузка и выполнение всех заданий, ограниченных скоростью работы 
устройств ввода-вывода. Если используется последняя из этих стратегий, то при за-
пуске процессов, ограниченных скоростью вычислений, они будут состязаться за ис-
пользование центрального процессора, а дисковое устройство будет простаивать. Затем, 
когда дело дойдет до выполнения заданий, ограниченных скоростью работы устройств 
ввода-вывода, они вступят в борьбу за дисковое устройство, а центральный процессор 
будет простаивать. Лучше за счет разумного сочетания процессов поддерживать в ра-
ботающем состоянии сразу всю систему.

2.4. Планирование   

185

Руководители крупных вычислительных центров, в которых запускается множество 
пакетных заданий, при оценке производительности своей системы обычно берут в рас-
чет три показателя: производительность, оборотное время и степень задействования 
центрального процессора. Производительность — это количество заданий, выпол-
ненных за один час. С учетом всех обстоятельств выполнение 50 заданий в час счита-
ется лучшим показателем, чем выполнение 40 заданий в час. Оборотное время — это 
среднестатистическое время от момента передачи задания на выполнение до момента 
завершения его выполнения. Им измеряется время, затрачиваемое среднестатистиче-
ским пользователем на вынужденное ожидание выходных данных. Здесь действует 
правило: чем меньше, тем лучше.

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

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

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

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

. Пользователям свойственно прикидывать (и зачастую невер-

но) продолжительность тех или иных событий. Когда запрос, рассматриваемый как 
сложный, занимает довольно продолжительное время, пользователь воспринимает это 
как должное, но когда запрос, считающийся простым, также занимает немало времени, 
пользователь выражает недовольство. Например, если по щелчку на значке иницииру-
ется выкладывание видео объемом 500 Мбайт на облачный сервер, что занимает 60 с, 
пользователь, наверное, воспримет это как должное, поскольку он не ожидает, что видео 
будет передано за 5 с, и знает, что для этого нужно время.

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