第3章 处理机调度和死锁.ppt

1、2020/10/12,阜阳师范学院计算机与信息学院,1,第3章 处理机调度与死锁,3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 产生死锁的原因和必要条件 3.5 预防死锁的方法 3.6 死锁的检测与解除,2020/10/12,阜阳师范学院计算机与信息学院,2,3.1 处理机调度的基本概念,3.1.1 高级调度、中级调度、低级调度 3.1.2 调度队列模型 3.1.3 选择调度方式和调度算法的若干准则,2020/10/12,阜阳师范学院计算机与信息学院,3,2020/10/12,阜阳师范学院计算机与信息学院,4,3.1.1 高级、中级和低级调度,经历下述三级调度: 1

2、、高级调度（High Scheduling） 2、中级调度（Intermediate-Level Scheduling） 3、低级调度（Low Level Scheduling）,2020/10/12,阜阳师范学院计算机与信息学院,5,1. 高级调度,又称为作业调度、宏观调度或长程调度。用于决定把后备队列中的哪些作业调入内存，为他们分配必要的资源，并创建进程。,批处理系统 ： 分时系统 ： 实时系统 ：,需要作业调度,不需作业调度,不需作业调度,2020/10/12,阜阳师范学院计算机与信息学院,6,1. 高级调度,执行作业调度时，必须作出两个决定： 接纳多少作业每次接纳多少作业进入内存，取决

3、于多道程序度，即允许多少个作业同时在内存中运行。 接纳哪些作业应接纳哪些作业从外存调入内存，取决于所采用的调度算法。,2020/10/12,阜阳师范学院计算机与信息学院,7,2. 低级调度,通常也称为进程调度、微观调度或短程调度。进程调度是最基本的一种调度，在三种OS中都有。用于决定就绪队列中哪个进程应先获得处理机，并将处理机分配给选中的进程。,为实现进程调度，应具有如下三个基本机制： 排队器 分派器 上下文切换,2020/10/12,阜阳师范学院计算机与信息学院,8,2. 低级调度,进程调度可采用下述两种调度方式： 非抢占方式 抢占方式 抢占的原则有： （1）优先权原则 （2）短作业（进程）

4、优先原则 （3）时间片原则,2020/10/12,阜阳师范学院计算机与信息学院,9,3. 中级调度,中级调度又称为交换调度或中程调度。 它按一定的算法将外存中已具备运行条件的进程换入内存，而将内存中处于阻塞状态的某些进程换出至外存。,运行,就绪,阻塞,挂起阻塞,挂起就绪,创建,退出,进程调度,中级调度,作业调度,调度的层次,2020/10/12,阜阳师范学院计算机与信息学院,11,3.1.2 调度队列模型,仅有进程调度的调度队列模型 具有高级和低级调度的调度队列模型 同时具有三级调度的调度队列模型,2020/10/12,阜阳师范学院计算机与信息学院,12,1. 仅有进程调度的调度队列模型,在分

5、时系统中就绪进程组织成FIFO队列形式，按时间片轮转方式运行。,2020/10/12,阜阳师范学院计算机与信息学院,13,2. 具有高级和低级调度的调度队列模型,2020/10/12,阜阳师范学院计算机与信息学院,14,3. 同时具有三级调度的调度队列模型,2020/10/12,阜阳师范学院计算机与信息学院,15,3.1.3 选择调度方式和调度算法的若干准则,面向用户的准则 周转时间短 平均周转时间T 平均带权周转时间（W= T(周转)/Ts(CPU执行) 响应时间快 截止时间的保证 优先权准则,面向系统的准则 系统吞吐量高 处理机利用率好 各类资源的平衡利用,2020/10/12,阜阳师范学

