C++实现短进程优先(SJF)调度算法(附完整代码)

C++实现短进程优先(SJF)调度算法

短进程优先（Shortest Job First，SJF）是一种常用的CPU调度算法，它优先选择服务时间最短的进程执行。本文将介绍SJF算法的原理，并提供使用C++实现的完整代码示例。

代码实现

下面是完整的C++代码，实现了短进程优先（SJF）调度算法：

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

using namespace std;

// 进程控制块
struct ProcessControlBlock {
    int process_id;
    int service_time;
    int remaining_time;
    int arrival_time;
};

// 自定义比较函数
struct CompareByServiceTimeAndArrivalTime {
    bool operator()(const ProcessControlBlock& a, const ProcessControlBlock& b) {
        if (a.service_time == b.service_time) {
            return a.arrival_time > b.arrival_time;
        }
        return a.service_time > b.service_time;
    }
};

// 短进程优先调度算法函数
void sjfScheduling(vector<ProcessControlBlock>& processes) {
    priority_queue<ProcessControlBlock, vector<ProcessControlBlock>, CompareByServiceTimeAndArrivalTime> ready_queue;

    int current_time = 0;
    while (!processes.empty()) {
        // 将到达时间小于等于当前时间的进程加入就绪队列
        for (auto& process : processes) {
            if (process.arrival_time <= current_time) {
                ready_queue.push(process);
            }
        }

        // 选择服务时间最短的进程执行
        ProcessControlBlock current_process = ready_queue.top();
        ready_queue.pop();

        current_time += current_process.remaining_time;
        cout << 'Process ' << current_process.process_id << ' is scheduled and completed at time ' << current_time << endl;

        // 从进程列表中移除已完成的进程
        processes.erase(remove_if(processes.begin(), processes.end(), [&](const ProcessControlBlock& process) {
            return process.process_id == current_process.process_id;
        }), processes.end());
    }
}

int main() {
    vector<ProcessControlBlock> processes = {
        {1, 10, 10, 0},
        {2, 4, 4, 2},
        {3, 6, 6, 3},
        {4, 2, 2, 4}
    };

    sjfScheduling(processes);

    return 0;
}

代码解释

进程控制块（ProcessControlBlock）: 定义了一个结构体，包含进程ID（process_id）、服务时间（service_time）、剩余时间（remaining_time）和到达时间（arrival_time）等属性。
自定义比较函数（CompareByServiceTimeAndArrivalTime）: 定义了一个结构体，用于自定义优先队列的比较方式。
- 如果两个进程的服务时间相同，则按照到达时间排序，先到达的进程优先级更高；
- 否则，按照服务时间排序，服务时间短的进程优先级更高。
sjfScheduling 函数: 实现了短进程优先调度算法。
- 使用优先队列（priority_queue）存储就绪队列，并使用自定义的比较函数对象 CompareByServiceTimeAndArrivalTime 作为第三个模板参数。
- 在每次循环中，将到达时间小于等于当前时间的进程加入就绪队列。
- 从就绪队列中取出服务时间最短的进程执行，并更新当前时间。
- 从进程列表中移除已完成的进程。
main 函数: 创建了一个包含四个进程的进程列表，并调用 sjfScheduling 函数进行短进程优先调度。

输出结果

运行上述代码，将输出如下的调度结果：

Process 2 is scheduled and completed at time 4
Process 4 is scheduled and completed at time 6
Process 3 is scheduled and completed at time 12
Process 1 is scheduled and completed at time 22

总结

通过短进程优先（SJF）调度算法，服务时间较短的进程会被优先调度和执行。这样可以最大程度地减少平均等待时间，提高系统的响应性和效率。

注意： SJF算法在现实系统中难以实现，因为它需要预先知道进程的服务时间。