死锁的处理与多粒度

死锁的处理1.死锁的预防2.死锁的检测3.死锁的恢复机制4.多粒度封锁方法死锁：是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。产生条件1）互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。2）请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。3）不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。4）循环等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。死锁的预防方法1.通过对加锁请求进行排序或同时获得所有的锁来保证不会发生循环等待。2.每当等待有可能导致死锁时，进行事务回滚而不是等待加锁。1)要求每个事务在开始之前封锁它的所有数据项

缺点:很难预知哪些数据需要封锁；

数据项使用率很低，数据项可能很长时间却用不到；2）对所有的数据项强加一个次序，同时要求事务只能按次序规定的顺序封锁数据项。

只要一个事务锁住了某个特定的数据项，就不能申请顺序中位于该数据项前面的锁。

抢占与事务回滚

在抢占机制中，若事务Tj所申请的锁已被事务Ti持有，则授予Ti的锁可能通过回滚事务Ti被抢占，被授予Tj。为控制抢占给每一个事务赋予一个唯一的时间戳。系统仅用时间戳来决定事务应当等待还是回滚。1）wait-die机制基于非抢占技术，当事务Ti申请数据项当前被Tj持有，仅当Ti的时间戳小于Tj时间戳时，允许Ti等待，否则回滚。2）wound-die机制基于抢占机制，当事务Ti申请数据项当前被Tj持有，仅当Ti的时间戳大于Tj时间戳时，允许Ti等待，否则回滚。假设事务T1.T2.T3.时间戳分别为5.10.15。如果T1申请的数据项当前被T2持有1）wait-die如果T1申请的数据项当前被T2持有，T1等待，如果T3所申请的数据项被T2持有，则T3回滚。2）wound-wait如果T1申请的数据项当前被T2持有，T1将从T2抢占该数据项，T2回滚。如果T3所申请的数据项被T2占有，则T3等待。死锁的检测死锁的检测算法：是当进程进行资源请求时检查并发进程组是否构成资源的请求和占用环路。如果不存在这一环路，则系统中一定没有死锁。1)无循环状态2)有一个环的状态T1T2T3T4T1T2T4T3死锁的恢复选择牺牲者事务已计算了多久，并在完成其指定任务之前该事务还将回滚多远。该事务已使用了多少数据项。为完成事务还需要多少数据项。回滚时涉及多少事务。回滚彻底回滚：中止该事务，重新开始。特点：彻底回滚设计到系统维护的东西少，执行简单。但是每次回滚都会使事务重新开始，效率低。部分回滚：只回到可以解除死锁的地方。特点：系统需要维护所有正在运行事务的额外信息，需要记录锁的申请/授予序列和食物执行的更新只有这样，系统才能准确的回滚到获得这些锁的第一个之前，并取消它之后的所有动作，然后确保回滚后事务恢复执行饿死：同一事物因为回滚代价小而总是被选为“牺牲者”，就会导致这个事务总是被回滚而无法完成，这样就发生“饿死”。为此代价因素中要包含回滚次数限制，来避免发生这样的事情多粒度两个问题：1，如果事务T需要访问整个数据库，使用的是一种封锁协议，则事务T必须给数据库中的每个数据项加锁，而执行这些加锁操作是费时的。2，如果事务T只需要存取少量数据项，就不应该给整个数据库加锁，否则并发性就丧失了。多粒度机制的思路是：小粒度数据嵌套在大粒度数据项中实现，形成数据粒度的层次结构，即多粒度树。然后只在高层进行加锁操作就可以影响一整个路径，同时在低层加锁操作也能在高层得到体现。粒度层次DBA1Fara1ra2ra3Fbrb1rb2A2Fcrc1rc2整个数据库Area类型File类型Record类型加锁规则举例：若事务Ti给Fb显式地加排他锁，则Fb下面的记录也加了隐式地排他锁。显式排他锁隐式排他锁XXX加锁规则情况1：此时Tj希望封锁Fb的记录rb1，向rb1发出加锁请求。Tj必须从树根到rb1遍历，发现不相容的锁，Tj就要延迟。显式排他锁隐式排他锁XXXTj请求加锁加锁规则情况2：Tk希望封锁整个数据库，但是不会成功，因为目前Ti在树某部分（Fb）持有锁。系统判定方法：搜索整个树，但是这于设计多粒度机制的初衷想违背。引入一种新的锁：意向锁。XXX显式排他锁隐式排他锁IXIX排他型意向锁DBA1Fara1ra2ra3Fbrb1rb2A2Fcrc1rc2三种意向锁共享型意向锁（IS）：较低层只能加共享锁；排他型意向锁（IX）：较低层加共享锁或者排他锁。共享排他型意向锁（SIX）：表明以该结点为根的子树显式加了共享锁，然后在更低层显式加了排他锁。XIXXXSIXIXSIX希望给某个结点（rb1）加锁的事务必须遍历从根到rb1的路径。遍历过程中，该事务给各结点加上意向锁。（如图）X多粒度封锁协议DBA1Fara1ra2ra3Fbrb1rb2A2Fcrc1rc2举例：假设事务T21读文件Fa的记录ra1。那么，T21需给数据库、区域A1，以及Fa加IS锁（按顺序），最后ra1加S锁。假设事务T22要修改文件Fa的记录ra2。那么，T22需给数据库、区域A1，以及Fa加IX锁（按顺序），最后ra2加X锁。假设事务T23要修改文件Fa的所有记录。那么，T23需给数据库和区域A1加IS锁（按顺序），最后给Fa加S锁。假设事务T24要读取整个数据库。它在给数据库加S锁后就可读取。其中T21、T23、T24可以并发存取数据库，事务T22可以与T21并行，但不能与T23或T24并发执行。该协议增强了并发性，减少了开销。sxIS/IXIS/IXIS/IX多粒度封锁协议ISIXSSIXXIStruetruetruetruefalseIXtruetruefalsefalsefalseStruefalsetruefalsefalseSIXtruefalsefalsefalsefalseXfalsefalsefalsefalsefalseDBA1Fara1ra2ra3Fbrb1rb2A2Fcrc1rc2XSIXXXSIX/ISIXISX1，事务Ti必须遵从图所示的锁类型相容函数2，事务Ti必须首先封锁树的根结点，并且可以加任意类型的锁3，仅当Ti当前对Q(Fb)的父结点具有IX或IS锁时，Ti对结点Q可加S或IS锁。4，仅当Ti当前对Q的父结点具有IX或SIX锁时，T