Реализация алгоритма кругового планирования (Round Robin Scheduling Algorithm)

Введение

В этом лабораторном занятии мы научимся реализовывать алгоритм планирования по кругу (Round Robin Scheduling Algorithm) на языке C++. Алгоритм планирования по кругу является прерываемым алгоритмом, в котором процесс выполняется в течение фиксированного временного интервала, известного как квант времени (time quantum). Если процесс завершает выполнение в рамках кванта времени, он завершается, в противном случае он перемещается в конец очереди готовых процессов.

Создать новый файл на C++

Сначала создайте новый файл на языке C++ в директории ~/project. Вы можете назвать его round_robin.cpp.

cd ~/project
touch round_robin.cpp

Подключить необходимые библиотеки

Подключите необходимые библиотеки в файле round_robin.cpp.

#include <iostream>
using namespace std;

Определить функцию main()

Определите функцию main() и инициализируйте идентификаторы процессов (process IDs), времена выполнения (burst times), квант времени (quantum) и количество процессов.

int main()
{
    // Process IDs
    int processes[] = { 1, 2, 3, 4 };

    // Burst time of all processes
    int burst_time[] = { 5, 9, 6, 8 };

    // Time quantum
    int quantum = 2;

    // Number of processes
    int n = sizeof processes / sizeof processes[0];

    return 0;
}

Реализовать функцию для нахождения времени ожидания

Функция findWaitingTime() используется для нахождения времени ожидания для всех процессов. Эта функция определена для итерации по процессам в порядке кругового планирования (round-robin).

void findWaitingTime(int processes[], int n, int bt[], int wt[], int quantum)
{
    // Make a copy of burst times bt[] to store remaining
    // burst times.
    int rem_bt[n];
    for (int i = 0; i < n; i++)
        rem_bt[i] = bt[i];

    int t = 0; // Current time

    // Keep traversing processes in round-robin manner
    // until all of them are not done.
    while (1) {
        bool done = true;

        // Traverse all processes one by one repeatedly
        for (int i = 0; i < n; i++) {
            // If burst time of a process is greater than 0
            // then only need to process further
            if (rem_bt[i] > 0) {
                done = false; // There is a pending process

                /* If remaining burst time is greater than
                quantum then decrease the time slice
                from remaining burst time */
                if (rem_bt[i] > quantum) {
                    // Increase the value of t i.e. shows
                    // how much time a process has been processed
                    t += quantum;

                    // Decrease the burst_time of current process
                    // by quantum
                    rem_bt[i] -= quantum;
                }
                /* If remaining burst time is smaller than
                or equal to quantum then the remaining
                burst time for this process is 0.*/
                else {
                    // Increase the value of t i.e. shows
                    // how much time a process has been processed
                    t += rem_bt[i];

                    // Waiting time is current time minus time
                    // used by this process
                    wt[i] = t - bt[i];

                    // As the process gets fully executed
                    // make its remaining burst time = 0
                    rem_bt[i] = 0;
                }
            }
        }

        // If all processes are done
        if (done == true)
            break;
    }
}

Реализовать функцию для нахождения времени выполнения процесса

Функция findTurnAroundTime() используется для нахождения времени выполнения (turn around time) для всех процессов.

void findTurnAroundTime(int processes[], int n,
                         int bt[], int wt[], int tat[])
{
    // calculating turnaround time by adding
    // bt[i] + wt[i]
    for (int i = 0; i < n; i++)
        tat[i] = bt[i] + wt[i];
}

Реализовать функцию для вычисления среднего времени

Функция findavgTime() используется для вычисления среднего времени ожидания и среднего времени выполнения (turn around time) для всех процессов.

void findavgTime(int processes[], int n, int bt[],
                                                 int quantum)
{
    int wt[n], tat[n], total_wt = 0, total_tat = 0;

    // Function to find waiting time of all processes
    findWaitingTime(processes, n, bt, wt, quantum);

    // Function to find turn around time for all processes
    findTurnAroundTime(processes, n, bt, wt, tat);

    // Display processes along with all details
    cout << "Processes "
         << " Burst time "
         << " Waiting time "
         << " Turn around time\n";

    // Calculate total waiting time and total turn
    // around time
    for (int i = 0; i < n; i++) {
        total_wt = total_wt + wt[i];
        total_tat = total_tat + tat[i];
        cout << " " << i + 1 << "\t\t" << bt[i] << "\t "
             << wt[i] << "\t\t " << tat[i] << endl;
    }

    cout << "Average waiting time = "
         << (float)total_wt / (float)n;
    cout << "\nAverage turn around time = "
         << (float)total_tat / (float)n;
}

Вызвать функцию findavgTime()

Вызовите функцию findavgTime() для вычисления среднего времени ожидания и среднего времени выполнения (turn around time) для процессов.

int main()
{
    int processes[] = { 1, 2, 3, 4 };

    // Burst time of all processes
    int burst_time[] = { 5, 9, 6, 8 };

    // Time quantum
    int quantum = 2;

    // Number of processes
    int n = sizeof processes / sizeof processes[0];

    // Function to find average time
    findavgTime(processes, n, burst_time, quantum);

    return 0;
}

Для запуска кода в терминале выполните следующую команду из директории ~/project.

g++ round_robin.cpp -o round_robin &&./round_robin

Резюме

В этом лабораторном занятии мы научились реализовывать алгоритм кругового планирования (Round Robin Scheduling Algorithm) на языке C++. Этот алгоритм используется для планирования процессов в операционной системе на временной интервал, известный как квант времени (time quantum). Мы также рассмотрели, как вычислить среднее время ожидания и среднее время выполнения (turn around time) для набора процессов.