Минимальная продолжительность потока: различия между версиями

Они также дали подходящую нижнюю границу коэффициента конкурентоспособности (с точностью до постоянных коэффициентов).

Заметим, что минимизация средней продолжительности потока эквивалентна минимизации общей его продолжительности. Предположим, что каждое задание выплачивает 1 доллар за каждую единицу времени, когда оно живо (т. е. не завершено), тогда сумма полученных платежей равна общей продолжительности потока. Суммируя оплату за каждый временной шаг, общую продолжительность потока можно выразить как сумму по количеству незавершенных заданий в каждую единицу времени. Поскольку SRPT работает с заданиями, которые могут быть завершены как можно скорее, интуитивно кажется, что в любой момент времени он должен наименьшее количество незавершенных заданий. Для одной машины это верно, однако для нескольких машин это не так (что показано в примере ниже). Основная идея работы [8] заключалась в том, чтобы показать, что в любой момент времени количество незавершенных работ в рамках SRPT «по сути» не более чем в O(min(log P)) раз больше, чем при любом другом алгоритме. Для этого авторы разработали технику группировки заданий в логарифмическое число классов в соответствии с их оставшимися размерами и рассуждений о суммарном объеме незавершенной работы в этих классах. С тех пор эта техника нашла широкое применение для получения других результатов. Чтобы получить гарантию, выраженную относительно n, требуются некоторые дополнительные идеи.

Приведенный ниже пример показывает, как SRPT может отклоняться от оптимума при наличии нескольких машин. Этот пример также является ключевым компонентом в построении нижней границы в Теореме 2. Предположим, у нас имеются две машины, и три задания размером 1, 1 и 2 поступают в момент времени t = 0. SRPT запланирует два задания размером 1 на момент времени t = 0, а затем будет работать над заданием размером 2 в момент времени t = 1. Таким образом, в момент t = 2 у него остается одна единица незавершенной работы. Однако оптимальный вариант может запланировать работу размера 2 на момент времени 0 и завершить все эти работы к моменту времени 2. Затем, в момент времени t = 2, поступают еще три задания с размерами 1/2, 1/2 и 1. Опять же, SRPT сначала будет работать над заданиями размера 1/2, и можно увидеть, что у него будет два незавершенных задания с оставшимся объемом работы 1/2 у каждого в момент t = 3, в то время как оптимальный алгоритм может закончить все эти задания к моменту 3. Эта схема продолжается, давая три задания размером 1/4, 1/4 и 1/2 при t = 3 и так далее. После k шагов у SRPT останется k заданий с размерами <math>1/2, 1/4, 1/8, ... , 1/2^{k - 2}, 1/2^{k - 1}; 1/2^{k - 1}</math>, тогда как у оптимального алгоритма не останется ни одного задания. Теперь соперник может давать 2 задания размером <math>1/2^k</math> каждые <math>1/2^k</math> единиц времени в течение длительного времени, что означает, что SRPT может быть в <math>\Omega(log \; P)</math> раз хуже оптимального.