操作系统课程设计进程调度模拟设计-先来先服务(共29页).doc

1、学 号： 课 程 设 计课程名字系统软件开发实训A题 目进程调度模拟设计先来先服务、优先级法学 院计算机科学与技术学院专 业计算机科学与技术专业班 级姓 名指导教师李玉强2014年01月13日课程设计任务书学生姓名： 专业班级： 指导教师： 李玉强 工作单位： 计算机科学与技术学院 题 目: 进程调度模拟设计先来先服务、优先级法 初始条件：1预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1模拟进程调度，能够处理以下的情形： 能够

2、选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。2设计报告内容应说明： 课程设计目的与功能； 需求分析，数据结构或模块说明(功能与框图)； 源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结。时间安排：设计安排3周：查阅、分析资料 1天系统软件的分析与建模 4天系统软件的设计 5天系统软件的实现 3天撰写文档 1天课程设计验收答辩 1天设计验收安排：设计周的第三周的指定时间到实验室进行上机验收。设计报告书收取时间：课程设

3、计验收答辩完结时。（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名： 2013 年 12 月 10日系主任（或责任教师）签名： 2013 年 12 月 10日课程设计报告书1.需求分析 1.1设计目的(1)阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。(2)掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1.2程序流程图开 始选择调度算法先来先服务法输入进程队列信息优先级法结束？Y/N结 束YN切 换 算 法1.3设计要求(1)能够选择不同的调度算法（要求中给出的调度算法）；

4、(2)能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等；(3)根据选择的调度算法显示进程调度队列；(4)根据选择的调度算法计算平均周转时间和平均带权周转时间。2.功能设计 2.1数据结构1. 进程的结构定义：struct processchar name10; /进程名int no; /进程序号double arrivetime; /进程达到时间double needtime; /进程运行时间 double starttime; /进程开始时间double endtime; /进程结束时间int state; /进程状态，0表示未执行，1表示已执行int priority; /进

5、程优先级process *next; process *head=Null;int count; ；2.使用链表存储进程并按照到达时间排序、开始链表空？只有一节点比较当前节点的到达时间与连续两个节点（p1,p1->next）的到达时间至少两个节点结 束YN插 到 链 头比较当前节点与已存在节点的到达时间在两节点之间？插入它们之间插 入p1=p1->nextvoid insert(process *current) if (head!=Null)if(head->next=Null) /如果只有一个节点if(current->arrivetime<head->

6、arrivetime) /如果比链头到达时间早，则插入链头current->next=head;head=current;elsecurrent->next=Null;head->next=current; else /如果至少两个节点 process *p1=head; if(head->arrivetime >current->arrivetime ) current->next=head; head=current; else int flag=1; while(p1->next!=Null) /当head后面不为空时一直做 /如果在两个节

7、点间 if(p1->arrivetime < current->arrivetime && p1->next->arrivetime > current->arrivetime) current->next=p1->next; p1->next=current; flag=0; break; else p1=p1->next; /如果到达时间最大，则插到链尾 if (flag=1) p1->next=current; current->next=Null; else head=current;2.2先

8、来先服务算法设计 1.FCFS算法说明将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。在该算法中，每个作业或进程按照它们在队列中等待时间长短来决定它们是否优先享受服务。在没有特殊理由要优先调度某类作业或进程时，从处理的角度来看，FCFS方式是一种最合适的方法，因为无论是追加还是取出一个队列元素在操作上都是最简单的。2.创建进程void createFCFS() process *q1=new process ; cout<<"请输入进程总数目" cin>>count; cou

9、t<<endl; int number=1; while(number<=count) q1=new process; q1->no=number; cout<<"进程序号"<<number<<endl; cout<<"进程名称" cin>>q1->name; cout<<"进程到达时间" cin>>q1->arrivetime; cout<<"进程运行时间" cin>>q

