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


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

Z1 Y1 X1 ЦП Уровень 1 FIFO

Истечение кванта времени

Готовые процессы Завершение

X1 Z2 Y2 X2 ЦП Уровень 2 FIFO

Истечение кванта времени
. . .

Готовые процессы Завершение

Xn-1 Zn Yn Xn ЦП Уровень n RR

Истечение кванта времени

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

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

Вопросы
1. Укажите различия между планировщиком заданий, планировщиком промежуточного уровня и диспетчером.
2. Перечислите основные цели планирования.
3. Укажите основные различия между рассмотренными алгоритмами планирования.(FIFO, RR и многоуровневыми очередями с обратными связями).
4. Приведите пример, показывающий, почему принцип FIFO является неподходящей дисциплиной планирования для интерактивных пользователей.
5. Определение размера кванта времени — сложная задача, опишите последствия, к которым приведет реализация каждого из следующих методов назначения размера кванта времени:
• выбирается фиксированным и идентичным для всех пользователей;
• выбирается фиксированным и уникальным для каждого пользователя;
• выбирается переменным и уникальным для каждого пользователя.
6. Покажите, каким образом многоуровневые очереди с обратными связями обеспечивают достижение каждой из следующих целей планирования:
• оказывать предпочтение коротким заданиям;
• определять характер задания как можно быстрее и соответствующим образом планировать его выполнение.