1、第 6 章死 锁6.1 死锁的概念6.2 死锁的预防和避免6.3 死锁的检测与解除6.4 避免死锁实现举例习题第 6 章死 锁引入多道程序设计技术后，在系统中可以同时驻留多个程序，多个程序在运行过程中可能需要使用系统中的资源，而系统中能提供的资源是有限的，所以，必然会出现多个进程对资源的竞争情况。故所谓死锁，就是指多个进程在运行过程中因竞争资源而造成的一种僵局，若无外力作用，这些进程将无法再向前推进。下面举个例子来说明死锁问题，假设系统中有P1、P2两个并发执行的进程，P1和P2在执行中同时需要R1和R2两类资源，6.1 死死锁锁的的概概念念第 6 章死 锁其中R1是输入机，R2是打印机，P1
2、和P2的执行过程如下：第 6 章死 锁从上面的申请释放过程可以看出，进程P1和P2在执行过程中有可能会出现这种情况：例如，P2首先得到R2，然后P1得到R1，接着P1申请R2，由于资源R2已经分配给了进程P2，所以进程P1因得不到R2而被阻塞(阻塞原因是：申请R2，等待P2唤醒)；若P2继续运行，将要申请R1，此时R1分配给了进程P1，则占有R2资源的进程P2将阻塞在R1上，如果P2不能前进，则P1也不能继续下去，反之亦然。此时称这两个进程处在死锁状态。第 6 章死 锁6.1.1 死锁的形成原因死锁的形成原因计算机系统中的各种资源(包括硬件资源和软件资源)都由操作系统进行管理和分配。作业在运行
3、过程中所需要的资源，可以在调度到某个作业时，根据作业提出的要求(例如，需要多少主存空间和需要哪些外围设备等)来进行分配；此外也可以是在进程执行时，根据各个进程的执行情况动态地申请资源(例如，请求读某个文件、请求扩充主存区域以及请求使用打印机输出结果等)。第 6 章死 锁前面的章节中介绍的对各类资源的管理和分配技术，主要目的是要充分发挥各个资源的作用，提高资源的利用率。当多个进程竞争共享资源时，还可以采用必要的措施来实现资源的互斥使用和保证进程能在有限的时间内获得所需的资源。但是，这些管理和分配都是根据作业或进程对某类或某个资源的需求来进行分配和调度的，而没有考虑一个进程已经占有某些资源后又要申
4、请其他资源时会发生怎样的情况。实际上，计算机系统中有限的资源与众多请求系统分配资源的进程之间会存在着矛盾。第 6 章死 锁当若干进程需求资源的总数大于系统能提供的资源数时，多个进程间就会出现竞争资源的现象，如果对进程竞争的资源管理或分配不当就会引起死锁。死锁产生的根本原因在于系统中的资源不能满足所有进程的需要，如果系统中的资源足够多，多到可以满足所有进程的需求，那么系统中的进程就不会因申请资源而陷入阻塞状态，即不会产生死锁。第 6 章死 锁1资源分配图资源分配图计算机系统中拥有着大量的资源，这些资源是在操作系统的统一管理和控制下进行分配和回收的。在多道环境下，系统中多个进程共享系统资源，而系统
5、资源是有限的，所以会导致多个进程对于资源的竞争。为了便于理解死锁的概念，在这里引入一个新的内容资源分配图。第 6 章死 锁资源分配图是由一组结点N和一组边E所组成的点对集合，即G=(N，E)，具有下述定义和限制：(1)N是两个互斥的子集，一组是进程结点P=P1，P2，P3，一组是资源结点R=R1，R2，R3，N=PR。(2)E中的每条边连接P中的一个结点和R中的一个结点。如果E中的一条边e=Pi，Rj，表示进程Pi请求资源Rj；第 6 章死 锁如果E中的一条边e=Rj，Pi，表示资源Rj已经分配给了进程Pi。在资源分配图中用圆圈代表进程，方框代表一类资源。由于一类资源可能有多个，在方框中用一个
6、点来代表一类资源中的一个资源。请求边是由进程指向资源，分配边是由资源指向进程。图6-1所示的是一个资源分配图，表示进程P1和P2共享两类资源R1和R2，其中R1类资源有2个，一个分配给了进程P1，R2资源分配给进程P2。图中有两条请求边(P1,R2)与(P2,R1)和两条分配边(R1,P1)与(R2,P2)。第 6 章死 锁图6-1 资源分配图第 6 章死 锁【例6-1】现假定有3类资源R1，R2，R3，其中R1和R3都只有1个资源，R2有2个资源。有3个进程P1，P2，P3，每个进程占用资源和等待资源的情况如表6-1所示。第 6 章死 锁表表6-1 进程和资源的分配情况进程和资源的分配情况第
7、 6 章死 锁于是，可做出如图6-2所示的资源分配图。图6-2 资源分配图第 6 章死 锁2.形成原因形成原因死锁产生的根本原因是由于系统资源不足以满足所有用户的所有的资源需求，因此，进程在执行过程中将会产生对资源的竞争使用情况。死锁的形成原因主要有以下两种：1)竞争资源系统中并发执行的进程共享着系统中的资源，系统中的资源数不足以满足所有进程的最大需求，所以进程间会竞争资源，从而才有可能出现进程间相互等待对方资源的情况。如图6-1所示，资源R2分配给了进程P2，而进程P1在运行时也需要资源R2，即请求R2。这样进程P1和P2就要竞争资源R2。第 6 章死 锁2)进程推进顺序不当进程具有异步性，
8、进程是以“停停走走”的步骤向前推进着，所以可能使得进程按着下述两种顺序向前推进。(1)进程推进顺序合理。如图6-3所示，有两个并发执行的进程P1和P2，共享两个资源R1和R2。X轴方向表示进程P1向前推进，Y轴方向表示进程P2向前推进，进程在推进过程中将申请或释放资源。在图6-3中如果进程P1和P2按照曲线、和的顺序向前推进，则两个进程都可以顺利完成，这种进程的推进顺序也不会引起死锁。第 6 章死 锁图6-3 进程推进顺序对死锁的影响第 6 章死 锁下面以曲线为例来分析一下进程执行过程：初始情况下资源R1和R2空闲。曲线表示进程P1先占有处理机执行，在执行过程中当执行到Request(R1)时
9、，表示进程P1将申请资源R1，此时R1空闲，进程P1得到满足可以继续执行；当执行到Request(R2)时，表示进程P1申请资源R2，也可以得到满足，继续执行；当执行到Release(R1)时，表示释放R1；当执行到Release(R2)时，表示释放R2；此后，进程P2将占有处理机。第 6 章死 锁P2占有处理机后，申请R2能够得到满足(P1执行结束已经释放了R1和R2，R1和R2空闲)继续执行，申请R1可以得到满足继续执行，释放R2，再释放R1。曲线、的情况和情况类似，进程都可顺利完成，不会陷入死锁状态。(2)进程推进顺序不当。如图6-3所示，如果进程P1和P2按照曲线的顺序推进，它们将会进
10、入阴影区。这时P1保持了R1，P2保持了R2，而P1和P2不论是谁占有处理机继续运行都将要申请另一个资源却又得不到，将进入阻塞状态，这时系统有可能死锁。第 6 章死 锁6.1.2 产生死锁的必要条件产生死锁的必要条件 死锁将会给计算机系统带来很大的麻烦，如果系统中并发执行的进程陷入死锁的状态，不仅涉及到死锁的那些进程无法再继续执行下去，而且还将妨碍其他进程的执行，甚至会导致系统的瘫痪。因此解决死锁就越发显得必要了。要解决死锁，应先分析在什么情况下可能发生死锁，从上述的例子中可以看出，产生死锁有如下4个必要条件。第 6 章死 锁1.互斥条件互斥条件并发执行的进程共享着系统中的资源，而进程对资源是
11、排它使用的，即在某段时间内每一个资源只能给一个进程使用。如果有某一个进程申请资源，该资源却被其他进程占有，则申请者必须等待，直到占有该资源的进程释放为止。2.不可剥夺条件不可剥夺条件不可剥夺，即不可抢占性，指的是当资源被某个进程占有后，除非此进程使用完毕释放了该资源，否则就不能被其他的进程强行抢占。第 6 章死 锁3.请求与保持条件请求与保持条件请求指的是进程申请资源，保持指的是进程已经拥有了部分资源。进程具有异步性，拥有部分资源就可以运行，那么在运行过程中必然要申请其他资源。4.环路等待条件环路等待条件一旦发生死锁，系统中的进程和资源之间必然形成了一条封闭的环路。如图6-2所示，各进程占用和
12、等待资源的情况没有形成环路，因而没有死锁发生。但是，如果进程P3又提出申请一个R2类资源的要求，由于当前R2中没有可被分配的资源，因此，要增加一条有向边P3R2，如图6-4所示。第 6 章死 锁图6-4 资源分配图(有环有死锁)第 6 章死 锁从图6-4中可看出进程P2在等待被进程P3占用的资源R3，进程P3在等待被进程P1或P2占用的资源R2，进程P1又在等待被进程P2占用的资源R1。于是，存在两条环路：P1R1P2R3P3R2P1P2R3P3R2P2这两条环路使进程P1，P2，P3等待资源的状态永远结束不了，这三个进程陷入死锁状态。因此，系统一旦发生死锁，进程和资源之间就形成了一条封闭的环
13、路。第 6 章死 锁图6-5 资源分配图(有环无死锁)第 6 章死 锁环路等待条件是死锁产生的必要条件而不是充分条件，即进程和资源之间形成环路却不一定会产生死锁。如图6-5所示，也存在一条环路：P1R1P3R2P1。但是，这条环路不形成死锁。因为进程P1和进程P3分别等待R1和R2类中的资源，由于进程P2和进程P4不再申请其他资源，它们能在有限时间里执行结束并归还 R1类和R2类资源，归还的资源可以分配给进程P1和进程P3。显然进程P1和进程P3也不会永远处于等待资源的状态。因此可以得出环路等待条件是死锁产生的必要条件而不是充分条件。第 6 章死 锁6.1.3 处理死锁的基本方法处理死锁的基本
14、方法上述是死锁的4个必要条件，即系统一旦发生死锁，上述条件必然成立；反之，如果上述条件之一不成立，则死锁就不会发生。根据上述分析，如果死锁发生，系统中的进程僵持不下，都处于阻塞的状态而无法运行结束，就会浪费大量的系统资源，甚至导致系统崩溃，因此必须要解决死锁问题。从理论上讲，解决死锁并不是很难，只要消除上述任一个条件就可以了。操作系统的设计者们研究了许多方法，主要提出了以下几种方法。第 6 章死 锁1.预防死锁预防死锁通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。预防死锁是一种比较容易实现的方法，已被广泛使用。但由于所施加的限制条件有时太严格，可能导致系统
15、资源利用率和系统吞吐量降低。2.避免死锁避免死锁不需要预先采取各种措施去破坏产生死锁的必要条件，而是在资源的动态分配过程中，采取某种措施去防止系统进入不安全状态，从而避免发生死锁。这种方法只需要在事先加以较弱的限制条件，便可获得较高的资源利用率及系统吞吐量，但在实现的过程中有一定的难度。在目前较完善的系统中，常用此方法来避免发生死锁。第 6 章死 锁3.检测死锁检测死锁这种方法预先并不采取任何措施，也不检查系统是否已经进入了不安全区，此法允许系统在运行过程中发生死锁。但可通过系统设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源，然后采取适当措施，从系统中将已经发生的死
16、锁清除掉。第 6 章死 锁4.解除死锁解除死锁这是与检测死锁相配套的一种措施，用于将进程从死锁的状态下解脱出来。常用的措施是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已经处于阻塞状态的进程，使之转为就绪状态继续运行。第 6 章死 锁6.2.1 死锁的预防死锁的预防死锁的预防是解决死锁的一种静态策略，它是通过采取某些措施，破环死锁的4个必要条件，从而达到防止死锁的目的。6.2 死锁的预防和避免死锁的预防和避免 第 6 章死 锁1.破坏互斥条件破坏互斥条件死锁产生的4个必要条件中第1个条件是互斥条件，要使互斥使用资源的条件不成立，唯一的办法是允许进程共享资源。“只读”文件是一种很好的
17、共享资源，多个进程可以同时打开一个“只读”文件，同时对该文件执行“只读”操作，因而进程在使用“只读”文件时不会成为等待状态。但是，在计算机系统中大多数资源都是必须互斥使用的，这是由资源本身的固有特性决定的，要求进程对于某些资源的访问必须是排它的。第 6 章死 锁2.破坏不可剥夺条件不可剥夺条件是指不允许进程抢夺已经被分配的资源。为了使这个条件不成立，进程在运行过程中可能已经拥有了部分资源，在运行中还要请求新的资源，如果一个进程在请求新资源时，不能立即得到满足，那么在其改为阻塞状态之前，必须释放其占有的全部资源，以后如果再需要，再重新申请。这样就破坏了不可剥夺条件。抢夺策略的具体做法如下：(1)
18、若进程A申请的资源r已被进程B占用，则查看进程B的状态。如果进程B处于等待另一个资源的状态，那么就抢夺进程B已占的资源r并把r分配给进程A；如果进程B不是处于等待资源状态，则让进程A处于等待资源r的状态。第 6 章死 锁(2)一个等待资源的进程只有在得到自己所申请的新资源和所有被抢夺的老资源后才能继续执行。这种可抢夺的资源分配策略不是对所有资源都适用的，例如，对打印机、磁带机等就不能采用抢夺的方式，否则会造成使用混乱。目前抢夺式的分配策略只适用于主存空间和处理机。例如，当若干进程都请求扩充主存空间得不到满足而处于等待时，为防止永远等待的发生，系统就可抢夺某进程已占的主存空间分配给一个等待主存资
19、源的进程，使该进程得到足够的主存空间后能执行到结束，然后归还所占的全部主存空间，系统再把收回的主存空间分配给被抢夺了主存空间的进程或其他等待主存空间的进程，使它们能继续执行。第 6 章死 锁对处理机的分配中，“时间片轮转”和“可抢占的优先数调度”算法就是抢夺式的分配处理机的策略。此外，一个占有处理机的进程在申请其他资源得不到满足时，系统把该进程置成等待资源的状态，也就是抢夺了该进程使用处理机的权力，把处理机分配给其他的进程使用。通过破坏“不可剥夺”条件来实现预防死锁的目的是比较困难的，需要系统花费时间在进程之间进行资源的协调分配，此外，被剥夺资源的进程可能要长期处于等待的状态，系统吞吐量降低。
20、第 6 章死 锁3.破坏请求与保持条件破坏请求与保持条件操作系统将每个进程在执行过程中需要的全部资源一次性分配，这种资源分配的策略称为“静态分配”，该方法是预防死锁发生的最简单的方法。如果某个进程所需要的资源系统能全部满足，系统就一次性将所需的资源全部分配给该进程，这样，进程在运行过程中就不会再提出新的资源要求，当进程运行结束将释放其占有的全部资源。如果某个进程所需要的资源不能全部满足，那么系统将不分配给该进程任何资源，让该进程处于等待状态。通过这种方法，处于等待状态的进程不占有任何资源，运行状态的进程也不会因请求资源得不到满足而进入等待状态。这样，就破坏了请求与保持条件，系统也不会陷入死锁。
21、静态分配资源的策略实现起来简单，但却降低了资源的利用率。第 6 章死 锁4.破坏环路等待条件破坏环路等待条件操作系统在进行分配时，通过采用有序资源分配法来破坏环路等待条件。该方法的基本思想是把系统中所有资源顺序编号，例如，磁带机=1，打印机=2，输入机=3，等等。要求任何一个进程在申请两个以上的资源时，必须严格按照资源编号递增的顺序申请资源，即每个进程只有在较低编号的资源请求得到满足后，它才能提出对较高编号的资源的申请，否则系统不予分配。第 6 章死 锁进程PB，使用资源的顺序是R2，R1；若采用动态分配有可能形成环路条件，造成死锁。若采用有序资源分配法，R1的编号为1，R2的编号为2，则：P
22、A申请次序应是R1，R2；PB申请次序应是R1，R2。这样就破坏了环路等待条件，避免了死锁的发生。第 6 章死 锁采用按序分配策略的最大困难是怎样合理地给各个资源编号，通常应按大多数进程使用资源的次序来给资源顺序编号。但是，总会有一些进程使用资源的次序与系统确定的资源编号的顺序不一致，就会出现后使用的资源必须先申请，先得到的资源可能在较长的时间里是空闲的，明显降低了资源的使用率。例如，某个进程要先使用打印机，再使用磁带机，根据按序分配的思想，该进程必须先申请到磁带机以后才能申请打印机，从而造成磁带机的浪费。第 6 章死 锁6.2.2 系统的安全状态系统的安全状态 死锁的避免是不去理会死锁产生的
23、4个必要条件，而是在资源的分配过程中，操作系统通过运行一个管理程序对提出资源需求的进程进行检查，通过模拟资源的分配过程，并判断是否会使得系统陷入死锁，从而避免死锁的发生。首先，这里需要引入两个重要的概念安全状态和安全序列。第 6 章死 锁1.安全状态安全状态 所谓安全状态，是指系统能按照某种顺序如P1，P2，P3，Pn，其中P1，P2等为系统中的进程，为每个进程分配其所需要的资源，并达到最大的需求，使得每个进程可以顺利完成。2.安全序列安全序列所谓安全序列，是指系统中所有的进程都能够执行完毕的一种执行次序，如P1，P2，P3，Pn。从定义中可以得知安全序列不唯一。第 6 章死 锁安全序列必须包
24、括当前系统中的所有进程，如果某个进程因资源不够而不能完成，则不存在安全序列，当前系统就处于不安全状态，可能导致死锁；如果系统在任意时刻都处于安全状态，则系统是安全的，不会有死锁产生。【例例6-2】假设系统中有3个进程P1、P2、P3，共有12台磁带机。进程P1需要10台磁带机，P2需要4台，P3需要9台。设某一时刻T0，进程占有资源的情况如表6-2所示。请判断系统在T0时刻是否安全，如果安全，请给出安全序列。第 6 章死 锁表表6-2 T0时刻的资源分配情况时刻的资源分配情况进 程 需 求 已 分 配 P1 10 5 P2 4 2 P3 9 2 第 6 章死 锁解：系统共有资源12台，P1占有
25、5台，P2占有2台，P3占有2台，系统剩余的空闲资源还有12-5-2-2=3台。P1还需要10-5=5台能够运行完成；P2还需要4-2=2台能够运行完成；P3还需要9-2=7台能够运行完成。第 6 章死 锁如果将系统剩余的3台磁带机分配给P2，那么P2就能顺利完成并释放资源，这时系统剩余的资源数为5台磁带机，此后将5台磁带机分给P1进程也能使其顺利完成并释放资源，这时系统剩余的资源数为10，能够满足P3的需求，使得P3也能完成。通过上述分析可以得知，如果系统按照P2、P1、P3的顺序分配资源，每个进程都能够顺利完成，即系统是安全的，P2、P1、P3是安全序列。第 6 章死 锁6.2.3 银行家
26、算法银行家算法 与死锁的预防相比，死锁的避免是一种动态策略，保证系统不进入死锁状态，对进程发出的资源请求进行动态检查，并根据检查结果决定是否分配资源。在进行资源分配动态检查时，如果发现分配资源后系统进入不安全状态，则不进行资源分配，否则满足进程的需要，分配资源。银行家算法是最具有代表性的避免死锁的方法，银行家算法需要如下几个重要的数据结构。为了描述方便，假设系统中有n个进程共享m类资源。第 6 章死 锁1.数据结构数据结构(1)Max矩阵。Max是一个nm的矩阵，表示系统中每个进程对各类资源的最大需求。(2)Allocation矩阵。Allocation是一个nm的矩阵，表示系统中每一个进程已
27、经占有的各类资源的数量。第 6 章死 锁(3)Need矩阵。Need是一个nm的矩阵，表示系统中每个进程运行完成还需要的各类资源的数量。从定义中可以得知Need矩阵=Max矩阵-Allocation矩阵。(4)Available矩阵。Available矩阵是含有m个元素的数组，表示系统剩余的可用资源数。第 6 章死 锁2.算法执行过程算法执行过程进程在执行过程中可能要请求资源，设Requesti是进程Pi对资源的请求向量，如果Requestj=k，表示进程Pi需要k个Rj资源。当进程Pi提出资源请求时，系统将按照如下过程进行动态检查：(1)如果RequestiNeedi，则转向步骤(2)；否则
28、出错，因为进程Pi请求的资源数超出进程运行完成还需要的资源数。第 6 章死 锁(2)如果RequestiAvailable，则转向步骤(3)，否则该进程必须等待，因为系统剩余的资源数不能满足进程的需要。(3)进行资源预分配，假设系统满足进程的需要，则将资源分配给进程Pi，并且修改相应的数据结构：Available=Available-Requesti；Allocation=Allocation+Requesti；Needi=Needi-Requesti；第 6 章死 锁(4)系统执行安全性算法，检查此次预分配后，系统是否处于安全状态。如果处于安全状态，正式将资源分配给进程Pi；否则，此次预分配
29、失败，恢复预分配前的系统的资源分配状态，让进程Pi处于等待状态。第 6 章死 锁3.安全性算法安全性算法安全性算法是用来检查系统是否处于安全状态的一种常用算法。安全性算法需要定义如下几个重要的数据结构。1)工作向量WorkWork表示系统可提供给进程继续运行所需要的各类资源的数目，即Work=Available。2)Finish向量Finish向量表示系统是否有足够的资源分配给进程，使其能运行完成，初始情况下Finish值均为False，当有足够的资源分配给进程使其能运行完成时，该进程对应的Finish的值变为True。第 6 章死 锁安全性算法的执行过程如下：(1)从n个进程中找到一个满足下
30、述条件的进程：Finishi=False NeediWork如果找到，执行步骤(2)，否则执行步骤(3)。(2)当进程Pi获得资源后，能够顺利完成，并释放占有的所有资源，这时需要修改两个向量Work和Finish。Work=Work+Allocationi Finishi=True转到步骤(1)。第 6 章死 锁(3)如果所有进程的Finishi=True，则表示所有的进程均顺利完成，即系统处于安全状态；否则，系统处于不安全状态。这里通过两个例子来分别理解安全性算法和银行家算法。【例例6-3】设系统中有3种类型的资源(A、B、C)和3个进程P1、P2、P3。已知A、B、C的总数为10、4、11
31、，在T0时刻的状态如表6-3所示，问T0时刻是否安全，如安全请给出安全序列。第 6 章死 锁表表6-3 各进程在各进程在T0时刻的资源需求和分配情况时刻的资源需求和分配情况第 6 章死 锁解：根据安全性算法Work向量：(2,3,3)，所有进程的Finishi=False 根据算法找到满足Finishi=False并且NeediWork的进程只有P3，P3获得资源至最大需求，顺利完成，修改：Finish3=TrueWork=(2,3,3)+(2,0,4)=(4,3,7)第 6 章死 锁 根据算法要求继续查找是否有满足Finishi=False并且NeediWork条件的进程，此时找到进程P2，
32、顺利完成，修改：Finish2=TrueWork=(4,3,7)+(4,0,2)=(8,3,9)同上，找到进程P1，完成后修改：Finish1=TrueWork=(8,3,9)+(2,1,2)=(10,4,11)系统中所有进程的Finishi=True，即系统处于安全状态，安全序列为P3、P2、P1第 6 章死 锁【例例6-4】设系统中有3种类型的资源(A、B、C)和5个进程P1、P2、P3、P4、P5。已知A、B、C的总数为17、5、20，在T0时刻的状态如表6-4所示。第 6 章死 锁表表6-4 各进程在各进程在T0时刻的资源需求和分配情况时刻的资源需求和分配情况第 6 章死 锁系统采用银
33、行家算法避免死锁。问：(1)T0时刻是否为安全状态？若是，请给出安全序列。(2)若T0时刻P2请求(0,3,4)，能否实施分配？为什么？(3)在(2)的基础上P4请求(2,0,1)，能否实施分配？为什么？(4)在(3)的基础上P1请求(0,2,0)，能否实施分配？为什么？第 6 章死 锁解：(1)根据安全性算法检查T0时刻是否安全。系统剩余可用资源：A类：17-(2+4+4+2+3)=2B类：5-(1+0+0+0+1)=3C类：20-(2+2+5+4+4)=3即Available=(2,3,3)根据安全性法算法检查可以得出在T0时刻系统是安全的，安全序列为P5、P4、P2、P3、P1、P4、P
34、5、P2、P1、P3等以P4、P5开头的序列。第 6 章死 锁(2)P2(0,3,4)Need2(1,3,4)成立 P2(0,3,4)Available(2,3,3)不成立所以，不能实施分配，进程P2处于等待状态。(3)P4(2,0,1)Need4(2,2,1)成立 P4(2,0,1)Available(2,3,3)成立进行预分配，修改相应的数据结构，修改后进程的资源需求和分配情况如表6-5所示。第 6 章死 锁表表6-5 P4请求资源预分配后各进程的资源需求和分配情况请求资源预分配后各进程的资源需求和分配情况第 6 章死 锁 Need4=(2,2,1)-(2,0,1)=(0,2,0)Allo
35、cation4=(2,0,4)+(2,0,1)=(4,0,5)Available=(2,3,3)-(2,0,1)=(0,3,2)根据安全性算法可以得知系统是安全的，可以找到安全序列P4、P5、P2、P1、P3，所以可以实施分配，这时系统将正式进入如表6-5所示的状态。第 6 章死 锁(4)在(3)的基础之上，P1提出请求资源，由于在(3)后，系统已经进入表6-5所表示的状态，所以此后的所有操作将是在表6-5所示的状态下完成的。P1(0,2,0)Need1(3,4,7)成立P1(0,2,0)Available(0,3,2)成立进行预分配，修改相应的数据结构，修改后进程的资源需求和分配情况如表6-
36、6所示。Need1=(3,4,7)-(0,2,0)=(3,2,7)Allocation1=(2,1,2)+(0,2,0)=(2,3,2)Available=(0,3,2)-(0,2,0)=(0,1,2)第 6 章死 锁表表6-6 P1请求资源预分配后各进程的资源需求和分配情况请求资源预分配后各进程的资源需求和分配情况第 6 章死 锁根据安全性算法可以得知系统剩余资源(0,1,2)不能满足任何一个进程的需要，即所有进程都不能顺利完成，所以不能实施分配，系统将回到如表6-5所示的状态，进程P1处于等待状态。第 6 章死 锁1.死锁的检测死锁的检测 通过对资源分配图进行简化可以检测出系统是否处于死锁
37、的状态，简化方法如下：(1)在资源分配图中，找到一个既不孤立也不阻塞的进程结点。如果该进程顺利结束将释放其占有的全部资源，即相当于消去资源分配图中该进程的所有请求边和分配边，使其变为孤立结点。如图6-6(a)所示，进程P1是既不阻塞也非孤立的结点，消去其两个分配边和一个请求边后，形成如图6-6(b)所示的情况。6.3 死锁的检测与解除死锁的检测与解除第 6 章死 锁(2)重复(1)的简化方法，则可以找到进程P2，消去P2的所有边，如图6-6(c)所示。如果能消去所有的边，使所有进程成为孤立的结点，则称该图是完全可简化的，如果不能，即有一条边消不去，则说明该图是不可完全简化的。死锁定理：如果系统
38、处于死锁状态，当且仅当其资源分配图是不可完全简化的。第 6 章死 锁图6-6 资源分配图的简化第 6 章死 锁2.死锁的解除方法死锁的解除方法当系统进入死锁状态时，需要立即解决，打破僵局，常采用以下两种方法：(1)撤销进程。撤销进程是最简单的方法，然而强行终止某个进程，可以使得系统从死锁状态中解救出来，但是进程前期所做的工作将前功尽弃，代价很大。稍好一些的方法是按照某种顺序逐个地终止进程，直到有足够的资源可以利用，死锁状态消除为止。(2)抢夺资源。从其他进程抢夺足够的资源来解除死锁状态，和前面死锁预防方法中“打破不可剥夺条件”所付出的代价是一样的。第 6 章死 锁1实验内容实验内容避免死锁实验
39、。2实验目的实验目的多个进程动态地共享系统的资源时可能会产生死锁现象。银行家算法是通过对资源的分配进行动态地检查来达到避免死锁的目的。本实验通过模拟银行家算法的应用，使读者了解银行家算法的执行过程。从而进一步理解死锁产生的条件和避免死锁问题产生的方法。6.4 避免死锁实现举例避免死锁实现举例第 6 章死 锁3实验题目实验题目编写一段程序模拟银行家算法。4实验提示实验提示(1)死锁的产生必须同时满足4个条件：互斥条件，即一个资源每次只能由一个进程占用。请求与保持条件，即某进程请求资源不能满足时，它必须等待，同时它仍保持已得到的所有其他资源。不可剥夺条件，任何一个进程不能抢占另一个进程已经获得且未
40、释放的资源。环路等待条件，系统进入死锁的状态时，进程和资源之间形成一条封闭的环路。第 6 章死 锁(2)银行家算法是一种具有代表性的避免死锁的算法。银行家算法为资源分配定义了两种状态，安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。处于安全状态的系统一定没有死锁发生。不安全状态：当系统中不存在一个安全序列时系统处于不安全状态。不安全状态下可能导致死锁发生。本实例就是根据银行家算法来检查系统状态是否处于安全状态。第 6 章死 锁5.实例代码实例代码/银行家算法实例 bank.c/运行环境Redhad9.0 gcc 4.0#include
41、stdlib.h#include stdio.h#define alloclen sizeof(struct allocation)#define maxlen sizeof(struct max)#define avalen sizeof(struct available)#define needlen sizeof(struct need)#define finilen sizeof(struct finish)#define pathlen sizeof(struct path)第 6 章死 锁struct allocation /分配的资源 int value;struct alloc
42、ation*next;struct max /最大需求 int value;struct max*next;struct available /可利用资源 int value;struct available*next;struct need /需要的资源 第 6 章死 锁 int value;struct need*next;struct path /安全序列 int value;struct path*next;struct finish /完成状态 int stat;struct finish*next;int main()第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁
43、第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁第 6 章死 锁1.什么是死锁？死锁产生的原因是什么？2.设系统中有A、B、C三类资源为10，5，7个，有P0，P1，P2，P3，P4进程，在T0时刻的系统状态如表6-7所示。习习 题题第 6 章死 锁表表6-7 在在T0时刻的系统状态时刻的系统状态第 6 章死 锁问：(1)T0时刻系统安全吗？
44、如果安全则给出安全序列。(2)有请求Request1=1,0,2，能否分配？为什么？(3)在(2)之后有一个新状态，此时Request0=0,2,0能否分配？为什么？3.设系统中仅有一类资源，数量为m，由n个进程竞争m个资源。当Needi0对i=1,2，n且所有进程对该类资源的需求总和m+n。证明该系统是无死锁的。如果不限定小于m+n，则该系统死锁的必要条件是什么？第 6 章死 锁4.系统处于不安全状态，但有可能不导致死锁。请举例验证之。5.考虑十字路口的交通死锁问题：把通过十字路口的汽车看做进程，十字路作为资源，画出进程资源图，说明产生死锁问题的四个必要条件在此例中均成立。6.讨论死锁检测算法与进程资源图中环路检测之间的关系。7.如何预防死锁？8.死锁产生的必要条件是什么？9.如何对资源分配图进行化简？10.在银行家算法中，若出现如表6-8所示的资源分配情况：第 6 章死 锁表表6-8 资源分配情况资源分配情况第 6 章死 锁试问：(1)当前状态是否安全？(2)如果进程P2提出请求Request2=(1,2,2,2)，系统能否将资源分配给它？说明原因。
