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

Планирование процессов включает в себя решение следующих задач:

• Определение момента времени для смены выполняемого процесса

• Выбор процесса на выполнение из очереди готовых процессов

• Переключение контекстов старого и нового процессов (обычно решается аппаратно)

Различные алгоритмы планирования решают эти задачи по-разному.

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

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

Современные системы – с вытесняющей многозадачностью.

Существуют механизмы прерывания, основанные на:

• Переключение по времени. Встраивается центральный таймер, который подает сигнал прерывания; может произойти в конкретный момент реального времени системы или по истечению кванта времени; кванты, выделяемые CPU могут быть постоянными и переменными. Переменный квант может динамически изменяться или вычисляться по формулам. Если квант маленький, то контекст очень быстро дергается. Большой квант – большая задержка.

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

Приоритет = (время ожидания + время обслуживания) / время обслуживания.

Планирование с абсолютными приоритетами.

• Если появился процесс наивысшим приоритетом, все остальные приоритеты прерываются.

• Процедура выбора

FIFO – first in, first out

LIFO – last in, first out

RR – round robin – циклическая процедура обслуживания

SJL – shortlist job first – кратчайшие задания – первыми

SRT – shortlist remaining time – по наименьшему оставшемуся до завершения времени

HPF – highest priority first

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