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

Существует несколько естественных алгоритмов без предвидения, таких как 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 в формулировке теории очередей, когда задания поступают в соответствии с пуассоновским процессом, а требования к обработке выбираются идентично и независимо из известного распределения вероятностей.