4640
правок
Планирование с учетом наименьшего прошедшего времени обработки: различия между версиями
Материал из WEGA
Планирование с учетом наименьшего прошедшего времени обработки (посмотреть исходный код)
Версия от 17:08, 23 февраля 2022
, 23 февраля 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
== Основные результаты == | == Основные результаты == | ||
В основополагающей работе [ ] Кальянасундарам и Прус доказали следующие положения. | В основополагающей работе [6] Кальянасундарам и Прус доказали следующие положения. | ||
Теорема 1 [6]. SETF является (1 + | '''Теорема 1 [6]. SETF является <math>(1 + \epsilon)</math>-скоростным, <math>(1 + 1/\epsilon)</math>-конкурентным алгоритмом без предвидения для минимизации средней продолжительности потока на одной машине с вытеснением.''' | ||
Для минимизации средней протяженности Мутукришнан, Раджараман, Шахин и Герке [ ] рассмотрели формулировку задачи с предвидением и показали, что алгоритм SRPT является 2-конкурентным для одной машины и 14-конкурентным для нескольких машин. Формулировку без предвидения рассмотрели Бансал, Дхамдхере, Конеманн и Синха [ ]. Они получили следующий результат: | Для минимизации средней протяженности Мутукришнан, Раджараман, Шахин и Герке [8] рассмотрели формулировку задачи с предвидением и показали, что алгоритм SRPT является 2-конкурентным для одной машины и 14-конкурентным для нескольких машин. Формулировку без предвидения рассмотрели Бансал, Дхамдхере, Конеманн и Синха [1]. Они получили следующий результат: | ||
Теорема 2 [1]. SETF является (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)-конкурентным (даже без дополнительного ускорения).''' | ||
| Строка 32: | Строка 32: | ||
Ключевой идеей вышеприведенного результата является связь между алгоритмами SETF и SRPT. Во-первых, за счет (1 + | Ключевой идеей вышеприведенного результата является связь между алгоритмами SETF и SRPT. Во-первых, за счет (1 + <math>\epsilon</math>)-ускорения можно показать, что SETF не хуже MLF в случае, когда пороги имеют степень (1 + <math>\epsilon</math>). Во-вторых, поведение MLF на экземпляре I может быть связано с поведением алгоритма Shortest Job First (SJF) на другом экземпляре I0, полученном из I путем разделения каждого задания на логарифмическое число заданий с геометрически возрастающими размерами. Наконец, производительность SJF связана с SRPT при помощи еще одного ускорения с коэффициентом (1 + <math>\epsilon</math>). | ||
| Строка 38: | Строка 38: | ||
Теорема 3 [ ]. В постановке задачи с предвидением алгоритмы SRPT и SJF являются (1 + | Теорема 3 [ ]. В постановке задачи с предвидением алгоритмы SRPT и SJF являются (1 + <math>\epsilon</math>)-скоростными, O(1/<math>\epsilon</math>)-конкурентными для минимизации lp-норм времени потока и растяжимости. С другой стороны, для 1 < p < 1 ни один онлайновый алгоритм (возможно, с предвидением) не может быть O(1)-конкурентным для минимизации lp норм растяжимости или продолжительности потока без ускорения. В частности, любой рандомизированный онлайн-алгоритм является по меньшей мере Q{n^ ^13р )-конкурентным для lp-норм растяжимости и по меньшей мере Q(n{P~l)lP{iP~l))-конкурентным для lp-норм продолжительности потока. | ||
| Строка 47: | Строка 47: | ||
Теорема 4 [ ]. В постановке задачи без предвидения алгоритм SETF является (1 + | Теорема 4 [ ]. В постановке задачи без предвидения алгоритм SETF является (1 + <math>\epsilon</math>)-скоростными, 0(l/€2+2lt>)-конкурентным для минимизации lp-норм продолжительности потока. Для минимизации lp-нормы растяжимости SETF является (1 + <math>\epsilon</math>)-скоростным, O(l/e3+1/? - log1+1/p P)-конкурентным. | ||