10、1->needtime; q1->next=NULL; insert(q1); number+; cout<<endl<<endl; 3.进程调度及输出结果开 始链表空？Head节点：开始时间=到达时间 结束时间=开始时间+执行时间 系统时间=结束时间并计算周转时间和带权周转时间P=head->nextP=null结 束YN前一个结束，后一个进程是否到达p节点：开始时间=到达时间 结束时间=开始时间+执行时间 系统时间=结束时间并计算周转时间和带权周转时间P=head->nextNp节点：开始时间=系统时间 结束时间=开始时间+执行时间 系统时间

11、=结束时间并计算周转时间和带权周转时间P=head->nextYvoid printFCFS() process *p=new process; double systime=0; /记录系统时间 double turn=0; /平均周转时间 double turnw=0; /平均带权周转时间 if(head=NULL) cout<<"没有进程调度"<<endl; /处理第一个 else if(head!=NULL) head->starttime=head->arriveTime; head->endtime=head-&g

12、t;arrivetime+head->needtime; systime=head->endtime; turn=turn+(head->endtime - head->arrivetime); turnw=turnw+(head->endtime - head->arrivetime) / head->needtime; p=head->next; while(p!=NULL) if(p->arrivetime>systime) /如果前一个结束后一个还没到达 p->starttime=p->arrivetime; p-

13、>endtime=p->starttime+p->needtime; systime=p->endTime; turn=turn+(p->endtime-p->arrivetime); turnw=turnw+(p->endtime-p->arrivetime)/p->needtime; p=p->next; else /如果前一个未结束时后一个已经到达 p->starttime=systime; p->endtime=p->starttime+p->needtime; systime=p->endtim

14、e; turn=turn+(p->endtime-p->arrivetime); turnw=turnw+(p->endtime-p->arrivetime)/p->needtime; p=p->next; cout.setf(ios:left); /设置对齐方式为left cout<<setw(10)<<"进程序号"<<setw(10)<<"进程名"<<setw(10)<<"到达时间"<<setw(10)<&

15、lt;"开始时间"<<setw(10)<<"执行时间"<<setw(10)<<"结束时间"<<endl; process *temp=head; while(temp!=NULL) cout.setf(ios:left); cout<<setw(10)<<temp->no<<setw(10)<<temp->name<<setw(10)<<temp->arriveTime<<s

16、etw(10)<<temp->startTime<<setw(10)<<temp->needTime<<setw(10)<<temp->endTime<<endl; temp=temp->next; cout<<"平均周转时间"<<turn/count<<endl<<"平均带权周转时间"<<turnw/count<<endl; /清空链表 while(head->next!=NULL

17、) /回收空间 process *t=new process; t=head->next; head->next=t->next; delete t; head=NULL; 2.3 优先级算法的设计1.PIRO算法及说明 优先级法可被用作作业或进程的调度策略。首先，系统或用户按某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权。该算法的核心是确定进程或作业的优先级。 确定优先级的方法可分为两类。即动态法和静态法静态法根据作业或进程的静态特性，在作业或进程开始执行之前就确定它们的优先级，一旦开始执行之后就不能改变。动态法则不然，它把作业或进程的静态特性和动态

18、特性结合起来确定作业或进程的优先级，随着作业或进程的执行过程，其优先级不断变化。 静态优先级中，可以由用户自己根据作业的紧急程度输入一个适当的优先级，为防止各用户都将自己的作业冠以高优先级，系统应对高优先级用户收取较高的费用；也可以由系统或操作员根据作业类型指定优先级。动态优先级中，基于静态优先级的调度算法实现简单，系统开销小，但由于静态优先级一旦确定之后，直到执行结束为止始终保持不变，从而系统效率较低，调度性能不高。现在的操作系统中，如果使用优先级调度的话，则大多采用动态优先级的调度策略。2.创建进程void createPRIO() process *q1=new process; cou

19、t<<"请输入进程总数目" cin>>count; cout<<endl; int number=1; while(number<=count) q1=new process; q1->no=number; cout<<"进程序号"<<number<<endl; cout<<"进程名称" cin>>q1->name; cout<<"优先级" cin>>q1->priorit

