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

Обозначим за <math>\mathcal{J} = \{ 1, 2, ..., n \}</math> множество заданий во входном экземпляре задачи. Каждое задание <math>j</math> характеризуется сроком запуска <math>r_j \;</math> и требованием к обработке <math>p_j \;</math>. В онлайновом режиме задание <math>j</math> сообщается планировщику только в момент времени <math>r_j</math>. Еще одним ограничением является ''режим с отсутствием предвидения'', в котором в момент <math>r_j</math> раскрывается только существование задания <math>j</math>; в частности, величина <math>p_j</math> планировщику неизвестна до тех пор, пока задание не выполнит свое требование к обработке и не покинет систему. Пусть имеется расписание; тогда время завершения <math>c_j</math> задания представляет собой самое раннее время, в которое задание <math>j</math> получает объем обслуживания <math>p_j</math>. Продолжительность потока <math>f_j</math> задания <math>j</math> определяется как <math>c_j - r_j</math>. Расписание называется вытесняющим, если задание может быть прервано произвольно, и его выполнение может быть возобновлено позже с момента прерывания без каких-либо штрафов. Хорошо известно, что вытеснение необходимо для получения разумных гарантий даже в оффлайновом режиме [4].  

Существует несколько естественных алгоритмов без предвидения, таких как First Come First Served (обслуживание в порядке поступления), Processor Sharing (работа над всеми текущими незавершенными заданиями с одинаковой скоростью), Shortest Elapsed Time First (работа над заданием, получившим на текущий момент наименьший объем обслуживания). Коффман и Кляйнрок [2] предложили еще один естественный алгоритм, получиаший название «многоуровневая очередь с обратной связью» (Multi-Level Feedback Queueing, MLF). MLF работает следующим образом. Имеются очереди <math>Q_0, Q_1, Q_2, ...</math>  и пороговые значения <math>0 < t_0 < t_1 < t_2...</math>. Первоначально по прибытии задание помещается в очередь <math>Q_0</math>. Когда задание в очереди <math>Q_i</math> получает кумулятивный объем обслуживания <math>t_i</math>, оно перемещается в <math>Q_{i + 1}</math>. В любой момент времени алгоритм работает с непустой очередью с наименьшим номером. Коффман и Кляйнрок проанализировали MLF в формулировке теории очередей, когда задания поступают в соответствии с пуассоновским процессом, а требования к обработке выбираются идентично и независимо из известного распределения вероятностей.