优先级法最高响应比优先调度算法.docx

优先级法最高响应比优先调度算法.docx

《优先级法最高响应比优先调度算法.docx》由会员分享，可在线阅读，更多相关《优先级法最高响应比优先调度算法.docx（46页珍藏版）》请在冰点文库上搜索。

优先级法最高响应比优先调度算法

学号：

课程设计

题目

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

学院

计算机科学与技术

专业

班级

姓名

指导教师

吴利军

2013

年

1

月

15

日

课程设计任务书

学生姓名：

指导教师：

吴利军工作单位：

计算机科学与技术学院

题目:

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

初始条件：

1．预备内容：

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

2．实践准备：

掌握一种计算机高级语言的使用。

要求完成的主要任务:

（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）

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

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

⑵能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等；

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

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

2．设计报告内容应说明：

⑴需求分析；

⑵功能设计（数据结构及模块说明）；

⑶开发平台及源程序的主要部分；

⑷测试用例，运行结果与运行情况分析；

⑸自我评价与总结：

）你认为你完成的设计哪些地方做得比较好或比较出色；

）什么地方做得不太好，以后如何改正；

）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；

）完成本题是否有其他方法（如果有，简要说明该方法）；

时间安排：

设计安排一周：

周1、周2：

完成程序分析及设计。

周2、周3：

完成程序调试及测试。

周4、周5：

验收、撰写课程设计报告。

（注意事项：

严禁抄袭，一旦发现，一律按0分记）

指导教师签名：

年月日

系主任（或责任教师）签名：

年月日

进程调度模拟设计

优先级法、最高响应比优先调度算法

1．设计目的与实现功能

模拟进程调度，使程序能够完成：

能够输入若干进程，包括进程的一些基本信息，如进程名、优先级、到达时间和运行时间等，选择不同的调度算法（优先级法或者最高响应比法），选择算法后，根据选择的调度算法显示进程调度队列；根据选择的调度算法计算平均周转时间和平均带权周转时间。

2．需求分析

2.1实验原理

最高响应比优先算法（HRN）：

最高响应比是对先来先服务和最短进程优先法德一种综合平衡。

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

响应比R定义如下：

R=（W+T）/T=1+W/T

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

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

优先级法：

系统和用户按某种原则为进程制定一个优先级来表示该进程所享有的调度优先权。

根据优先级的高低来对进程加以调度。

3.数据结构

3.1主要结构及函数

structtimer//时间类型

{

bytehour;

byteminute;

}

typedefstructprocess//进程结构

{

charname[20];//进程名

byterank;//进程等级

timertime_in;//进程到达的时间

byteuse_time;//运行需要消耗时间

timertime_start;//开始运行时刻

byteused_time;//已经运行的时间

timertime_end;//进程结束时刻

boolflag;//进程运行完成标志，完成true

}process,*process_ptr;

boolsearch（processprocess_n[]）//查看是否所有进程都执行完

boolcompare（timertime1,timertime2）//比较两个时间类型的大小

voidpaixv（processprocess_n[]）//进程按优先级有大到小排序，规定rank越小优先级越高

voidprintf_last（processprocess_n[]）//打印结果

voidgrade_first（processprocess_n[]）//抢占式优先级调度算法

voidHRN（processprocess_n[]）//最高响应比优先算法

优先级调度的思路：

这里设计的是一个抢占式优先级调度设一个标志位作为时钟，时间一分分地走，通过每次扫描各个进程的状态，确定这一分钟该哪个进程执行，在这之间要记录某个进程的开始时间、已运行时间和结束最后，到每个进程都执行过，完成优先级调度。

最高响应比优先调度的思路：

每次调度前都计算每个作业的响应比，从而选择其中最大者投入运行。

3.2流程图

4.源程序的主要部分

4．1查看是否所有进程都执行完

boolsearch（processprocess_n[]）

{

for（inti=0;i

{

if（process_n[i].flag==false）

{

returnfalse;

}

}

returntrue;

}

//比较两个时间类型的大小

boolcompare（timertime1,timertime2）

{

if（time1.hour>time2.hour）

{

returntrue;

}

elseif（time1.hour==time2.hour&&time1.minute>=time2.minute）

{

returntrue;

}

else

{

returnfalse;

}

}

4．2进程按优先级有大到小排序，规定rank越小优先级越高

voidpaixv（processprocess_n[]）

{

inti,j;

processtemp;

for（i=0;i

{

for（j=0;j

{

if（process_n[j].rank>process_n[j+1].rank）

{

temp=process_n[j];

process_n[j]=process_n[j+1];

process_n[j+1]=temp;

}

}

}

}

4.3打印结果

