死鎖的處理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