进程调度模拟设计

学号：0120809330323昭计專目进程调度模拟设计先来先服务、优先级法学院计算机科学与技术学院专业计算机科学与技术班级计算机 0809姓名雷经纬指导教师汪祥莉2011 年 1 月 19 日课程设计任务书学生姓名：雷经纬专业班级：计算机0809指导教师：汪祥莉工作单位：计算机科学与技术学院题 目: 进程调度模拟设计先来先服务、优先级法 初始条件：1预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程 调度算法有深入的理解。2实践准备：掌握一种计算机高级语言的使用。 要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写 等具体要求）1模拟进程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。2设计报告内容应说明： 课程设计目的与功能； 需求分析，数据结构或模块说明（ 功能与框图）； 源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；V）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周 2：完成程序分析及设计。周 2、周 3：完成程序调试及测试。 周 4、周 5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名：年 月 日系主任（或责任教师）签名课程设计报告书1 需求分析1.1 模拟进程调度，能够处理的情形 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的基本信息，如进程名、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。1.2 设计要求阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解2 设计分析2.1 一些约定 进程名是进程存在的唯一标示，请勿重复 输入进程名 0 表示进程已输入完毕 时间统一取自秒制2.2 处理情形本次设计预计可以处理任意满足约定的输入进程信息，并提供操作选择。对 于输入的进程数没有要求，并且增加了 CPU 空转即无进程运行情况。在最大程 度上模拟了实际运行要求。2.3 实现以下错误处理 进程名作为唯一标示，不可重复 起始时刻应不小于 0 ，运行时间应大于 0 错误操作选择则即时处理2.4 设想及理论分析这个实验主要是进程调度模拟设计，进程调度有很多方法，例如：先来 先服务法，最高响应比优先调度算法，优先级法，非抢占式断进程优先法， 抢占式短进程优先级法等等。他们原理都不一样，各自有各自的好处和不足， 因此我们要在不同的场合使用不同的调度方法，这个课程设计要求使用先来 先服务和优先级两种算法，来实现对进程的模拟。首先他要求能够用两种方法实现进程调度，我们需要首先输出一个选择程 序，来选择一个调度算法，输入数据来进行运算，这是我们首先要解决的问 题。其次，我们要接近输入数据的存放问题，毕竟我还需要数据来进行操作 和调度。我们要用结构体来存放一个进程的相关信息，例如：进程名字，进 程到达时间，进程的运行时间。但是我们在出来进程的时候，还必须要按照 一定的顺序来处理，所以我们必须要对结构体里存放的进程相关信息来进行 排序。只有经过处理过后，才能更容易的实现进程的调度，同时当不只一个 进程的 时候，我们还必须设置用多个地址单元来实验对输入的数据进行存 储，多个输入就相当于的链表的插入处理，因此我们又必须要对链表之间的 指针进行处理，这涉及到指针的跳转，我们 必须要运用我们所学的知识进行。我们还必须要对程序的输出进行处理，因为按照实验要求，我们必须显 示进程调度队列；根据选择的调度算法计算平均周转时间和平均带权周转时 间。这要求我们要设计算法，将进程的调度顺序给输出，从输出就可以检查 自己的设计是否是正确的。而周转时间则是完成时间减去提交时间，平均周转时间就是几个进程的 周转时间的平均值。而带权周转时间就是周转时间除以执行时间。2.4 程序流程图3 软件具体设计3.1 数据结构链表节点typedef struct jincheng/进程链表节点 structstring name;double level,timein,timeon,zztime,dctime;优先级 到达时间 运行时间,周转时 间,带权周转时间jincheng *next;注意：本次链表在首节点即head保留为不可用值3.2 定义全局变量及函数声明static int n=0;/进程数目static jincheng *head; /进程链表头指针，注意首节点为空void shuru();/输入bool check(int i,double time); /检测输入时间有无错误bool check(string ming);/检测进程名有无重复(本程序以进程名作为唯一标示) void dayin();/打印输入void shixu();/按时间排序void paixu();/按优先级结合时序排序void yunxing(int i);/运行并打印3.3 程序入口初始化head=new jincheng; pp=new jincheng;首节点即head保留为不可用值pp=NULL; head-next=pp;3.4 分函数介绍1 输入函数 shuru()void shuru()/输入进程信息string over(0),name;/设置输入结束标志 double time;n=0;jincheng *p1,*p2;p1=p2=new jincheng;p1-next=NULL;p2-next=NULL;coutn;cout！ 1进程名是进程存在的唯一标示，请勿重复。n； cout！ 2输入进程名0表示进程已输入完毕n;cout！ 3时间统一取自秒制n;coutn;cout请输入第+nname;while(pare(name)/输入不为 0 则继续p1-name=name;cou t 请输入namep1-level;checkl:cou t请输入nametime;if(check(1,time) /检错couttimein=time;check2: cou t请输入nametime;if(check(2,time)/检错couttimeon=time;if(head-next=NULL) head-next=p1;/首节点问题else p2-next=p1;p2=p1;p1=new jincheng;p1-next=NULL;check3:cou t请输入第+nname;if(check(name) /检错cou t !进程名name重复，请调整n;n-; goto check3;n-;dayin();2 两个 check 检错函数重载bool check(int i,double time) / 检验输入时刻和运行时间，不小于 0 且小于 100switch(i)case 1:if(time100) return true;else return false;break;case 2:if(time100) return true;else return false;bool check(string ming) /检验进程名，不可重复 jincheng *p;p=new jincheng;p=head-next; while(p!=NULL) if(p-name=ming)return true;p=p-next;return false;3 为了及时反馈输入信息，立即打印输入汇总 dayin()void dayin()jincheng *p;p=new jincheng; p=head-next;cout 待 运 行 进n; while(p!=NULL)cou t进程名 优先级 到达时间运行时间n；cout;coutname；cout.setf(ios:left);/设置对齐方式为 left cout；cout.width(10);coutlevel;cou t.wid th(ll);/设置宽度为11,不足用空格填充 couttimein;cout.width(11); couttimeonnext;4 按时间排序的 shixu()void shixu()/按时间排序jincheng *p1,*p2,*temp1,*temp2,*temp3;p1=new jincheng;p2=new jincheng; int flag;temp1=new jincheng;temp2=new jincheng;temp3=new jincheng;p1-next=NULL; p2-next=NULL;temp1-next=NULL;temp2-next=NULL;temp3-nex t二NULL;/初始化 p1=head;for(int i=0;inext;flag=0;/相邻节点标志while(p2-next!=NULL)if(p1-next-timeinp2-next-timein)if(flag=0)temp1=p1-next;/交换相邻节点temp2=p1-next-next-next;p1-next=p1-next-next;p1-next-next=temp1;p1-next-next-next=temp2;flag=1;p2=p1-next-next;elsetemp1=p1-next;/交换节点temp2=p1-next-next;temp3=p2-next-next;p1-next=p2-next;p1-next-next=temp2;p2-next=temp1;p2-next-next=temp3;p2=p2-next;elsep2=p2-next;flag=1;p1=p1-next;5 优先级排序void paixu()/优先级排序jincheng *p1,*p2,*temp1,*temp2,*temp3;double mintime=100,systime=0;p1=new jincheng;p2=new jincheng;int flag;temp1=new jincheng;temp2=new jincheng;temp3=new jincheng;p1-next=NULL;p2-next=NULL;temp1-next=NULL;temp2-next=NULL;temp3-nex t二NULL;/初始化p1=head;for(int i=0;inext;while(temp1!=NULL)/修正系统时间，空转现象if(mintimetemp1-timein) mintime=temp1-timein; temp1=temp1-next;if(systimenext;flag=0;while(p2-next!=NULL)if( p1-next-levelnext-level&(p2-next-timeinnext;temp2=p1-next-next-next;p1-next=p1-next-next;p1-next-next=temp1; p1-next-next-next=temp2;flag=1;p2=p1-next-next;/交换相邻节点elsetemp1=p1-next;temp2=p1-next-next;temp3=p2-next-next;p1-next=p2-next;p1-next-next=temp2;p2-next=temp1;p2-next-next=temp3;/交换节点p2=p2-next;else p2=p2-next; systime+=p1-next-timeon;/ 调整系统时间，空转特殊情况 temp1=p1-next;while(temp1!=NULL)if(mintimetimein) mintime=temp1-timein; temp1=temp1-next;if(systimenext;6 运行并打印输出 yunxing()void yunxing(int i)/运行，打印结果double totalzztime=0,totaldctime=0,systime=0;jincheng *p;p=head-next;if(i=1)cout 先 来 先 服 务 法 运 行 过 程n;elsecout 优 先 级 法 运 行 过 程n;cout 进程名 优先级 到达时间 运行时间 运行起始时间 结束时 间 周转时间 带权周转时间 n;while(p!=NULL) if(systimetimein) cout! 空 转 时 间 段 : systime-timeintimein; p-zztime=systime+p-timeon-p-timein; p-dctime=p-zztime/p-timeon;cout ;coutname;cout.setf(ios:left);/设置对齐方式为 left cout;cout.width(9); coutlevel;cou t.wid th(9);/设置宽度为10,不足用空格填充 couttimein;cout.width(10);coutsystime;cout.width(10); couttimeon+systime;cout.width(9); couttimeon;cout.width(9); coutzztime;cout.width(10); coutdctimezztime;totaldctime+=p-dctime; systime+=p-timeon;p=p-next;cou t平均周转时间为：0? tot alzz time/n:0);coutn 平均带权周转时间为： 0?totaldctime/n:0)endl; coutnn;7 先来先服务法 FFS()由于shixu ()已经解决了次序问题，故直接调用yunxing ()即可。8 优先级法 YXJ()在shixu ()的基础上，调用paixu ()函数，施以优先级排序，然后调用 yunxing ()即可。9 操作处理选择算法及输入start:coutnext=pp;cout请选择算法：n; cout1 先来先服务法 n;cout2优先级法n;coutchoice1;if(choice12)system(cls); /选项不对则清屏goto start;shuru();/输入待运行进程shixu();/立即按时间排序again:if(choice1=1) FFS();/先来先服务法else if(choice1=2) YXJ(); /优先级法 else goto start;cout请选择操作: coutcoutcoutchoice2;switch(choice2)系统操作1改变输入进程并重新操作n;2保留原输入而改变算法n； 3退出n;您的选择： ；case 1: system(cls); /重新操作则清屏 goto start;break;case 2:if(choice1=1) choice1=2;else choice1=1;goto again;break;case 3: return ;default:return ;/默认退出4 软件具体设计4.1 软件入口及选择操作提示n s D S0 0 01 1 8 1 4 6 各3 :各丘:1 :各 程-刻-刻一一 -刻国 进蹩级-#1级吋于#1 的先达貫先达话先达曹祜的先达需先达水达行于酉 僅到运僅到运僅到运程到运亦撬到不到运衣垣程 进的的的进的的的进的的的进Jr迸的的的进的的应的的应的进个个養曇个 社进进进軟进进进報进进进輕名輕进进进報进进皐进屠撤 A-AAAA-AAAA-AAAA註A入入入入入入.人入丰j入入f*f*臺后f*主星输.1AG 新 输 0 10107 重16f 新牡 社：各r请：讐各:刻卷刻间洛4.2选择先来先服务法并输入进程信息进程名重复的检错与恢复输入时间时刻的检错与恢复以“0”结束4.3 打印输入信息特运行逬程进程名优先级到达时间运行时间A31俾1W进程名优先级到达时间运行时间S681W进程名优先级到达时间运行时间D146进程名优先级到达时间运行时间F8进程名G优先级4到达时间16运行时间84.4打印所选算法的运行结果（此为先来先服务法）先来先服务法运行过程”購备機级芒営间运行时间运行起始吋间结東时间周转时间带权周转晒D14410661S682121.2A3102总3%202F81040303G41640488324I诗时问为：枝周转时间为：2色 2!244.5选择操作（保留输入而用另一种算法）3退田优先级法运行过程-进程名优先级到达时间运行时间运行起始时间结束时间周转时间带权周转时间 M空转时间段：4184108161019.62.154102Q3S38102Q303848101081810222238112.22_?53.8选择齢；ipsasr 3退出4.6 选择操作（重新输入进程信息并选择算法）您的选择:2,小 ，、.您的选择：1 枠3畑*我程调度模拟设计一一先来先服务、fj 选择算扫 曲务法；虧鎳耦严重复? 统一取自秒制5 总结与体会5.1 本次设计的优点本设计软件达到了预期的实验目标，并且充分考虑了操作冗余度。进程管理 切换的模拟是一个动态的过程，涉及到进程的保存标示，分配。对于进程的存储采用了链表结构，便于动态生成与组织，虽然链表的操作 相对麻烦一些，但是这是一个很好的锻炼机会。在算法的实现上，也是充分利用 了两种算法的共性和判别思路的特点。先来先服务算法基于时间进行排序，而优 先级法必须结合时间排序，并施以优先级特征。在进程信息的组织上，尤其是时间的处理，简化了时分秒系统而统一采用 秒制，清晰地说明了问题。最后本程序对于输入的冗余处理大大提高了健壮性， 也更符合实际。5.2 不足之处在对链表的操作上，尤其是交换两个链表节点，本程序分了两种情况，一种 是交换相邻链表，另一种是交换不相邻节点。为此设置了 flag标志，并且效率 上有所降低。而且链表的头结点也是作为NULL处理，浪费了空间。5.3 总结与体会操作系统是一门理论性很强的课程，设计的模块多，进程控制更是重点。本 次课程设计：进程调度模拟设计先来先服务、优先级法。让我对于系统进程 的组织有了更深的了解，尤其是进程调度切换有了直观认识。当然了进程的调度 不止这两种算法，个人体会，无论采用什么算法，都必须结合先来先服务方法。 各种算法都有一些共性，而我们怎么样找到一种合适的算法才是关键，也许我们 还可以从进程的组织结构入手。在编制程序的过程中，刚开始对于数据结构的选择犹豫了一会儿，究竟是采 用动态数组还是链表，后来为了输入的实用性，采用链表。在基于链表的操作时 本着够用的原则，将各种操作融合到了逻辑处理中。最后在程序冗余度上下了一 些功夫。调试的过程中，刚开始并不能对于所有的输入正确处理，慢慢发现问题如下：没有考虑CPU 空转，链表操作不当。后来更正了这些问题，现在本程序已经能够处理各种输入，并能 准确报告全运行过程。6 参考文献1 张尧学 史美林等 计算机操作系统教程（第3 版）.清华大学出版社.2006.102 严蔚敏 吴伟民.数据结构（C语言版）清华大学出版社.2003.5本科生课程设计成绩评定表班级：计算机 0809 姓名：雷经纬学号：0120809330323序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100 分）、良（80-89 分）、中（70-79 分）、 及格（60-69分）、60 分以下为不及格指导教师签名：2011 年 1 月 日