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

В оффлайновом случае <math>\rho_A \;</math> является ''коэффициентом аппроксимации'' алгоритма. В онлайновом случае будем называть <math>\rho_A \;</math> ''коэффициентом конкурентоспособности'' A.

Если ''вытеснение'' разрешено, обработка задания может быть прервана и возобновлена после завершения других заданий в промежутке. Как будет показано далее, вытеснение необходимо для разработки эффективных алгоритмов на базе рассматриваемой структуры [5, 6].

Рассмотрим любое задание j данного экземпляра и время t в плане A и обозначим за <math>w_j(t) \;</math> количество времени, проведенного A над выполнением задания j до наступления момента t. Обозначим за <math>x_j(t) = p_j - w_j(t) \;</math> его ''оставшееся время обработки'' в момент t.

Наилучшей известной эвристикой для минимизации средней продолжительности потока при разрешенном вытеснении является эвристика ''«наименьшее оставшееся время обработки»'' (shortest remaining processing time, SRPT). В любое время t эвристика SRPT выполняет «повисшее» задание j, для которого <math>x_j(t) \;</math> минимально. Если вытеснение не разрешено, эта эвристика превращается в эвристику ''«сначала самое короткое задание»'' (shortest job first, SJF): в начале выполнения плана или при завершении задания алгоритм выбирает «повисшее» задание с наименьшим временем обработки и выполняет его до завершения.

Рассматриваемая задача является полиномиально разрешимой на единичном компьютере с разрешенным вытеснением [9, 10]. Если вытеснение допускается, то оптимальным для одного компьютера является подход SRPT. На параллельных компьютерах наилучшая известная верхняя граница для случая с вытеснением достигается алгоритмом SRPT, который является O(log min n/m, P)-аппроксимируемым [6], где P – отношение между самым большим и самым малым временем обработки для данного экземпляра. Заметим, что алгоритм SRPT является онлайновым, так что предыдущий результат выполняется также и для онлайнового случая. Кроме того, в [6] было доказано, что в онлайновом случае эта нижняя граница является строгой. Для оффлайнового случая с разрешенным вытеснением не найдено неконстантной нижней границы.

В случае с отсутствием вытеснения ни один оффлайновый алгоритм не способен улучшить <math>\Omega (n^{1/3 - \epsilon})</math>-аппроксимацию, для любого <math>\epsilon > 0 \;</math>, а наилучшая верхняя граница составляет <math>O(\sqrt{n/m} \; log(n/m))</math> [6]. В случае с единственным компьютером верхняя и нижняя границы приобретают вид <math>O(\sqrt{n})</math> и <math>\Omega (n^{1/2 - \epsilon})</math>, соответственно [5].

Для вышеописанных сценариев было предложено немало расширений, в частности, для онлайнового случая с разрешенным вытеснением. Большинство предположений касались мощности алгоритма или знания экземпляра входных данных. В первом случае представляет интерес вариант, в котором алгоритм выполняется на более быстрых компьютерах, нежели его оптимальный аналог. Этот аспект обсуждался в работе [4]. Ее авторы доказали, что даже небольшое повышение скорости приводит к тому, что эффективность некоторых простых эвристик будет приближена к оптимальной.

Что до знания алгоритмом экземпляра входных данных, любопытным вариантом онлайновой конфигурации, встречающимся во многих современных практических приложениях, является вышеупомянутый подход с отсутствием предвидения. Этот аспект рассматривался в работах [1, 3]. В частности, авторы [1] доказали, что рандомизированный вариант эвристики MLF, описанной выше, позволяет получить коэффициент конкурентоспособности, который в среднем отличается от оптимума не более чем на полилогарифмический коэффициент.

Первой и основной сферой приложения политик планирования является распределение ресурсов по процессам в многозадачных операционных системах [11]. В частности, использование эвристик, подобных «сначала самое короткое задание», а именно эвристики MLF, документировано в таких широко распространенных ОС, как UNIX и WINDOWS NT [8, 11]. Впоследствии рассматривалось их применение в других областях – таких как доступ к веб-ресурсам [2].