20、y; cout<<"进程到达时间" cin>>q1->arriveTime; cout<<"进程运行时间" cin>>q1->needTime; q1->next=NULL; insert(q1); number+; cout<<endl<<endl; 3.把最先达到的进程的排在链头，后面的进程按优先级大小重新排序void changePRIO(double systime) /把最先到达的放到链头 然后后面的结点按照优先级来排序 /排序的前提是结点数至少是3个 从

21、第二个开始和后面的比较 if(count>2) process *n0=head; process *n1=n0->next; process *n2=n1->next; for(int i=0;i<count-1;i+) while(n1!=NULL && n2!=NULL && n1->arrivetime <= systime && n2->arrivetime <= systime) /如果前面的优先级大于后面的优先级，则交换 if(n1->priority < n2->p

22、riority) n1->next=n2->next; n0->next=n2; n2->next=n1; n1=n0->next; n2=n0->next->next; n0=n1; n1=n2; n2=n2->next; 4.输出调度结果开 始链表空？Head节点：开始时间=到达时间 结束时间=开始时间+执行时间 系统时间=结束时间并计算周转时间和带权周转时间P=head->nextP=null结 束N到达&&未执行p节点：开始时间=系统时间 结束时间=开始时间+执行时间 系统时间=结束时间标记为已执行并计算周转时间和带

23、权周转时间P=head->nextYvoid printPRIO() process *p=new process; double sysTime=0; /记录系统时间 double turn=0; /平均周转时间 double turnw=0; /平均带权周转时间 if(head=NULL) cout<<"没有进程调度！"<<endl; else /先把最先到达的输出，然后再根据系统时间和优先级判断后续的进程 head->starttime=head->arrivetime; head->endtime=head->a

24、rrivetime+head->needtime; head->state=1; systime=head->endtime; turn=turn+(head->endtime - head->arrivetime); turnw=turnw+(head->endtime - head->arrivetime) / head->needtime; /判断后面的 for(int i=0;i<count-1;i+) p=head->next; while(p!=NULL) changePRIO(double systime); /如果优先

25、级最大的进程已经到达，则执行 if(p->arrivetime <= systime && p->state=0) p->starttime=systime; p->endtime=p->arrivetime+p->needtime; systime=p->endtime; p->state=1; turn=turn+(p->endtime-p->arrivetime); turnw=turnw+(p->endtime-p->arrivetime)/p->needtime; p=p->ne

26、xt; else p=p->next; process *temp=head; cout.setf(ios:left); cout<<setw(10)<<"进程序号"<<setw(10)<<"进程名"<<setw(10)<<"优先级"<<setw(10)<<"到达时间"<<setw(10)<<"开始时间"<<setw(10)<<"执行时间

27、"<<setw(10)<<"结束时间"<<endl; while(temp!=NULL) cout<<setw(10)<<temp->no<<setw(10)<<temp->name<<setw(10)<<temp->priority<<setw(10)<<temp->arriveTime<<setw(10)<<temp->startTime<<setw(10)<

28、<temp->needTime<<setw(10)<<temp->endTime<<endl; temp=temp->next; cout<<"平均周转时间："<<turn/count<<endl<<"平均带权周转时间："<<turnw/count<<endl; while(head->next!=NULL) process *t=new process; t=head->next; head->next=

29、t->next; delete t; head=NULL; 3. 源程序的主要部分 主程序主要完成调用各个函数完成相应的功能，以及选择调度算法的输出提示，根据提示并完成相应的算法实现过程。/程序主要部分int main()int choice; /选择服务int go=1;while (go)cout<<endl<<endl<<"-"<<"进程调度模拟设计"<<"-"<<endl<<endl; cout<<"1.先来先服务算

30、法"<<endl<<"2.优先级法"<<endl<<"3.退出"<<endl<<endl;cout<<"请选择："cin>>choice；switch(choice) case 1:FCFS();break; /调用先来先服务算法 case 2:PRIO();break; /调用优先计算法 case 3:cout<<"退出"<<endl; go=0;break; /退出，返回首页 def

