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

《自考操作系统原理 第八章 死锁》由会员分享，可在线阅读，更多相关《自考操作系统原理 第八章 死锁（49页珍藏版）》请在文档大全上搜索。

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估计到可能会