В соответствии с алгоритмами, основанными на квантовании, каждому процессу поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени – квант. Смена активного процесса происходит, если:
- процесс завершился и покинул систему,
- произошла ошибка,
- процесс перешел в состояние ОЖИДАНИЕ,
- исчерпан квант процессорного времени, отведенный данному процессу.
Граф состояний процесса при планировании, основанном на квантовании, приведен на рис.
Процесс завершен или ошибка
Процессу предоставлен Процесс инициировал
квант Процесс ввод-вывод
исчерпал квант
Ввод-вывод
завершен
Граф состояний в системе с квантованием
Процесс, исчерпавший свой квант, переводится в состояние ГОТОВНОСТЬ. Он ожидает предоставления ему нового кванта процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый процесс из очереди готовых.
Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени.
Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Типичные значения кванта: десятки – сотни миллисекунд. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании.
Рассмотрим следующий пример. Пусть в очереди в состоянии Готовность находятся три процесса p0, p1 и p2, для которых известны времена их выполнения процессором(ВВП). Эти времена приведены в таблица 3.1 в некоторых условных единицах.
Таблица 3.1.
Процесс
p0
p1
p2
Продолжительность очередного ВВП
Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка ВВП, что процессы не совершают операций ввода-вывода и что время переключения контекста так мало, что им можно пренебречь. Пусть величина кванта времени равна 4.
Выполнение этих процессов иллюстрируется таблица 3.2.
Таблица 3.2.
Время
p0
В
В
В
В
Г
Г
Г
Г
Г
В
В
В
В
В
В
В
В
В
p1
Г
Г
Г
Г
В
В
В
В
p2
Г
Г
Г
Г
Г
Г
Г
Г
В
Обозначение "В" используется в ней для процесса, находящегося в состоянии ВЫПОЛНЕНИЕ, обозначение "Г" – для процессов в состоянии ГОТОВНОСТЬ, пустые ячейки соответствуют завершившимся процессам. Состояния процессов показаны на протяжении соответствующей единицы времени, т. е. колонка с номером 1 соответствует промежутку времени от 0 до 1. Первым для исполнения выбирается процесс p0. Продолжительность его ВВП больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид p1, p2, p0. Следующим начинает выполняться процесс p1. Время его исполнения совпадает с величиной выделенного кванта, поэтому процесс работает до своего завершения. Теперь очередь процессов в состоянии готовность состоит из двух процессов, p2 и p0. Процессор выделяется процессу p2. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу p0 – единственному не закончившему к этому моменту свою работу. Время ожидания для процесса p0 (количество символов "Г" в соответствующей строке) составляет 5 единиц времени, для процесса p1 – 4 единицы времени, для процесса p2 – 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6(6) единицы времени. Полное время выполнения для процесса p0 (количество непустых столбцов в соответствующей строке) составляет 18 единиц времени, для процесса p1 – 8 единиц, для процесса p2 – 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6(6) единицы времени.