2.4 Планирование

Часть операционной системы, отвечающая за выбор рабочего процесса из группы активных процессов, называется планировщиком, а используемый алгоритм – алгоритмом планирования. Практически все процессы чередуют периоды вычислений с операциями ввода-вывода (Рисунок 14).

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

Основные ситуации, когда необходимо применять планирование:

• при создание нового процесса, необходимо решить, какой процесс запустить: родительский или дочерний;

• при завершении работы процесса необходимо из набора готовых процессов выбрать и запустить следующий, если нет ни одного готового, то запускается холостой процесс из операционной системы;

• при блокировании процесса на операции ввода-вывода, семафоре или по-другому, необходимо выбрать и запустить другой процесс;

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

Рисунок 14 – Периоды использования процессора, чередующиеся с ожиданием ввода-вывода: процесс, ограниченный возможностями процессора (а); процесс, ограниченный возможностями устройств ввода-вывода (б)

Если аппаратный таймер выполняет периодические прерывания с частотой 50 Гц, 60 Гц или с любой другой частотой, решения планирования могут приниматься при каждом прерывании по таймеру или при каждом k-м прерывании. Алгоритмы планирования можно разделить на две категории согласно их поведению после прерываний.

1 Алгоритмы планирования без переключений (неприоритетное планирование), выбирают процесс и позволяют его работать вплоть до блокировки (в ожидании ввода-вывода или другого процесса), либо вплоть до того момента, когда процесс сам не отдаст процессор. Процесс может работать часами.

2 Алгоритмы планирования с переключениями (приоритетное планирование), выбирают процесс и позволяют ему работать максимально фиксированное время, затем приостанавливается и управление переходит к другому процессу. Приоритетное планирование требует прерываний по таймеру, чтобы передать управление планировщику.

В различных средах используются различные алгоритмы планирования. Выделяют 3 типичных среды [14]:

• системы пакетной обработки данных;

• интерактивные системы;

• системы реального времени.

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

Во вторых системах необходимы алгоритмы с переключениями, чтобы предотвратить захват процессора одним процессом.

В третьих системах приоритетное планирование необязательно, т.к. там существуют другие программы, которые знают когда надо блокироваться.

Основные задачи алгоритмов планирования:

а) для всех систем;

1) справедливость – предоставление каждому процессу справедливой доли процессорного времени;

2) принудительное применение политики – контроль за выполнением принятой политики (т.е., к примеру, предоставление процессам контроля безопасности процессора по первому требованию);

3) баланс – поддержка занятости всех частей системы (т.е. важно, чтобы работало больше устройств, чем один процесс только производил вычисления);

б) для систем пакетной обработки данных;

1) пропускная способность – максимальное количество задач в час;

2) оборотное время – минимизация времени, затрачиваемого на ожидание обслуживания и обработку задачи;

3) использование процессора – поддержка постоянной занятости процессора;

в) для интерактивных систем;

1) время отклика – быстрая реакция на запросы;

2) соразмерность – выполнение пожеланий пользователя;

г) для систем реального времени;

1) окончание работы к сроку – предотвращение потери данных;

2) предсказуемость – предотвращение деградации качества в мультимедийных системах.

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