Рассмотрим три алгоритма динамического переноса нагрузки, предложенные разработчиками SPEEDES:
- случайный алгоритм (random, R);
- алгоритм, основанный на коммуникациях (communication, С);
- алгоритм, основанный на вычислении нагрузки (load, L).
Будем в дальнейшем называть эти алгоритмы балансировки RCL-стратегией.
Алгоритм переноса объекта или процесса с одного компьютера достаточно сложен. Введение некоторых разумных допущений только незначительно снижает сложность этого алгоритма. Итак, сделаны следующие допущения:
- Распределённая система является гетерогенной.
- Пользователь может интерактивно взаимодействовать с машиной в любой момент времени.
- Количество вычислительных узлов в сети ограничено.
- Возможно изменение сети.
- Задержки на коммуникацию в сети остаются неизменными.
- Издержки на перенос нагрузки с одного на другой процессор соизмерим с физическими размерами этой нагрузки.
RCL стратегия использует двухуровневый процесс принятия решений, который объединяет централизованный и децентрализованный подходы. Двухуровневый процесс принятия решений предполагает:
- Центральный процесс-координатор принимает решение о переносе нагрузки,
- Каждый отсылающий сообщения процесс ответственен за выбор нагрузки, которую следует перенести.
На первом уровне выбирается центральный координатор для того, чтобы среди всех рабочих станций именно он мог принимать решения. Во время процесса переноса нагрузки все рабочие станции приостанавливают свою работу на некоторый промежуток времени, пока центральный координатор собирает информацию о загрузке процессоров. Координатор анализирует информацию, которая включает сведения о загрузке компьютеров и о распределении нагрузки в системе. Координатор, на основании этой информации решает, следует ли предпринимать действия по переносу нагрузки с одного компьютера на другой. Если состояние системы таково, что перенос нагрузки необходим (состояние соответствует критерию переноса нагрузки), центральный координатор начинает процедуру перераспределения нагрузки, руководствуясь скоростью работы компьютеров.
Если в переносе нагрузки нет необходимости, компьютер должен разослать сообщение об этом всем другим компьютерам. В этом случае действия второго уровня игнорируются, и каждый компьютер продолжает обрабатывать свои локальные события. Если, находясь на втором уровне, посылающие данные рабочие станции получат от центрального координатора сигнал о необходимости миграции нагрузки, они начинают процесс выбора части нагрузки для переноса её на другой хост. При выборе используют RCL стратегию. После того, как части нагрузки выбраны на всех пересылающих данные рабочих станциях, начинается процесс миграции. Последовательность шагов, предпринимаемых при миграции нагрузки между двумя компьютерами, включает упаковку данных и их отправку с посылающего компьютера, и приём и распаковку на принимающем компьютере. В конце каждого шага миграции принимающий компьютер рассылает всем остальным сообщение о завершении процедуры миграции и о новом размещении данных. После этого каждый компьютер продолжает обработку. Рассмотрим более детально действия на каждом уровне.