第三章 处理机调度与死锁

1、第三章 处理机调度与死锁,在多道程序环境下，进程数目往往 多于处理机数目。要求系统按照某种算 法，动态的把处理机分配给就绪队列中 的一个进程，使之执行。,第三章 处理机调度与死锁,一、处理机调度的基本概念,如何从作业中挑选作业进入主存运行、如何在进程之间分配处理机时间，无疑是操作系统资源管理中的一个重要问题。 这一涉及处理机分配的问题，称之为处理机调度。,高级调度（High Scheduling） 又称为作业调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程，分配必要的资源，再将新创建的进程排在就绪队列上，准备执行。,高级调度（High Scheduling） 接纳多少个

2、作业 取决于多道程序度，即允许多少个作业同时在内存中运行。 接纳哪些作业（调度算法） 先来先服务、短作业优先、优先权,低级调度（Low level Scheduling） 也称为进程调度，用来决定就绪队列中的哪个进程应获得处理机。,两种调度方式 非抢占方式（Non-preemptive Mode） 抢占方式（Preemptive Mode）,非抢占方式（Non-preemptive Mode） 一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞。 引起调度的因素： 进程执行完毕； 进程因提出I/O请求而暂停执行； 在进程通信或同步过程中执行了某种原语操作。,非抢

3、占方式（Non-preemptive Mode） 优点：实现简单，系统开销小。 缺点：不能满足紧急任务要求，不适合实时系统。,抢占方式（Preemptive Mode） 允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。 抢占原则： 优先权原则 短作业优先原则 时间片原则,进程调度频率最高，约10-100ms进行一次，因而调度 算法不能太复杂，以免占用太多CPU时间。,调度队列模型,二、调度算法,先来先服务 短作业（进程）优先 优先权调度 时间片轮转法 多级反馈队列调度,1、先来先服务调度算法（FCFS）,既可用于作业调度，又可用于进程调度。 作业

4、调度：从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。 进程调度：从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。,1、先来先服务调度算法（FCFS）,比较有利于长作业（进程），而不利于短作业（进程）。,先来先服务调度算法 平均周转时间 t = 1.725 平均带权周转时间 w =6.875,带权周转时间=周转时间/服务时间,3,2、短作业（进程）SJ(P)F优先,对短作业（进程）优先调度的算法。 短作业优先:从后备队列中选择一个或若干个估计运行时间最短的作业，将它调入内存运行。 短进程优先：从就绪队列

5、中选出一估计运行时间最短的进程，将处理机分配给它。,2、短作业（进程）SJ(P)F优先,对长作业（进程）不利；未考虑作业（进程）的紧迫度。,3,3、高优先权优先调度算法,可用于批处理系统，也可用于实时系统。 作业调度：从后备队列中选择若干优先权最高的作业，装入内存。 进程调度：把处理机分配给就绪队列中优先权最高的进程。 分类：非抢占式优先权算法 抢占式优先权调度算法,3,3、高优先权优先调度算法,进程的优先权类型： 静态优先权：是在创建进程时确定的，且在进程的整个运行期间保持不变。 动态优先权：在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。

6、,3,4、时间片轮转法,分时系统中，为能及时响应用户的请求，须采用基于时间片的轮转式进程调度算法。 各进程按提交顺序排成就绪队列，调度时将CPU分配给就绪队列的队首进程，令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片完成后，将该进程送往就绪队列的末尾。 系统能在给定的时间内，响应所有用户的请求。,3,5、多级反馈队列调度算法,设立多个就绪队列，优先级越高的队列，其执行的时间片越小； 当进程在一个时间片内未运行完，则降到下一级队列； 当上级及本级队列均无进程就绪时，才调度下级队列内进程； 刚被唤醒的进程可以抢占优先级比它低的当前进程； 某队列内进程按FCFS调度，末级队列按时

