Планирование с учетом наименьшего прошедшего времени обработки: различия между версиями
Irina (обсуждение | вклад) м (→Нотация) |
KVN (обсуждение | вклад) |
||
(не показано 12 промежуточных версий 1 участника) | |||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Данная задача связана с планированием динамически поступающих заданий в сценарии, когда требования к обработке заданий планировщику неизвестны. Отсутствие знания о том, сколько времени займет выполнение задания, нередко встречается в реальных системах, где такую информацию может быть трудно или невозможно получить. Цель состоит в том, чтобы составить расписание заданий, обеспечивающее пользователям высокое качество обслуживания. В частности, целью является разработка алгоритмов, демонстрирующих хорошую среднюю производительность и являющихся справедливыми в том смысле, что ни одно подмножество пользователей не получает существенно более низкой производительности по сравнению с другими. | |||
== Нотация == | == Нотация == | ||
Обозначим за <math>\mathcal{J} = \{ 1, 2, ..., n \}</math> множество заданий во входном экземпляре задачи. Каждое задание j характеризуется временем | Обозначим за <math>\mathcal{J} = \{ 1, 2, ..., n \}</math> множество заданий во входном экземпляре задачи. Каждое задание j характеризуется временем высвобождения <math>r_j</math> и требованием к обработке <math>p_j</math>. В онлайновом режиме задание j сообщается планировщику только в момент времени <math>r_j</math>. Еще одним ограничением является режим ''с отсутствием предвидения'', в котором в момент <math>r_j</math> раскрывается только существование задания j; в частности, <math>p_j</math> планировщику неизвестно до тех пор, пока задание не выполнит свое требование к обработке и не покинет систему. Пусть имеется расписание; тогда время завершения <math>c_j</math> задания представляет собой самое раннее время, в которое задание j получает объем обслуживания <math>p_j</math>. Продолжительность потока <math>f_j</math> задания j определяется как <math>c_j - r_j</math>. Протяженность задания определяется как отношение продолжительности потока к его объему. Протяженностью также называют нормализованную продолжительность потока или его замедление, и она является естественной мерой справедливости, поскольку измеряет время ожидания задания на единицу полученного обслуживания. Расписание называется вытесняющим, если задание может быть прервано произвольно, и его выполнение может быть возобновлено позже с момента прерывания без каких-либо штрафов. Хорошо известно, что вытеснение необходимо для получения разумных гарантий продолжительности потока даже в оффлайновом режиме [5]. | ||
Вспомним, что онлайновый алгоритм Shortest Remaining Processing Time (SRPT), который в любой момент времени работает над заданием с наименьшим оставшимся временем обработки, является оптимальным для минимизации средней продолжительности потока. | Вспомним, что онлайновый алгоритм Shortest Remaining Processing Time (SRPT), который в любой момент времени работает над заданием с наименьшим оставшимся временем обработки, является оптимальным для минимизации средней продолжительности потока. Однако алгоритм SRPT часто критикуют за то, что он может привести к «зависанию» заданий, в случае которого некоторые задания могут откладываться на неопределенное время. Например, рассмотрим последовательность, в которой задание размера 3 поступает в момент времени t = 0, а затем в течение длительного времени одно задание размера 1 поступает каждую единицу времени, начиная с t = 1. При использовании алгоритма SRPT задание размера 3 будет отложено до тех пор, пока не перестанут поступать задания размера 1. С другой стороны, если целью является минимизация максимальной продолжительности потока, то легко увидеть, что оптимальным алгоритмом является алгоритм First in First Out (FIFO). Однако FIFO может работать очень плохо с точки зрения средней продолжительности потока (например, множество маленьких заданий может застрять из-за очень большого задания, которое прибыло чуть раньше). Естественным способом сбалансировать среднюю и наихудшую производительность является рассмотрение <math>\ell_p</math>-норм продолжительности потока и протяженности, где <math>\ell_p</math>-норма последовательности <math>x_1, ..., x_n</math> определяется как <math>(\sum_i x^p_i)^{1/p}</math>. | ||
Shortest Elapsed Time First (SETF) – это алгоритм без предвидения, который в любой момент времени работает над заданием, получившим на текущий момент наименьший объем обслуживания. Это естественный способ отдать предпочтение коротким заданиям в условиях отсутствия знания о размерах заданий. Фактически SETF представляет собой непрерывную версию алгоритма многоуровневой обратной связи (Multi-Level Feedback, MLF). К сожалению, SETF (или любой другой детерминированный алгоритм без предвидения) плохо работает в рамках конкурентного анализа, где алгоритм называется c-конкурентным, если для каждого входного экземпляра его производительность не более чем в ''c'' раз ниже, чем у оптимального автономного (обладающего предвидением) решения для этого экземпляра [7]. Однако конкурентный анализ может быть слишком пессимистичным в своих гарантиях. Способ обойти эту проблему был предложен Кальянасундарамом и Прусом [6], которые позволили онлайн-планировщику использовать немного более быстрый процессор, чтобы компенсировать отсутствие знаний о будущих поступлениях и размерах заданий. Алгоритм <math>Alg</math> является s-скоростным, c-конкурентным по скорости, где ''c'' – отношение наихудшего случая для всех экземпляров I, <math>Alg_s(I)/Opt_1(I)</math>, где <math>Alg_s</math> – значение решения, полученного <math>Alg</math> при использовании s-скоростного процессора, а <math>Opt_1</math> – оптимальное значение при использовании процессора с единичной скоростью. Как правило, наиболее интересные результаты получаются в случаях, когда ''c'' мало, а s = (1 + <math>\epsilon</math>) для любого произвольного <math>\epsilon > 0</math>. | |||
Shortest Elapsed Time First (SETF) – это алгоритм без предвидения, который в любой момент времени работает над заданием, получившим на текущий момент наименьший объем обслуживания. Это естественный способ отдать предпочтение коротким заданиям | |||
== Основные результаты == | == Основные результаты == | ||
В основополагающей работе [ ] Кальянасундарам и Прус доказали следующие положения. | В основополагающей работе [6] Кальянасундарам и Прус доказали следующие положения. | ||
'''Теорема 1 [6]. SETF является <math>(1 + \epsilon)</math>-скоростным, <math>(1 + 1/\epsilon)</math>-конкурентным алгоритмом без предвидения для минимизации средней продолжительности потока на одной машине с вытеснением.''' | |||
Для минимизации средней протяженности Мутукришнан, Раджараман, Шахин и Герке [8] рассмотрели формулировку задачи с предвидением и показали, что алгоритм SRPT является 2-конкурентным для одной машины и 14-конкурентным для нескольких машин. Формулировку без предвидения рассмотрели Бансал, Дхамдхере, Конеманн и Синха [1]. Они получили следующий результат: | |||
'''Теорема 2 [1]. SETF является <math>(1 + \epsilon)</math>-скоростным, <math>O(log^2 P)</math>-конкурентным алгоритмом для минимизации средней растяжимости, где P – отношение максимального размера задания к минимальному. С другой стороны, даже при скорости O(1) любой алгоритм без предвидения является по меньшей мере <math>\Omega(log \; P)</math>-конкурентным. Любопытно, что с точки зрения ''n'' любой алгоритм без предвидения должен быть <math>\Omega(n)</math>-конкурентным даже при ускорении O(1). Более того, SETF является O(n)-конкурентным (даже без дополнительного ускорения).''' | |||
Для специального случая, когда все задания поступают в момент времени 0, алгоритм SETF является оптимальным вплоть до константных коэффициентов. Он O( | '''Для специального случая, когда все задания поступают в момент времени 0, алгоритм SETF является оптимальным вплоть до константных коэффициентов. Он O(log P)-конкурентен (без дополнительного ускорения). Более того, любой алгоритм без предвидения должен быть <math>\Omega(log \; P)</math>-конкурентным даже при ускорении порядка O(1).''' | ||
Ключевой идеей вышеприведенного результата является связь между алгоритмами SETF и SRPT. Во-первых, за счет (1 + | Ключевой идеей вышеприведенного результата является связь между алгоритмами SETF и SRPT. Во-первых, за счет (1 + <math>\epsilon</math>)-ускорения можно показать, что SETF не хуже MLF в случае, когда пороги имеют степень (1 + <math>\epsilon</math>). Во-вторых, поведение MLF на экземпляре ''I'' может быть связано с поведением алгоритма Shortest Job First (SJF) на другом экземпляре ''I''', полученном из ''I'' путем разделения каждого задания на логарифмическое число заданий с геометрически возрастающими размерами. Наконец, производительность SJF связана с SRPT при помощи еще одного ускорения с коэффициентом (1 + <math>\epsilon</math>). | ||
Бансал и Прус [ ] рассмотрели задачу минимизации | Бансал и Прус [2] рассмотрели задачу минимизации <math>\ell_p</math>-норм продолжительности потока и растяжимости на одной машине. Они получили следующий результат: | ||
Теорема 3 [ ]. В постановке задачи с предвидением алгоритмы SRPT и SJF являются (1 + | '''Теорема 3 [2]. В постановке задачи с предвидением алгоритмы SRPT и SJF являются (1 + <math>\epsilon</math>)-скоростными, O(1/<math>\epsilon</math>)-конкурентными для минимизации <math>\ell_p</math>-норм времени потока и растяжимости. С другой стороны, для <math>1 < p < \infty</math> ни один онлайновый алгоритм (возможно, с предвидением) не может быть O(1)-конкурентным для минимизации <math>\ell_p</math>норм растяжимости или продолжительности потока без ускорения. В частности, любой рандомизированный онлайн-алгоритм является по меньшей мере <math>\Omega(n^{(p - 1) / 3p^2})</math>-конкурентным для <math>\ell_p</math>-норм растяжимости и по меньшей мере <math>\Omega(n^{(p - 1) / p (3p - 1)})</math>-конкурентным для <math>\ell_p</math>-норм продолжительности потока.''' | ||
Вышеприведенные нижние границы несколько удивительны, поскольку SRPT и FIFO оптимальны для случая p = 1 и p = | Вышеприведенные нижние границы несколько удивительны, поскольку SRPT и FIFO оптимальны для случая p = 1 и p = <math>\infty</math> для продолжительности потока. | ||
Бансал и Прус [ ] также рассматривают вариант задачи без предвидения. | Бансал и Прус [2] также рассматривают вариант задачи без предвидения. | ||
Теорема 4 [ ]. В постановке задачи без предвидения алгоритм SETF является (1 + | '''Теорема 4 [2]. В постановке задачи без предвидения алгоритм SETF является <math>(1 + \epsilon)</math>-скоростным, <math>O(1 / \epsilon^{2 + 2/p})</math>-конкурентным для минимизации <math>\ell_p</math>-норм продолжительности потока. Для минимизации <math>\ell_p</math>-норм растяжимости SETF является <math>(1 + \epsilon)</math>-скоростным, <math>O(1 / \epsilon^{3 + 1/p} \cdot log^{1 + 1/p} P)</math>-конкурентным.''' | ||
Наконец, | Наконец, Бансал и Прус также рассматривают алгоритм Round Robin (RR) или Processor Sharing, который в любой момент времени делит процессор поровну между незавершенными заданиями. Считается, что RR является идеальной справедливой стратегией, поскольку одинаково относится ко всем незавершенным заданиям. Тем не менее, они показали следующий результат: | ||
Теорема 5. Для любого p > | '''Теорема 5. Для любого <math>p \ge 1</math> существует <math>\epsilon > 0</math>, такое, что даже при наличии в <math>(1 + \epsilon)</math> раз более быстрого процессора алгоритм RR не является <math>n^{o(1)}</math>-конкурентным для минимизации <math>\ell_p</math>-норм продолжительности потока. В частности, для <math>\epsilon < 1/2p</math> алгоритм RR является <math>(1 + \epsilon)</math>-скоростным, <math>\Omega(n^{(1 - 2 \epsilon p)/p})</math>-конкурентным. Для <math>\ell_p</math>-норм растяжимости RR является <math>\Omega(n)</math>-конкурентным, как и фактически любой рандомизированный алгоритм без предвидения.''' | ||
Приведенные выше результаты были расширены по нескольким направлениям. Бансал и Прус [ ] распространили эти результаты на взвешенные | Приведенные выше результаты были расширены по нескольким направлениям. Бансал и Прус [2] распространили эти результаты на ''взвешенные'' <math>\ell_p</math>-нормы продолжительности потока и растяжимости. Чекури, Ханна, Кумар и Гель [4] распространили их результаты на случай нескольких машин. Их алгоритмы особенно элегантны: каждое задание назначается некоторой машине случайным образом, и все задания на определенной машине обрабатываются с помощью алгоритма SRPT или SETF (в зависимости от применимости). | ||
== Применение == | == Применение == | ||
Строка 65: | Строка 61: | ||
Наиболее первоочередная задача заключается в том, можно ли сократить разрыв между O(log P) и | Наиболее первоочередная задача заключается в том, можно ли сократить разрыв между <math>O(log^2 P)</math> и <math>\Omega(log \; P)</math> для минимизации средней растяжимости в формулировке без предвидения. | ||
== См. также== | == См. также== | ||
Строка 92: | Строка 88: | ||
10. Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall Inc., Englewood Cliffs (1992) | 10. Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall Inc., Englewood Cliffs (1992) | ||
[[Категория: Совместное определение связанных терминов]] |
Текущая версия от 11:57, 7 декабря 2024
Ключевые слова и синонимы
Продолжительность пребывания; время отклика; составление расписания с неизвестными размерами заданий; алгоритм MLF; очереди с обратной связью
Постановка задачи
Данная задача связана с планированием динамически поступающих заданий в сценарии, когда требования к обработке заданий планировщику неизвестны. Отсутствие знания о том, сколько времени займет выполнение задания, нередко встречается в реальных системах, где такую информацию может быть трудно или невозможно получить. Цель состоит в том, чтобы составить расписание заданий, обеспечивающее пользователям высокое качество обслуживания. В частности, целью является разработка алгоритмов, демонстрирующих хорошую среднюю производительность и являющихся справедливыми в том смысле, что ни одно подмножество пользователей не получает существенно более низкой производительности по сравнению с другими.
Нотация
Обозначим за [math]\displaystyle{ \mathcal{J} = \{ 1, 2, ..., n \} }[/math] множество заданий во входном экземпляре задачи. Каждое задание j характеризуется временем высвобождения [math]\displaystyle{ r_j }[/math] и требованием к обработке [math]\displaystyle{ p_j }[/math]. В онлайновом режиме задание j сообщается планировщику только в момент времени [math]\displaystyle{ r_j }[/math]. Еще одним ограничением является режим с отсутствием предвидения, в котором в момент [math]\displaystyle{ r_j }[/math] раскрывается только существование задания j; в частности, [math]\displaystyle{ p_j }[/math] планировщику неизвестно до тех пор, пока задание не выполнит свое требование к обработке и не покинет систему. Пусть имеется расписание; тогда время завершения [math]\displaystyle{ c_j }[/math] задания представляет собой самое раннее время, в которое задание j получает объем обслуживания [math]\displaystyle{ p_j }[/math]. Продолжительность потока [math]\displaystyle{ f_j }[/math] задания j определяется как [math]\displaystyle{ c_j - r_j }[/math]. Протяженность задания определяется как отношение продолжительности потока к его объему. Протяженностью также называют нормализованную продолжительность потока или его замедление, и она является естественной мерой справедливости, поскольку измеряет время ожидания задания на единицу полученного обслуживания. Расписание называется вытесняющим, если задание может быть прервано произвольно, и его выполнение может быть возобновлено позже с момента прерывания без каких-либо штрафов. Хорошо известно, что вытеснение необходимо для получения разумных гарантий продолжительности потока даже в оффлайновом режиме [5].
Вспомним, что онлайновый алгоритм Shortest Remaining Processing Time (SRPT), который в любой момент времени работает над заданием с наименьшим оставшимся временем обработки, является оптимальным для минимизации средней продолжительности потока. Однако алгоритм SRPT часто критикуют за то, что он может привести к «зависанию» заданий, в случае которого некоторые задания могут откладываться на неопределенное время. Например, рассмотрим последовательность, в которой задание размера 3 поступает в момент времени t = 0, а затем в течение длительного времени одно задание размера 1 поступает каждую единицу времени, начиная с t = 1. При использовании алгоритма SRPT задание размера 3 будет отложено до тех пор, пока не перестанут поступать задания размера 1. С другой стороны, если целью является минимизация максимальной продолжительности потока, то легко увидеть, что оптимальным алгоритмом является алгоритм First in First Out (FIFO). Однако FIFO может работать очень плохо с точки зрения средней продолжительности потока (например, множество маленьких заданий может застрять из-за очень большого задания, которое прибыло чуть раньше). Естественным способом сбалансировать среднюю и наихудшую производительность является рассмотрение [math]\displaystyle{ \ell_p }[/math]-норм продолжительности потока и протяженности, где [math]\displaystyle{ \ell_p }[/math]-норма последовательности [math]\displaystyle{ x_1, ..., x_n }[/math] определяется как [math]\displaystyle{ (\sum_i x^p_i)^{1/p} }[/math].
Shortest Elapsed Time First (SETF) – это алгоритм без предвидения, который в любой момент времени работает над заданием, получившим на текущий момент наименьший объем обслуживания. Это естественный способ отдать предпочтение коротким заданиям в условиях отсутствия знания о размерах заданий. Фактически SETF представляет собой непрерывную версию алгоритма многоуровневой обратной связи (Multi-Level Feedback, MLF). К сожалению, SETF (или любой другой детерминированный алгоритм без предвидения) плохо работает в рамках конкурентного анализа, где алгоритм называется c-конкурентным, если для каждого входного экземпляра его производительность не более чем в c раз ниже, чем у оптимального автономного (обладающего предвидением) решения для этого экземпляра [7]. Однако конкурентный анализ может быть слишком пессимистичным в своих гарантиях. Способ обойти эту проблему был предложен Кальянасундарамом и Прусом [6], которые позволили онлайн-планировщику использовать немного более быстрый процессор, чтобы компенсировать отсутствие знаний о будущих поступлениях и размерах заданий. Алгоритм [math]\displaystyle{ Alg }[/math] является s-скоростным, c-конкурентным по скорости, где c – отношение наихудшего случая для всех экземпляров I, [math]\displaystyle{ Alg_s(I)/Opt_1(I) }[/math], где [math]\displaystyle{ Alg_s }[/math] – значение решения, полученного [math]\displaystyle{ Alg }[/math] при использовании s-скоростного процессора, а [math]\displaystyle{ Opt_1 }[/math] – оптимальное значение при использовании процессора с единичной скоростью. Как правило, наиболее интересные результаты получаются в случаях, когда c мало, а s = (1 + [math]\displaystyle{ \epsilon }[/math]) для любого произвольного [math]\displaystyle{ \epsilon \gt 0 }[/math].
Основные результаты
В основополагающей работе [6] Кальянасундарам и Прус доказали следующие положения.
Теорема 1 [6]. SETF является [math]\displaystyle{ (1 + \epsilon) }[/math]-скоростным, [math]\displaystyle{ (1 + 1/\epsilon) }[/math]-конкурентным алгоритмом без предвидения для минимизации средней продолжительности потока на одной машине с вытеснением.
Для минимизации средней протяженности Мутукришнан, Раджараман, Шахин и Герке [8] рассмотрели формулировку задачи с предвидением и показали, что алгоритм SRPT является 2-конкурентным для одной машины и 14-конкурентным для нескольких машин. Формулировку без предвидения рассмотрели Бансал, Дхамдхере, Конеманн и Синха [1]. Они получили следующий результат:
Теорема 2 [1]. SETF является [math]\displaystyle{ (1 + \epsilon) }[/math]-скоростным, [math]\displaystyle{ O(log^2 P) }[/math]-конкурентным алгоритмом для минимизации средней растяжимости, где P – отношение максимального размера задания к минимальному. С другой стороны, даже при скорости O(1) любой алгоритм без предвидения является по меньшей мере [math]\displaystyle{ \Omega(log \; P) }[/math]-конкурентным. Любопытно, что с точки зрения n любой алгоритм без предвидения должен быть [math]\displaystyle{ \Omega(n) }[/math]-конкурентным даже при ускорении O(1). Более того, SETF является O(n)-конкурентным (даже без дополнительного ускорения).
Для специального случая, когда все задания поступают в момент времени 0, алгоритм SETF является оптимальным вплоть до константных коэффициентов. Он O(log P)-конкурентен (без дополнительного ускорения). Более того, любой алгоритм без предвидения должен быть [math]\displaystyle{ \Omega(log \; P) }[/math]-конкурентным даже при ускорении порядка O(1).
Ключевой идеей вышеприведенного результата является связь между алгоритмами SETF и SRPT. Во-первых, за счет (1 + [math]\displaystyle{ \epsilon }[/math])-ускорения можно показать, что SETF не хуже MLF в случае, когда пороги имеют степень (1 + [math]\displaystyle{ \epsilon }[/math]). Во-вторых, поведение MLF на экземпляре I может быть связано с поведением алгоритма Shortest Job First (SJF) на другом экземпляре I', полученном из I путем разделения каждого задания на логарифмическое число заданий с геометрически возрастающими размерами. Наконец, производительность SJF связана с SRPT при помощи еще одного ускорения с коэффициентом (1 + [math]\displaystyle{ \epsilon }[/math]).
Бансал и Прус [2] рассмотрели задачу минимизации [math]\displaystyle{ \ell_p }[/math]-норм продолжительности потока и растяжимости на одной машине. Они получили следующий результат:
Теорема 3 [2]. В постановке задачи с предвидением алгоритмы SRPT и SJF являются (1 + [math]\displaystyle{ \epsilon }[/math])-скоростными, O(1/[math]\displaystyle{ \epsilon }[/math])-конкурентными для минимизации [math]\displaystyle{ \ell_p }[/math]-норм времени потока и растяжимости. С другой стороны, для [math]\displaystyle{ 1 \lt p \lt \infty }[/math] ни один онлайновый алгоритм (возможно, с предвидением) не может быть O(1)-конкурентным для минимизации [math]\displaystyle{ \ell_p }[/math]норм растяжимости или продолжительности потока без ускорения. В частности, любой рандомизированный онлайн-алгоритм является по меньшей мере [math]\displaystyle{ \Omega(n^{(p - 1) / 3p^2}) }[/math]-конкурентным для [math]\displaystyle{ \ell_p }[/math]-норм растяжимости и по меньшей мере [math]\displaystyle{ \Omega(n^{(p - 1) / p (3p - 1)}) }[/math]-конкурентным для [math]\displaystyle{ \ell_p }[/math]-норм продолжительности потока.
Вышеприведенные нижние границы несколько удивительны, поскольку SRPT и FIFO оптимальны для случая p = 1 и p = [math]\displaystyle{ \infty }[/math] для продолжительности потока.
Бансал и Прус [2] также рассматривают вариант задачи без предвидения.
Теорема 4 [2]. В постановке задачи без предвидения алгоритм SETF является [math]\displaystyle{ (1 + \epsilon) }[/math]-скоростным, [math]\displaystyle{ O(1 / \epsilon^{2 + 2/p}) }[/math]-конкурентным для минимизации [math]\displaystyle{ \ell_p }[/math]-норм продолжительности потока. Для минимизации [math]\displaystyle{ \ell_p }[/math]-норм растяжимости SETF является [math]\displaystyle{ (1 + \epsilon) }[/math]-скоростным, [math]\displaystyle{ O(1 / \epsilon^{3 + 1/p} \cdot log^{1 + 1/p} P) }[/math]-конкурентным.
Наконец, Бансал и Прус также рассматривают алгоритм Round Robin (RR) или Processor Sharing, который в любой момент времени делит процессор поровну между незавершенными заданиями. Считается, что RR является идеальной справедливой стратегией, поскольку одинаково относится ко всем незавершенным заданиям. Тем не менее, они показали следующий результат:
Теорема 5. Для любого [math]\displaystyle{ p \ge 1 }[/math] существует [math]\displaystyle{ \epsilon \gt 0 }[/math], такое, что даже при наличии в [math]\displaystyle{ (1 + \epsilon) }[/math] раз более быстрого процессора алгоритм RR не является [math]\displaystyle{ n^{o(1)} }[/math]-конкурентным для минимизации [math]\displaystyle{ \ell_p }[/math]-норм продолжительности потока. В частности, для [math]\displaystyle{ \epsilon \lt 1/2p }[/math] алгоритм RR является [math]\displaystyle{ (1 + \epsilon) }[/math]-скоростным, [math]\displaystyle{ \Omega(n^{(1 - 2 \epsilon p)/p}) }[/math]-конкурентным. Для [math]\displaystyle{ \ell_p }[/math]-норм растяжимости RR является [math]\displaystyle{ \Omega(n) }[/math]-конкурентным, как и фактически любой рандомизированный алгоритм без предвидения.
Приведенные выше результаты были расширены по нескольким направлениям. Бансал и Прус [2] распространили эти результаты на взвешенные [math]\displaystyle{ \ell_p }[/math]-нормы продолжительности потока и растяжимости. Чекури, Ханна, Кумар и Гель [4] распространили их результаты на случай нескольких машин. Их алгоритмы особенно элегантны: каждое задание назначается некоторой машине случайным образом, и все задания на определенной машине обрабатываются с помощью алгоритма SRPT или SETF (в зависимости от применимости).
Применение
Алгоритм SETF и его варианты, такие как MLF, широко используются в операционных системах [9, 10]. Отметим, что SETF не совсем практичен, поскольку каждое задание может вытесняться бесконечное число раз. Однако варианты SETF с меньшим числом вытеснений довольно популярны.
Открытые вопросы
Было бы любопытно исследовать другие понятия справедливости в контексте динамического планирования. В частности, хотелось бы рассмотреть алгоритмы, одновременно являющиеся справедливыми и имеющие хорошую среднюю производительность.
Наиболее первоочередная задача заключается в том, можно ли сократить разрыв между [math]\displaystyle{ O(log^2 P) }[/math] и [math]\displaystyle{ \Omega(log \; P) }[/math] для минимизации средней растяжимости в формулировке без предвидения.
См. также
- Минимизация продолжительности потока
- Минимальная продолжительность потока
- Многоуровневые очереди с обратными связями
Литература
1. Bansal, N., Dhamdhere, K., Konemann, J., Sinha, A.: Non-Clairvoyant Scheduling for Minimizing Mean Slowdown. Algorithmica 40(4), 305-318 (2004)
2. Bansal, N., Pruhs, K.: Server scheduling in the Lp norm: a rising tide lifts all boat. In: Symposium on Theory of Computing, STOC, pp. 242-250 (2003)
3. Bansal, N., Pruhs, K.: Server scheduling in the weighted Lp norm. In: LATIN, pp.434-443 (2004)
4. Chekuri, C., Goel, A., Khanna, S., Kumar, A.: Multi-processor scheduling to minimize flow time with epsilon resource augmentation. In: Symposium on Theory of Computing, STOC, pp. 363-372 (2004)
5. 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)
6. Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617-643 (2000)
7. Motwani, R., Phillips, S., Torng, E.: Non-Clairvoyant Scheduling. Theor. Comput. Sci. 130(1), 17-47 (1994)
8. Muthukrishnan, S., Rajaraman, R., Shaheen, A., Gehrke, J.: Online Scheduling to Minimize Average Stretch. SIAM J. Comput. 34(2),433-452(2004)
9. Nutt, G.: Operating System Projects Using Windows NT. Addison Wesley, Reading (1999)
10. Tanenbaum, A.S.: Modern Operating Systems. Prentice-Hall Inc., Englewood Cliffs (1992)