进程调度模拟设计——先来先服务、最高响应比优先调度算法

学 号： 012091034001

课 程 设 计

题 目 学 院 专 业 班 级 姓 名 指导教师

进程调度模拟设计——先来先服务、最高响应比优先调度算法

计算机科学与技术 计算机科学与技术 计算机009班

旭 汪 祥 莉

2012 年 1 月 9 日

武汉理工大学《计算机操作系统》课程设计

课程设计任务书

学生姓名： 旭 专业班级： 计算机009 指导教师： 汪祥莉 工作单位： 计算机科学与技术学院

题 目: 进程调度模拟设计——先来先服务、最高响应比优先调度算法

初始条件：

1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。

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

要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写

等具体要求）

1．模拟进程调度，能够处理以下的情形：

⑴ 能够选择不同的调度算法（要求中给出的调度算法）；

⑵ 能够输入进程的基本信息，如进程名、到达时间和运行时间等； ⑶ 根据选择的调度算法显示进程调度队列；

⑷ 根据选择的调度算法计算平均周转时间和平均带权周转时间。 2．设计报告内容应说明： ⑴ 课程设计目的与功能；

⑵ 需求分析，数据结构或模块说明(功能与框图)； ⑶ 源程序的主要部分；

⑷ 测试用例，运行结果与运行情况分析； ⑸ 自我评价与总结：

i）你认为你完成的设计哪些地方做得比较好或比较出色； ii）什么地方做得不太好，以后如何改正；

iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）； iv）完成本题是否有其他方法（如果有，简要说明该方法）； v）对实验题的评价和改进意见，请你推荐设计题目。

时间安排：

设计安排一周：周1、周2：完成程序分析及设计。

周2、周3：完成程序调试及测试。 周4、周5：验收、撰写课程设计报告。

（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）

指导教师签名： 年 月 日 系主任（或责任教师）签名： 年 月 日

武汉理工大学《计算机操作系统》课程设计

目录

1 设计题目 ................................ 1 2 需求分析 ................................ 1

2.1 功能需求 .................................... 1

2.1.1进程调度模拟设计先来先服务法.................. 1 2.1.2进程调度模拟设计最高响应比优先调度算法......... 2

2.2 环境需求 .................................... 3 2.3 用户界面需求 ................................ 3

3 功能设计 ................................ 3

3.1数据结构 ..................................... 3 3.2模块说明 ..................................... 4

4 开发平台及源程序的主要部分 ...............5

4.1 开发平台 ..................................... 5 4.2 源程序主要部分 ................................5

5 测试用例，运行结果与运行情况分析 .........6

5.1 测试用例 .................................... 6 5.2 运行结果 .....................................6

6 自我评价与总结 ..........................7 7 附加代码.................................8

武汉理工大学《计算机操作系统》课程设计

1. 设计题目

1. 先来先服务、最高响应比优先调度算法需求分析 模拟进程调度，能够处理以下的情形：

⑴ 能够选择不同的调度算法（要求中给出的调度算法）； ⑵ 能够输入进程的基本信息，如进程名、到达时间和运行时间等；

⑶ 根据选择的调度算法显示进程调度队列；

⑷ 根据选择的调度算法计算平均周转时间和平均带权周转时间。

2.1

功能需求

2.1.1 实现先来先服务法：

先来先服务算法基本思想：按照作业提交或进 程变为就绪状态的先后次序，调入系统或分派 CPU ，换句话说，调度程序每次选择的作业/ 进程是等待时间最久的，而不管其运行时间的 长短。这种调度算法突出的优点是实现简单， 效率较低，在一些实 际的系统和一般应用程 序中采用这种算法的较多。因此，在设计中， 首先对输入的各进程的提交时间进行比较，对

- 1 -

武汉理工大学《计算机操作系统》课程设计

先进入等待队列的进程提供服务。

2.1.2 实现最高响应比优先调度算法：

最高响应比优先法（HRN）是对FCFS方式和SJF 方式的一种综合平衡。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。

响应比R定义如下： R=(W+T)/T=1+W/T

其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。

每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF 之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF 法，从而采用HRN 方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，

- 2 -

武汉理工大学《计算机操作系统》课程设计

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

2.2 环境需求

开发环境、运行环境及开发语言： 开发环境：Windows平台＋Visual C++ 6.0 运行环境：Windows全系列平台 开发语言：C++

2.3 用户界面需求

输入输出均采用命令行界面。 格式如下： 首先 输入进程数。

其次 输入进程编号，姓名，到达时间，执行时间等 相关信息。

然后 选择算法，优先法或者是最高响应比算法。 最后，输出程序运行所得结果。