31、ault:cout<<"选择有误，请重新输入选择！"<<endl;break;system("pause");return 0;void FCFS() createFCFS(); printFCFS(); void PRIO() createPRIO(); /changePRIO(); printPRIO(); 4.程序测试4.1先来先服务测试用例进程序号进程名称到达时间执行时间1a042b133c224d334.2先来先服务运行结果进程序号进程名称优先级到达时间执行时间1a1042b4163c2244d3354.3先来先服务测试

32、用例4.4优先级算法运行结果5.自我评价与总结本次课程设计的内容基本上是老师在课堂上所讲的，所以我还是比较熟悉先来先服务算法和优先级算法。看到这个题目时，我还是感觉相当轻松的，因为我还是比较熟悉该内容，比较熟悉算法思想。设计过程中要注意流程的条理清晰，易于读懂和规划，程序编写完成以后，实现了预期的效果，达到了设计的要求。界面设计比较清晰明了，易于阅读和理解。本程序中，有些地方有重复，可以通过设计函数来简化程序，例如程序的创建，可以通过函数调用来实现，从而不必在两个算法中分别编写。编写程序时要先画出程序的流程图是非常有必要的，根据流程图的顺序来实现程序，并要注意合理的使用函数调用来使程序得到简化

33、，并且易读易懂。编写程序的时候一定要先画流程图，对应流程图设计函数来简化程序。这次课程设计中比较失败的地方就是优先级算法的输出开始时间和结束时间出了点问题。 这次课程设计使得我受益匪浅，尤其是对优先级调度分析方法有了更深的理解和掌握。通过这次课程设计，我的编程能力又得到了进一步的提高，同时也培养了我的思维能力。总的说来，这次课程设计不仅丰富了我的理论知识，也加强了我的动手能力，还锻炼了我的思维能力。在实验程序编写和调试过程中我学会了很多，也认识到了自己的不足，我还需要进一步的努力，以致取得更大的进步。我需要的就是要对自己有信心，脚踏实地，持之以恒，遇到困难时要冷静思考，勇敢面对，直到得出结果。

34、在实验设计过程中，我也养成了较好地习惯，先有框架，然后跟着框架发展，最后就是要注重细节，要做到严谨和缜密。不可否认这种好习惯让我受益无限，我也必须拥有它，以致我获得更多。6.源程序#include<iostream.h>#include<stdlb.h>#include<iomanip.h>struct processchar name10; /进程名int no; /进程序号double arrivetime; /进程达到时间double needtime; /进程运行时间 double starttime; /进程开始时间double endtime;

35、/进程结束时间int state; /进程状态int priority; /进程优先级process *next; process *head=Null;int count; ；void FCFS();void PRIO();void createFCFS();void insert(process *current); void printFCFS();void createPRIO();void changePRIO(double systime); void printPRIO() ;/程序主要部分int main()int choice; /选择服务int go=1;while (go

36、)cout<<endl<<endl<<"-"<<"进程调度模拟设计"<<"-"<<endl<<endl; cout<<"1.先来先服务算法"<<endl<<"2.优先级法"<<endl<<"3.退出"<<endl<<endl;cout<<"请选择："cin>>choi

37、ce；switch(choice) case 1:FCFS();break; /调用先来先服务算法 case 2:PRIO();break; /调用优先计算法 case 3:cout<<"退出"<<endl; go=0;break; /退出，返回首页 default:cout<<"选择有误，请重新输入选择！"<<endl;break;system("pause");return 0;void FCFS() createFCFS(); printFCFS(); void PRIO() cr

38、eatePRIO(); /changePRIO(); printPRIO(); /使用链表结构 按达到时间的顺序将进程进行排序void insert(process *current) if (head!=Null)if(head->next=Null) /如果只有一个节点if(current->arrivetime<head->arrivetime) /如果比链头到达时间早，则插入链头current->next=head;head=current;elsecurrent->next=Null;head->next=current; else /如果至

39、少两个节点 process *p1=head; if(head->arrivetime >current->arrivetime ) current->next=head; head=current; else int flag=1; while(p1->next!=Null) /当head后面不为空时一直做 /如果在两个节点间 if(p1->arrivetime < current->arrivetime && p1->next->arrivetime > current->arrivetime) cur

