Жадные методы решения задачи распределения нагрузки

Жадные методы решения задачи распределения нагрузки

 

 

Курсовой проект по дисциплине
«Проектная и научно-исследовательская деятельность»

 

 

Выполнил студент группы ФИб-2301-51-00                              / К.О. Дёмин /

Руководитель к.т.н., д-р пед. н., профессор                                 / С.М. Окулов /

 

Работа защищена с оценкой                                                          ____.____.201_ г.

 

Члены комиссии:                                                                            /                      /

                                                                                                          /                      /

 

Киров 2017

Оглавление

Введение. 3

Глава 1. 5

1.1 Основные понятия. 5

1.2 Методы и алгоритмы балансировки нагрузки. 6

1.3 Постановка задачи. 8

1.4 Описание алгоритмов. 8

1.4.1 Greedy-Balance. 8

1.4.2 Sorted-Balance. 11

1.5 Анализ алгоритмов. 15

1.5.1 Анализ Greedy-Balance алгоритма. 15

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

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

1.6 Выводы по главе. 18

Глава 2. 20

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

2.2 Выбор языка программирования и среды разработки. 20

2.3 Программная реализация. 20

2.3.1 Входные и выходные данные. 20

2.3.2 Структура программы.. 22

2.3.3 Интерфейс программы.. 25

2.3.4 Тестирование программы.. 26

2.4 Экспериментальное исследование алгоритмов. 27

2.4.1 Исследование времени работы.. 27

2.4.2 Сравнение эффективности алгоритмов. 29

2.5 Выводы по главе. 30

Заключение. 31

Библиографический список. 32

Приложения. 33

Приложение 1. 33

Приложение 2. 38

 

Введение

С развитием науки и компьютерных технологий требования к вычислительной мощности возросли. Значительное влияние на темпы роста потребления ресурсов оказало развитие интернета. По состоянию на 30 июня 2017 года, количество пользователей интернета превысило отметку в 3,8 миллиарда человек[1]. Так, через социальную сеть «ВКонтакте» проходит 5 миллиардов сообщений в сутки[2], а время выполнения запросов варьируется от 30 до 50 миллисекунд[3]. Для выполнения поставленных задач используются сервера – мощные вычислительные машины. Каждый такой сервер направлен на выполнение определенного рода задач, например, работа с фотографиями, передача аудиозаписей, транслирование видео, проведение вычислений, обработка веб-страниц и так далее. Сервера располагаются в центрах обработки данных (дата-центрах). Помимо серверов, внутри дата-центров находится балансировщик нагрузки, на который поступают все входящие запросы [5]. Его задачей является распределение поставленных задач так, чтобы выровнять нагрузку между серверами в зависимости от загруженности каждого из них.

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

Цель курсового проекта – исследование применения жадных алгоритмов при распределении нагрузки между серверами.

Задачи курсового проекта:

1. Обзор литературы по балансировке нагрузки.

2. Обзор методов и алгоритмов балансировки нагрузки.

3. Анализ жадных алгоритмов для решения задачи распределения нагрузки.

4. Разработка тестирующего программного обеспечения с использованием жадных алгоритмов.

5. Проведение экспериментального исследования алгоритмов, подведение итогов.

 

 

Глава 1

Основные понятия

Жадный алгоритм (Greedy algorithm) – это алгоритм, который на каждом шаге выполнения делает наилучший выбор с целью получить в конце наиболее оптимальное решение [4].

Оптимальное решение – это решение, которое максимально удовлетворяет поставленной задаче.

Вычислительная машина – специализированный компьютер, направленный на выполнение определенных задач.

Период обработки – максимальная нагрузка на машину из множества машин.

Балансировка нагрузки ­– процесс распределения запросов (заданий) между устройствами с целью оптимизировать использование ресурсов, а также повысить общую производительность и отказоустойчивость системы.

Пример работы балансировки нагрузки представлен на Рис. 1.1 и Рис. 1.2: задания поступают на балансировщик нагрузки, который распределяет их между серверами так, чтобы каждый из них был равномерно нагружен.

