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

В соответствии с алгоритмами, основанными на квантовании, каждому процессу поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени – квант. Смена активного процесса происходит, если:

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

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

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

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

Граф состояний процесса при планировании, основанном на квантовании, приведен на рис.

Процесс завершен или ошибка

Процессу предоставлен Процесс инициировал

квант Процесс ввод-вывод

исчерпал квант

Ввод-вывод

завершен

Граф состояний в системе с квантованием

Процесс, исчерпавший свой квант, переводится в состояние ГОТОВНОСТЬ. Он ожидает предоставления ему нового кванта процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый процесс из очереди готовых.

Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени.

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

Рассмотрим следующий пример. Пусть в очереди в состоянии Готовность находятся три процесса p₀, p₁ и p₂, для которых известны времена их выполнения процессором(ВВП). Эти времена приведены в таблица 3.1 в некоторых условных единицах.

Таблица 3.1.
Процесс	p₀	p₁	p₂
Продолжительность очередного ВВП

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

Выполнение этих процессов иллюстрируется таблица 3.2.

Таблица 3.2.

Время

p₀

p₁

p₂

Обозначение "В" используется в ней для процесса, находящегося в состоянии ВЫПОЛНЕНИЕ, обозначение "Г" – для процессов в состоянии ГОТОВНОСТЬ, пустые ячейки соответствуют завершившимся процессам. Состояния процессов показаны на протяжении соответствующей единицы времени, т. е. колонка с номером 1 соответствует промежутку времени от 0 до 1. Первым для исполнения выбирается процесс p₀. Продолжительность его ВВП больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид p₁, p₂, p₀. Следующим начинает выполняться процесс p₁. Время его исполнения совпадает с величиной выделенного кванта, поэтому процесс работает до своего завершения. Теперь очередь процессов в состоянии готовность состоит из двух процессов, p₂ и p₀. Процессор выделяется процессу p₂. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу p₀ – единственному не закончившему к этому моменту свою работу. Время ожидания для процесса p₀ (количество символов "Г" в соответствующей строке) составляет 5 единиц времени, для процесса p₁ – 4 единицы времени, для процесса p₂ – 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6(6) единицы времени. Полное время выполнения для процесса p₀ (количество непустых столбцов в соответствующей строке) составляет 18 единиц времени, для процесса p₁ – 8 единиц, для процесса p₂ – 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6(6) единицы времени.