40、rent->next=p1->next; p1->next=current; flag=0; break; else p1=p1->next; /如果到达时间最大，则插到链尾 if (flag=1) p1->next=current; current->next=Null; else head=current;void createFCFS() process *q1=new process ; cout<<"请输入进程总数目" cin>>count; cout<<endl; int number=1;

41、 while(number<=count) q1=new process; q1->no=number; cout<<"进程序号"<<number<<endl; cout<<"进程名称" cin>>q1->name; cout<<"进程到达时间" cin>>q1->arrivetime; cout<<"进程运行时间" cin>>q1->needtime; q1->next=

42、NULL; insert(q1); number+; cout<<endl<<endl; void printFCFS() process *p=new process; double systime=0; /记录系统时间 double turn=0; /平均周转时间 double turnw=0; /平均带权周转时间 if(head=NULL) cout<<"没有进程调度"<<endl; /处理第一个 else if(head!=NULL) head->starttime=head->arriveTime; he

43、ad->endtime=head->arrivetime+head->needtime; systime=head->endtime; turn=turn+(head->endtime - head->arrivetime); turnw=turnw+(head->endtime - head->arrivetime) / head->needtime; p=head->next; while(p!=NULL) if(p->arrivetime>systime) /如果前一个结束后一个还没到达 p->starttim

44、e=p->arrivetime; p->endtime=p->starttime+p->needtime; systime=p->endTime; turn=turn+(p->endtime-p->arrivetime); turnw=turnw+(p->endtime-p->arrivetime)/p->needtime; p=p->next; else /如果前一个未结束时后一个已经到达 p->starttime=systime; p->endtime=p->starttime+p->needtime

45、; systime=p->endtime; turn=turn+(p->endtime-p->arrivetime); turnw=turnw+(p->endtime-p->arrivetime)/p->needtime; p=p->next; cout.setf(ios:left); /设置对齐方式为left cout<<setw(10)<<"进程序号"<<setw(10)<<"进程名"<<setw(10)<<"到达时间"

46、;<<setw(10)<<"开始时间"<<setw(10)<<"执行时间"<<setw(10)<<"结束时间"<<endl; process *temp=head; while(temp!=NULL) cout.setf(ios:left); cout<<setw(10)<<temp->no<<setw(10)<<temp->name<<setw(10)<<temp-&

47、gt;arriveTime<<setw(10)<<temp->startTime<<setw(10)<<temp->needTime<<setw(10)<<temp->endTime<<endl; temp=temp->next; cout<<"平均周转时间"<<turn/count<<endl<<"平均带权周转时间"<<turnw/count<<endl; /清空链表 whi

48、le(head->next!=NULL) /回收空间 process *t=new process; t=head->next; head->next=t->next; delete t; head=NULL; void createPRIO() process *q1=new process; cout<<"请输入进程总数目" cin>>count; cout<<endl; int number=1; while(number<=count) q1=new process; q1->no=number

49、; cout<<"进程序号"<<number<<endl; cout<<"进程名称" cin>>q1->name; cout<<"优先级" cin>>q1->priority; cout<<"进程到达时间" cin>>q1->arriveTime; cout<<"进程运行时间" cin>>q1->needTime; q1->next=N

50、ULL; insert(q1); number+; cout<<endl<<endl; void changePRIO(double systime) /把最先到达的放到链头 然后后面的结点按照优先级来排序 /排序的前提是结点数至少是3个 从第二个开始和后面的比较 if(count>2) process *n0=head; process *n1=n0->next; process *n2=n1->next; for(int i=0;i<count-1;i+) while(n1!=NULL && n2!=NULL &&am

51、p; n1->arrivetime <= systime && n2->arrivetime <= systime) /如果前面的优先级大于后面的优先级，则交换 if(n1->priority < n2->priority) n1->next=n2->next; n0->next=n2; n2->next=n1; n1=n0->next; n2=n0->next->next; n0=n1; n1=n2; n2=n2->next; void printPRIO() process *p=new