进程调度算法WHEN

0/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除1/136

3.1.1处理机调度的基本概念在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。2/1361、进程调度要解决的问题WHAT：按什么原则分配CPU—进程调度算法WHEN：何时分配CPU—进程调度的时机HOW：如何分配CPU—CPU进程调度过程（进程的上下文切换）3/1362、高级、中级和低级调度处理机是计算机系统中的重要资源；处理机调度算法对整个计算机系统的综合性能指标有重要影响；可把处理机调度分成三个层次：

高级调度中级调度低级调度4/136它用于确定把后备队列上的哪些作业调入内存；高级调度的时间尺度通常是分钟、小时或天；高级调度要解决的问题：接纳多少作业接纳哪些作业——取决于调度算法高级调度—作业调度（宏观调度）5/136涉及进程在内外存间的交换；把进程的部分或全部换出到外存上，将当前进程所需部分换入到内存。

中级调度—对换暂时不能运行的进程6/136指在多道程序环境下，内核按一定的调度算法，从就绪队列中选出一进程，把处理机分配给它。低级调度的时间尺度通常是毫秒级的。低级调度—微观调度（进程调度）7/1363、进程调度的任务

进程调度的任务:控制协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。8/1364、进程调度方式非剥夺方式（NON-PreemptiveMode）分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。剥夺方式（PreemptiveMode）当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。9/1365、确定算法的原则具有公平性；资源利用率高（特别是CPU利用率）；在交互式系统情况下要追求响应时间（越短越好）；在批处理系统情况下要追求系统吞吐量。10/1366、进程调度性能衡量的指标周转时间:从作业提交给系统开始到作业完成为止的时间间隔（作业周转时间）。

周转时间=作业在后备队列上的等待（作业）调度时间

+进程在就绪队列上等待进程调度的时间

+进程在CPU上执行的时间

+进程等待I/O操作完成的时间11/1366、进程调度性能衡量的指标（续）响应时间:从提交一个请求到首次产生响应的时间间隔。

响应时间＝从键盘输入的请求信息传送到处理机的时间

＋处理机对请求信息处理的时间＋响应信息回送到终端显示器的时间CPU-I/O执行期:进程在运行时，交替地处于两种工作状态：CPU忙和I/O忙。12/136

3.1.２调度队列模型仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型同时具有三级调度的调度队列模型13/136１、仅有进程调度的调度队列模型（分时系统）14/136２、具有高级和低级调度的队列模型（批处理）15/136与进程调度队列模型的区别就绪队列的形式优先权队列无序链表设置多个阻塞队列16/136３、同时具有三级调度的调度队列模型17/136

3.1.３选择调度方式和算法的准则面向用户的准则面向系统的准则18/136１、面向用户的准则周转时间短响应时间快截止时间的保证——任务必须开始执行的最迟时间优先权准则——紧急任务优先执行19/136２、面向系统的准则系统吞吐率高——单位时间内完成的作业多；处理机利用高——40%~90%；各类资源平衡利用。20/136处理机调度的概念

系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。课程回顾21/136调度队列模型仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型同时具有三级调度的调度队列模型22/136处理机调度应遵循的准则资源的利用率高响应时间快周转时间短系统吞吐率大公平、一致23/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除24/1363.2调度算法学习目标：熟练掌握常见的调度算法，明确各调度算法的优缺点。学习难点：理解各调度算法的思想，将算法在实践中灵活应用。25/136先来先服务算法(FirstComeFirstServed)最短作业优先算法(ShortestJobFirst)最高响应比优先算法(HighestResponseRatioFirst)基于时间片的调度算法

时间片轮转(Round-Robin)

多队列反馈调度算法(MultilevelFeedback)

3.2.1主要的调度算法26/136算法基本思想：按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。

3.2.2先来先服务算法（FirstComeFirstServed）12345cpu27/136算法基本思想：按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。

3.2.2先来先服务算法（FirstComeFirstServed）12345cpu28/136算法举例：（单位:小时，以十进制计）作业提交时间运行时间开始时间完成时间周转时间带权周转时间A06B13C25D32平均周转时间t=平均带权周转时间w=06616982.67914122.41416136.59.753.14=完成时间-提交时间=周转时间/运行时间29/136算法优缺点：算法容易实现；适用于作业调度和进程调度；效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短；不利于短作业。30/136算法思想应用：日常生活中先来先服务思想的应用31/136随堂思考：一批作业几乎同时提交，（有先后次序，但相差时间可忽略不记）如果作业提交的次序发生改变，结果是否会发生变化？（三个进程所需的CPU时间分别为28、9、3）32/136A(28)B(9)C(3)283740A(28)B(9)C(3)91240A(28)B(9)C(3)312403520.318.333/136算法基本思想：

SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。3.2.3最短作业优先算法（ShortestJobFirst）12345cpu34/136算法基本思想：

SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。3.2.3最短作业优先算法（ShortestJobFirst）12345cpu35/136算法举例：（单位:小时，以十进制计）作业提交时间运行时间开始时间完成时间周转时间带权周转时间A06B13C25D32平均周转时间t=平均带权周转时间w=0661811103.31116142.86852.58.752.4FCFSt=9.75w=3.14结论：SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好=完成时间-提交时间=周转时间/运行时间36/136算法优缺点：算法容易实现；适用于作业调度；能有效降低作业的平均等待时间；忽视了作业等待时间，对长作业不利，有可能导致长作业（进程）长期不被调度（出现饥饿现象）；要精确知道一个作业的运行时间比较困难的。37/136算法思想应用：厨师做菜次序的安排38/136课后思考：如采用最短剩余时间优先算法SRTF（ShortestRemainingTimeFirst），情况将如何变化。作业提交时间运行时间A06B13C25D32/new/misxtrj

课程资源→其他资源→课后作业39/136作业提交时间运行时间首次开始首次完成再次开始再次完成周转时间带权周转A06B13C25D32平均周转时间t=平均带权周转时间w=01144661111161131431.8312.81.57.751.5340/1363.2.4最高响应比优先（HighestResponseRatioFirst）优先权的类型：静态优先权—在创建进程时确定的，且在进程的整个运行期间保持不变。动态优先权—在创建进程时赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变。41/136最高响应比优先（HighestResponseRatioFirst）响应比概念：公式理解：等待时间相近，服务时间越短，优先权越高SJF服务时间相近，等待时间越长，优先权越高FCFS算法基本思想：

HRRF算法在当前作业执行完时,计算剩余作业的响应比，选取响应比最高的作业投入运行。42/136举例：以下四个作业先后到达系统进入调度：

开始只有作业1，被选中执行时间20ms；作业1执行完毕，响应比依次为1+15/15、1+10/5、1+5/10，作业3被选中，执行时间5ms；作业3执行完毕，响应比依次为1+20/15、1+10/10，作业2被选中，执行时间15ms；作业2执行完毕，作业4被选中，执行时间10ms；平均作业周转时间T=(20+15+35+35)/4=26.25平均带权作业周转时间W=(20/20+15/5+35/15+35/10)/4=2.4643/136算法优缺点：

算法适用于作业调度；既考虑作业等待时间，又考虑作业的运行时间；既照顾短作业又不使长作业的等待时间过长;

计算响应比需要耗费时间。44/136算法思想应用：义诊就医次序安排45/136算法基本思想：

系统按照固定的时间片依次轮流执行就绪队列中的各个进程。3.2.5时间片轮转法（Round-Robin)ABCD46/136算法举例：有三个进程P1、P2、P3先后到达，它们分别需要20、4和2个单位时间运行完毕。假如它们按P1、P2、P3的顺序执行，且不可剥夺，则三进程各自的周转时间、平均周转时间是多少个时间单位。假如它们按P1、P2、P3的顺序执行，且不可剥夺，则三进程各自的周转时间分别为20、24、26个单位时间，平均周转时间是23.33个时间单位。47/136算法举例：有三个进程P1、P2、P3先后到达，分别需要20、4和2个单位时间运行完毕，假如用时间片轮转原则的剥夺调度方式，时间片为2个时间单位。则各进程的周转时间和平均周转时间。02468101214161820222426p1p2p3p1p2p1p1p1p1p1p1p1p1P1、P2、P3的周转时间分别为26、10、6平均周转时间为（26+10+6）/3=1448/136算法优缺点：

算法主要针对分时系统，适用于进程调度；对用户的响应及时、快速；时间片的长度确定比较困难；进程切换开销比较大。49/136算法思想应用：驾校培训安排50/136回顾与总结

算法FCFSSJFHRRFRR

