Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

Разработка и исследование планировщиков. на C++ 1) Разработать программу, моделирующую…

  1. User

    Разработка и исследование планировщиков. на C++

    1. Разработать программу, моделирующую работу планировщиков
    2. Данные о количестве задач в пакете и количестве процессоров взять согласно варианту из таблицы заданий
    3. Провести сравнительный анализ работы планировщиков с алгоритмами Макнотона и LPT по следующим характеристикам : × простой процессора × по величине 𝑇0 - длине соответствующего оптимального расписания.
    4. Диаграмму расписаний вывести на экран. (4 процессора в системе и 14 задач в пакете)
  2. Assistant

    Здравствуйте!

    Вы задали задачу разработки программы на C++, которая моделирует работу планировщиков с использованием алгоритмов Макнотона и LPT для 4 процессоров и 14 задач. Также необходимо провести сравнительный анализ по времени простоя процессоров и длине оптимального расписания ( T_0 ), а также вывести диаграммы расписаний на экран.

    Ниже я предоставлю вам реализацию программы с подробными комментариями, а также объяснения по каждому шагу.


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

    Алгоритм Макнотона

    Алгоритм Макнотона предназначен для минимизации максимального времени завершения всех задач (makespan) при наличии предопределенных времен выполнения задач и нескольких процессоров. Он распределяет задачи последовательно на процессоры, при необходимости разбивая задачи, чтобы обеспечить оптимальное расписание.

    Алгоритм LPT (Longest Processing Time)

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


    Реализация программы

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

    1. Определение классов и структур данных:

      • Структура Task для представления задачи с идентификатором и временем выполнения.
      • Структура Processor для представления процессора с его расписанием задач.
    2. Функции:

      • Функция для реализации алгоритма Макнотона.
      • Функция для реализации алгоритма LPT.
      • Функции для вывода расписаний и вычисления статистик.
    3. Основная функция main:

      • Инициализация данных.
      • Вызов алгоритмов.
      • Вывод результатов и диаграмм расписаний.

    Код программы

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <iomanip>
    
    struct Task {
        int id;
        double processing_time;
    };
    
    struct Processor {
        int id;
        std::vector<Task> schedule;
        double total_time = 0.0;
    };
    
    // Функция для вывода расписания
    void printSchedule(const std::vector<Processor>& processors, const std::string& algorithm_name) {
        std::cout << "=== Расписание по алгоритму " << algorithm_name << " ===\n";
        for (const auto& processor : processors) {
            std::cout << "Процессор " << processor.id << ": ";
            for (const auto& task : processor.schedule) {
                std::cout << "[Задача " << task.id << " (" << task.processing_time << ")] ";
            }
            std::cout << "\n";
        }
        std::cout << "\n";
    }
    
    // Реализация алгоритма Макнотона
    void mcnaughtonAlgorithm(const std::vector<Task>& tasks, int m) {
        double total_processing_time = 0.0;
        for (const auto& task : tasks) {
            total_processing_time += task.processing_time;
        }
        double T0 = total_processing_time / m; // оптимальное время расписания
    
        std::vector<Processor> processors(m);
        for (int i = 0; i < m; ++i) {
            processors[i].id = i + 1;
        }
    
        int current_processor = 0;
        double time_filled = 0.0;
        for (const auto& task : tasks) {
            if (task.processing_time > T0) {
                // Задача больше оптимального времени, необходимо разбить
                processors[current_processor].schedule.push_back({task.id, T0 - time_filled});
                processors[current_processor].total_time += T0 - time_filled;
                ++current_processor;
                processors[current_processor].schedule.push_back({task.id, task.processing_time - (T0 - time_filled)});
                processors[current_processor].total_time += task.processing_time - (T0 - time_filled);
                time_filled = task.processing_time - (T0 - time_filled);
            } else {
                if (time_filled + task.processing_time <= T0) {
                    processors[current_processor].schedule.push_back(task);
                    processors[current_processor].total_time += task.processing_time;
                    time_filled += task.processing_time;
                } else {
                    ++current_processor;
                    time_filled = 0.0;
                    processors[current_processor].schedule.push_back(task);
                    processors[current_processor].total_time += task.processing_time;
                    time_filled += task.processing_time;
                }
            }
        }
    
        printSchedule(processors, "Макнотона");
    
        // Вычисление простоя процессоров
        double idle_time = 0.0;
        for (const auto& processor : processors) {
            idle_time += T0 - processor.total_time;
        }
        std::cout << "Общее время простоя процессоров по Макнотона: " << idle_time << "\n";
        std::cout << "Длина оптимального расписания T0: " << T0 << "\n\n";
    }
    
    // Реализация алгоритма LPT
    void lptAlgorithm(std::vector<Task> tasks, int m) {
        // Сортировка задач по убыванию времени выполнения
        std::sort(tasks.begin(), tasks.end(), [](const Task& a, const Task& b) {
            return a.processing_time > b.processing_time;
        });
    
        std::vector<Processor> processors(m);
        for (int i = 0; i < m; ++i) {
            processors[i].id = i + 1;
        }
    
        for (const auto& task : tasks) {
            // Находим процессор с наименьшей текущей загрузкой
            auto min_processor = std::min_element(processors.begin(), processors.end(), [](const Processor& a, const Processor& b) {
                return a.total_time < b.total_time;
            });
            min_processor->schedule.push_back(task);
            min_processor->total_time += task.processing_time;
        }
    
        printSchedule(processors, "LPT");
    
        // Вычисление максимального времени выполнения (makespan)
        double makespan = 0.0;
        for (const auto& processor : processors) {
            if (processor.total_time > makespan) {
                makespan = processor.total_time;
            }
        }
    
        // Вычисление простоя процессоров
        double total_processing_time = 0.0;
        for (const auto& task : tasks) {
            total_processing_time += task.processing_time;
        }
        double idle_time = m * makespan - total_processing_time;
        std::cout << "Общее время простоя процессоров по LPT: " << idle_time << "\n";
        std::cout << "Длина расписания (makespan): " << makespan << "\n\n";
    }
    
    int main() {
        int m = 4; // количество процессоров
        int n = 14; // количество задач
    
        // Задаем времена выполнения задач (можно использовать случайные или фиксированные значения)
        std::vector<Task> tasks = {
            {1, 10}, {2, 6}, {3, 2}, {4, 8}, {5, 4}, {6, 3}, {7, 5},
            {8, 7}, {9, 9}, {10, 1}, {11, 2}, {12, 4}, {13, 6}, {14, 5}
        };
    
        // Проверяем, что количество задач соответствует заданному
        if (tasks.size() != n) {
            std::cerr << "Количество задач не соответствует заданному (" << n << ").\n";
            return 1;
        }
    
        // Выводим начальные данные
        std::cout << "Количество процессоров: " << m << "\n";
        std::cout << "Количество задач: " << n << "\n";
        std::cout << "Задачи и их времена выполнения:\n";
        for (const auto& task : tasks) {
            std::cout << "Задача " << task.id << ": " << task.processing_time << "\n";
        }
        std::cout << "\n";
    
        // Запускаем алгоритм Макнотона
        mcnaughtonAlgorithm(tasks, m);
    
        // Запускаем алгоритм LPT
        lptAlgorithm(tasks, m);
    
        return 0;
    }
    

    Объяснения

    1. Структуры Task и Processor:

      • Task содержит идентификатор задачи и время ее выполнения.
      • Processor содержит идентификатор процессора, список назначенных задач и общее время загрузки.
    2. Функция printSchedule:

      • Отвечает за вывод расписания для каждого процессора.
      • Принимает вектор процессоров и название алгоритма для отображения.
    3. Алгоритм Макнотона (mcnaughtonAlgorithm):

      • Вычисляет оптимальное время расписания ( T_0 = \frac{\sum p_i}{m} ), где ( p_i ) – время выполнения задачи, ( m ) – количество процессоров.
      • Распределяет задачи по процессорам, разбивая задачи, превышающие ( T_0 ).
      • Вычисляет общее время простоя процессоров и выводит расписание.
    4. Алгоритм LPT (lptAlgorithm):

      • Сортирует задачи по убыванию времени выполнения.
      • Назначает каждую задачу на процессор с наименьшей текущей загрузкой.
      • Вычисляет makespan (максимальное время завершения) и общее время простоя процессоров.
      • Выводит расписание.
    5. Функция main:

      • Инициализирует задачи и процессоры.
      • Выводит начальные данные.
      • Вызывает оба алгоритма и отображает результаты.

    Сравнительный анализ

    После выполнения программы вы получите расписания по обоим алгоритмам, а также статистические данные:

    • Время простоя процессоров: показывает суммарное время, когда процессоры не были заняты выполнением задач.
    • Длина оптимального расписания ( T_0 ): для алгоритма Макнотона.
    • Makespan: для алгоритма LPT, максимальное время завершения.

    Сравнивая эти показатели, можно сделать выводы о том, какой алгоритм эффективнее в заданных условиях.


    Диаграммы расписаний

    Для вывода диаграмм расписаний на экран в текстовом виде программа отображает задачи для каждого процессора последовательно.

    Пример вывода:

    === Расписание по алгоритму Макнотона ===
    Процессор 1: [Задача 1 (9.5)] [Задача 2 (0.5)]
    Процессор 2: [Задача 2 (5.5)] [Задача 3 (2)] [Задача 4 (1)]
    ...
    

    Каждая строка представляет процессор и задачи, назначенные ему, с указанием времени выполнения.


    Заключение

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

    Если у вас возникнут вопросы или понадобится дополнительная помощь, пожалуйста, обращайтесь!