7、间片轮转法调度。,3,5、多级反馈队列调度算法,三、死锁的产生,死锁的定义 产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法,例子：死锁在生活中的影子,A,B,假设有这么两个人A，B：地位平等且自私。 任务：每个人都独立去植树 工具：目前只有1把铲子和1个水桶,要求：每个人若想独立去把植树完成，植树时必须同时具备1把铲子和1个水桶 场景：现在，A手中有1把铲子，B手中有1个水桶 问题：A、B两人能否分别完成自己的任务呢？,例子：死锁的生活中的影子,A,B,有铲子,有水桶,缺水桶,缺铲子,Waiting,Waiting,Waiting for dead,分析,1、死锁（Deadlock）,

8、死锁：系统中的并发进程因竞争资源而无限期的相互等待，使系统处于停滞状态。,2、产生死锁的原因,竞争资源 进程间推进顺序非法,竞争资源引起进程死锁,可剥夺和非剥夺性资源 可剥夺性资源：指某进程在获得这类资源后，该资源可以再被其它进程或系统剥夺。 非剥夺性资源：当系统把这类资源分配给某进程后，再不能强行收回。如：打印机等。,竞争资源引起进程死锁,竞争非剥夺性资源 系统中配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程因竞争这些资源而陷入死锁。,竞争资源引起进程死锁,竞争临时性资源 临时性资源：指由一个进程产生，被另一进程使用一短暂时间后便无用的资源。 例子,竞争资源引起进程死锁

9、,竞争临时性资源 P1：Release(S1)；Request(S3) P2：Release(S2)；Request(S1) P3：Release(S3)；Request(S2) 如改成： P1：Request(S3)；Release(S1) P2：Request(S1)；Release(S2) P3：Request(S2)；Release(S3) 可能发生死锁。,进程推进顺序不当引起死锁,进程推进顺序合法 不会引起进程死锁的推进顺序是合法的。 进程推进顺序非法 引起死锁。,A 死锁点,路线1,路线2,t,t,t2,t1,死锁点,路线1,路线2,问题：那么为什么没有斜线的推进的进程顺序呢？,t

10、,t,3、产生死锁的必要条件,死锁的发生有以下四个必要条件： 互斥条件：指进程对所分配到的资源进行排它性使用。 请求和保持条件：进程申请资源而阻塞时，不释放已占用资源。 不剥夺条件：进程已占用的资源未使用完前不可剥夺，只能由进程资源释放。 环路等待条件：死锁时进程间形成一个等待资源的循环链。,4、处理死锁的基本方法,预防死锁：破坏四个必要条件。 避免死锁：不破坏条件，系统允许进程动态申请资源。在分配资源之前，先计算资源分配的安全性。若将导致不安全状态，则不分配，该进程等待。 检测死锁：检查系统是否死锁，以及哪些进程和资源涉及死锁。 解除死锁：撤消死锁进程或剥夺资源以摆脱死锁.,四、死锁的预防,

11、预防死锁 系统安全状态 利用银行家算法避免死锁,1、预防死锁,预防死锁的方法是使四个必要条件之一不能成立，来避免发生死锁。 互斥条件 请求和保持条件 不剥夺条件 环路等待条件,1、预防死锁,互斥条件：不能破坏。 摒弃“请求和保持”条件：系统规定所有进程开始运行之前，都必须一次性地申请其在整个运行过程中所需的全部资源。 再分配资源时，只要有一种资源不能满足某进程的要求，即使其它所需的各资源都空闲，也不分配给该进程，而让进程等待。 缺点：资源严重浪费。,1、预防死锁,摒弃“不剥夺”条件：进程申请新资源不能满足而阻塞时: 释放所有已占用的资源 逐个资源地被剥夺并分配给其它需要该资源的进程。本进程需要

12、时再重新申请。 缺点：资源被迫释放可能会造成前段工作的失效。,1、预防死锁,摒弃“环路等待”条件：系统给每个资源一个编号，各进程对资源的申请必须严格按编号递增顺序进行。释放资源时按编号递减顺序进行。,2、系统安全状态,安全状态：存在一个由所有进程构成的安全序列。如果系统按照这个顺序为每个进程分配所需资源，直至最大需求，可以使每个进程都运行完。不会产生死锁。 不安全状态：系统中不存在任何一个安全序列。,不安全状态死锁状态,2、系统安全状态,假定系统中有三个进程P1，P2，P3，共有12台磁带机。在T0时刻： 此时存在一安全序列：,2、系统安全状态,如果P1申请并得到一个资源，系统将处于不安全状态

