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

进程调度模拟 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ——先来先服务、强占式短进程优先算法.doc 学 号: 0120910340305 进程调度模拟设计——先来先服 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目 务、强占式短进程优先算法 学 院 计算机科学与技术 专 业 计算机科学与技术 班 级 计算机0903 姓 名 方传强 指导教师 杜薇 2012 年 1 月 11 日 课程设计任务书 学生姓名: 方传强 专业班级: 计算机0903 指导教师: 杜薇 工作单位: 计算机科学与技术学院 题 目: 进程调度模拟设计——先来先服务、强占式短进程优先算法 初始条件: 1(预备内容:阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。 2(实践准备:掌握一种计算机高级语言的使用。 要求完成的主要任务: (包括课程设计工作量及其技术要求，以及说明书撰写 等具体要求) 1(模拟进程调度，能够处理以下的情形: ? 能够选择不同的调度算法(要求中给出的调度算法); ? 能够输入进程的基本信息，如进程名、到达时间和运行时间等; ? 根据选择的调度算法显示进程调度队列; ? 根据选择的调度算法计算平均周转时间和平均带权周转时间。 2(设计 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 内容应说明: ? 需求分析; ? 功能设计(数据结构及模块说明); ? 开发平台及源程序的主要部分; ? 测试用例，运行结果与运行情况分析; ? 自我评价与 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf : i)你认为你完成的设计哪些地方做得比较好或比较出色; ii)什么地方做得不太好，以后如何改正; iii)从本设计得到的收获(在编写，调试，执行过程中的经验和教训); iv)完成本题是否有其他方法(如果有，简要说明该方法); v)对实验题的评价和改进意见，请你推荐设计题目。 时间安排: 设计安排一周:周1、周2:完成程序分析及设计。 周2、周3:完成程序调试及测试。 周4、周5:验收、撰写课程设计报告。 (注意事项:严禁抄袭，一旦发现，一律按0分记) 指导教师签名: 年 月 日 系主任(或责任教师)签名: 年 月 日 1 课程设计报告书 1. 课程设计的题目 进程调度模拟设计——先来先服务、强占式短进程优先算法。 2.课程设计的目的 此次课程设计的预备内容是阅读操作系统的处理机管理章节内容，并对进程调度的功能以及进程调度算法有深入的理解和掌握。 完成此次模拟进程调度，需要处理一下的情形: ? 能够选择不同的调度算法(先来先服务算法和强占式短进程优先 算法); ? 能够输入进程的基本信息(如进程名、到达时间和运行时间等); ? 根据选择的调度算法显示进程调度队列; ? 根据选择的调度算法计算平均周转时间和平均带权周转时间。 3.需求分析 进程调度模拟设计是本次课设的课题，根据其课程设计的目的和要求，对其需求分析如下所示: 3.1 对进程信息的描述和实现 此次课程设计中，进程作为基本数据处理单元，需要对进程的基本信息进行相关的描述。 进程的基本信息包括进程进程名，到达的时间以及预计的进程运行时间。设计一个模块，用以实现进程的基本信息的定义和封装，提高设计的简洁性，如使用类模块。 3.2 对调度算法的描述和实现 进程基本信息所构成的模块作为基本单元，并且相关调度算法的侧重进程基本信息点不同，所以要根据其调度算法的特点来结合基本信息进行对应的设计。此次课程设计要求的调度算法描述如下: 3.2.1 先来先服务调度算法 先来先服务调度算法是以进程的到达时间为判断标准，按各个进程所的到达时间先后顺序进行调度。 要实现此先来先服务调度算法以及考虑程序的简洁性，用一个数据结构如优先级队列，容器等来存储进程基本信息，并要对所有的进程按其到达时间先后顺序进行排序，实现依次取出的进程是所有未运行进程中到达时间最早的进程。 3.2.2 强占式短进程优先调度算法 2 此调度算法和先来先服务调度算法相区别，强占式短进程优先调度算法的实现相对而言较为复杂。 对强占式短进程优先调度算法而言，其本质特征便是按进程的预计运行时间长短进行排序，先执行短进程。 若内存中运行的进程优先级比就绪队列中的某进程优先级低(即运行的进程预计运行时间比就绪队列中的某进程长)，此运行的进程让出内存并进入就绪队列，优先级更高的短进程强占内存资源并运行直到结束或者遇到优先级更高的进程强占为止。 3.3计算平均周转时间和平均带权周转时间 平均周转时间和平均带权周转时间是对调度算法进行评估的参考标准，在此次课设中要求计算出平均周转时间和平均带钱周转时间。 平均周转时间可由所有进程的周转时间之和除以进程数，同理平均带权周转时间也可如此求得。 3.4 显示调度序列 按课程设计要求，要显示进程调度队列，并且还要求对平均周转时间和平均带权周转时间进行显示。 就先来先服务调度算法而言，要求显示的进程调度队列即是进程运行顺序(也就是进程到达时间先后顺序排序的队列);而强占式短进程优先级调度算法中，为了简洁便利的因素以及直观性，所以就以进程完成运行的先后时间顺序进行显示。 4.功能设计 此次课设采用面向对象的方法进行对此进程调度系统的模拟。以下分别就概要设计和详细设计先后进行功能设计的相关描述。 4.1 概要设计 根据课设要求和需求分析的结果，设计了两个类模板，即process类和dispatch类。 process类用以描述进程的信息，其数据域有进程名(name)，进程到达时间(start_time)，进程预计运行时间(run_time)。并设计了一个布尔变量bvisited标志进程是否运行结束，设计了一个变量end_time存储进程完全运行结束的时间点，用以辅助显示进程调度队列。Process类声明如下: class process{ friend std::istream& operator>>(std::istream& input,process& Process);//友元函数process输入流 friend std::ostream& operator<<(std::ostream& output,process& Process);//友元函数process输出流 friend bool compare_SF(process &pro1,process &pro2); 3 friend bool compare_FSFC(process &pro1,process &pro2); public: process(){}; process(string _name,double stime,double rtime); bool Set_bvisited(bool visited = true);//设定或修改结束标志 bool Get_bvisited();//取得结束标志 double GETstart_time();//取得进程到达时间 double GETrun_time();//取得进程预计运行时间 double SETend_time(double time);//设置和修改end_time的值 double GETend_time();//取得end_time的值 string GETname();//取得进程名 string SETname(string str);//设置或修改进程名 private: string name;//进程名 double start_time,run_time,end_time;//进程的到底时间，预计运行时间,完成时间 bvisited;//标志进程状态是否已经执行结束 bool }; dispatch类用以描述调度算法的实现，其数据域有进程个数(count)，总周转时间(Tse)，总带权周转时间(Wi)。在dispatch类中，还定义了一个优先级队列PQueue，一个普通队列Queue,以及一个vector容器。dispatch类的声明如下: class dispatch{ friend std::istream& 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_queue,compare_type> PQueue;//定义按到达时间顺序的队列PQueue queue Queue;//定义此队列表示完成的进程 vector vec; public: dispatch(bool sf_fc = true); void FCFS();//先来先服务调度算法 void Short_No1();//强占式短进程优先调度算法 4 void print();//显示调度队列的算法 }; dispatch类中PQueue队列用以存储所有输入的原有进程信息，并且其优先级是以到达时间的先后顺序而确定，即先到的进程排在前，后到的进程排在后。Vector容器用以支持强占式短进程优先调度算法的实现，存储所有在当前时间点已经到达的进程信息，并每次存入新的进程信息时便对此vector中元素进行排序，其排序要求按预计运行的时间长短，即预计运行时间较短的进程排在预计运行时间较长的进程前面。普通队列Queue用以存储完成运行的队列，其依旧按照队列的“先进先出”的属性，即把先运行完毕的进程排在前，后运行结束的进程排在后。 在此次设计中，设计了一个文本文档(lin.txt)用以存储进程信息，以文本的方式读入进程信息或写入进程信息，可以直接在lin.txt直接添加或删除进程信息。 设计了一个主函数，其中建立一个dispatch类对象，采用简单菜单模式。 4.2 详细设计 界面设计不是本次课程设计的要求，所以就使用dos命令窗口。而进程调度算法则是本次设计的核心部分，所以就此调度算法部分的逻辑进行阐释说明，进程调度算法的逻辑图如下所示: 4.2.1 main函数以及进程信息的输入 开始运行主函数 输出选择进程调度算调用进程调度算法 法的提示信息 否 调用显示进程调度 信息的算法print() 输入数据 满足要求 是 用delete语句撤 销dispatch对象 根据满足要求的输入，调用dispatch的 构造函数构生成相应的dispatch对象 结束主函数的运行 从文本文档lin.txt读入进程 信息 关闭lin/.txt文档 5 图1 4.2.2 先来先服务进程调度算法(FCFS) 调用FCFSS算法 按到达时间顺序排 列的PQueue进程 队列是否为空, 否 取出第PQueue中的队首元素，即 PQueue队列中到达时间最早的进程 察看当前进程 是否访问过, 输出错误提示 否 模拟运行该进程，对总周转时间，总带权周 转时间进行赋值，对end_time(结束时间) 点赋值。并把当前进程插入Queue队列，并 删除其在PQueue中的信息 队列PQueue 是否为空, 是 结束FCFS函数调用 图2 6 4.2.3 强占式短进程优先进程调度算法(SF) 调用SF算法 结束SF函数调用 是 PQueue队 列是空, 模拟当前进程运行结束，对总周转时间，总带否 权周转时间，以及运行结束时间点(end_time) 赋值。并把进程信息插入Queue队列，且删取PQueue队列第一个元素，即到达时 除其在vector中的进程信息 间最早的进程进行模拟运行，并计算出 不被强占情况下的结束时间点(atime) 取下一个运行进程的信息 在atime之前是是 否 否有进程到达, PQueue队Vector是 是 列为空, 否为空, 是 否 否 计算出当前系统时间点，并对运行中的进程进 行的预计运行时间进行设置(此处以未标志取vector第一个取PQueue队列 bvisited时的end_time表示)。并将此进程和的队首元素 元素模拟运行 所有其他新到达进程都插入vector之中进行 排序(排序按预计运行时间短在前长居后)， 删除新到达的进程在PQeuee队列中的信息 取出vector中的第一个元素进入模拟运行状态。 计算出此进程不被强占情况下的结束时间点 (atime) 图3 7 5 开发平台和源程序主要代码 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<<"共有进程数为"<= 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_queue,compare_type>(compare_1); cout<<"选择的是最短进程优先(抢占式)调度算法"<,compare_type>(compare_1); cout<<"选择的是先来先服务调度算法"<>(std::istream& input,dispatch& Dispatch){ process Pro1; int count1=0; while(input>>(Pro1)){ Dispatch.PQueue.push(Pro1); ++count1; } Dispatch.count = count1; cout<<"共有进程数为"<::iterator iter,iter1,iter2; process *ptr = &PQueue.top();//对队首元素的end_time()进行初始化 (*ptr).SETend_time( (*ptr).GETrun_time()); vec.push_back(PQueue.top());//取出第一个到达的进程,放入vector PQueue.pop(); iter=vec.begin(); ctime = (*iter).GETstart_time(); atime = (*iter).GETrun_time()+(*iter).GETstart_time(); while(count1>0){ 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();//取得修改后的到达时间队列中的新队首进程 11 } //找到优先级高的进程，则退出此循环，重新进行小进程运行并查找时候有更高优先级的进程到达 } else{ if(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());//取出第一个到达的进程,放入vector PQueue.pop(); iter=vec.begin(); ctime = (*iter).GETstart_time(); atime = (*iter).GETend_time()+(*iter).GETstart_time(); } break; } else{ iter =vec.begin(); atime = (*iter).GETend_time()+ctime; } } } 12 6.运行结果以及分析 6.1测试用例 假设有四个进程，其进程信息如下表所示: 进程名 到达时间 运行时间 P1 8:00 4:00 P2 9:00 2:00 P3 10:00 1:00 P4 11:00 2:00 6.2 运行结果 运行main函数后，dos命令窗口如下(图4): 输入数据 “3”后，显示结果如下(图5): 重新输入数据“1”后，显示如下(图6): 13 输入任意键开始，显示如下(图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中。 14 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进行进程信息的输入。在类模板中设定了输入输出流，利用此种重载的友元函数极大的提高了编程的效率。 同样，在此次的课程设计中存在着一些不足之处。 在对进程的到达时间以及运行时间的设计中，没有对时间的表示进行具体的设计和模拟，在此次课程设计中对时间的模拟直接采用十进制的形式，另外如果添加了标准时间制来设计进程信息将会取到更好的效果。在设计主函数时候，采用指针实现不同调度算法的选择。 此次课设还存在着一个健壮性的问题，先来先服务调度算法的健壮性较好，而强占式短进程优先级的健壮性就相较而言较差。因为此次的课设只是为了模拟出调度的过程，所以全采用整数的时间点。若采用小数的时间点，则强占式短进程优先级算法说求出的平均周转时间和平均带权周转时间将会不正确。 在此次课程设计过程中，对进程的相关知识有了一定的加深。特别是对进程的进程控制块的存在和价值有了更进一步的认识。在编写程序的过程之中，对进程自身信息的设计和管理以及调度的算法都有助于对书本知识的理解和掌握。 特别是设计先来先服务调度算法和强占式短进程优先调度算法的时候，对进程的调度算法有了更好的直观接触。对进程管理中的等待队列，就绪队列，优先级，强占式等概念有了更深刻的印象。 在设计此模拟进程调度的课设中，也加深了对c++知识的把握。解决了一些以往在编程中遇到了困难。通过此次的课程设计，不仅提高了对操作系统的认知， 15 也在同时提高了编程的能力，加强了实践。另外，我觉得我们的实验课题都是比较有代表性的，不仅体现了操作系统的知识点，也体现了其他学科的相关知识，但是像进程调度算法这样的侧重于一个调度算法的课程设计有些美中不足，不过鉴于时间的关系，这样的课程设计是最佳的，也是最适合我们现阶段实践的。 8.参考资料 计算机操作系统教程(第3版) 张尧学 史美林等编著 清华大学出版社 Accelerated C++中文版 (美)Andrew Koeing Barbara E.Moo 著 勒志伟 等译 16 本科生课程设计成绩评定表 班级: 计算机0903 姓名:方传强 学号:0120910340305 序号 评分项目 满分 实得分 1 10 学习态度认真、遵守纪律 2 10 设计分析合理性 3 20 设计方案正确性、可行性、创造性 4 40 设计结果正确性 5 10 设计报告的 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 性 6 10 设计验收 总得分/等级 评语: 注:最终成绩以五级分制记。优(90-100分)、良(80-89分)、中(70-79分)、 及格(60-69分)、60分以下为不及格 指导教师签名: 200 年 月 日 17