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

1、学 号： 09课 程 设 计题 目进程调度模拟设计优先级法、最高响应比优先调度算法学 院计算机科学与技术专 业计算机科学与技术班 级计算机0606姓 名肖文俊指导教师孙玉芬2009年1月9日课程设计任务书学生姓名： 肖文俊 专业班级： 计算机0606 指导教师： 孙玉芬 工作单位： 计算机科学与技术学院 题 目: 进程调度模拟设计优先级法、最高响应比优先调度算法 初始条件：1预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1模拟进

2、程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。2设计报告内容应说明： 需求分析； 功能设计（数据结构及模块说明）； 开发平台及源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方

3、法）；v）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目录1 设计题目 12 需求分析 12.1 功能需求 12.1.1进程调度模拟设计优先级法-12.1.2进程调度模拟设计最高响应比优先调度算法-22.2 环境需求 22.3 用户界面需求 23 功能设计 31233.1 数据结构 33.2 模块说明 34 开发平台及源程序的主要部分 44.1 开发平台 44.2

4、 源程序主要部分 45 测试用例，运行结果与运行情况分析 85.1 测试用例 85.2 运行结果 85.3 运行情况分析 116 自我评价与总结 11123451. 设计题目1. 优先级法、最高响应比优先调度算法2. 需求分析2.1 功能需求2.1.1 实现优先级法：优先级法可被用作作业或进程的调度策略。首先，系统或用户按某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权。该算法的核心是确定进程或作业的优先级。确定优先级的方法可分为静态法和动态法。静态法根据作业或进程的静态特性，在作业或进程开始执行之前就确定它们的优先级，一旦开始执行之后就不能改变。动态法则不然，它把作业或

5、进程的静态特性和动态特性结合起来确定作业或进程的优先级，随着作业或进程的执行过程，其优先级不断变化。 静态优先级 作业调度中的静态优先级大多按以下原则确定： (1) 由用户自己根据作业的紧急程度输入一个适当的优先级。为防止各用户都将自己的作业冠以高优先级，系统应对高优先级用户收取较高的费用。 (2) 由系统或操作员根据作业类型指定优先级。作业类型一般由用户约定或由操作员指定。例如：可将作业分为： IO繁忙的作业， CPU繁忙的作业， IO与CPU均衡的作业， 一般作业，等等。 系统或操作员可以给每类作业指定不同的优先级。 (3) 系统根据作业要求资源情况确定优先级。例如根据估计所需处理机时间、

6、内存量大小、IO设备类型及数量等，确定作业的优先级。 进程的静态优先级确定原则可以是： (1) 按进程的类型给予不同的优先级。例如，在有些系统中，进程被划分为系统进程和用户进程。系统进程享有比用户进程高的优先级。对于用户进程来说，则可以分为：IO繁忙的进程， CPU繁忙的进程， IO与CPU均衡的进程， 其他进程。 对系统进程，也可以根据其所要完成的功能划分为不同的类型，例如，调度进程、IO进程、中断处理进程、存储管理进程等。这些进程还可进一步划分为不同类型和赋予不同的优先级。例如，在操作系统中，对于键盘中断的处理优先级和对于电源掉电中断的处理优先级是不相同的。 (2) 将作业的静态优先级作为

7、它所属进程的优先级。2.1.2 实现最高响应比优先调度算法：最高响应比优先法（HRN）是对FCFS方式和SJF 方式的一种综合平衡。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 响应比R定义如下： R=(W+T)/T=1+W/T 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。 每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF 之间的一种折中算法。由于长作业也有机会投入运行

8、，在同一时间内处理的作业数显然要少于SJF 法，从而采用HRN 方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。2.2 环境需求开发环境、运行环境及开发语言：开发环境：Windows平台Visual C+ 6.0运行环境：Windows全系列平台开发语言：C+2.3 用户界面需求输入输出均采用命令行界面。格式如下：首先 输入进程数。其次 输入进程编号，姓名，到达时间，执行时间等相关信息。然后 选择算法，优先法或者是最高响应比算法。最后，输出程序运行所得结果。3 功能设计：3.1 数据结构：创建一个进程信心类：class Processpub

9、lic:Process(); void modify(); /进程信息输入 void print(); /进程信息输出friend void output(); friend int PRI(); friend int hrn();private: char name10; /进程名称 int number; /进程编号int pri; /优先级 double comet; /到达时间 double runbt; /开始运行时间 double runt; /运行时间 double runet; /运行结束时间 double trt; /周转时间 double wtrt; /带权周转时间 dou

10、ble respond_rate; int order; /运行次序 int run_flag; /运行状态;/Process Process MAX,Processcopy MAX;void copy()/复制函数 int i;for(i=0;icounter;i+)Processcopyi=Processi;说明：防止修改了原信息中的的内容设置进程的优先级算法和最高响应比算法：int PRI()/优先级函数int j=0,i;int d=0;int temp=Pet; Processj.runbt=Pet;Processj.runet=Proce

11、et+Processj.runt;Processj.run_flag=1;Processj.order=d+1;d+;temp=Processj.runet;说明：这是部分代码，设置各进程的优先级来调用；int hrn()/最高响应比函数说明：最高响应比是调度策略同时考虑每个作业的等待时间的长短和估计需要执行时间的长短，从中选出响应比最高的作业投入执行。4 开发平台及源程序的主要部分：4.1 开发平台：开发环境、运行环境及开发语言：开发环境：Windows平台Visual C+ 6.04.2 源程序主要部分：int PRI()/优先级算法int j=0,i;int d=0;int

12、 temp=Pet; Processj.runbt=Pet;Processj.runet=Pet+Processj.runt;Processj.run_flag=1;Processj.order=d+1;d+; temp=Processj.runet;int pritemp=100;int z=0;for(i=1;icounter;i+)for(int a=0;acounter;a+)if(Processa.run_flag=0)if(Processa.pripritemp)pritemp=Processa.pri;z=a; P

13、rocessz.runbt=temp; Processz.runet=Processz.runbt+Processz.runt; temp=Processz.runet; Processz.run_flag=1; pritemp=100; Processz.order=d+1;d+;return 0;int hrn()/最高响应比优先调度算法int i,j,p;int current_counter=0;double current_time=Pet;for(i=0;icounter;i+) double max_respond_rate=-1; for(j=0;jcou

14、nter;j+) if(Processj.run_flag=0) Processj.respond_rate=(current_time-Pet)/Processj.runt; for(j=0;jmax_respond_rate) p=j; max_respond_rate=Processj.respond_rate; if(Pet=current_time) Processp.runbt=current_time; else Processp.runbt=Pet;Processp.runet=Processp.runbt+Pr

15、ocessp.runt; Processp.run_flag=1; current_counter=current_counter+1;Processp.order=current_counter; current_time=Processp.runet;return 0;5 测试用例，运行结果与运行情况分析：5.1 测试用例：测试用例1：进程个数：3，内容：1 1 1 1 12 2 1.2 1.5 33 3 1.8 2 2 测试用例2： 进程个数：3 内容:1 1 1 1 1 2 2 1.1 1.2 3 3 3 2 1.5 2a) 运行结果测试用例1：优先级法结果如下：最高响应比算法结果如下：测试用例2：优先级法结果如下：最高响应比算法结果如下：b) 运行情况分析：2组测试数据完全符合通过手工计算出来的结果六 自我评价与总结：本次课程设计题目较为简单，主要是对优先级和最高响应比这两个算法的理解和对进程调度的功能以及进程调度算法有深入的理解。在这次的课程