处理机调度与死锁n

《处理机调度与死锁n》由会员分享，可在线阅读，更多相关《处理机调度与死锁n（93页珍藏版）》请在金锄头文库上搜索。

1、第三章 处理机调度与死锁,3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除,教学目的与要求,理解处理机调度的概念和调度的层次 掌握各种作业、进程调度算法和实时调度算法 理解死锁的基本概念 掌握死锁的处理方法,教学重点：各种作业、进程调度算法和死锁 的处理方法等。 教学难点：作业、进程调度算法, 死锁,3.1 处理机调度的层次,对资源进行有效的调度是非常必要的，我们生活中也会经常遇到，如：调度银行出纳员服务顾客请求问题等。 CPU是计算机系统中的一个十分重要的资源，对它

2、进行高效的调度是操作系统设计的中心问题之一。,3.1 处理机调度的层次,3.1.1高级调度 （作业调度、长程调度、接纳调度） 1、作业和作业步 作业：包含程序、数据和作业说明书。 作业步：作业执行过程中的每一个加工步骤 作业流：作业进入系统，依次存于外存形成作业流 2、作业控制块（JCB） 它是作业在系统中存在的标志，其中保存了系统 对作业进行管理和调度所需的全部信息。 内容： 作业标识，用户名，作业类型，作业状态，调度信息等 进入系统建立JCB-插入相应后备队列-作业调度-作业控制作业结束回收资源,3、作业调度 将外存作业调入内存，创建PCB等，插入就绪队列。 一般用于批处理系统，分/实时系

3、统一般直接入内存，无此环节。 调度特性 接纳作业数（内存驻留数，多道程序度） 太多 周转时间T长 太少 系统效率低 接纳策略：即采用何种调度算法：FCFS、短作业优先等,3.1.2 低级调度（进程调度，短程调度）,主要是决定就绪队列中的哪个进程应获得处理机， 然后由分派程序（Dispatcher）分派处理机。 1.低级调度的功能： 保存处理机现场信息 按某种算法选取进程 把处理机分配给进程 2.进程调度的三个进步机制 排队器 分派器 上下文切换机制：两对切换,CPU Switch From Process to Process,3.进程调度方式：,1)非抢占方式： 简单、系统开销小，实时性差

4、(如win31) 2)抢占方式 （1）优先权原则 （2）短进程优先原则 （3）时间片原则 引起进程调度的因素有哪些？ 进程正常终止或异常终止 进程因某种原因阻塞：I/O请求；wait操作等 时间片用完 抢占方式下，就绪队列中某进程的优先权比当前执行的进程高,为提高系统吞吐量和内存利用率而引入的一 内-外存对换功能（换出时，进程为挂起或就绪驻外存状态） 三级调度的运行频率 低中高。,3.1.3 中级调度（中程）,3. 2调度的队列模型和调度准则,1.仅有进程调度的队列模型,就绪队列,CPU,阻塞队列,交互用户,时间片完,进程调度,进程完成,等待事件,事件出现,3.2.1调度的队列模型,2.具有高

5、、低级调度的队列模型,就绪队列,CPU,阻塞队列,时间片完,进程调度,进程完成,等待事件1,事件1出现,后备队列,阻塞队列,等待事件2,事件2出现,作业调度,3.具有三级调度的队列模型,就绪队列,CPU,就绪、挂起队列,时间片完,进程调度,进程完成,后备队列,阻塞、挂起队列,事件出现,作业调度,阻塞队列,等待事件,挂起,事件出现,中级调度,交互型作业,3.2.2 选择调度方式和调度算法的若干准则,1、面向用户的准则 （1）周转时间短（常用于批处理系统） 概念：作业从提交 完成的时间.分为： 驻外存等待调度时间 驻内存等待调度时间 执行时间 阻塞时间,1、面向用户的准则 平均周转时间 平均带权

