实现轮转调度算法 - C++ 编程教程

介绍

在本实验中，我们将学习如何在 C++ 中实现轮转调度算法（Round Robin Scheduling Algorithm）。轮转调度算法是一种抢占式算法，其中每个进程会执行一个固定的时间片（time quantum）。如果进程在时间片内完成了执行，它将被终止；否则，它会被移到就绪队列的末尾。

创建一个新的 C++ 文件

首先，在 ~/project 目录下创建一个新的 C++ 文件。你可以将其命名为 round_robin.cpp。

cd ~/project
touch round_robin.cpp

包含必要的库

在 round_robin.cpp 文件中包含必要的库。

#include <iostream>
using namespace std;

定义 main() 函数

定义 main() 函数并初始化进程 ID、执行时间（burst time）、时间片（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() 用于计算所有进程的等待时间。该函数以轮转方式遍历进程。

void findWaitingTime(int processes[], int n, int bt[], int wt[], int quantum)
{
    // 复制 burst time bt[] 以存储剩余的 burst time
    int rem_bt[n];
    for (int i = 0; i < n; i++)
        rem_bt[i] = bt[i];

    int t = 0; // 当前时间

    // 以轮转方式持续遍历进程，直到所有进程完成
    while (1) {
        bool done = true;

        // 重复遍历所有进程
        for (int i = 0; i < n; i++) {
            // 如果进程的 burst time 大于 0，则需要进一步处理
            if (rem_bt[i] > 0) {
                done = false; // 有未完成的进程

                /* 如果剩余的 burst time 大于 quantum，
                则从剩余的 burst time 中减去时间片 */
                if (rem_bt[i] > quantum) {
                    // 增加 t 的值，表示进程已处理的时间
                    t += quantum;

                    // 将当前进程的 burst time 减去 quantum
                    rem_bt[i] -= quantum;
                }
                /* 如果剩余的 burst time 小于或等于 quantum，
                则该进程的剩余 burst time 为 0 */
                else {
                    // 增加 t 的值，表示进程已处理的时间
                    t += rem_bt[i];

                    // 等待时间是当前时间减去该进程使用的 burst time
                    wt[i] = t - bt[i];

                    // 由于进程已完全执行，将其剩余 burst time 设为 0
                    rem_bt[i] = 0;
                }
            }
        }

        // 如果所有进程都已完成
        if (done == true)
            break;
    }
}

实现计算周转时间的函数

函数 findTurnAroundTime() 用于计算所有进程的周转时间。

void findTurnAroundTime(int processes[], int n,
                         int bt[], int wt[], int tat[])
{
    // 通过 bt[i] + wt[i] 计算周转时间
    for (int i = 0; i < n; i++)
        tat[i] = bt[i] + wt[i];
}

实现计算平均时间的函数

函数 findavgTime() 用于计算所有进程的平均等待时间和平均周转时间。

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

    // 计算所有进程的等待时间
    findWaitingTime(processes, n, bt, wt, quantum);

    // 计算所有进程的周转时间
    findTurnAroundTime(processes, n, bt, wt, tat);

    // 显示进程及其详细信息
    cout << "Processes "
         << " Burst time "
         << " Waiting time "
         << " Turn around time\n";

    // 计算总等待时间和总周转时间
    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() 函数以计算进程的平均等待时间和平均周转时间。

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

    // 所有进程的 burst time
    int burst_time[] = { 5, 9, 6, 8 };

    // 时间片（quantum）
    int quantum = 2;

    // 进程数量
    int n = sizeof processes / sizeof processes[0];

    // 计算平均时间的函数
    findavgTime(processes, n, burst_time, quantum);

    return 0;
}

要在终端中运行代码，请在 ~/project 目录下执行以下命令。

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

总结

在本实验中，我们学习了如何在 C++ 中实现轮转调度算法（Round Robin Scheduling Algorithm）。该算法用于在操作系统中调度进程，每个进程会执行一个固定的时间片（time quantum）。我们还学习了如何计算一组进程的平均等待时间和平均周转时间。