课程设计任务书学生姓名：闫敏专业班级：计科1103班指导教师：蔡菁工作单位：计算机科学与技术学院题目: 进程调度模拟设计——先来先服务、最高响应比优先调度算法初始条件：1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。

2．实践准备：掌握一种计算机高级语言的使用。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1．模拟进程调度，能够处理以下的情形：⑴能够选择不同的调度算法（要求中给出的调度算法）；⑵能够输入进程的基本信息，如进程名、到达时间和运行时间等；⑶根据选择的调度算法显示进程调度队列；⑷根据选择的调度算法计算平均周转时间和平均带权周转时间。

2．设计报告内容应说明：⑴课程设计目的与功能；⑵需求分析，数据结构或模块说明(功能与框图)；⑶源程序的主要部分；⑷测试用例，运行结果与运行情况分析；⑸自我评价与总结。

时间安排：设计安排3周：查阅、分析资料 1天系统软件的分析与建模 4天系统软件的设计 5天系统软件的实现 3天撰写文档 1天课程设计验收答辩 1天设计验收安排：设计周的第三周的指定时间到实验室进行上机验收。

设计报告书收取时间：课程设计验收答辩完结时。

（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名： 2013 年 12 月 10日系主任（或责任教师）签名： 2013 年 12 月 10日目录1.课程设计目的与功能 (3)2.需求分析与模块说明 (3)2.1需求分析 (3)2.1.1功能需求 (3)2.1.2环境需求 (4)2.1.3用户界面需求 (4)2.2模块说明 (5)3.源程序的主要部分 (5)3.1数据结构 (5)3.2主要函数 (7)4.测试用例，运行结果与运行情况分析 (10)4.1测试用例 (10)4.2运行结果分析 (12)5.自我评价与总结 (12)6. 附录 (13)1.课程设计目的与功能模拟进程调度，能够处理以下的情形：⑴能够选择不同的调度算法（要求中给出的调度算法）；⑵能够输入进程的基本信息，如进程名、到达时间和运行时间等；⑶根据选择的调度算法显示进程调度队列；⑷根据选择的调度算法计算平均周转时间和平均带权周转时间。

2.需求分析与模块说明2.1需求分析2.1.1功能需求（1）实现先来先服务法：先来先服务算法基本思想：按照作业提交或进程变为就绪状态的先后次序，调入系统或分派CPU ，换句话说，调度程序每次选择的作业进程是等待时间最久的，而不管其运行时间的长短。

这种调度算法突出的优点是实现简单，效率较低，在一些实际的系统和一般应用程序中采用这种算法的较多。

因此，在设计中，首先对输入的各进程的提交时间进行比较，对先进入等待队列的进程提供服务。

（2）实现最高响应比优先调度算法：最高响应比优先法（HRN）是对FCFS方式和SJF 方式的一种综合平衡。

HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。

响应比R 定义如下：R=(W+T)/T=1+W/T其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。

每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。

这样，即使是长作业，随着它等待时间的增加，W/T也就随着增加，也就有机会获得调度执行。

这种算法是介于FCFS和SJF 之间的一种折中算法。

由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF 法，从而采用HRN 方式时其吞吐量将小于采用SJF 法时的吞吐量。

另外，由于每次调度前要计算响应比，系统开销也要相应增加。

2.1.2环境需求开发环境、运行环境及开发语言：开发环境：Windows平台＋Visual C++ 6.0运行环境：Windows全系列平台开发语言：C++2.1.3用户界面需求输入输出均采用命令行界面，格式如下：首先，输入进程数；其次，输入进程编号、进程名、到达时间、执行时间等相关信息；然后，选择算法，先来先服务算法或最高响应比算法；最后，输出程序运行所得结果。

2.2模块说明程序流程图如下：首先选择调度算法，若选1先来先服务然则调用create （）创建进程队列，然后调用fcfsrun()进行先来先服务算法，后Goto 到起始点。

若选择2最高响应比算法则调用create （）创建进程队列，然后调用Hrn （）进行最高响应比算法，后Goto 到起始点。

若选择3则退出，选择其他则报错。

