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

第3章处理机调度(2)2020年2月2日3.3实时调度.3.4产生死锁的原因和必要条件.3.5预防死锁的方法.3.6死锁检测与解除3.7小结3.3实时调度一实现实时调度的基本条件1提供必要的信息2系统处理能力强3采用抢占式调度机制4具有快速切换机制二实时调度算法的分类1非抢占式调度算法1)非抢占式轮转调度算法2)非抢占式优先调度算法2抢占式调度算法1)基于时钟中断的抢占优先权调度算法2)立即抢占的优先权调度算法三、常用的几种实时调度算法1最早截至时间优先级EDF（EarliestDeadlineFirst）2最低松弛度优先级LLF（LeastLaxityFirst）目录返回本章首页3.4产生死锁的原因和必要条件一、产生死锁(Deadlock)的原因1死锁(Deadlock)的定义所谓死锁，是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。计算机系统产生死锁的根本原因就是资源有限且进程间推进顺序不当。用一个资源--进程有向图来说明死锁现象R2P1P2R1设备共享时的死锁情况：2死锁的起因死锁发生原因：死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。显然，由于资源的有限性，我们不可能为所有要求资源的进程无限制地提供资源。但是，我们可以采用适当的资源分配算法，以达到消除死锁的目的。3产生死锁的必要条件只有4个条件都满足时，才会出现死锁。1）互斥条件：即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。2）不剥夺条件：进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。（3）请求和保持条件：进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。（4）环路条件：存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。具体地，存在一个进程等待序列{P1，P2，...，Pn}，其中P1等待P2所占有的某一资源，P2等待P3所占有的某一源，......，而Pn等待P1所占有的的某一资源，形成一个进程循环等待环。二、处理死锁的基本方法方法资源分配策略各种可能模式主要优点主要缺点预防保守的；宁可资源闲置一次请求所有资源条件1适用于作突发式处理的进程；不必剥夺效率低；进程初始化时间延长资源剥夺条件3适用于状态可以保存和恢复的资源剥夺次数过多；多次对资源重新起动资源按序申请条件4可以在编译时（而不必在运行时）就进行检查不便灵活申请新资源方法资源分配策略各种可能模式主要优点主要缺点避免Avoidance是“预防”和“检测”的折衷（在运行时判断是否可能死锁）寻找可能的安全的运行顺序不必进行剥夺必须知道将来的资源需求；进程可能会长时间阻塞检测Detection宽松的；只要允许，就分配资源定期检查死锁是否已经发生不延长进程初始化时间；允许对死锁进行现场处理通过剥夺解除死锁，造成损失二、处理死锁的基本方法（con.）目录返回本章首页3.5预防死锁的方法死锁的预防是保证系统不进入死锁状态的一种策略。它的基本思想是要求进程申请资源时遵循某种协议，从而打破产生死锁的四个必要条件中的一个或几个，保证系统不会进入死锁状态。目录返回本章首页1预防死锁1）破坏“请求和保持”条件即允许进程同时访问某些资源。但是，有的资源是不允许被同时访问的，像打印机等等，这是由资源本身的属性所决定的。所以，这种办法并无实用价值。2）破坏“不剥夺”条件即允许进程强行从占有者那里夺取某些资源。就是说，当一个进程已占有了某些资源，它又申请新的资源，但不能立即被满足时，它必须释放所占有的全部资源，以后再重新申请。3）破坏“环路等待”条件可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足，则不分配任何资源，此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时，才一次性地将所申请的资源全部分配给该进程。由于运行的进程已占有了它所需的全部资源，所以不会发生占有资源又申请资源的现象，因此不会发生死锁。2.死锁的避免死锁的避免：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。在分配资源时判断是否会出现死锁，如不会死锁，则分配资源。3.死锁的检测和恢复保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。死锁检测算法主要是检查是否有循环等待.2系统安全状态1）安全状态所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列{P1，P2…Pn}就是安全序列。如果存在这样一个安全序列，则系统是安全的。3）由安全状态向不安全状态的转换2）安全状态之例进程最大需求已分配可用P1P2P310495223安全序列：P2P1P3不安全序列：P1…P3…P2P3P13利用银行家算法避免死锁1）银行家算法中的数据结构可利用资源向量Available。最大需求矩阵Max。分配矩阵allocation需求矩阵need2）银行家算法一个银行家拥有一定数量的资金，有若干个客户要贷款，每个客户须在一开始就声明他所需贷款的总额，若该客户贷款总额不超过银行家的资金总额，银行家可以接受客户的要求。客户贷款是以每次一个资金单位（如1万RMB等）的方式进行的，客户在借满所需的全部单位款额之前可能会等待，但银行家须保证这种等待是有限的，可完成的。安全性算法3.6死锁检测与解除1死锁的检测死锁检测算法是当进程进行资源请求时检查并发进程组是否构成资源的请求和占用环路。如果不存在这一环路，则系统中一定没有死锁。1）资源分配图2）死锁定理3）死锁检测中的数据结构2死锁的解除1）剥夺资源2）撤消进程终止参与死锁的进程，收回它们占有的资源，从而解除死锁。一次性撤消参与死锁的全部进程，剥夺全部资源；或者逐步撤消参与死锁的进程，逐步收回死锁进程占有的资源。目录返回本章首页3.7小结•理解处理机调度的基本概念•理解并掌握几种常用的调度算法•死锁的概念、成因和处理办法目录返回本章首页