项目适用范围抢占性优点缺点作业、进程作业作业进程非抢占两者均可非抢占抢占简单利于短作业均衡调度响应及时无视特殊要求易导致饥饿计算耗时切换开销大51/136讨论与练习52/136算法基本思想：将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列优先权越高,为每个进程所规定的执行时间片就越小；系统从第一级调度，当第一级为空时，系统转向第二个队列，.....当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列。

多队列反馈调度算法53/136首先系统中设置多个就绪队列；每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大；各个队列按照先进先出调度算法；一个新进程就绪后进入第一级队列；进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列；当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾；当第一级队列空时，就去调度第二级队列，如此类推；当时间片到后，进程放弃CPU，回到下一级队列。算法步骤：54/136多队列反馈调度算法模型55/1363.2.6引起进程调度的原因正在执行的进程执行完毕或因发生某事件而不能再继续执行；执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作如P操作、阻塞、挂起原语等；在可剥夺式调度中，有比当前进程优先权更高的进程进入就绪队列；在时间片轮转法中，时间片完。56/1363.2.7进程调度算法其中，RQ为就绪队列指针，EP为运行队列指针。57/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除58/1363.3实时调度

3.3.1实现实时调度的基本条件

提供必要的信息(就绪时间、截止时间、处理时间、资源优先级)；系统处理能力强；采用抢占式调度机制；具有快速切换机制。59/1363.3.2实时调度算法的分类非抢占式调度算法非抢占式轮转调度算法非抢占式优先调度算法抢占式调度算法基于时钟中断的抢占优先调度算法立即抢占优先权调度算法60/136图3-5实时进程调度

61/136

最早截止时间优先即EDF(EarliestDeadlineFirst)算法

图3-6EDF算法用于非抢占调度方式

3.3.3常用的几种实时调度算法

62/136

最低松弛度优先(LLF)算法

该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。该算法主要用于可抢占调度方式中。假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms。

图3-7A和B任务每次必须完成的时间63/136

在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需10ms，可算出A1的松弛度为10ms；B1必须在50ms时完成，而它本身运行就需25ms，可算出B1的松弛度为25ms，故调度程序应先调度A1执行。在t2=10ms时，A2的松弛度可按下式算出：

A2的松弛度=必须完成时间-其本身的运行时间-当前时间

=40ms-10ms-10ms=20ms

类似地，可算出B1的松弛度为15ms，调度程序应选择B2运行。t3=30ms时，A2的松弛度已减为0，B1的松弛度为15ms，于是调度程序应抢占B1的处理机而调度A2运行…….64/136图3-8利用ELLF算法进行调度的情况t1=0时：A1的松弛度=必须完成时间-其本身的运行时间-当前时间

=20ms-10ms-0ms=10ms

B1的松弛度=必须完成时间-其本身的运行时间-当前时间

=50ms-25ms-0ms=25ms01020304050607080A1t2=10时：A2的松弛度=必须完成时间-其本身的运行时间-当前时间

=40ms-10ms-10ms=20ms

B1的松弛度=必须完成时间-其本身的运行时间-当前时间

=50ms-25ms-10ms=15msB1(20)t3=30时：A2的松弛度=必须完成时间-其本身的运行时间-当前时间

=40ms-30ms-10ms=0ms

B1的松弛度=必须完成时间-其本身的运行时间-当前时间

=50ms-5ms-30ms=15msA2t4=40时：A3的松弛度=必须完成时间-其本身的运行时间-当前时间

=60ms-10ms-40ms=10msB1的松弛度=必须完成时间-其本身的运行时间-当前时间

=50ms-5ms-40ms=5msB1(5)A3B2(15)A4B2(10)9065/136图3-8利用ELLF算法进行调度的情况66/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除67/1363.4多处理机系统中的调度

MPS——MultiProcessorSystem

3.4.1紧密耦合MPS和松弛耦合MPS

1.紧密耦合MPS

通过高速总线或高速交叉开关连接多个处理器，多个CPU共享主存储器和I/O设备，系统中的所有资源和进程由操作系统统一控制和管理

2.松弛耦合MPS

通过通道或通信线路连接多个计算机，每个计算机都有自己的存储器和I/O设备，都有自己的操作系统控制和管理本地资源和进程的运行(——计算机网络)68/1363.4.2对称MPS和非对称MPS

根据处理器是否相同来划分。

1.对称MPS——SMPS

系统中的处理器在结构和功能上都相同。

