C++ 实现短作业优先 (SJF) 调度算法：使用结构体和自定义比较函数

本文介绍了使用 C++ 实现短作业优先 (SJF) 调度算法的方法，包括定义进程结构体、使用自定义比较函数对进程进行排序、使用最小堆进行调度以及计算平均等待时间和平均周转时间。

代码实现

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

// 进程结构体
struct Process {
    int id; // 进程编号
    int arrival_time; // 到达时间
    int burst_time; // 执行时间
    int waiting_time; // 等待时间
    int turnaround_time; // 周转时间
    // 自定义比较函数，按执行时间排序
    bool operator<(const Process& other) const {
        return burst_time > other.burst_time;
    }
};

// 短作业优先(SJF)调度算法
void sjf_schedule(vector<Process>& processes) {
    // 按到达时间排序
    sort(processes.begin(), processes.end(),
         [](const Process& p1, const Process& p2) {
            return p1.arrival_time < p2.arrival_time;
         });
    // 最小堆，按执行时间排序
    priority_queue<Process> pq;
    int current_time = 0;
    int total_waiting_time = 0;
    int total_turnaround_time = 0;
    // 循环执行进程
    for (int i = 0; i < processes.size(); i++) {
        // 当前时间小于等于进程到达时间，直接执行进程
        if (current_time <= processes[i].arrival_time) {
            current_time = processes[i].arrival_time + processes[i].burst_time;
        } else { // 否则将进程放入最小堆中，等待执行
            pq.push(processes[i]);
            // 记录等待时间
            processes[i].waiting_time = current_time - processes[i].arrival_time;
            total_waiting_time += processes[i].waiting_time;
        }
        // 循环执行最小堆中的进程
        while (!pq.empty()) {
            Process p = pq.top();
            pq.pop();
            // 执行时间为当前时间加上进程的执行时间
            current_time += p.burst_time;
            // 记录周转时间
            p.turnaround_time = current_time - p.arrival_time;
            total_turnaround_time += p.turnaround_time;
        }
    }
    // 计算平均等待时间和平均周转时间
    double avg_waiting_time = static_cast<double>(total_waiting_time) / processes.size();
    double avg_turnaround_time = static_cast<double>(total_turnaround_time) / processes.size();
    // 输出结果
    cout << "SJF调度结果：" << endl;
    cout << "平均等待时间：" << avg_waiting_time << endl;
    cout << "平均周转时间：" << avg_turnaround_time << endl;
}

int main() {
    // 测试数据
    vector<Process> processes = {
        {1, 0, 6},
        {2, 1, 8},
        {3, 2, 7},
        {4, 3, 3},
        {5, 4, 4}
    };
    // 执行短作业优先调度算法
    sjf_schedule(processes);
    return 0;
}

代码解释

定义进程结构体
- id: 进程编号
- arrival_time: 到达时间
- burst_time: 执行时间
- waiting_time: 等待时间
- turnaround_time: 周转时间
自定义比较函数
- operator<: 按执行时间进行排序，执行时间短的进程优先级高。
实现短作业优先(SJF)调度算法
- 按到达时间对进程进行排序。
- 使用最小堆 priority_queue 对进程进行排序，按执行时间排序。
- 循环执行进程：
  - 如果当前时间小于等于进程到达时间，直接执行进程。
  - 否则将进程放入最小堆中等待执行。
  - 循环执行最小堆中的进程，直到最小堆为空。
计算平均等待时间和平均周转时间
- 计算所有进程的等待时间总和，除以进程数量得到平均等待时间。
- 计算所有进程的周转时间总和，除以进程数量得到平均周转时间。
输出结果
- 输出 SJF 调度结果、平均等待时间和平均周转时间。

总结

本文介绍了使用 C++ 实现短作业优先 (SJF) 调度算法的方法，通过定义进程结构体、使用自定义比较函数进行排序、使用最小堆进行调度以及计算平均等待时间和平均周转时间，可以实现简单的 SJF 调度算法。