自考操作系统原理 第八章 死锁

1、死锁死锁死锁死锁 多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，这些进程将永远不能向前推进。死锁形成的原因死锁形成的原因R1R2进程进程A进程进程B请求请求R2请求请求R1进程进程B占用占用R2进程进程A占用占用R1n系统有三种独占型资源R1、R2、R3，有三个进程A、B、C并发执行，进程A需使用资源R3和R1，进程B需使用资源R1和R2，进程C需使用资源R2和R1。问在什么情况下会发生死锁，并说明原因。R1R2R3进程进程A进程进程B进程进程C死锁死锁n若系统中存在一组进程（两个或多个），它们中每个进程占用了某种资源，又再等待已被该组进程中的其他进程占用的资源，如果这种进程等

2、待永远不能结束，则说系统出现了死锁，或者说这组进程处于死锁状态。例例1：资源分配不当造成的死锁：资源分配不当造成的死锁n系统有某类资源5个，被5个进程共享，每个进程要求2个资源。nP1请求1个资源，分配nP2请求1个资源，分配nP3请求1个资源，分配nP4请求1个资源，分配nP5请求1个资源，能否分配？例例2:并发进程执行的速度引起死锁并发进程执行的速度引起死锁n哲学家吃面条问题 五个哲学家P1，P2，P3，P4，P5，每两个哲学家之间放一根筷子，每个哲学家必须拿到左右手的两个筷子才能取到面条。哲学家吃面条哲学家吃面条S1，S2，S3，S4，S5:semaphore;S1:=1;S2:=1;S

3、3:=1;S4:=1;S5:=1；process P1 begin P(S1); 取f1; P(S2); 取f2; 吃面条； 放下f1,f2 V(S1); V(S2);end;process P2 begin P(S2); 取f2; P(S3); 取f3; 吃面条； 放下f2,f3 V(S2); V(S3);end;process P3 begin P(S3); 取f3; P(S4); 取f4; 吃面条； 放下f3,f4 V(S3); V(S4);end;process P4 begin P(S4); 取f4; P(S5); 取f5; 吃面条； 放下f4,f5 V(S4); V(S5);end

4、;process P5 begin P(S5); 取f5; P(S1); 取f1; 吃面条； 放下f5,f1 V(S5); V(S1);end;不属于死锁范围的情况不属于死锁范围的情况1、进程申请了系统中不存在的资源，或者申请的资源数超过了系统拥有的最大资源数而造成的等待。2、硬件故障引起的循环等待不属于死锁范围的情况不属于死锁范围的情况为了讨论在操作系统设计中可能出现的死锁问题，假定：1、任何一个进程要求资源的最大数量不超过系统能提供的最大资源量2、若任何一个进程在执行中所申请的资源能全部得到满足，那么它一定能在有限的时间内执行完毕，并归还他所占用的资源3、一个进程只有在它所申请的资源得不到

5、满足时，才处于等待资源状态死锁的必要条件死锁的必要条件n互斥的使用资源n占有且等待资源n不可抢夺资源n循环等待资源n只要发生死锁，则这四个条件一定同时成立，四个条件同时成立不一定有死锁。如果其中的一个或几个条件不成立，一定没有死锁。资源分配图资源分配图n假设某个系统有三类资源R1，R2，R3，其中R1和R3都有1个资源，R2有2个资源，系统中有三个进程P1，P2，P3，这些进程占用资源和等待的情况如表所示：进程已占用的资源类已占用的数量等待的资源类P1R21R1P2R1，R21 , 1R3P3R31P1R1R2P2P3R3有环路无死锁有环路无死锁P1R1R2P2P3P4R1有两个资源，R2有两

6、个资源1、资源分配图中无环路，一定没有死锁2、如果资源分配图中有环路，且每个资源类只有一个资源，则环路存在着意味着死锁的形成，环路中的进程处于死锁状态3、如果资源分配图总有环路，但涉及的资源类有多个资源，则环路的存在未必形成死锁。死锁的防止死锁的防止n只要破坏四个必要条件之一，就可以防止死锁破坏破坏“互斥互斥”条件条件n方法是允许进程共享资源。但是在计算机系统中，由于资源本身的固有特性，使得大部分资源都必须互斥使用。n破坏这个条件通常行不通。破坏破坏“占有并等待占有并等待”条件条件n静态分配资源q开始执行前申请自己所要的全部资源，执行过程中不再申请(同时还能破坏循环等待条件)q缺点：降低了资源