2.非对称MPS

系统中有多种类型的处理器，它们的结构和功能各不相同。其中一个是主处理器，其余都是从处理器。69/136

一）对称多处理器系统中的进程分配方式

1.静态分配方式进程从开始执行到执行结束，都被固定地分配到一个处理器。每个此类系统一般采用主从式操作系统，即OS的核心驻留于主处理器中，而用户程序则在从处理器上，进程调度由主处理器执行。每当从处理器空闲时，就向主处理器发送一个索求进程的信号，主处理器从公用就绪队列中进行进程调度处理器有一个专用的就绪队列，被阻塞的进程再次就绪时，仍回到该队列的末尾。

2.动态分配方式系统中可以只设置一个公共的就绪队列，其中的进程可以分配到系统中的任何一个处理器。3.4.3进程分配方式70/136

二）非对称MPS中的进程分配方式此类系统一般采用主从式操作系统，即OS的核心驻留于主处理器中，而用户程序则在从处理器上，进程调度由主处理器执行。每当从处理器空闲时，就向主处理器发送一个索求进程的信号，主处理器从公用就绪队列中进行进程调度。71/136一）自调度方式

1.自调度机制在系统中设置一个公共的进程(线程)就绪队列，所有的处理器空闲时，都可以自己到该队列中取得一个进程(线程)投入运行

(1)FCFS算法

(2)最小优先数优先算法

(3)抢占式最小优先数优先算法3.4.4进程(线程)调度方式72/1362.自调度方式的特点有任务的情况下处理机不会空闲分布式调度可以沿用单处理机环境下的就绪队列组方式织和进程调度方法多处理机互斥共享单就绪队列引起的瓶颈重新调度时线程迁移引起的低效性线程切换频繁73/136二）成组调度

1.基本原理把一个进程中的一组线程分配到一组处理机上执行。其优点是：

(1)若一组线(进)程可以并行执行，就可以减少阻塞情况的发生，减少了切换频率，提高了性能

(2)一次调度为一组线程分配处理机，减少了调度频率，减少了系统开销2.为应用程序分配处理机时间的方法

1)为所有的应用程序平均分配处理机时间

2)为所有的线程平均分配处理机时间74/136

1.基本原理为一个应用程序的每个线程分配一个处理器，直到该应用程序执行完毕，才释放为该应用程序所分配的所有处理器。3.4.5专用处理器分配2.采用专用处理器分配方法的理由

1)专用处理器分配方式的缺点部分处理器的利用率可能不高

2)仍然采用专用处理器分配方式的原因

(1)在大规模(甚至几百个处理器)高度并行的系统中，单个处理器的利用率不那么重要；

(2)避免了线程切换，加速了程序运行。75/136讨论与练习76/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除77/1363.5.1死锁的概念1.死锁例子:(deadlock)一个由于申请不同类型资源而产生死锁的例子设系统有一台打印机(R1)一台扫描仪(R2)，两进程共享这两台设备。用信号量S1表示R1是否可用，用信号量S2表示R2是否可用，S1、S2初值为1。

78/136

死锁概念指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。79/136参与死锁的进程最少是两个；参与死锁的进程至少有两个已经占有资源；参与死锁的所有进程都在等待资源；参与死锁的进程是当前系统中所有进程的子集。注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。

关于死锁的一些结论80/136永久性资源：可以被多个进程多次使用（可再用资源）可抢占资源(处理机,主存)不可抢占资源(打印机,磁带机)临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源）“申请--分配--使用--释放”模式

永久性资源和临时性资源81/1363.5.2产生死锁的原因1.竞争系统资源

当系统中供多个进程共享的资源数目不足以满足诸进程的需要时,会引起进程对资源的竞争而产生死锁。2.进程的推进顺序不当

进程在运行过程中,请求和释放资源的顺序不当,也可能造成进程死锁。82/1361.竞争系统资源