3.源程序的主要部分3.1数据结构创建一个进程信息结构：struct PCB开始 1：先来 先服务 2：最高响应比 3：退出 程序输入进程数 进程1信息 进程2信息 进程n 信息{string name;//进程名float ta;//进程到达时间float ts;//进程估计运行的时间float tb;//进程开始运行时间float tm;//进程仍需运行的时间float to;//进程完成的时间float rn;//进程运行的次数float totalTime;//周转时间double weightTotalTime;//带权周转时间(周转时间/估计运行时间）PCB *next;//定义指向下一个进程的指针};此外，对输入信息进行创建链表队列：PCB *create(PCB *head){PCB *p1,*p2;p1=p2=new PCB;head=p1;cout<<"请输入进程数：";cin>>pronum;for(int i=0;i<pronum;i++){p2=p1;p1=new PCB;p1->next=NULL;cout<<"请依次输入第"<<i+1<<"个进程的信息(进程名、到达时间、估计运行时间)：";cin>>p1->name>>p1->ta>>p1->ts;p1->tm=p1->ts;p1->rn=1;p2->next=p1;}return head;}3.2主要函数struct PCB｛｝；//进程结构#define MAX_NUM 15PCB *create(PCB *head);//创建进程队列void deal(PCB *head);//FCFS记录处理void sort(PCB *head);//将进程按到达的先后顺序排列void fcfsrun(PCB *head);//先来先服务算法void Hrn(PCB *head,int n);//最高响应比算法void main(){}//主函数其中先来先服务算法和最高响应比算法具体如下：void fcfsrun(PCB *head)//先来先服务算法{deal(head);PCB *p,*q,*s;p=head->next;cout<<"进程执行顺序为：";while(p!=NULL){cout<<"--"<<p->name;p=p->next;}cout<<endl;cout<<"进程名提交时间开始时间结束时间周转时间带权周转时间\n";s=head->next;while(s!=NULL){cout<<setw(4)<<s->name<<setw(7)<<s->ta<<setw(10)<<s->tb<<setw(11)<<s->t o<<setw(10)<<s->totalTime<<setw(10)<<s->weightTotalTime<<endl;s=s->next;}cout<<endl;cout<<" 平均周转时间："<<total/(double)pronum<<endl;cout<<"平均带权周转时间："<<weight/(double)pronum<<endl;cout<<"******************************************************"<<en dl;total=0;weight=0;}//最高响应比算法函数void Hrn(PCB *head,int n){PCB *p,*p1;PCB *flag=NULL;PCB *q=NULL;double time=0,j=0,runTime=0, drunTime=0;int xuhao=0;string pname[MAX_NUM];for(int ss=0;ss<MAX_NUM;ss++)pname[ss]="";sort(head);cout<<endl;cout<<" 顺序进程名提交时间开始时间结束时间周转时间带权周转时间\n";head=head->next;p=head;while(head){q=head;if(time < p->ta) //如果该进程提交时间早于其它进程，则先执行该进程time=p->ta;flag=head; //用于暂存将要执行的进程//计算当前链表中进程的响应比while(q && q->ta <= time){if((time - q->ta)/(q->ts) > (time - flag->ta)/(flag->ts))flag=q;q=q->next;}if(time < flag->ta)//如果上一次结束时间比当前选中要执行进程的结束时间小time=flag->ta; //则当前进程开始时间为提交时间//输出当前执行进程的信息cout<<setw(4)<<xuhao+1;cout<<setw(8)<<flag->name;cout<<setw(8)<<flag->ta;cout<<setw(8)<<time;cout<<setw(10)<<(time + flag->ts);cout<<setw(10)<<(time - flag->ta + flag->ts);cout<<" "<<setw(11)<<(double)((time-flag->ta + flag->ts)/flag->ts)<<endl;j=(time-flag->ta+flag->ts); //当前执行进程的周转时间runTime +=j; //记录周转时间time+=flag->ts;drunTime+=j/flag->ts; //带权周转时间pname[xuhao]=flag->name;xuhao++;//将执行过的进程从链表中删除if(flag==head) //在链表头head=head->next;else{ //在链表中p1=head;while(p1->next!=flag)p1=p1->next;p1->next=flag->next;delete flag; //删除这个进程所占的节点}}cout<<"进程执行顺序为：";for(ss=0;ss<n;ss++){cout<<pname[ss];if(pname[ss+1] !="")cout<<" -> ";}cout<<endl;cout<<" 平均周转时间为："<<runTime/n<<endl;cout<<"平均带权周转时间为："<<drunTime/n<<endl;cout<<"******************************************************"<<en dl;}4.测试用例，运行结果与运行情况分析4.1测试用例（1）先来先服务算法（2）响应比优先算法输入错误4.2运行结果分析对以上测试用例进行分析，用这两种调度算法所得的进程执行顺序正确，其平均周转时间和平均带权周转时间也是正确。