操作系统原理第4章

1、第,4,章,处理机调度,4.1,分级调度,4.2,作业调度,4.3,进程调度,4.4,调度算法,4.5,算法评价,4.6,实时系统调度方法,1,第,4,章,处理机调度,4.1,分级调度,4.1.1,作业的状态及其转换,4.1.2,调度的层次,(1),作业调度,宏观调度或高级调度,(2),交换调度,中级调度,(3),进程调度,微观调度或低级调度,(4),线程调度,4.1.3,作业与进程的关系,2,第,4,章,处理机调度,?,进程状态及其转换,Running,Terminate,Timeout,Event Wait,Dispatch,Create,Ready,Event Occurs,Blocke

2、d,Suspend,Resume,Suspend,Resume,Ready,Event Occurs,Blocked,Suspended,Suspended,3,第,4,章,处理机调度,?,作业状态及其转换,运行,完成,用户,提交,收容,就绪,等待,执行,作业调度,作业录入,作业调度,4,第,4,章,处理机调度,4.2,作业调度,4.2.1,作业调度功能,4.2.2,作业调度目标与性能衡量,?,调度目标：,(1),对所有的作业应该是公平合理的；,(2),应使设备有高的利用率；,(3),执行尽可能多的作业（吞吐量大）；,(4),有快的响应时间。,?,性能衡量：,1.,周转时间,T,i,=T,ei

3、,?,T,si,或,T,i,=T,wi,+T,ri,(T,si,作业的提交时间，,T,ei,作业的完成时间,),2.,带权周转时间,W,i,=T,i,/T,ri,5,第,4,章,处理机调度,4.3,进程调度,4.3.1,进程调度的功能,4.3.2,进程调度的时机,4.3.3,进程上下文切换,4.3.4,进程调度性能评价,6,第,4,章,处理机调度,4.4,调度算法,1.,先来先服务,FCFS,First Come First Serve,2.,轮转法,RR,Round Robin,3.,多级反馈轮转法,Round Robin with multiple feedback,4.,优先级法,静态法

4、和动态法,例,线性优先级调度策略,享受服务进程队列,CPU,新创建进程队列,完成,图,4.5,线性优先级调度,7,第,4,章,处理机调度,?,新创建进程队列中进程的优先级,P=a*t (a0),?,享受服务进程队列中进程的优先级,P=b*t (ab0),P(t)=a*(t,?,t,1,),进程在时刻,t,1,被创建,P(t)=a*(t,ba0,，则为,1,?,t,1,)+b*(t,?,t,FCFS,1,),进程在时刻,t,；,1,转入享受服务队列,若,若,ab=0,，则为,RR,法。,线性优先级调度策略介于,FCFS,和,RR,法之间。,P(t),t,1,t,1,t,2,t,2, t,图,4.

5、6,优先级变化曲线,8,第,4,章,处理机调度,4.4,调度算法,5.,最短作业优先法,SJF,Shortest Job First,6.,最高响应比优先法,HRN,Highest Response-ratio Next,响应比,=,等待时间,/,运行时间,例,作业,到输入井时间,执行时间,A,B,C,8:50,9:00,9:30,1.5,小时,0.4,小时,1,小时,9:30,开始调度：作业,A,的响应比,=40/90,，作业,B,的响应比,=30/24,，作业,C,的响应比,=0/60,。,9:54,调度：作业,A,的响应比,=64/90,，作业,C,的响应比,=24/60,。,调度次序：

6、,B,、,A,、,C,。,9,第,4,章,处理机调度,?,常用的作业调度算法,(1),先来先服务,(FCFS,First Come First Serve),(2),短作业优先,(SJF,Shortest Job First),(3),响应比高者优先,(HRN,Highest Response-ratio Next),响应比,=,等待时间,/,运行时间,(4),优先级调度,(5),均衡调度算法,(,资源调度算法,),10,第,4,章,处理机调度,试题,6,（,90,）,从供选择的答案中，选出应填入下列叙述中,_n_,内的正确答案，把编号,写在答卷的对应栏内。,假设某多道程序设计系统有供用户使用

7、的主存空间,100K,，磁带机,2,台，,打印机,1,台，系统采用可变分区方式管理主存，对磁带机和打印机采用静态分,配，并假设输入输出操作的时间忽略不计。现有一作业序列如下：,作业号,进输入井时间,要求计算时间,要求主存量,申请磁带机数,申请打印机数,1,2,3,4,5,8:00,8:20,8:20,8:30,8:35,25,分钟,10,分钟,20,分钟,20,分钟,15,分钟,15K,30K,60K,20K,10K,1,台,0,台,1,台,1,台,1,台,1,台,1,台,0,台,0,台,1,台,11,第,4,章,处理机调度,假设作业调度采用先来先服务算法，优先分配主存的低地址区域且,不准移动

