4652
правки
Планирование с учетом наименьшего прошедшего времени обработки: различия между версиями
Перейти к навигации
Перейти к поиску
м
Планирование с учетом наименьшего прошедшего времени обработки (посмотреть исходный код)
Версия от 17:20, 23 февраля 2022
, 23 февраля 2022→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 46: | Строка 46: | ||
Теорема 4 [2]. В постановке задачи без предвидения алгоритм 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>\ell_p</math>-норм продолжительности потока. В частности, для e < 1/2p алгоритм RR является <math>(1 + \epsilon)</math>-скоростным, ^(п^-^РЩ-конкурентным. Для <math>\ell_p</math>-норм растяжимости RR является Q(n)-конкурентным, как и фактически любой рандомизированный алгоритм без предвидения.''' | ||