7、利用率n释放已占资源q先释放已占用的资源，再申请资源破坏破坏“不可抢夺不可抢夺”条件条件n一个进程占有了某些资源后又要申请资源R，而R已经被另一进程P占用，系统可以抢夺P占用的R。qA申请的R尚未占用，可以把R分配给AqA申请的R已被B占用，如果B出于等待另一资源的状态，那么抢夺资源R分配给A，否则让A等待。q一个等待资源的进程只有得到自己申请的资源和所有被抢走的老资源，才能继续执行。q适用于CPU,主存，对打印机、磁带机不适合破坏破坏“循环等待循环等待”条件条件n对资源进程编号，进程申请两个及以上资源时，总是先申请编号小的资源，再申请编号大的资源。破坏破坏“循环等待循环等待”条件条件n假设，

8、某系统有m个资源Rk1，Rk2，Rk3.Rkn, 编号是k1,k2.kn,且k1k2k3.kn，任何一个进程在得到了Ri之后再申请Rj (ij)，证明：按此策略分配资源，一定不会产生循环等待的情况。例例2:哲学家吃面条哲学家吃面条S1，S2，S3，S4，S5:semaphore;S1:=1;S2:=1;S3:=1;S4:=1;S5:=1；process P1 begin P(S1); 取f1; P(S2); 取f2; 吃面条； 放下f1,f2 V(S1); V(S2);end;process P2 begin P(S2); 取f2; P(S3); 取f3; 吃面条； 放下f2,f3 V(S2)

9、; V(S3);end;process P3 begin P(S3); 取f3; P(S4); 取f4; 吃面条； 放下f3,f4 V(S3); V(S4);end;process P4 begin P(S4); 取f4; P(S5); 取f5; 吃面条； 放下f4,f5 V(S4); V(S5);end;process P5 begin P(S1); 取f1; P(S5); 取f5; 吃面条； 放下f1,f5 V(S1); V(S5);end;P247 3n某系统有输入机和打印机各一台，今有两个进程要同时使用它们。请写出采用PV操作实现请求使用和归还的程序。死锁的避免死锁的避免n估计到可能会

10、发生死锁的时候，设法避免死锁的发生。n资源分配时测试系统的状态，仅当能确保不会发生死锁时，才把资源分配给申请者，否则拒绝。安全状态安全状态n如果操作系统能保证所有的进程在有限的时间内得到需要的全部资源，则系统处于安全状态。安全状态的判断安全状态的判断n12个同类资源供3个进程共享进程已占资源数 最大需求数P129P2510P324不安全状态不安全状态n例如：12个同类资源供3个进程共享进程已占资源数最大需求数P139P2510P324不安全状态隐含着将会发生死锁nP247 4nP247 5nP285 2P247 4进程已占资源数最大需求数P124P236P347P41412个同类资源供4个进程

11、共享，分配表如下，目前系统是否处于安全状态？P247 5进程资源情况已分配A B C D最大需求A B C D尚需资源A B C DP10 0 1 2 0 0 1 20 0 0 0P21 0 0 01 7 5 00 7 5 0P31 3 5 42 3 5 61 0 0 2P40 6 3 20 6 5 20 0 2 0P50 0 1 40 6 5 60 6 4 2系统剩余(1,5,2,0)分配给P4，系统剩余(1, 11, 5, 2)分配给P3，系统剩余(2, 14, 10, 6)分配给P2，系统剩余(3, 14, 10, 6)分配给P5，系统剩余(3, 14, 11, 10)P285 2n有三

12、个进程A、B、C，它们对某类资源的需求分别是7个，8个，3个，且目前已经分别得到了3个，3个，和2个。为了保证系统安全，系统还至少应提供多少个资源？安全状态安全状态n系统在分配资源时，只要保证系统处于安全状态，就可避免死锁的发生。n有进程要求分配资源时，系统应该分析系统的资源情况，如果分配后仍然处于安全状态，就可以分配，否则暂不分配。银行家算法银行家算法银行家算法（Dijkstra, 1965）问题：一个银行家把他的固定资金代给若干顾客。只要不发生现有的资金不能满足任何一个顾客的需求的情况，银行家的资金应安全的。银行家需一个算法保证借出去的资金在有限时间内可收回。 银行家算法银行家算法n系统当