voidprintf_last（processprocess_n[]）

{

floata[MAX];//记录每个进程的周转时间

floatb[MAX];//记录每个进程的带权周转时间

floatout_a=0;

floatout_b=0;

printf（"进程名进程级别提交时间运行时间开始时间完成时间周转时间带权周转时间\n"）;

for（inti=0;i

{

a[i]=（float）（（process_n[i].time_end.hour-process_n[i].time_in.hour）*60+process_n[i].time_end.minute-process_n[i].time_in.minute）;

b[i]=a[i]/process_n[i].use_time;

out_a+=a[i];

out_b+=b[i];

printf（"%4s\t%4d\t",process_n[i].name,process_n[i].rank）;

printf（""）;

if（process_n[i].time_in.hour<10）

{

printf（"0%d",process_n[i].time_in.hour）;

}

else

{

printf（"%d",process_n[i].time_in.hour）;

}

printf（":

"）;

if（process_n[i].time_in.minute<10）

{

printf（"0%d\t",process_n[i].time_in.minute）;

}

else

{

printf（"%d\t",process_n[i].time_in.minute）;

}

/////////////////////////////////////////////////

/////////////////////////////////////////////////

printf（"%4d\t",process_n[i].use_time）;

/////////////////////////////////////////////////

/////////////////////////////////////////////////

if（process_n[i].time_start.hour<10）

{

printf（"0%d",process_n[i].time_start.hour）;

}

else

{

printf（"%4d",process_n[i].time_start.hour）;

}

printf（":

"）;

if（process_n[i].time_start.minute<10）

{

printf（"0%d\t",process_n[i].time_start.minute）;

}

else

{

printf（"%d\t",process_n[i].time_start.minute）;

}

/////////////////////////////////////////////////

printf（""）;

/////////////////////////////////////////////////

if（process_n[i].time_end.hour<10）

{

printf（"0%d",process_n[i].time_end.hour）;

}

else

{

printf（"%d",process_n[i].time_end.hour）;

}

printf（":

"）;

if（process_n[i].time_end.minute<10）

{

printf（"0%d\t",process_n[i].time_end.minute）;

}

else

{

printf（"%d\t",process_n[i].time_end.minute）;

}

///////////////////////////////////////////////

///////////////////////////////////////////////

printf（"%.2f\t",a[i]）;

printf（"%.2f\n",b[i]）;

}

out_a=out_a/n;

out_b=out_b/n;

printf（"平均周转时间为：

%f\n",out_a）;

printf（"平均带权周转时间为：

%f\n",out_b）;

}

4.4抢占式优先级调度算法

/********************************************

*抢占式优先级调度算法*

********************************************/

voidgrade_first（processprocess_n[]）

{

inti;

boolflag;//标志位，用于控制当前时间

while

（1）

{

flag=true;

for（i=0;i<=n;i++）

{

if（compare（current,process_n[i].time_in）&&!

（process_n[i].flag））

{

flag=false;

//获取开始运行时间

if（process_n[i].time_start.hour==0&&process_n[i].time_start.minute==0）

{

process_n[i].time_start=current;

}

//记录进程已经运行的时间

process_n[i].used_time++;

//时钟继续一分一分走

current.minute++;

if（current.minute==60）

{

current.hour+=1;

current.minute=0;

}

//运行完成后，记录完成时间

if（process_n[i].used_time==process_n[i].use_time）

{

process_n[i].flag=true;

process_n[i].time_end=current;

}

break;

}

}

if（flag）

{

current.minute++;

if（current.minute==60）

{

current.hour+=1;

current.minute=0;

}

}

if（search（process_n））

{

break;

}

else

{

continue;

}

}

}

4.5最高响应比优先算法

/*****************************************************

*最高响应比优先算法*

*****************************************************/

voidHRN（processprocess_n[]）

{

floatflag_xiangxi[MAX];//记录进程的响应比

//找到最小的时间作为当前基准时间

current=process_n[0].time_in;

for（inti=1;i

{

if（compare（current,process_n[i].time_in））

{

current=process_n[i].time_in;

}

}

///////////////////////////////////////

while（!

search（process_n））

{

floattemp=0;

for（inti=0;i

{

if（compare（current,process_n[i].time_start）&&process_n[i].flag==false）

{flag_xiangxi[i]=（（float）（current.hour-process_n[i].time_in.hour）*60+current.minute-process_n[i].time_in.minute）/process_n[i].use_time;

if（flag_xiangxi[i]>temp）

{

temp=flag_xiangxi[i];

}

}

}

for（intj=0;j

{if（compare（current,process_n[j].time_start）&&process_n[j].flag==false&&temp==flag_xiangxi[j]）

{

process_n[j].time_start=current;

current.hour=（current.hour*60+current.minute+process_n[j].use_time）/60;

current.minute=（current.hour*60+current.minute+process_n[j].use_time）%60;

process_n[j].time_end=current;

process_n[j].flag=true;

break;

}

}

}

}