3 功能设计：

3.1 数据结构：

创建一个进程信息结构：

struct PCB {

string name;//进程名 float ta;//进程到达时间 float ts;//进程估计运行的时间 float tb;//进程开始运行时间 float tm;//进程仍需运行的时间 float to;//进程完成的时间 float rn;//进程运行的次数

- 3 -

武汉理工大学《计算机操作系统》课程设计

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;inext=NULL;

cout<<\"请依次输入第\"<>p1->name>>p1->ta>>p1->ts; p1->tm=p1->ts; p1->rn=1; p2->next=p1; }

return head; }

3.2 模块说明

首先选择调度算法，若选1先来先服务然则调用create（）

- 4 -

武汉理工大学《计算机操作系统》课程设计

创建进程队列，然后调用fcfsrun()进行先来先服务算法，后Goto到起始点。若选择2最高响应比算法则调用create（）创建进程队列，然后调用Hrn（）进行最高响应比算法，后Goto到起始点。若选择3则退出，选择其他则报错。

4 开发平台及源程序的主要部分：

4.1 开发平台：

开发环境、运行环境及开发语言：

开发环境：Windows平台＋Visual C++ 6.0

4.2 源程序主要部分：

struct PCB｛｝；//进程结构 #define MAX_NUM 15

int pronum;//定义进程数为pronum float total;//记录所有进程的总时间 double weight;//记录所有进程的带权周转时间 PCB *create(PCB *head);//创建进程队列 void deal(PCB *head);//FCFS记录处理

void sort(PCB *head);//将进程按到达的先后顺序排列 void fcfsrun(PCB *head);//先来先服务算法 void Hrn(PCB *head,int n);//最高响应比算法 void main(){}//主函数

- 5 -

武汉理工大学《计算机操作系统》课程设计

流程图如下： 1：先来 先服务 2：最高响应比 进程1信息 输入进程数 进程2信息 进程n信息 开始 3：退出 程序 5 测试用例，运行结果与运行情况分析：

5.1 测试用例：

正确的测试用例： 先来先服务算法结果：

- 6 -

武汉理工大学《计算机操作系统》课程设计

最高响应比结果：

其他：

六 自我评价与总结：

这次课程设计是让我们用已经学过的操作系统知识对先来先服务算法和最高响应比算法进行设计，使我在对进程调度的先来先服务和最高响应比优先算法充分理解的同时，也使我的实践编程能力和运用理论知识的能力得到进一步提高。

在此次实验中，我认为我比较出色的是自己一开始就有了一个整体的思路，不像以前的课程设计一样，对全局的规划不是很清楚，以至于在后来模块的衔接做得不到位，但是此次的设计由于初始就对各个功能块的相互调用也比较了解，所以对该课设的设计整体上比较轻松，也使程序的编写比较清晰。

- 7 -

武汉理工大学《计算机操作系统》课程设计

不过，在此次课设中我也出现了不少问题，尤其是在对先来先服务和最高响应比优先功能块的设计时，对其中每个进程之间的时间比较和响应比比较的具体代码还比较模糊，因此使得设计一度陷入了修改和编写中；此外，刚开始对程序的容错能力并未加入考虑的范围，所以使得程序的完整性和健壮性比较欠缺。所以，从中看出自己在具体细致的地方还约显不足，还有待提高。

通过此次课程设计，也使我见到对同一实验目的可以使用多种方法，C++的编程比较符合我们现在的编程设计能力，但是使用JAVA也可以完成相同功能，而且会使得某些步骤还比较简易。此外，使程序具有较强的容错能力也对程序设计的优劣性起到较为重要的因素。相信通过这次的设计，对我以后的学习和编程能力有一定的帮助。

七、附加代码

#include #include #include using namespace std; struct PCB {

string name;//进程名 float ta;//进程到达时间 float ts;//进程估计运行的时间 float tb;//进程开始运行时间 float tm;//进程仍需运行的时间 float to;//进程完成的时间 float rn;//进程运行的次数 float totalTime;//周转时间

- 8 -

武汉理工大学《计算机操作系统》课程设计

double weightTotalTime;//带权周转时间(周转时间/估计运行时间）

PCB *next;//定义指向下一个进程的指针 };

#define MAX_NUM 15

int pronum;//定义进程数为pronum float total;//记录所有进程的总时间 double weight;//记录所有进程的带权周转时间

PCB *create(PCB *head);//创建进程队列 void deal(PCB *head);//FCFS记录处理

void sort(PCB *head);//将进程按到达的先后顺序排列 void fcfsrun(PCB *head);//先来先服务算法 void Hrn(PCB *head,int n); void main() {

