死鎖的處理與多粒度

死鎖的處理1.死鎖的預(yù)防2.死鎖的檢測(cè)3.死鎖的恢復(fù)機(jī)制4.多粒度封鎖方法死鎖：是指兩個(gè)或兩個(gè)以上的進(jìn)程在執(zhí)行過程中，由于競(jìng)爭(zhēng)資源或者由于彼此通信而造成的一種阻塞的現(xiàn)象，若無(wú)外力作用，它們都將無(wú)法推進(jìn)下去。產(chǎn)生條件1）互斥條件：指進(jìn)程對(duì)所分配到的資源進(jìn)行排它性使用，即在一段時(shí)間內(nèi)某資源只由一個(gè)進(jìn)程占用。如果此時(shí)還有其它進(jìn)程請(qǐng)求資源，則請(qǐng)求者只能等待，直至占有資源的進(jìn)程用畢釋放。2）請(qǐng)求和保持條件：指進(jìn)程已經(jīng)保持至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源已被其它進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但又對(duì)自己已獲得的其它資源保持不放。3）不剝奪條件：指進(jìn)程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時(shí)由自己釋放。4）循環(huán)等待條件：指在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程——資源的環(huán)形鏈，即進(jìn)程集合{P0，P1，P2，···，Pn}中的P0正在等待一個(gè)P1占用的資源；P1正在等待P2占用的資源，……，Pn正在等待已被P0占用的資源。死鎖的預(yù)防方法1.通過對(duì)加鎖請(qǐng)求進(jìn)行排序或同時(shí)獲得所有的鎖來(lái)保證不會(huì)發(fā)生循環(huán)等待。2.每當(dāng)?shù)却锌赡軐?dǎo)致死鎖時(shí)，進(jìn)行事務(wù)回滾而不是等待加鎖。1)要求每個(gè)事務(wù)在開始之前封鎖它的所有數(shù)據(jù)項(xiàng)

缺點(diǎn):很難預(yù)知哪些數(shù)據(jù)需要封鎖；

數(shù)據(jù)項(xiàng)使用率很低，數(shù)據(jù)項(xiàng)可能很長(zhǎng)時(shí)間卻用不到；2）對(duì)所有的數(shù)據(jù)項(xiàng)強(qiáng)加一個(gè)次序，同時(shí)要求事務(wù)只能按次序規(guī)定的順序封鎖數(shù)據(jù)項(xiàng)。

只要一個(gè)事務(wù)鎖住了某個(gè)特定的數(shù)據(jù)項(xiàng)，就不能申請(qǐng)順序中位于該數(shù)據(jù)項(xiàng)前面的鎖。

搶占與事務(wù)回滾

