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

Справедливость (Fairness); малая длительность пребывания (Low sojourn times); составление расписания с неизвестными размерами заданий (Scheduling with unknown job sizes)

Существует несколько естественных алгоритмов без предвидения, таких как First Come First Served (обслуживание в порядке очереди поступления), Processor Sharing (работа над всеми текущими незавершенными заданиями с одинаковой скоростью), Shortest Elapsed Time First (работа над заданием, получившим на текущий момент наименьший объем обслуживания). Коффман и Кляйнрок [2] предложили другой естественный алгоритм, известный как многоуровневая очередь с обратной связью (Multi-Level Feedback Queueing, MLF). MLF работает следующим образом. Имеются очереди Q0;Q1;Q2 и пороговые значения 0 < t0 < h < t. Первоначально по прибытии задание помещается в очередь Q0. Когда задание в очереди Qi получает кумулятивный объем обслуживания <math>t_i</math>, оно перемещается в Qi+1. В любой момент времени алгоритм работает с непустой очередью с наименьшим номером Коффман и Кляйнрок проанализировали MLF в формулировке теории очередей, когда задания поступают в соответствии с пуассоновским процессом, а требования к обработке выбираются идентично и независимо из известного распределения вероятностей.

Хотя алгоритмы без предвидения активно изучались в теории очередей в течение многих десятилетий, само это понятие было рассмотрено Мотвани, Филлипсом и Торнгом [5]относительно недавно в контексте конкурентного анализа. Как и в традиционном конкурентном анализе, без предвидения алгоритм называется c-конкурентным, если для каждого входного экземпляра его производительность не более чем в c раз ниже, чем у оптимального оффлайнового решения для этого экземпляра. Мотвани, Филлипс и Торнг показали следующее.

Теорема 1 [5]. Для задачи минимизации средней продолжительности потока на одной машине любой детерминированный алгоритм без предвидения должен иметь коэффициент конкурентоспособности не менее Q(n1/3), а любой рандомизированный алгоритм – не менее £?(log n), где n – количество заданий в экземпляре.

Не слишком удивительно, что любой детерминированный алгоритм должен иметь плохой коэффициент конкурентоспособности. Например, рассмотрим алгоритм MLF, у которого пороги являются степенями 2, то есть 1, 2, 4, ... Предположим, что n = 2 задания размера 2k+1 поступают в моменты времени 0, 2k, 2 - 2k, …, (2k - 1)2k, соответственно. Тогда легко проверить, что средняя продолжительность потока для MLF равна Q{n2), тогда как у оптимального алгоритма она равна Q{n).

Заметим, что MLF плохо работает на приведенном выше примере, поскольку все задания застревают в очереди до конца, когда у них остается всего одна единица работы. Любопытно, что Калянасундарам и Прухс [3] разработали рандомизированный вариант MLF (названный ими RMLF) и доказали, что его коэффициент конкурентоспособности почти оптимален. Для каждого задания j и для каждой очереди Qi алгоритм RMLF устанавливает порог f,j случайно и независимо в соответствии с усеченным экспоненциальным распределением. Грубо говоря, задание случайного порога гарантирует, что если задание застряло в очереди, то оставшееся время его обработки будет составлять разумную долю от первоначального времени обработки.

Теорема 2 [3]. Алгоритм RMLF является O (log n log log n)-конкурентным относительно рассеянного соперника. Более того, алгоритм RMLF является O(log n log log n)-конкурентным даже относительно адаптивного соперника при условии, что соперник заранее выбирает все размеры заданий.

Позже Беккетти и Леонарди [ ] показали, что на самом деле RMLF оптимально конкурентоспособен с точностью до постоянного коэффициента. Они также проанализировали RMLF на одинаковых параллельных машинах.

Теорема 3 []. Алгоритм RMLF является O (log n)-конкурентным для одной машины. Для нескольких одинаковых машин RMLF достигает коэффициента конкурентоспособности O(log nlog(mn)), где m – количество машин.