Рис. 1.1. Пример состояния перед началом балансировки нагрузки между серверами.

 

Рис. 1.2. Пример балансировки нагрузки между серверами.

Постановка задачи

Введём следующие обозначения.

– множество из M машин (серверов);

 – множество из N задач (запросов);

Каждая задача  имеет время выполнения ;

 – множество заданий, назначенных на машину  из множества n;

– общее время работы (нагрузка) машины m_i.

(1)

Необходимо выполнить балансировку так, чтобы нагрузка между всеми машинами была максимально сбалансированной.

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

Описание алгоритмов

Greedy-Balance

Greedy-Balance алгоритм – это простой жадный алгоритм, который в любом порядке перебирает поставленные задачи и назначает каждую из них на машину с минимальной текущей нагрузкой [3].

Пусть даны непустые множества m и n, и пустое множество заданий A. В множестве n элементы располагаются в любом порядке. Из множества задач берётся элемент  и добавляется в множество , где i – это элемент множества m с минимальным на текущий момент . Так продолжается до тех пор, пока множество n не станет пустым.

На Рис. 1.3 приведён псевдокод алгоритма.

1	void GreedyBalance(queue <task> n, machine m[], queue <task> A []) // n - множество задач, m - множество машин, A - множество задач машин
2	{
3	int min;
4	while(!n.empty())
5	{
6	min = find_min(m); // ищем номер машины с минимальной нагрузкой
7	task temp = n.front(); // берём элемент из множества
8	n.pop(); // убираем задачу из множества
9	m[min].T += temp.T; // прибавляем машине время обработки задачи
10	A[min].push(temp); // добавляем задание во множество задач машины min
11	}
12	}
Рис. 1.3. Псевдокод Greedy-Balance алгоритма.

Временная сложность алгоритма O (M·N), где M – количество машин, а N – количество задач. При этом, используя очередь с приоритетом, временная сложность алгоритма составит O (log (M) · N). На Рис 1.4 приведён псевдокод алгоритма с использованием очереди с приоритетом.

 

1	void GreedyBalanceModified(queue <task> n, priority_queue<machine> m) // n - множество задач, m - множество машин
2	{
3	machine min;
4	while(!n.empty())
5	{
6	min = m.top(); // берём машину с минимальной нагрузкой
7	m.pop(); // удаляем машину из очереди с приоритетом
8	task temp = n.front(); // берём элемент из множества задач
9	n.pop(); // убираем задачу из множества
10	min.T += temp.T; // прибавляем машине время обработки задачи
11	m in.A.push(temp); // добавляем задание во множество задач машины min
12	m.push(min);
13	}
14	}
Рис. 1.4. Псевдокод Greedy-Balance алгоритма с применением очереди с приоритетом.

Наглядный пример последовательной работы алгоритма представлен на Рис. 1.5: стрелочки указывают на машину, которой будет назначена текущая задача; каждая задача имеет время выполнения; задачи последовательно назначаются на машину с минимальным временем выполнения на данный момент времени. Период обработки равен 7.

 

Рис. 1.5. Пример работы Greedy-Balance алгоритма.

Sorted-Balance

Sorted-Balance алгоритм – это разновидность жадного алгоритма, которая в порядке убывания времени выполнения задачи распределяет их на машины с минимальной текущей нагрузкой [3].

Даны непустые множества m и n, и пустое множество заданий A. В начале работы алгоритма все задачи множества n сортируются в порядке убывания по времени выполнения . Затем последовательно из множества задач берётся элемент  и добавляется в множество , где i – это номер машины с минимальной нагрузкой. Действия повторяются пока множество n не станет пустым. На Рис. 1.6 приведён псевдокод алгоритма.