4.6主函数

intmain（）

{

intone_two;

processprocess_n[MAX];

processprocess_n_other[MAX];

chartime_string[10];

charFLAG_exit;

while

（1）

{

printf（"请输入进程个数：

"）;

scanf（"%d",&n）;

fflush（stdin）;

for（inti=0;i

{

printf（"请输入第%d个进程的参数：

\n",（i+1））;

printf（"进程名:

"）;

scanf（"%s",process_n[i].name）;

fflush（stdin）;

printf（"进程等级:

"）;

scanf（"%d",&（process_n[i].rank））;

fflush（stdin）;

printf（"提交时间:

"）;

scanf（"%s",&time_string）;

fflush（stdin）;

while（strlen（time_string）!

=5）

{

printf（"输入格式不符合要求！

请重新输入...\n"）;

printf（"提交时间:

"）;

scanf（"%s",&time_string）;

fflush（stdin）;

}

inta=（time_string[0]-48）*10+time_string[1]-48;

while（a>24）

{

printf（"输入格式不符合在24小时内的要求！

请重新输入...\n"）;

printf（"提交时间:

"）;

scanf（"%s",&time_string）;

fflush（stdin）;

a=（time_string[0]-48）*10+time_string[1]-48;

}

process_n[i].time_in.hour=a;

a=（time_string[3]-48）*10+time_string[4]-48;

while（a>=60）

{

printf（"输入格式不符合在60分钟内的要求！

请重新输入...\n"）;

printf（"提交时间:

"）;

scanf（"%s",&time_string）;

fflush（stdin）;

a=（time_string[3]-48）*10+time_string[4]-48;

}

process_n[i].time_in.minute=a;

printf（"执行时间:

"）;

scanf（"%d",&（process_n[i].use_time））;

fflush（stdin）;

process_n[i].flag=false;

}

L1:

printf（"请你选择你将采用的调度算法:

\n"）;

printf（"1--优先级调度\n2--最高响应比优先算法\n"）;

printf（"如果想退出程序请输入其他\n"）;

scanf（"%d",&one_two）;

fflush（stdin）;

if（one_two==1）

{

current.hour=0;

current.minute=0;

for（i=0;i

{

process_n_other[i]=process_n[i];

}

paixv（process_n_other）;

grade_first（process_n_other）;

printf_last（process_n_other）;

printf（"是否退出程序？

退出请输入y\n"）;

scanf（"%c",&FLAG_exit）;

fflush（stdin）;

if（FLAG_exit=='y'||FLAG_exit=='Y'）

return0;

else

gotoL1;

}

elseif（one_two==2）

{

current.hour=0;

current.minute=0;

for（i=0;i

{

process_n_other[i]=process_n[i];

}

HRN（process_n_other）;

printf_last（process_n_other）;

printf（"是否退出程序？

退出请输入y\n"）;

scanf（"%c",&FLAG_exit）;

fflush（stdin）;

if（FLAG_exit=='y'||FLAG_exit=='Y'）

return0;

else

gotoL1;

}

else

{

return0;

}

}

return0;

}

5．测试

输入测试用例：

名称优先级到达时间运行时间（分）

A212:

3530

B312:

2025

C412:

3920

D112:

4022

1.优先级算法

分析如下：

第3级别B进程开始运行，但由于是抢占式的，在12:

35时，也就是B运行15分钟后，有第2级别的A进程到来，A只运行5分钟后，D到来，由于D是最高级别，D可以运行完，此时是13:

02，A继续进行25分钟，完成A，之后B再运行10分钟，完成B，最后运行C。

2.优先级算法

分析如下：

B进程先到，所以先把B进程完成，也就到时间12:

45，此时A、C、D进程都到了，

如果运行A:

R=（W+T）/T=1+W/T=（12:

45+30-12:

35）/30=4/3=1.333

如果运行C:

R=（W+T）/T=1+W/T=（12:

45+20-12:

39）/20=13/10=1.3

如果运行D:

R=（W+T）/T=1+W/T=（12:

45+22-12:

40）/22=27/22=1.22

由于A的响应比最大，所以先运行A,

同理，A运行之后

如果运行C：

R=（W+T）/T=1+W/T=（13:

15+20-12:

39）/20=14/5=2.8

如果运行D:

R=（W+T）/T=1+W/T=（13:

15+22-12:

40）/22=57/22=2.59