进程调度模拟设计——先来先服务、强占式短进程优先算法.doc

学 号： 0120910340305操作系统课 程 设 计题 目进程调度模拟设计先来先服务、强占式短进程优先算法 学 院计算机科学与技术专 业计算机科学与技术班 级计算机0903姓 名方传强指导教师杜薇2012年1月11日课程设计任务书学生姓名： 方传强 专业班级： 计算机0903 指导教师： 杜薇 工作单位： 计算机科学与技术学院 题 目: 进程调度模拟设计先来先服务、强占式短进程优先算法 初始条件：1预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1模拟进程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的基本信息，如进程名、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。2设计报告内容应说明： 需求分析； 功能设计（数据结构及模块说明）； 开发平台及源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日课程设计报告书1. 课程设计的题目进程调度模拟设计先来先服务、强占式短进程优先算法。2.课程设计的目的此次课程设计的预备内容是阅读操作系统的处理机管理章节内容，并对进程调度的功能以及进程调度算法有深入的理解和掌握。完成此次模拟进程调度，需要处理一下的情形：2 能够选择不同的调度算法（先来先服务算法和强占式短进程优先算法）； 能够输入进程的基本信息(如进程名、到达时间和运行时间等)；3 根据选择的调度算法显示进程调度队列；4 根据选择的调度算法计算平均周转时间和平均带权周转时间。3.需求分析进程调度模拟设计是本次课设的课题，根据其课程设计的目的和要求，对其需求分析如下所示：3.1 对进程信息的描述和实现此次课程设计中，进程作为基本数据处理单元，需要对进程的基本信息进行相关的描述。进程的基本信息包括进程进程名，到达的时间以及预计的进程运行时间。设计一个模块，用以实现进程的基本信息的定义和封装，提高设计的简洁性，如使用类模块。3.2 对调度算法的描述和实现进程基本信息所构成的模块作为基本单元，并且相关调度算法的侧重进程基本信息点不同，所以要根据其调度算法的特点来结合基本信息进行对应的设计。此次课程设计要求的调度算法描述如下：3.2.1 先来先服务调度算法先来先服务调度算法是以进程的到达时间为判断标准，按各个进程所的到达时间先后顺序进行调度。要实现此先来先服务调度算法以及考虑程序的简洁性，用一个数据结构如优先级队列，容器等来存储进程基本信息，并要对所有的进程按其到达时间先后顺序进行排序，实现依次取出的进程是所有未运行进程中到达时间最早的进程。3.2.2 强占式短进程优先调度算法此调度算法和先来先服务调度算法相区别，强占式短进程优先调度算法的实现相对而言较为复杂。对强占式短进程优先调度算法而言，其本质特征便是按进程的预计运行时间长短进行排序，先执行短进程。若内存中运行的进程优先级比就绪队列中的某进程优先级低（即运行的进程预计运行时间比就绪队列中的某进程长），此运行的进程让出内存并进入就绪队列，优先级更高的短进程强占内存资源并运行直到结束或者遇到优先级更高的进程强占为止。3.3计算平均周转时间和平均带权周转时间 平均周转时间和平均带权周转时间是对调度算法进行评估的参考标准，在此次课设中要求计算出平均周转时间和平均带钱周转时间。平均周转时间可由所有进程的周转时间之和除以进程数，同理平均带权周转时间也可如此求得。3.4 显示调度序列按课程设计要求，要显示进程调度队列，并且还要求对平均周转时间和平均带权周转时间进行显示。就先来先服务调度算法而言，要求显示的进程调度队列即是进程运行顺序（也就是进程到达时间先后顺序排序的队列）；而强占式短进程优先级调度算法中，为了简洁便利的因素以及直观性，所以就以进程完成运行的先后时间顺序进行显示。4.功能设计此次课设采用面向对象的方法进行对此进程调度系统的模拟。以下分别就概要设计和详细设计先后进行功能设计的相关描述。4.1 概要设计根据课设要求和需求分析的结果，设计了两个类模板，即process类和dispatch类。process类用以描述进程的信息，其数据域有进程名（name），进程到达时间（start_time），进程预计运行时间（run_time）。并设计了一个布尔变量bvisited标志进程是否运行结束，设计了一个变量end_time存储进程完全运行结束的时间点，用以辅助显示进程调度队列。Process类声明如下：class processfriend std:istream& operator(std:istream& input,process& Process);/友元函数process输入流friend std:ostream& operator(std:istream& input,dispatch& Dispatch);/友元函数dispatch输入流friend std:ostream& operator(std:ostream& output,dispatch& Dispatch);/友元函数dispatch输出流private:int count; /定义变量表示进程process的个数bool SF_FC;/标志选择的调度算法类型double Tse,Wi;/总周转时间和总带权周转时间typedef bool (*compare_type)(process&,process&);/定义指向函数的指针，实现不同调度算法选择的实现compare_type compare_1,compare_2;/定义指向函数的指针，实现不同调度算法选择的实现priority_queueprocess,vector,compare_type PQueue;/定义按到达时间顺序的队列PQueuequeue Queue;/定义此队列表示完成的进程vector vec;public:dispatch(bool sf_fc = true);void FCFS();/先来先服务调度算法void Short_No1();/强占式短进程优先调度算法void print();/显示调度队列的算法;dispatch类中PQueue队列用以存储所有输入的原有进程信息，并且其优先级是以到达时间的先后顺序而确定，即先到的进程排在前，后到的进程排在后。Vector容器用以支持强占式短进程优先调度算法的实现，存储所有在当前时间点已经到达的进程信息，并每次存入新的进程信息时便对此vector中元素进行排序，其排序要求按预计运行的时间长短，即预计运行时间较短的进程排在预计运行时间较长的进程前面。普通队列Queue用以存储完成运行的队列，其依旧按照队列的“先进先出”的属性，即把先运行完毕的进程排在前，后运行结束的进程排在后。在此次设计中，设计了一个文本文档（lin.txt）用以存储进程信息，以文本的方式读入进程信息或写入进程信息，可以直接在lin.txt直接添加或删除进程信息。设计了一个主函数，其中建立一个dispatch类对象，采用简单菜单模式。4.2 详细设计界面设计不是本次课程设计的要求，所以就使用dos命令窗口。而进程调度算法则是本次设计的核心部分，所以就此调度算法部分的逻辑进行阐释说明，进程调度算法的逻辑图如下所示：4.2.1 main函数以及进程信息的输入用delete语句撤销dispatch对象调用显示进程调度信息的算法print（）调用进程调度算法根据满足要求的输入，调用dispatch的构造函数构生成相应的dispatch对象输出选择进程调度算法的提示信息关闭lin/.txt文档从文本文档lin.txt读入进程信息输入数据满足要求开始运行主函数结束主函数的运行否是图14.2.2 先来先服务进程调度算法（FCFS）调用FCFSS算法输出错误提示否察看当前进程是否访问过？取出第PQueue中的队首元素，即PQueue队列中到达时间最早的进程否按到达时间顺序排列的PQueue进程队列是否为空？模拟运行该进程，对总周转时间，总带权周转时间进行赋值，对end_time（结束时间）点赋值。并把当前进程插入Queue队列，并删除其在PQueue中的信息队列PQueue是否为空？是结束FCFS函数调用图24.2.3 强占式短进程优先进程调度算法（SF）结束SF函数调用调用SF算法是PQueue队列是空？模拟当前进程运行结束，对总周转时间，总带权周转时间，以及运行结束时间点（end_time）赋值。并把进程信息插入Queue队列，且删除其在vector中的进程信息否取PQueue队列第一个元素，即到达时间最早的进程进行模拟运行，并计算出不被强占情况下的结束时间点（atime）取下一个运行进程的信息在atime之前是否有进程到达？是PQueue队列为空？Vector是否为空？否是否否是计算出当前系统时间点，并对运行中的进程进行的预计运行时间进行设置（此处以未标志bvisited时的end_time表示）。并将此进程和所有其他新到达进程都插入vector之中进行排序（排序按预计运行时间短在前长居后），删除新到达的进程在PQeuee队列中的信息取PQueue队列的队首元素取vector第一个元素模拟运行取出vector中的第一个元素进入模拟运行状态。计算出此进程不被强占情况下的结束时间点（atime）图35 开发平台和源程序主要代码5.1 开发平台本次课程设计编程部分采用Microsoft Visual Studio 2008。5.2 核心代码5.2.1关于process类的部分函数std:istream& operator(std:istream& input,dispatch& Dispatch) /友元函数dispatch输入流process Pro1;int count1=0;while(input(Pro1)Dispatch.PQueue.push(Pro1);+count1;Dispatch.count = count1;cout共有进程数为Dispatch.count;return input;std:ostream& operator(std:ostream& output,dispatch& Dispatch) /友元函数dispatch输出流int i=1;output共有的进程数目：Dispatch.countendl;output进程名 到达时间 运行时间 endl;while(i= Dispatch.count)cout.endl;outputDispatch.PQueue.top()endl;Dispatch.PQueue.pop();+i;cout.endl;cout*endl;return output;bool compare_SF(process &pro1,process &pro2)/比较进程预计运行时间长短if(pro1.end_time != pro2.end_time)return pro1.end_time pro2.end_time;elsereturn pro1.start_time = pro2.start_time;5.2.2 dispatch类部分函数/构造函数dispatch(bool sf_fc = true):count(0),SF_FC(sf_fc),Tse(0),Wi(0) compare_1 = &compare_FSFC;compare_2 = &compare_SF;if (sf_fc = false)/当给定的标志为真时，表示FSFC调度算法PQueue = priority_queueprocess,vector,compare_type(compare_1);cout选择的是最短进程优先（抢占式）调度算法endl;elsePQueue = priority_queueprocess,vector,compare_type(compare_1);cout选择的是先来先服务调度算法endl;/显示进程调度队列函数void print()process *ptr;int i = 1;/cout进程调度信息如下：endl;cout *运行顺序*进程名*到达时间*运行时间*结束时间*endl;while (Queue.empty() = false)ptr = &Queue.front();cout*i*(*ptr).GETname();cout*(*ptr).GETstart_time();cout*(*ptr).GETrun_time();cout*(*ptr).GETend_time()*endl;+i;Queue.pop();cout平均周转时间：(Tse/count)endl;cout平均带权周转时间：(Wi/count)(std:istream& input,dispatch& Dispatch)process Pro1;int count1=0;while(input(Pro1)Dispatch.PQueue.push(Pro1);+count1;Dispatch.count = count1;cout共有进程数为Dispatch.count;return input;5.2.3 先来先服务算法void FCFS()/先来先服务的实现.int i =0;double atime ; /标志当前内存中进程结束的时间点process *Pro1 = &PQueue.top();/ 取队首元素atime = (*Pro1).GETstart_time();while(i count)(*Pro1).Set_bvisited();cout(*Pro1) endl;+i;atime=atime+(*Pro1).GETrun_time(); (*Pro1).SETend_time(atime);if(*Pro1).Get_bvisited()/如果当前进程已经完成服务功能Tse = Tse +(*Pro1).GETend_time()-(*Pro1).GETstart_time();Wi = Wi + (*Pro1).GETend_time()-(*Pro1).GETstart_time()/(*Pro1).GETrun_time();Queue.push(*Pro1);else couterror!endl;return ;PQueue.pop();/删除队列中的队首元素if(PQueue.empty() = false)process *Pro1 = &PQueue.top();/ 取队首元素5.2.4强占式短进程优先级算法void Short_No1()double atime;/标志当前内存中进程结束的时间点double btime;/表示内存中进程剩余的运行时间double ctime;/表示执行顺序时间点int count1 = count;vector:iterator iter,iter1,iter2;process *ptr = &PQueue.top();/对队首元素的end_time()进行初始化(*ptr).SETend_time( (*ptr).GETrun_time();vec.push_back(PQueue.top();/取出第一个到达的进程,放入vectorPQueue.pop();iter=vec.begin();ctime = (*iter).GETstart_time();atime = (*iter).GETrun_time()+(*iter).GETstart_time();while(count10)process *ptr;if(PQueue.empty()=false)ptr= &PQueue.top();/对队首元素的end_time()进行初始化(*ptr).SETend_time( (*ptr).GETrun_time();while( PQueue.empty()=false & atime(*ptr).GETstart_time()/如果在进程运行期间有进程到达ctime = (*ptr).GETstart_time();btime = atime - ctime;(*iter).SETend_time(btime);/设置运行进程的剩余时间vec.push_back(*ptr);/把到达的进程放进vector中iter = vec.begin();if( (*iter).GETend_time()(*ptr).GETrun_time() )atime =(*ptr).GETstart_time() +(*ptr).GETrun_time();sort(vec.begin(),vec.end(),compare_2); /若新进来的进程优先级高，则排序，令优先高的进程位置于vector第一个元素iter = vec.begin();if(PQueue.empty()=false)PQueue.pop();/删除在到达时间队列中的队首进程信息if(PQueue.empty()=false)ptr =&PQueue.top();/取得修改后的到达时间队列中的新队首进程/找到优先级高的进程，则退出此循环，重新进行小进程运行并查找时候有更高优先级的进程到达elseif(PQueue.empty()=false)PQueue.pop(); /删除在到达时间队列中的队首进程信息if(PQueue.empty()=false)ptr =&PQueue.top();/取得修改后的到达时间队列中的新队首进程iter1 =vec.begin();/取优先级最高的进程ctime = atime;(*iter1).Set_bvisited(true);(*iter1).SETend_time(atime);Tse = Tse+(atime-(*iter1).GETstart_time();Wi = Wi +(atime-(*iter1).GETstart_time()/(*iter).GETrun_time();Queue.push(*iter1);vec.erase(iter1);-count1;/标志完全结束一个进程的运行iter1=vec.begin();iter2=vec.end();if(iter1=iter2)if(PQueue.empty()=false)vec.push_back(PQueue.top();/取出第一个到达的进程,放入vectorPQueue.pop();iter=vec.begin();ctime = (*iter).GETstart_time();atime = (*iter).GETend_time()+(*iter).GETstart_time();break;elseiter =vec.begin();atime = (*iter).GETend_time()+ctime;6.运行结果以及分析6.1测试用例假设有四个进程，其进程信息如下表所示：进程名到达时间运行时间P1 8:00 4:00 P2 9:00 2:00 P3 10:00 1:00 P4 11:00 2:006.2 运行结果运行main函数后，dos命令窗口如下（图4）：输入数据 “3”后，显示结果如下（图5）： 重新输入数据“1”后，显示如下（图6）：输入任意键开始，显示如下（图7）：输入数据“2”，察看抢占式短进程优先算法（图8）：6.3 结果分析6.3.1 先来先服务此调度算法是按照进程到达时间顺序进行运行，所以进程的到达时间顺序就是和进程运行结束时间点的先后顺序相一致。由于进程是按P1,P2,P3,P4顺序到达（如图6所示），则也是按P1,P2,P3,P4的顺序运行结束。如图7所示。6.3.2 强占式最短进程优先由于进程到达时间点先后顺序是P1,P2,P3,P4（如图6所示），所以P1进程首先模拟运行。到时间点9：00，有新进程进入，则比较两者优先级，发现P2优先级较高，则P2强占并模拟运行，P1则插入就绪vector中。P2模拟运行，到达时间点10：00，新进程P3进入，相比较之下P2预计运行时间（此时为剩余的运行时间）和P3预计运行时间相比，两者相等，而此时便按照先来先运行的原则，即P2先模拟运行，P3插入就绪vector中。时间点11：00，P2运行结束，有新进程P4到达。P1,P3,P4在vector中进行优先级比较，P3优先级高即预计运行时间最短，则P3模拟运行。到达时间点12点，因为PQueue队列为空，即没有新的进程到达，则取出vector中的首元素即优先级最高的进程P4,P4运行到时间点14：00后P1运行，直到时间点17：00四个进程都运行结束。6.3.3 调度算法比较比较两个调度算法，即可以根据其平均周转时间和平均带权周转时间相比较，比较之后发现强占式短进程优先调度算法比先来先服务要占据一定的优势，其平均周转时间和平均带权周转时间都较小。7.自我评价与总结在此次课程设计中，得到了很大的锻炼和提高，现就一些方面进行简要的阐述和分析。此次课程设计中，做得比较好的是直接把进程信息设定为一个类模板，如此以来对进程的操作，就是对一个类模板对象的操作，实现了基本信息的有效封装。在设计输入进程信息时，也曾考虑过直接在调试的时候手工输入进程的信息，但是如果那样做的话便会在调试过程中造成时间的极大浪费。如若在调试的过程遇到一些难以解决的问题时便要反复地进行调试，如此一来将花费较大的精力。所以考虑到便捷的问题便设计了一个文本文档lin.txt