若系统中只有一台打印机R1和一台读卡机R2，可供进程P1和P2共享。若形成环路，这样会产生死锁。83/136有环有死锁84/136有环无死锁85/1362.进程的推进顺序不当在进程P1和P2并发执行时，按照左图曲线①②③所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。若按曲线④的顺序推进时，进入不安全区D内，两进程再推进会产生死锁。P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)③④③③③②②①①进程P1、P2并发执行。资源R1、R2曲线4将进入不安全区域（进程推进顺序非法）87/136互斥使用：在一段时间内，一个资源只能由一个进程独占使用，若别的进程也要求该资源，则须等待直至其占用者释放；保持和等待：允许进程在不释放其已分得资源的情况下请求并等待分配新的资源；非剥夺性：进程所获得的资源在未使用完之前，不能被其它进程强行夺走，而只能由其自身释放；循环等待：存在一个等待进程集合，P0正在等待一个P1占用的资源，P1正在等待一个P2占用的资源，…，Pn正在等待一个由P0占用的资源。3.5.3产生死锁的必要条件88/136预防死锁：通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或者几个，预防死锁。避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态，避免死锁。检测死锁：检测死锁的发生，确定与死锁有关的进程与资源，采取措施，从系统中将已发生的死锁清除。解除死锁：通过撤消和挂起一些进程，回收一些资源，分配给处于阻塞状态的进程，使之转为就绪状态。3.5.4解决死锁的基本办法89/1363.5.4解决死锁的基本办法90/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除91/136

3.6预防死锁的方法和避免死锁

在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。资源一次性分配；(破坏请求和保持条件)可剥夺资源；即当某进程新的资源未满足时，释放已占有的资源(破坏不可剥夺条件)资源有序分配法；系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反(破坏环路等待条件)

3.6.1预防死锁的方法92/136死锁避免定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意的系统性能来避免死锁。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。

3.6.2避免死锁93/136

安全状态指系统能按某种进程顺序来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态。

3.6.3安全状态与不安全状态94/1361)安全序列概念

一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j<i)当前占有资源量之和，系统处于安全状态。

(安全状态一定是没有死锁发生的)95/136

我们通过一个例子来说明安全性。假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：进程最大需求已分配可用P1P2P3104952232)安全序列举例安全序列（P2,P1,P3)96/136

如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。

因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。进程最大需求已分配可用P1P2P3104952233)由安全状态向不安全状态的转换

97/136讨论与练习98/136安全状态与不安全状态不安全状态:不存在一个安全序列，不安全状态一定导致死锁99/1363.6.4利用银行家算法避免死锁

1)银行家算法中的数据结构

(1)可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个。[ə'veiləbəl]

100/136

(2)最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。(3)分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。101/136(4)需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。Need［i,j］=Max［i,j］-Allocation［i,j］

102/136

设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查:(1)如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所请求的资源数已超过它所宣布的最大值;

(2)如果Requesti［j］≤Available［j］，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。2)银行家算法103/136(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值:

Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。104/1363)安全性算法

(1)设置两个向量：①工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;②Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false;当有足够资源分配给进程时，再令Finish［i］∶=true。105/136(2)从进程集合中找到一个能满足下述条件的进程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，执行步骤(3)，否则，执行步骤(4)。(4)如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work［j］∶=Work［j］+Allocation［i,j］;Finish［i］∶=true;gotostep2;106/1364)银行家算法之例

假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-15所示。图3-8T0时刻的资源分配表

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431

(1)T0时刻的安全性

资源进程WorkNeedAllocationWork+AllocationFinishABCABCABCABCp1332122200532truep3532011211743truep4743431002745truep0745743010755truep27556003021057true108/136(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中的圆括号所示。④再利用安全性算法检查此时系统是否安全。

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431Request1(1，0，2)

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

资源进程WorkNeedAllocationWork+AllocationFinishABCABCABCABCp1230020302532truep3532011211743truep4743431002745truep0745743010755truep27556003021057true111/136

(3)P4请求资源：P4发出请求向量Request4(3，3，0)

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431系统按银行家算法进行检查：①Request4(3,3,0)≤Need

(4,3,1);②Request4(3,3,0)>Available(2,3,0)，让P4等待。112/136(4)P0请求资源：P0发出请求向量Requst0(0，2，0)

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431系统按银行家算法检查：①Request0(0,2,0)≤Need

(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系统暂时先假定可为P0分配资源，并修改有关数据，如下图所示。

Request0(0，2，0)

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753030723210P1322302020P2902302600P3222211011P4433002431114/136(5)进行安全性检查:可用资源Available(2,1,0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源．如果把P0发出请求向量改为Request0(0,１,0)，系统是否可以将资源分配给它？？？

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753030723210P1322302020P2902302600P3222211011P4433002431Request0(0，1，0)

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

资源进程MaxAllocationNeedAvailableABCAB