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

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

Средой разработки был выбран Microsoft Visual Studio, так как он является бесплатным инструментом, включающим в себя редактор исходного кода, встроенный отладчик, а также имеет возможность создавать или добавлять дополнительные библиотеки для расширения функциональности.

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

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

В первой строке входного файла содержится следующая информация: 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 должны также содержать одинаковые ответы. Результат работы программной реализации полностью идентичен результату, полученного при ручной трассировке. Алгоритмы реализованы верно.