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

Ключевые слова и синонимы

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

Постановка задачи

Задача связана с планированием динамически поступающих заданий в сценарии, когда требования к обработке заданий неизвестны планировщику. Это классическая проблема, возникающая, например, при составлении расписания работы процессора, когда пользователи подают задания (различные команды операционной системе) с течением времени. Планировщик знает только о существовании задания и не знает, сколько времени потребуется на его выполнение, а цель состоит в том, чтобы запланировать задания так, чтобы обеспечить хорошее качество обслуживания пользователей. Формально далее будет рассматриваться мера средней продолжительности потока, определяемая как длительность времени с момента выпуска задания до окончания выполнения его требований по обработке.

Нотация

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

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

Вспомним, что онлайновый алгоритм Shortest Remaining Processing Time (SRPT), который в любой момент времени работает над заданием с наименьшим оставшимся временем обработки, создает оптимальное расписание. Однако SRPT требует знания размеров заданий и, следовательно, не является алгоритмом без предвидения. Поскольку алгоритм без предвидения знает только нижнюю границу размера задания (определяемую количеством обслуживания, которое оно получило на данный момент), MLF пытается подражать SRPT, отдавая предпочтение заданиям, которые на текущий момент получили наименьший объем обслуживания.

Основные результаты

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

Теорема 1 [5]. Для задачи минимизации средней продолжительности потока на одной машине любой детерминированный алгоритм без предвидения должен иметь коэффициент конкурентоспособности не менее [math]\displaystyle{ \Omega(n^{1/3}) }[/math], а любой рандомизированный алгоритм – не менее [math]\displaystyle{ \Omega(log \; n) }[/math], где n – количество заданий в экземпляре.

Не слишком удивительно, что любой детерминированный алгоритм должен иметь плохой коэффициент конкурентоспособности. Например, рассмотрим алгоритм MLF, у которого пороги являются степенями 2, то есть 1, 2, 4, ... Предположим, что [math]\displaystyle{ n = 2^k }[/math] заданий размера [math]\displaystyle{ 2^k + 1 }[/math] каждое поступают в моменты времени [math]\displaystyle{ 0, 2^k, 2 \cdot 2^k, ..., (2^k - 1)2^k }[/math], соответственно. Тогда легко проверить, что средняя продолжительность потока для MLF равна [math]\displaystyle{ \Omega(n^2) }[/math], тогда как у оптимального алгоритма она равна [math]\displaystyle{ \Omega(n) }[/math].

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

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

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

Теорема 3 [1]. Алгоритм RMLF является [math]\displaystyle{ O(log \; n) }[/math]-конкурентным для одной машины. Для нескольких одинаковых машин RMLF достигает коэффициента конкурентоспособности [math]\displaystyle{ O(log \; n \; log \Big( \frac{m}{n} \Big) ) }[/math], где m – количество машин.

Применение

Алгоритм MLF и его варианты широко используются в операционных системах [6, 7]. Эти алгоритмы не только близки к оптимальным с точки зрения продолжительности потока, но и обладают другими привлекательными свойствами, например, амортизированное число вытеснений является логарифмическим (вытеснения происходят только случае, когда задание прибывает, выбывает или переходит в другую очередь).

Открытые вопросы

Неизвестно, существует ли o(n)-конкурентный детерминированный алгоритм. Было бы любопытно устранить разрыв между верхней и нижней границами для этого случая. Зачастую в реальных системах, даже если планировщик не знает точного размера заданий, он может иметь некоторую информацию о его распределении, основанную на исторических данных. Интересным направлением исследований может стать разработка и анализ алгоритмов, использующих эту информацию.

См. также

• Минимизация продолжительности потока
• Минимальная продолжительность потока
• Планирование с учетом наименьшего прошедшего времени обработки

Литература

1. Becchetti, L., Leonardi, S.: Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. J. ACM (JACM) 51(4), 517-539 (2004)

2. Coffman, E.G., Kleinrock, L.: Feedback Queueing Models for Time-Shared Systems. J. ACM (JACM) 15(4), 549-576 (1968)

3. Kalyanasundaram, B., Pruhs, K.: Minimizing flow time nonclairvoyantly. J. ACM (JACM) 50(4), 551-567 (2003)

4. Kellerer, H., Tautenhahn, T., Woeginger, G.J.: Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine. SIAM J. Comput. 28(4), 1155-1166 (1999)

5. Motwani, R., Phillips, S., Torng, E.: Non-Clairvoyant Scheduling. Theor. Comput. Sci. 130(1), 17-47 (1994)

6. Nutt, G.: Operating System Projects Using Windows NT. Addison Wesley, Reading (1999)

7. Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall Inc., Upper Saddle River (1992)