Распределенный эвристический алгоритм, инициируемый отправителем

Теперь рассмотрим некоторые распределенные алгоритмы. Один из них гласит, что при создании процесс запускается на узле, который его создал, если тот не перегружен. Перегрузка может оцениваться по числу процессов, их суммарной нагрузке на процессор или какому-нибудь другому параметру.
Если узел перегружен, он произвольным образом выбирает другой узел и запрашивает у него данные о его загрузке (используя ту же систему оценки). Если загрузка проверяемого узла оказывается ниже определенного порогового значения, новый процесс отправляется на этот узел (Eager et al.,
1986). Если проверяемый узел не отвечает этому требованию, для проверки выбирается другая машина. Проверка не ведется до бесконечности. Если за N проверок найти подходящий узел не удается, алгоритм завершает свою работу и процесс запускается на породившей его машине. Замысел заключается в том, чтобы сильно загруженные узлы пытались избавиться от чрезмерной работы, как показано на рис. 8.25, а, где изображено выравнивание нагрузки, инициированное отправителем.

Рис. 8.25. а — перегруженный узел ищет недогруженный узел, которому можно было бы передать процесс; б — незагруженный узел ищет, чем бы заняться


Для данного алгоритма была создана аналитическая модель очередей (Eager et al., 1986). При использовании этой модели было установлено, что алгоритм неплохо себя ведет и работает стабильно в широком диапазоне параметров, включая различные пороговые значения, затраты на перенос данных и ограничения по количеству проб.

Тем не менее следует заметить, что в условиях большой загруженности все машины будут постоянно отправлять тестовые сообщения другим машинам, тщетно пытаясь найти машину, желающую получить дополнительную работу. При этом машины избавятся лишь от весьма незначительного количества процессов, но попытки избавления приведут к значительным издержкам.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Распределенный эвристический алгоритм, инициируемый отправителем:

  1. 4. Ответственность отправителя и получателя груза.
  2. 4. Содержательная эвристическая оценка произведения.
  3. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  7. § 5. Особенности обязательств по производству эвристических работ (на примере научно-исследовательских, опытно-конструкторских и технологических работ — НИР и ОКТР) (п. 2137-2143)
  8. Алгоритм исцеления:
  9. ДИАПАЗОН РАСПРЕДЕЛЕНИЯ
  10. Алгоритм избавления от боли
  11. 4.2. Анализ одномерных распределений
  12. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  13. Алгоритм обработки результатов.
  14. 2. Специфика и алгоритмы работы с источниками.