数据结构第3章

《数据结构第3章》由会员分享，可在线阅读，更多相关《数据结构第3章（122页珍藏版）》请在金锄头文库上搜索。

1、第三章 处理机调度与死锁,第一节 处理机调度的基本概念 第二节 调度算法 第三节 实时调度 第四节 多处理机系统中的调度 第五节 产生死锁的原因和必要条件 第六节 死锁问题的解决方法,3.1 处理机调度的基本概念,3.1.1 高级、中级和低级调度,1. 高级调度(High Scheduling),在每次执行作业调度时，都须做出以下两个决定。1) 接纳多少个作业 2) 接纳哪些作业,2. 低级调度(Low Level Scheduling),1) 非抢占方式(Non-preemptive Mode),2) 抢占方式(Preemptive Mode),抢占的原则有：,优先权原则。 (2) 短作业(

2、进程)优先原则。 (3) 时间片原则。,3. 中级调度(Intermediate-Level Scheduling),中级调度又称中程调度(Medium-Term Scheduling)。 引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。,3.1.2 调度队列模型,1. 仅有进程调度的调度队列模型,图 3 - 1 仅具有进程调度的调度队列模型,2. 具有高级和低级调度的调度队列模型,图 3-2 具有高、低两级调度的调度队列模型,就绪队列的形式。(2) 设置多个阻塞队列。,图 3-2 示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。,3. 同时具有三

3、级调度的调度队列模型,图 3-3 具有三级调度时的调度队列模型,3.1.3 选择调度方式和调度算法的若干准则,1. 面向用户的准则,(1) 周转时间短。,作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为:,作业周转时间=作业完成时间-作业提交时间,可把平均周转时间描述为：,例：有如下三个作业，系统为它们服务的顺序是1、2、3。请平均周转时间和平均带权周转时间。,(2) 响应时间快。 (3) 截止时间的保证。 (4) 优先权准则。,2. 面向系统的准则,系统吞吐量高。 (2) 处理机利用率好。 (3) 各类资源的平衡利用。,3.2

4、调 度 算 法,3.2.1 先来先服务和短作业(进程)优先调度算法,1. 先来先服务调度算法（ First Come First Serve ）,2. 短作业(进程)优先调度算法（ Shortest Job /Process First ）,短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。短作业优先(SJF)的调度算法短进程优先(SPF)调度算法,SJ(P)F调度算法也存在不容忽视的缺点：(1) 该算法对长作业不利(2) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。(3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，

5、而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。,3.2.2 高优先权优先调度算法,1. 优先权调度算法的类型,非抢占式优先权算法,2) 抢占式优先权调度算法,2. 优先权的类型,1) 静态优先权确定进程优先权的依据有如下三个方面：(1)进程类型。 (2) 进程对资源的需求。 (3) 用户要求。,2) 动态优先权动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。,3. 高响应比优先调度算法（Highest Response_ratio Next ）,优先权的变化规律可描述为：,由于等

