进程调度算法(先来先服务/短作业优先)代码实现

本文主要是介绍进程调度算法(先来先服务/短作业优先)代码实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近在复习408操作系统进程时，决定用代码模拟调度算法来熟悉详细过程!
选择两个好写点的算法进行练习!!!
以下代码使用c++语言。优先队列和队列直接使用STL容器!!!

引入头文件

#include<iostream>
#include<queue>
#include<map>
using namespace std;

数据结构设计

//进程控制块
struct PCB {string ID;//进程IDdouble arrivalTime;//到达处理机时间double remainTime;//剩余服务时间double priority;//优先级(越小优先级越高)//其他信息省略...
};

由于有两个算法,为了减少冗余度。将`公共部分`使用自定义基类`Base`实现。

//调度基础类
class Base {
public:map<string,pair<double,double>>times;//进程ID->[等待时间,运行时间]queue<PCB*>Queue;//普通队列priority_queue<PCB*, vector<PCB*>, cmp>pq;//优先队列double avWait;//平均等待时间double avTurnaround;//平均周转时间double avWeightedTurnaround;//平均带权周转时间Base() {this->avWait = this->avTurnaround = this->avWeightedTurnaround = 0.0;}//输出各进程时间void printTime() {for (map<string, pair<double, double>>::iterator it = times.begin(); it != times.end(); ++it) {printf("进程%s运行了%.3lf秒,等待了%.3lf秒\n", it->first.c_str(), it->second.second, it->second.first);}calculate_time();//计算平均时间printf("平均等待时间为%.3lf秒,平均周转时间%.3lf秒,平均带权周转时间%.3lf秒\n",avWait,avTurnaround,avWeightedTurnaround);}//计算各平均时间void calculate_time() {double sumWait = 0.0, sumTurnaround = 0.0, sumWeightedTurnaround = 0.0;//总等待时间 总周转时间 总带权周转时间for (map<string, pair<double, double>>::iterator it = times.begin(); it != times.end(); ++it) {sumWait += it->second.first;sumTurnaround += it->second.first + it->second.second;sumWeightedTurnaround += (it->second.first + it->second.second) / it->second.second;}avWait = sumWait / times.size();avTurnaround = sumTurnaround / times.size();avWeightedTurnaround = sumWeightedTurnaround / times.size();}
};

先来先服务调度类

解释:
在FCFS构造函数中将进程控制块添加到普通队列Queue中
过程:
①.每次从Queue中取出一个元素
②.如果当前时间小于即将需要运行的进程到达时间，就将当前时间改成下一个需要运行进程到达的时间。
③.times成员时用于记录进程等待时间和运行时间。
④.运行完成后,当前时间+=上一个进程运行的时间

//先来先服务调度类(FCFS)[非抢占式]
class FCFS :private Base {
public:FCFS(PCB* pcbs,int len) {for (int i = 0; i < len; ++i) {Queue.push(pcbs+i);//加入到进程队列}}void run() {double curTime = 0;//当前时间while (!Queue.empty()) {PCB* curRun = Queue.front();//①从队列头部获取进程控制块Queue.pop();//弹出进程控制块if (curTime < curRun->arrivalTime) {//②当前时间比现在需要运行的进程时间小,需要将当前时间改成进程到达时间curTime = curRun->arrivalTime;}times[curRun->ID] = { curTime - curRun->arrivalTime,curRun->remainTime };//③curTime += curRun->remainTime;//④当前时间 += 进程剩余服务时间}}void show() {this->printTime();}
};

测试函数

void fcfs() {cout << "先来先服务算法:" << endl;PCB pcbs[4] = { {"1号",8.0,2.0},{"2号",8.4,1.0},{"3号",8.8,0.5},{"4号",9.0,0.2} };FCFS fcfs(pcbs, 4);fcfs.run();fcfs.show();
}

短作业优先调度类

解释:
将进程的剩余时间作为优先级的比较       (每次调度需要使用剩余时间最小的)
过程:
①.while循坏的作用时只要还有进程没运行完,就继续调度
②.首先将到达时间比当前时间小的进程的PCB放入优先队列中。
③.如果优先队列为空就
             如果后续没有进程加入->调度结束
             如果后续还有进程加入->将当前时间改为下一个需要运行的进程到达时间
④.向后遍历(查看后面是否有多个同时到达的进程)
⑤.从优先队列取出需要服务时间最短的进程
⑥.记录等待时间和运行时间

//短作业优先调度类(SJF)[非抢占式]
class SJF :private Base {
public:SJF(PCB* pcbs, int len) {run(pcbs,len);}void run(PCB* pcbs, int len) {double curTime = 0.0;//当前时间int i = 0;//pcbs的下标while (!pq.empty() || i < len) {//①当优先队列不为空或还有进程没运行//每个进程运行期间可能有其他进程加入//因此需要将运行期间加入的进程放入优先队列中for (; i < len; ++i) {if (pcbs[i].arrivalTime <= curTime) {//②进程到达时间小于等于当前时间pq.push(&pcbs[i]);}else {break;}}//如果当前优先队列中没有进程//说明在当前时间运行完了已到达的进程//但是可能后续还有进程//当前时间就要跳到后续进程的到达时间if (pq.empty()) {//③if (i == len) {//说明运行结束,可以退出了break;}else {//后续还有进程到来curTime = pcbs[i].arrivalTime;}}//可能同时有多个进程到来//多以需要便利加入for (; i < len; ++i) {//④if (curTime == pcbs[i].arrivalTime) {pq.push(&pcbs[i]);}else {break;}}PCB* curRun = pq.top();//⑤pq.pop();times[curRun->ID] = { curTime - curRun->arrivalTime,curRun->remainTime };//⑥curTime += curRun->remainTime;}}void show() {this->printTime();}
};

测试函数

void sjf() {cout << "短作业优先算法:" << endl;
/*由于在设计优先队列对比的优先级是根据pcb中的优先级对比的,但是这里需要根据时间来对比优先级,将剩余时间直接赋值给优先级用于对比
*/PCB pcbs[4] = { {"1号",8.0,2.0,2.0},{"2号",8.4,1.0,1.0},{"3号",8.8,0.5,0.5},{"4号",9.0,0.2,0.2} };SJF sjf(pcbs,4);sjf.show();
}

主函数

int main() {fcfs();sjf();
}

运行结果

先来先服务算法:
进程1号运行了2.000秒,等待了0.000秒
进程2号运行了1.000秒,等待了1.600秒
进程3号运行了0.500秒,等待了2.200秒
进程4号运行了0.200秒,等待了2.500秒
平均等待时间为1.575秒,平均周转时间2.500秒,平均带权周转时间5.625秒
短作业优先算法:
进程1号运行了2.000秒,等待了0.000秒
进程2号运行了1.000秒,等待了2.300秒
进程3号运行了0.500秒,等待了1.400秒
进程4号运行了0.200秒,等待了1.000秒
平均等待时间为1.175秒,平均周转时间2.100秒,平均带权周转时间3.525秒

测试数据来自王道考研操作系统2024版64页或2025版71页!!!