1	void SortedBalance(queue <task> n, machine m[], queue <task> A []) // n - множество задач, m - множество машин, A - множество задач машин
2	{
3	int min;
4	Sort(n); // сортируем множество задач по убыванию времени
5	while(!n.empty())
6	{
7	min = find_min(m); // ищем номер машины с минимальной нагрузкой
8	task temp = n.front(); // берём элемент из множества
9	n.pop(); // убираем задачу из множества
10	m[min].T += temp.T; // прибавляем машине время обработки задачи
11	A[min].push(temp); // добавляем задание во множество задач машины min
12	}
13	}
Рис. 1.6. Псевдокод Sorted-Balance алгоритма.

Временная сложность алгоритма O ( + M·N), где  – время выполнения сортировки множества N в порядке убывания времени выполнения. Как и в предыдущем алгоритме, при использовании очереди с приоритетом временная сложность алгоритма составит O ( + log (M)·N). Псевдокод с использованием очереди с приоритетом представлен на Рис. 1.7.

 

 

1	void SortedBalanceModified(queue <task> n, priority_queue<machine> m) // n - множество задач, m - множество машин
2	{
3	machine min;
4	sort(n); // функция сортировки очереди заданий в порядке убывания времени выполнения
5	while(!n.empty())
6	{
7	min = m.top(); // берём машину с минимальной нагрузкой
8	m.pop(); // удаляем машину из очереди с приоритетом
9	task temp = n.front(); // берём элемент из множества задач
10	n.pop(); // убираем задачу из множества
11	min.T += temp.T; // прибавляем машине время обработки задачи
12	m in.A.push(temp); // добавляем задание во множество задач машины min
13	m.push(min);
14	}
15	}
Рис. 1.7. Псевдокод Sorted-Balance алгоритма с применением очереди с приоритетом.

Пример работы алгоритма представлен на Рис. 1.8: в начале работы алгоритма элементы множества n сортируются в порядке убывания, после чего происходит распределение задач между машинами; стрелочки указывают машину назначения. Период обработки равен 6.

Рис. 1.8. Пример работы алгоритма

Анализ алгоритмов

Введём следующие обозначения.

 – период обработки текущей балансировки.

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

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

Алгоритм 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 Анализ требований

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

Программная реализация

Входные и выходные данные

В первой строке входного файла содержится следующая информация: K – количество тестов, M – число машин и N – число задач в одном тесте. В последующих K строках содержится информация для каждого теста. В них содержится N чисел, которые являются временем выполнения задачи. На Рис. 2.1 изображен пример входного файла. В первой строке указано: 8 тестов, 5 машин и 10 задач в одном тесте. В последующих 8 строках находится по 10 чисел, которые являются временем выполнения задачи. Эти 10 чисел будут распределены между 5 машинами.

Рис. 2.1. Пример входного файла.

Во время выполнения тестирования результаты работы записываются в текстовый файл. В файле содержится: период обработки после балансировки каждым алгоритмом, время выполнения одного теста для каждого алгоритма и суммарное время выполнения всех тестов у каждого алгоритма. Пример выходного файла изображён на Рис. 2.2: количество строк (кроме последней) соответствует количеству тестов. В последней строке написано общее время работы каждого алгоритма. В первом столбце записаны периоды обработки после работы GreedyBalance алгоритма, во втором столбце записано время выполнения балансировки GreedyBalance. В последующих столбцах находится аналогичная информация для SortedBalance, GreedyBalanceModified и SortedBalanceModified алгоритмов. Так, в первом тесте GreedyBalance алгоритмы выполнили балансировку с периодом обработки равному 73, а SortedBalance алгоритмы выполнили балансировку с периодом обработки 49. Стоит отметить, что столбцы 1–5 и 3–7 одинаковые, поскольку они используют одинаковые алгоритмы, но с разной реализацией и разными структурами данных.

 

Рис. 2.2. Пример выходного файла

Структура программы

Программы разделена на 3 модуля:

1) AlgorithmTester.cpp – главный файл программы, содержащий основную функцию консольного приложения int main().

2) Balancer.h – заголовочный файл, содержащий описание класса Balancer. Для удобства все алгоритмы из первой главы были вынесены в этот класс, поскольку они работают с одинаковыми наборами данных. Все данные также содержатся в классе.

3) Balancer.cpp – файл исходного кода, содержащий код для всех методов, описанных в заголовочном файле.