6、待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：,3.2.3 基于时间片的轮转调度算法,1. 时间片轮转法,(1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。 图 3-5 是多级反馈队列算法的示意。(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列后，；(3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行,依次类推；新进程可抢占低级进程的处理机。,2. 多级反馈队列调度算法,3. 多级反馈队列调度算法的性能,

7、终端型作业用户。 (2) 短批处理作业用户。 (3) 长批处理作业用户。,3.3 实 时 调 度,3.3.1 实现实时调度的基本条件,对实时系统的要求：1.提供必要的调度信息，如就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级；2.系统处理能力强3.采用抢占式调度机制，特别是在实时要求严格的实时系统；4.具有快速切换机制，减小切换时的系统开销。（1）对外部中断的快速响应时间（2）快速的任务分派能力,在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任

8、务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：,系统才是可调度的。,例如：系统中有6个硬实时任务，它们的周期时间都是50ms，每次的处理时间为10ms，则,提高系统的处理能力，其途径有二：其一仍是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；其二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为：,3.3.2 实时调度算法的分类,1. 非抢占式调度算法,非抢占式轮转调度算法。 (2) 非抢占式优先调度算法。,进程1,进程2,进程n,实时进程,调度时间,实时进程要求调度,调度实时进程运行,a 非抢占

9、轮转调度,当前进程,实时进程,实时进程要求调度,当前进程运行完成,b 非抢占优先权调度,调度时间,2. 抢占式调度算法,基于时钟中断的抢占式优先权调度算法。 (2) 立即抢占(Immediate Preemption)的优先权调度算法。,图 3-6 实时进程调度,c 基于时钟中断抢占的优先权抢占调度,当前进程,实时进程,实时进程要求调度,抢占时刻（其它中断）,b 立即抢占优先权调度,当前进程,实时进程,实时进程要求调度,时钟中断到达时,调度时间,调度时间,3.3.3 常用的几种实时调度算法,1. 最早截止时间优先即EDF(Earliest Deadline First)算法,图 3-7 EDF

10、算法用于非抢占调度方式,2. 最低松弛度优先即LLF(Least Laxity First)算法,该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。,图 3-8 A和B任务每次必须完成的时间,假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。,图 3-9 利用ELLF算法进行调度的情况,3.5 产生死锁的原因和必要条件,死锁（Deadlock）：是指两个或两个以上的进程在运行过程中，因争夺资源而造成的一种互

11、相等待（谁也无法再继续推进）的现象，若无外力作用，它们都将无法向前推进下去。,3.5.1 产生死锁的原因,竞争资源。 (2) 进程间推进顺序非法。,申请不同类型资源产生死锁,P1： 申请打印机 使用 申请扫描仪 使用 释放打印机 释放扫描仪 ,P2： 申请扫描仪 使用 申请打印机 使用 释放打印机 释放扫描仪 ,申请同类资源产生死锁（如内存） 原则：* 满足总申请后才能使用* 使用完后一次性释放内存资源m=5，P1进程需要4个单位的内存资源，P2 进程需要4个，P3进程需要3个 ，现P1已经申请到3个， P2也申请了2个。 资源分配不当导致死锁产生,1. 竞争资源引起进程死锁,可剥夺和非剥夺性

12、资源 2) 竞争非剥夺性资源 3) 竞争临时性资源,图 3-12 I/O设备共享时的死锁情况,图 3-13 进程之间通信时的死锁,假定进程P1和P2并发执行，均需要使用独享设备Rl打印机，R2读卡机。先申请后再申请，使用完后释放和，而先申请后再申请，使用完后释放和。P1、P2进程在进程调度程序的作用下，Pl、P2交替运行。,2. 进程推进顺序不当引起死锁,其中，当两个进程顺序申请和时，不可能死锁；而当先申请获得，申请获得，这时、已分别被、占用，接着继续执行申请阻塞，而申请阻塞而死锁，按这种路径会产生死锁。,3.5.2 产生死锁的必要条件,互斥条件 (2) 请求和保持条件 (3) 不剥夺条件 (

13、4) 环路等待条件,3.5.3 处理死锁的基本方法,预防死锁。 (2) 避免死锁。 (3) 检测死锁。 (4) 解除死锁。,3.6 预防死锁的方法,摒弃“请求和保持”条件 2. 摒弃“不剥夺”条件 3. 摒弃“环路等待”条件,3.6.1 预防死锁,3.6.2 系统安全状态,1. 安全状态按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。能找到安全序列的状态为安全状态。,2. 安全状态之例假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台

14、空闲未分配，如下表所示：,3. 由安全状态向不安全状态的转换 上例中，若P3再申请一台，则不安全,3.6.3 利用银行家算法避免死锁 数据结构： 可用资源向量available 最大需求矩阵max 分配矩阵allocation 需求矩阵need 请求向量request,2. 银行家算法设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：(1) 如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2) 如果RequestijAvailabl

15、ej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。,(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablej=Availablej-Requestij;Allocationi,j=Allocationi,j+Requestij;Needi,j=Needi,j-Requestij;(4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。,3. 安全性算法,(1) 设置两个向量： 工作向量Work Finish,(2) 从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj=Worki+Allocationi,j;Finishi=true;go to step 2;,(4) 如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。,4. 银行家算法之例,假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。,