第3章 处理机调度(2)1.ppt

1、第3章 处理机调度(2),2020年7月27日,3.3 实时调度 . 3.4 产生死锁的原因和必要条件 . 3.5 预防死锁的方法 . 3.6 死锁检测与解除 3.7 小结,3.3 实时调度,一 实现实时调度的基本条件 1 提供必要的信息 2 系统处理能力强 3 采用抢占式调度机制 4 具有快速切换机制,二 实时调度算法的分类 1 非抢占式调度算法 1) 非抢占式轮转调度算法 2) 非抢占式优先调度算法 2 抢占式调度算法 1) 基于时钟中断的抢占优先权调度算法 2) 立即抢占的优先权调度算法,三、常用的几种实时调度算法 1 最早截至时间优先级EDF（Earliest Deadline Fir

2、st） 2 最低松弛度优先级LLF（Least Laxity First）,目 录返回本章首页,3.4 产生死锁的原因和必要条件,一、产生死锁(Deadlock)的原因 1 死锁(Deadlock)的定义 所谓死锁，是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。计算机系统产生死锁的根本原因就是资源有限且进程间推进顺序不当 。,用一个资源-进程有向图来说明死锁现象,R2,P1,P2,R1,设备共享时的死锁情况：,2 死锁的起因 死锁发生原因：死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。显然，由于资源的有限性，我们不可能为所

3、有要求资源的进程无限制地提供资源。但是，我们可以采用适当的资源分配算法，以达到消除死锁的目的。,3 产生死锁的必要条件,只有4个条件都满足时，才会出现死锁。 1）互斥条件： 即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。 2）不剥夺条件： 进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。,（3）请求和保持条件： 进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。 （4）环路条件： 存在一种进程循环链，链中每一

4、个进程已获得的资源同时被下一个进程所请求。 具体地，存在一个进程等待序列P1，P2，.，Pn，其中P1等待P2所占有的某一资源，P2等待P3所占有的某一源，.，而Pn等待P1所占有的的某一资源，形成一个进程循环等待环。,二、处理死锁的基本方法,二、处理死锁的基本方法 （con.）,目 录返回本章首页,3.5 预防死锁的方法,死锁的预防是保证系统不进入死锁状态的一种策略。它的基本思想是要求进程申请资源时遵循某种协议，从而打破产生死锁的四个必要条件中的一个或几个，保证系统不会进入死锁状态。,目 录返回本章首页,1 预防死锁 1）破坏“请求和保持”条件 即允许进程同时访问某些资源。但是，有的资源是不

5、允许被同时访问的，像打印机等等，这是由资源本身的属性所决定的。所以，这种办法并无实用价值。 2）破坏“不剥夺”条件 即允许进程强行从占有者那里夺取某些资源。就是说，当一个进程已占有了某些资源，它又申请新的资源，但不能立即被满足时，它必须释放所占有的全部资源，以后再重新申请。,3）破坏“环路等待”条件 可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足，则不分配任何资源，此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时，才一次性地将所申请的资源全部分配给该进程。由于运行的进程已占有了它所需的全部资源，所以不会发生占有资源又

6、申请资源的现象，因此不会发生死锁。,2. 死锁的避免,死锁的避免：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。 在分配资源时判断是否会出现死锁，如不会死锁，则分配资源。,3. 死锁的检测和恢复,保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。 死锁检测算法主要是检查是否有循环等待.,2 系统安全状态 1）安全状态 所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列 P1 ，P2 Pn就是安全序列。如果存在这

7、样一个安全序列，则系统是安全的。 3）由安全状态向不安全状态的转换,2）安全状态之例,安全序列：P2 P1 P3 不安全序列：P1 P3 P2P3P1,3 利用银行家算法避免死锁 1）银行家算法中的数据结构 可利用资源向量Available。 最大需求矩阵Max。 分配矩阵allocation 需求矩阵need,2）银行家算法 一个银行家拥有一定数量的资金，有若干个客户要贷款，每个客户须在一开始就声明他所需贷款的总额，若该客户贷款总额不超过银行家的资金总额，银行家可以接受客户的要求。客户贷款是以每次一个资金单位（如1万RMB等）的方式进行的，客户在借满所需的全部单位款额之前可能会等待，但银行家须保证这种等待是有限的，可完成的。 安全性算法,3.6 死锁检测与解除,1 死锁的检测 死锁检测算法是当进程进行资源请求时检查并发进程组是否构成资源的请求和占用环路。如果不存在这一环路，则系统中一定没有死锁。 1）资源分配图 2）死锁定理 3）死锁检测中的数据结构,2 死锁的解除 1）剥夺资源 2）撤消进程 终止参与死锁的进程，收回它们占有的资源，从而解除死锁。 一