9.3. Традиционное планирование unix

В этом разделе мы рассмотрим традиционное планирование UNIX, используемое как в SVR3, так и в 4.3 BSD UNIX. Эти системы в первую очередь предназначены для работы в интерактивной среде с разделением времени. Алгоритм планирования разработан таким образом, чтобы обеспечить приемлемое время отклика для интерактивных пользователей, в то же время гарантируя отсутствие голодания низкоприоритетных заданий. Хотя описываемый алгоритм и был заменен в более современных версиях UNIX, его изучение как представителя практически используемых алгоритмов с разделением времени не лишено основания. Схема планирования SRV4 соответствует требованиям реального времени, но этот вопрос мы обсудим в главе 10, "Многопроцессорное планирование и планирование реального времени".

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

где

CPU_j(i)— мера использования процессора процессом j на протяжении интервала i;

Р_j (i) — приоритет процесса j в начале интервала i (меньшее значение соответствует большему приоритету);

Base_j — базовый приоритет процесса j;

nice_j — указываемый пользователем коэффициент.

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

• программа свопинга;

• управление блочными устройствами ввода-вывода;

• управление файлами;

• управление символьными устройствами ввода-вывода;

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

Пример работы планировщика приведен в табл. 9.8. Процессы А, В и С создаются одновременно с одним и тем же базовым приоритетом 60 (мы игнорируем наличие значения параметра nice). Таймер прерывает выполнение процесса 60 раз в секунду и увеличивает значение счетчика текущего процесса. В примере предполагается, что ни один процесс не блокируется сам по себе и нет никаких других процессов, готовых к выполнению. Сравните эту таблицу с табл. 9.7.