C++ 实现短作业优先调度算法 (SJF) 代码示例及练习题

以下是 C++ 语言实现短作业优先调度算法的代码示例：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 进程结构体，包含进程 ID、到达时间和执行时间
struct Process {
    int id;       // 进程 ID
    int arrival;  // 到达时间
    int burst;    // 执行时间
    Process(int id, int arrival, int burst) {
        this->id = id;
        this->arrival = arrival;
        this->burst = burst;
    }
};
// 按到达时间排序的比较函数
bool compareArrival(const Process& p1, const Process& p2) {
    return p1.arrival < p2.arrival;
}
// 短作业优先调度算法
void sjf(const vector<Process>& processes) {
    int n = processes.size();
    // 根据到达时间排序
    vector<Process> sortedProcesses = processes;
    sort(sortedProcesses.begin(), sortedProcesses.end(), compareArrival);
    // 记录完成时间、周转时间和等待时间
    vector<int> completion(n);
    vector<int> turnaround(n);
    vector<int> waiting(n);
    for (int i = 0, currentTime = 0; i < n; i++) {
        // 选择执行时间最短的进程
        int shortestJobIndex = i;
        for (int j = i + 1; j < n && sortedProcesses[j].arrival <= currentTime; j++) {
            if (sortedProcesses[j].burst < sortedProcesses[shortestJobIndex].burst) {
                shortestJobIndex = j;
            }
        }
        // 更新当前时间、完成时间、周转时间和等待时间
        completion[sortedProcesses[shortestJobIndex].id - 1] = currentTime + sortedProcesses[shortestJobIndex].burst;
        turnaround[sortedProcesses[shortestJobIndex].id - 1] = completion[sortedProcesses[shortestJobIndex].id - 1] - sortedProcesses[shortestJobIndex].arrival;
        waiting[sortedProcesses[shortestJobIndex].id - 1] = turnaround[sortedProcesses[shortestJobIndex].id - 1] - sortedProcesses[shortestJobIndex].burst;
        currentTime = completion[sortedProcesses[shortestJobIndex].id - 1];
        // 将已完成的进程移动到末尾
        swap(sortedProcesses[shortestJobIndex], sortedProcesses[i]);
    }
    // 输出结果
    cout << "进程 | 完成时间 | 周转时间 | 等待时间" << endl;
    cout << "-----|-----------|-----------|-----------" << endl;
    for (int i = 0; i < n; i++) {
        cout << "P" << i + 1 << "    | " << completion[i] << "        | " << turnaround[i] << "        | " << waiting[i] << endl;
    }
}
int main() {
    // 测试用例
    vector<Process> processes = {
        Process(1, 0, 6),
        Process(2, 1, 8),
        Process(3, 2, 7),
        Process(4, 3, 3),
        Process(5, 4, 4)
    };
    sjf(processes);
    return 0;
}

练习题

假设有五个进程，它们的到达时间、执行时间分别为：

| 进程 | 到达时间 | 执行时间 | |---|---|---| | P1 | 0 | 6 | | P2 | 1 | 8 | | P3 | 2 | 7 | | P4 | 3 | 3 | | P5 | 4 | 4 |

请使用短作业优先调度算法计算它们的完成时间、周转时间和等待时间，并输出结果。

提示： 可以按到达时间排序后依次选择执行时间最短的进程。

解答

按到达时间排序后，进程的顺序为：P1、P2、P3、P4、P5。

首先执行 P1，完成时间为 6，周转时间为 6，等待时间为 0。

然后执行 P4，完成时间为 9，周转时间为 6，等待时间为 3（P1 在执行期间等待了 3 个时间单位）。

接着执行 P5，完成时间为 13，周转时间为 9，等待时间为 5（P1 和 P4 在执行期间分别等待了 4 和 1 个时间单位）。

然后执行 P3，完成时间为 20，周转时间为 18，等待时间为 11（P1、P4 和 P5 在执行期间分别等待了 7、6 和 5 个时间单位）。

最后执行 P2，完成时间为 28，周转时间为 27，等待时间为 20（P1、P4、P5 和 P3 在执行期间分别等待了 22、19、18 和 13 个时间单位）。

因此，这五个进程的完成时间、周转时间和等待时间分别为：

| 进程 | 完成时间 | 周转时间 | 等待时间 | |---|---|---|---| | P1 | 6 | 6 | 0 | | P2 | 28 | 27 | 20 | | P3 | 20 | 18 | 11 | | P4 | 9 | 6 | 3 | | P5 | 13 | 9 | 5 |