操作系统————FCFS(先来先服务)，优先级调度，SJF（短作业优先调度），RR（时间片轮转调度）四大算法的c++代码实现
在正文开始之前，希望读者对下面六个指标的计算公式做到熟练应用，因为整个代码的设计都将围绕这六个公式展开
🍕🍕🍕指标1：周转时间=完成时间-到达时间
🍕🍕🍕指标2：带权周转时间=周转时间/运行时间
🍕🍕🍕指标3：等待时间=周转时间-运行时间
🍕🍕🍕指标4：平均周转时间=周转时间总和/进程总数
🍕🍕🍕指标5：平均带权周转时间=带权周转时间总和/进程总数
🍕🍕🍕指标6：平均等待时间=等待时间总和/进程总数
特别注意运行时间和到达时间是已知的，其他都是需要计算的
另外我们给出的设计思路只是算法整体的设计思路，具体的每一步实现原理小编会在代码注释里标注，希望读者能仔细阅读代码注释
🍬🍬🍬算法1：FCFS（先来先服务算法）
🍕🍕🍕代码设计思路：
关键在于comparearrival函数，这个函数把进程按照到达时间的先后顺序排列，这也是FCFS的关键，然后我们采用结构体把进程封装起来，再使用一个vector容器存放所有进程，❤️❤️❤️要注意等待时间=开始时间-到达时间或者等待时间=周转时间-运行时间，但如果用第二个公式需要先计算周转时间，注意编程时候的顺序，FCFS函数计算进程的所有的时间，最后打印出结果，具体计算方法见代码注释
还要注意传参时要和结构体定义成员的顺序相一致，否则结果会出问题！！！
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct process {int id;//进程idint arrival;//到达时间int burst;//执行时间int start;//开始时间int finish;//完成时间int waiting;//等待时间int turnaround;//周转时间};
bool comparearrival(process a, process b) {return a.arrival < b.arrival;//按照到达时间排序
}
void FCFS(vector<process>& processes) {int currenttime = 0;sort(processes.begin(), processes.end(), comparearrival);for (int i = 0; i < processes.size(); ++i) {//遍历所有进程process& p = processes[i];if (currenttime < p.arrival) {currenttime = p.arrival;//如果没有到达进程的到达时间，直接跳转到进程到达的时间}p.start = currenttime;//进程开始时间就是当前时间p.finish = p.start + p.burst;//完成时间等于开始时间+运行时间p.waiting = p.start - p.arrival;//等待时间=开始时间-到达时间或者等待时间=周转时间-运行时间但如果用第二个公式需要先计算周转时间，即下一行代码要前面p.turnaround = p.finish - p.arrival;//周转时间=完成时间-到达时间currenttime = p.finish;//更新时间点为进程完成时间}}
void printresult(const vector<process>& processes) {//打印结果cout << "进程id\t到达时间\t执行时间\t开始时间\t完成时间\t等待时间\t周转时间" << endl;for (const auto& p : processes) {cout << p.id << "\t"<< p.arrival << "\t\t"<< p.burst << "\t\t"<< p.start << "\t\t"<< p.finish << "\t\t"<< p.waiting << "\t\t"<< p.turnaround << endl;}double totalturnaroundtime = 0;double totalwaitingtime = 0;for (const auto& process : processes) {totalturnaroundtime += process.turnaround;//计算所有进程的周转时间总和totalwaitingtime += process.waiting;//计算所有进程的等待时间总和}int n = processes.size();cout << "平均周转时间:" << totalturnaroundtime / n << endl;cout << "平均等待时间" << totalwaitingtime / n << endl;
}
int main() {vector<process>processes = {{1,0,6},{2,1,2},{3,0,1},{4,3,5},{5,3,8}//按照进程id,到达时间，执行时间传入参数};FCFS(processes);printresult(processes);return 0;
}运行结果：
🍬🍬🍬算法2：优先级调度算法
🍕🍕🍕代码设计思路：
核心还是comprearrival函数，FCFS是按到达时间排序的，这里的比较函数我们按照优先级的顺序，优先级数值大的优先级高，我们按照优先级的顺序降序排列，这样就能保证优先级高的进程先执行，这样就不是到达时间优先，而是按照优先级调度
这里注意主函数传参时要传入优先级！！！
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct process {int id;int arrival;int burst;int priorlevel;//进程优先级int start;int finish;int waiting;int turnaround;};
bool comparearrival(process a, process b) {return a.priorlevel > b.priorlevel;//核心部分
}
void FCFS(vector<process>& processes) {int currenttime = 0;sort(processes.begin(), processes.end(), comparearrival);for (int i = 0; i < processes.size(); ++i) {process& p = processes[i];if (currenttime < p.arrival) {currenttime = p.arrival;}p.start = currenttime;//这里的计算方法同FCFS相同p.finish = p.start + p.burst;p.waiting = p.start - p.arrival;p.turnaround = p.finish - p.arrival;currenttime = p.finish;}}
void printresult(const vector<process>& processes) {cout << "进程id\t进程优先级\t到达时间\t执行时间\t开始时间\t完成时间\t等待时间\t周转时间" << endl;for (const auto& p : processes) {cout << p.id << "\t"<< p.priorlevel << "\t\t"<< p.arrival << "\t\t"<< p.burst << "\t\t"<< p.start << "\t\t"<< p.finish << "\t\t"<< p.waiting << "\t\t"<< p.turnaround << endl;}double totalturnaroundtime = 0;double totalwaitingtime = 0;for (const auto& process : processes) {totalturnaroundtime += process.turnaround;totalwaitingtime += process.waiting;}int n = processes.size();cout << "平均周转时间:" << totalturnaroundtime / n << endl;cout << "平均等待时间" << totalwaitingtime / n << endl;
}
int main() {vector<process>processes = {{1,0,6,4},{2,1,2,3},{3,0,1,2},{4,3,5,1},{5,3,8,5}};FCFS(processes);printresult(processes);return 0;
}运行结果：
🍬🍬🍬算法3：SJF（短作业优先调度算法）
🍕🍕🍕代码设计思路：
SJF算法与前两种算法不同的是会发生抢占，我们在结构体中设置一个bool型标记，标记进程状态，这样被抢占的进程还会被重新调度。然后每次找到当前到达且没有执行的最短作业，周转时间等的计算方法同前两种算法相一致，比较函数要同时考虑到达时间先后和执行时间长短
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;// 定义进程结构体
struct Process {int pid; // 进程IDint arrivalTime; // 到达时间int burstTime; // 执行时间int startTime; // 开始时间int completionTime; // 完成时间int waitingTime; // 等待时间int turnaroundTime; // 周转时间bool isExecuted; // 标记进程是否已执行
};// 比较函数，用于按照到达时间和执行时间排序
bool compare(Process a, Process b) {if (a.arrivalTime != b.arrivalTime) {return a.arrivalTime < b.arrivalTime;}return a.burstTime < b.burstTime;
}// 计算进程的各种时间
void calculateTimes(vector<Process>& processes) {int currentTime = 0;int n = processes.size();// 初始化所有进程的执行标记为falsefor (auto& process : processes) {process.isExecuted = false;}while (true) {int shortestProcessIndex = -1;//最短进程初始化为-1int shortestBurstTime = numeric_limits<int>::max();// 找到当前到达且未执行的最短作业for (int i = 0; i < n; ++i) {if (!processes[i].isExecuted && processes[i].arrivalTime <= currentTime) {if (processes[i].burstTime < shortestBurstTime) {shortestBurstTime = processes[i].burstTime;//更新最短执行时间shortestProcessIndex = i;/找到最短的进程}}}if (shortestProcessIndex == -1) {// 没有符合条件的进程，结束循环break;}// 计算开始时间processes[shortestProcessIndex].startTime = currentTime;// 计算完成时间processes[shortestProcessIndex].completionTime = currentTime + processes[shortestProcessIndex].burstTime;// 计算等待时间processes[shortestProcessIndex].waitingTime = processes[shortestProcessIndex].startTime - processes[shortestProcessIndex].arrivalTime;// 计算周转时间processes[shortestProcessIndex].turnaroundTime = processes[shortestProcessIndex].completionTime - processes[shortestProcessIndex].arrivalTime;// 更新当前时间currentTime = processes[shortestProcessIndex].completionTime;// 标记该进程已执行processes[shortestProcessIndex].isExecuted = true;}
}// 计算平均等待时间和平均周转时间
void calculateAverageTimes(const vector<Process>& processes) {int n = processes.size();int totalWaitingTime = 0;int totalTurnaroundTime = 0;for (const auto& process : processes) {totalWaitingTime += process.waitingTime;totalTurnaroundTime += process.turnaroundTime;}double averageWaitingTime = static_cast<double>(totalWaitingTime) / n;double averageTurnaroundTime = static_cast<double>(totalTurnaroundTime) / n;cout << "平均等待时间: " << averageWaitingTime << endl;cout << "平均周转时间: " << averageTurnaroundTime << endl;
}// 输出进程信息
void printProcesses(const vector<Process>& processes) {cout << "进程ID\t到达时间\t执行时间\t开始时间\t完成时间\t等待时间\t周转时间\t进程状态\n";for (const auto& process : processes) {cout << process.pid << "\t\t" << process.arrivalTime << "\t\t" << process.burstTime << "\t\t" << process.startTime << "\t\t" << process.completionTime << "\t\t" << process.waitingTime << "\t\t" << process.turnaroundTime <<"\t\t"<<process.isExecuted << endl;}
}int main() {vector<Process> processes = {{1, 0, 6, 0, 0, 0, 0, false},{2, 1, 2, 0, 0, 0, 0, false},//传参时注意传入标记{3, 1, 1, 0, 0, 0, 0, false},{4, 3, 5, 0, 0, 0, 0, false},{5, 3, 8, 0, 0, 0, 0, false},{6, 0, 1, 0, 0, 0, 0, false},};calculateTimes(processes);printProcesses(processes);calculateAverageTimes(processes);return 0;
}
运行结果：
🍬🍬🍬算法4：RR（时间片轮转调度算法）
🍕🍕🍕代码设计思路：
RR算法较为灵活，时间片的大小我们可以自己指定，比较函数按照进程到达时间排序，我们给每个进程记录剩余执行时间和执行标记，roundRobin函数部分我们分两种情况讨论，第一种是剩余时间大于一个时间片，此时我们就不能计算完成时间，让时间线继续往后走，第二种就是剩余执行时间小于一个时间片，此时进程就可以执行完毕，我们也可以计算完成时间，周转时间等
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 定义进程结构体
struct Process {int pid; // 进程IDint arrivalTime; // 到达时间int burstTime; // 执行时间int startTime; // 开始时间int completionTime; // 完成时间int waitingTime; // 等待时间int turnaroundTime; // 周转时间bool isExecuted; // 标记进程是否已执行
};// 比较函数，用于按照到达时间排序
bool compare(Process a, Process b) {//比较函数return a.arrivalTime < b.arrivalTime;
}void roundRobin(vector<Process>&processes, int timeQuantum) {int currentTime = 0;int n = processes.size();int remainingTime[10];// 初始化剩余执行时间和执行标记for (int i = 0; i < n; ++i) {remainingTime[i] = processes[i].burstTime;processes[i].isExecuted = false;}while (true) {bool allFinished = true;for (int i = 0; i < n; ++i) {if (remainingTime[i] > 0) {allFinished = false;if (remainingTime[i] > timeQuantum) {//剩余时间大于一个时间片if (!processes[i].isExecuted) {processes[i].startTime = currentTime;processes[i].isExecuted = true;}currentTime += timeQuantum;//时间过去了一个时间片remainingTime[i] -= timeQuantum;//运行了一个时间片，剩余时间减少相应的时间}else {//剩余时间小于一个时间片就可以直接运行完然后计算完成时间周转时间等if (!processes[i].isExecuted) {processes[i].startTime = currentTime;processes[i].isExecuted = true;}currentTime += remainingTime[i];processes[i].completionTime = currentTime;processes[i].turnaroundTime = processes[i].completionTime - processes[i].arrivalTime;processes[i].waitingTime = processes[i].turnaroundTime - processes[i].burstTime;//先计算周转时间通过周转时间-运行时间计算等待时间remainingTime[i] = 0;}}}if (allFinished) {break;}}
}
// 计算平均等待时间和平均周转时间
void calculateAverageTimes(const vector<Process>& processes) {int n = processes.size();int totalWaitingTime = 0;int totalTurnaroundTime = 0;for (const auto& process : processes) {totalWaitingTime += process.waitingTime;totalTurnaroundTime += process.turnaroundTime;}double averageWaitingTime = static_cast<double>(totalWaitingTime) / n;double averageTurnaroundTime = static_cast<double>(totalTurnaroundTime) / n;cout << "平均等待时间: " << averageWaitingTime << endl;cout << "平均周转时间: " << averageTurnaroundTime << endl;
}// 输出进程信息
void printProcesses(const vector<Process>& processes) {cout << "进程ID\t到达时间\t执行时间\t开始时间\t完成时间\t等待时间\t周转时间\t进程状态\n";for (const auto& process : processes) {cout << process.pid << "\t\t" << process.arrivalTime << "\t\t" << process.burstTime << "\t\t" << process.startTime << "\t\t" << process.completionTime << "\t\t" << process.waitingTime << "\t\t" << process.turnaroundTime<<"\t\t"<<process.isExecuted << endl;}
}int main() {vector<Process> processes = {{1, 0, 3, 0, 0, 0, 0, false},{2, 1, 8, 0, 0, 0, 0, false},{3, 2, 3, 0, 0, 0, 0, false},{4, 3, 6, 0, 0, 0, 0, false},};int timeQuantum = 3; // 时间片大小，这里读者可以自行修改时间片大小sort(processes.begin(), processes.end(), compare);roundRobin(processes, timeQuantum);cout << "时间片大小是：" << timeQuantum << endl;printProcesses(processes);calculateAverageTimes(processes);return 0;
}
运行结果：
