Балансировка нагрузки: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 36: | Строка 36: | ||
'''Ограниченное назначение''' | '''Ограниченное назначение''' | ||
Что касается ограниченных назначений, то временные задачи делают эту модель гораздо более сложной, чем постоянные. Коэффициент конкурентоспособности O (log m), достигаемый простым жадным алгоритмом | Что касается ограниченных назначений, то временные задачи делают эту модель гораздо более сложной, чем постоянные. Коэффициент конкурентоспособности O(log m), достигаемый простым жадным алгоритмом [8], в данном случае сохранить не удается. Для этого алгоритма он составляет <math>\Omega(m^{\frac{2}{3}})</math> [4]. Более того, в той же работе было показано, что нижняя граница коэффициента конкурентоспособности любого алгоритма равна <math>\Omega (\sqrt{m})</math>. При этом его построение было весьма сложным; впрочем, Ма и Плоткин [16] предложили упрощенное построение, дающее тот же результат. | ||
При построении в работе [16] выбирается значение p, которое представляет собой наибольшее целое число, удовлетворяющее соотношению <math>p + p^2 \le m</math>. Очевидно, что <math>p = \Theta (\sqrt{m})</math>. Для расчета нижней границыиспользуются два набора машин – <math>p</math> машин, которые называются «малой группой», и <math>p^2</math> машин, называемые «большой группой». Построение состоит из <math>p^2</math> фаз, каждая из которых состоит из <math>p</math> заданий и предназначена для одной машины в большой группе. На фазе i задание k этой фазы может выполняться либо на k-й машине малой группы, либо на i-й машине большой группы. После этого поступления только одно из этих <math>p</math> заданий не убывает. Оптимальный оффлайновый алгоритм на каждой фазе назначает все задания малой группы, за исключением одного задания, которое не убывает. Таким образом, после завершения построения на каждую машину большой группы приходится по одной задаче. Максимальная нагрузка, когда-либо достигаемая OPT, равна 1. Однако алгоритм не знает на каждой фазе, какое из имеющихся заданий не уйдет. Если на фазе i малой группе не назначено ни одного задания, то нагрузка на машину i полагается равной <math>p</math>. В противном случае задание, которое алгоритм назначает малой группе, выбирается как задание, которое не убывает вместе с остальными. Таким образом, после <math>p</math> фаз на малой группе накапливается совокупная нагрузка <math>p^2</math>, что означает, что по крайней мере одна машина в ней имеет нагрузку <math>p</math>. На этом конструирование завершается. | |||
Альтернативный алгоритм под названием ROBIN HOOD был предложен в работе [7]. Этот алгоритм сохраняет нижнюю границу на OPT, которая представляет собой максимум из двух следующих функций. Первой из них является максимальная средняя загрузка машины за прошедшее время работы алгоритма. Второй – максимальный размер работы среди всех, поступивших за это время. Обозначим эту нижнюю границу на время t (после того, как произошли t событий) за | |||
Альтернативный алгоритм под названием ROBIN HOOD был предложен в работе [7]. Этот алгоритм сохраняет нижнюю границу на OPT, которая представляет собой максимум из двух следующих функций. Первой из них является максимальная средняя загрузка машины за прошедшее время работы алгоритма. Второй – максимальный размер работы среди всех, поступивших за это время. Обозначим эту нижнюю границу на время t (после того, как произошли t событий) за <math>B^t</math>. Машина i называется «богатой» в момент времени t, если <math>L^t_i \ge \sqrt{m B^t}</math>. В противном случае она называется «бедной». Временем «удачи» богатой машины i является такой момент времени t, что в момент времени t' - 1 она еще является бедной, а в моменты t', ..., t, – уже богатой; т. е. именно в этот момент машина i перешла в разряд богатых. Очевидно, что машины могут стать бедными из-за обновления <math>B^t</math> или убытия заданий. Стать богатой машина может в результате поступления заданий, назначенных ей. | |||
Алгоритм назначает задание j бедной машине в M(j), если такая машина существует. В противном случае j присваивается машине в M(j) с самым последним временем «удачи». Анализ использует тот факт, что одновременно богатыми могут быть не более | Алгоритм назначает задание j бедной машине в M(j), если такая машина существует. В противном случае j присваивается машине в M(j) с самым последним временем «удачи». Анализ использует тот факт, что одновременно богатыми могут быть не более <math>\sqrt{m}</math> машин. | ||
Заметим, что для малых значений m (m | Заметим, что для малых значений m <math>(m \le 5)</math> коэффициент конкурентоспособности жадного алгоритма все еще является наилучшим, как было показано в [1]. В данной работе было показано, что для эта граница равна (m + 3)/2 для m = 3, 4, 5. Нетрудно заметить, что для m = 2 лучшая граница равна 2. | ||
'''Несвязанные машины''' | '''Несвязанные машины''' | ||
Самая большая разница возникает в случае несвязанных машин. В отличие от случая постоянных задач, в котором может быть достигнута верхняя граница O(log m) [ ], в [ ] было показано, что любой алгоритм имеет коэффициент конкурентоспособности | Самая большая разница возникает в случае несвязанных машин. В отличие от случая постоянных задач, в котором может быть достигнута верхняя граница O(log m) [3], в [2] было показано, что любой алгоритм имеет коэффициент конкурентоспособности <math>\Omega(m / log \; m)</math>. Отметим, что у тривиального алгоритма, который назначает каждое задание машине, имеющей имеет минимальную нагрузку, коэффициент конкурентоспособности не превышает m [3]. | ||
= Применение == | = Применение == | ||