13、。 分配后仍处于“安全状态”才分配，否则不分配。,3、利用银行家算法避免死锁,银行家算法的数据结构 设n=进程数 m=资源类型数 可利用资源向量Available,长度为m的向量。 Availablej=k,表示系统中现有第j类资源k个。 最大需求矩阵Max：n*m的矩阵。 Maxi, j=k,表示进程i需要第j类资源最多k个。,3、利用银行家算法避免死锁,银行家算法的数据结构 设n=进程数 m=资源类型数 分配矩阵Allocation：n*m的矩阵。 Allocationi, j=k,表示进程i已分得第j类资源k个。 需求矩阵Need：n*m的矩阵。 Needi, j=k,表示进程i还需要第

14、j类资源k个。 Needi, j=Maxi, j-Allocationi, j,3、利用银行家算法避免死锁,银行家算法 进程Pi的资源请求算法 Requestij=k: Pi请求k个第j类资源。,3、利用银行家算法避免死锁,3、利用银行家算法避免死锁,安全性算法 设置两个向量： 工作向量Workm：系统可提供给进程继续运行所需的各类资源数目。开始时，Work=Available。 结束向量Finishn:表示某进程是否可运行完。若是，则Finishi=true;否则Finishi=false。,3、利用银行家算法避免死锁,安全性算法 寻找一个进程i,满足以下两个条件： Finishi=fals

15、e Needi=Work 如果没有这样的进程，转步骤4。 假设Pi可以运行完并释放其所有资源，则修改向量：Work=Work+Allocationi Finishi=true 转步骤2. 若对于所有进程，Finishi=true, 则系统处于安全状态。,3、利用银行家算法避免死锁,银行家算法例子 在时刻T0，资源数量：A(10),B(5),C(7),3、利用银行家算法避免死锁,T0时刻是安全的，存在安全序列,3、利用银行家算法避免死锁,P2请求资源Request(1,0,2),执行银行家算法： Request(1,0,2)=Need(1,2,2); Request(1,0,2)=Availab

16、le(3,3,2); 系统试探为P2分配资源后，资源情况是：,3、利用银行家算法避免死锁,再进行安全性检查，得到一安全序列:,3、利用银行家算法避免死锁,P5请求资源Request(3,3,0),执行银行家算法: Request(3,3,0)=Available(2,3,0);则P5等待。 P1请求资源Request(0,2,0),执行银行家算法: Request(0,2,0)=Need(7,4,3); Request(0,2,0)=Available(2,3,0); 系统试探为P1分配资源后，资源情况是：,3、利用银行家算法避免死锁,再进行安全检查，Available(2,1,0)不能满足任

17、何进程，进入不安全状态，恢复旧数据结构，P1等待。,五、死锁的检测与解除,当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须：保存有关资源的请求和分配信息；提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。,五、死锁的检测与解除,死锁的检测 资源分配图 P：进程 R：资源 请求边：Pi Rj 分配边：Rj Pi,五、死锁的检测与解除,若死锁，则资源分配图中必有环路。但有环路时并不一定死锁。 有死锁环：,五、死锁的检测与解除,有环无死锁： 如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。,五、死锁的检测与解除,死锁定理(

18、资源分配图化简法检测死锁) S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全化简的。,五、死锁的检测与解除,完全化简：逐个找出既不阻塞又非独立的进 程结点，消去其请求边和分配边，直至所有 进程结点都孤立。,五、死锁的检测与解除,死锁的解除 剥夺资源：代价最小地选择一个牺牲品。从其它进程剥夺足够数量的资源给死锁进程。 撤消进程：代价最小地将死锁进程撤消。终止所有死锁进程，或每次终止一个死锁进程，直至死锁环解除。,习题,设有4个作业同时到达，每个作业的执行时间均为2个小时，它们在一台处理机上按单道方式执行，则平均周转时间为（ ） A、2小时， B、5小时 C、2.5小时 D、8小时 答案：B,习题,某系统采用短作业优先的调度策略，现有作业序列：作业1（提交时间：8:00,运行时间1.50） 作业2（提交时间：8:30,运行时间0.80）