Операционные системы - страница 16

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 «Первым пришёл – первым ушёл»

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

2 Алгоритм «Кратчайшая задача – первая»

Категория алгоритма – без переключений. Суть алгоритма заключается в следующем: если в очереди есть несколько одинаково важных задач, планировщик выбирает первой самую короткую по времени. Эта схема работает лишь в случае одновременного наличия задач и обычно неактуальна.