搜索
习题课——关于死锁与饥饿死锁与饥饿死锁:indefinitewait.可察觉饥饿:notnecessarilyinwaitstate.?死锁和饥饿都是由于进程竞争资源而引起的.多道环境中，并发改善系统的资源的利用率。但可能存在一种危险＿＿死锁。一、什么是死锁例子：r1和r2为可再用资源;P1:applyforr1;...applyforr2;...returnr1;...returnr2;P2:applyforr2;...applyforr1;...returnr1;...returnr2;12死锁定义一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。资源竞争可能导致死锁，但不一定就会死锁，死锁的出现主要取决于进程推进速度以及对资源的申请顺序。因此产生死锁的因素不仅与系统拥有的资源数量有关，而且与资源的分配策略（剥夺式还是非剥夺式）、进程对资源的使用顺序以及并发进程推进的速度有关。二、死锁预防对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。优点：简单，系统不需要做什么。缺点：对进程的约束，违反约束仍可能死锁。预防方法：预先分配法：进程运行前申请所需全部资源。有序分配法：例子DBACW:直行E：左转S：左转死锁的可能性：情形1，情形2资源编号：F(D)=1;F(B)=2;F(A)=3;F(C)=4;VarS1,S2,S3,S4:semaphore;(1,1,1,1)ProcedureS:P(S1);驶入D；P(S2);驶入B;V(S1);P(S3);驶入A；V(S2);驶出A;V(S3)ProcedureE:P(S2);驶入B；P(S3);驶入A;V(S2);P(S4);驶入C；V(S3);驶出C;V(S4);ProcedureW:P(S1);P(S4);驶入C;驶入D；V(S4);驶出D；V(S1);COBEGINS1:S;…;Sm:S;E1:E;…;En:E;W1:W;...;Wo:WCOEND;三、死锁避免检测可满足请求分配不分配安全不安全系统处于安全状态：存在安全进程序列p1,p2,…,pn进程序列p1,p2,…,pn安全，p1,p2,…,pn可依次进行完。安全不安全死锁银行家算法(Cont.)当有进程有资源申请请求时：1.先判断系统是否安全：寻找安全序列；2.判断申请是否是合法请求：request与need比较；3.判断系统是否能满足申请：request与available比较；4.若不能满足，让进程等待；5.若能满足，则响应申请，进行分配，修availabe和need及allocation量后，判断是否安全：安全则承认分配不安全则让进程等待，恢复数据。R={A(10),B(5),C(7)}，P={p0,p1,p2,p3,p4}ClaimAllocationNeedAvailableWorkFinishABCABCABCABCABC753010743332322200122902302600222211011433002431P0:p1:p2:p3:p4:是否安全？p1请求：Request[1]=(1,0,2)p4请求：Request[4]=(3,3,0),p0请求：Request[0]=(0,2,0),安全，进程序列：p1,p3,p4,p2,p0安全，进程序列：p1,p3,p4,p0,p2不能满足，等待；不安全，等待。不安全状态是否必然导致系统进入死锁状态？不安全状态不一定导致系统进入死锁状态。因为，安全性检查中的向量Max是进程执行前提供的，而在实际运行过程中，一进程需要的总资源量可能小于Max，如某进程对应的程序中有一段进行错误处理的代码，其中需要n个Ａ种资源，若该进程在运行过程中没有碰到应错误而不需要调用错误处理代码，则它实际不会请求这n个Ａ种资源。讨论Remarks1:银行家算法要求条件：进程所需资源最大量,这个信息对于充要性分析是不够的。Remarks2:预先给出进程有关资源的命令序列,则可以给出死锁避免的充要性算法，但事先给出命令序列是困难的(程序的分枝和循环）。Remarks3:银行家算法与预防策略相比,提高了系统的资源利用率,但增加了系统的开销。四、死锁的检测数据结构：Available:array[1..m]ofinteger;Allocation:array[1..n,1..m]ofinteger;Request:array[1..n,1..m]ofinteger;临时变量：Work:array[1..m]ofinteger;Finish:array[1..n]ofboolean;考虑因素：死锁发生频度；死锁影响进程。1.等待时检测：发现早，恢复代价小，开销大（overhead)。2.定时检测：3.资源（eg.CPU）利用率下降时检测。例1.P={p1,p2,p3},R={r1(1),r2(2),r3(1),r4(3)}E={(p1,r1),(p2,r3),(r1,p2),(r2,p1),(r2,p2),(r3,p3)}p1p2p3r1r3r2r4五、死锁检测时刻无p1p2p3r1r3r2r4增加边（p3,r2)有六、死锁的恢复1.重新启动简单，代价大，涉及未参与死锁的进程。2.终止进程(processtermination)环路上占有资源的进程。(1)一次性全部终止；(2)逐步终止（优先级，代价函数）3.剥夺资源(resourcepreemption)（1）逐步剥夺（2）一次剥夺4.进程回退(rollback)问题:(1)保存snapshot代价大；(2)消除影响困难;七、死锁的实现--鸵鸟算法视而不见Pro:工程师观点(考虑死锁发生的频率,危害,处理代价)死锁发生频率其它故障引起的系统瘫痪的频率死锁处理constantoverhead危害Cont:数学家观点必须处理,无论代价如何目前系统实际如此Eg.UNIXWindows八、饥饿与饿死饥饿：没有时间上界的等待排队等待忙式等待饿死：等待时间超过极限(deadline)饿死vs死锁死锁进程处于等待状态，饿死不然死锁可以检测（有循环等待），饿死不然死锁一定涉及多个进程，但饿死可能只有一个。死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，其等待时限没有上界。九、死锁例子——哲学家进餐有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替在进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。1.利用信号量实现同步经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：Varchopstick:array[0，…，4]ofsemaphore；Varchopstick:array[0,…,4]ofsemaphore:=(1,1,1,1,1);repeatthink;wait(chopstick[i]);wait(chopstick(i+1)mod5]);：eat;：signal(chopstick[i]);signal(chopstick(i+1)mod5]);：think;untilfalse;Swait(chopstick(i+1)mod5],chopstick[i]);Ssingal(chopstick(i+1)mod5],chopstick[i]);假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0，出现死锁。死锁产生的必要条件之一循环等待不可能成立。如果存在所有左边的哲学家等待右边的哲学家放下筷子的循环等待链，则右撇子不存在。同样也不可能存在相反的循环等待链。系统中也不可能存在５个以下哲学家的循环等待链，因为不相邻的哲学家之间不竞争资源。因此，不保能产生死锁。在哲学家就餐问题中，如果将先拿起左边的筷子的哲学家称为左撇子，而将先拿起右边筷子的哲学家称为右撇子，请说明在同时存在左撇子和右撇子的情况下，任何就座安排都不会产生死锁。2.利用管程解决ForksControl:monitortypeT=array[0,……,4]ofinteger;B=array[0,……,4]ofboolean;varforks,Right,left:T;ready:B;procedureentryPickup(varme:integer);beginiffork(me)2thenready(me).wait;forks(right(me)):=forks(right(me))-1;forks(left(me)):=forks(left(me))-1;endprocedureentryPutdown(varme:integer);beginforks(right(me)):=forks(right(me))+1;forks(left(me)):=forks(left(me))+1;iffork(right(me))=2thenready(right(me)).signal;iffork(left(me))=2thenready(left(me)).signal;endbeginfori=0to4dobeginfork(i):=2;right(i)=[i+1]mod5;left(i)=[i+1]mod5;ready(i):=true;endFork.T..T..T..T..T.0123401234412340012322222RightleftReadypickup(0)11pickup(4).F.pickup(4)putdown(0)22.T.pickup(4)parbeginPhilosopher0:Process(varhung:boolean);beginrepeatifhung=truethenbeginforksControl.Pickup(0);eat;forksControl.Putdown(0);endthink;forever;endPhilosopher1:Process;……；：：Philosopher４:Process;……；parend3.利用信号量，提高并发性#defineN5Typedefenumstatus{thinking,hungry,eating};Statusstate[n];Semaphoreself[n];Semaphoremutex=1;Voidphilosopher(inti){while(1){think();pick_fork(i);eat();put_fork(i);}}Voidpick_fork(inti){p(&mutex);state[i]=hungry;test(i);V(&mutex);P(&self[i]);}Voidput_fork(inti){p(&mutex);state[i]=thinking;test((i-1)%5);test((i+1)%5);V(&mutex);}Voidtest(inti){if((state[i]==hungry&&(statue[(i-1)%5]!=eating)&&(state[(i+1)%5)!=eating)){state[i]=eating;V(&self[i]);}Voidmain{inti;for(i=0;i5;i++)state[i]=thinking;self[i].value=0;phillsopher(i);}mutex.value=1;}十、饥饿的例子---过河问题过河问题（1）：水流12n-1n…WestEastW-EE-WDeadlockprevention:onedirectionatanytime.Varwest_crossing,e