Курс лекций Операционным системам и среды (стр. 10 из 21)
Если планировщик принимает и вынужденные, и невынужденные решения, говорят о вытесняющем планировании (приоритетный алгоритм). Термин "вытесняющее планирование" возник потому, что исполняющийся процесс помимо своей воли может быть вытеснен из состояния исполнение другим процессом. Вытесняющее планирование обычно используется в системах разделения времени. В этом режиме планирования процесс может быть приостановлен в любой момент исполнения. Операционная система устанавливает специальный таймер для генерации сигнала прерывания по истечении некоторого интервала времени – кванта. После прерывания процессор передается в распоряжение следующего процесса. Временные прерывания помогают гарантировать приемлемое время отклика процессов для пользователей, работающих в диалоговом режиме, и предотвращают "зависание" компьютерной системы из-за зацикливания какой-либо программы.
Неудивительно, что в различных условиях окружающей среды требуются разные алгоритмы планирования. Это обусловлено тем, что различные сферы приложений (и разные типы операционных систем) предназначены для решения разных задач. Иными словами, предмет оптимизации для планировщика не может совпадать во всех системах. При этом стоит различать три среды:
1) пакетную;
2) интерактивную;
3) реального времени.
В пакетных системах не бывает пользователей, терпеливо ожидающих за своими терминалами быстрого ответа на свой короткий запрос. Поэтому для них зачастую приемлемы неприоритетные алгоритмы или приоритетные алгоритмы с длительными периодами для каждого процесса. Такой подход сокращает количество переключений между процессами, повышая при этом производительность работы системы. Пакетные алгоритмы носят весьма общий характер и часто находят применение также и в других ситуациях, поэтому их стоит изучить даже тем, кто не работает в сфере корпоративных вычислений с использованием универсальных машин.
В среде с пользователями, работающими в интерактивном режиме, приобретает важность приоритетность, сдерживающая отдельный процесс от захвата центрального процессора, лишающего при этом доступа к службе всех других процессов. Даже при отсутствии процессов, склонных к бесконечной работе, один из процессов в случае программной ошибки мог бы навсегда закрыть доступ к работе всем остальным процессам. Для предупреждения такого поведения необходимо использование приоритетного алгоритма. Под эту категорию подпадают и серверы, поскольку они, как правило, обслуживают нескольких вечно спешащих (удаленных) пользователей.
В системах, ограниченных условиями реального времени, как ни странно, приоритетность иногда не требуется, поскольку процессы знают, что они могут запускаться только на непродолжительные периоды времени, и зачастую выполняют свою работу довольно быстро, а затем блокируются. В отличие от интерактивных систем в системах реального времени запускаются лишь те программы, которые предназначены для содействия определенной прикладной задаче. Интерактивные системы имеют универсальный характер и могут запускать произвольные программы, которые не выполняют совместную задачу или даже вредят друг другу.
Задачи алгоритма планирования
Чтобы создать алгоритм планирования, нужно иметь некое представление о том, с чем должен справиться толковый алгоритм. Некоторые задачи зависят от среды окружения (пакетная, интерактивная или реального времени), но есть и такие задачи, которые желательно выполнить в любом случае. Вот некоторые задачи алгоритма планирования, которых следует придерживаться при различных обстоятельствах, и которые нам вскоре предстоит рассмотреть:
Все системы
1) Равнодоступность — предоставление каждому процессу справедливой доли времени центрального процессора (несправедливо предоставлять одному процессу больше времени центрального процессора, чем другому, эквивалентному ему процессу).
2) Принуждение к определенной политике — наблюдение за выполнением установленной политики (если локальная политика заключается в том, что процессы, контролирующие безопасность, должны получать возможность возобновления своей работы сразу же, как только в этом возникнет необходимость, даже если при этом расчет заработной платы задержится на полминуты, планировщик должен обеспечить осуществление этой политики).
3) Баланс — поддержка загруженности всех составных частей системы (если центральный процессор и все устройства ввода-вывода смогут быть постоянно задействованы, то будет произведен больший объем работы в секунду, чем при простое каких-нибудь компонентов).
Пакетные системы
1) Производительность — выполнение максимального количества заданий в час.
2) Оборотное время — минимизация времени между представлением задачи и ее завершением.
3) Использование центрального процессора — поддержка постоянной загруженности процессора.
Интерактивные системы
1) Время отклика — быстрый ответ на запросы.
2) Пропорциональность — оправдание пользовательских надежд (пользователям свойственно прикидывать (и зачастую неверно) продолжительность тех или иных событий. Когда запрос, рассматриваемый как сложный, занимает довольно продолжительное время, пользователь воспринимает это как должное, но когда запрос, считающийся простым, также занимает немало времени, пользователь выражает недовольство.).
Системы реального времени
Они характеризуются наличием крайних сроков выполнения, которые обязательно или, по крайней мере, желательно должны быть выдержаны. Например, если компьютер управляет устройством, которое выдает данные с определенной скоростью, отказ от запуска процесса сбора данных может привести к потере информации. Поэтому самым главным требованием в системах реального времени является соблюдение всех (или большей части) крайних сроков.
1) Соблюдение предельных сроков — предотвращение потери данных.
2) Предсказуемость — предотвращение ухудшения качества в мультимедийных системах. В некоторых системах реального времени, особенно в мультимедийных системах, существенную роль играет предсказуемость. Редкие случаи несоблюдения крайних сроков не приводят к сбоям, но если аудиопроцесс прерывается довольно часто, то качество звука резко ухудшается. Это относится и к видеопроцессам, но человеческое ухо более чувствительно к случайным искажениям, чем глаз. Чтобы избежать подобной проблемы, планирование процессов должно быть исключительно предсказуемым и постоянным.
Алгоритмы планирования
Планирование в пакетных системах
1) «Первый пришел - первым обслужен» (FIFO - First In Fist Out)
Простейший неприоритетный алгоритм.
Процессор выделяется процессам в порядке поступления их запросов. По сути, используется одна очередь процессов, находящихся в состоянии готовности. Когда рано утром в систему извне попадает первое задание, оно тут же запускается на выполнение и получает возможность выполняться как угодно долго. Оно не прерывается по причине слишком продолжительного выполнения. По мере поступления других заданий они помещаются в конец очереди. При блокировке выполняемого процесса следующим запускается первый процесс, стоящий в очереди. Когда заблокированный процесс переходит в состояние готовности, он, подобно только что поступившему заданию, помещается в конец очереди.
Достоинства: простота, справедливость.
Недостатки: среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди. Если у нас есть процесс с длительным временем выполнения, то короткие процессы, перешедшие в состояние готовность после длительного процесса, будут очень долго ждать начала выполнения.
Пример. Пусть в состоянии готовность находятся три процесса p1, p2 и p3, для которых известны времена их выполнения в некоторых условных единицах:
Таблица 1
| Процесс | Время выполнения |
| P1 | 13 |
| P2 | 4 |
| P3 | 1 |
Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка времени, что процессы не совершают операций ввода-вывода и что время переключения между процессами так мало, что им можно пренебречь.
Если процессы расположены в очереди процессов, готовых к исполнению, в порядке p1, p2, p3, то картина их выполнения выглядит так, как показано на рис. 9.