6、可见带权w越小越好,Ts为实际服务时间。,3.1.3选择调度方式和算法的若干准则,1、面向用户的准则 （2）响应时间快：（对交互性作业） 概念：键盘提交请求到首次响应时间 输入传送时间 处理时间 响应传送时间 （3）截止时间的保证（特别是实时系统） （4）优先权准则：（即需要抢占调度）,3.1.3选择调度方式和算法的若干准则,2、面向系统的准则 （1）吞吐量高（特别是批处理）：单位时间完成作业数 （2）处理机利用率好：（因CPU贵，特别是大中型多用户系统） （3）各类资源的平衡利用。,3.1.3选择调度方式和算法的若干准则,3.3调度算法是一个资源分配问题,3.3.1先来先服务和短作业（进程）

7、优先调度算法 1.先来先服务调度算法（FCFS） 特点：简单，有利于长作业（进程） 即CPU繁忙性作业,不利于短作业（进程） 2.短作业（进程）优先调度算法：SJ(P)F 提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量） 特点：对长作业不利，有可能得不到服务 估计时间不易确定,先来先服务算法实例,图3-4 FCFS和SJ(P)F比较,3.3.2高优先权优先调度算法,1.优先权调度算法类型 非抢占式优先权算法 抢占式优先权算法，实时性更好。 2.优先权类型： 1）静态优先权： 进程优先权在整个运行期不变。 确定优先权依据 进程类型 进程对资源的需求； 根据用户需求。 特点：简单，但低

8、优先权作业可能长期不被调度（饥饿）。 （例子MIT IBM7049 ）,3.3.2高优先权优先调度算法(2),2）动态优先权： 如：优先权随执行时间而下降，随等待时间而升高。 优点：长短兼顾 缺点：需经常计算各进程优先级 3.高响应比优先调度算法： 响应比Rp=（Tw+Ts）/Ts 特点： （1）短作业RP大。 （2）Ts（要求服务时间）相同的进程间相当于FCFS。 （3）长作业等待一段时间仍能得到服务。,22,常见的批处理作业调度算法,先来先服务算法（FCFS：First Come First Serve） 最短作业优先算法（SJF：Shortest Job First） 最短剩余时间优先（

9、SRTF: Shortest Remaining Time First） 最高响应比优先算法（HRRF：Highest Response Ratio First） 响应比 R = 响应时间/要求服务时间 =（等待时间+要求服务时间）/要求服务时间 = 1 +（等待时间/要求服务时间）,23,基于优先数调度算法 （HPF：Highest Priority First） （a）由用户规定优先数（外部优先数） 用户提交作业时，根据急迫程度规定适当的优先数，作业调度程序根据JCB优先数决定进入内存的次序。 （b）由系统计算优先数（内部优先数） 例：可按如下公式计算作业的优先数： 优先数= 用户规定优先

10、数作业处理时间+ 作业等待时间输出量,24,25,26,27,28,29,30,31,32,3.2.3基于时间片的轮转调度算法,1.时间片轮转 时间片大小的确定 太大：退化为FCFS； 太小：系统开销过大 系统对响应时间的要求；T=nq 就绪队列中进程的数目； 系统的处理能力：（应保证一个时间片处理完常用命令）,3.2.3基于时间片的轮转调度算法（2）,2.多级反馈队列调度 特点：长、短作业兼顾，有较好的响应时间 短作业一次完成； 中型作业周转时间不长； 大型作业不会长期不处理。,就绪队列1,至CPU,S1,就绪队列2,S2,至CPU,就绪队列3,S3,至CPU,就绪队列n,Sn,至CPU,时

