实验环境:VS2010 VC++ 实验题目: 模拟短作业优先算法、时间片轮转算法(RR)和优先数算法的执行情况,并 动态画出其进程执行的 Gantt 图,计算以上算法的每个进程的响应时间和周转时间。
/* 模拟短作业优先算法、时间片轮转算法(RR)和优先数算法的执行情况,并动态画出其进程执行的Gantt图,计算以上算法的每个进程的响应时间和周转时间。 */ #include<iostream> using namespace std; const int MAX = 100; //定义进程结构体 struct process{ char p_name[10]; //进程名 int reach_time; //到达时间 int run_time; //剩余运行时间 int priority; //优先级 int response_time; //响应时间 int turnaround_time;//周转时间 }; struct gantt{ char p_name[10]; //进程名 int run_time; //运行时间 }; process p[MAX]; //进程数组 gantt g[MAX]; //Gantt图数组 int p_Num; //实际进程数 char FileName[20]; //进程序列文件名 int MaxReachTime; //最大到达时间 int BeReached[MAX]; //到达进程数组 int reach_Num; //到达进程数 //读文件 int ReadFile() { FILE *fp; int i; char c; cout << "请输入要打开的文本文件名(注意:包括路径名和后缀名): "; cin >> FileName; if((fp = fopen(FileName,"r")) == NULL) { cout << "错误:文件 " << FileName << " 打不开,请检查文件名和路径!!" << endl; exit(0); } else { c = fgetc(fp); while(c == ' ' || c == 10 || c == 9) //过滤空格、换行和TAB字符 { c = fgetc(fp); } if(c == EOF) { printf("错误:文件:%s 为空!!\n", FileName); exit(0); } else { fseek(fp, -1, SEEK_CUR); while(!feof(fp)) { fscanf(fp, "%s %d %d %d", p[p_Num].p_name, &p[p_Num].reach_time, &p[p_Num].run_time, &p[p_Num].priority); p_Num++; } //输出所读入的进程数据 cout << endl << "从文件 " << FileName << " 读入的进程数据:" << endl << endl; cout << "进程名 到达时间 运行时间 优先数" << endl; for(i = 0; i < p_Num; i++) { cout << " " << p[i].p_name << " " << p[i].reach_time << " " << p[i].run_time << " " << p[i].priority << endl; } cout << endl << "进程总数:" << p_Num << endl << endl; return 0; } } } //找到所有进程中的最大到达时间 void GetMaxReachTime() { for(int i = 0; i < p_Num; i++) { if(p[i].reach_time > MaxReachTime) MaxReachTime = p[i].reach_time; } } //全部初始化 void Init() { for(int i = 0; i < MAX; i++) { strcpy(p[i].p_name, ""); p[i].reach_time = -1; p[i].run_time = -1; p[i].priority = -1; p[i].response_time = -1; p[i].turnaround_time = -1; strcpy(g[i].p_name, ""); g[i].run_time = 0; BeReached[i] = -1; } p_Num = 0; MaxReachTime = 0; reach_Num = 0; ReadFile(); GetMaxReachTime(); } //检查是否所有进程都运行结束 bool CheckFinish() { for(int i = 0; i < p_Num; i++) { if(p[i].run_time > 0) return false; } return true; } //显示Gantt图 void ShowGantt() { int i = 0; cout << "Gantt图如下所示:" << endl << endl; cout << "进程名 运行时间" << endl; while(true) { if(g[i].run_time == 0) break; cout << " " << g[i].p_name << " " << g[i].run_time << endl; i++; } cout << endl; } //显示每个进程的响应时间和周转时间 void ShowTime() { int i = 0; cout << "进程名 响应时间 周转时间" << endl; while(i < p_Num) { cout << " " << p[i].p_name << " " << p[i].response_time << " " << p[i].turnaround_time << endl; i++; } cout << endl; } //更新到达进程数组和到达进程数 void UpdateReachArray(int t) { if(t <= MaxReachTime) { for(int i = 0; i < p_Num; i++) { if(p[i].reach_time - t == 0) { BeReached[reach_Num++] = i; } } } } //短作业优先算法,抢占调度 void SPN() { int t = 0, i, j = -1; int ilMin; //上次最短进程下标 int iMin = -1; //当前最短进程下标 int iMinRuntime; //当前最短运行时间 while(true) { UpdateReachArray(t); //更新到达进程数组 ilMin = iMin; iMinRuntime = 100000; for(i=0; i<reach_Num; i++) //找到剩余运行时间最短的进程 { if(p[BeReached[i]].run_time > 0 && p[BeReached[i]].run_time < iMinRuntime) { iMin = BeReached[i]; iMinRuntime = p[BeReached[i]].run_time; } } if(ilMin != iMin) //若当前运行进程和上个运行进程不是同一个,则j++ { j++; strcpy(g[j].p_name, p[iMin].p_name); } g[j].run_time += 1; p[iMin].run_time -= 1; if(p[iMin].response_time == -1) p[iMin].response_time = t - p[iMin].reach_time; //记录该进程响应时间 if(p[iMin].run_time == 0) p[iMin].turnaround_time = t + 1 - p[iMin].reach_time; //记录该进程周转时间 if(CheckFinish()) break; t++; //时间加1 } ShowGantt(); ShowTime(); } //时间片轮转法算法,抢占调度,BTime为时间片大小的参数 void RR(int BTime) { int t = 0, j = 0, k = 0; int FBTime = 0; //已用时间片长度 while(true) { UpdateReachArray(t); if(FBTime == BTime || p[BeReached[k]].run_time == 0) //时间片用完或当前运行进程已结束 { j++; k++; FBTime = 0; //已用时间片清零 } if(k == reach_Num) k = 0; //已运行到队列最后进程之后,从队列最前重新运行 while(p[BeReached[k]].run_time == 0) //如果该进程已运行结束,跳到下一个进程 { k++; if(k == reach_Num) k = 0; } strcpy(g[j].p_name, p[BeReached[k]].p_name); g[j].run_time += 1; p[BeReached[k]].run_time -= 1; if(p[BeReached[k]].response_time == -1) p[BeReached[k]].response_time = t - p[BeReached[k]].reach_time; //记录该进程响应时间 if(p[BeReached[k]].run_time == 0) p[BeReached[k]].turnaround_time = t + 1 - p[BeReached[k]].reach_time; //记录该进程周转时间 if(CheckFinish()) break; t++; //时间加1 FBTime++; //已用时间片加1 } ShowGantt(); ShowTime(); } //优先数算法 void Priority() { int t = 0, i, j = -1; int ilMin; //上次最高优先级进程下标 int iMin = -1; //当前最高优先级进程下标 int iMinPriority; //当前最高优先级(数值小的优先级高) while(true) { UpdateReachArray(t); //更新到达进程数组 ilMin = iMin; iMinPriority = 100; for(i = 0; i < reach_Num; i++) //找到优先级最高的进程 { if(p[BeReached[i]].run_time > 0 && p[BeReached[i]].priority < iMinPriority) { iMin = BeReached[i]; iMinPriority = p[BeReached[i]].priority; } } if(ilMin != iMin) //若当前运行进程和上个运行进程不是同一个,则j++ { j++; strcpy(g[j].p_name, p[iMin].p_name); } g[j].run_time += 1; p[iMin].run_time -= 1; if(p[iMin].response_time == -1) p[iMin].response_time = t - p[iMin].reach_time; //记录该进程响应时间 if(p[iMin].run_time == 0) p[iMin].turnaround_time = t + 1 - p[iMin].reach_time; //记录该进程周转时间 if(CheckFinish()) break; t++; //时间加1 } ShowGantt(); ShowTime(); } void Information() { cout << "***********************************提示信息***********************************" << endl; cout << "文本文件格式为:" << endl; cout << "进程名 到达时间 运行时间 优先级" << endl << endl; } void main() { Information(); cout << "********************************短作业优先算法********************************" << endl << endl; Init(); SPN(); cout << "****************************时间片轮转法(时间片为1)***************************" << endl << endl; Init(); RR(1); cout << "****************************时间片轮转法(时间片为2)***************************" << endl << endl; Init(); RR(2); cout << "****************************时间片轮转法(时间片为3)***************************" << endl << endl; Init(); RR(3); cout << "**********************************优先数算法**********************************" << endl << endl; Init(); Priority(); }
实验结果如下图: