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

Вытесняющий алгоритм, основанный на приоритетах.

Приоритет – число, характеризующее степень привилегированности потока. Приоритет процесса определяется ОС при его создании, а приоритет потока всегда определён приоритетом процесса. Различают динамические и фиксированные процессы установки приоритетов. Существует 2 разновидности приоритетного планирования: с относительными и с абсолютными приоритетами обслуживания. Они различаются моментом смены процессов.

Смешанные алгоритмы планирования.

В их основе лежит совмещение квантования и алгоритма приоритетов: квант времени, отводимый потоку, зависит от степени его приоритета. Перепланировка происходит, если:

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

2. Активный процесс выполнил системный запрос на доступ к ресурсу, который занят;

3. Процесс выполнил запрос к освободившемуся ресурсу;

4. Аппаратное прерывание, поступившее от периферийных устройств после завершения операции ввода-вывода, переводит процесс в состояние готовности;

5. Внутреннее прерывание сигнализирует об ошибке, которая произошла в результате выполнения процесса.

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

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

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

· переключение контекстов "старого" и "нового" процессов.

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

В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:

· процесс завершился и покинул систему,

· произошла ошибка,

· процесс перешел в состояние ОЖИДАНИЕ,

· исчерпан квант процессорного времени, отведенный данному процессу.

Процесс, который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый процесс из очереди готовых. Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени. Граф состояний процесса, изображенный на рисунке 3, соответствует алгоритму планирования, основанному на квантовании. Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. По разному может быть организована очередь готовых процессов: циклически, по правилу "первый пришел - первый обслужился" (FIFO) или по правилу "последний пришел - первый обслужился" (LIFO). Другая группа алгоритмов использует понятие "приоритет" процесса. Приоритет - это число, характеризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии. Приоритет может выражаться целыми или дробными, положительным или отрицательным значением. Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной платы, либо вычисляться самой ОС по определенным правилам, он может оставаться фиксированным на протяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом. В последнем случае приоритеты называются динамическими. Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты. В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: выбирается процесс, имеющий наивысший приоритет. По-разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности. На рисунке 3 показаны графы состояний процесса для алгоритмов с относительными (а) и абсолютными (б) приоритетами.

Рис.3. Графы состояний процессов в системах
(а) с относительными приоритетами; (б)с абсолютными приоритетами

Контрольные вопросы: – Являются ли синонимами термины «планирование процессов» и «диспетчеризация процессов»? Ответ: Да – Можно ли задачу планирования процессов целиком возложить на приложения? – Понятия: задание, процесс, планирование процесса. – Состояния существования процесса. – Диспетчеризация процесса. – Блок состояния процесса. – Алгоритм диспетчеризации. – Способ выбора процесса для диспетчеризации. – Понятие события. – Блок состояния события. – Механизм установления соответствия между процессом и событием.

Домашнее задание: Конспект лекций

Лекция 2 (2/4)

Проверка Д/З:

1). У 3 чел. Проверить конспекты + ОС будущего 2). 3 чел. спросить по предыдущему (см. выше)

Дата добавления: 2013-12-12