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

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

數(shù)據(jù)項使用率很低，數(shù)據(jù)項可能很長時間卻用不到；2）對所有的數(shù)據(jù)項強加一個次序，同時要求事務只能按次序規(guī)定的順序封鎖數(shù)據(jù)項。

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

搶占與事務回滾

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