6、院计算机与信息学院,16,3.2 调度算法,3.2.1 FCFS与SJF/SPF调度算法 3.2.2 高优先权优先调度算法 3.2.3 基于时间片的轮转调度算法,2020/10/12,阜阳师范学院计算机与信息学院,17,3.2.1 FCFS与SJF/SPF调度算法,1. 先来先服务调度算法(FCFS) 按进程申请CPU（就绪）的次序,0 27 30 35,2020/10/12,阜阳师范学院计算机与信息学院,18,FCFS实例 下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，计算出各自的周转时间和带权周转时间。,FCFS（First Come

7、First Serve),2020/10/12,阜阳师范学院计算机与信息学院,19,FCFS（First Come First Serve),0,1,1,1,1,101,100,1,101,102,100,100,102,202,199,1.99,2020/10/12,阜阳师范学院计算机与信息学院,20,FCFS的特点: FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业（进程） 比较有利于长作业，而不利于短作业,FCFS（First Come First Serve),2020/10/12,阜阳师范学院计算机与信息学院,21,2. 短作业（进程）优先调度算法,4,4,1,7

8、,6,2,12,10,2,14,11,5.5,18,14,3.5,9,2.8,4,4,1,9,8,2.67,18,16,3.2,6,3,1.5,13,9,2.25,8,2.1,2020/10/12,阜阳师范学院计算机与信息学院,22,2 . 短作业（进程）优先调度算法,SJF调度算法的优缺点： 优点：有效降低作业的平均等待时间，提高系统吞吐量 缺点： (1) 对长作业不利 (2) 不能保证紧迫性作业（进程）的及时处理 (3) 不一定能真正做到短作业优先。,2020/10/12,阜阳师范学院计算机与信息学院,23,3.2.2 高优先权优先调度算法,1. 优先权调度算法的类型 为照顾紧迫性作业，使

9、之在进入系统后便获得优先处理，引入了最高优先权优先（HPF）调度算法。它分为两种： 非抢占式优先权算法 抢占式优先权调度算法,2020/10/12,阜阳师范学院计算机与信息学院,24,3.2.2 高优先权优先调度算法,2. 优先权的类型 静态优先权：在创建进程时确定的，在进程的整个运行期间保持不变,又称优先数。 动态优先权：在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变。,2020/10/12,阜阳师范学院计算机与信息学院,25,3. 高响应比优先调度算法(HRRN),为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则可解决问题。见下式： 优先

10、权=(等待时间+要求服务时间)/要求服务时间 响应时间/要求服务时间,3.2.2 高优先权优先调度算法,2020/10/12,阜阳师范学院计算机与信息学院,26,3.2.3 基于时间片的轮转调度算法(RR),在分时系统中，为保证能及时响应用户的请求，必须采用基于时间片的轮转式进程调度算法。在早期，分时系统中采用的是简单的时间片轮转法，进入90年代后，广泛采用多级反馈队列调度算法。,2020/10/12,阜阳师范学院计算机与信息学院,27,将系统中所有的就绪进程按照FCFS原则，排成一个队列。 每次调度时将CPU分派给队首进程，让其执行一个时间片。 在一个时间片结束时，将其送到就绪队列的末尾，并

11、通过上下文切换执行当前的队首进程。,一、时间片轮转算法,1. 基本原理,2020/10/12,阜阳师范学院计算机与信息学院,28,2. 时间片长度的确定,时间片长度变化的影响 过长退化为FCFS算法。 过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加。 对响应时间的要求： T(响应时间)=N(进程数目)*q(时间片),一、时间片轮转算法,2020/10/12,阜阳师范学院计算机与信息学院,29,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18,A,B,C,D,E,A,AB BA,BAC ACB,ACBDCBDA,CBDA EBDAEC,