13、前剩余资源量为n，进程首次申请资源，如果该进程资源的最大需求量为max，本次申请量为xmaxnyes分配x个no不分配例例n假定系统有三类资源A,B,C和5个进程，三类资源A,B,C的数量分别为10，5，7，P1-P5的第一次申请能否满足？进程Max A B C第一次申请 A B CP17 5 30 1 0 P23 2 22 0 0P39 0 23 0 2P42 2 22 1 1P54 3 30 0 2满足P1申请，结束后系统剩余(10,4,7)满足P2申请，结束后系统剩余(8,4,7)不能满足P3的最大需求，P3等待满足P4申请，结束后系统剩余(6,3,6)满足P5申请，结束后系统剩余(6,

14、3,4)银行家算法银行家算法n如果非首次分配，系统当前剩余资源量为n，如果该进程尚需资源量为need，本次申请量为xxneedno不分配yesyes分配给进程x个no不分配needn例例假定系统有四类资源A,B,C,D和5个进程，四类资源的数量分别为(3,14,12,12)，P2请求(0,4,2,0)能否满足？进程已分配A B C D最大需求A B C D 尚需A B C DP10 0 1 2 0 0 1 20 0 0 0P21 0 0 01 7 5 00 7 5 0P31 3 5 42 3 5 61 0 0 2P40 6 3 20 6 5 20 0 2 0P50 0 1 40 6 5 60

15、6 4 2系统剩余资源(1,5,2,0)因为(0,4,2,0)(0,7,5,0)，所以此次申请的资源量小于P2尚需的资源量。因为(1,5,2,0)不能满足(0,7,5,0)，不能满足P2要求P248 ,8n某系统有同类资源10个，P1，P2，P3所需资源总数分别是8, 4, 9，它们向系统申请资源的次数和数量如表所示：n写出第6次分配后各进程的状态和占用的资源量n在以后各次申请中，哪次的申请要求可以先得到满足？次序 进程 申请量1P322P143P224P125P316P227P338P129P33n假设，某系统有同类资源m个，可并发且共享该类资源的进程最多n个，而每个进程申请该类资源的最大量

16、为x(1x m)，只要下面不等式成立，则该系统一定不会发生死锁。 n （x -1） + 1 mn某系统中仅有3个并发进程竞争某类资源，并都需要该类资源4个，如要使这个系统不发生死锁，那么该类资源至少有几个？n在哲学家就餐问题中，若仅提供5把叉子，则同时要求就餐的人数最多不超过_个（最大数）时，一定不会发生死锁。死锁的检测死锁的检测n如果系统对资源的分配不加限制，则可定时运行一个检测死锁的程序，该程序按一定算法去检测系统中是否存在死锁。死锁的检测方法死锁的检测方法n每类资源中只有一个资源资源占用进程R1P1R2P3R3P2R4P2R5P1进程等待资源P1R3P2R2P3R5(a) 占用表(b)

17、等待表P1P2P3P1010P2001P3100Pi等待等待Pj的资源，的资源，Bij置为置为1否则否则Bij置为置为0死锁的检测方法死锁的检测方法P1P2P3P1010P2001P3100for k := 1 to n do for i := 1 to n do for j := 1 to n do Bij := Bij (Bik B kj) 死锁的检测方法死锁的检测方法n资源类中含有若干个资源n第一步：找出所有资源已满足进程，将其所占资源和系统剩余资源加在一起作为可分配资源，为这些进程置标志位进程Allocation A B CNeed A B CflagP10 1 0 0 0 0finishP22 0 02 2 2P33 0 30 0 0finishP42 1 11 0 0P50 0 20 0 2系统初始资源：7,2,6按照表格，剩余：0,0,0P1，P3已满足归还后，系统资源：3,1,3死锁的检测死锁的检测进程Allocation A B CNeed A B CflagP10 1 0 0 0 0finishP22 0 02 2 2P33 0 30 0 0finishP42 1 11 0 0finishP50 0 20 0 2n第二步：找出尚需资源不超过系统可分配资源的进程，将其所占资源和系统剩余资源加在一起作为可分配资源，为这些进程置标志位系统可用资：3,1,3能够满足P