1、第四章第四章 死锁死锁n死锁的概念死锁的概念n死锁的预防和避免死锁的预防和避免n死锁的检测和解除死锁的检测和解除1死锁的概念死锁的概念n死锁举例死锁举例n产生死锁的原因产生死锁的原因 n产生死锁的必要条件产生死锁的必要条件 n处理死锁的基本方法处理死锁的基本方法 2死锁举例（死锁举例（1）n两个小孩在一起玩耍，一个在玩皮球，另一两个小孩在一起玩耍，一个在玩皮球，另一个玩自动步枪个玩自动步枪n如果这两个小孩都要对方手中的玩具，而又如果这两个小孩都要对方手中的玩具，而又不肯先放掉自己拿着的玩具，这时就发生了不肯先放掉自己拿着的玩具，这时就发生了僵持局面。僵持局面。3死锁举例（死锁举例（2）n设系统
2、有一台打印机和一台扫描仪，进程设系统有一台打印机和一台扫描仪，进程P1、P2并发执行，在某时刻并发执行，在某时刻T，进程，进程P1和和P2分别占用分别占用了打印机和扫描仪。了打印机和扫描仪。n在时刻在时刻T1（T1T），），P1又要申请扫描仪，但由又要申请扫描仪，但由于扫描仪被于扫描仪被P2占用，占用，P1只有等待。只有等待。n在时刻在时刻T2（T2T），），P2又申请打印机，但由于又申请打印机，但由于打印机被打印机被P1占用，占用，P2只有等待。只有等待。n如此两进程均不能执行完成。称这种现象为死锁。如此两进程均不能执行完成。称这种现象为死锁。4 n在生产者在生产者-消费者问题中将生产者进程
3、的两个消费者问题中将生产者进程的两个P操操作颠倒时会发生死锁。作颠倒时会发生死锁。n将消费者进程的两个将消费者进程的两个P操作颠倒时也会发生死锁。操作颠倒时也会发生死锁。死锁举例（死锁举例（3）5死锁的定义死锁的定义n一组进程中，两个或多个进程都无限期地等待永一组进程中，两个或多个进程都无限期地等待永远不会发生的条件，我们称此系统处于死锁状态。远不会发生的条件，我们称此系统处于死锁状态。n死锁（死锁（Deadlock）n饥饿（饥饿（Starvation）6死锁的起因死锁的起因n根本原因：系统能够提供的资源个数比要求该资根本原因：系统能够提供的资源个数比要求该资源的进程所需的资源个数少。源的进程
4、所需的资源个数少。7判断判断 1 1、参与死锁的所有进程都占有资源、参与死锁的所有进程都占有资源 错误：有可能有的进程在等待其他进程释放资源错误：有可能有的进程在等待其他进程释放资源 2 2、参与死锁的所有进程均正在等待资源、参与死锁的所有进程均正在等待资源 错误：有可能一个占有资源错误：有可能一个占有资源 3 3、参与死锁的所有进程中至少有两个进程占有、参与死锁的所有进程中至少有两个进程占有资源资源 错误错误 4 4、参与死锁的进程至少有两个、参与死锁的进程至少有两个 正确正确8关于死锁的一些结论关于死锁的一些结论参与死锁的进程最少是两个参与死锁的进程最少是两个 （两个以上进程才会出现死锁）
5、（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃甚至导致系统崩溃9产生死锁的必要条件产生死锁的必要条件四个必要条件（重点）四个必要条件（重点）n互斥条件：涉及的资源是非共享的。互斥条件：涉及的资源是非共享的。n不剥夺条件：不能强行剥夺进程拥有的资源。不剥夺条件：不能强行剥夺进程拥有的资源。n部分分配条件：进程在等待
6、一新资源时继续占有部分分配条件：进程在等待一新资源时继续占有已分配的资源。已分配的资源。n环路条件：存在一种进程的循环链，链中的每一环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所个进程已获得的资源同时被链中的下一个进程所请求。请求。10处理死锁的基本方法处理死锁的基本方法1、预防死锁：、预防死锁：n通过设置某些限制条件，去破坏死锁四个必要条通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。件中的一个或多个，来防止死锁。n较易实现，广泛使用，但由于所施加的限制往往较易实现，广泛使用，但由于所施加的限制往往太严格，可能导致系统资源利用率和
7、系统吞吐量太严格，可能导致系统资源利用率和系统吞吐量的降低。的降低。11处理死锁的基本方法（续）处理死锁的基本方法（续）2 2、避免死锁：、避免死锁：n不事先采取限制去破坏产生死锁的条件，而是在不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。进入不安全状态，从而避免死锁的发生。n实现较难，只需要较弱的限制条件，可获得较高实现较难，只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量。的资源利用率和系统吞吐量。12处理死锁的基本方法（续）处理死锁的基本方法（续）3、检测死锁：、检
8、测死锁：n事先并不采取任何限制，也不检查系统是否进入事先并不采取任何限制，也不检查系统是否进入不安全区，允许死锁发生，但可通过检测机构及不安全区，允许死锁发生，但可通过检测机构及时检测出死锁的发生，并精确确定与死锁有关的时检测出死锁的发生，并精确确定与死锁有关的进程和资源，然后采取适当措施，将系统中已发进程和资源，然后采取适当措施，将系统中已发生的死锁清除掉生的死锁清除掉13处理死锁的基本方法（续）处理死锁的基本方法（续）4、解除死锁：、解除死锁：n与检测死锁相配套，用于将进程从死锁状态解脱与检测死锁相配套，用于将进程从死锁状态解脱出来。出来。n常用的方法是撤消或挂起一些进程常用的方法是撤消或
9、挂起一些进程。以回收一些。以回收一些资源，再将它们分配给处于阻塞状态的进程，使资源，再将它们分配给处于阻塞状态的进程，使之转为就绪状态。之转为就绪状态。n实现难度大，但可获得较好的资源利用率和系统实现难度大，但可获得较好的资源利用率和系统吞吐量。吞吐量。14死锁的预防和避免死锁的预防和避免n死锁的预防死锁的预防 n系统的安全状态系统的安全状态 n利用银行家算法避免死锁利用银行家算法避免死锁15死锁的预防死锁的预防n在系统设计时确定资源分配算法，保证不发生死在系统设计时确定资源分配算法，保证不发生死锁锁n具体的做法是破坏产生死锁的四个必要条件之一具体的做法是破坏产生死锁的四个必要条件之一16破坏
10、部分分配条件破坏部分分配条件n系统要求所有进程要一次性地申请在整个运行过系统要求所有进程要一次性地申请在整个运行过程中所需的全部资源。若系统有足够资源则完全程中所需的全部资源。若系统有足够资源则完全分配。分配。17 优点：简单、易于实现且安全。优点：简单、易于实现且安全。缺点：缺点：n一个用户在作业运行之前可能提不出他的作业将要使用的全一个用户在作业运行之前可能提不出他的作业将要使用的全部设备。部设备。n用户作业必须等待，直到所有资源满足才能运行。实际上某用户作业必须等待，直到所有资源满足才能运行。实际上某些资源可能要到运行后期才会用到。些资源可能要到运行后期才会用到。n一个作业运行期间，对某
11、些设备的使用时间很短，甚至不会一个作业运行期间，对某些设备的使用时间很短，甚至不会用到。如：当用户作业出错时才需要打印机输出错误信息，用到。如：当用户作业出错时才需要打印机输出错误信息，但采用静态分配法必须把打印机分配给该作业，并长期占用。但采用静态分配法必须把打印机分配给该作业，并长期占用。采用该方法对系统来说是非常浪费的。采用该方法对系统来说是非常浪费的。破坏部分分配条件破坏部分分配条件方法分析方法分析18破坏不可剥夺条件破坏不可剥夺条件n一个已拥有资源的进程，若它再提出新资源要求一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的而不能立即得到满足时，它必
12、须释放已经拥有的所有资源。以后需要时再重新申请。所有资源。以后需要时再重新申请。n实现复杂、要付出很大的代价。实现复杂、要付出很大的代价。19破坏环路条件破坏环路条件n系统中的所有资源都有一个确定的唯一号码，所系统中的所有资源都有一个确定的唯一号码，所有分配请求必须以序号上升的次序进行。有分配请求必须以序号上升的次序进行。n例如：系统中有下列设备：输入机（例如：系统中有下列设备：输入机（1），打印），打印机（机（2），穿孔机（），穿孔机（3），磁带机（），磁带机（4），磁盘），磁盘（5）。有一进程要先后使用输入机、磁盘、打）。有一进程要先后使用输入机、磁盘、打印机，则它申请设备时要按输入机、打
13、印机、磁印机，则它申请设备时要按输入机、打印机、磁盘的顺序申请。盘的顺序申请。20破坏环路条件破坏环路条件方法分析方法分析n优点：同前两法相比，其资源利用率和系统吞吐优点：同前两法相比，其资源利用率和系统吞吐量有较明显的改善。量有较明显的改善。n缺点：缺点：进程实际需要资源的顺序不一定与资源的进程实际需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费。编号一致，因此仍会造成资源浪费。21系统的安全状态系统的安全状态n死锁避免定义：死锁避免定义：在系统运行过程中，对进程发出的每一个系统能在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结够满足的资源申请进
14、行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。锁，则不予分配，否则予以分配。22安全状态安全状态如果系统能按某种顺序（如如果系统能按某种顺序（如P4,P1,Pn，称，称为安全序列）为每个进程分配其所需的资源，直为安全序列）为每个进程分配其所需的资源，直至所有进程都能运行完成，称系统处于安全状态。至所有进程都能运行完成，称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状若不存在这样一个安全序列称系统处于不安全状态。态。23安全状态举例安全状态举例n有三个进程有三个进程p1、p2、p3，有，有1
15、2台磁带机。台磁带机。nP1共要求共要求10台，台，P2共要求共要求4台，台，P3共要求共要求9台。台。n在在T0时刻，时刻，p1,p2,p3分别获得分别获得5、2、2台，尚有台，尚有3台空闲。台空闲。24分析分析进程最大需求已分配还需可用p110553p2422p3927经分析，在经分析，在T0时刻，系统是安全的。时刻，系统是安全的。因为存在一个安全序列因为存在一个安全序列p2、p1、p3。见下图。见下图。25由安全状态向不安全状态的转换由安全状态向不安全状态的转换n如果不按安全序列分配资源，则系统可能会由安如果不按安全序列分配资源，则系统可能会由安全状态进入不安全状态。全状态进入不安全状态
16、。n如在如在T0以后，以后，P3要求要求1台磁带机，若系统分给它台磁带机，若系统分给它一台，则系统进入不安全状态。一台，则系统进入不安全状态。n因为其余因为其余2台分给台分给P2，P2完成后，只能释放完成后，只能释放4台，台，这既不能满足这既不能满足P1（5台），也不能满足台），也不能满足P3（6台）。将导致死锁。台）。将导致死锁。n可见当可见当P3申请资源时，尽管系统中有资源也不申请资源时，尽管系统中有资源也不能分给它。能分给它。26系统进入不安全状态系统进入不安全状态进程最大需求已分配还需可用p110552p2422p393627利用银行家算法避免死锁利用银行家算法避免死锁最有代表性的避免
17、死锁算法，由最有代表性的避免死锁算法，由Dijkstra提出。提出。1、银行家算法中的数据结构、银行家算法中的数据结构n可利用资源向量可利用资源向量Available。它是一个含有。它是一个含有m个元个元素的数组，其中每个元素代表一类可利用资源的素的数组，其中每个元素代表一类可利用资源的数目。数目。n如：如：28ABC523利用银行家算法避免死锁（续）利用银行家算法避免死锁（续）n最大需求矩阵最大需求矩阵Max。n*m矩阵，表示矩阵，表示n个进程的个进程的每一个对每一个对m类资源的最大需求。类资源的最大需求。ABCP1562P2331P3425P433229利用银行家算法避免死锁（续）利用银行
18、家算法避免死锁（续）n分配矩阵分配矩阵Allocation。n*m矩阵，表示每个进程矩阵，表示每个进程分配的资源数。分配的资源数。ABCP1212P2121P3222P413230利用银行家算法避免死锁（续）利用银行家算法避免死锁（续）n需求矩阵需求矩阵Need。n*m矩阵，表示每个进程还需矩阵，表示每个进程还需要各类资源数。要各类资源数。ABCP1352P2211P3223P423231例例n设系统有五个进程和三类资源，每类资源分别有设系统有五个进程和三类资源，每类资源分别有10、5、7。在。在T0时刻资源分配情况如图：时刻资源分配情况如图：32银行家算法描述银行家算法描述当进程当进程pi提
19、出资源申请时，系统执行下列步骤：提出资源申请时，系统执行下列步骤：（1）若）若RequestiNeedi，转（，转（2）；）；否则错误返回否则错误返回（2）若若RequestiAvailable，转（转（3）；否则进程等待）；否则进程等待33银行家算法描述（续）银行家算法描述（续）（3）假设系统分配了资源，则有：）假设系统分配了资源，则有：Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-Requesti（4）执行安全性算法，若系统新状态是安全的，）执行安全性算法，若系统新状态是安全的，则分
20、配完成，若系统新状态是不安全的，则恢复则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待。原状态，进程等待。34安全性算法安全性算法n为进行安全性检查，定义数据结构：为进行安全性检查，定义数据结构：nWork:ARRAY0.m-1 of integer;nFinish:ARRAY0.n-1 of Boolean;nm代表资源的数量，代表资源的数量，n代表进程的数量代表进程的数量35安全性算法步骤安全性算法步骤(1)Work:=Available;Finish:=false;(2)寻找满足下列条件的寻找满足下列条件的i：a)Finishi=false;b)NeediWork;如果不存在，
21、则转如果不存在，则转(4)36安全性算法步骤（续）安全性算法步骤（续）(3)Work:=Work+Allocationi;Finishi:=true;转转(2)(4)若对所有若对所有i,Finishi=true,则系统处于安全状态，则系统处于安全状态，否则处于不安全状态否则处于不安全状态37T0时刻的安全性检查时刻的安全性检查T0时刻可以找到一个安全序列时刻可以找到一个安全序列p1,p3,p4,p2,p0.系统是安全的。系统是安全的。38例例1：T0时刻时刻P1请求资源请求资源P1发出请求发出请求Request(1,0,2)，执行银行家算法，执行银行家算法39执行安全性算法执行安全性算法可以找
22、到一个安全序列可以找到一个安全序列p1,p3,p4,p0,p2.系统是安全的，系统是安全的，可以将可以将P1的请求分的请求分配给它。配给它。40例例2：P4请求资源请求资源nP4发出请求发出请求Request(3,3,0)，执行银行家算法，执行银行家算法nAvailable=2 3 0Available=2 3 0n不能通过算法第不能通过算法第2步步（RequestiAvailableRequestiAvailable），所以），所以P4等待。等待。41例例3：P0请求资源请求资源nRequest（0，2，0），执行银行家算法），执行银行家算法42进行安全性检查进行安全性检查nAvailabl
23、e2,1,0已不能满足任何进程需要，所以已不能满足任何进程需要，所以系统进入不安全状态，系统进入不安全状态，P0的请求不能分配的请求不能分配43n练习：有三类资源练习：有三类资源A(17)、B(5)、C(20)。有。有5个进程个进程P1P5。T0时刻系统状态如下：时刻系统状态如下：问问(1)T0时刻是否为安全状态，给出安全序列。时刻是否为安全状态，给出安全序列。(2)T0时刻，时刻，P2:Request(0,3,4)，能否分配，为什么？，能否分配，为什么？(3)在在(2)的基础上的基础上P4：Request(2,0,1)，能否分配，为什么？，能否分配，为什么？(4)在在(3)的基础上的基础上P
24、1：Request(0,2,0)，能否分配，为什么？，能否分配，为什么？最大需求已分配P15 5 92 1 2P25 3 64 0 2P34 0 114 0 5P44 2 52 0 4P54 2 43 1 444解：解：(1)T0时刻得出安全系列时刻得出安全系列最大需求已分配NeedP15 5 92 1 23 4 7P25 3 64 0 21 3 4P34 0 114 0 50 0 6P44 2 52 0 42 2 1P54 2 43 1 41 1 0A(17)、B(5)、C(20)Work=available=2 3 3先求出先求出Need和和Work45WorkAllocationNeed
25、W+AFinishP52 3 33 1 41 1 05 4 7TP45 4 72 0 42 2 17 4 11TP37 4 114 0 50 0 611 4 16TP211 4 164 0 21 3 415 4 18TP115 4 182 1 23 4 717 5 20TWork=2 3 346(2)P2:Request(0,3,4)n因因（Available=2 3 3）Request(0,3,4)所以不所以不能分配能分配47(3)P4：Request(2,0,1)48Available=2 3 3AllocationNeedAvailableP12 1 23 4 70 3 2P24 0 2
26、1 3 4P34 0 50 0 6P44 0 50 2 0P53 1 41 1 0有安全序列有安全序列P4 P5 P3 P2 P1 可以分配可以分配WorkAllocationNeedW+AFinishP40 3 24 0 50 2 04 3 7TP54 3 73 1 41 1 07 4 11TP37 4 114 0 50 0 611 4 16TP211 4 164 0 21 3 415 4 18TP115 4 182 1 23 4 717 5 20T49(4)P1：Request(0,2,0)AllocationNeedAvailableP12 3 23 2 70 1 2P24 0 21 3
27、 4P34 0 50 0 6P44 0 50 2 0P53 1 41 1 00 1 2 已不能满足任何进程的需要，不能分配已不能满足任何进程的需要，不能分配50死锁的检测和解除死锁的检测和解除死锁检测：死锁检测：n允许死锁发生，操作系统不断监视系统进展情况，允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生判断死锁是否发生n一旦死锁发生则采取专门的措施，解除死锁并以一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行最小的代价恢复操作系统运行51检测时机：检测时机：n 当进程等待时检测死锁当进程等待时检测死锁 （其缺点是系统的开销大）（其缺点是系统的开销大）n 定时检
28、测定时检测n 系统资源利用率下降时检测死锁系统资源利用率下降时检测死锁52死锁的解除死锁的解除 重要的是以最小的代价恢复系统的运行。方法如重要的是以最小的代价恢复系统的运行。方法如下：下：1）重新启动）重新启动 2）撤消进程）撤消进程 3）剥夺资源）剥夺资源 4）进程回退）进程回退53资源分配图资源分配图n 用有向图描述进程的死锁用有向图描述进程的死锁 准确、形象准确、形象 n 系统由若干类资源构成，一类资源称为一个资系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为源类；每个资源类中包含若干个同种资源，称为资源实例资源实例54 二元组二元组G=（V，E）V：结
29、点集，分为：结点集，分为P，R两部分两部分 P=p1,p2,pn R=r1,r2,rm E：边的集合，其元素为有序二元组：边的集合，其元素为有序二元组 (pi,rj)或或(rj,pi)55表示法表示法资源类（资源的不同类型）资源类（资源的不同类型）用方框表示用方框表示资源实例（存在于每个资源中）资源实例（存在于每个资源中）用方框中的黑圆点（圈）表示用方框中的黑圆点（圈）表示进程进程 用圆圈中加进程名表示用圆圈中加进程名表示56分配边：分配边：资源实例资源实例进程的一条有向边进程的一条有向边申请边：申请边：进程进程资源类的一条有向边资源类的一条有向边5758例例死锁定理死锁定理n如果资源分配图中
30、没有环路，则系统中没有死锁，如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁如果图中存在环路则系统中可能存在死锁n如果每个资源类中只包含一个资源实例，则环路如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件是死锁存在的充分必要条件59资源分配图化简资源分配图化简1）找一个非孤立点进程结点且只有分配边，去掉）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点分配边，将其变为孤立结点2）再把相应的资源分配给一个等待该资源的进程，）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边即将某进程的申请边变为分配边3）重复以
31、上步骤，若所有进程成为孤立结点，称）重复以上步骤，若所有进程成为孤立结点，称该图是可完全简化的，否则称该图是不可完全简该图是可完全简化的，否则称该图是不可完全简化的。化的。死锁状态的充分条件是：当且仅当资源分配图是不死锁状态的充分条件是：当且仅当资源分配图是不可完全简化的。可完全简化的。6061有环有死锁有环有死锁62有环无死锁有环无死锁有安全系列如下有安全系列如下WorkAllocationNeedW+AFinishP12 2 03 0 20 2 05 2 2TP35 2 22 1 10 1 17 3 3TP47 3 30 0 24 3 17 3 5TP07 3 50 2 07 3 37 5
32、 5TP27 5 53 0 26 0 010 5 7T63例：例：nP0请求：请求：Reqest(0,1,0)AllocationNeedAvailableP00 1 07 4 32 3 0P13 0 20 2 0P23 0 26 0 0P32 1 10 1 1P40 0 24 3 164n试探分配后试探分配后AllocationNeedAvailableP00 2 07 3 32 2 0P13 0 20 2 0P23 0 26 0 0P32 1 10 1 1P40 0 24 3 12 2 0P15 2 2P37 3 3P47 3 5P07 5 5P210 5 765习题习题1 1 已分配的资
33、源已分配的资源最大需求量最大需求量 A A B BC CA AB BC CP P1 1 0 1 0 10 07 75 53 3P P2 2 2 0 2 00 03 32 22 2P P3 3 3 3 0 02 29 90 02 2P P4 4 2 2 1 11 12 22 22 2P P5 5 0 0 0 02 24 43 33 3剩余资源剩余资源A AB BC C 3 33 3 2 266问题问题:此状态是否为安全状态，如果此状态是否为安全状态，如果 是是,则找出安全序列则找出安全序列在此基础上在此基础上P P2 2 申请（申请（1 1，0 0，2 2）能否分配？为什么？）能否分配？为什么？
34、P P5 5 申请（申请（3 3，3 3，0 0）能否分配？为什么？）能否分配？为什么？P P1 1 申请（申请（0 0，2 2，0 0）能否分配？为什么？）能否分配？为什么？67习题习题21、一台计算机共一台计算机共8台磁带机，由台磁带机，由N个进程共享，每个进程共享，每个进程最多要个进程最多要3台，问台，问N为多少时不会有死锁，为多少时不会有死锁，为什么？为什么？N=22、有、有R1(2)、R2(1)两类资源和两个进程两类资源和两个进程P1、P2，两个进程均以两个进程均以申请申请R1申请申请R2申请申请R1释放释放R1释放释放R2释释放放R1顺序使用资源，求可能达到的死锁点，并画出此时顺序使用资源，求可能达到的死锁点，并画出此时的资源分配图。的资源分配图。68解解n当两个进程都执行完第当两个进程都执行完第1步后，无论哪个进程执步后，无论哪个进程执行完第行完第2步，以后，这两个进程再申请资源时就步，以后，这两个进程再申请资源时就会死锁。会死锁。P1P2R1R269小结小结70