В главной функции int main(), находящейся в файле AlgorithmTester.cpp,  выполняется чтение названия файла с входными данными, после чего вызывается процедура void startTesting(string & testName), в которой аргументом является название файла. Происходит проверка на наличие этого файла. Если файл существует, то в цикле считываются исходные данные и вызываются алгоритмы балансировки, вычисляя время работы алгоритма. Результаты балансировки и время работы записываются в файл, как было описано ранее.

Внутри класса Balancer описаны две структуры данных:

· struct Task – структура данных, в которой хранится информация о задаче. Полями структуры являются: int id – номер задачи, int processingTime – время выполнения задачи;

· struct Machine – структура данных, в которой хранится информация о машине. Полями являются: int totalTime – общее время работы машины, int id – номер машины, vector<Task> assignedTasks – множество задач, назначенных на машину.

Полями класса являются:

· int numberOfTasks – число задач, которые необходимо распределить;

· int numberOfMachines – число машин, между которыми необходимо распределить задачи;

· queue<Task> tasks; – множество задач для алгоритмов без сортировки;

· vector<Task> sortedTasks; – множество задач для алгоритмов с сортировкой;

· vector<Machine> machines – множество машин, между которыми требуется распределить задачи;

· vector<int> priorityList – список номеров машин для очереди с приоритетом, основанной на двоичной куче. Первым в списке всегда будет номер машины с минимальной нагрузкой.

Все поля и структуры имеют модификатор доступа private, то есть доступ к ним есть только внутри класса.

Алгоритмы балансировки из первой главы вынесены в следующие методы:

· void greedyBalance(); – процедура Greedy Balance алгоритма;

· void sortedBalance(); – процедура Sorted Balance алгоритма;

· void greedyBalanceModified(); – процедура модифицированного Greedy Balance алгоритма. Используется очередь с приоритетом на основе двоичной кучи;

· void sortedBalanceModified(); – процедура Sorted Balance алгоритма с использованием очереди с приоритетом;

Прочими методами класса являются:

· int getProcessingPeriod(); – функция получения периода обработки;

· void startBalancing(int type = 0); – процедура запуска балансировки с указанным в параметрах алгоритмом;

· void addTask(int _processingTime); – процедура добавления задачи в множество задач с указанным временем выполнения;

· void setNumberOfMachines(int numberOfMachines_); – процедура установки балансировщику числа машин;

· void updateQueue(); – процедура обновления порядка в очереди с приоритетом;

· Balancer(); – конструктор класса;

· ~Balancer(); – деконструктор класса;

· static bool compareMachines(const Machine &a, const Machine &b); – функция сравнения двух машин;

· static bool compareTasks(const Task &a, const Task &b); – функция сравнения двух задач.

Все методы работают с данными, описанными внутри класса.

В программной реализации используются следующие директивы:

· iostream – заголовочный файл для работы с вводом/выводом, используется для вывода информации в окно консоли;

· vector – контейнер для эмуляции массива, используется в качестве множеств машин и задач;

· queue – контейнер для реализации очереди в Greedy и Sorted Balance функциях.

· algorithm – заголовочный файл с набором функций для работы с контейнерами, используется для сортировки множества задач и поиска машины с минимальным временем работы;

· fstream – заголовочный файл для работы с файлами, используется для чтения тестов из файлов и вывода информации в файл;

· string – класс для организации работы со строками;

· ctime – заголовочный файл для работы с временем, используется для вычисления времени работы.

Листинг программы приведён в Приложении 1.

Интерфейс программы

В качестве интерфейса программы используется консольное приложение. Пользователь вводит название файла с тестами, откуда будут считываться входные данные для балансировки. В случае, если файл не был найден, программа сообщит об этом. После выполнения всех тестов, приложение сообщает о завершении работы. На Рис. 2.3 и Рис. 2.4 приведены скриншоты окна консоли. Выходные данные записываются в файл “result_{название теста}.txt”.

Рис. 2.3. Скриншоты окна консоли программы.