8、已在主存中的作业，在主存中的作业平分,CPU,时间，则作业调,度选中作业的次序是,_A_,，如果把一个作业从进入输入井到得到计算,结果的时间定义为周转时间，则在忽略系统工作时间的情况下，最大的,作业周转时间是,_B_,，最小的作业周转时间是,_C_,，作业的平均周转,时间是,_D_,，作业全部执行结束的时间是,_E_,。,供选择的答案,A,：,(1, 3, 2, 4, 5),(1, 2, 3, 4, 5),(1, 3, 4, 2, 5),(1, 2, 4, 3, 5),BD,：,30,分钟,36,分钟,40,分钟,44,分钟,55,分钟,E,：,9:20,64,分钟,9:30,9:40,9:5

9、0,12,A,：,B,：,C,：,D,：,E,：,第,4,章,处理机调度,8:00 8:20 8:30 9:00 9:10 9:15,J1,15K,空闲,85K,J1,15K,J3,60K,空闲,25K,空闲,15K,J2,30K,J3,60K,空闲,45K,J4,20K,J4,20K,空闲,5K,空闲,5K,内存分配图,J2,30K,空闲,70K,J5,10K,空闲,90K,13,8:00 8:20 8:30 8:35 9:00 9:10 9:15 9:30,第,4,章,处理机调度,J1,J2,J3,20,分钟,5,分钟,5,分钟,5,分钟,5,分钟,15,分钟,J4,J5,15,分钟,5,

10、分钟,15,分钟,周转时间：,J1(30,分钟,),、,J2(55,分钟,),、,J3(40,分钟,),、,J4(40,分钟,),、,J5(55,分钟,),14,第,4,章,处理机调度,4.6,实时系统调度方法,4.6.1,实时系统的特点,(1),有限等待时间,(2),有限响应时间,(3),用户控制,(4),可靠性高,(5),系统出错处理能力强,4.6.2,实时调度算法的分类,(1),静态表格驱动类,(2),静态优先级驱动抢先式调度算法类,(3),动态计划调度算法类,(4),尽力而为调度算法类,15,第,4,章,处理机调度,4.6.3,时限调度算法与频率单调调度算法,开始时限,starting

11、 deadline,结束时限,ending deadline,?,时限调度算法所需要的相关输入信息：,(1),任务就绪时间或事件到达时间,(2),开始时限,(3),完成时限,(4),处理时间,(5),资源需求,(6),优先级,16,第,4,章,处理机调度,例,设实时系统从两个不同的数据源,DA,和,DB,周期性地收集数据并进,行处理，其中,DA,的时限要求以,30ms,为周期，,DB,的时限要求以,75ms,为,周期。设,DA,所需处理时限为,15ms,，,DB,所需处理时限为,38ms,，则与,DA,和,DB,有关进程的事件发生时限（就绪时限）、执行时限以及结束,时限如下图所示。,进,程,事

12、件发生时限,执行时限,结束时限,DA(1),0,15,30,DA(2),30,15,60,DA(3),60,15,90,DB(1),0,38,75,DB(2),75,38,150,DB(3),150,38,225,17,第,4,章,处理机调度,DA(1) DB(1) DA(2) DB(1) DB(1) DA(3) DA(4) DB(2) ,15 30 45 60 75 90 105 130 t,图,4.12,时限调度算法的调度顺序,?,频率单调调度算法是一种被广泛用于多周期性实时处理,的调度算法。,频率单调调度算法的基本原理是频率越低（周期越长）,的任务的优先级越低。,设任务周期为,T,，任务

13、的执行时间为,C,，则使用频率单,调调度算法的必要条件是,CT,。,18,第,4,章,处理机调度,设有,A,、,B,、,C,三个作业，执行情况如下表所示。请,填写周转时间栏，并回答下列问题：,(1),作业的平均周转时间是多少？,(2),采用了什么作业调度算法？,作业名,到达时间,开始执行时间,执行结束时间,周转时间,(,小时,),A,10:00,10:00,12:00,B,10:10,12:25,13:25,C,10:25,12:00,12:25,19,第,4,章,处理机调度,(1),作业的平均周转时间是,2.42,小时。,(2),采用的作业调度算法是,SJF,。,作业名,A,B,C,到达时间

14、,10:00,10:10,10:25,开始执行时间,10:00,12:25,12:00,执行结束时间,周转时间,(,小时,),12:00,13:25,12:25,2.00,3.25,2.00,20,第,4,章,处理机调度,k,个进程共享某种资源,r,，该资源共有,m,个可分配单位，每个进程,一次申请和释放资源单位一个。假设每个进程对该资源的最大需求量,均小于,m,，且各进程最大需求量之和小于,m+k,，试证明这个系统中不,可能产生死锁。,反证法：假设系统已发生死锁,M(i),第,i,个进程的最大资源需求量,N(i),第,i,个进程还需要的资源量,U(i),第,i,个进程已分配的资源量,M(1)+M(2)+ M(k),=(N(1)+N(2)+N(k