C++ 实现 FCFS 调度程序：先来先服务算法实践

介绍

在本次实验中，你将使用 C++ 实现先来先服务（First Come First Serve, FCFS）调度算法。FCFS 是最简单的 CPU 调度算法，它按照进程请求 CPU 的顺序为其分配 CPU。就绪队列中最先到达的进程将最先得到服务。

该算法易于理解和实现，但在平均等待时间方面可能无法提供最优性能。在本次实验结束时，你将了解 FCFS 算法的工作原理，并能够计算进程的重要指标，如等待时间和周转时间。

理解 FCFS 并创建程序结构

先来先服务（First Come First Serve, FCFS）是一种非抢占式调度算法，进程按照它们进入就绪队列的顺序依次执行。在这一步中，你将创建程序文件并搭建基本结构。

首先，创建一个新的 C++ 文件：

打开 WebIDE 界面，导航到文件资源管理器面板。
在资源管理器面板中右键单击，选择“新建文件”。
将文件命名为 fcfs.cpp，然后按回车键。

现在，为程序添加必要的头文件和命名空间声明：

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    return 0;
}

这段代码为程序搭建了基本结构，包含：

#include <iostream> —— 用于输入/输出操作
#include <iomanip> —— 用于格式化输出表格
using namespace std; —— 使用标准命名空间
一个 main() 函数，用于显示标题

编译并运行程序，确保一切设置正确：

g++ fcfs.cpp -o fcfs
./fcfs

你应该会看到以下输出：

FCFS Scheduling Algorithm Implementation
----------------------------------------

这表明程序的基本结构已正确运行。下一步，你将实现输入进程详细信息的功能。

实现进程输入功能

在这一步中，你将实现收集待调度进程信息的功能。对于 FCFS 调度算法，你需要了解以下信息：

进程的数量
每个进程的突发时间（每个进程所需的执行时间）

修改 fcfs.cpp 文件以包含此功能：

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                  // Number of processes
    int burst_time[20];     // Array to store burst time of each process

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Display the entered data
    cout << "\nProcess\tBurst Time" << endl;
    cout << "--------------------" << endl;
    for (int i = 0; i < n; i++) {
        cout << "P" << i + 1 << "\t" << burst_time[i] << endl;
    }

    return 0;
}

下面来看看新增的内容：

用于存储进程数量 (n) 和每个进程突发时间 (burst_time[20]) 的变量。
用于收集进程数量和每个进程突发时间的输入提示。
输入验证，确保进程数量在合理范围（1 - 20）内，且突发时间为正数。
一个表格显示，用于验证输入的数据。

编译并运行更新后的程序：

g++ fcfs.cpp -o fcfs
./fcfs

运行程序时，你将被提示输入进程数量及其突发时间。尝试输入以下数据：

这表示有 3 个进程，其突发时间分别为 5、9 和 4 个时间单位。你应该会看到类似以下的输出：

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time
--------------------
P1      5
P2      9
P3      4

这证实了输入功能已正确实现。下一步，你将计算每个进程的等待时间和周转时间。

计算等待时间和周转时间

在这一步中，你将为每个进程计算两个重要的指标：

等待时间（Waiting Time, WT）：进程在就绪队列中等待获取 CPU 时间的时长。
周转时间（Turnaround Time, TAT）：从进程提交到完成所花费的总时间。

下面来了解在 FCFS 算法中这些指标是如何计算的：

对于第一个进程（P1），等待时间始终为 0（它立即开始执行）。
对于后续进程，等待时间是所有先前进程突发时间的总和。
每个进程的周转时间是其突发时间和等待时间的总和。

现在，修改 fcfs.cpp 文件以添加这些计算：

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    return 0;
}

下面来看看新增的内容：

两个新数组：waiting_time[20] 和 turnaround_time[20]，用于存储每个进程的等待时间和周转时间。
用于跟踪总等待时间和总周转时间的变量。
等待时间的计算：
- 第一个进程的等待时间为 0。
- 对于每个后续进程，等待时间是所有先前进程突发时间的总和。
周转时间的计算：
- 对于每个进程，周转时间 = 突发时间 + 等待时间。
一个格式化表格，用于显示计算结果。

编译并运行更新后的程序：

g++ fcfs.cpp -o fcfs
./fcfs

尝试输入与之前相同的数据：

你应该会看到类似以下的输出：

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

下面来分析这些结果：

