Дисциплины с одной очередью
По-видимому, самой хорошей стратегией является стратегия предоставления всем пользователям одинаковых услуг. Что это означает? Разумная интерпретация состоит в том, что ни один процесс в среднем не ждет дольше, чем любой другой. Более точная формулировка основывается на понятии среднего времени ожидания.
Рассмотрим систему, которая после завершения действий, связанных с инициированием системы, работает достаточно долго, выполняя некоторую смесь процессов. Предположим, что реакция системы не меняется со временем, т. е. система работает в установившемся режиме. Тогда для некоторого процесса, перешедшего в состояние готовности, можно было бы экспериментально измерить время ожидания. Повторяя эти измерения много раз в случайно выбранные моменты времени, можно было бы получить последовательность значений времен ожидания. Среднее значение, полученное для этих величин при бесконечном числе измерений, является средним временем ожидания для данного процесса. Конечно, имеется в виду не практическое, а только теоретическое бесконечное повторение эксперимента. Тем не менее, имея достаточную информацию о процессе и точное описание алгоритма диспетчеризации, можно, используя теорию очередей, вычислить среднее время ожидания. Если расширить мысленный эксперимент и выполнить такие измерения не для одного конкретного процесса, а для всех процессов, то получим общее среднее время ожидания; его также можно вычислить используя теорию очередей.
Теперь стратегию предоставления равных услуг можно сформулировать следующим образом: обеспечить для всех процессов одно и то же среднее время ожидания. Достигнуть этого можно, обслуживая процессы в порядке их появления и позволяя каждому процессу выполняться до конца, за исключением, конечно, тех случаев, когда процесс переходит в заблокированное состояние. Такую дисциплину, не осуществляющую перераспределение процессора, иногда называют FIFO в связи с тем, что ее можно реализовать с помощью обычной очереди, если ни один из процессов никогда не переходит в заблокированное состояние. Поскольку процессы все же блокируются, то в какой-то степени более подходящим названием этой дисциплины является первым-пришел-первым- обслужен (FCFS, по первым буквам "first-come-first-served"). Стоимость реализации низка, так как очередь готовых к исполнению процессов нужно поддерживать в порядке возрастания времен создания процессов, а перераспределение процессора не производится. По мнению многих пользователей, основным недостатком механизма FCFS является то, что короткие процессы вынуждены ждать столько же, сколько и длинные. Пользователи считают, что равное среднее время ожидания не является эквивалентом равных услуг. Теория очередей вскрывает два дополнительных недостатка: во-первых, среднее время ожидания может неограниченно расти, по мере того, как система приближается к пределу своей загруженности; во-вторых, с увеличением дисперсии времени выполнения процессов среднее время ожидания увеличивается. Для интерактивного режима механизм FCFS непривлекателен еще и потому, что при любой дисциплине, не осуществляющей перераспределение процессора, процесс, долго не переходящий в заблокированное состояние, задерживает другие процессы.
Стратегия, избавленная от недостатков FCFS, состоит в минимизации общего среднего времени ожидания. Если приоритет, учитываемый при диспетчеризации, основан на времени выполнения процесса, а не на времени его создания, то дисциплина планирования называется следующий-с-кратчайшим- заданием (SJN, shortest-job-next). Она обычно реализуется как дисциплина, не перераспределяющая процессор. Можно показать, что по сравнению с FCFS SJN снижает общее среднее время ожидания; при этом среднее время ожидания коротких процессов становится меньше, чем у длинных, но это достигается дорогой ценой. По сравнению с FCFS увеличивается среднее время ожидания для длинных процессов, растет также и дисперсия времени ожидания. В результате трудно предсказать, когда процесс будет обслужен. Для многих пользователей предсказуемость обслуживания почти также важна, как и скорость обслуживания. Быстро избавляясь от коротких процессов, дисциплина SJN приводит к уменьшению числа процессов, находящихся в очереди готовых к исполнению. В SJN можно ввести перераспределение процессора, удаляя выполняющийся процесс всякий раз, когда появляется более короткий, готовый к исполнению процесс. Последний может возникнуть либо в результате деблокирования, либо это будет новый процесс, появившийся в системе. От этого еще больше выигрывают короткие процессы. С другой стороны, неразумно снимать с процессора почти закончившийся процесс ради другого, чей общий запрос на время меньше, но чья текущая потребность во времени больше времени, необходимого для завершения удаляемого процесса.
Если запоминать, какие отрезки времени выделялись процессам, то перераспределять процессор можно более разумно. В этом случае система может использовать дисциплину следующий-с-минимальным-оставшимся- временем (SRT, "shortest-remaining time"). Оставшееся время-это разность между временем, запрошенным пользователем, и временем, которое процесс уже получил и которое измеряется системой с помощью часов, встроенных в оборудование. При SRT можно было бы не перераспределять процессор, но это свело бы на нет основное достоинство алгоритма, заключающееся в том, что всегда исполняется процесс, которому до завершения осталось работать меньше всего. Следовательно, при использовании дисциплины SRT обычно выполняется перераспределение процессора, и ее можно считать аналогом SJN с перераспределением процессора. При SRT короткие процессы еще сильнее выигрывают за счет длинных, чем при SJN. Можно показать, что при SRT достигается минимально возможное общее среднее время ожидания. Поскольку дисциплины SJN и SRT основаны на. оценке времени, необходимого процессу, то они не подходят для диспетчеризации интерактивных процессов.
При SJN и SRT пользователь, который запрашивает на обработку небольшое время, получает более высокий приоритет, чем тот, кто запрашивает большое время. Поэтому появляется желание занизить оценку времени, чтобы искусственно повысить свой приоритет. Для борьбы с этим можно, например, удалять процесс из системы, как только заказанное на его обслуживание время исчерпано, или повышать стоимость машинного времени, которое будет дополнительно предоставлено. Для всех дисциплин проблемой является процесс, не выходящий из цикла, и поэтому почти всегда для каждого процесса устанавливается некоторое максимально допустимое время исполнения.
Другая дисциплина, сокращающая среднее время ожидания, состоит в предоставлении более высокого диспетчерского приоритета тем процессам, которые (что известно системе на основе других критериев, отличных от заказанного времени) с большой степенью вероятности потребуют мало процессорного времени. Например, предпочтение можно отдавать процессам с большим числом обменов. Чем чаще процесс осуществляет ввод/вывод, тем чаще он блокируется. Если очередь организована в порядке возрастания интервалов времени с момента последней команды ввода/вывода, то предпочтение будет обычно отдаваться процессам, число обменов которых в данный момент велико. В результате это приведет к максимальному использованию подсистемы ввода/вывода. Использование одной очереди, упорядоченной в соответствии с числом обменов, не позволяет принимать в расчет другие факторы. Поэтому предоставление более высокого приоритета процессам, связанным с вводом/выводом, чаще осуществляется с помощью дисциплины с несколькими очередями.
Недостатком предыдущих дисциплин, предназначенных для сокращения общего среднего времени ожидания, является задержка выполнения длинных процессов. В некоторых системах процессы теряются практически навсегда. Если к требованию минимизации добавить требование гарантированного завершения всех процессов, то можно получить новые дисциплины планирования. Особой популярностью пользуется циклическая, (RR, "round -robin") дисциплина перераспределения процессора с очень простым управлением очередью. Каждому процессу по очереди выделяется фиксированный квант времени q, в конце которого, если процесс к этому времени не закончился или не был заблокирован, он снимается с процессора, а на процессор ставится следующий процесс из числа находящихся в состоянии готовности. Процесс, снятый с процессора, считается деблокированным или только что появившимся в системе, и он ставится в конец очереди. При циклической дисциплине обслуживания приоритет процесса возрастает с увеличением времени ожидания с момента получения последнего кванта (или, для нового процесса, с момента его создания). Если существует n готовых к исполнению или исполняющихся процессов, то каждый получит n часть процессорного времени. Такая форма равного обслуживания неявно отдает предпочтение коротким процессам, поскольку они будут заканчиваться быстрее, чем длинные, но без чрезмерного ущемления “интересов” длинных процессов. Из-за расходов на переключение процессов общее время ожидания может быть больше, чем при FCFS. Однако, если дисперсия времени выполнения процессов велика, то при циклическом механизме общее среднее время ожидания может быть меньше, чем при FCFS. Циклический механизм широко используется в интерактивных системах.
Существенную роль играет размер кванта времени. При большом значении q появление или деблокирование процессов может задержать исполнение процесса, а их блокирование - ускорить его исполнение. Эта неравномерность приводит к отклонению от равного обслуживания всех процессов, Кроме того, с ростом q для любого процесса возрастает время ожидания между последовательными выделениями ему процессора, что является недостатком для интерактивных систем. С другой стороны, при маленьком значении q общее время ожидания может быть больше, чем при большом q. Более того, при маленьком q увеличивается частота переключения процессов, а затраченное на это время может превышать время, остающееся на долю процессов. В результате для q необходимо выбрать некоторое приемлемое значение; оно, как правило, лежит в интервале от 200 до 2000 мсек.
Существует несколько видов циклических дисциплин. Одна из них используется в интерактивных системах, стремящихся гарантировать определенное минимальное время реакции t. В начале каждого просмотра очереди готовых процессов g = t / n, где n - число процессов s очереди в данный момент. Процессы, которые должны быть введены в систему, составляют другую очередь, которая затем, когда первая очередь исчерпана, обрабатывается в том же порядке. Чтобы время переключения процессов было равно s, необходимо установить q = (t / n) - s. Отсюда следует, что при больших n затраты на переключение (s) будут большими. Поддерживая значение q на некотором минимальном уровне, их можно уменьшить, увеличивая время реакции t.
Другим средством, гарантирующим выделение процессора длинным процессам, является повышение их приоритетов с течением времени. Этот способ известен как учет старения, и заключается в вычислении разности между приоритетом и временем создания процесса (предполагается, что более высокому приоритету соответствует более высокое числовое значение). Чем старше процесс, тем меньшая величина будет вычитаться, и в результате его приоритет будет выше, чем у всех последующих процессов.