Рис. 2.4. Скриншоты окна программы после выполнения тестирования.

Тестирование программы

Чтобы убедиться в правильности работы программной реализации был сгенерирован специальный тестовый файл, изображённый на Рис. 2.5. Всего будет 5 тестов, в которых между 5 машинами будут распределены 10 заданий. Время выполнения задания варьируется от 1 до 30.

Рис. 2.5. Файл для проверки работоспособности алгоритмов.

В Таблице 1 приведены результаты правильной балансировки для данных тестов. Все результаты получены путём ручной трассировки алгоритмов.

Таблица 1. Результаты балансировки теста.
Номер теста	Период обработки
	Greedy Balance	Sorted Balance
1	41	33
2	50	42
3	29	28
4	39	28
5	40	36

Подробная информация с временем работы и назначенными заданиями для каждой машины находится в Приложении 2.

Результат работы программы приведён на Рис. 2.6.

Рис. 2.6. Результат работы программы с файлом тестирования.

Чтобы убедиться в верности полученных результатов, сравним ответы в столбцах 1-3 с ответами из Таблицы 1. Кроме того, столбцы 1-5 и 3-7 должны также содержать одинаковые ответы. Результат работы программной реализации полностью идентичен результату, полученного при ручной трассировке. Алгоритмы реализованы верно.

Исследование времени работы

В качестве исходных данных возьмем следующее количество машин: 50, 100, 500, 1000, 2000. Количество задач будет в 2 и 5 раз больше количества машин. В тестовых файлах сгенерированы данные для тысячи тестов. Минимальное время выполнения задания равно 1, максимальное – 50. После прохождения всех тестов для каждого алгоритма вычисляем среднее арифметическое значение времени выполнения. Результаты тестирования записаны в Таблице 2. В первом столбце записано количество машин, участвующих в балансировке, во втором столбце указано количество задач, которое необходимо распределить между машинами. В последующих столбцах записано среднее время выполнения балансировки в секундах.

 

Таблица 2. Результаты тестирования.
Количество машин	Количество задач	Greedy Balance, сек.	Sorted Balance, сек.	Greedy Balance Modified, сек.	Sorted Balance Modified, сек.
50	100	0,00118	0,00132	0,00176	0,00186
50	250	0,00302	0,00345	0,00447	0,00478
100	200	0,00284	0,00317	0,00405	0,00424
100	500	0,00717	0,00796	0,01015	0,01069
500	1000	0,03228	0,03369	0,02571	0,02622
500	2500	0,08160	0,08510	0,06497	0,06673
1000	2000	0,11076	0,11350	0,05690	0,05757
1000	5000	0,27796	0,28477	0,14292	0,14614
2000	4000	0,40115	0,40671	0,12265	0,12382
2000	10000	1,01289	1,02636	0,31121	0,31694

По результатам тестирования, жадные алгоритмы с очередью с приоритетом работают дольше обычных алгоритмов при количестве машин менее 500. Но при большем количестве машин не модифицированные жадные алгоритмы оказываются медленнее в несколько раз. Так, при двух тысячах машин и десяти тысячах заданий жадные алгоритмы работают в 3 раза дольше модифицированных. Это связано с тем, что в GreedyBalance и SortedBalance поиск машины с минимальной нагрузкой занимает линейное время, то есть равно количеству машин. В других же алгоритмах используется очередь с приоритетом, обновление которой занимает логарифмическое время.

Жадные алгоритмы с сортировкой выполняют балансировку за большее время, так как им перед балансировкой требуется упорядочить все задачи по убыванию их времени выполнения. Чем больше задач, тем большее время будет затрачено.

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

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

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

 

Заключение

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

 

Библиографический список

1. Arregoces M., Portolani M. Data Center Fundamentals. – Cisco Press, 2004. – p. 676 –681.

2. KEMP Technologies: Load Balancing Techniques and Algorithms. [Электронный ресурс] – Режим доступа: https://kemptechnologies.com/load-balancer/load-balancing-algorithms-techniques/.

3. Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. Классика Computers Science. – СПб.: Питер, 2016. – с. 600–605.

4. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: Построение и анализ. – М.: И. Д. Вильямс, 2013. – с. 448.

5. Куроуз Д., Росс К. Компьютерные сети: Нисходящий подход. – М.: Издательство «Э», 2016. – с. 555.

 

Приложения

Приложение 1

AlgorithmTester.cpp:

#include "stdafx.h"

#include "Balancer.h"

#include <fstream>

#include <string>

#include <ctime>

 

using namespace std;

 

void startTesting(string & testName); // функция тестирования алгоритмов

 

int main() // главная функция

{

  system("chcp 1251"); // установка в консоли русского языка

  std::ios::sync_with_stdio(false); // отключение синхронизации с stdio для более быстрого чтения из файла

  string testName; // название файла для чтения

  cout << "Введите название теста, который будет выполняться" << endl; // вывод текста в консоль

  cin >> testName; // чтение из консоли названия файла

  startTesting(testName); // вызов функции тестирования алгоритмов

  cin.ignore(); // ожидание нажатий клавиш пользователем после выполнения тестов

  cin.get();

return 0;

}

 

void startTesting(string & testName)

{

  int numberOfMachines, numberOfTasks, numberOfTests; // numberOfMachines - число машин, numberOfTasks - число задач, numberOfTests - число тестов

  ifstream input("../Tests/" + testName + ".txt"); // открываем файл для чтения из него тестов и заданий

  clock_t operatingTime[4] = { 0 }; // объявляем массив с временем выполнения всех тестов для каждого алгоритма

  if (!input.is_open()) // если не получается открыть файл, выходим из функции

  {

        cout << "Невозможно открыть файлы тестирования" << endl;

        input.close(); // закрытие файла

        return; // выход из функции

  }

  input >> numberOfTests >> numberOfMachines >> numberOfTasks; // считываем из файла информацию

  cout << "Начато тестирование: " << testName << endl;

  cout << "Число машин: " << numberOfMachines << endl;

  cout << "Число задач в 1 тесте: " << numberOfTasks << endl;

  cout << "Общее число тестов: " << numberOfTests << endl;

  ofstream result("../Tests/result_" + testName + ".txt"); // создаем файл result.txt для вывода информации

  for (int i = 1; i <= numberOfTests; i++) // в цикле от 1 до числа тестов выполняем тестирование алгоритмов

  {

        int taskTime, workTime; // taskTime - время выполнения задания, workTime - время выполнения балансировки

        Balancer greedyTests[4]; // создаём объекты класса

        clock_t startTime, finishTime; // startTime - время начала выполнения балансировки

        for (int task = 0; task < numberOfTasks; task++) // считываем numberOfTasks чисел из файла и добавляем их в балансировщики

        {

               input >> taskTime; // считываем из текстового файла время выполнения задания

               for (int j = 0; j < 4; j++)

                      greedyTests[j].addTask(taskTime); // добавляем в каждый балансировщик данное задание

        }

        for (int j = 0; j < 4; j++) // выполнение тестирования

        {

               greedyTests[j].setNumberOfMachines(numberOfMachines); // устанавливаем количество машин в балансировщике

               startTime = clock(); // получаем время начала работы алгоритма

               greedyTests[j].startBalancing(j); // запускаем балансировку с необходимым алгоритмом

               finishTime = clock(); // получаем время после работы алгоритма

               workTime = (finishTime - startTime); // вычисляем время выполнения

               operatingTime[j] += workTime; // прибавляем время к общему времени

               result << greedyTests[j].getProcessingPeriod() << "\t" << (double)workTime /1000.0 << "\t"; // вывод в файл периода обработки

        }

        result << endl; // переход в файле на следующую строку

  }

  for (int j = 0; j < 4; j++)

        result << "\t" << (double)operatingTime[j] / 1000.0 << "\t"; // вывод в файл времени выполнения всех тестов

  cout << "Тестирование завершено" << endl;

  result.close(); // закрытие файлов

  input.close();

}

Balancer.h:

#pragma once