1294
правки
Балансировка нагрузки: различия между версиями
Материал из WEGA
→Открытые вопросы
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 42: | Строка 42: | ||
Альтернативный алгоритм под названием 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> или убытия заданий. Стать богатой машина может в результате поступления заданий, назначенных ей. | Альтернативный алгоритм под названием 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', что в момент времени t' - 1 она еще является бедной, а в моменты t', ..., t, – уже богатой; т. е. именно в этот момент машина i перешла в разряд богатых. Очевидно, что машины могут стать бедными из-за обновления <math>B^t</math> или убытия заданий. Стать богатой машина может в результате поступления заданий, назначенных ей. | ||
| Строка 48: | Строка 48: | ||
Заметим, что для малых значений m <math>(m \le 5)</math> коэффициент конкурентоспособности жадного алгоритма все еще является наилучшим, как было показано в [1]. В данной работе было показано, что | Заметим, что для малых значений m <math>(m \le 5)</math> коэффициент конкурентоспособности жадного алгоритма все еще является наилучшим, как было показано в [1]. В данной работе было показано, что эта граница равна (m + 3)/2 для m = 3, 4, 5. Нетрудно заметить, что для m = 2 лучшая граница равна 2. | ||
'''Несвязанные машины''' | '''Несвязанные машины''' | ||
Самая большая разница возникает в случае несвязанных машин. В отличие от случая постоянных задач, в котором может быть достигнута верхняя граница O(log m) [3], в [2] было показано, что любой алгоритм имеет коэффициент конкурентоспособности <math>\Omega(m / log \; m)</math>. Отметим, что у тривиального алгоритма, который назначает каждое задание машине, имеющей | Самая большая разница возникает в случае несвязанных машин. В отличие от случая постоянных задач, в котором может быть достигнута верхняя граница O(log m) [3], в [2] было показано, что любой алгоритм имеет коэффициент конкурентоспособности <math>\Omega(m / log \; m)</math>. Отметим, что у тривиального алгоритма, который назначает каждое задание машине, имеющей минимальную нагрузку, коэффициент конкурентоспособности не превышает m [3]. | ||
== Применение == | == Применение == | ||
| Строка 59: | Строка 59: | ||
В [10] исследовалась иерархическая модель. Это специальный случай ограниченного задания, в котором для каждого задания j M(j) является префиксом машин. | В [10] исследовалась иерархическая модель. Это специальный случай ограниченного задания, в котором для каждого задания j элемент M(j) является префиксом машин. Было показано, что даже для временных заданий для этой модели существует алгоритм с константным коэффициентом конкурентоспособности. | ||
В работе [6], в которой изучалось приращение ресурсов при балансировке нагрузки, рассматривались также и временные задачи. Приращение ресурсов представляет собой вид анализа, при котором онлайновый алгоритм сравнивается с оптимальным оффлайновым алгоритмом, имеющим меньшее количество машин. | В работе [6], в которой изучалось приращение ресурсов при балансировке нагрузки, рассматривались также и временные задачи. Приращение ресурсов представляет собой вид анализа, при котором онлайновый алгоритм сравнивается с оптимальным оффлайновым алгоритмом, имеющим меньшее количество машин. | ||
= Открытые вопросы = | == Открытые вопросы == | ||
По-прежнему остаются небольшие пробелы как для равномерно связанных, так и для несвязанных машин. Для несвязанных машин может быть любопытно выяснить, существует ли алгоритм с коэффициентом конкурентоспособности o(m), а также имеет ли простой алгоритм, описанный выше, оптимальный коэффициент конкурентоспособности (с поправкой на мультипликативный множитель). | По-прежнему остаются небольшие пробелы как для равномерно связанных, так и для несвязанных машин. Для несвязанных машин может быть любопытно выяснить, существует ли алгоритм с коэффициентом конкурентоспособности o(m), а также имеет ли простой алгоритм, описанный выше, оптимальный коэффициент конкурентоспособности (с поправкой на мультипликативный множитель). | ||
| Строка 102: | Строка 102: | ||
16. Ma, Y., Plotkin, S.: Improved lower bounds for load balancing of tasks with unknown duration. Inf. Process. Lett. 62, 31-34 (1997) | 16. Ma, Y., Plotkin, S.: Improved lower bounds for load balancing of tasks with unknown duration. Inf. Process. Lett. 62, 31-34 (1997) | ||
[[Категория: Совместное определение связанных терминов]] | |||
