28死锁

2.8死锁问题回顾数据库系统中活锁与死锁活锁：可能无限等待事务T1请求封锁数据对象R后，事务T2也请求封锁R，于是T2等待，接着T3也请求封锁R，T1释放R上的锁，系统首先批准T3的请求，T2继续等待，同理，T4、T5等等后请求，系统先处理，T2有可能永远等下去。死锁：永远无限等待事务T1封锁了数据A，事务T2封锁了数据B。之后T1又申请封锁数据B，因T2已经封锁了B，于是T1等待T2释放B上的锁。接着T2又申请封锁A，因T1已封锁了A，T2也只能等待T1释放A上的锁。这样就出现了T1、T2相互等待的局面，这两个事务永远不能结束。死锁的定义死锁进程：两个或两个以上的进程在执行过程中，因争夺资源而造成的一中相互等待的现象，若无外力作用，他们都将无法推进下去。称此时系统处于死锁状态或系统产生了死锁，这些永远在相互等待的进程称为死锁进程。演示动画：死锁的定义哲学家就餐问题简介：五个哲学家围坐在圆桌旁，他们的生活方式是交替地进行思考和进餐；圆桌上摆放着5把叉子和5个装有通心粉的盘子。规定第i号哲学家固定坐在第i把椅子上(i=0，1，2，3，4)，且每个科学家必须两手分别拿起他旁边的两把叉子，才能吃通心粉；假定通心粉取之不尽死锁的定义哲学家就餐问题的启示：思考：P(S[i])；拿起左边的叉子；P(S[(i+1)mod5]);拿起右边的叉子；吃通心粉；放下左边的叉子；V(S[i]);放下右边的叉子；V(S[(i+1)mod5]);分析：如果五位哲学家因为饥饿同时拿起了左边的叉子，当他们申请拿右手叉子时，均因无叉子可拿而阻塞，且永远阻塞。因此陷入死锁状态死锁的定义解决办法：思考：P(mutex);P(S[i])；拿起左边的叉子；P(S[(i+1)mod5]);拿起右边的叉子；吃通心粉；放下左边的叉子；V(S[i]);放下右边的叉子；V(S[(i+1)mod5]);V(mutex)；分析：限定至多四位哲学家可以同时去拿左边的叉子，这样能保证最终至少有一为哲学家可以拿到左右两边的叉子，进餐结束放下叉子，从而使其他哲学家能够进餐产生死锁的原因(1)竞争临界资源当系统中供多个进程共享的临界资源的数目不能满足诸多进程的需要时，会引起诸多进程对资源的竞争而产生死锁思考：竞争临界资源引发的死锁为什么不能在多道程序系统中解决？多道程序系统是在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制之下，相互穿插的运行。该系统无法改变程序运行所需要的资源，因此还是会出现争夺临界资源的现象。(2)进程推进顺序不当进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁的产生。产生死锁的必要条件1、互斥条件2、占有并请求条件3、不可剥夺条件4、循环等待条件只要这四个条件中的一个条件不成立，就不会发生死锁。死锁的预防死锁的预防是通过破坏产生死锁的必要条件之一，使系统中不发生死锁。1、静态资源分配法——破坏占有并请求条件每一个进程开始前，一次性申请其在整个运行过程中的全部资源。优点：简单安全易实现缺点：资源被严重浪费2、有序资源使用法——破坏循环等待条件资源编号，每个进程只能按编号的升序申请资源。优点：利用率比静态资源分配法有所提高。缺点：难以给出合适的变好，不便于系统增添新设备，不便于拥护编程，且仍有一定的资源浪费现象。死锁的避免1、安全状态某一时刻系统能按某种进程顺序来为每个进程分配其所需的资源，直至最大需求，使每个进程均可顺利完成，则称此时系统的状态为安全状态。这样的序列为安全序列。实质：序列中每个进程到运行完成还需要的资源量不超过系统当前剩余的资源量与所有在序列中排在它前面的进程当前所占有的资源量之和。若在某一时刻，系统中不存在一个安全序列，则称系统处于不安全状态注意:(1)安全状态可能不唯一(2)安全状态是非死锁状态，而不安全状态不一定是死锁状态死锁的避免2、银行家算法实质：设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。即每当进程提出资源请求且系统的资源能够该满足请求时，系统将判断如果满足此次资源请求系统状态是否安全，如果安全则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞。数据结构：available:可用资源向量max：最大需求矩阵need：需求矩阵allocation:分配矩阵request：请求向量死锁的避免算法描述：1)若requestineedi，则进程Pi出错2)若requestiavailable，则进程Pi阻塞3)系统试着把资源分配给进程Pi，并对相印数据结构做如下修改：available-requesti;allocationi+requesti;needi-requesti4)系统执行安全性检测子算法，以判断试分配后系统状态是否安全5)若第四步返回逻辑真值，即“安全”，则完成此次分配，返回6)否则撤销此次步骤三中试分配。进程Pi阻塞死锁的避免安全性检测子算法：1)初始化：work=available;finish=false;2)finish=false且need=work的进程P，则假设该进程不久讲完成任务，于是置work=work+allocation和finish=true,然后重复执行这一步。3)否则，若所有进程的可完成标志finish为真，则返回逻辑真值（表示安全）。4)否则，返回逻辑假值（表示不安全）。P60-62例2.8假定系统中有4个进程P1、P2、P3、P4和3类资源R1、R2、R3（资源数量分别为9、3、6），在t0时刻的资源分配情况如下表资源情况进程maxallocationneedavailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222112P2613511102P3314211103P4422002420T0时刻的安全性检查资源情况进程workneedallocationWork+allocationfinihR1R2R3R1R2R3R1R2R3R1R2R3P2112102511623TrueP1623222100723TrueP3723103211934TrueP4934420002936True为P2试分配资源后的有关资源数据资源情况进程maxallocationneedavailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222011P2613511102P3314211103P4422002420P2申请资源时的安全性检查资源情况进程workneedallocationWork+allocationfinihR1R2R3R1R2R3R1R2R3R1R2R3P2011001612623TrueP1623222100723TrueP3723103211934TrueP4934420002936True为P3试分配资源后的有关资源数据资源情况进程maxallocationneedavailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222010P2613612001P3314212102P4422002420例2.9某系统有同类互斥资源m个，供n个进程共享使用，如果每个进程最多申请x个资源（1=x=m），试证明：当n(x-1)+1=m时，系统不会发生死锁。证明：最坏状况：每个进程已经得到x-1个资源，并且现在需要申请最后一个资源。剩余资源：m-n(x-1)因此只要系统中至少还有一个资源可供使用就可以使这n个进程中某个程序得到其所需要的全部资源，并能够执行完成，归还资源后可供其他进程使用。死锁的检测与解除1、死锁的检测：实际确定系统中是否存在死锁，并试图找出先入死锁的进程和资源。通常采用的检测算法主要是通过对资源分配图的化简来确定资源分配时是否有循环等待时间，是个与银行家算法中的安全检测子算法想死的算法。2、死锁的接触(1)撤销进程法(2)挂起进程法鸵鸟算法：对死锁置之不理，交给管理员处理。