11、间片：S1S2S3,图35多级队列反馈调度算法,36,进程调度算法,对下表，分别采用先来先服务（FCFS）、非抢占最短进程优先（SPF）及抢占的最短剩余时间优先（SRT）、高响应比优先（HRRN）、时间片轮转（RR,时间片q=1）、多级反馈队列（FB，第i级队列的时间片=2i-1）调度算法进行CPU调度，求出各进程的执行情况以及平均周转时间和平均带权周转时间。,FCFS 的调度性能,同样，看到进程E的不利情况。,先来先服务（FCFS）,短作业/进程优先（SJ(P)F）,降低对长进程有利的一种方法就是短进程优先策略：,表 SPF 的调度性能,=1.84,0,3,11,15,9,3,9,15,20

12、,11,TA=3,TB=7,TC=11,TD=14,TE=3,=7.60,8,3,6,4,5,2,2,0,4,6,A,B,C,D,E,WE=1.50,WA=1,WB=1.17,WC=2.75,WD=2.80,E,C,D,A,B,周转时间T=结束时间Tc-到达时间Tin=3-0=3,周转时间 T,带权周转时间W=周转时间T/服务时间Tr=3/3=1,带权周转时 间W,平均,SJF对短作业有利，明显的作业E提前接受了服务，并且整体性能也得到了提高；SJF的问题：,SJF需要事先知道或至少需要估计每个作业所需的处理机时间。,只要不断的有短作业进入系统，就有可能使长作业长期得不到运行而“饿死”。,SJ

13、F 偏向短作业，不利于分时系统（由于不可抢占性）。,短作业/进程优先（SJF）,表 HRRN的调度性能,=2.14,0,3,9,15,13,3,9,13,20,15,TA=3,TB=7,TC=9,TD=14,TE=7,=8.00,8,3,6,4,5,2,2,0,4,6,A,B,C,D,E,WE=3.50,WA=1,WB=1.17,WC=2.25,WD=2.80,E,C,D,A,B,周转时间T=结束时间Tc-到达时间Tin=3-0=3,周转时间 T,带权周转时间W=周转时间T/服务时间Tr=3/3=1,带权周转时 间W,平均,=(9-4)+4/4=2.25,=(9-6)+5/5=1.6,=(9-

14、8)+2/2=1.5,RC,RD,RE,RD,=(13-6)+5/5=2.4,RE,=(13-8)+2/2=3.5,最高响应比（HRRN）,不同调度算法对的性能分析:,进程调度算法,最短剩余时间（SRT）,SRT是针对 SPF 增加了强占机制的一种调度算法，它总是选择预期剩余时间最短的进程。只要新进程就绪，且有更短的剩余时间，调度程序就可能抢占当前正在运行的进程。 SRT不象FCFS偏向长进程，也不象轮转法（下个算法）产生额外的中断，从而减少了开销。 必须记录过去的服务时间，从而增加了开销。 从周转时间来看，SRT 比SPF 有更好的性能。,处理机调度,表 SRT 的调度性能,=1.59,0,

15、3,4,15,8,3,15,8,20,10,TA=3,TB=13,TC=4,TD=14,TE=2,=7.20,8,3,6,4,5,2,2,0,4,6,A,B,C,B,E,WE=1.00,WA=1,WB=2.17,WC=1.00,WD=2.80,E,C,D,A,B,周转时间T=结束时间Tc-到达时间Tin=3-0=3,周转时间 T,带权周转时间W=周转时间T/服务时间Tr=3/3=1,带权周转时 间W,平均,D,B剩余时间=6-1=5；,C剩余时间=4-0=4；,0,5,0,0,最短剩余时间（SRT）,不同调度算法的性能对比分析:,表 RR 的调度性能,周转时间 T,带权周转时 间W,=2.71,0,2,5,7,10,4,18,17,20,15,TA=4,TB=16,TC=13,TD=14,TE=7,=10.80,8,3,6,4,5,2,2,0,4,6,WE=3.50,WA=1.33,WB=2.67,WC=3.25,WD=2.80,E,C,D,A,B,平均,轮转（RRRound Robin）,调度算法（对同样进程情况下，5个算法比较）,47,FCFS,S