计算机操作系统第5章死锁

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,计算机操作系统,第,5,章,死,锁,从进程同步的概念可以知道，当并发进程需要竞争使用资源或需要相互协作向前推进时，如果不采取同步措施，或同步措施不恰当，那么很容易导致并发进程不能向前推进而陷入僵局，即死锁现象。死锁是发生在一组相互竞争或协作的进程与线程之间的一个非正常现象。,死锁是所有操作系统都面临着的潜在问题，操作系统除了需要预防死锁、防止死锁外，还需要能够检测死锁，并从死锁中进行恢复。,本章的主要内容如下：,死锁的产生；,死锁的预防；,死锁的防止；,死锁的检测和解除；,线程死锁。,5.1,死锁的产生,5.1.1,死锁产生的原因,竞争资源引起死锁,在多道程序系统，多个进程共享系统的资源。系统资源分为二类，一类是不可抢占的资源，如打印机、磁带机等。当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。另一类是可抢占的资源，如,CPU、,内存等。由于系统拥有的不可抢占的资源有限，多个进程共享竞争不可抢占的资源就可能引起死锁。,进程推进顺序不当引起死锁,在多道程序系统中，并发执行的进程推进序列不可予测，有些推进顺序，进程可以顺利完成，这些推进顺序是合法的；而有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成了死锁。,5.1.1 死锁产生的原因续,进程推进顺序不当引起死锁例：,进程,P,和,Q,并发执行，进程,P,和,Q,程序如下：,Process P Process Q,.,Get A Get B,.,Get B Get A,.,Release A Release B,.,Release B Release A,.,5.1.1 死锁产生的原因续,P,A,Q,B,当,P、Q,按如下次序执行时：,P:GET A,Q:GET B,P:GET B,Q:GET A,A,B,C,S2,S1,S3,哲学家吃面的问题,A:,P(S1),P(S3),Eating,V(S3),V(S1),B:,P(S2),P(S1),Eating,V(S1),V(S2),C:,P(S3),P(S2),Eating,V(S2),V(S3),A:P(S1),B:P(S2),C:P(S3),A:P(S3):,阻塞,B:P(S1):,阻塞,C:P(S2):,阻塞,A,S1,C,S3,S2,B,5.1.2,死锁产生的条件,1.产生死锁的必要条件 Conditions for Deadlock,互斥 Mutual exclusion 条件：一个资源一次只能被一个进程所使用，即是排它性使用。,不可抢占 No preemption 条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强占。,请求和保持 Hold-and-wait 条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。,环路等待 Circular wait 条件：当每类资源只有一个时，在发生死锁时，必然存在一个进程-资源的环形链。如一系统状态的资源分配图所示，P1正在等待一个P2 占用的资源R2，P2正在等待一个P1占用的资源R1。,5.1.2,死锁产生的条件,(,续,),2.,资源分配图,由结点和边组成。结点有二类，一类是进程结点，用园圈表示；另一类是资源结点，用小方框表示一类资源，用方框中的小圈表示资源数。边也有二类，一类是分配边，它由资源结点指向进程结点，另一类是申请边，它由进程结点指向资源结点。,返回,R,1,R,2,P,1,P,2,5.1.2,死锁产生的条件,(,续,),3.处理死锁的根本方法,a.死锁的预防,静态方法：在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个必要条件之一，防止发生死锁。,B.死锁的防止,动态的方法：在进程执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是在进程申请资源时用某种方法去防止系统进入不平安状态，从而防止发生死锁。,C.死锁的检测和解除,这种方法预先并不采用任何限制措施，允许系统在运行过程中发生死锁，但可通过系统设置的检测机构及时检测死锁的发生，如检测到死锁，那么采用撤消进程等死锁解除方法使系统正常工作。,5.2,死 锁 预 防,(,Deadlock Prevention,),预防死锁的方法是破坏四个产生死锁的必要条件之一。,1。破坏互斥条件,互斥使用是资源本身特征所决定的。使用硬软件结合可改变资源本身特性，例如采用SPOOLing技术可将“独享 打印机改变为“共享的打印机。,2。破坏不可抢占条件,抢占式调度法主要用于处理机和存贮器资源调度，它们的状态容易保存和恢复。但此法对外部设备和私存数据不宜使用。,5.2,死 锁 预 防,(,Deadlock Prevention,)-1,3。破坏请求和保持条件,系统可采用资源静态予分配方式来破坏请求保持条件。系统要求所有进程一次性地申请在整个运行过程中全部资源，假设系统有足够资源满足给进程，那么在运行前，一次性将其所需要的所有资源分配给该进程。这样该进程在整个运行期间，便不再提出资源要求，从而摒弃了请求条件。这种预防死锁的方法，优点是简单、易予实现且很平安，但其资源利用率很低，进程也延迟运行。,4。破坏循环等待条件,有序资源使用法,该方法将所有的资源按类型进行线性排队，并赋予不同的序号。例如令输入机的序号为1，打印机序号为2，磁盘机序号为3等。,5.2,死 锁 预 防,(,Deadlock Prevention,)-,2,所有进程对资源的请求必须严格按资源序号递增的次序提出。这样在所形成的资源分配图中不可能再出现环路，因而摒弃了“环路等待条件，在采用这种策略时总有一个进程占据了较高序号的资源，它继续请求的资源必然是空闲的，因而进程可以一直向前推进。这种预防死锁的策略可以提高资源利用率，但在进程使用各类资源的顺序与系统规定的顺序不同时会造成资源浪费的情况。,资源按级分配法,该方法是把资源递增排序成假设干等级如L1、L2.Lm，其中每级可包含几类资源，要求每个进程在获得了Lj级中资源之后，它才能申请更高级的LKLKLj级中的资源；如果它还需申请比LK级低的LI级LI 4,P2 4 2 2 =4,因为找不到一个平安序列使所有进程顺序地一个个地运行完毕，所以T1状态是不平安状态，由于实施分配给1台磁带机给P3的操作会引起系统状态由平安状态T0向不平安状态下的转换，所以为了防止死锁，上述的分配只是平安检测，检测后判定这样的申请不能满足，P3为申请1台磁带机而必须阻塞等待。,3.利用银行家算法防止死锁,最具代表的防止死锁算法是Dijkstra的银行家算法，这是由于该算法用于银行系统现金贷款的发放而得名。,银行家算法的数据结构,可用资源向量 Available m,m为系统中资源种类数，Availablej=k表示系统中第j类资源数为k个。,最大需求矩阵Maxn，m,n为系统中进程数，Maxi,j=k表示进程i对j类资源的最大需求数为中k。,分配矩阵Allocationn，m,它定义了系统中每一类资源当前已分配给每一进程资源数，Allocationi,j=k表示进程i已分得j类资源的数目为k个。,3.利用银行家算法防止死锁-1,需求矩阵Needn,m,它表示每个进程尚需的各类资源数，Needi,j=k 表示进程i还需要j类资源k个。Needi,j=Maxi,j-Allocationi,j,银行家算法,假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requestij=k。系统按下述步骤进行平安检查：,如果RequestiNeedi那么继续以下检查，否那么显示需求申请超出最大需求值的错误。,如果RequestiAvailable那么继续以下检查，否那么显示系统无足够资源，Pi阻塞等待。,系统试探把要求的资源分配给进程i并修改有关数据结构的值：,Available =Available-Requesti；,Allocationi=Allocationi+Requesti；,Needi=Needi-Requesti ；,3.利用银行家算法防止死锁-2,系统执行平安性算法，检查此次资源分配后，系统是否处于平安状态，假设平安，才正式将资源分配给进程i，以完本钱次分配；否那么将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,平安性算法,平安性算法执行步骤如下：,A.初始化设置工作向量Workm表示系统可提供的各类资源数目，用以保护原数据结构有关值。Work=Available，设置完成标志向量 Finishn。Finishi=false 表示i进程尚末完成，如值为true那么表示进程i已完成。,B.从进程集合n中找到一个能满足下述二个条件:Finishi=false和NecdiWork，如找到那么执行步骤C，如找不到同时满足以上二条件的进程那么执行步骤D。,3.利用银行家算法防止死锁-3,C.当进程i获得资源后可顺利执行直到完成，并释放出分配给它的资源，表示如下：,work=work+Allocationi；Finishi=true；转执行步骤B。,D.如果所有的Finishiture，那么表示系统处于平安状态，否那么系统处于不平安状态。,银行家算法,例：,假定系统中有五个进程P0、P1、P2、P3、P4和三种类型资源A、B、C，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下 所示。,Max Allocation Need Available,A B CA B C A B C A B C,P0 7 5 3 0 1 0 7 4 3 3 3 2,P1 3 2 2 2 0 0 1 2 2,P2 9 0 2 3 0 2 6 0 0,P3 2 2 2 2 1 1 0 1 1,P4 4 3 3 0 0 2 4 3 1,试问：T0时刻是否平安？,P1请求资源Request1(1,0,2)是否允许？,P4请求资源Request4(3,3,0)是否允许？,银行家算法,例-1,T0时刻是否平安？,从表中可找出一个序列(P1、P3、P4、P2、P0使各进程顺序地一个个地执行完成。,Max Allocation Need Available Available,(分配资源前)(释放资源后,A B C A B C A B C A B C A B C,P0 7 5 3 0 1 0 7 4 3 =10 4 7 10 5 7,P1 3 2 2 2 0 0 1 2 2 =3 3 2 5 3 2,P2 9 0 2 3 0 2 6 0 0 =7 4 5 10 4 7,P3 2 2 2 2 1 1 0 1 1 =5 3 2 7 4 3,P4 4 3 3 0 0 2 4 3 1 =7 4 3 7 4 5,平安序列为P1、P3、P4、P2、P0，T0时刻系统是平安的。,P1请求资源Request1(1,0,2)可否允许？,银行家算法,例-2,Request1(1,0,2)Need1(1,2,2)，P1请求在最大需求范围内。,Request1(1,0,2)Available(3,3,2)，可用资源可满足P1请求需要。,试探把要求的资源分配给进程P1并修改有关数据结构的数值：,Available=Available(3，3，2)Request1(1,0,2)=Available(2,3,0)；,Need1=Need1(1,2,2)Request1(1,0,2)=Need1(0,2,0)；,Allocation1=Allocation1(2,0,0)+Request1(1,0,2)=Allocation1(3,0,2)；,利用平安性算法检查试探将资源分配后状态的平安性如下：,银行家算法,例-3,Max Allocation Need Available Available,(分配资源前)(释放资源后,A B C A B C A B C A B C A B C,P0 7 5 3 0 1 0