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

Эвристики «сначала самое короткое задание» возникают в задачах упорядочения, целью которых является минимизация воспринимаемой задержки для пользователей в многопользовательской или многозадачной системе. В этой задаче алгоритм должен спланировать множество заданий для пула из m идентичных компьютеров. Для каждого задания известны срок запуска и продолжительность обработки. Цель заключается в минимизации среднего времени, потраченного на выполнение задания системой. Это обычно считается подходящей метрикой для оценки качества услуги, предоставляемой системой интерактивным пользователям. Формальное определение задачи оптимизации выглядит следующим образом.

Множество m идентичных компьютеров и множество n заданий 1, 2, ..., n. Каждому заданию j присвоены срок запуска <math>r_j \;</math> и продолжительность обработки <math>p_j \;</math>. Обозначим за <math>\mathcal{I}</math> множество допустимых экземпляров входных данных.

Можно также сделать предположения о знании алгоритмом продолжительности обработки каждого задания. В частности, стоит иметь в виду важный случай, часто встречающийся в практических приложениях, в котором <math>p_j \;</math> полностью неизвестно онлайновому алгоритму до того момента, как выполнение задания будет полностью завершено (''отсутствие предвидения'') [1, 3].

В оффлайновом случае <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].

Алгоритмы на основе эвристик типа «сначала самое короткое задание» в недавнем прошлом активно исследовались. Однако некоторые вопросы остаются нерешенными. В частности, для оффлайнового случая с параллельными компьютерами до сих пор не найдено неконстантной нижней границы аппроксимации. А для онлайнового случая с параллельными компьютерами не известно строгой нижней границы при отсутствии предвидения. Актуальная нижняя граница <math>\Omega(log \; n)</math> была получена для конфигурации с одним компьютером [7], и есть причины предполагать, что она оказывается на логарифмический коэффициент ниже границы для параллельного случая.