1、今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 1 页页第四章 死锁及其对策4.1 死锁的基本概念死锁的基本概念4.2 死锁原理及对策死锁原理及对策4.3 鸵鸟算法鸵鸟算法4.4 死锁的检测和恢复死锁的检测和恢复4.5 死锁预防死锁预防4.6 死锁避免死锁避免今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 2 页页4.1 死锁的基本概念死锁的基本概念在计算机系统中，产生死锁的直接原因是多个进在计算机系统中，产生死锁的直接原因是多个进程的并发执行。多个进程的并发执行改善了系统资源程的并发执行。多个进程的并发执行改善了系统资源
2、的利用率，提高了系统的处理能力，但由于每个系统的利用率，提高了系统的处理能力，但由于每个系统资源都由多个进程共享，有些资源本身又要求互斥的资源都由多个进程共享，有些资源本身又要求互斥的使用，所以如果处理不当就可能产生死锁。使用，所以如果处理不当就可能产生死锁。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 3 页页4.1.1 4.1.1 资源资源依资源的性质：可剥夺和非可剥夺资源依资源的性质：可剥夺和非可剥夺资源可剥夺资源可剥夺资源：处理机和内存处理机和内存非可剥夺资源非可剥夺资源：磁带和打印机磁带和打印机依资源的使用方式：共享资源和独享资源依资源的使用方式
3、：共享资源和独享资源共享资源共享资源：处理机、内存、磁盘等处理机、内存、磁盘等独享资源独享资源：磁带机、读卡机和打印机等磁带机、读卡机和打印机等依资源的使用期限：永久资源和临时资源依资源的使用期限：永久资源和临时资源永久资源永久资源：硬资源和可重入的纯代码过程硬资源和可重入的纯代码过程临时资源临时资源：进程同步和通信过程中出现的消息、信号的数据。进程同步和通信过程中出现的消息、信号的数据。在进行资源分配时，一定要先认清相应资源的特性，以便选择在进行资源分配时，一定要先认清相应资源的特性，以便选择合适的分配策略，在竞争非剥夺资源和临时性资源时都可能产生死合适的分配策略，在竞争非剥夺资源和临时性资
4、源时都可能产生死锁。在并发进程的活动中，若选择一种合理的推进顺序就可以避免锁。在并发进程的活动中，若选择一种合理的推进顺序就可以避免死锁的发生。死锁的发生。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 4 页页4.1.2 死锁的定义死锁的定义死锁是计算机系统中多道程序并发执行时，两个或死锁是计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争系统资源而出现的一种互相等两个以上的进程由于竞争系统资源而出现的一种互相等待的现象。待的现象。此时，每个进程都此时，每个进程都“占用占用”一些其他进程正在等待一些其他进程正在等待的资源，而用，每个进程都的资源，
5、而用，每个进程都 没有完全得到所有的资源，没有完全得到所有的资源，结果所有这些进程互相等待，谁也无法继续，我们称这结果所有这些进程互相等待，谁也无法继续，我们称这些进程是死锁的，相应的计算机系统处于死锁状态。些进程是死锁的，相应的计算机系统处于死锁状态。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 5 页页4.1.3 产生死锁的原因产生死锁的原因系统竞争临界资源系统竞争临界资源。当系统所拥有的某种临界资源当系统所拥有的某种临界资源个数比各个进程要求该资源的总数要少时，则有可能引个数比各个进程要求该资源的总数要少时，则有可能引起多个并发进程对资源的竞争而产生
6、死锁。起多个并发进程对资源的竞争而产生死锁。进程推进顺序不当进程推进顺序不当，进程运行过程中，由于请示和进程运行过程中，由于请示和释放资源的顺序不当，而产生死锁。释放资源的顺序不当，而产生死锁。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 6 页页1、竞争临界资源引起的死锁、竞争临界资源引起的死锁u 竞争非剥夺性资源引起的死锁竞争非剥夺性资源引起的死锁u 竞争临时性资源引起的死锁竞争临时性资源引起的死锁u 竞争同一类资源引起的死锁竞争同一类资源引起的死锁2、进程推进顺序不当引起的死锁、进程推进顺序不当引起的死锁今天日期：今天日期：2022-12-16第四章
7、第四章 死锁及其对策死锁及其对策第第 7 页页0 0G1G1G2G2G3G3A1A1B1B1C1C1D1D1P1P1进展进展P2P2进展进展A2A2B2B2C2C2D2D2占占用用R2R2占用占用R2R2DN占用占用R1R1占用占用R2R2占占用用R1R1占用占用R1R1今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 8 页页4.2 死锁原理及对策死锁原理及对策4.2.1 死锁原理及产生死锁的必要条件死锁原理及产生死锁的必要条件 死锁是与时间有关的一种现象，它涉及到多进程死锁是与时间有关的一种现象，它涉及到多进程的并发，并发进程对一些特殊资源的共享，以及具体
8、的并发，并发进程对一些特殊资源的共享，以及具体进行并发进程资源调度的时机等。综上所述，产生死进行并发进程资源调度的时机等。综上所述，产生死锁的四个必要条件如下：锁的四个必要条件如下：互斥条件、不可剥夺条件、部分分配条件、环路等待互斥条件、不可剥夺条件、部分分配条件、环路等待条件条件今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 9 页页4.2.2 死锁的描述死锁的描述1、资源分配图、资源分配图P2P1R1R2今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 10 页页2 2、死锁举例、死锁举例u竞争非剥夺性资源引起的死锁竞争
9、非剥夺性资源引起的死锁u竞争临时性资源引起的死锁竞争临时性资源引起的死锁u竞争同一类资源引起的死锁竞争同一类资源引起的死锁R1P1R2P2S1P1S3P3P2S2P1P2P3今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 11 页页4.2.3 解决死锁的方法解决死锁的方法1.预防死锁预防死锁：为了使系统不发生死锁现象，在系统设计初期即为了使系统不发生死锁现象，在系统设计初期即选择一些限制条件，来破坏产生死锁的四个必要选择一些限制条件，来破坏产生死锁的四个必要条件之一或其中几个。这样，系统中就不会出现条件之一或其中几个。这样，系统中就不会出现死锁现象。死锁现象
10、。2.避免死锁避免死锁：一方面预防死锁的方法会降低系统资源利用率；一方面预防死锁的方法会降低系统资源利用率；另一方面死锁的必要条件在存在未必就一定会使另一方面死锁的必要条件在存在未必就一定会使系统发生死锁。因此为提高系统资源的利用率，系统发生死锁。因此为提高系统资源的利用率，避免死锁并不严格限制死锁必要条件的存在，而避免死锁并不严格限制死锁必要条件的存在，而是在资源的动态分配过程中，使用某种方法去防是在资源的动态分配过程中，使用某种方法去防止系统进入不安全状态，从而避免死锁的最终出止系统进入不安全状态，从而避免死锁的最终出现。现。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对
11、策死锁及其对策第第 12 页页3.检测和解除死锁检测和解除死锁：在一些相对简单的系统中，为节省预防在一些相对简单的系统中，为节省预防和避免死锁而增加的系统开销，又因为死锁产生和避免死锁而增加的系统开销，又因为死锁产生的概率总是比较小的，所以系统中允许出现死锁的概率总是比较小的，所以系统中允许出现死锁状态。在这种系统中，专门设置了一个检测机构，状态。在这种系统中，专门设置了一个检测机构，可以随时检测出死锁的发生，并能确定与死锁有可以随时检测出死锁的发生，并能确定与死锁有关的进程和资源，然后采用适当的方法解除系统关的进程和资源，然后采用适当的方法解除系统中的死锁状态。常用的方法有：中的死锁状态。常
12、用的方法有：l一是强制性的撤销一些死锁进程，并剥夺它一是强制性的撤销一些死锁进程，并剥夺它们的资源给其余进程；们的资源给其余进程；l一是使用一个有效的挂起和解除挂起机构来一是使用一个有效的挂起和解除挂起机构来挂起一些进程，以便从被挂起的进程中剥夺挂起一些进程，以便从被挂起的进程中剥夺一些资源用来解除死锁。一些资源用来解除死锁。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 13 页页4.4 死锁的检测与恢复死锁的检测与恢复检测系统中是否存在死锁产生的必要条件：检测系统中是否存在死锁产生的必要条件：环路等待环路等待4.4.1 利用资源分配图描述系统状态利用资源
13、分配图描述系统状态1、死锁状态的推断思想、死锁状态的推断思想封锁进程封锁进程：是指某个进程由于请求了超过系统中现有是指某个进程由于请求了超过系统中现有的未分配资源数目的资源，而被系统封锁的进程。的未分配资源数目的资源，而被系统封锁的进程。非封锁进程非封锁进程：没有被系统封锁的进程没有被系统封锁的进程今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 14 页页2、资源分配图的化简、资源分配图的化简 假设某个资源分配图中存在一个进程假设某个资源分配图中存在一个进程PiPi，此刻，此刻 PiPi 是非是非封锁进程，那么可对此资源分配图作以下化简：当封锁进程，那么可对
14、此资源分配图作以下化简：当 PiPi 有请有请求边时，首先将其请求边变成分配边，即满足求边时，首先将其请求边变成分配边，即满足PiPi 进程的相应进程的相应资源请求，而一旦资源请求，而一旦PiPi 进程的所有资源请求都得到满足，进程的所有资源请求都得到满足，PiPi 进程就能在有限时间内运行结束，并释放它所占用的所有资进程就能在有限时间内运行结束，并释放它所占用的所有资源。所以此时源。所以此时PiPi 只有分配边，可以将所有这些分配边删去。只有分配边，可以将所有这些分配边删去。总之，对非封锁进程总之，对非封锁进程PiPi 的化简即删除资源分配图中与的化简即删除资源分配图中与PiPi 连接的所有
15、有向边，使连接的所有有向边，使PiPi 成为孤立结点。成为孤立结点。P2P1R1R2P2P1R1R2P2P1R1R2(a)(b)(c)今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 15 页页假如一个资源分配图可以被其上的所有进程所化简，则假如一个资源分配图可以被其上的所有进程所化简，则称该图为称该图为完全可化简的完全可化简的。反之，若一个资源分配图不能被其上的任一进程化简，反之，若一个资源分配图不能被其上的任一进程化简，则称其为则称其为不可化简的不可化简的。若某个资源分配图只能被其上的一些进程所化简，则该若某个资源分配图只能被其上的一些进程所化简，则该图为
16、图为非完全可化简的非完全可化简的。P2P1R1R2图图 完全可化简的资源分配图完全可化简的资源分配图P2P1R1R2图图 不可化简的资源分配图不可化简的资源分配图今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 16 页页3、死锁定理：当一个资源分配图是完全可化简时，该资当一个资源分配图是完全可化简时，该资源分配图能被其上所有的进程所化简。也就是此时系统中存源分配图能被其上所有的进程所化简。也就是此时系统中存在一个进程序列，按此安全序列的顺序运行，可使每个进程在一个进程序列，按此安全序列的顺序运行，可使每个进程都顺利完成，所以此时系统处于都顺利完成，所以此时系
17、统处于安全状态安全状态，即系统不会发生，即系统不会发生死锁。反之当某资源分配图是非完全可化简的时候，说明该死锁。反之当某资源分配图是非完全可化简的时候，说明该资源分配图不能被中的一些进程所化简。也就是此刻系统中资源分配图不能被中的一些进程所化简。也就是此刻系统中出现了一些互相等待的封锁进程，系统中不存在一个进程的出现了一些互相等待的封锁进程，系统中不存在一个进程的安全序列。这些互相等待的封锁进程永远无法运行到终点，安全序列。这些互相等待的封锁进程永远无法运行到终点，所以此时系统处于死锁状态。资源分配图中不能化简的进程所以此时系统处于死锁状态。资源分配图中不能化简的进程即为死锁进程。即为死锁进程
18、。死锁定理：系统中某个时刻死锁定理：系统中某个时刻S为死锁状态的充分必要条为死锁状态的充分必要条件是，件是，S时刻系统的资源分配图是非完全可化简的。时刻系统的资源分配图是非完全可化简的。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 17 页页4.4.2 死锁检测中的数据结构死锁检测中的数据结构 假设系统中的假设系统中的N N个进程个进程P P1 1,P,P2 2,P,Pn n，有，有M M种资源，种资源，R R1 1,R,R2 2,R,Rm m，则请求矩阵和分配矩阵都是一个，则请求矩阵和分配矩阵都是一个N NM M的二维数组：的二维数组：(1)请求矩阵请求
19、矩阵Re：是一个是一个N NM M的二维数组，的二维数组，每行代表一个进程当前对各类资源的请求数目。每行代表一个进程当前对各类资源的请求数目。若若Re(i,j)=k,Re(i,j)=k,则代表第则代表第 i i个进程个进程P Pi i请求了请求了R Rj j类类资源资源k k个分配单位。个分配单位。(2)分配矩阵分配矩阵Al：是一个是一个N NM M的二维数组，的二维数组，代表某个时刻系统中资源的分配情况。若代表某个时刻系统中资源的分配情况。若Al(i,j)=k,Al(i,j)=k,则代表第则代表第 i i个进程个进程P Pi i已分配到了已分配到了 R Rj j类资源类资源k k个分配单位。
20、个分配单位。P1 1Pn nP2 2R1 1R2 2Rm m )m,nRe(.),nRe(),nRe(.)m,Re(.),Re(),Re()m,Re(.),Re(),Re(212221212111 )m,n(Al.),n(Al),n(Al.)m,(Al.),(Al),(Al)m,(Al.),(Al),(Al212221212111今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 18 页页(3)(3)可利用资源向量可利用资源向量Av，是一个长度为是一个长度为M M的一维数组，表的一维数组，表示系统中各类资源的可利用数目。示系统中各类资源的可利用数目。(4)(4
21、)工作向量工作向量Work：是一个长度为是一个长度为M M的一维数组，动态的一维数组，动态的反映系统中可让进程运行的各类资源的数目。的反映系统中可让进程运行的各类资源的数目。(5)(5)进程向量进程向量L：是一个集合，所有已运行结束的进程都是一个集合，所有已运行结束的进程都送入送入L L中，若最后中，若最后L L中包括了所有的中包括了所有的N N个进程，则说明系统处个进程，则说明系统处于安全状态。于安全状态。)m(A.,),(A),(AA 21 )m(Work.,)(Work),(WorkWork21 今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 19 页
22、页4.4.3 死锁检测算法死锁检测算法1 1、在某个时刻在某个时刻T T，j j从从1 1到到M M执行执行Work(j)=Av(j)Work(j)=Av(j)。2 2、检查检查AlAl矩阵和矩阵和ReRe矩阵，是否存在某个矩阵，是否存在某个i(ii(i从从1 1到到M)M)使使AlAl矩阵第矩阵第i i行中所行中所有的有的Al(i,jAl(i,j)和和ReRe矩阵第矩阵第i i行中所有的行中所有的Re(i,jRe(i,j)均为零。若存在这个均为零。若存在这个i i说明在说明在资源分配图中资源分配图中PiPi进程已成为孤立结点，将进程已成为孤立结点，将PiPi进程送入进程向量进程送入进程向量L
23、 L中。中。3 3、在系统中除已送入在系统中除已送入L L之外的所有进程中逐个寻找，若某个之外的所有进程中逐个寻找，若某个 i i使使Re(i,jRe(i,j)=Work(j)=Work(j)，(j(j的取值从的取值从1 1到到M)M)，则执行：，则执行：1)j1)j从从1 1到到M M，Work(j)=Work(j)+Al(i,j)Work(j)=Work(j)+Al(i,j)2)j2)j从从1 1到到M M，令所有的，令所有的Al(i,j)=0Al(i,j)=0，所有的，所有的Re(i,j)=0Re(i,j)=03)3)将当前的这个进程也送入进程向量将当前的这个进程也送入进程向量L L中中
24、这样反复执行，直到所有这样反复执行，直到所有L L以外的进程中再没有满足上述条件为止。以外的进程中再没有满足上述条件为止。4 4、检查检查L L向量，若向量，若N N个进程都在个进程都在L L中，说明系统中不会发生死锁，反之，系中，说明系统中不会发生死锁，反之，系统中存在死锁，那些没能进入统中存在死锁，那些没能进入L L向量的进程均为死锁进程。向量的进程均为死锁进程。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 20 页页由于当系统中有了新的请求，而这种由于当系统中有了新的请求，而这种请求又不能立即满足时才可能发生死锁。请求又不能立即满足时才可能发生死锁。
25、所以在一个非死锁状态的前提下，要判断所以在一个非死锁状态的前提下，要判断下一个状态是否为死锁，只需要在某个进下一个状态是否为死锁，只需要在某个进程执行新的进程请求而又不能立即满足时，程执行新的进程请求而又不能立即满足时，进行死锁检测进行死锁检测，由于死锁检测算法执行时，由于死锁检测算法执行时间长、系统开销大，可以在较长时间间隔间长、系统开销大，可以在较长时间间隔后，执行一次检测算法。后，执行一次检测算法。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 21 页页4.4.4 死锁的恢复死锁的恢复强制性地从系统中撤销一些死锁进程，并剥夺它们的资源强制性地从系统中
26、撤销一些死锁进程，并剥夺它们的资源给其余进程。给其余进程。使用一个有效的挂起和解除机构来挂起一些进程，以便从使用一个有效的挂起和解除机构来挂起一些进程，以便从被挂起的进程中剥夺一些资源用来解除死锁被挂起的进程中剥夺一些资源用来解除死锁1、撤销进程、撤销进程：为了保证系统所受到的影响最小，可以逐个为了保证系统所受到的影响最小，可以逐个撤销进程，直到死锁不复存在为止。一般依次选择撤销代价最撤销进程，直到死锁不复存在为止。一般依次选择撤销代价最小的进程。小的进程。撤销代价包括：撤销代价包括：进程的优先数、运行代价（从重新启动该进程的优先数、运行代价（从重新启动该进程并运行到此撤销时刻所需要的时间）、
27、进程并运行到此撤销时刻所需要的时间）、该进程对应作业的外部代价。该进程对应作业的外部代价。2、挂起进程、挂起进程今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 22 页页4.5 死锁的预防死锁的预防4.5.1 4.5.1 打破打破“不剥夺不剥夺”条件条件强迫那些请求新资源而没有立即得到满足的进程释放它已保持的其它强迫那些请求新资源而没有立即得到满足的进程释放它已保持的其它资源，即一个进程已占用的资源在运行过程中可能要暂时释放。实现复杂，资源，即一个进程已占用的资源在运行过程中可能要暂时释放。实现复杂，只适用于只适用于CPUCPU和内存。和内存。4.5.2 4
28、.5.2 打破打破“部分分配部分分配”条件条件对某进程所要求的资源一次性地分配完毕，又称预先静态分配法。对某进程所要求的资源一次性地分配完毕，又称预先静态分配法。4.5.3 4.5.3 打破打破“环路等待环路等待”条件条件在资源的分配过程中，对资源的请求作出某种限制，使环路不可能出在资源的分配过程中，对资源的请求作出某种限制，使环路不可能出现。现。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 23 页页具体的方法是具体的方法是：为系统中每种资源规定一个唯一的为系统中每种资源规定一个唯一的序号，例如，输入机为序号，例如，输入机为1 1，打印机为，打印机为2
29、2，穿孔机为，穿孔机为3 3，磁带，磁带机为机为4 4，磁盘机为，磁盘机为5 5等，而且要求每个进程都要严格按照等，而且要求每个进程都要严格按照递增的顺序请求资源。若能认真的安排资源序号，将各递增的顺序请求资源。若能认真的安排资源序号，将各作业经常使用的、比较普通的资源安排成低序号，不常作业经常使用的、比较普通的资源安排成低序号，不常使用的资源、比较繁重的资源安排成高序号，便能提高使用的资源、比较繁重的资源安排成高序号，便能提高资源的利用率。但在各资源的序号安排好后，不能经常资源的利用率。但在各资源的序号安排好后，不能经常变动。变动。今天日期：今天日期：2022-12-16第四章第四章 死锁及
30、其对策死锁及其对策第第 24 页页4.6 死锁避免4.6.1 系统状态的安全性系统状态的安全性1 1、安全状态、安全状态：是指系统能按照某种顺序为每个进程分配所需的是指系统能按照某种顺序为每个进程分配所需的资源，使每个进程都能顺利完成。当且仅当系统资源，使每个进程都能顺利完成。当且仅当系统中存在此安全序列时，系统处于安全状态。中存在此安全序列时，系统处于安全状态。假设系统中有假设系统中有3 3个进程，个进程，1010个可供分配的资源单位个可供分配的资源单位进程进程 已分配资源已分配资源 还需申请的资源还需申请的资源P1 4 4P2 2 2P3 2 72 2、不安全状态、不安全状态：某个时刻系统
31、中不存在一个安全序列，能使所有某个时刻系统中不存在一个安全序列，能使所有的进程都顺利完成。不安全状态不是死锁状态，的进程都顺利完成。不安全状态不是死锁状态，进入不安全状态的进程有可能进入死锁。进入不安全状态的进程有可能进入死锁。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 25 页页银行家算法是银行家算法是最有代表性的避免死锁算法，由最有代表性的避免死锁算法，由DijkstrnDijkstrn提出。提出。1 1、银行家算法中的数据结构、银行家算法中的数据结构(1)(1)可利用资源向量可利用资源向量AvAv 它是一个含有它是一个含有m m个元素的数组，其中每
32、个元素代表一类个元素的数组，其中每个元素代表一类可利用资源的数目。可利用资源的数目。例如：例如：3253R2R1RAvAv数组数组4.6.2 银行家算法银行家算法 前提条件：前提条件：假设分配资源的单位是固定的，请求资源的进假设分配资源的单位是固定的，请求资源的进程数也固定不变，而且每个进程必须先告诉系统对某类资源的程数也固定不变，而且每个进程必须先告诉系统对某类资源的最大需求量，当某个进程要求的资源数量小于系统所拥有的该最大需求量，当某个进程要求的资源数量小于系统所拥有的该类资源的最大量时，系统会在有限的时间内满足进程的要求。类资源的最大量时，系统会在有限的时间内满足进程的要求。今天日期：今
33、天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 26 页页(2)(2)最大需求矩阵最大需求矩阵MaxMax n nm m矩阵，表示矩阵，表示n n个进程对个进程对m m类资源的最大类资源的最大需求。需求。例如：假设例如：假设n=5,m=3 2983124435726155P4P3P2P1P3R2R1RMaxMax矩阵为：矩阵为：今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 27 页页(3)(3)分配矩阵分配矩阵AlAl n nm m矩阵，表示每个进程已经分配到的资源矩阵，表示每个进程已经分配到的资源的数目。的数目。例如：设例如：设n
34、=5,m=3 2001122030020105P4P3P2P1P3R2R1RAlAl矩阵为：矩阵为：今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 28 页页(4)(4)需求矩阵需求矩阵NeedNeed n nm m矩阵，表示每个进程还需要各类资源矩阵，表示每个进程还需要各类资源的数目。的数目。例如：例如：n=5,m=3 1341100062213475P4P3P2P1P3R2R1RNeedNeed矩阵为：矩阵为：今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 29 页页所有所有Re(i,j)=Need(i,j)？(j=1
35、,2,m)所有所有Re(i,j)=Av(j)？(j=1,2,m)Av(j)=Av(j)-Re(i,j)Al(i,j)=Al(i,j)+Re(i,j)Need(i,j)=Need(i,j)-Re(i,j)(j=1,2,m)Av(j)=Av(j)+Re(i,j)Al(i,j)=Al(i,j)-Re(i,j)Need(i,j)=Need(i,j)+Re(i,j)(j=1,2,m)出错处理系统是否处于安全状态？系统是否处于安全状态？断定分配可以进行断定分配可以进行否否否否是是是是是是否否结束结束Pi必须等待执行安全执行安全性算法性算法恢复分配前资源状态恢复分配前资源状态Re：请求矩阵：请求矩阵Need
36、：需求矩阵：需求矩阵Av：可利用资源向量：可利用资源向量Al：分配矩阵：分配矩阵Max：最大需求矩阵：最大需求矩阵Work(j)=Av(i,j)(j=1,2,m)Finish(i)=False(i=1,2,n)找能满足找能满足Finish(i)=False(i=1,2,n)且且Need(i,j)=Work(j)(j=1,2,m)的进程的进程PiWork(j)=Work(j)+Al(i,j)(j=1,2,m)令令 Finish(i)=True说明系统处于不安全状态说明系统处于不安全状态即、至少有一个即、至少有一个Pi，使，使Finish(i)=False所有的所有的Finish(i)=True？
37、(i=1,2,n)则系统为安全状态则系统为安全状态安全性算法结束安全性算法结束找到找到是是找不到找不到否否今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 31 页页4.6.3 银行家算法举例设系统有五个进程和三类资源，每类资源分别有设系统有五个进程和三类资源，每类资源分别有1010、5 5、7 7。在在T T1 1时刻资源分配情况如下图：时刻资源分配情况如下图：2001122030020105P4P3P2P1P3R2R1RAlAl矩阵：矩阵：1341100062213475P4P3P2P1P3R2R1RNeedNeed矩阵：矩阵：2333R2R1RAvAv数
38、组：数组：今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 32 页页假设假设T1T1时刻时刻 初始状态为初始状态为 Work(j)=3 3 2 Finish(i)=F F F F F的的话。首先，判断它是否处于安全状态：话。首先，判断它是否处于安全状态：由于由于i=2i=2时，存在一个时，存在一个P2 P2，使，使Finish(2)=F Finish(2)=F，且，且 故由故由 Work(j)=Work(j)+Al(2,j)得到得到 Work(J)=5 3 2 Finish(iWork(J)=5 3 2 Finish(i)=F)=F T T F F F F
39、F F由于由于i=4i=4时，存在一个时，存在一个P4 P4，使，使Finish(4)=F Finish(4)=F，且，且 故由故由 Work(j)=Work(j)+Al(4,j)得到得到 Work(J)=7 4 3 Finish(iWork(J)=7 4 3 Finish(i)=F)=F T T F F T T F F由于由于i=5i=5时，存在一个时，存在一个P5 P5，使，使Finish(5)=F Finish(5)=F，且，且 故由故由 Work(j)=Work(j)+Al(5,j)得到得到 Work(J)=7 4 5 Finish(iWork(J)=7 4 5 Finish(i)=F
40、)=F T T F F T T T T 1341100062213475P4P3P2P1P3R2R1R=Work(j)=3 3 2 1341100062213475P4P3P2P1P3R2R1R=Work(j)=5 3 2 1341100062213475P4P3P2P1P3R2R1R=Work(j)=7 4 3Need=今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 33 页页由于由于i=3i=3时，存在一个时，存在一个P3 P3，使，使Finish(3)=F Finish(3)=F，且，且 故由故由 Work(j)=Work(j)+Al(3,j)得到得到
41、 Work(J)=10 4 7 Finish(iWork(J)=10 4 7 Finish(i)=F)=F T T T T T T T T 由于由于i=1i=1时，存在一个时，存在一个P1 P1，使，使Finish(1)=F Finish(1)=F，且，且 故由故由 Work(j)=Work(j)+Al(1,j)得到得到 Work(J)=10 5 7 Finish(iWork(J)=10 5 7 Finish(i)=)=T T T T T T T T T T 此时、安全标志为真，存在一个安全序列（此时、安全标志为真，存在一个安全序列（P2,P4,P5,P3,P1P2,P4,P5,P3,P1）,
42、所以系所以系统是安全的。统是安全的。1341100062213475P4P3P2P1P3R2R1R=Work(j)=7 4 5 1341100062213475P4P3P2P1P3R2R1R=Work(j)=10 4 7今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 34 页页.假设假设T2T2时刻时刻P2P2请求资源，即请求资源，即Re(2,j)=1 0 2Re(2,j)=1 0 2的话，使用银行家算法来判断，的话，使用银行家算法来判断，此时此时i=2i=2，Need(2,j)=1 2 2Need(2,j)=1 2 2AlR1 R2 R3NeedR1 R2
43、 R3AvR1 R2 R3Re R1 R2 R3P1P2P3P4P5 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 3 3 2 1 0 2满足满足Re(jRe(j)=Need(2,j)=Need(2,j)满足满足Re(j)=Av(jRe(j)=Av(j)AlR1 R2 R3NeedR1 R2 R3AvR1 R2 R3Re R1 R2 R3P1P2P3P4P5 0 1 0 3 0 2 3 0 2 2 1 1 0 0 2 7 4 3 0 2 0 6 0 0 0 1 1 4 3 1 2 3 0 1 0 2执行执行Av(j)=A
44、v(j)-Re(2,j)Al(2,j)=Al(2,j)+Re(2,j)Need(2,j)=Need(2,j)-Re(2,j)(j=1,2,m)今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 35 页页然后，对T2时刻进行安全性检查，方法同T1时刻。检查结果，可以找到一个安全序列（P2,P4,P5,P1,P3)。可以得出P2的请求不会导致系统进入不了安全状态。所以可以将P2申请的资料分配给他。今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 36 页页3.3.假设假设T3T3时刻时刻P5P5请求资源，即请求资源，即Re(5,j
45、)=3 3 0Re(5,j)=3 3 0的话，使用银行家算法来判断，此的话，使用银行家算法来判断，此时时i=5i=5，Need(5,j)=4 3 1Need(5,j)=4 3 1AlR1 R2 R3NeedR1 R2 R3AvR1 R2 R3Re R1 R2 R3P1P2P3P4P5 0 1 0 3 0 2 3 0 2 2 1 1 0 0 2 7 4 3 0 2 0 6 0 0 0 1 1 4 3 1 2 3 0 3 3 0满足满足Re(jRe(j)=Need(5,j)=Need(5,j)Re(j)=Av(jRe(j)=Av(j)不满足不满足所以所以P5P5必须等待必须等待今天日期：今天日期：
46、2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 37 页页4.4.假设假设T4T4时刻时刻P1P1请求资源，即请求资源，即Re(1,j)=0 2 0Re(1,j)=0 2 0的话，使用银行家算法来判断，此的话，使用银行家算法来判断，此时时i=1i=1，Need(1,j)=7 4 3Need(1,j)=7 4 3AlR1 R2 R3NeedR1 R2 R3AvR1 R2 R3Re R1 R2 R3P1P2P3P4P5 0 1 0 3 0 2 3 0 2 2 1 1 0 0 2 7 4 3 0 2 0 6 0 0 0 1 1 4 3 1 2 3 0 0 2 0满足满足Re(jRe(
47、j)=Need(1,j)=Need(1,j)满足满足Re(j)=Av(jRe(j)=Av(j)AlR1 R2 R3NeedR1 R2 R3AvR1 R2 R3Re R1 R2 R3P1P2P3P4P5 0 3 0 3 0 2 3 0 2 2 1 1 0 0 2 7 2 3 0 2 0 6 0 0 0 1 1 4 3 1 2 1 0 0 2 0执行执行Av(j)=Av(j)-Re(1,j)Al(1,j)=Al(1,j)+Re(1,j)Need(1,j)=Need(1,j)-Re(1,j)(j=1,2,m)今天日期：今天日期：2022-12-16第四章第四章 死锁及其对策死锁及其对策第第 38 页
48、页然后，对然后，对T4T4时刻进行安全性检查。此时，时刻进行安全性检查。此时，Work(jWork(j)=2 1 0)=2 1 0。找。找b b不不到一个满足条件的到一个满足条件的PiPi。即。即P1P1的这次请求要导致系统进入不了安全状态。的这次请求要导致系统进入不了安全状态。所以，所以，P1P1的申请不能满足，本次分配作废，要恢复的申请不能满足，本次分配作废，要恢复AlAl，NeedNeed和和AvAv数组，数组，并让并让P1P1等待。即对等待。即对AlR1 R2 R3NeedR1 R2 R3AvR1 R2 R3Re R1 R2 R3P1P2P3P4P5 0 3 0 3 0 2 3 0 2 2 1 1 0 0 2 7 2 3 0 2 0 6 0 0 0 1 1 4 3 1 2 1 0 0 2 0AlR1 R2 R3NeedR1 R2 R3AvR1 R2 R3Re R1 R2 R3P1P2P3P4P5 0 1 0 3 0 2 3 0 2 2 1 1 0 0 2 7 4 3 0 2 0 6 0 0 0 1 1 4 3 1 2 3 0 0 2 0执行执行Av(j)=Av(j)+Re(1,j)Al(1,j)=Al(1,j)-Re(1,j)Need(1,j)=Need(1,j)+Re(1,j)(j=1,2,m)
