C++最短作业优先算法详解（手把手教你用C++实现SJF调度算法）

SJF算法的基本步骤

1. 收集所有进程的到达时间和执行时间（CPU burst time）。
2. 按到达时间排序（因为进程是随时间陆续到达的）。
3. 在当前可执行的进程中（已到达但未执行），选择执行时间最短的那个。
4. 重复上述过程，直到所有进程执行完毕。

C++代码实现

下面是一个完整的C++实现SJF算法的示例程序：

#include <iostream>#include <vector>#include <algorithm>using namespace std;// 定义进程结构体struct Process {    int id;          // 进程ID    int arrival;     // 到达时间    int burst;       // 执行时间    int start;       // 开始执行时间    int completion;  // 完成时间    int waiting;     // 等待时间    int turnaround;  // 周转时间};// 比较函数：按到达时间排序bool compareArrival(const Process &a, const Process &b) {    return a.arrival < b.arrival;}// 比较函数：按执行时间排序（用于选择最短作业）bool compareBurst(const Process &a, const Process &b) {    return a.burst < b.burst;}void SJF(vector<Process> &processes) {    int n = processes.size();    vector<bool> completed(n, false);    int currentTime = 0;    int completedCount = 0;    // 按到达时间排序    sort(processes.begin(), processes.end(), compareArrival);    while (completedCount < n) {        vector<Process> available;        for (int i = 0; i < n; i++) {            if (!completed[i] && processes[i].arrival <= currentTime) {                available.push_back(processes[i]);            }        }        if (available.empty()) {            currentTime++; // CPU空闲，时间推进            continue;        }        // 在可用进程中选择执行时间最短的        sort(available.begin(), available.end(), compareBurst);        int selectedId = available[0].id;        // 找到原数组中的索引        int idx = -1;        for (int i = 0; i < n; i++) {            if (processes[i].id == selectedId) {                idx = i;                break;            }        }        // 设置执行信息        processes[idx].start = currentTime;        processes[idx].completion = currentTime + processes[idx].burst;        processes[idx].turnaround = processes[idx].completion - processes[idx].arrival;        processes[idx].waiting = processes[idx].turnaround - processes[idx].burst;        currentTime = processes[idx].completion;        completed[idx] = true;        completedCount++;    }}int main() {    int n;    cout << "请输入进程数量: ";    cin >> n;    vector<Process> processes(n);    for (int i = 0; i < n; i++) {        processes[i].id = i + 1;        cout << "请输入进程 " << i + 1 << " 的到达时间和执行时间: ";        cin >> processes[i].arrival >> processes[i].burst;    }    SJF(processes);    // 输出结果    cout << "\n进程调度结果:\n";    cout << "ID\t到达\t执行\t开始\t完成\t等待\t周转\n";    float totalWaiting = 0, totalTurnaround = 0;    for (const auto &p : processes) {        cout << p.id << "\t" << p.arrival << "\t" << p.burst << "\t"             << p.start << "\t" << p.completion << "\t"             << p.waiting << "\t" << p.turnaround << "\n";        totalWaiting += p.waiting;        totalTurnaround += p.turnaround;    }    cout << "\n平均等待时间: " << totalWaiting / n << endl;    cout << "平均周转时间: " << totalTurnaround / n << endl;    return 0;}

代码说明

上面的代码实现了非抢占式SJF调度：

• Process 结构体存储每个进程的关键信息。
• 主函数 SJF 模拟调度过程：在每个时间点，找出所有已到达但未执行的进程，从中选择 burst 最小的执行。
• 程序最后输出每个进程的详细调度信息，并计算平均等待时间和平均周转时间。

运行示例

假设输入如下：

请输入进程数量: 4请输入进程 1 的到达时间和执行时间: 0 6请输入进程 2 的到达时间和执行时间: 1 8请输入进程 3 的到达时间和执行时间: 2 7请输入进程 4 的到达时间和执行时间: 3 3

程序将优先执行进程4（执行时间最短为3），然后是进程1（6）、进程3（7）、最后是进程2（8）。

总结

通过本教程，你已经掌握了如何用C++实现SJF调度算法。这种SJF调度算法C++实现不仅有助于理解操作系统原理，还能提升你的编程能力。记住，SJF虽然能最小化平均等待时间，但在实际系统中可能因“饥饿”问题（长作业一直得不到执行）而不被单独使用。建议结合其他调度算法（如多级反馈队列）综合学习。

希望这篇关于C++最短作业优先算法的教程对你有所帮助！动手试试吧～