Анализ Sorted-Balance алгоритма

Все задания сортируются в порядке убывания времени выполнения. Первые M заданий распределяются последовательно на разные машины.

Возьмем только первые M+1 заданий. Все они имеют время выполнения не менее . Так как заданий больше M, то будет хоть одна машина, на которую будет назначено минимум два задания и время работы которой будет не меньше .

Оптимальная возможная нижняя граница периода обработки при будет иметь вид.

(8)

Рассмотрим машину  с максимальной нагрузкой. Если на неё назначено только 1 задание, то балансировка оптимальна. Если же заданий минимум два, то  является последним назначенным заданием ().

(9)

Нагрузка машины  перед назначением ей последней задачи равна , что меньше . Получается аналогичная формула (5).

Объединим выражения (5) и (9).

(10)

Таким образом, период обработки Sorted-Balance алгоритма:

(11)

Сравнение алгоритмов

Алгоритм Greedy-Balance строит решение с периодом обработки . Пример, когда период обработки будет почти в два раза больше оптимального решения, изображён на Рис. 1.10: алгоритм последовательно распределяет задания с временем выполнения равным 1. Задание с временем выполнения 3 находится в очереди последним и назначается на машину . Период обработки будет равен 5.

Рис. 1.10. Пример с периодом обработки, превышающий оптимальный почти в два раза.

Оптимальным решением станет назначение этой задачи на отдельную машину. Sorted-Balance строит решение с периодом обработки  и выполнит балансировку с периодом обработки равным 3.

Но не всегда данный алгоритм оказывается наиболее эффективным. В ситуациях, когда заданий меньше количества машин, или, когда задания имеют одинаковое время выполнения, оба алгоритма выполнят балансировку с одним периодом обработки, но алгоритм с сортировкой будет работать дольше. Временная сложность Greedy-Balance составляет O (Log(M) · N), а Sorted-Balance выполняет балансировку за O ( + Log(M) · N).

Таким образом, когда разброс между временем выполнения заданий значительный, алгоритм Sorted-Balance работает эффективнее, и полученный период обработки будет минимальный. Но данный алгоритм имеет большую временную сложность и при прочих условиях Greedy-Balance выдаст близкий период обработки за меньшее время.

Выводы по главе

Для выполнения большого количества задач за минимальный промежуток времени используются множество серверов. Процессом распределения задач между серверами с целью повышения общей производительности системы и оптимизацией использования ресурсов, называется балансировка нагрузки. В процессе распределения на программном уровне могут использоваться различные алгоритмы, одними из которых являются Greedy-Balance и Sorted-Balance. Эти алгоритмы называются жадными, так как на каждом шаге работы они делают наилучший выбор с целью получить оптимальный результат. Greedy-Balance последовательно берёт задачи из неупорядоченного множества и назначает каждую из них их на машину с минимальной текущей нагрузкой. В Sorted-Balance множество задач упорядочивается по убыванию их времени выполнения, после чего задачи последовательно распределяются, назначая каждую на машину с минимальной текущей нагрузкой. Временная сложность Greedy-Balance меньше, чем у Sorted-Balance, так как у модификации жадного алгоритма требуется время на сортировку множества задач. Но период обработки Greedy-Balance в некоторых ситуациях будет значительно больше, чем у Sorted-Balance. Следовательно, в ситуациях большого разброса времени выполнения сортировочная балансировка окажется эффективнее, но будет работать за больший промежуток времени. При прочих обстоятельствах жадная балансировка выполнится быстрее и получит близкий к Sorted-Balance результат.

 

 

Глава 2

2.1 Анализ требований

Требуется в автоматическом порядке выполнять балансировку, используя приведённые ранее алгоритмы. Программа тестирования представляет собой консольное приложение. Данные для балансировки необходимо считывать из указанного пользователем файла. Кроме того, должно вычисляться время прохождения одного теста для каждого алгоритма, которое записывается в выходные данные. Помимо этого, в выходные данные также записываются периоды обработки для всех балансировок. Все алгоритмы должны быть легко интегрируемы в различные системы и обладать заявленной ранее эффективностью.