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

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

2.4.2. Планирование согласно приоритетам

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

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

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

Приоритеты процессам могут присваиваться статически или динамически. На военной базе процессу, запущенному генералом, присваивается приоритет 100, полковником - 90, майором - 80, капитаном - 70, лейтенантом - 60 и т. д. А в коммерческом компьютерном центре выполнение заданий с высоким приоритетом может стоить 100 долларов в час, со средним - 75, с низким - 50. В системе UNIX есть команда nice, позволяющая пользователю добровольно снизить приоритет своих процессов, чтобы быть любезным по отношению к остальным пользователям. Этой командой никто никогда не пользуется.

Система вправе динамически назначать приоритеты для достижения своих целей. Например, некоторые процессы сильно ограничены возможностями устройств ввода/вывода и большую часть времени проводят в ожидании завершения соответствующих операций. Когда бы ни потребовался процессор такому процессу, его следует немедленно предоставить, чтобы процесс мог начать обрабатывать следующий запрос ввода/вывода, который будет выполняться параллельно с вычислениями другого процесса. Если заставить процесс, ограниченный возможностями устройств ввода/вывода, длительное время ждать доступа к процессору, он будет неоправданно долго находиться в памяти. Простой алгоритм обслуживания процессов, сдерживаемых возможностями устройств ввода/вывода, состоит в установке приоритета, равного 1 , где / - часть использованного в последний раз кванта. Процесс, утилизировавший всего 1 мс из 50 мс кванта, получит приоритет 50, процесс, использовавший 25 мс, получит приоритет 2, а процесс, задействовавший весь квант, получит приоритет 1.

Часто бывает удобно сгруппировать процессы в классы по приоритетам и использовать планирование согласно приоритетам среди классов, но циклическое планирование внутри каждого класса. На рис. 2.10 представлена система с четырьмя классами приоритетов. Алгоритм планирования выглядит следующим образом: пока в классе 4 есть готовые к запуску процессы, они запускаются один за другим согласно алгоритму циклического планирования, и каждому отводится квант времени. При этом классы с более низким приоритетом не будут их беспокоить. Если в классе 4 нет готовых к запуску процессов, запускаются процессы класса 3 и т. д. Если приоритеты постоянны, до процессов класса 1 процессор может не дойти никогда.

Заголовки очередей

Процессы, готовые к запуску

Приоритет 4

Приоритет 3

Приоритет 2

Приоритет 1

(Самый высокий приоритет)

(Самый низкий приоритет)

Рис. 2.10. Алгоритм планирования с четырьмя классами приоритетов

2.4.3. Планирование с несколькими очередями

Один из первых приоритетных планировщиков был реализован в системе CTSS (Compatible Time-Shared System - совместимая система с разделением времени) [75]. Основной проблемой системы CTSS стало слишком медленное переключение процессов, поскольку в памяти компьютера IBM 7094 мог находиться только один процесс. Каждое переключение означало выфузку текущего процесса на диск и считывание нового процесса с диска. Разработчики CTSS быстро сообра-

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

В качестве примера рассмотрим процесс, которому необходимо производить вычисления в течение 100 квантов. Вначале ему будет предоставлен один квант, затем процесс будет сброшен на диск. В следующий раз ему достанется 2 кванта, затем 4, 8, 16, 32, 64, хотя из 64 он использует только 37. В этом случае понадобятся всего 7 перекачек (включая первоначальную загрузку) вместо 100, которые понадобились бы в случае циклического алгоритма. Помимо того, по мере погружения в очередь приоритетов процесс будет все реже запускаться, в пользу более коротких процессов.

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

Для разделения процессов по классам используются также многие другие алгоритмы. Например, в системе XDS 940, разработанной в Беркли [79], было четыре класса приоритетов, называвшихся: терминал, ввод/вывод, короткий квант и длинный квант. Когда запускался процесс, ожидающий вывода на терминал, он перемещался в класс высшего приоритета (терминал). Когда снималась блокировка процесса, ожидавшего доступа к диску, он переходил во второй класс. Если к концу отведенного времени процесс все еще работал, он сначала зачислялся в третий класс. Если процесс слишком много раз полностью задействовал свой квант времени, не блокируясь на терминале или другом устройстве ввода/вывода, он перемещался в последний класс. Этот метод практикуется во многих системах для предоставления преимущества интерактивным процессам по сравнению с фоновыми.

2.4.4. Самый короткий процесс - следующий

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