进程调度算法实现及比较：FCFS、SJF、HRRN、SP
本次设计主要涉及进程调度算法，包括先来先服务算法（FCFS）、短作业优先算法（SJF）、高响应比优先算法（HRRN）和静态优先权调度算法（SP），以及比较各算法的平均周转时间。通过本次设计，我对进程调度算法的原理和实现有了更深入的理解。
在实现算法的过程中，我掌握了排序函数的使用方法以及结构体的定义和初始化。在FCFS算法中，按照进程的到达时间从早到晚排序，依次执行进程。在SJF算法中，按照进程的到达时间从早到晚排序，每次选择运行时间最短的进程。在HRRN算法中，按照进程的到达时间从早到晚排序，每次选择响应比最高的进程。在SP算法中，按照进程的到达时间从早到晚排序，每次选择优先级最低的进程。
我认为设计中比较出色的部分是比较各算法平均周转时间的实现。通过将各个算法的平均周转时间进行比较，可以更直观地了解不同算法的性能差异。
未来可以考虑对设计进行以下改进和展望：
- 实现更复杂的进程调度算法，例如多级反馈队列调度算法等。
- 加入图形界面，使程序更易于使用。
- 将算法的实现与实际操作系统结合起来，进行更深入的测试和分析。
#include
using namespace std;
//函数声明 int Turn(); int Menu(); int Select(); int Input(); int FCFS(int n, bool m); int SJF(int n, bool m); int HRRN(int n, bool m); int SP(int n, bool m); void CompareACT(int n); int StateShow(int i, int flag);
//初始化PCB struct Node { string name; //进程名 int priority; // 优先级 double arrivetime; //进程到达时间 double begintime; //进程开始执行时间 double waittime; //进程等待时间 double runtime; //需要运行时间 double finishtime; //进程结束时的时间 double cyclyingtime;//进程周转时间 double RR;//当前进程的相应比 bool state; //当前进程状态 未执行false 已经执行 = true }P[maxn]; Node rem[maxn]; //功能5中会用
//主函数 int main() { Turn(); return 0; }
//循环过程 int Turn() { Menu(); int n = Select(); if (n == 6) { exit(257); } else { int count = Input(); //统计进程数 printf("\n提示："); switch (n) { case 1: printf("当前使用的算法是’先来先服务算法’\n\n"); FCFS(count, true); break; case 2: printf("当前使用的算法是’短进程优先算法’\n\n"); SJF(count, true); break; case 3: printf("当前使用的算法是’高响应比优先算法’\n\n"); HRRN(count, true); break; case 4: printf("当前使用的算法是’静态优先权算法’\n\n"); SP(count, true); break; case 5: printf("比较各算法的平均周转时间\n\n"); CompareACT(count); break; } } }
//选择菜单 int Select() { int n; while (1) { cin >> n; if (n < 1 || n>6) cout << "输入有误请重新输入!!!" << endl; else { system("cls"); break; } } return n; }
//菜单：选择算法 int Menu() { printf("\n\n\n"); printf("\t\t\t请选择算法（1-5）*** \n\n"); printf("\t\t\t\t1-- 先来先服务算法（FCFS）\n\n"); printf("\t\t\t\t2-- 短作业优先算法（SJF）\n\n"); printf("\t\t\t\t3-- 高相应比优先调度算法（HRRN）\n\n"); printf("\t\t\t\t4-- 静态优先权调度算法（SP）\n\n"); printf("\t\t\t\t5-- 比较各个算法的平均周转时间\n\n"); printf("\t\t\t\t6-- 退出程序！~\n\n"); cout << " 请输入选择的序号： "; }
//输入内容 int Input() { int progress_num; //进程总数 cout << "请输入进程总数："; cin >> progress_num; cout << "请选择输入方式：手动输入（H/h），文件输入（F/f）: " << endl;
string str; cin >> str;
if (str == "H" || str == "h") {
cout << "请手动输入：" << endl;
cout << "进程名 优先级 到达时间 需要运行时间 " << endl;
cout << "------------------------------------------------------" << endl;
for (int i = 1;i <= progress_num;++i) { //注意从1开始
cin >> P[i].name;
rem[i].name = P[i].name;
cin >> P[i].priority;
rem[i].priority = P[i].priority;
cin >> P[i].arrivetime;
rem[i].arrivetime = P[i].arrivetime;
cin >> P[i].runtime;
rem[i].runtime = P[i].runtime;
P[i].state = false; //输入的进程默认都是就绪状态
rem[i].state = false;
}
}
if (str == "F" || str == "f") { //文件读写
freopen("in.txt", "r", stdin);
for (int i = 1;i <= progress_num;++i) { //注意从1开始
cin >> P[i].name;
rem[i].name = P[i].name;
cin >> P[i].priority;
rem[i].priority = P[i].priority;
cin >> P[i].arrivetime;
rem[i].arrivetime = P[i].arrivetime;
cin >> P[i].runtime;
rem[i].runtime = P[i].runtime;
P[i].state = false; //输入的进程默认都是就绪状态
rem[i].state = false;
}
fclose(stdin);
cout << "\n\n";
cout << "自动输入完毕！" << endl;
}
return progress_num;
}
//计算各个属性 int Calculate(int i, int flag) { if (i == 1 || P[i].arrivetime >= P[flag].finishtime) { //如果是第一个进程或者此进程到达之前前一个进程已经执行完毕 P[i].waittime = 0; //那么等待时间为0 P[i].begintime = P[i].arrivetime; //当前进程的开始时间 = 到达时间 P[i].finishtime = P[i].begintime + P[i].runtime; //进程的完成时间=到达时间+运行时间 } else { P[i].waittime = P[flag].finishtime - P[i].arrivetime; //否则，等待时间=上一个进程的完成时间-当前进程的到达时间 P[i].begintime = P[flag].finishtime; //当前进程开始时间 = 上一个进程的完成时间 P[i].finishtime = P[i].begintime + P[i].runtime;//完成时间=开始时间+当前进程运行时间 } P[i].cyclyingtime = P[i].finishtime - P[i].arrivetime; //计算周转时间 P[i].RR = (double)(P[i].waittime + P[i].runtime) / P[i].runtime; //计算响应比 }
//输出内容 int Output(int i, int flag) //传入当前进程号,和上一步执行的进程号 { Calculate(i, flag); cout << "进程名 到达时间 等待时间 开始时间 运行时间 完成时间 优先权 周转时间 带权周转时间 " << endl; cout << "-------------------------------------------------------------------------------------------" << endl; cout << " " << P[i].name; printf("%10.2f", P[i].arrivetime); printf("%10.2f", P[i].waittime); printf("%10.2f", P[i].begintime); printf("%10.2f", P[i].runtime); printf("%10.2f", P[i].finishtime); printf("%10.d", P[i].priority); printf("%10.2f", P[i].cyclyingtime); printf("%10.2f/%.2f\n", P[i].cyclyingtime, P[i].runtime);
//StateShow(i, flag);
cout << endl;
}
// 显示进程状态：就绪和执行 int StateShow(int i, int flag) { string str; cout << "是否需要查看此进程在某时刻的状态？是（Y）y || 否（N）n："; cin >> str;
if (str == "n" || str == "N") {
}
else if (str == "y" || str == "Y") {
while (true) {
Calculate(i, flag);
double t;
cout << "请输入想要查看状态的时间：";
cin >> t;
if (t < P[i].begintime) {
cout << P[i].name+"处于就绪状态";
cout << endl;
}
else if (t >= P[i].begintime && t < P[i].finishtime) {
cout << P[i].name + "处于执行状态";
cout << endl;
}
cout << "还需要查看其他时刻的状态吗？继续（C）c || 结束（B）b";
string str01;
cin >> str01;
if (str01 == "b" || str01 == "B") {
break;
}
}
}
}
void ReturnMenu() //返回菜单选项 { cout << "演示结束！" << endl; cout << "按R（r）返回菜单||按E（e）退出程序" << endl; string ss; cin >> ss; if (ss == "R" || ss == "r") { system("cls"); Turn(); } else { exit(257); } }
//计算平均周转时间 void ACTime(int n, bool m) { double sumcyclyingtime = 0; double avercyclyingtime; for (int i = 1;i <= n;++i) { sumcyclyingtime += P[i].cyclyingtime; } avercyclyingtime = sumcyclyingtime / n; printf("平均周转时间 = %.2f\n", avercyclyingtime);
if (m == 1)
ReturnMenu();
}
bool FCFS_cmp(Node a, Node b) { return a.arrivetime < b.arrivetime; //按到达时间从早到晚 } int FCFS(int n, bool m) { sort(P + 1, P + n + 1, FCFS_cmp); //将进程根据arrivetime排序 for (int i = 1;i <= n;++i) { if (m == 1) Output(i, i - 1); else Calculate(i, i - 1); } ACTime(n, m);
}
bool SJF_cmp(Node a, Node b)
{
if (a.arrivetime == b.arrivetime) //如果同时到达
return a.runtime < b.runtime; //按作业由小到大排序
return a.arrivetime < b.arrivetime; //否则按到达时间排序
}
int SJF(int n, bool m)
{
int flag = 0;
int T = n;
while (T--) {
int pre = flag; //pre:先前执行的进程
sort(P + 1, P + n + 1, SJF_cmp);
double minx = INF; //用来找运行时间最短的进程
for (int i = 1;i <= n;++i) {
if (P[i].state == true)
continue; //如果这个进程已经执行过，那么忽略
if (i == 1) {
flag = 1;
break;
}
if (P[i].arrivetime <= P[pre].finishtime) { //如果已经到达
if (P[i].runtime < minx) {
minx = P[i].runtime;
flag = i;
}
}
}
if (m == 1) Output(flag, pre);
else Calculate(flag, pre);
P[flag].state = true;
}
ACTime(n, m);
}
bool HRRN_cmp(Node a, Node b) { if (a.arrivetime == b.arrivetime) return a.RR > b.RR; //返回响应比高的 响应比Rp = （等待时间+要求服务时间）/ 要求服务时间 = 1 +（等待时间 / 要求服务时间） return a.arrivetime < b.arrivetime; }
int HRRN(int n, bool m) { int flag = 0; int T = n; while (T--) { int pre = flag; sort(P + 1, P + n + 1, FCFS_cmp); double maxx = 0.0; //用来找最大响应比的进程 for (int i = 1;i <= n;++i) { if (P[i].state == true) continue; if (i == 1) { flag = 1; break; } if (P[i].arrivetime <= P[pre].finishtime) { Calculate(i, pre); //计算已经到达的响应比 if (m == 1) printf("P[%d]的响应比为：%.2lf\n", i, P[i].RR); if (P[i].RR > maxx) { maxx = P[i].RR; flag = i; } } } if (m == 1) Output(flag, pre); else Calculate(flag, pre); P[flag].state = true; } ACTime(n, m); }
bool SP_cmp(Node a, Node b) { if (a.arrivetime == b.arrivetime) return a.priority < b.priority; return a.arrivetime < b.arrivetime; } int SP(int n, bool m) { int flag = 0; int T = n; while (T--) { int pre = flag; sort(P + 1, P + n + 1, SJF_cmp); double minx = INF; //用来找优先权最小的进程 for (int i = 1;i <= n;++i) { if (P[i].state == true) continue; if (i == 1) { flag = 1; break; } if (P[i].arrivetime <= P[pre].finishtime) {
if (P[i].priority < minx) {
minx = P[i].priority;
flag = i;
}
}
}
if (m == 1)
Output(flag, pre);
else
Calculate(flag, pre);
P[flag].state = true;
}
ACTime(n, m);
}
//因为功能5要比较各个进程的周转时间，然而每运行一次某个算法 //进程的各属性值会改变，因此先保存一下输入的原内容，每次执行 //下一个算法时进行更新 void Update(int n) { for (int i = 1;i <= n;++i) { P[i].name = rem[i].name; P[i].priority = rem[i].priority; P[i].arrivetime = rem[i].arrivetime; P[i].runtime = rem[i].runtime; P[i].state = false; } }
//比较各个算法的平均周转时间 void CompareACT(int n) { cout << "FCFS : "; FCFS(n, false); cout << endl; Update(n);
cout << "SJF : ";
SJF(n, false);
cout << endl;
Update(n);
cout << "HRRN : ";
HRRN(n, false);
cout << endl;
Update(n);
cout << "SP : ";
SP(n, false);
cout << endl;
Update(n);
ReturnMenu();
}
原文地址: https://www.cveoy.top/t/topic/lQQq 著作权归作者所有。请勿转载和采集!