4817
правок
Многоуровневые очереди с обратными связями: различия между версиями
Материал из WEGA
Многоуровневые очереди с обратными связями (посмотреть исходный код)
Версия от 05:12, 13 мая 2025
, 13 майнет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Справедливость (Fairness); малая длительность пребывания (Low sojourn times); составление расписания с неизвестными размерами заданий (Scheduling with unknown job sizes) == Постановка задачи == Задача связана с планированием динамически поступающих з...») |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 5: | Строка 5: | ||
Задача связана с планированием динамически поступающих заданий в сценарии, когда требования к обработке заданий неизвестны планировщику. Это классическая проблема, возникающая, например, при составлении расписания работы процессора, когда пользователи подают задания (различные команды операционной системе) с течением времени. Планировщик знает только о существовании задания и не знает, сколько времени потребуется на его выполнение, а цель состоит в том, чтобы запланировать задания так, чтобы обеспечить хорошее качество обслуживания пользователей. Формально далее будет рассматриваться мера средней продолжительности потока, определяемая как длительность времени с момента выпуска задания до окончания выполнения его требований по обработке. | Задача связана с планированием динамически поступающих заданий в сценарии, когда требования к обработке заданий неизвестны планировщику. Это классическая проблема, возникающая, например, при составлении расписания работы процессора, когда пользователи подают задания (различные команды операционной системе) с течением времени. Планировщик знает только о существовании задания и не знает, сколько времени потребуется на его выполнение, а цель состоит в том, чтобы запланировать задания так, чтобы обеспечить хорошее качество обслуживания пользователей. Формально далее будет рассматриваться мера средней продолжительности потока, определяемая как длительность времени с момента выпуска задания до окончания выполнения его требований по обработке. | ||
'''Нотация''' | |||
Обозначим за <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>. Расписание называется вытесняющим, если задание может быть прервано произвольно, и его выполнение может быть возобновлено позже с момента прерывания без каких-либо штрафов. Хорошо известно, что вытеснение необходимо для получения разумных гарантий даже в оффлайновом режиме. | |||
Существует несколько естественных алгоритмов без предвидения, таких как 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 получает кумулятивный объем обслуживания | |||
Существует несколько естественных алгоритмов без предвидения, таких как 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 в формулировке теории очередей, когда задания поступают в соответствии с пуассоновским процессом, а требования к обработке выбираются идентично и независимо из известного распределения вероятностей. | |||
