第八章

并發(fā)控制技術(shù)單用戶和多用戶系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)一般可以分為單用戶系統(tǒng)和多用戶系統(tǒng)。單用戶系統(tǒng)在任何時(shí)刻只允許一個(gè)用戶使用的數(shù)據(jù)庫(kù)系統(tǒng)。多用戶系統(tǒng)允許多個(gè)用戶同時(shí)使用數(shù)據(jù)庫(kù)的系統(tǒng)。事務(wù)的并發(fā)執(zhí)行并行Vs串行基本比較并行事務(wù)會(huì)破壞數(shù)據(jù)庫(kù)的一致性。串行事務(wù)效率低。并行的優(yōu)點(diǎn)一個(gè)事務(wù)由不同的步驟組成，所涉及的系統(tǒng)資源也不同。這些步驟可以并發(fā)執(zhí)行，以提高系統(tǒng)的吞吐量。系統(tǒng)中存在著周期不等的各種事務(wù)，串行會(huì)導(dǎo)致難于預(yù)測(cè)的時(shí)延。如果各個(gè)事務(wù)所涉及的是數(shù)據(jù)庫(kù)的不同部分，采用并發(fā)會(huì)減少平均響應(yīng)時(shí)間。并發(fā)控制的必要性不可重復(fù)讀(Non-RepeatableRead)指事務(wù)T1讀取數(shù)據(jù)后，事務(wù)T2執(zhí)行更新操作，使T1無(wú)法再現(xiàn)前一次讀取的結(jié)果。具體的講，不可重復(fù)讀包括三種情況：事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對(duì)其作了修改，當(dāng)事務(wù)T1再次讀取該數(shù)據(jù)時(shí)，得到與前一次不同的值。事務(wù)T1按照一定條件從數(shù)據(jù)庫(kù)中讀取了某些數(shù)據(jù)記錄后，事務(wù)T2刪除了其中部分記錄，當(dāng)T1再次按照相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)某些記錄神秘的消失了。事務(wù)T1按照一定條件從數(shù)據(jù)庫(kù)中讀取了某些數(shù)據(jù)記錄后，事務(wù)T2插入了一些記錄，當(dāng)T1再次按照相同條件讀取數(shù)據(jù)時(shí)，發(fā)現(xiàn)多了一些記錄。后兩種不可重復(fù)讀有時(shí)也稱作幻影（PhantomRow）現(xiàn)象。并發(fā)控制的必要性T1T2讀A=50讀B＝100求和=150讀B＝100B=B*2寫回B＝200讀A＝50讀B＝200求和＝250并發(fā)控制的必要性T1T2select*fromSCwhereCNO=‘C01’andSNO=‘S01’DeleteFromSCWhereCNO=‘C01’andSNO=‘S01’select*fromSCwhereCNO=‘C01’andSNO=‘S01’并發(fā)控制的必要性T1T2select*fromSCwhereCNO=‘C01’andSNO=‘S01’insertintoSCvalues(S01,C01,null)select*fromSCwhereCNO=‘C01’andSNO=‘S01’并發(fā)控制封鎖的定義封鎖就是事務(wù)T在對(duì)某個(gè)數(shù)據(jù)對(duì)象如表、記錄等操作之前，先向系統(tǒng)發(fā)出請(qǐng)求，對(duì)其加鎖，從而對(duì)該數(shù)據(jù)對(duì)象有了一定的控制，在事務(wù)T釋放它的鎖之前，其他事務(wù)不能更新此數(shù)據(jù)對(duì)象。封鎖是并發(fā)控制的一個(gè)非常重要的技術(shù)。并發(fā)控制封鎖的類型排它鎖（X鎖，eXclusivelock）：事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上X鎖，則只允許T讀取和修改A，其它事務(wù)對(duì)A的任何封鎖請(qǐng)求都不能成功（因而不能讀取和修改R），直至T釋放A上的X鎖。共享鎖（S鎖，Sharelock）：事務(wù)T對(duì)數(shù)據(jù)對(duì)象A加上S鎖，則事務(wù)T可以讀取但不能修改A，其它事務(wù)只能對(duì)A加S鎖（因而可以讀取A），而不能對(duì)A的加X鎖（因而不能修改A），直到T釋放A上的S鎖。并發(fā)控制一級(jí)封鎖協(xié)議事務(wù)T在修改數(shù)據(jù)R之前必須對(duì)其加X鎖，直到事務(wù)結(jié)束才釋放。事務(wù)結(jié)束包括正常結(jié)束(COMMIT)和非正常結(jié)束(ROLLBACK)。一級(jí)封鎖協(xié)議可以防止丟失修改，并保證事務(wù)T是可恢復(fù)的。在一級(jí)封鎖協(xié)議中，如果僅僅是讀數(shù)據(jù)而不對(duì)其進(jìn)行修改，是不需要對(duì)其加鎖的，因此它不能保證可重復(fù)讀和不讀“臟”數(shù)據(jù)。并發(fā)控制T1T2XLOCKA獲得讀A=16XLOCKAA=A-1寫回A=15COMMITUNLOCKA等待等待等待等待獲得XLOCKA讀A=15A=A-1寫回A=14COMMITUNLOCKA沒(méi)有丟失修改并發(fā)控制二級(jí)鎖協(xié)議二級(jí)鎖協(xié)議是：一級(jí)鎖協(xié)議加上事務(wù)T在讀取數(shù)據(jù)R之前必須先對(duì)其加S鎖，讀完后即可釋放S鎖。二級(jí)鎖除了防止丟失修改，還可以進(jìn)一步防止讀“臟”數(shù)據(jù)。但由于讀完后即可釋放S鎖，所以不能保證可重復(fù)讀。并發(fā)控制三級(jí)鎖協(xié)議三級(jí)鎖協(xié)議是：一級(jí)鎖協(xié)議加上事務(wù)T在讀取R之前必須對(duì)其加S鎖，直到事務(wù)結(jié)束才釋放。三級(jí)封鎖協(xié)議除了防止丟失修改和讀“臟”數(shù)據(jù)以外，還進(jìn)一步防止了不可重復(fù)讀。并發(fā)控制T1T2SLOCKA獲得SLOCKB獲得讀A=50讀B=100求和＝150XLOCKB讀A＝50讀B＝100求和=150COMMITUNLOCKAUNLOCKB等待等待等待等待等待等待T1T2等待等待等待等待獲得XLOCKB讀B＝100B=B*2寫回B=200COMMITUNLOCKB可重復(fù)讀并發(fā)控制X鎖S鎖一致性保證操作結(jié)束釋放事務(wù)結(jié)束釋放操作結(jié)束釋放事務(wù)結(jié)束釋放不丟失修改不讀“臟”數(shù)據(jù)可重復(fù)讀一級(jí)封鎖協(xié)議二級(jí)封鎖協(xié)議三級(jí)封鎖協(xié)議并發(fā)控制死鎖(Deadlock)定義 在數(shù)據(jù)庫(kù)運(yùn)行期間，如果存在一個(gè)事務(wù)集合={T0，T1，…，Tn}，使得T0等待T1持有的數(shù)據(jù)項(xiàng)鎖，…，Tn-1等待Tn持有的數(shù)據(jù)項(xiàng)鎖，Tn等待T1持有的數(shù)據(jù)項(xiàng)鎖，則稱系統(tǒng)處于死鎖狀態(tài)，稱為死鎖事務(wù)集合。并發(fā)控制死鎖的例子 如果事務(wù)T1封鎖了數(shù)據(jù)R1，T2封鎖了數(shù)據(jù)R2，然后T1又請(qǐng)求封鎖R2，因T2已封鎖了R2，于是T1等待T2釋放R2上的鎖。接著，T2又申請(qǐng)封鎖R1，因T1已經(jīng)封鎖了R1，T2也只能等待T1釋放R1上的鎖。這樣就出現(xiàn)了T1在等待T2，而T2又在等待T1的局面，T1和T2兩個(gè)事務(wù)永遠(yuǎn)不能結(jié)束，形成死鎖。并發(fā)控制解決死鎖的方法①預(yù)防死鎖②死鎖檢測(cè)和恢復(fù)并發(fā)控制死鎖檢測(cè)超時(shí)法如果一個(gè)事務(wù)的等待時(shí)間超過(guò)了規(guī)定的期限，就認(rèn)為發(fā)生了死鎖。等待圖法事務(wù)等待圖是一個(gè)有向回路G=(T,U)。T為結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)表示正在運(yùn)行的事務(wù)；U為邊的集合，每條邊表示事務(wù)等待的情況。若T1等待T2，則T1，T2之間畫一條有向邊，從T1指向T2。事務(wù)等待圖動(dòng)態(tài)地反映了所有事務(wù)的等待情況。并發(fā)控制子系統(tǒng)周期性的檢測(cè)事務(wù)等待圖，如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)出現(xiàn)死鎖。并發(fā)控制T2T1T3事務(wù)號(hào)占有資源號(hào)請(qǐng)求資源號(hào)T1R1R2T2R2R3T3R3R1事務(wù)的調(diào)度與可串行性問(wèn)題：計(jì)算機(jī)系統(tǒng)對(duì)并發(fā)事務(wù)中并發(fā)操作的調(diào)度是隨機(jī)的，而不同的調(diào)度可能產(chǎn)生不同的結(jié)果，那么哪個(gè)結(jié)果是正確的呢？定義：多個(gè)事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行的執(zhí)行它們時(shí)的結(jié)果相同，我們稱這種調(diào)度策略為可串行化調(diào)度。一個(gè)給定的并發(fā)調(diào)度，當(dāng)且僅當(dāng)它是可串行化的，才認(rèn)為是正確調(diào)度。并發(fā)控制兩段鎖協(xié)議(Two-phaseLocking)內(nèi)容①在對(duì)任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要獲得對(duì)該數(shù)據(jù)的封鎖。②在釋放一個(gè)封鎖之后，事務(wù)不再獲得任何其它封鎖。并發(fā)控制所謂兩階段鎖協(xié)議的含義是指所有事務(wù)必須分兩個(gè)階段對(duì)數(shù)據(jù)項(xiàng)加鎖和解鎖。第一階段是獲得封鎖也稱擴(kuò)展階段。在這一階段，事務(wù)可以申請(qǐng)獲得任何數(shù)據(jù)項(xiàng)上的任何類型的封鎖，但不能釋放任何鎖。第二階段是釋放階段，也稱收縮階段。在這階段，事務(wù)可以釋放任何數(shù)據(jù)項(xiàng)上的任何類型的封鎖，但是不能夠再申請(qǐng)任何鎖。定理：若所有事務(wù)均遵從兩段鎖協(xié)議，則這些事務(wù)的所有并行調(diào)度都是可串行化的。并發(fā)控制T1T2SLOCKB得到讀B=2Y=BXLOCKASLOCKA等待A=Y+1寫回A=3UNLOCKBUNLOCKA等待等待等待等待T1T2SLOCKA得到讀A=3Y=AXLOCKB得到B=Y+1寫回B=4UNLOCKBUNLOCKA并發(fā)控制封鎖粒度封鎖對(duì)象的大小稱為封鎖粒度封鎖對(duì)象：包括邏輯單元，如:屬性值、屬性值集合、元組、關(guān)系、某索引項(xiàng)、整個(gè)索引、整個(gè)數(shù)據(jù)庫(kù)；和物理單元如：物理頁(yè)、塊。封鎖粒度大，則并發(fā)度低，封鎖機(jī)構(gòu)簡(jiǎn)單，開銷小。 封鎖粒度小，則并發(fā)度高，封鎖機(jī)構(gòu)復(fù)雜，開銷高。如果在一個(gè)系統(tǒng)中同時(shí)支持多種封鎖粒度供不同的事務(wù)選擇是比較理想的，這種封鎖方法稱為多粒度封鎖（MultipleGranularityLocking）。選擇封鎖粒度時(shí)應(yīng)同時(shí)考慮封鎖開銷和并發(fā)度兩個(gè)因素，適當(dāng)選擇封鎖粒度以達(dá)到最優(yōu)效果。并發(fā)控制多粒度樹多粒度樹的根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫(kù)，表示最大的粒度。葉結(jié)點(diǎn)表示最小的粒度。數(shù)據(jù)庫(kù)關(guān)系Rn關(guān)系R1……元組元組……元組元組……并發(fā)控制多粒度封鎖協(xié)議多粒度封鎖協(xié)議允許多粒度樹中的每個(gè)結(jié)點(diǎn)被獨(dú)立地加鎖。對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)的所有后裔結(jié)點(diǎn)也被加以同樣類型的鎖。因此，在多粒度封鎖中一個(gè)數(shù)據(jù)對(duì)象可能以兩種方式封鎖，即：顯式封鎖是應(yīng)事務(wù)的要求直接加到數(shù)據(jù)對(duì)象上的封鎖。隱式封鎖是該數(shù)據(jù)對(duì)象沒(méi)有獨(dú)立加鎖，是由于其上級(jí)結(jié)點(diǎn)加鎖而使該數(shù)據(jù)對(duì)象加上了鎖。并發(fā)控制意向鎖一般的，對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖，系統(tǒng)要檢查該數(shù)據(jù)對(duì)象上有無(wú)顯式封鎖與之沖突；還要檢查其所有上級(jí)結(jié)點(diǎn)，看本事務(wù)的顯式封鎖是否與該數(shù)據(jù)對(duì)象上的隱式封鎖沖突；還要檢查其所有下級(jí)結(jié)點(diǎn)，看上面的顯式封鎖是否與本事務(wù)的隱式封鎖沖突。效率很低，因此引入了意向鎖。意向鎖的含義是如果對(duì)一個(gè)結(jié)點(diǎn)加意向鎖，則說(shuō)明該結(jié)點(diǎn)的下層結(jié)點(diǎn)正在被加鎖；對(duì)任一結(jié)點(diǎn)加鎖時(shí)，必須先對(duì)它的上層結(jié)點(diǎn)加意向鎖。并發(fā)控制三種常用的意向鎖意向共享鎖（IntentShareLock，簡(jiǎn)稱IS鎖）如果要對(duì)一個(gè)數(shù)據(jù)對(duì)象加IS鎖，表示它的后裔結(jié)點(diǎn)擬（意向）加S鎖。意向排它鎖（IntentExclusiveLock，簡(jiǎn)稱IX鎖）如果要對(duì)一個(gè)數(shù)據(jù)對(duì)象加IX鎖，表示