Алгоритмы планирования

Вытесняющее и невытесняющее планирование

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

- когда процесс переводится из состояния «исполнение» в состояние «ожидание»;

- когда процесс переводится из состояния «исполнение» в состояние «завершение»;

- когда процесс переводится из состояния «исполнение» в состояние «готовность» (после прерывания от таймера);

- когда процесс переводится из состояния «ожидание» в состояние «готовность».

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

Если планирование осуществляется только в случаях один и два – это невытесняющее планирование, в противном случае говорят о вытесняющем планировании.

Невытесняющее планирование используется в Windows 3.1 и в Apple Macintosh. При таком режиме процесс занимает столько процессорного времени, сколько ему необходимо. При этом переключение процессов возникает только при желании самого процесса передать управление. Этот метод планирования легко реализуем и достаточно эффективен. Он позволяет использовать большую часть процессорного времени на работу самих процессов и до минимума сократить затраты на переключения контекста.

Минусы: возможность полного захвата процессора одним процессом, который вследствие ошибки прерывания зацикливается и не может передать управление другому процессу. Решение – перезагрузка всей ОС.

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

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

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

Рассмотрим три системы:

1. система пакетной обработки. Могут использовать неприоритетный и приоритетный алгоритмы (FIFO)

Задачи алгоритма:

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

2. оборотное время - минимизация времени на ожидание обслуживания и обработку задач;

3 процессор должен быть всегда занят.

2. интерактивные. Могут использовать только приоритетный алгоритм, т.к. нельзя допустить, чтобы один процесс занял надолго процессор (циклическая (Round Robin), приоритетное планирование).

Задачи алгоритма:

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

2 соразмерность - ожидание пользователей.

3. системы реального времени. Могут использовать неприоритетный и приоритетный алгоритм.

Задачи алгоритма:

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

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

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

1. справедливость - каждому процессу - справедливую долю процессорного времени;

2. контроль для выполнения принятой политики;

3. баланс - поддержка занятости всех частей системы.

Дата добавления: 2015-05-10