Добавлен: 29.10.2018
Просмотров: 48043
Скачиваний: 190
186
Глава 2. Процессы и потоки
операция не завершается после 30 с, пользователь вряд ли смолчит, а после 60 с он
будет просто взбешен. Такое поведение будет соответствовать обычным пользователь-
ским представлениям о том, что на отправку большого объема данных предполагается
затратить намного больше времени, чем на разрыв соединения. В некоторых случаях
(как и в этом) планировщик не может повлиять на время отклика, но в других случаях
он может это сделать, особенно если задержка обусловлена неверным выбором очеред-
ности выполнения процессов.
В отличие от интерактивных систем системы реального времени имеют другие свой-
ства, а значит, и другие задачи планирования. Они характеризуются наличием крайних
сроков выполнения, которые обязательно или по крайней мере желательно выдер-
живать. Например, если компьютер управляет устройством, которое выдает данные
с определенной скоростью, отказ от запуска процесса сбора данных может привести
к потере информации. Поэтому главным требованием в системах реального времени
является соблюдение всех (или большей части) крайних сроков.
В некоторых системах реального времени, особенно в мультимедийных системах,
существенную роль играет предсказуемость. Редкие случаи несоблюдения крайних
сроков не приводят к сбоям, но если аудиопроцесс прерывается довольно часто, то
качество звука резко ухудшается. Это относится и к видеопроцессам, но человеческое
ухо более чувствительно к случайным искажениям, чем глаз. Чтобы избежать подобной
проблемы, планирование процессов должно быть исключительно предсказуемым и по-
стоянным. В этой главе мы рассмотрим алгоритмы планирования процессов в пакетных
и интерактивных системах. Планирование процессов реального времени в этой книге
не рассматривается, но дополнительный материал, касающийся мультимедийных опе-
рационных систем, можно найти на веб-сайте книги.
2.4.2. Планирование в пакетных системах
Теперь давайте перейдем от общих вопросов планирования к специализированным
алгоритмам. В этом разделе будут рассмотрены алгоритмы, используемые в пакетных
системах, а в следующих разделах мы рассмотрим алгоритмы, используемые в инте-
рактивных системах и системах реального времени. Следует заметить, что некоторые
алгоритмы используются как в пакетных, так и в интерактивных системах. Мы рас-
смотрим их чуть позже.
Первым пришел — первым обслужен
Наверное, наипростейшим из всех алгоритмов планирования будет неприоритетный
алгоритм, следующий принципу «первым пришел — первым обслужен». При исполь-
зовании этого алгоритма центральный процессор выделяется процессам в порядке
поступления их запросов. По сути, используется одна очередь процессов, находящихся
в состоянии готовности. Когда рано утром в систему извне попадает первое задание,
оно тут же запускается на выполнение и получает возможность выполняться как угод-
но долго. Оно не прерывается по причине слишком продолжительного выполнения.
Другие задания по мере поступления помещаются в конец очереди. При блокировке
выполняемого процесса следующим запускается первый процесс, стоящий в очереди.
Когда заблокированный процесс переходит в состояние готовности, он, подобно толь-
ко что поступившему заданию, помещается в конец очереди, после всех ожидающих
процессов.
2.4. Планирование
187
Сильной стороной этого алгоритма является простота его понимания и такая же
простота его программирования. Его справедливость сродни справедливости рас-
пределения дефицитных билетов на спортивные или концертные зрелища или мест
в очереди на новые айфоны тем людям, которые заняли очередь с двух часов ночи.
При использовании этого алгоритма отслеживание готовых процессов осуществляется
с помощью единого связанного списка. Выбор следующего выполняемого процесса
сводится к извлечению одного процесса из начала очереди. Добавление нового задания
или разблокированного процесса сводится к присоединению его к концу очереди. Что
может быть проще для восприятия и реализации?
К сожалению, принцип «первым пришел — первым обслужен» страдает и существен-
ными недостатками. Предположим, что используются один процесс, ограниченный
скоростью вычислений, который всякий раз запускается на 1 с, и множество процессов,
ограниченных скоростью работы устройств ввода-вывода, незначительно использу-
ющих время центрального процессора, но каждый из которых должен осуществить
1000 считываний с диска, прежде чем завершить свою работу. Процесс, ограниченный
скоростью вычислений, работает в течение 1 с, а затем переходит к чтению блока дан-
ных с диска. Теперь запускаются все процессы ввода-вывода и приступают к чтению
данных с диска. Когда процесс, ограниченный скоростью вычислений, получает свой
блок данных с диска, он запускается еще на 1 с, а за ним непрерывной чередой следуют
все процессы, ограниченные скоростью работы устройств ввода-вывода.
В итоге каждый процесс, ограниченный скоростью работы устройств ввода-вывода,
считывает один блок в секунду, и завершение его работы займет 1000 с. Если исполь-
зуется алгоритм планирования, выгружающий процесс, ограниченный скоростью
вычислений, каждые 10 мс, то процессы, ограниченные скоростью работы устройств
ввода-вывода, завершаются за 10 с вместо 1000 с, при этом особо не замедляя работу
процесса, ограниченного скоростью вычислений.
Сначала самое короткое задание
Теперь рассмотрим другой неприоритетный алгоритм для пакетных систем, в котором
предполагается, что сроки выполнения заданий известны заранее. К примеру, в стра-
ховой компании люди могут довольно точно предсказать, сколько времени займет
выполнение пакета из 1000 исковых заявлений, поскольку подобная работа выполня-
ется ежедневно. Когда в ожидании запуска во входящей очереди находится несколько
равнозначных по важности заданий, планировщик выбирает сначала самое короткое
задание
. Рассмотрим изображение, приведенное на рис. 2.21. Здесь представлены
четыре задания: A, B, C и D со сроками выполнения 8, 4, 4 и 4 минуты соответственно.
Если их запустить в этом порядке, оборотное время для задания A составит 8 мин, для
B — 12 мин, для C — 16 мин и для D — 20 мин при среднем времени 14 мин.
Рис. 2.21. Пример планирования, когда первым выполняется самое короткое задание:
а — запуск четырех заданий в исходном порядке; б — запуск этих заданий в порядке,
когда самое короткое из них выполняется первым
188
Глава 2. Процессы и потоки
Теперь рассмотрим запуск этих четырех заданий, когда первым запускается самое ко-
роткое из них (рис. 2.21, б). Теперь показатели оборотного времени составляют 4, 8, 12
и 20 мин при среднем времени 11 мин. Оптимальность алгоритма, при котором первым
выполняется самое короткое задание, можно доказать. Рассмотрим пример с четырьмя
заданиями, выполняемыми за время a, b, c и d соответственно. Первое задание будет
выполнено за время a, второе — за время a + b и т. д. Среднее оборотное время составит
(4a + 3b + 2c + d)/4. Очевидно, что время a оказывает наибольшее влияние на средний
показатель по сравнению со всеми остальными временными показателями, поэтому это
должно быть самое короткое задание. Затем по нарастающей должны идти b, c и на-
конец d как самое продолжительное, которое оказывает влияние лишь за счет своего
собственного оборотного времени. Аналогичные аргументы точно так же применимы
к любому количеству заданий.
Следует заметить, что алгоритм, основанный на выполнении первым самого короткого
задания, оптимален только в том случае, если все задания доступны одновременно.
В качестве примера противоположной ситуации рассмотрим пять заданий от A до E
со сроками выполнения 2, 4, 1, 1 и 1 соответственно. Время их поступления 0, 0, 3, 3
и 3. Первоначально может быть выбрано только задание A или задание B, а остальные
три задания к тому времени еще не поступят. Используя правило, по которому первым
выполняется самое короткое задание, мы будем выполнять задания в следующей оче-
редности: A, B, C, D, E — при среднем времени ожидания, равном 4,6. Разумеется, их
запуск в следующем порядке: B, C, D, E, A — привел бы к среднему времени ожидания,
равному 4,4.
Приоритет наименьшему времени выполнения
Приоритетной версией алгоритма выполнения первым самого короткого задания
является алгоритм первоочередного выполнения задания с наименьшим оставшимся
временем выполнения
. При использовании этого алгоритма планировщик всегда вы-
бирает процесс с самым коротким оставшимся временем выполнения. Здесь, так же
как и прежде, время выполнения заданий нужно знать заранее. При поступлении
нового задания выполняется сравнение общего времени его выполнения с оставши-
мися сроками выполнения текущих процессов. Если для выполнения нового задания
требуется меньше времени, чем для завершения текущего процесса, этот процесс при-
останавливается и запускается новое здание. Эта схема позволяет быстро обслужить
новое короткое задание.
2.4.3. Планирование в интерактивных системах
Теперь давайте рассмотрим некоторые алгоритмы, которые могут быть использованы
в интерактивных системах. Они часто применяются на персональных компьютерах,
серверах и в других разновидностях систем.
Циклическое планирование
Одним из самых старых, простых, справедливых и наиболее часто используемых
считается алгоритм циклического планирования. Каждому процессу назначается
определенный интервал времени, называемый его квантом, в течение которого ему
предоставляется возможность выполнения. Если процесс к завершению кванта вре-
2.4. Планирование
189
мени все еще выполняется, то ресурс центрального процессора у него отбирается
и передается другому процессу. Разумеется, если процесс переходит в заблокированное
состояние или завершает свою работу до истечения кванта времени, то переключе-
ние центрального процессора на другой процесс происходит именно в этот момент.
Алгоритм циклического планирования не представляет сложности в реализации. На
рис. 2.22, а показано, что от планировщика требуется всего лишь вести список про-
цессов, готовых к выполнению. Когда процесс исчерпает свой квант времени, он, как
показано на рис. 2.22, б, помещается в конец списка.
Рис. 2.22. Циклическое планирование: а — список процессов, находящихся в состоянии
готовности; б — тот же список после того, как процесс B исчерпал свой квант времени
Единственное, что по-настоящему представляет интерес в циклическом планирова-
нии, — это продолжительность кванта времени. Переключение с одного процесса на
другой требует определенного количества времени для выполнения задач администри-
рования — сохранения и загрузки регистров и карт памяти, обновления различных
таблиц и списков, сброса на диск и перезагрузки кэша памяти и т. д. Предположим,
что переключение процесса, или переключение контекста, как его иногда называют,
занимает 1 мс, включая переключение карт памяти, сброс на диск и перезагрузку кэша
и т. д. Также предположим, что значение кванта времени установлено на 4 мс. При
таких параметрах настройки после 4 мс полезной работы центральному процессору
придется затратить (то есть потерять) 1 мс на переключение процесса. Таким образом,
20 % процессорного времени будет выброшено на административные издержки, а это,
вне всякого сомнения, слишком много.
Чтобы повысить эффективность использования центрального процессора, мы можем
установить значение кванта времени равным, скажем, 100 мс. Теперь теряется всего 1 %
времени. Но посмотрим, что получится на серверной системе, если за очень короткое
время к ней поступит 50 запросов, имеющих широкий разброс степени востребован-
ности центрального процессора. В список готовых к запуску процессов будет помещено
50 процессов. Если центральный процессор простаивает, первый из них будет запущен
немедленно, второй не сможет запуститься, пока не истекут 100 мс, и т. д. Если пред-
положить, что все процессы полностью воспользуются своими квантами времени, то
самый невезучий последний процесс может пребывать в ожидании в течение 5 с, пре-
жде чем получит шанс на запуск. Многим пользователям работа системы при пятисе-
кундном ожидании ответа на короткую команду покажется слишком медленной. Эта
ситуация получит особо негативную окраску, если некоторые из запросов, размещен-
ные ближе к концу очереди, требуют всего лишь несколько миллисекунд процессорного
времени. Если квант времени будет короче, качество их обслуживания улучшится.
Другая особенность состоит в том, что если значение кванта времени установлено боль-
шим, чем среднее время задействованности центрального процессора, переключение
процесса не будет происходить слишком часто. Вместо этого большинство процессов
190
Глава 2. Процессы и потоки
будут выполнять операцию блокировки перед истечением кванта времени, вызывающим
переключение процессов. Исключение принудительного прерывания повышает произ-
водительность, поскольку переключение процессов происходит только при логической
необходимости, то есть когда процесс блокируется и не может продолжить работу.
Из этого следует, что установка слишком короткого кванта времени приводит к слиш-
ком частым переключениям процессов и снижает эффективность использования цен-
трального процессора, но установка слишком длинного кванта времени может привести
к слишком вялой реакции на короткие интерактивные запросы. Зачастую разумным
компромиссом считается квант времени в 20–50 мс.
Приоритетное планирование
В циклическом планировании явно прослеживается предположение о равнозначности
всех процессов. Зачастую люди, обладающие многопользовательскими компьютера-
ми и работающие на них, имеют на этот счет совершенно иное мнение. К примеру,
в университете иерархия приоритетности должна нисходить от декана к факультетам,
затем к профессорам, секретарям, техническим работникам, а уже потом к студентам.
Необходимость учета внешних факторов приводит к приоритетному планированию.
Основная идея проста: каждому процессу присваивается значение приоритетности
и запускается тот процесс, который находится в состоянии готовности и имеет наи-
высший приоритет.
Даже если у персонального компьютера один владелец, на нем могут выполняться
несколько процессов разной степени важности. Например, фоновому процессу, от-
правляющему электронную почту, должен быть назначен более низкий приоритет, чем
процессу, воспроизводящему на экране видеофильм в реальном времени.
Чтобы предотвратить бесконечное выполнение высокоприоритетных процессов, пла-
нировщик должен понижать уровень приоритета текущего выполняемого процесса
с каждым сигналом таймера (то есть с каждым его прерыванием). Если это действие
приведет к тому, что его приоритет упадет ниже приоритета следующего по этому по-
казателю процесса, произойдет переключение процессов. Можно выбрать и другую
альтернативу: каждому процессу может быть выделен максимальный квант допусти-
мого времени выполнения. Когда квант времени будет исчерпан, шанс запуска будет
предоставлен другому процессу, имеющему наивысший приоритет.
Приоритеты могут присваиваться процессам в статическом или в динамическом ре-
жиме. Например, на военных компьютерах процессы, инициированные генералами,
могут начинать свою работу с приоритетом, равным 100, процессы, инициированными
полковниками, — с приоритетом, равным 90, майорами — с приоритетом 80, капита-
нами — 70, лейтенантами — 60 и так далее вниз по табели о рангах. А в коммерческом
компьютерном центре высокоприоритетные задания могут стоить 100 долларов в час,
задания со средним приоритетом — 75, а задания с низким приоритетом — 50. В UNIX-
системах есть команда nice, позволяющая пользователю добровольно снизить при-
оритет своего процесса, чтобы угодить другим пользователям, но ею никто никогда
не пользуется.
Приоритеты также могут присваиваться системой в динамическом режиме с целью до-
стижения определенных системных задач. К примеру, некоторые процессы испытывают
существенные ограничения по скорости работы устройств ввода-вывода и проводят