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

Хотя алгоритмы без предвидения активно изучались в теории очередей в течение многих десятилетий, само это понятие было рассмотрено Мотвани, Филлипсом и Торнгом [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 случайно и независимо в соответствии с усеченным экспоненциальным распределением. Грубо говоря, задание случайного порога гарантирует, что если задание застряло в очереди, то оставшееся время его обработки будет составлять разумную долю от первоначального времени обработки.