5.4. Многоуровневые очереди с обратными связями

Когда процесс получает в свое распоряжение центральный процессор, диспетчер не имеет ни малейшего представления о том, какое именно количество времени процессора потребуется данному процессу.

Механизм диспетчеризации при этом должен

- оказывать предпочтение коротким процессам;

- оказывать предпочтение процессам, связанным в основном с вводом -выводом, чтобы обеспечить хороший коэффициент использования устройств ввода - вывода;

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

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

Для минимизации среднего времени ожидания большинство рассмотренных ранее алгоритмов с одной очередью использовали информацию, предоставляемую пользователем (например, время выполнения процесса). Во время исполнения информация о каждом процессе может быть пополнена и использована для изменения приоритета этого процесса. Тем самым связь между процессом и очередью становится динамической. Такие очереди называются очередями с обратной связью, поскольку информация о выполнении процесса используется для его диспетчеризации.

Пример многоуровневой очереди с обратными связями приведен на рис.5.4.

Новый процесс входит в сеть очередей с конца верхней очереди. Он перемещается по этой очереди, реализующей алгоритм FCFS , пока не получит в свое распоряжение центральный процессор. Если процесс завершается или освобождает ЦП, чтобы подождать завершения операции ввода-вывода или наступления некоторого события, то этот процесс выходит из сети­­ очередей. Если выделенный квант времени и­­стекает до того, как процесс добровольно освободит ЦП, этот процесс помещается в конец следующей очереди более низкого ­уровня. Этот процесс в следующий раз получит в свое распоряжение ЦП, когда он достигнет начала данной очереди, если при этом не будет процессов, ожидающих в первой очереди. Если данный процесс будет продолжать использовать полный квант вр­емени, предоставляемый на каждом уровне, он продолжит переход в конец очереди следующего нижележащего уровня. Обычно в системе предусматривается некоторая очередь самого нижнего уровня, которая реализует алгоритм циклического обслуживания и в которой данный процесс циркулирует до тех пор, пока не завершится.

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

Рис. 5.4. Многоуровневые очереди с обратными связями

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

Рассмотрим теперь, каким образом подобный механизм реагирует на различные типы процессов. Этот механизм должен оказывать предпочтение процессам, связанным с вводом-выводом, чтобы обеспечить хорошую загрузку устройств ввода-вывода и малое ­время реакции на запросы интерактивных пользователей. Действительно, так и будет, поскольку процесс, связанный с вводом-выводом, будет поступать­ в очередь с очень высоким приоритетом и ему будет быстро предоставляться ЦП. Квант времени для первой очереди выбирается достаточно большим, с тем чтобы подавляющее большинство заданий, связанных с вводом-выводом, успевало выдать запрос ввода-вывода еще до истечения первого кванта. Когда подобный процесс выдает запрос ввода-вывода, он выходит из сети очередей, причем получив истинно приоритетное обслуживание, что и требовалось.

Если верхнюю очередь сети (очередь с очень высоким приоритетом) поступает процесс, требующий много времени центрального процессора, то он получает в свое распоряжение ЦП весьма быстро, однако после истечения выделенного ему кванта времени процесс переходит в конец очереди следующего нижележащего уровня. Теперь этот процесс будет иметь более низкий приоритет, так что вновь поступающие процессы, особенно связанные по преимуществу с вводом-выводом, будут первыми получать в свое распоряжение ЦП. Со временем данный вычислительный процесс все же получит ЦП, ему будет выделен квант времени большей величины, чем в очереди наивысшего приоритета, но он снова не успеет завершиться по истечении этого полного кванта. Затем он будет помещен в конец очереди­ следующего нижележащего уровня. Таким образом, данный процесс будет продолжать переходить в очереди с более низкими приоритетами и будет дольше ждать в промежутках между выделяемыми ему квантами времени и каждый раз полностью использовать свой квант, когда будет получать в свое распоряжение ЦП (если при этом не будет прерываться из-за поступления процесса с более высоким приоритетом). В конце концов этот вычислительный процесс окажется в очереди самого низкого уровня с циклическим обслуживанием, где и будет циркулировать, пока не завершится.

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

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

На рис.5.5 показано выполнение ранее представленных процессов с использованием многоуровневых очередей с обратными связями для случаев как с постоянным значением кванта времени (q = 1), так и увеличивающимся в зависимости от уровня очереди (q = 2 ⁿ ). Числовые значения времени, характеризующего выполнение процессов, приведены в табл.5.3.

Рис.5.5. Сравнение алгоритмов диспетчеризации для многоуровневых очередей с обратными связями

Таблица 5.3

Алгоритм диспетче-ризации	Процесс № Время поступления Время выполнения	1 0 3	2 2 6	3 4 4	4 6 5	5 8 2	Среднее значе-ние
FB q = 1	Время завершения Длительность цикла обработки Время ожидания	4 4 1	20 18 12	16 12 8	19 13 8	11 3 1	10,0 6,0
FB q = 2 ^n	Время завершения Длительность цикла обработки Время ожидания	4 4 1	17 15 9	18 14 10	20 14 9	14 6 4	10,6 6,6

Как следует из табл.5.3, увеличение значения кванта времени при переходе процесса в очередь более низкого уровня позволяет сократить время ожидания для длинных процессов, хотя среднее время ожидания при этом может увеличиться.