int choice;

cout<<\"*进程调度模拟设计——先来先服务、最高响应比优先算法*\"<cout<<\"***********1. cout<<\"***********2. cout<<\"***********3

l1: cout<<\"请输入您的选择：\"<>choice; PCB *head=NULL;

- 9 -

先最

高

来响

先应退

服比

务优

先

算算

法法出

***************************\"<*************************************\"<武汉理工大学《计算机操作系统》课程设计

switch(choice) {

case 1:head=create(head);fcfsrun(head);goto l1; case 2:head=create(head);Hrn(head,pronum);goto l1; case 3:break;

default:cout<<\"输入错误！\\n请重新输入：\"<PCB *create(PCB *head) {

PCB *p1,*p2; p1=p2=new PCB; head=p1;

cout<<\"请输入进程数：\"; cin>>pronum;

for(int i=0;inext=NULL;

cout<<\"请依次输入第\"<cin>>p1->name>>p1->ta>>p1->ts; p1->tm=p1->ts; p1->rn=1; p2->next=p1; }

return head;

- 10 -

武汉理工大学《计算机操作系统》课程设计

}

void sort(PCB *head)//将进程按到达的先后顺序排列 {

PCB *p,*q,*r,*s; if(head->next!=NULL) {

p=head->next->next; head->next->next=NULL; } while(p) { q=p; p=p->next; r=head; s=head->next;

while(s&&s->ta<=q->ta) { r=s; s=s->next; }

r->next=q; q->next=s; } }

void deal(PCB *head)//FCFS记录处理 {

sort(head);

- 11 -

武汉理工大学《计算机操作系统》课程设计

PCB *p,*q;

q=head->next; q->tb=q->ta; q->to=q->tb+q->ts; q->totalTime=q->to-q->ta;

q->weightTotalTime=q->totalTime/(double)q->ts; total+=q->totalTime; weight+=q->weightTotalTime;

p=q->next; while(p!=NULL) {

p->tb=q->to; p->to=p->tb+p->ts; p->totalTime=p->to-p->ta;

p->weightTotalTime=p->totalTime/(double)p->ts; total+=p->totalTime; weight+=p->weightTotalTime; q=p; p=p->next; } }

void fcfsrun(PCB *head)//先来先服务算法 {

- 12 -

武汉理工大学《计算机操作系统》课程设计

deal(head); PCB *p,*q,*s; p=head->next;

cout<<\"进程执行顺序为：\"; while(p!=NULL) {

cout<<\"--\"<name; p=p->next; }

cout<cout<<\"进程名 提交时间 开始时间 结束时间 周转时间 带权周转时间\\n\"; s=head->next; while(s!=NULL) {

cout<name<ta<tb<to<totalTime<weightTotalTime<next; }

cout<cout<<\" 平均周转时间：\"<- 13 -

武汉理工大学《计算机操作系统》课程设计

//最高响应比算法函数 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;sscout<<\" 顺序 进程名 提交时间 开始时间 结束时间 周转时间 带权周转时间\\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)

- 14 -

> (time -

武汉理工大学《计算机操作系统》课程设计

flag->ta)/(flag->ts)) flag=q; q=q->next; }

if(time < flag->ta)//如果上一次结束时间比当前选中要执行进程的结束时间小

time=flag->ta; //则当前进程开始时间为提交时间 //输出当前执行进程的信息 cout<name; cout<ts; cout<cout<ts);

cout<ta + flag->ts); cout<<\"

\"<ta

+

flag->ts)/flag->ts)<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

{ //在链表中

- 15 -

武汉理工大学《计算机操作系统》课程设计

p1=head;

while(p1->next!=flag) p1=p1->next; p1->next=flag->next;

delete flag; //删除这个进程所占的节点 } }

cout<<\"进程执行顺序为：\"; for(ss=0;sscout< \"; }

cout<cout<<\" 平均周转时间为：\"<- 16 -

武汉理工大学《计算机操作系统》课程设计

本科生课程设计成绩评定表

班级： 计算机009 姓名： 旭 学号：012091034001 序号 1 2 3 4 5 6 评分项目 学习态度认真、遵守纪律 设计分析合理性 设计方案正确性、可行性、创造性 设计结果正确性 设计报告的规范性 设计验收 满分 10 10 20 40 10 10 总得分/等级 实得分 评语： 注：最终成绩以五级分制记。优（90-100分）、良（80-分）、中（70-79分）、

及格（60-69分）、60分以下为不及格

指导教师签名：

201 年 月 日

- 17 -