P1：等待时间 = 0，周转时间 = 5（其突发时间）
P2：等待时间 = 5（P1 的突发时间），周转时间 = 14（5 + 9）
P3：等待时间 = 14（P1 + P2 的突发时间），周转时间 = 18（14 + 4）

这证实了等待时间和周转时间的计算是正确的。下一步，你将计算平均时间并显示最终结果。

计算平均时间并显示最终结果

在这最后一步，你将计算所有进程的平均等待时间和平均周转时间。这些平均值是评估调度算法效率的重要指标。

修改 fcfs.cpp 文件以添加这些计算并完成程序：

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;
    float avg_waiting_time = 0.0;
    float avg_turnaround_time = 0.0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    // Calculate average waiting time and average turnaround time
    avg_waiting_time = (float)total_waiting_time / n;
    avg_turnaround_time = (float)total_turnaround_time / n;

    // Display the results with two decimal places
    cout << fixed << setprecision(2);
    cout << "\nAverage Waiting Time: " << avg_waiting_time << " time units" << endl;
    cout << "Average Turnaround Time: " << avg_turnaround_time << " time units" << endl;

    // Visual representation of the FCFS schedule (Gantt chart in text)
    cout << "\nGantt Chart:" << endl;
    cout << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }
    cout << endl << "|";

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "P" << i + 1;
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "|";
    }

    cout << endl << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }

    cout << endl;
    cout << "0";
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        current_time += burst_time[i];
        for (int j = 0; j < burst_time[i] * 2 - 1; j++) {
            cout << " ";
        }
        if (current_time < 10) cout << " ";
        cout << current_time;
    }
    cout << endl;

    return 0;
}

下面来看看新增的内容：

两个新变量：avg_waiting_time 和 avg_turnaround_time，用于存储平均时间。
平均时间的计算：
- 平均等待时间 = 总等待时间 / 进程数量
- 平均周转时间 = 总周转时间 / 进程数量
格式化输出，以两位小数显示平均时间。
一个简单的基于文本的甘特图（Gantt chart），用于可视化 FCFS 调度：
- 每个进程由其 ID（P1、P2 等）表示。
- 每个进程块的宽度与其突发时间成正比。
- 时间标记显示在底部。

编译并运行最终程序：

g++ fcfs.cpp -o fcfs
./fcfs

尝试输入与之前相同的数据：

你应该会看到类似以下的输出：

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

Average Waiting Time: 6.33 time units
Average Turnaround Time: 12.33 time units

Gantt Chart:
 --------------------
|   P1    |    P2    |  P3  |
 --------------------
0         5         14     18

查看结果：

平均等待时间：(0 + 5 + 14) / 3 = 6.33 个时间单位
平均周转时间：(5 + 14 + 18) / 3 = 12.33 个时间单位

甘特图直观地展示了进程随时间的调度情况：

P1 在时间 0 到 5 运行
P2 在时间 5 到 14 运行
P3 在时间 14 到 18 运行

至此，你已完成 FCFS 调度算法的实现。你可以尝试不同数量的进程和突发时间，看看它们如何影响平均等待时间和周转时间。

总结

在本次实验中，你已成功使用 C++ 实现了先来先服务（First Come First Serve, FCFS）CPU 调度算法。以下是你学到的关键概念和技能：

FCFS 算法基础：理解进程如何按照到达顺序进行调度。
性能指标计算：
- 等待时间：进程在开始执行前等待的时间。
- 周转时间：从进程提交到完成的总时间。
- 平均等待时间和平均周转时间：调度算法的关键性能指标。
C++ 编程概念：
- 使用数组存储进程信息。
- 使用循环进行迭代计算。
- 带验证的输入/输出操作。
- 格式化输出，以便更好地展示数据。
可视化技术：创建基于文本的甘特图（Gantt chart），以可视化调度时间线。

FCFS 算法易于理解和实现，但并不总是能提供最优性能。它可能会导致“护航效应”，即短进程会被长进程阻塞，从而增加平均等待时间。

本次实现为理解更复杂的调度算法（如最短作业优先（Shortest Job First, SJF）、优先级调度和轮转调度（Round Robin, RR））奠定了基础，这些算法旨在优化进程调度的不同方面。

用于 FCFS 调度算法的 C++ 程序

介绍

理解 FCFS 并创建程序结构

实现进程输入功能

计算等待时间和周转时间

计算平均时间并显示最终结果

总结