在搶占機(jī)制中，若事務(wù)Tj所申請(qǐng)的鎖已被事務(wù)Ti持有，則授予Ti的鎖可能通過回滾事務(wù)Ti被搶占，被授予Tj。為控制搶占給每一個(gè)事務(wù)賦予一個(gè)唯一的時(shí)間戳。系統(tǒng)僅用時(shí)間戳來(lái)決定事務(wù)應(yīng)當(dāng)?shù)却€是回滾。1）wait-die機(jī)制基于非搶占技術(shù)，當(dāng)事務(wù)Ti申請(qǐng)數(shù)據(jù)項(xiàng)當(dāng)前被Tj持有，僅當(dāng)Ti的時(shí)間戳小于Tj時(shí)間戳?xí)r，允許Ti等待，否則回滾。2）wound-die機(jī)制基于搶占機(jī)制，當(dāng)事務(wù)Ti申請(qǐng)數(shù)據(jù)項(xiàng)當(dāng)前被Tj持有，僅當(dāng)Ti的時(shí)間戳大于Tj時(shí)間戳?xí)r，允許Ti等待，否則回滾。假設(shè)事務(wù)T1.T2.T3.時(shí)間戳分別為5.10.15。如果T1申請(qǐng)的數(shù)據(jù)項(xiàng)當(dāng)前被T2持有1）wait-die如果T1申請(qǐng)的數(shù)據(jù)項(xiàng)當(dāng)前被T2持有，T1等待，如果T3所申請(qǐng)的數(shù)據(jù)項(xiàng)被T2持有，則T3回滾。2）wound-wait如果T1申請(qǐng)的數(shù)據(jù)項(xiàng)當(dāng)前被T2持有，T1將從T2搶占該數(shù)據(jù)項(xiàng)，T2回滾。如果T3所申請(qǐng)的數(shù)據(jù)項(xiàng)被T2占有，則T3等待。死鎖的檢測(cè)死鎖的檢測(cè)算法：是當(dāng)進(jìn)程進(jìn)行資源請(qǐng)求時(shí)檢查并發(fā)進(jìn)程組是否構(gòu)成資源的請(qǐng)求和占用環(huán)路。如果不存在這一環(huán)路，則系統(tǒng)中一定沒有死鎖。1)無(wú)循環(huán)狀態(tài)2)有一個(gè)環(huán)的狀態(tài)T1T2T3T4T1T2T4T3死鎖的恢復(fù)選擇犧牲者事務(wù)已計(jì)算了多久，并在完成其指定任務(wù)之前該事務(wù)還將回滾多遠(yuǎn)。該事務(wù)已使用了多少數(shù)據(jù)項(xiàng)。為完成事務(wù)還需要多少數(shù)據(jù)項(xiàng)?；貪L時(shí)涉及多少事務(wù)?；貪L徹底回滾：中止該事務(wù)，重新開始。特點(diǎn)：徹底回滾設(shè)計(jì)到系統(tǒng)維護(hù)的東西少，執(zhí)行簡(jiǎn)單。但是每次回滾都會(huì)使事務(wù)重新開始，效率低。部分回滾：只回到可以解除死鎖的地方。特點(diǎn)：系統(tǒng)需要維護(hù)所有正在運(yùn)行事務(wù)的額外信息，需要記錄鎖的申請(qǐng)/授予序列和食物執(zhí)行的更新只有這樣，系統(tǒng)才能準(zhǔn)確的回滾到獲得這些鎖的第一個(gè)之前，并取消它之后的所有動(dòng)作，然后確保回滾后事務(wù)恢復(fù)執(zhí)行餓死：同一事物因?yàn)榛貪L代價(jià)小而總是被選為“犧牲者”，就會(huì)導(dǎo)致這個(gè)事務(wù)總是被回滾而無(wú)法完成，這樣就發(fā)生“餓死”。為此代價(jià)因素中要包含回滾次數(shù)限制，來(lái)避免發(fā)生這樣的事情多粒度兩個(gè)問題：1，如果事務(wù)T需要訪問整個(gè)數(shù)據(jù)庫(kù)，使用的是一種封鎖協(xié)議，則事務(wù)T必須給數(shù)據(jù)庫(kù)中的每個(gè)數(shù)據(jù)項(xiàng)加鎖，而執(zhí)行這些加鎖操作是費(fèi)時(shí)的。2，如果事務(wù)T只需要存取少量數(shù)據(jù)項(xiàng)，就不應(yīng)該給整個(gè)數(shù)據(jù)庫(kù)加鎖，否則并發(fā)性就喪失了。多粒度機(jī)制的思路是：小粒度數(shù)據(jù)嵌套在大粒度數(shù)據(jù)項(xiàng)中實(shí)現(xiàn)，形成數(shù)據(jù)粒度的層次結(jié)構(gòu)，即多粒度樹。然后只在高層進(jìn)行加鎖操作就可以影響一整個(gè)路徑，同時(shí)在低層加鎖操作也能在高層得到體現(xiàn)。粒度層次DBA1Fara1ra2ra3Fbrb1rb2A2Fcrc1rc2整個(gè)數(shù)據(jù)庫(kù)Area類型File類型Record類型加鎖規(guī)則舉例：若事務(wù)Ti給Fb顯式地加排他鎖，則Fb下面的記錄也加了隱式地排他鎖。顯式排他鎖隱式排他鎖XXX加鎖規(guī)則情況1：此時(shí)Tj希望封鎖Fb的記錄rb1，向rb1發(fā)出加鎖請(qǐng)求。Tj必須從樹根到rb1遍歷，發(fā)現(xiàn)不相容的鎖，Tj就要延遲。顯式排他鎖隱式排他鎖XXXTj請(qǐng)求加鎖加鎖規(guī)則情況2：Tk希望封鎖整個(gè)數(shù)據(jù)庫(kù)，但是不會(huì)成功，因?yàn)槟壳癟i在樹某部分（Fb）持有鎖。系統(tǒng)判定方法：搜索整個(gè)樹，但是這于設(shè)計(jì)多粒度機(jī)制的初衷想違背。引入一種新的鎖：意向鎖。XXX顯式排他鎖隱式排他鎖IXIX排他型意向鎖DBA1Fara1ra2ra3Fbrb1rb2A2Fcrc1rc2三種意向鎖共享型意向鎖（IS）：較低層只能加共享鎖；排他型意向鎖（IX）：較低層加共享鎖或者排他鎖。共享排他型意向鎖（SIX）：表明以該結(jié)點(diǎn)為根的子樹顯式加了共享鎖，然后在更低層顯式加了排他鎖。XIXXXSIXIXSIX希望給某個(gè)結(jié)點(diǎn)（rb1）加鎖的事務(wù)必須遍歷從根到rb1的路徑。遍歷過程中，該事務(wù)給各結(jié)點(diǎn)加上意向鎖。（如圖）X多粒度封鎖協(xié)議DBA1Fara1ra2ra3Fbrb1rb2A2Fcrc1rc2舉例：假設(shè)事務(wù)T21讀文件Fa的記錄ra1。那么，T21需給數(shù)據(jù)庫(kù)、區(qū)域A1，以及Fa加IS鎖（按順序），最后ra1加S鎖。假設(shè)事務(wù)T22要修改文件Fa的記錄ra2。那么，T22需給數(shù)據(jù)庫(kù)、區(qū)域A1，以及Fa加IX鎖（按順序），最后ra2加X鎖。假設(shè)事務(wù)T23要修改文件Fa的所有記錄。那么，T23需給數(shù)據(jù)庫(kù)和區(qū)域A1加IS鎖（按順序），最后給Fa加S鎖。假設(shè)事務(wù)T24要讀取整個(gè)數(shù)據(jù)庫(kù)。它在給數(shù)據(jù)庫(kù)加S鎖后就可讀取。其中T21、T23、T24可以并發(fā)存取數(shù)據(jù)庫(kù)，事務(wù)T22可以與T21并行，但不能與T23或T24并發(fā)執(zhí)行。該協(xié)議增強(qiáng)了并發(fā)性，減少了開銷。sxIS/IXIS/IXIS/IX多粒度封鎖協(xié)議ISIXSSIXXIStruetruetruetruefalseIXtruetruefalsefalsefalseStruefalsetruefalsefalseSIXtruefalsefalsefalsefalseXfalsefalsefalsefalsefalseDBA1Fara1ra2ra3Fbrb1rb2A2Fcrc1rc2XSIXXXSIX/ISIXISX1，事務(wù)Ti必須遵從圖所示的鎖類型相容函數(shù)2，事務(wù)Ti必須首先封鎖樹的根結(jié)點(diǎn)，并且可以加任意類型的鎖3，僅當(dāng)Ti當(dāng)前對(duì)Q(Fb)的父結(jié)點(diǎn)具有IX或IS鎖時(shí)，Ti對(duì)結(jié)點(diǎn)Q可加S或IS鎖。4，僅當(dāng)Ti當(dāng)前對(duì)Q的父結(jié)點(diǎn)具有IX或SIX鎖時(shí)，T