chapter处理机调度与死锁.ppt

第三章 处理机调度与死锁3.1 处理机调度的基本概念3.2 进程调度算法3.3 实时调度3.4 多处理机系统中的调度3.5 产生死锁的原因和必要条件3.6 预防死锁的方法和死锁避免3.7 死锁的检测和解除 3.1 处理机调度的基本概念 在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。 进程调度要解决的问题WHAT：按什么原则分配CPU 进程调度算法WHEN：何时分配CPU 进程调度的时机HOW： 如何分配CPU CPU调度过程（进程的上下文切换）1. 高级、中级和低级调度l处理机是计算机系统中的重要资源l处理机调度算法对整个计算机系统的综合性能指标有重要影响l可把处理机调度分成三个层次： 高级调度高级调度 中级调度中级调度 低级调度低级调度 高级调度也称为作业调度或长程调度 决定将外存上处于后备队列中的哪些作业调入内存，并为它们创建进程，排入就绪队列，准备执行。作业调度的时间尺度通常是分钟级。 中级调度中级调度又称中程调度。 引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。 为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。涉及进程在内外存间的交换。 低级调度也称进程调度、短程调度，它决定就绪队列中的哪个进程获得处理机。进程调度的时间尺度通常是毫秒级的。2.进程调度的任务 进程调度的任务是控制协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程3.确定算法的原则 具有公平性 资源利用率高（特别是CPU利用率） 在交互式系统情况下要追求响应时间（越短越好） 在批处理系统情况下要追求系统吞吐量4.进程调度方式 非剥夺方式：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。 剥夺方式：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。5.进程调度性能衡量的指标 周转时间 响应时间 CPU-I/O执行期6.进程调度模型 1) 1)只有进程调度的调度队列模型只有进程调度的调度队列模型图 3 - 1 仅具有进程调度的调度队列模型 2)具有高低级调度的调度队列模型图 3-2 具有高、低两级调度的调度队列模型3)具有三级调度的调度队列模型图 3-3 具有三级调度时的调度队列模型7.选择进程调度方式的准则面向用户的准则： 周转时间短； 所谓周转时间，指作业从提交到完成的时间，作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间 响应时间快； 截止时间的保证； 优先权准则面向系统的准则：系统吞吐量高；处理机利用率好；各类资源的平衡利用3.2 3.2 进程调度算法 先进先出(FIFO)算法 最短CPU运行期优先调度算法 最高优先权优先调度算法 轮转法 多级反馈队列 1.先进先出(FIFO)算法 该算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。 优点:实现简单. 缺点:没考虑进程的优先级1.先进先出(FIFO)算法 FCFS有利于长作业，而不利于短作业。该算法短作业C的带权周转时间为100，这是无法容忍的，而长作业D的带权周转时间仅为1.99。 所以，FCFS有利于CPU繁忙型作业（如科学计算），而不利于I/O繁忙型作业。目前大多数的事务处理都属于I/O繁忙型作业 2.短作业(进程)优先调度算法 短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。 短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。 短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，使它立即执行。图 3-4 FCFS和SJF调度算法的性能 FCFS和SJF的性能比较 2.短作业(进程)优先调度算法 SJ(P)F调度算法也存在不容忽视的缺点： (1) 该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。 (2) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。 (3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。 3.最高优先权优先调度算法 该算法总是把处理机分配给就绪队列中具有最高优先权的进程。 抢占式 非抢占式 3.最高优先权优先调度算法 常用以下两种方法来确定进程的优先权(优先级根据优先数来决定) 静态优先数法：静态优先权是在创建进程时确定的，在整个运行期间不再改变。依据有：进程类型、进程对资源的要求、用户要求的优先权。 3.最高优先权优先调度算法 动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先权可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。 4.高响应比优先调度算法 优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： 4.高响应比优先调度算法 (1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。(3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机。 5. 轮转法 把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行 简单轮转法：系统将所有就绪进程按FIFO规则排队，按一定的时间间隔把处理机分配给队列中的进程。这样，就绪队列中所有进程均可获得一个时间片的处理机而运行。 多级队列方法：将系统中所有进程分成若干类，每类为一级。如分成前（轮转法）、后台（优先权法）队列。 6.分时系统中常用时间片轮转法时间片选择问题时间片选择问题： 固定时间片 可变时间片与时间片大小有关的因素：与时间片大小有关的因素： 系统响应时间正比 就绪进程个数反比 CPU能力 1)简单轮转法的调度模型2)多队列反馈调度算法* 首先系统中设置多个就绪队列，并为各个队列赋予不同的优先级。 第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。* 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大* 各个队列按照先进先出调度算法* 一个新进程就绪后进入第一级队列* 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列* 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾* 当第一级队列空时，就去调度第二级队列，如此类推* 当时间片到后，进程放弃CPU，回到下一级队列，如此下去，一个长作业(进程)从第一队列依次降到第n队列 3)多队列反馈调度算法 3)多队列反馈调度算法多级反馈队列调度算法的性能 终端型作业用户。 短批处理作业用户。 长批处理作业用户。7.进程调度算法 其中，RQ为就绪队列指针，EP为运行队列指针。3.3 3.3 实实 时时 调调 度度 1.实现实时调度的基本条件实现实时调度的基本条件 提供必要的信息(就绪时间、截止时间、处理时间、资源、优先级)系统处理能力强采用抢占式调度机制3.3 3.3 实实 时时 调调 度度 1.实现实时调度的基本条件实现实时调度的基本条件 具有快速切换机制对外部中断的快速响应能力。能及时响应紧迫的外部事件， 以免耽误时机。 快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度， 应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。 2.实时调度算法的分类 1)非抢占式调度算法非抢占式调度算法 : 非抢占式轮转调度算法 非抢占式优先调度算法2)2)抢占式调度算法抢占式调度算法: : 基于时钟中断的抢占优先调度算法 几毫秒几十毫秒 立即抢占优先权调度算法。 几毫秒100微秒 图 3-5 实时进程调度 3.常用的几种实时调度算法 1）最早截止时间优先即）最早截止时间优先即EDF(Earliest Deadline First)算法算法 图 3-6 EDF算法用于非抢占调度方式 3.常用的几种实时调度算法 1）最早截止时间优先即）最早截止时间优先即EDF算法的缺点：算法的缺点： 图 3-6 EDF算法用于非抢占调度方式 只考虑了进程的截止时间，未考虑其运行时间只考虑了进程的截止时间，未考虑其运行时间2）最低松弛度优先(LLF)算法 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。该算法主要用于可抢占调度方式中。 假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。 图 3-7 A和B任务每次必须完成的时间 在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10ms；B1必须在50ms时完成， 而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛度可按下式算出： A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms 类似地，可算出B1的松弛度为15ms，调度程序应选择B1运行。t3=30 ms时，A2的松弛度已减为0，B1的松弛度为15 ms，于是调度程序应抢占B1的处理机而调度A2运行.图 3-8 利用ELLF算法进行调度的情况t4=40 ms时，A3的松弛度为10 ms ，B1的松弛度为5 ms，于是重新调度B1；t5=45 ms时，B1完成，而A3的松弛度只有5 ms，而B2还有30，先调度A3；t6=55 ms时，A3完成，而A4的松弛度有15 ms，而B2有20，应先执行A4，但由于A尚未进入第4周期，而B已进入第2周期，所以先调度B2；t7=70 ms时，A4的松弛度已减为0，而B2有20，于是调度程序应抢占B2的处理机而调度A4运行；图 3-8 利用ELLF算法进行调度的情况3.4 多处理机系统中的调度 1.1.多处理器系统的类型多处理器系统的类型 (1) 紧密耦合(Tightly Coupted)MPS。 (2) 松散耦合(Loosely Coupled)MPS。2.2.对称对称多处理器系统和非对称多处理器系统3.进程分配方式 (1)对称多处理器系统中的进程分配方式 静态分配(Static Assigenment)方式 动态分配(Dynamic Assgement)方式 (2)非对称MPS中的进程分配方式4. 进程(线程)调度方式 (1）自调度(Self-Scheduling)方式 （2）成组调度(Gang Scheduling)方式英特尔 酷睿 双核处理器 英特尔 酷睿 双核处理器带有两个执行内核，专为多线程应用和多任务处理进行了优化。 可以同时运行多种要求苛刻的应用，如图形密集型游戏或序列号运算程序；同时在后台下载音乐或运行病毒扫描安全程序。2.91 亿个晶体管65纳米芯片加工工艺512核芯片 浮点运算每秒5120亿次Grape DR处理器采用90nm制程，由台积电代工，尺寸为1717mm ，每秒5120亿次浮点(512Gflops)运算能力.60W其目标是在2008年达到每秒运算2000万亿次浮点(2Petaflops)，并以40Gbps带宽连接各个中央处理单位. 2010年研发45纳米工艺、计算能力达34Tflops的处理器Grape DR处理器芯片组，接口为PCI-XGrape DR处理器演示采用AMD Opteron 2路系统，可见其开放性 512核芯片 浮点运算每秒5120亿次3.4 多处理机系统中的调度 1.1.多处理器系统的类型多处理器系统的类型 (1) 紧密耦合(Tightly Coupted)MPS。 这通常是通过高速总线或高速交叉开关，来实现多个处理器之间的互连的。它们共享主存储器系统和I/O设备，并要求将主存储器划分为若干个能独立访问的存储器模块，以便多个处理机能同时对主存进行访问。系统中的所有资源和进程，都由操作系统实施统一的控制和管理。3.4 多处理机系统中的调度 1.1.多处理器系统的类型多处理器系统的类型 (2) 松散耦合(Loosely Coupled)MPS。 在松散耦合MPS中，通常是通过通道或通信线路，来实现多台计算机之间的互连。每台计算机都有自己的存储器和I/O设备，并配置了OS来管理本地资源和在本地运行的进程。因此，每一台计算机都能独立地工作， 必要时可通过通信线路与其它计算机交换信息，以及协调它们之间的工作。 3.4 多处理机系统中的调度 2.2.对称对称多处理器系统和非对称多处理器系统(1) 对称多处理器系统SMPS(Symmetric MultiProcessor System)。 在系统中所包含的各处理器单元，在功能和结构上都是相同的， 当前的绝大多数MPS都属于SMP系统。例如，IBM公司的SR/6000 Model F50, 便是利用4片Power PC处理器构成的。 (2) 非对称多处理器系统。在系统中有多种类型的处理单元， 它们的功能和结构各不相同，其中只有一个主处理器，有多个从处理器。 3.4 多处理机系统中的调度 3.进程分配方式 (1)对称多处理器系统中的进程分配方式在SMP系统中，所有的处理器都是相同的，因而可把所有的处理器作为一个处理器池(Processor pool)，由调度程序或基于处理器的请求， 将任何一个进程分配给池中的任何一个处理器去处理。在进行进程分配时，可采用以下两种方式之一。 1) 静态分配(Static Assigenment)方式 2) 动态分配(Dynamic Assgement)方式 (2)非对称MPS中的进程分配方式3.4 多处理机系统中的调度 3.进程分配方式 (2)非对称MPS中的进程分配方式 对于非对称MPS，其OS大多采用主从(Master-Slave)式OS，即OS的核心部分驻留在一台主机上(Master)，而从机(Slave)上只是用户程序，进程调度只由主机执行。 每当从机空闲时，便向主机发送一索求进程的信号，然后，便等待主机为它分配进程。在主机中保持有一个就绪队列，只要就绪队列不空，主机便从其队首摘下一进程分配给请求的从机。从机接收到分配的进程后便运行该进程，该进程结束后从机又向主机发出请求。 3.4 多处理机系统中的调度 4. 进程(线程)调度方式 (1）自调度(Self-Scheduling)方式 在多处理器系统中，自调度方式是最简单的一种调度方式。它是直接由单处理机环境下的调度方式演变而来的。在系统中设置有一个公共的进程或线程就绪队列，所有的处理器在空闲时，都可自己到该队列中取得一进程(或线程)来运行。在自调度方式中，可采用在单处理机环境下所用的调度算法，如先来先服务(FCFS)调度算法、最高优先权优先(FPF)调度算法和抢占式最高优先权优先调度算法等。 3.4 多处理机系统中的调度 4. 进程(线程)调度方式 (1）自调度(Self-Scheduling)方式缺点：瓶颈问题。 低效性。 线程切换频繁。其调度算法可沿用单处理机系统所用的算法，亦即，很容易将单处理机环境下的调度机制移植到多处理机系统中， 故它仍然是当前多处理机系统中较常用的调度方式。3.4 多处理机系统中的调度 （2）成组调度(Gang Scheduling)方式为解决自调度中线程切换频繁的问题，可将一个进程中的一组线程分配给一组CPU执行。 1) 面向所有应用程序平均分配处理器时间2) 面向所有线程平均分配处理器时间图 3 - 10 两种分配处理器时间的方法 第三章第三章 处理机调度与死锁处理机调度与死锁 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.5.1 死锁的概念死锁的概念1.1.死锁例子死锁例子: : 一个由于一个由于申请不同类型资源申请不同类型资源而产生死锁而产生死锁的例子的例子 设系统有一台打印机设系统有一台打印机(R1)(R1)一台扫描仪一台扫描仪(R2)(R2)，两进程共享这两台设备。，两进程共享这两台设备。 用信号量用信号量S1S1表示表示R1R1是否可用，用信号量是否可用，用信号量S2S2表示表示R2R2是否可用，是否可用， S1S1、 S2S2初值为初值为1 1。 死锁例子死锁例子 这两个进程在并发执行过程中，可这两个进程在并发执行过程中，可能会发生死锁。大家可以思考一下，如能会发生死锁。大家可以思考一下，如何修改，进程才不会发生死锁。何修改，进程才不会发生死锁。2.死锁概念 指多个进程因竞争共享资源而造成的指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程一种僵局，若无外力作用，这些进程都将永远不能再向前推进。都将永远不能再向前推进。 即：一组进程中，每个进程都无限等即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称现象称为进程死锁，这一组进程就称为死锁进程。为死锁进程。2.死锁概念3.5.2 产生死锁的原因1.1.竞争系统资源竞争系统资源竞争非剥夺性资源（打印机、磁带机）竞争非剥夺性资源（打印机、磁带机）竞争临时性资源竞争临时性资源 只可使用一次的资源；如信号量只可使用一次的资源；如信号量, ,中断信号，同步中断信号，同步信号等（可消耗性资源）信号等（可消耗性资源） “申请申请-分配分配-使用使用-释放释放”模式模式2.2.进程的推进顺序不当进程的推进顺序不当 1. 1. 竞争系统资源 若系统中只有一台打印机若系统中只有一台打印机R1R1和一台和一台读卡机读卡机R2R2，可供进程，可供进程P1P1和和P2P2共享。若共享。若形形成环路成环路，这样会产生死锁，这样会产生死锁。 2.2.进程的推进顺序不当 在进程在进程P1P1和和P2P2并发执行时，按照左图曲并发执行时，按照左图曲线线所示顺序推进时，两进程会顺所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。利完成，我们称这种推进顺序是合法的。若按曲线若按曲线的顺序推进时，进入不安全的顺序推进时，进入不安全区区D D内，两进程再推进会产生死锁。内，两进程再推进会产生死锁。 2.2.进程的推进顺序不当若并发进程P1和P2按曲线所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1, P2保持了资源R2, 系统处于不安全状态。因为，这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1:Request(R2)时，将因R2已被P2占用而阻塞；当P2运行到P2: Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁。 3.5.3 产生死锁的必要条件 综上所述，在同时具备下列四个条件时，综上所述，在同时具备下列四个条件时，就会产生死锁。就会产生死锁。互斥条件互斥条件（资源独占）（资源独占） 在一段时间内，一个资源只能由一个进程独占使用，在一段时间内，一个资源只能由一个进程独占使用，若别的进程也要求该资源，则须等待，直至其占用者若别的进程也要求该资源，则须等待，直至其占用者释放；释放；请求和保持条件请求和保持条件 允许进程在不释放其已分得资源的情况下请求并等待允许进程在不释放其已分得资源的情况下请求并等待分配新的资源；分配新的资源；不剥夺条件（不剥夺条件（不可强占）不可强占） 进程所获得的资源在未使用完之前，不能被其它进程强行夺进程所获得的资源在未使用完之前，不能被其它进程强行夺走，而只能由其自身释放；走，而只能由其自身释放；环路等待条件。环路等待条件。 存在一个等待进程集合，存在一个等待进程集合，P0P0正在等待一个正在等待一个P1P1占用的资源，占用的资源，P1P1正在等待正在等待一个一个P2P2占用的资源，占用的资源，PnPn正在等待一个由正在等待一个由POPO占用的资源。占用的资源。解决死锁的基本办法 预防死锁预防死锁 避免死锁避免死锁 检测死锁检测死锁 解除死锁解除死锁 3.6 预防死锁的方法和避免死锁 1.预防死锁的方法 在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件任何一个。 3.6 预防死锁的方法和避免死锁1)1)破坏请求和保持条件破坏请求和保持条件资源一次性分配；资源一次性分配；要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配(破坏请求和保持条件)2)2)破坏不可剥夺条件破坏不可剥夺条件可剥夺资源；可剥夺资源；即当某进程新的资源未满足时，释放已占有的资源3)3)破坏环路等待条件破坏环路等待条件资源有序分配法资源有序分配法；系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反2. 死锁避免 预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意得系统性能来避免死锁。 死锁避免定义死锁避免定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。 该方法把系统的状态分为安全状态和不安全状态，只要处于安全状态就可以避免死锁。3. 安全状态与不安全状态 安全状态指系统能按某种进程顺序安全状态指系统能按某种进程顺序来为每个进程分配其所需资源，直至最来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处系统不存在这样一个序列，则称系统处于不安全状态。于不安全状态。 1)安全序列 所谓安全状态，是指系统能按某种进程顺序(P1, P2, ，Pn)(称P1, P2, , Pn序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。检测可满足请求 分配 不分配安全不安全系统处于安全状态：存在安全进程序列进程序列安全，p1,p2,pn可依次进行完。 2) 安全状态之例安全状态之例 我们通过一个例子来说明安全性。假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： 进 程 最 大 需 求 已 分 配 可 用 P1P2P310495223进 程 最 大 需 求 已 分 配 可 用 P1P2P310495223给P3分配一个后 3) 由安全状态向不安全状态的转换由安全状态向不安全状态的转换 如果不按照安全序分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。 因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。 进 程 最 大 需 求 已 分 配 可 用 P1P2P310495223安全状态与不安全状态 不安全状态:不存在一个安全序列，不安全状态可能导致死锁4.利用银行家算法避免死锁 1)银行家算法中的数据结构银行家算法中的数据结构 (1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中现有Rj类资源K个。 (2) 最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。 (3) 分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。 (4) 需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Needi,j=Maxi,j-Allocationi,j 2)银行家算法银行家算法 设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej =Availablej-Requestij; Allocationi,j =Allocationi,j+Requestij; Needi,j =Needi,j-Requestij; (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 3)安全性算法（略读）安全性算法（略读） (1) 设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work =Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi =false; 当有足够资源分配给进程时， 再令Finishi =true。 (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 所示。 图 3-8 T0时刻的资源分配表 (1) T0时刻的安全性： 图 3-9 T0时刻的安全序列 (2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 3-15 中的圆括号所示。 再利用安全性算法检查此时系统是否安全。 图 3-10 P1申请资源时的安全性检查 (3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，让P4等待。 (4) P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0); 系统暂时先假定可为P0分配资源，并修改有关数据，如图 3-18 所示。 图 3-11 为P0分配资源后的有关资源数据 当为进程分配资源时，如果未采取任何限制措施，则必须提供死锁检测和解除功能 允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行3.7 死锁的检测和解除1.检测时机 当进程等待时检测死锁 （其缺点是系统的开销大） 定时检测 系统资源利用率下降时检测死锁2.资源分配图 用有向图描述进程的死锁准确、形象 系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例资源分配图 二元组G=（N，E） N：结点集，分为进程结点P，资源结点R两部分 P=p1,p2,pn, R=r1,r2,rm N=PR E：边的集合，其元素为有序二元组: 资源请求边(pi,rj)，进程指向资源 资源分配边(rj,pi)，资源指向进程表示法表示法: :资源类资源类: :用方框表示（资源的不同类型）资源实例资源实例: :用方框中的黑圆点表示（某类资源中的一个资源） 进程进程 : :用圆圈中加进程名表示分配边：分配边：资源实例进程的一条有向边申请边：申请边：进程资源类的一条有向边 3. 资源分配图化简方法如下:1）找一个既不阻塞又非独立的进程结点Pi。在顺利情况下， Pi可获取所需资源而继续执行，执行完毕，再释放所占有的全部资源。这相当于消去Pi所有的分配边和请求边，使之成为孤立结点。2）P1把释放资源后，便可使P2获得资源而继续执行，直到P2完成又释放所占有的资源。重复上述过程直到不能化简为止。图 3-12 资源分配图的简化 资源分配图的简化 a资源分配图的简化 b4. 死锁定理 S为死锁状态的充分条件：当且仅当S状态所对应的资源分配图是不可完全化简的。 完全化简：消除图中所有边，使进程都成为孤立结点。 化简结果与化简顺序无关。 4. 死锁定理 如果资源分配图中没有环路,则系统中没有死锁,如果图中存在环路则系统中可能存在死锁。 如果每个资源类中只包含一个资源实例,则环路是死锁存在的充分必要条件。 有环有死锁有环无死锁5.死锁的解除 重要的是以最小的代价恢复系统的运行。方法如下： 1）重新启动 2）撤消进程 3）剥夺资源 4）进程回退