12、BDAEC DAECB,BDAEC DAEC,DAEC AEC,AEC EC,2020/10/12,阜阳师范学院计算机与信息学院,30,二、多级反馈队列调度算法,实施过程如下： （1） 应设置多个队列并为各个队列赋予不同的优先级。第一个最高，依次降低。该算法赋予各个队列中进程执行时间片的大小也不相同，优先权越高，时间片越短。,1. 调度算法,2020/10/12,阜阳师范学院计算机与信息学院,31,多级反馈队列调度算法,2020/10/12,阜阳师范学院计算机与信息学院,32,二、多级反馈队列调度算法,(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。如它

13、在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾。 (3）仅当第1（i-1）队列空闲时，才会调度第i队列中的进程运行。,2020/10/12,阜阳师范学院计算机与信息学院,33,2. 多级反馈队列调度算法的性能,终端型作业用户 短批处理作业用户 长批处理作业用户,二、多级反馈队列调度算法,练习题,有一个内存中只能装入两道作业的批处理系统，作业调度采用短作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法，有表所示的作业序列，表中所列的优先数是指进程调度的优先数，且优先数越小优先级越高。表中给出了作业的到达时间、估计运行时间和优先数,2020/10/12,阜阳师范学院计算

14、机与信息学院,34,列出所有作业进入内存的时刻以及结束的时刻。 计算作业的平均周转时间。,2020/10/12,阜阳师范学院计算机与信息学院,36,补充作业,假如有四道作业，它们的进入时间和运行时间由下表给出，在单道程序环境下，分别填写先来先服务、短作业优先和RR（3）算法的完成时间、周转时间、带权周转时间、平均周转时间和带权平均周转时间。,2020/10/12,阜阳师范学院计算机与信息学院,37,2020/10/12,阜阳师范学院计算机与信息学院,38,第3章 处理机调度与死锁,3.3 实时调度 3.4 产生死锁的原因和必要条件 3.5 预防死锁的方法 3.6 死锁的检测与解除,2020/1

15、0/12,阜阳师范学院计算机与信息学院,39,3.3 实时调度,实时调度： 合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。 实时任务： 具有明确时间约束的计算任务。,2020/10/12,阜阳师范学院计算机与信息学院,40,3.3 实时调度,3.3.1 实现实时调度的基本条件 3.3.2 实时调度算法的分类 3.3.3 常用的几种实时调度算法,2020/10/12,阜阳师范学院计算机与信息学院,41,3.3.1 实现实时调度的基本条件,提供必要的信息 系统处理能力强 采用抢占式调度机制 具有快速切换机制,2020/10/12,阜阳师范学院计算机与信息学院,42,1. 提供

16、必要的信息,就绪时间 开始截止时间和完成截止时间 处理时间 资源要求 优先级,2020/10/12,阜阳师范学院计算机与信息学院,43,2. 系统处理能力强,假如系统中有M个周期性的硬实时任务，处理时间为Ci，周期时间表示为Pi 则单机系统中必须满足条件 （ Ci / Pi ）1 多处理机系统 （ Ci / Pi ）N,2020/10/12,阜阳师范学院计算机与信息学院,44,3. 采用抢占式调度机制,硬实时任务： 广泛采用抢占机制 小的实时系统： 可采用非抢占调度机制（简化调度程序和对任务调度时所花费的系统开销）,2020/10/12,阜阳师范学院计算机与信息学院,45,4. 具有快速切换机

17、制,(1) 对外部中断的快速响应能力 (2) 快速的任务分派能力,2020/10/12,阜阳师范学院计算机与信息学院,46,3.3.2 实时调度算法的分类,可以按照不同方式对实时调度算法加以分类： 根据实时任务性质的不同可分为硬实时调度算法和软实时调度算法； 按调度方式的不同可分为非抢占调度算法和抢占调度算法；,2020/10/12,阜阳师范学院计算机与信息学院,47,3.3.3 常用的几种实时调度算法,最早截止时间优先EDF（Earliest Deadline First）算法 最低松弛度优先LLF（Least Laxity First）算法,2020/10/12,阜阳师范学院计算机与信息学

18、院,48,EDF算法用于非抢占调度图示,1. 最早截止时间优先EDF算法,截止时间越早，其优先级越高,2020/10/12,阜阳师范学院计算机与信息学院,49,2. 最低松弛度优先LLF算法,松弛度=完成截止时间运行时间当前时间 任务的紧急程度愈高，松弛度愈低，优先级愈高。 该算法主要用于可抢占调度方式中,2020/10/12,阜阳师范学院计算机与信息学院,50,LLF算法例,假如在一个实时系统中，有两个周期型实时任务A、B，任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为25ms；由此可得知AB任务每次必须完成的时间分别为A1、A2、A3和B1、B2

19、、B3如下图：,2020/10/12,阜阳师范学院计算机与信息学院,51,LLF算法例图示,2020/10/12,阜阳师范学院计算机与信息学院,52,3.5 产生死锁的原因和必要条件,3.5.1 产生死锁的原因 3.5.2 产生死锁的必要条件 3.5.3 处理死锁的基本方法,2020/10/12,阜阳师范学院计算机与信息学院,53,关于死锁,死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种状态时，若无外力作用，它们都将无法再向前推进。,2020/10/12,阜阳师范学院计算机与信息学院,54,3.5.1 产生死锁的原因,产生死锁的原因可归结为如下两点： 竞争资源 进程间推

20、进顺序非法,可剥夺和非剥夺性资源 永久性资源和临时性资源,2020/10/12,阜阳师范学院计算机与信息学院,55,P,2,Rel(R,1,),P,2,Rel(R,2,),P,2,Req(R,1,),P,2,Req(R,2,),P,1,Req(R,1,),P,1,Req(R,2,),P,1,Rel(R,1,),P,1,Rel(R,2,),D,进程推进顺序不当引起死锁,2020/10/12,阜阳师范学院计算机与信息学院,56,3.5.2 产生死锁的必要条件,虽然进程在运行过程中可能发生死锁，但死锁的发生也必须具备一定的条件。可以看出，必须具备以下四个条件: 1. 互斥条件：进程所竞争的资源必须被

21、互斥使用。 2. 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放。,2020/10/12,阜阳师范学院计算机与信息学院,57,3.5.2 产生死锁的必要条件,3. 不剥夺条件：指进程已获得的资源，只能在使用完时由自己释放。 4. 环路等待条件：指在发生死锁时，必然存在一个“进程资源”的环形链，环路中的每一条边是进程在请求另一进程已经占有的资源。,2020/10/12,阜阳师范学院计算机与信息学院,58,3.5.3 处理死锁的基本方法,一、预防死锁消除产生死锁的必要条件 二、避免死锁分配资源时防

22、止进入不安全状态 三、检测死锁不预防死锁，出现死锁就解除 四、解除死锁与检测死锁配合使用,2020/10/12,阜阳师范学院计算机与信息学院,59,3.6 预防与避免死锁的方法,3.6.1 预防死锁 3.6.2 系统安全状态 3.6.3 利用银行家算法避免死锁,2020/10/12,阜阳师范学院计算机与信息学院,60,3.6.1 预防死锁,1. 摒弃“请求和保持”条件,静态资源分配法 优点：算法简单、易于实现且很安全 缺点：资源浪费严重，进程延迟运行,2020/10/12,阜阳师范学院计算机与信息学院,61,2. 摒弃“不剥夺”条件,资源暂时释放策略:申请新的资源得不到满足则暂时释放已有的所有

23、资源。从而摒弃了“不剥夺”条件。 该方法实现起来比较复杂且付出很大代价。可能会造成前功尽弃，反复申请和释放情况。,3.6.1 预防死锁,2020/10/12,阜阳师范学院计算机与信息学院,62,3. 摒弃“环路等待”条件,有序资源分配法： 与前两种策略比较，资源利用率和系统吞吐量都有较明显的改善。 但也存在严重问题：为资源编号限制新设备的增加；进程使用设备顺序与申请顺序相反；限制用户编程自由。,2020/10/12,阜阳师范学院计算机与信息学院,63,系统处于安全状态：存在安全进程序列;,1. 安全状态,3.6.2 系统安全状态,避免死锁的实质就是系统在进行资源分配时，如何使系统不进入不安全状

24、态。,2020/10/12,阜阳师范学院计算机与信息学院,64,2. 安全状态之例,假定系统中有三个进程A、B和C，共有12台磁带机。进程A总共要求10台，B和C分别要求4台和9台。假设在T0时刻,进程A、B和C已分别获得5台、2台和2台，尚有3台未分配，如下表所示：,10,4,9,5,2,2,5,2,7,3,B 4 2 2,3,5,A 10 5 5,10,C 9 2 7,12,经分析发现，在T0时刻系统是安全的，因为此时存在一个安全序列，即只要系统按此进程序列分配资源，就能使每个进程都顺利完成。,2020/10/12,阜阳师范学院计算机与信息学院,65,3. 由安全状态向不安全状态的转换,如

25、果在T0时刻后，C又请求到一台磁带机，若此时系统把剩余3台中的1台分配给C，则系统便进入不安全状态。因为，此时再也无法找到一个安全序列，结果导致死锁。,所以，引入安全状态的目的在于进行资源分配时，要使系统不发生死锁，只要保证当前的系统状态是安全的，即每次资源分配之后系统都处于安全状态。,2,C 9 3 6,2020/10/12,阜阳师范学院计算机与信息学院,66,3.6.3 利用银行家算法避免死锁,最有代表性的避免死锁的算法，是Dijkstra的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名的。 银行家算法中的数据结构,（1）可利用资源向量Available。这是一个含有m个元素

26、的数组，其中的每一个元素代表一类可利用的资源数目，其动态初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配与回收而动态的改变。如果Availablej=K,则表示系统中现有Rj类资源K个。,（2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K,则表示进程i需要Rj类资源的最大数目为K。,（3）分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K,则表示进程i当前已分得Rj类资源的数目为K。,（4）需求矩阵Need。

27、这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K,则表示进程i还需要Rj类资源K个，方能完成其任务。 上述三个矩阵间存在的关系：Needi,j=Maxi,j-Allocationi,j,2020/10/12,阜阳师范学院计算机与信息学院,67,3.6.3 利用银行家算法避免死锁,银行家算法 设Requesti是进程Pi的请求向量，如果Requesti j=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：,2020/10/12,阜阳师范学院计算机与信息学院,68,Pi请求资源,RequestijNeedj,请求超量，错返,R

28、equestijAvailablej,不满足，等待,Availablej:=Availablej-Requestij Allocationi,j:=Allocationi,j+Requestij Needi,j:=Needi,j-Requestij,安全,确认，pi继续,Availablej:=Availablej+Requestij Allocationi,j:=Allocationi,j-Requestij Needi,j:=Needi,j+Requestij pi等待,F,T,F,T,T,F,请求的资源是否超出实际需求,是否有足够的资源,暂时分配资源,恢复原来的资源分配状态,2020/1

29、0/12,阜阳师范学院计算机与信息学院,69,（1）如果Requestij= Needi,j,便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 （2）如果Requestij= Availablej,便转向步骤3；否则，表示尚无足够资源，Pi需等待。 （3）系统试探着把资源分配给进程Pi ，并修改下面数据结构中的数值： Availablej:= Availablej- Requestij; Allocationi,j:=Allocationi,j+Requestij; Needi,j:=Needi,j-Requestij; （4）系统执行安全性算法，检查此次资源分配后系统

30、是否出于安全状态以决定是否完成本次分配。,银行家算法,2020/10/12,阜阳师范学院计算机与信息学院,70,3.6.3 利用银行家算法避免死锁,安全性算法 系统所执行的安全性算法可描述如下： （1）设置两个向量： 工作向量work：表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，work:=Available; Finish: 它表示系统是否有足够的资源分配进程，使之运行完成。开始时先做Finishi:=false;当有足够资源分配给进程时，再令Finishi:=true。,2020/10/12,阜阳师范学院计算机与信息学院,71,安全性检测算法,F,

31、Work:=Available; Finish:=false;,有满足条件的j: Finishi=false NeedjWork,Finishi=true; Work:=Work+Allocationj,T,i ,Finishi=true,T,F,安全,不安全,赋初值,进程是否完成 资源是否够用,进程获得资源后，顺利完成并释放资源,进程是否都完成,2020/10/12,阜阳师范学院计算机与信息学院,72,（2）从进程集合中找到一个能满足下述条件的进程： Finishi=false;Needi,j=workj;若找到，执行步骤3，否则执行步骤4。 （3）当进程Pi获得资源后，可顺利执行，直至完成

32、，并释放出分配给它的资源，故应执行： workj:= worki+ Allocationi,j ; Finishi:=true; goto step 2; （4）如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。,安全性算法,2020/10/12,阜阳师范学院计算机与信息学院,73,4. 银行家算法之例,假定系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。,2020/10/12,阜阳师范学院计算机与信息学院,74,4. 银行家算法之例,T0时刻的安全性：利用安全性

33、算法对T0时刻的资源分配情况进行分析可知，在T0时刻存在着一个安全序列P1,P3,P4,P2,P0，故系统是安全的。,False,False,False,False,False,True,10 5 7,0 1 0,7 4 3,10 4 7,P0,True,10 4 7,3 0 2,6 0 0,7 4 5,P2,True,7 4 5,0 0 2,4 3 1,7 4 3,P4,True,7 4 3,2 1 1,0 1 1,5 3 2,P3,True,5 3 2,2 0 0,1 2 2,3 3 2,P1,Finish,Work+Allocation A B C,Allocation A B C,Ne

34、ed A B C,Work A B C,资源情况 进程,2020/10/12,阜阳师范学院计算机与信息学院,75,4. 银行家算法之例,P1请求资源：P1发出请求向量Request1(1， 0， 2),系统按银行家算法进行检查： （1）Request1(1，0，2)=Need1(1，2，2) （2）Request1(1，0，2)=Available1(3，3，2) （3）系统先假定可为P1分配资源，并修改Available、Allocation1和Need1向量。 （4）再利用安全性算法检查此时系统是否安全。如下表。,2020/10/12,阜阳师范学院计算机与信息学院,76,False,Fal

35、se,False,False,False,4. 银行家算法之例,由所进行的安全性检查得知，可以找到一个安全序列P1,P3,P4,P0,P2,因此，系统是安全的，可以立即将P1所申请的资源分配给它。,True,10 5 7,3 0 2,6 0 0,7 5 5,P2,True,7 5 5,0 1 0,7 4 3,7 4 5,P0,True,7 4 5,0 0 2,4 3 1,7 4 3,P4,True,7 4 3,2 1 1,0 1 1,5 3 2,P3,True,5 3 2,3 0 2,0 2 0,2 3 0,P1,Finish,Work+Allocation A B C,Allocation

36、A B C,Need A B C,Work A B C,资源情况 进程,2020/10/12,阜阳师范学院计算机与信息学院,77,4. 银行家算法之例,P4请求资源：P4发出请求向量Request4(3，3，0),系统按银行家算法进行检查： （1）Request4(3，3，0)=Need4(4，3，1); （2）Request4(3，3，0)=Available(2，3，0),让P4等待。 P0请求资源：P0发出请求向量Request0(0，2，0),系统按银行家算法进行检查： （1）Request0(0，2，0)=Need0(7，4，3); （2）Request0(0，2，0)=Available(2，3，0)； （3）系统暂时先假定可为P0分配资源，