进程调度模拟设计——优先级法、_最高响应比优先调度算法.docx

学 号： 课 程 设 计题 目进程调度模拟设计优先级法、最高响应比优先调度算法学 院计算机科学与技术专 业班 级姓 名指导教师吴利军2013年1月15日课程设计任务书学生姓名： 指导教师：吴利军 工作单位： 计算机科学与技术学院 题 目: 进程调度模拟设计优先级法、最高响应比优先调度算法 初始条件：1预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1模拟进程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。2设计报告内容应说明： 需求分析； 功能设计（数据结构及模块说明）； 开发平台及源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日进程调度模拟设计优先级法、最高响应比优先调度算法1设计目的与实现功能模拟进程调度，使程序能够完成：能够输入若干进程，包括进程的一些基本信息，如进程名、优先级、到达时间和运行时间等，选择不同的调度算法（优先级法或者最高响应比法），选择算法后，根据选择的调度算法显示进程调度队列；根据选择的调度算法计算平均周转时间和平均带权周转时间。2需求分析2.1实验原理 最高响应比优先算法（hrn）：最高响应比是对先来先服务和最短进程优先法德一种综合平衡。hrn调度策略同时考虑每个进程的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的进程投入执行。 响应比r定义如下：r=(w+t)/t=1+w/t其中t为该进程的估计需要的执行时间，w为进程在后备状态队列的等待时间。每当要进行进程调度是，系统计算每个进程的响应比，选择其中r最大者投入执行。优先级法：系统和用户按某种原则为进程制定一个优先级来表示该进程所享有的调度优先权。根据优先级的高低来对进程加以调度。3. 数据结构3.1主要结构及函数struct timer /时间类型 byte hour;byte minute;typedef struct process/进程结构char name20; /进程名byte rank; /进程等级 timer time_in; /进程到达的时间byte use_time; /运行需要消耗时间timer time_start;/开始运行时刻byte used_time; /已经运行的时间timer time_end; /进程结束时刻bool flag; /进程运行完成标志，完成trueprocess,*process_ptr;bool search(process process_n)/查看是否所有进程都执行完bool compare(timer time1,timer time2) /比较两个时间类型的大小void paixv(process process_n)/进程按优先级有大到小排序，规定rank越小优先级越高void printf_last(process process_n)/打印结果void grade_first(process process_n)/抢占式优先级调度算法void hrn(process process_n)/最高响应比优先算法优先级调度的思路： 这里设计的是一个抢占式优先级调度设一个标志位作为时钟，时间一分分地走，通过每次扫描各个进程的状态，确定这一分钟该哪个进程执行，在这之间要记录某个进程的开始时间、已运行时间和结束最后，到每个进程都执行过，完成优先级调度。最高响应比优先调度的思路： 每次调度前都计算每个作业的响应比，从而选择其中最大者投入运行。3.2流程图输入进程信息最高响应比算法选择使用的方法优先级算法输出调度序列4. 源程序的主要部分41查看是否所有进程都执行完bool search(process process_n)for(int i=0;itime2.hour)return true;else if(time1.hour=time2.hour&time1.minute=time2.minute)return true;elsereturn false;42进程按优先级有大到小排序，规定rank越小优先级越高void paixv(process process_n)int i,j;process temp;for(i=0;in-1;i+)for(j=0;jprocess_nj+1.rank) temp=process_nj;process_nj=process_nj+1; process_nj+1=temp; 4.3打印结果void printf_last(process process_n)float amax;/记录每个进程的周转时间 float bmax;/记录每个进程的带权周转时间float out_a=0; float out_b=0; printf(进程名 进程级别 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间n); for(int i=0;in;i+) ai=(float)(process_ni.time_end.hour-process_ni.time_in.hour)*60+process_ni.time_end.minute-process_ni.time_in.minute); bi=ai/process_ni.use_time; out_a+=ai; out_b+=bi; printf(%4st%4dt,process_,process_ni.rank); printf( ); if(process_ni.time_in.hour10) printf(0%d,process_ni.time_in.hour); else printf(%d,process_ni.time_in.hour); printf(:); if(process_ni.time_in.minute10) printf(0%dt,process_ni.time_in.minute); else printf(%dt,process_ni.time_in.minute); / / printf(%4dt,process_ni.use_time); / / if(process_ni.time_start.hour10) printf(0%d,process_ni.time_start.hour); else printf(%4d,process_ni.time_start.hour); printf(:); if(process_ni.time_start.minute10) printf(0%dt,process_ni.time_start.minute); else printf(%dt,process_ni.time_start.minute); / printf( ); / if(process_ni.time_end.hour10) printf(0%d,process_ni.time_end.hour); else printf(%d,process_ni.time_end.hour); printf(:); if(process_ni.time_end.minute10) printf(0%dt,process_ni.time_end.minute); else printf(%dt,process_ni.time_end.minute); / / printf(%.2ft,ai); printf(%.2fn,bi);out_a=out_a/n;out_b=out_b/n;printf(平均周转时间为：%fn,out_a);printf(平均带权周转时间为：%fn,out_b);4.4抢占式优先级调度算法/* 抢占式优先级调度算法 */void grade_first(process process_n) int i; bool flag;/标志位，用于控制当前时间 while(1) flag=true;for(i=0;i=n;i+)if(compare(current,process_ni.time_in)&!(process_ni.flag) flag=false;/获取开始运行时间if(process_ni.time_start.hour=0&process_ni.time_start.minute=0)process_ni.time_start=current;/记录进程已经运行的时间process_ni.used_time+;/时钟继续一分一分走current.minute+;if(current.minute=60) current.hour+=1; current.minute=0;/运行完成后，记录完成时间if(process_ni.used_time=process_ni.use_time)process_ni.flag=true;process_ni.time_end=current;break;if(flag)current.minute+;if(current.minute=60)current.hour+=1;current.minute=0;if(search(process_n) break;else continue; 4.5最高响应比优先算法/* 最高响应比优先算法 */void hrn(process process_n)float flag_xiangximax;/记录进程的响应比/找到最小的时间作为当前基准时间current=process_n0.time_in;for(int i=1;in;i+) if(compare(current,process_ni.time_in) current=process_ni.time_in; /while(!search(process_n)float temp=0;for(int i=0;itemp)temp=flag_xiangxii;for(int j=0;jn;j+) if(compare(current,process_nj.time_start)&process_nj.flag=false&temp=flag_xiangxij)process_nj.time_start=current;current.hour=(current.hour*60+current.minute+process_nj.use_time)/60;current.minute=(current.hour*60+current.minute+process_nj.use_time)%60;process_nj.time_end=current;process_nj.flag=true;break;4.6主函数int main()int one_two;process process_nmax;process process_n_othermax;char time_string10;char flag_exit;while(1)printf(请输入进程个数：);scanf(%d,&n); fflush(stdin);for(int i=0;i24) printf(输入格式不符合在24小时内的要求！请重新输入.n); printf(提交时间:); scanf(%s,&time_string); fflush(stdin); a=(time_string0-48)*10+time_string1-48;process_ni.time_in.hour=a;a=(time_string3-48)*10+time_string4-48;while(a=60)printf(输入格式不符合在60分钟内的要求！请重新输入.n);printf(提交时间:);scanf(%s,&time_string); fflush(stdin);a=(time_string3-48)*10+time_string4-48;process_ni.time_in.minute=a; printf(执行时间:);scanf(%d,&(process_ni.use_time); fflush(stdin);process_ni.flag=false; l1:printf(请你选择你将采用的调度算法:n);printf(1-优先级调度n2-最高响应比优先算法n);printf(如果想退出程序请输入其他n);scanf(%d,&one_two); fflush(stdin); if(one_two=1)current.hour=0;current.minute=0;for(i=0;in;i+)process_n_otheri=process_ni; paixv(process_n_other);grade_first(process_n_other); printf_last(process_n_other);printf(是否退出程序？退出请输入yn);scanf(%c,&flag_exit);fflush(stdin);if(flag_exit=y|flag_exit=y)return 0;else goto l1;else if(one_two=2)current.hour=0; current.minute=0;for(i=0;in;i+)process_n_otheri=process_ni; hrn(process_n_other); printf_last(process_n_other); printf(是否退出程序？退出请输入yn); scanf(%c,&flag_exit); fflush(stdin); if(flag_exit=y|flag_exit=y)return 0; else goto l1;elsereturn 0;return 0;5测试输入测试用例：名称 优先级 到达时间 运行时间（分）a 2 12:35 30b 3 12:20 25c 4 12:39 20d 1 12:40 221. 优先级算法分析如下：第3级别b进程开始运行，但由于是抢占式的，在12:35时，也就是b运行15分钟后，有第2级别的a进程到来，a只运行5分钟后，d到来，由于d是最高级别，d可以运行完，此时是13:02，a继续进行25分钟，完成a，之后b再运行10分钟，完成b，最后运行c。2. 优先级算法分析如下：b进程先到，所以先把b进程完成，也就到时间12:45，此时a、c、d进程都到了，如果运行a:r=(w+t)/t=1+w/t=（12:45+30-12:35）/30=4/3=1.333 如果运行c:r=(w+t)/t=1+w/t=（12:45+20-12:39）/20=13/10=1.3如果运行d: r =(w+t)/t=1+w/t=（12:45+22-12:40）/22=27/22=1.22由于a的响应比最大，所以先运行a,同理，a运行之后 如果运行c：r=(w+t)/t=1+w/t=（13:15+20-12:39）/20=14/5=2.8 如果运行d:r=(w+t)/t=1+w/t=（13:15+22-12:40）/22=57/22=2.59 故运行c，最后运行d6.自我评价与总结6.1自我认为出色的地方在这次的操作系统课程设计中，我设计的进程的结构是合理的，其中进程结束与否这个标志位对程序的运行起到了很大的作用，结构如下：typedef struct process/进程结构char name20; /进程名byte rank; /进程等级 timer time_in; /进程到达的时间byte use_time; /运行需要消耗时间timer time_start;/开始运行时刻byte used_time; /已经运行的时间timer time_end; /进程结束时刻bool flag; /进程运行完成标志，完成trueprocess,*process_ptr;优先级调度的算法实现过程中，取一个参考时钟对实现抢占式的优先级起到了很大的作用，原本想实现非抢占式的优先级调度，后来想挑战一下自己，就选择抢占式的算法，在实现过程中遇到一些问题，但很好的锻炼了自己。在最高响应比优先采用另外一个数组flag_xainximax来记录每个进程响应比，通过比较每个响应比的大小确定下一个执行的进程，没有在进程中的结构体中添加字段来反映响应比，简化了结构。6.2不足之处采用数组形式实现的，输入的进程的个数是有限的，不能动态的增加，可以采用链表的形式，结合malloc，realloc函数来实现动态增加进程。本程序也使用大量的for循环，不宜大数据量的计算，影响了程序的运行速度，以后要仔细观察，进行代码优化。6.3总结通过这次课程设计，巩固了知识，对进程调度的理解更加深刻，同时也对c语言的基本语言有了重新的认识，开阔了自己的思维。这些经典的进程调度算法很值得我自己动手去模拟、去实现，所以在做了这两个进程调度算法后，我又去模拟实现了磁盘的电梯调度和最短时间优先调度算法以及页式调度中的最近最久未使用（lru）算法，感觉模拟这些并不困难，但在操作系统中实现这些算法就涉及的是真正的进程和硬件设备了，去实现一个操作系统还是比较难的。但这些模拟让我明白操作系统怎么管理进程运行，管理内存空间的，也让我明白了自己的不足，为以后的深入学习奠定了基础。7、源码/优先级法、最高响应比优先调度算法#include #include #includetypedef unsigned char byte;#define max 20 /时间类型struct timer byte hour;byte minute;timer current; /标志当前时间int n; /输入的进程数byte flag; /标志当前选择的是抢占式优先-1， /还是最高响应比-2/进程结构typedef struct processchar name20; /进程名byte rank; /进程等级 timer time_in; /进程到达的时间byte use_time; /运行需要消耗时间timer time_start;/开始运行时刻byte used_time; /已经运行的时间timer time_end; /进程结束时刻bool flag; /进程运行完成标志，完成trueprocess,*process_ptr;/查看是否所有进程都执行完bool search(process process_n)for(int i=0;itime2.hour)return true;else if(time1.hour=time2.hour&time1.minute=time2.minute)return true;elsereturn false;/进程按优先级有大到小排序/规定rank越小优先级越高void paixv(process process_n)int i,j;process temp;for(i=0;in-1;i+)for(j=0;jprocess_nj+1.rank) temp=process_nj;process_nj=process_nj+1; process_nj+1=temp; /打印结果void printf_last(process process_n)float amax;/记录每个进程的周转时间 float bmax;/记录每个进程的带权周转时间float out_a=0; float out_b=0; printf(进程名 进程级别 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间n); for(int i=0;in;i+) ai=(float)(process_ni.time_end.hour-process_ni.time_in.hour)*60+process_ni.time_end.minute-process_ni.time_in.minute); bi=ai/process_ni.use_time; out_a+=ai; out_b+=bi; printf(%4st%4dt,process_,process_ni.rank); printf( ); if(process_ni.time_in.hour10) printf(0%d,process_ni.time_in.hour); else printf(%d,process_ni.time_in.hour); printf(:); if(process_ni.time_in.minute10) printf(0%dt,process_ni.time_in.minute); else printf(%dt,process_ni.time_in.minute); / / printf(%4dt,process_ni.use_time); / / if(process_ni.time_start.hour10) printf(0%d,process_ni.time_start.hour); else printf(%4d,process_ni.time_start.hour); printf(:); if(process_ni.time_start.minute10) printf(0%dt,process_ni.time_start.minute); else printf(%dt,process_ni.time_start.minute); / printf( ); / if(process_ni.time_end.hour10) printf(0%d,process_ni.time_end.hour); else printf(%d,process_ni.time_end.hour); printf(:); if(process_ni.time_end.minute10) printf(0%dt,process_ni.time_end.minute); else printf(%dt,process_ni.time_end.minute); / / printf(%.2ft,ai); printf(%.2fn,bi);out_a=out_a/n;out_b=out_b/n;printf(平均周转时间为：%fn,out_a);printf(平均带权周转时间为：%fn,out_b);/* 抢占式优先级调度算法 */void grade_first(process process_n) int i; bool flag;/标志位，用于控制当前时间 while(1) flag=true;for(i=0;i=n;i+)if(compare(current,process_ni.time_in)&!(process_ni.flag) flag=false;/获取开始运行时间if(process_ni.time_start.hour=0&process_ni.time_start.minute=0)process_ni.time_start=current;/记录进程已经运行的时间process_ni.used_time+;/时钟继续一分一分走current.minute+;if(current.minute=60) current.hour+=1; current.minute=0;/运行完成后，记录完成时间if(process_ni.used_time=process_ni.use_time)process_ni.flag=true;process_ni.time_end=current;break;if(flag)current.minute+;if(current.minute=60)current.hour+=1;current.minute=0;if(search(process_n) break;else continue; /* 最高响应比优先算法 */void hrn(process process_n)float flag_xiangximax;/记录进程的响应比/找到最小的时间作为当前基准时间current=process_n0.time_in;for(int i=1;in;i+) if(compare(current,process_ni.time_in) current=process_ni.time_in; /while(!search(process_n)float temp=0;for(int i=0;itemp)temp=flag_xiangxii;for(int j=0;jn;j+) if(compare(current,process_nj.time_start)&process_nj.flag=false&temp=flag_xiangxij)process_nj.time_start=current;current.hour=(current.hour*60+current.minute+process_nj.use_time)/60;current.minute=(current.hour*60+current.minute+process_nj.use_time)%60;process_nj.time_end=current;process_nj.flag=true;break;/主函数int main()int one_two;process process_nmax;process process_n_othermax;char time_string10;char flag_exit;while(1)printf(请输入