數(shù)據(jù)庫(kù)系統(tǒng)概論高等教育出版社chp11

1、數(shù)據(jù)庫(kù)系統(tǒng)概論數(shù)據(jù)庫(kù)系統(tǒng)概論 An Introduction to Database System 第十一章第十一章 并發(fā)控制并發(fā)控制 主要內(nèi)容：本章主要介紹數(shù)據(jù)庫(kù)的并發(fā)控制主要內(nèi)容：本章主要介紹數(shù)據(jù)庫(kù)的并發(fā)控制 機(jī)制的概念及保證并發(fā)執(zhí)行正確性的原則。機(jī)制的概念及保證并發(fā)執(zhí)行正確性的原則。 重點(diǎn)難點(diǎn)：并發(fā)控制、重點(diǎn)難點(diǎn)：并發(fā)控制、 鎖協(xié)議、鎖協(xié)議、 并發(fā)控制的并發(fā)控制的 正確性準(zhǔn)則等概念。正確性準(zhǔn)則等概念。 多用戶數(shù)據(jù)庫(kù)系統(tǒng)的存在 允許多個(gè)用戶同時(shí)使用的數(shù)據(jù)庫(kù)系統(tǒng) n飛機(jī)定票數(shù)據(jù)庫(kù)系統(tǒng) n銀行數(shù)據(jù)庫(kù)系統(tǒng) 特點(diǎn)：在同一時(shí)刻并發(fā)運(yùn)行的事務(wù)數(shù)可達(dá)數(shù)百個(gè) 不同的多事務(wù)執(zhí)行方式 (1)事務(wù)串行執(zhí)行 每個(gè)

2、時(shí)刻只有一個(gè)事務(wù)運(yùn)行，其 他事務(wù)必須等到這個(gè)事務(wù)結(jié)束以 后方能運(yùn)行 不能充分利用系統(tǒng)資源，發(fā)揮數(shù) 據(jù)庫(kù)共享資源的特點(diǎn) T1 T2 T3 事務(wù)的串行執(zhí)行方式 (2)交叉并發(fā)方式（Interleaved Concurrency） 在單處理機(jī)系統(tǒng)中，事務(wù)的并行執(zhí)行是這些并行事務(wù) 的并行操作輪流交叉運(yùn)行 單處理機(jī)系統(tǒng)中的并行事務(wù)并沒(méi)有真正地并行運(yùn)行， 但能夠減少處理機(jī)的空閑時(shí)間，提高系統(tǒng)的效率 事務(wù)的交叉并發(fā)執(zhí)行方式 (3)同時(shí)并發(fā)方式（simultaneous concurrency） 多處理機(jī)系統(tǒng)中，每個(gè)處理機(jī)可以運(yùn)行一個(gè)事務(wù)， 多個(gè)處理機(jī)可以同時(shí)運(yùn)行多個(gè)事務(wù)，實(shí)現(xiàn)多個(gè)事務(wù) 真正的并行運(yùn)行 一個(gè)簡(jiǎn)

3、單的銀行數(shù)據(jù)庫(kù)系統(tǒng)一個(gè)簡(jiǎn)單的銀行數(shù)據(jù)庫(kù)系統(tǒng) 設(shè)每個(gè)帳號(hào)在數(shù)據(jù)庫(kù)中具有一條數(shù)據(jù)庫(kù)記設(shè)每個(gè)帳號(hào)在數(shù)據(jù)庫(kù)中具有一條數(shù)據(jù)庫(kù)記 錄，用以記錄這個(gè)帳號(hào)的存款數(shù)量和其他信息。錄，用以記錄這個(gè)帳號(hào)的存款數(shù)量和其他信息。 設(shè)有兩個(gè)事務(wù)設(shè)有兩個(gè)事務(wù)T0和和T1， 事務(wù)事務(wù)T0從帳號(hào)從帳號(hào)A轉(zhuǎn)轉(zhuǎn)2000 元到帳號(hào)元到帳號(hào)B；事務(wù)；事務(wù)T1從帳號(hào)從帳號(hào)A轉(zhuǎn)轉(zhuǎn)20%的款到帳的款到帳 號(hào)號(hào)B。 T 0和和T 1的定義如下：的定義如下： 例例: 事務(wù)并發(fā)執(zhí)行帶來(lái)的問(wèn)題 T0: read(A); T1: read(A); A:=A-2000; temp:=A*0.2; write(A); A:=A-temp; read(B)

4、; write(A); B:=B+2000; read(B); write(B) B:=B+temp; write(B) 假設(shè)用假設(shè)用A和和B表示帳號(hào)表示帳號(hào)A和帳號(hào)和帳號(hào)B的存款數(shù)量；的存款數(shù)量； A、B的初值為的初值為10000和和20000。如果這兩個(gè)事務(wù)順。如果這兩個(gè)事務(wù)順 序執(zhí)行，可以有兩種方案。序執(zhí)行，可以有兩種方案。 一種是先執(zhí)行一種是先執(zhí)行T0后執(zhí)行后執(zhí)行T1，如圖，如圖a所示。所示。 另一種是先執(zhí)行另一種是先執(zhí)行T1后執(zhí)行后執(zhí)行T0，如圖，如圖b所示。所示。 結(jié)果正確 結(jié)果錯(cuò)誤 對(duì)于對(duì)于N N個(gè)事務(wù)，一個(gè)事務(wù)，一 定最多有定最多有N!N!種正確種正確 的串行調(diào)度。并行的串行調(diào)

5、度。并行 調(diào)度將產(chǎn)生不一致調(diào)度將產(chǎn)生不一致 狀態(tài)。狀態(tài)。 并發(fā)事務(wù)的可串行化并發(fā)事務(wù)的可串行化 可串行化并行調(diào)度策略：幾個(gè)事務(wù)的并行執(zhí)行是正確可串行化并行調(diào)度策略：幾個(gè)事務(wù)的并行執(zhí)行是正確 的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行執(zhí)行它們時(shí)的結(jié)果的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行執(zhí)行它們時(shí)的結(jié)果 相同。相同?？纱行允遣⑿惺聞?wù)正確性的惟一準(zhǔn)則可串行性是并行事務(wù)正確性的惟一準(zhǔn)則。 會(huì)產(chǎn)生多個(gè)事務(wù)同時(shí)存取同一數(shù)據(jù)的情況 可能會(huì)存取和存儲(chǔ)不正確的數(shù)據(jù)，破壞事務(wù)一致性和 數(shù)據(jù)庫(kù)的一致性 事務(wù)并發(fā)執(zhí)行帶來(lái)的問(wèn)題 DBMS的一個(gè)重要任務(wù)就是要有一種機(jī)制去保證事務(wù)在的一個(gè)重要任務(wù)就是要有一種機(jī)制去保證事務(wù)在 并發(fā)

6、的存取和修改數(shù)據(jù)的時(shí)候數(shù)據(jù)的完整性不被破壞，并發(fā)的存取和修改數(shù)據(jù)的時(shí)候數(shù)據(jù)的完整性不被破壞， 同時(shí)同時(shí) 確保這些事務(wù)能正確的運(yùn)行并取得正確的結(jié)果。確保這些事務(wù)能正確的運(yùn)行并取得正確的結(jié)果。 并發(fā)控制就并發(fā)控制就 是一種在多用戶環(huán)境下對(duì)數(shù)據(jù)庫(kù)進(jìn)行并發(fā)操作規(guī)范的機(jī)制。是一種在多用戶環(huán)境下對(duì)數(shù)據(jù)庫(kù)進(jìn)行并發(fā)操作規(guī)范的機(jī)制。 1. 并發(fā)帶來(lái)的好處和問(wèn)題并發(fā)帶來(lái)的好處和問(wèn)題 (1) 并發(fā)的優(yōu)點(diǎn)并發(fā)的優(yōu)點(diǎn) 改善系統(tǒng)的資源利用率。改善系統(tǒng)的資源利用率。 (2) 并發(fā)所引起的問(wèn)題并發(fā)所引起的問(wèn)題 在并發(fā)執(zhí)行過(guò)程中如果不對(duì)并發(fā)執(zhí)行的事務(wù)通過(guò)某種在并發(fā)執(zhí)行過(guò)程中如果不對(duì)并發(fā)執(zhí)行的事務(wù)通過(guò)某種 機(jī)制加以控制，機(jī)制加以

7、控制， 將有可能產(chǎn)生數(shù)據(jù)的不一致性等問(wèn)題。將有可能產(chǎn)生數(shù)據(jù)的不一致性等問(wèn)題。 以飛機(jī)訂票系統(tǒng)為例的一個(gè)活動(dòng)序列：以飛機(jī)訂票系統(tǒng)為例的一個(gè)活動(dòng)序列： 甲售票點(diǎn)（甲事務(wù)）讀出某航班的機(jī)票余額，甲售票點(diǎn)（甲事務(wù)）讀出某航班的機(jī)票余額， 設(shè)；設(shè)； 乙售票點(diǎn)（乙事務(wù)）讀出同一航班的機(jī)票余額，乙售票點(diǎn)（乙事務(wù)）讀出同一航班的機(jī)票余額， 也為；也為； 甲售票點(diǎn)賣出一張機(jī)票，甲售票點(diǎn)賣出一張機(jī)票， 修改余額修改余額， 變?yōu)?，變?yōu)椋?把寫(xiě)回?cái)?shù)據(jù)庫(kù)；把寫(xiě)回?cái)?shù)據(jù)庫(kù)； 乙售票點(diǎn)也賣出一張機(jī)票，乙售票點(diǎn)也賣出一張機(jī)票， 修改余額修改余額， 也變?yōu)?，也變?yōu)椋?把寫(xiě)回?cái)?shù)據(jù)庫(kù)。把寫(xiě)回?cái)?shù)據(jù)庫(kù)。 結(jié)果是明明賣出兩張結(jié)果是明明賣出

8、兩張 機(jī)票，機(jī)票， 但數(shù)據(jù)庫(kù)中機(jī)票余額只減少。但數(shù)據(jù)庫(kù)中機(jī)票余額只減少。 這種情況稱為這種情況稱為數(shù)據(jù)庫(kù)的不一致性數(shù)據(jù)庫(kù)的不一致性。 這種不這種不 一致性是由一致性是由并發(fā)操作引起并發(fā)操作引起的。的。 在并發(fā)操作情況下，在并發(fā)操作情況下， 對(duì)甲、對(duì)甲、 乙兩個(gè)事務(wù)的操作序列的調(diào)度是隨機(jī)的。乙兩個(gè)事務(wù)的操作序列的調(diào)度是隨機(jī)的。 若按上面的調(diào)度序列執(zhí)行，若按上面的調(diào)度序列執(zhí)行， 甲事務(wù)的修改就被丟甲事務(wù)的修改就被丟 失。失。 這是由于第步中乙事務(wù)修改并寫(xiě)回后覆這是由于第步中乙事務(wù)修改并寫(xiě)回后覆 蓋了甲事務(wù)的修改。蓋了甲事務(wù)的修改。 可見(jiàn)，可見(jiàn)， 若對(duì)并發(fā)的事務(wù)訪問(wèn)若對(duì)并發(fā)的事務(wù)訪問(wèn) 數(shù)據(jù)庫(kù)的操作不

9、進(jìn)行有效控制，數(shù)據(jù)庫(kù)的操作不進(jìn)行有效控制， 數(shù)據(jù)庫(kù)中的數(shù)據(jù)數(shù)據(jù)庫(kù)中的數(shù)據(jù) 就有可能變?yōu)椴徽_，就有可能變?yōu)椴徽_， 從而影響數(shù)據(jù)的正確性。從而影響數(shù)據(jù)的正確性。 注： 并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性通常分為三類：并發(fā)操作帶來(lái)的數(shù)據(jù)不一致性通常分為三類： 丟失修丟失修 改、不可重復(fù)讀和讀改、不可重復(fù)讀和讀“臟臟”數(shù)據(jù)。數(shù)據(jù)。 丟失修改丟失修改（Lost Update）。 丟失修改是由于兩個(gè)事務(wù)對(duì)同一數(shù)據(jù)并發(fā)地寫(xiě)入所引丟失修改是由于兩個(gè)事務(wù)對(duì)同一數(shù)據(jù)并發(fā)地寫(xiě)入所引 起的，起的， 常稱為寫(xiě)后寫(xiě)沖突（常稱為寫(xiě)后寫(xiě)沖突（Write-Write Conflict）。）。 上上 面飛機(jī)訂票例子就屬此類。面飛機(jī)訂

10、票例子就屬此類。 不可重復(fù)讀不可重復(fù)讀（Non-Repeatable Read）。 不可重復(fù)讀是指事務(wù)不可重復(fù)讀是指事務(wù)T1讀取數(shù)據(jù)后，事務(wù)讀取數(shù)據(jù)后，事務(wù)T2執(zhí)行更新執(zhí)行更新 操作，操作， 使使1無(wú)法再現(xiàn)前一次讀取結(jié)果。無(wú)法再現(xiàn)前一次讀取結(jié)果。 具體地講，具體地講， 不可不可 重復(fù)讀包括三種情況重復(fù)讀包括三種情況： （a） 事務(wù)事務(wù)T1讀取某一數(shù)據(jù)后，讀取某一數(shù)據(jù)后， 事務(wù)事務(wù)T2對(duì)其對(duì)其 作了修改，作了修改， 當(dāng)事務(wù)當(dāng)事務(wù)T1再次讀該數(shù)據(jù)時(shí)，再次讀該數(shù)據(jù)時(shí)， 得到與前得到與前 一次不同的值。一次不同的值。 時(shí)刻事務(wù)T1事務(wù)T2數(shù)據(jù)庫(kù)X的值 t0read(X)X=30 t1read(X)X=

11、30 t2X:X+10 t3write(X)X=40 t4X=30是一個(gè)過(guò)時(shí)的數(shù)據(jù) （b） 事務(wù)事務(wù)T1按一定條件從數(shù)據(jù)庫(kù)中讀取了某些數(shù)據(jù)按一定條件從數(shù)據(jù)庫(kù)中讀取了某些數(shù)據(jù) 記錄后，記錄后， 事務(wù)事務(wù)T2刪除了其中部分記錄，刪除了其中部分記錄， 當(dāng)當(dāng)T1再次按相再次按相 同條件讀取數(shù)據(jù)時(shí)，同條件讀取數(shù)據(jù)時(shí)， 發(fā)現(xiàn)某些記錄神秘的消失了。發(fā)現(xiàn)某些記錄神秘的消失了。 （c） 事務(wù)事務(wù)T1按一定條件從數(shù)據(jù)庫(kù)中讀取了某些數(shù)按一定條件從數(shù)據(jù)庫(kù)中讀取了某些數(shù) 據(jù)記錄后，據(jù)記錄后， 事務(wù)事務(wù)T2插入了一些記錄，插入了一些記錄， 當(dāng)當(dāng)T1再次按相同再次按相同 條件讀取數(shù)據(jù)時(shí)，條件讀取數(shù)據(jù)時(shí)， 發(fā)現(xiàn)多了一些記錄。

12、發(fā)現(xiàn)多了一些記錄。 后兩種不可重復(fù)讀有時(shí)也稱為后兩種不可重復(fù)讀有時(shí)也稱為幻影（幻影（Phantom Row）現(xiàn)象）現(xiàn)象。 讀讀“臟臟”數(shù)據(jù)（數(shù)據(jù)（irty Read）。）。 讀讀“臟臟”數(shù)據(jù)是指兩個(gè)或多個(gè)事務(wù)并發(fā)執(zhí)行時(shí)，數(shù)據(jù)是指兩個(gè)或多個(gè)事務(wù)并發(fā)執(zhí)行時(shí)， 事務(wù)事務(wù) T1修改了某一數(shù)據(jù)，修改了某一數(shù)據(jù)， 并將其寫(xiě)回磁盤(pán)，并將其寫(xiě)回磁盤(pán)， 事務(wù)事務(wù)T2在這之后讀在這之后讀 取了同一數(shù)據(jù)，取了同一數(shù)據(jù)， 此時(shí)事務(wù)此時(shí)事務(wù)T1在未正式提交之前由于某種原在未正式提交之前由于某種原 因被撤銷，因被撤銷， 系統(tǒng)就要對(duì)事務(wù)系統(tǒng)就要對(duì)事務(wù)T1已修改過(guò)的數(shù)據(jù)恢復(fù)原值，已修改過(guò)的數(shù)據(jù)恢復(fù)原值， 這樣事務(wù)這樣事務(wù)T2

13、讀的數(shù)據(jù)就與數(shù)據(jù)庫(kù)中的數(shù)據(jù)產(chǎn)生了不一致，讀的數(shù)據(jù)就與數(shù)據(jù)庫(kù)中的數(shù)據(jù)產(chǎn)生了不一致， 稱這種數(shù)據(jù)為稱這種數(shù)據(jù)為“臟臟”數(shù)據(jù)。數(shù)據(jù)。 產(chǎn)生上述三類數(shù)據(jù)不一致性的產(chǎn)生上述三類數(shù)據(jù)不一致性的 主要原因是并發(fā)操作破壞了事務(wù)的隔離性。主要原因是并發(fā)操作破壞了事務(wù)的隔離性。 時(shí)刻事務(wù)T1事務(wù)T2數(shù)據(jù)庫(kù)X的值 t0read(X)X=10 t1X:X*X t2write(X)X=100 t3read(X)X=100 t4ROLLBACK T 數(shù)據(jù)不一致性：數(shù)據(jù)不一致性：由于并發(fā)操作破壞了事務(wù)的隔離性由于并發(fā)操作破壞了事務(wù)的隔離性 T 并發(fā)控制就是要用并發(fā)控制就是要用正確的方式調(diào)度并發(fā)操作正確的方式調(diào)度并發(fā)操作，使

14、一個(gè)用戶，使一個(gè)用戶 事務(wù)的執(zhí)行不受其他事務(wù)的干擾，從而避免造成數(shù)據(jù)的不事務(wù)的執(zhí)行不受其他事務(wù)的干擾，從而避免造成數(shù)據(jù)的不 一致性一致性 并發(fā)控制的主要技術(shù)并發(fā)控制的主要技術(shù) 封鎖封鎖(Locking) 時(shí)間戳?xí)r間戳(Timestamp) 樂(lè)觀控制法樂(lè)觀控制法 商用的商用的DBMS一般都采用封鎖方法一般都采用封鎖方法 什么是封鎖 基本封鎖類型 鎖的相容矩陣 封鎖封鎖 封鎖是實(shí)現(xiàn)并發(fā)控制的一個(gè)非常重要的技術(shù)。封鎖是實(shí)現(xiàn)并發(fā)控制的一個(gè)非常重要的技術(shù)。 (1) 封鎖的定義及類型封鎖的定義及類型。 所謂封鎖就是事務(wù)在對(duì)某個(gè)數(shù)據(jù)對(duì)象（如表、所謂封鎖就是事務(wù)在對(duì)某個(gè)數(shù)據(jù)對(duì)象（如表、 記錄等）記錄等） 操作

15、之前，操作之前， 先向系統(tǒng)發(fā)出請(qǐng)求，先向系統(tǒng)發(fā)出請(qǐng)求， 對(duì)其加鎖。對(duì)其加鎖。 加鎖后事務(wù)就加鎖后事務(wù)就 對(duì)該數(shù)據(jù)對(duì)象有了一定的控制，對(duì)該數(shù)據(jù)對(duì)象有了一定的控制， 在事務(wù)釋放它的鎖之前，在事務(wù)釋放它的鎖之前， 其他的事務(wù)不能更新此數(shù)據(jù)對(duì)象。其他的事務(wù)不能更新此數(shù)據(jù)對(duì)象。 加鎖必須滿足一定的協(xié)議，加鎖必須滿足一定的協(xié)議， 即鎖協(xié)議（即鎖協(xié)議（Locking Protocol）。）。 基本的封鎖類型有兩種：基本的封鎖類型有兩種： 排它鎖（排它鎖（Exclusive Lock, 簡(jiǎn)稱簡(jiǎn)稱 X鎖）和共享鎖（鎖）和共享鎖（Share Locks, 簡(jiǎn)稱簡(jiǎn)稱S鎖）。鎖）。 排它鎖排它鎖(又稱寫(xiě)鎖又稱寫(xiě)鎖)：

16、 若事務(wù)對(duì)數(shù)據(jù)對(duì)象加上鎖，若事務(wù)對(duì)數(shù)據(jù)對(duì)象加上鎖， 則只允許讀取和修改，則只允許讀取和修改， 其他任何事務(wù)都不能再對(duì)其他任何事務(wù)都不能再對(duì) 加任何類型的鎖，加任何類型的鎖， 直至直至T釋放其鎖為止。釋放其鎖為止。 這就保證了其這就保證了其 他事務(wù)在釋放上的鎖之前不能再讀取和修改。他事務(wù)在釋放上的鎖之前不能再讀取和修改。 共享鎖（又稱為讀鎖）：共享鎖（又稱為讀鎖）： 若事務(wù)對(duì)數(shù)據(jù)對(duì)象加上若事務(wù)對(duì)數(shù)據(jù)對(duì)象加上 鎖，鎖， 則事務(wù)可以讀但不能修改，則事務(wù)可以讀但不能修改， 其他事物只能其他事物只能 再對(duì)加鎖，再對(duì)加鎖， 而不能加鎖，而不能加鎖， 直到釋放上的鎖。直到釋放上的鎖。 這就保證了其他事物可以

17、讀，這就保證了其他事物可以讀， 但在釋放上的鎖之但在釋放上的鎖之 前不能對(duì)做任何修改。前不能對(duì)做任何修改。 表 封鎖類型的相容矩陣 T1T2 Xlock A R(A)=16 Xlock A AA-1等待 W(A)=15等待 Commit等待 Unlock A等待 獲得Xlock A R(A)=15 AA-1 W(A)=14 Commit Unlock A 例：例： T1T2 Slock A Slock B R(A)=50 R(B)=100 求和=150 Xlock B 等待 等待 R(A)=50等待 R(B)=100等待 求和=150等待 Commit等待 Unlock A等待 Unlock

18、B等待 獲得XlockB R(B)=100 BB*2 W(B)=200 Commit Unlock B T1T2 Xlock C R(C)=100 CC*2 W(C)=200 Slock C 等待 ROLLBACK等待 (C恢復(fù)為100)等待 Unlock C等待 獲得Slock C R(C)=100 Commit C Unlock C 例例 封鎖技術(shù)可以有效地解決并行操作的一致性問(wèn)題，但封鎖技術(shù)可以有效地解決并行操作的一致性問(wèn)題，但 也帶來(lái)一些新的問(wèn)題也帶來(lái)一些新的問(wèn)題 死鎖死鎖 活鎖活鎖 T 事務(wù)事務(wù)T1封鎖了數(shù)據(jù)封鎖了數(shù)據(jù)R T 事務(wù)事務(wù)T2又請(qǐng)求封鎖又請(qǐng)求封鎖R，于是，于是T2等待。等

19、待。 T T3也請(qǐng)求封鎖也請(qǐng)求封鎖R，當(dāng)，當(dāng)T1釋放了釋放了R上的封鎖之后系統(tǒng)首先批上的封鎖之后系統(tǒng)首先批 準(zhǔn)了準(zhǔn)了T3的請(qǐng)求，的請(qǐng)求，T2仍然等待。仍然等待。 T T4又請(qǐng)求封鎖又請(qǐng)求封鎖R，當(dāng)，當(dāng)T3釋放了釋放了R上的封鎖之后系統(tǒng)又批準(zhǔn)上的封鎖之后系統(tǒng)又批準(zhǔn) 了了T4的請(qǐng)求的請(qǐng)求 T T2有可能永遠(yuǎn)等待，這就是有可能永遠(yuǎn)等待，這就是活鎖活鎖的情形的情形 避免活鎖：采用避免活鎖：采用先來(lái)先服務(wù)先來(lái)先服務(wù)的策略。的策略。 當(dāng)多個(gè)事務(wù)請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí)當(dāng)多個(gè)事務(wù)請(qǐng)求封鎖同一數(shù)據(jù)對(duì)象時(shí) 按請(qǐng)求封鎖的先后次序?qū)@些事務(wù)排隊(duì)按請(qǐng)求封鎖的先后次序?qū)@些事務(wù)排隊(duì) 該數(shù)據(jù)對(duì)象上的鎖一旦釋放，首先批準(zhǔn)申請(qǐng)

20、隊(duì)列中第該數(shù)據(jù)對(duì)象上的鎖一旦釋放，首先批準(zhǔn)申請(qǐng)隊(duì)列中第 一個(gè)事務(wù)獲得鎖一個(gè)事務(wù)獲得鎖 T 事務(wù)事務(wù)T1封鎖了數(shù)據(jù)封鎖了數(shù)據(jù)R1 T T2封鎖了數(shù)據(jù)封鎖了數(shù)據(jù)R2 T T1又請(qǐng)求封鎖又請(qǐng)求封鎖R2，因，因T2已封鎖了已封鎖了R2，于是，于是T1等待等待T2釋放釋放 R2上的鎖上的鎖 T 接著接著T2又申請(qǐng)封鎖又申請(qǐng)封鎖R1，因，因T1已封鎖了已封鎖了R1，T2也只能等待也只能等待 T1釋放釋放R1上的鎖上的鎖 T 這樣這樣T1在等待在等待T2，而，而T2又在等待又在等待T1，T1和和T2兩個(gè)事務(wù)永兩個(gè)事務(wù)永 遠(yuǎn)不遠(yuǎn)不能結(jié)束，形成能結(jié)束，形成死鎖死鎖 T1T2 lock R1 Lock R2 Lo

21、ck R2. 等待 等待Lock R1 等待等待 等待等待 兩類方法 1. 預(yù)防死鎖 2. 死鎖的診斷與解除 T 產(chǎn)生死鎖的原因是兩個(gè)或多個(gè)事務(wù)都已封鎖了一些數(shù)據(jù)對(duì) 象，然后又都請(qǐng)求對(duì)已為其他事務(wù)封鎖的數(shù)據(jù)對(duì)象加鎖， 從而出現(xiàn)死等待。 T 預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件 預(yù)防死鎖的方法 一次封鎖法 順序封鎖法 要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，要求每個(gè)事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖， 否則就不能繼續(xù)執(zhí)行否則就不能繼續(xù)執(zhí)行 存在的問(wèn)題存在的問(wèn)題 降低系統(tǒng)并發(fā)度降低系統(tǒng)并發(fā)度 難于事先精確確定封鎖對(duì)象難于事先精確確定封鎖對(duì)象 順序封鎖法是預(yù)先對(duì)數(shù)據(jù)對(duì)象規(guī)定一個(gè)封鎖順序

22、，所有事 務(wù)都按這個(gè)順序?qū)嵭蟹怄i。 順序封鎖法存在的問(wèn)題 維護(hù)成本 數(shù)據(jù)庫(kù)系統(tǒng)中封鎖的數(shù)據(jù)對(duì)象極多，并且在不斷地變 化。 難以實(shí)現(xiàn)：很難事先確定每一個(gè)事務(wù)要封鎖哪些對(duì)象 結(jié)論結(jié)論 在操作系統(tǒng)中廣為采用的預(yù)防死鎖的策略并不很適合在操作系統(tǒng)中廣為采用的預(yù)防死鎖的策略并不很適合 數(shù)據(jù)庫(kù)的特點(diǎn)數(shù)據(jù)庫(kù)的特點(diǎn) DBMS在解決死鎖的問(wèn)題上更普遍采用的是診斷并解在解決死鎖的問(wèn)題上更普遍采用的是診斷并解 除死鎖的方法除死鎖的方法 死鎖的診斷死鎖的診斷 n超時(shí)法超時(shí)法 n事務(wù)等待圖法事務(wù)等待圖法 T 如果一個(gè)事務(wù)的等待時(shí)間超過(guò)了規(guī)定的時(shí)限，就認(rèn)為如果一個(gè)事務(wù)的等待時(shí)間超過(guò)了規(guī)定的時(shí)限，就認(rèn)為 發(fā)生了死鎖發(fā)生了死鎖

23、 T 優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單 T 缺點(diǎn)缺點(diǎn) 有可能誤判死鎖有可能誤判死鎖 時(shí)限若設(shè)置得太長(zhǎng)，死鎖發(fā)生后不能及時(shí)發(fā)現(xiàn)時(shí)限若設(shè)置得太長(zhǎng)，死鎖發(fā)生后不能及時(shí)發(fā)現(xiàn) 用事務(wù)等待圖動(dòng)態(tài)反映所有事務(wù)的等待情況用事務(wù)等待圖動(dòng)態(tài)反映所有事務(wù)的等待情況 事務(wù)等待圖是一個(gè)有向圖事務(wù)等待圖是一個(gè)有向圖G=(T，U) T為結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)表示正運(yùn)行的事務(wù)為結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)表示正運(yùn)行的事務(wù) U為邊的集合，每條邊表示事務(wù)等待的情況為邊的集合，每條邊表示事務(wù)等待的情況 若若T1等待等待T2，則，則T1，T2之間劃一條有向邊，從之間劃一條有向邊，從T1指向指向 T2 事務(wù)等待圖 n 圖圖(a)中，事務(wù)中，事務(wù)T1

24、等待等待T2，T2等待等待T1，產(chǎn)生了死鎖，產(chǎn)生了死鎖 n 圖圖(b)中，事務(wù)中，事務(wù)T1等待等待T2，T2等待等待T3，T3等待等待T4，T4又等待又等待 T1，產(chǎn)生了死鎖，產(chǎn)生了死鎖 n 圖圖(b)中，事務(wù)中，事務(wù)T3可能還等待可能還等待T2，在大回路中又有小的回路，在大回路中又有小的回路 并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務(wù)并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務(wù) 等待圖，檢測(cè)事務(wù)。如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中等待圖，檢測(cè)事務(wù)。如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中 出現(xiàn)了死鎖。出現(xiàn)了死鎖。 解除死鎖解除死鎖 選擇一個(gè)處理死鎖代價(jià)最小的事務(wù)，將其撤消選擇一個(gè)處理死鎖代價(jià)

25、最小的事務(wù)，將其撤消 釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能繼續(xù)運(yùn)行釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能繼續(xù)運(yùn)行 下去下去 DBMS對(duì)并發(fā)事務(wù)不同的調(diào)度可能會(huì)產(chǎn)生不同的結(jié)果 什么樣的調(diào)度是正確的？ 可串行化(Serializable)調(diào)度 n多個(gè)事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與 按某一次序串行地執(zhí)行這些事務(wù)時(shí)的結(jié)果相同 可串行性(Serializability) 是并發(fā)事務(wù)正確調(diào)度的準(zhǔn)則 一個(gè)給定的并發(fā)調(diào)度，當(dāng)且僅當(dāng)它是可串行化的， 才認(rèn)為是正確調(diào)度 例現(xiàn)在有兩個(gè)事務(wù)，分別包含下列操作： 事務(wù)T1：讀B；A=B+1；寫(xiě)回A 事務(wù)T2：讀A；B=A+1；寫(xiě)回B 現(xiàn)給出對(duì)這兩個(gè)事務(wù)不同的

26、調(diào)度策略 T1T2 Slock B Y=R(B)=2 Unlock B Xlock A A=Y+1=3 W(A) Unlock A Slock A X=R(A)=3 Unlock A Xlock B B=X+1=4 W(B) Unlock B 串行調(diào)度(a) n 假設(shè)A、B的初值均為2。 n 按T1T2次序執(zhí)行結(jié)果 為A=3，B=4 n 串行調(diào)度策略,正確的調(diào)度 T1T2 Slock A X=R(A)=2 Unlock A Xlock B B=X+1=3 W(B) Unlock B Slock B Y=R(B)=3 Unlock B Xlock A A=Y+1=4 W(A) Unlock A

27、串行調(diào)度(b) n 假設(shè)A、B的初值均為2。 n T2T1次序執(zhí)行結(jié)果為B=3， A=4 n 串行調(diào)度策略,正確的調(diào)度 T1T2 Slock B Y=R(B)=2 Slock A X=R(A)=2 Unlock B Unlock A Xlock A A=Y+1=3 W(A) Xlock B B=X+1=3 W(B) Unlock A Unlock B 不可串行化的調(diào)度 n 執(zhí)行結(jié)果與(a)、(b)的結(jié) 果都不同 n 是錯(cuò)誤的調(diào)度 T1T2 Slock B Y=R(B)=2 Unlock B Xlock A Slock A A=Y+1=3等待 W(A)等待 Unlock A等待 X=R(A)=3

28、 Unlock A Xlock B B=X+1=4 W(B) Unlock B 可串行化的調(diào)度 n 執(zhí)行結(jié)果與串行調(diào)度 (a)的執(zhí)行結(jié)果相同 n 是正確的調(diào)度 可串行化調(diào)度的充分條件充分條件 一個(gè)調(diào)度Sc在保證沖突操作沖突操作的次序不變的情況下，通 過(guò)交換兩個(gè)事務(wù)不沖突操作的次序得到另一個(gè)調(diào)度Sc， 如果Sc是串行的，稱調(diào)度Sc為沖突可串行化的調(diào)度 一個(gè)調(diào)度是沖突可串行化，一定是可串行化的調(diào)度 沖突操作沖突操作 沖突操作是指不同的事務(wù)對(duì)同一個(gè)數(shù)據(jù)的讀寫(xiě)操作和寫(xiě)寫(xiě) 操作 Ri (x)與Wj(x) /* 事務(wù)Ti讀x，Tj寫(xiě)x*/ Wi(x)與Wj(x) /* 事務(wù)Ti寫(xiě)x，Tj寫(xiě)x*/ 其他操作

29、是不沖突操作 不同事務(wù)的沖突操作和同一事務(wù)的兩個(gè)操作不能交換 (Swap) 例今有調(diào)度 Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) 把w2(A)與r1(B)w1(B)交換，得到： r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B) 再把r2(A)與r1(B)w1(B)交換： Sc2=r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) Sc2等價(jià)于一個(gè)串行調(diào)度T1，T2，Sc1沖突可串行化的調(diào) 度 沖突可串行化調(diào)度是可串行化調(diào)度的充分條件，不是必要 條件。還有不滿足沖突可串行化條件的可串行化

30、調(diào)度。 例有3個(gè)事務(wù) T1=W1(Y)W1(X)，T2=W2(Y)W2(X)，T3=W3(X) 調(diào)度L1=W1(Y)W1(X)W2(Y)W2(X) W3(X)是一個(gè)串行 調(diào)度。 調(diào)度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不滿足沖突可 串行化。但是調(diào)度L2是可串行化的，因?yàn)長(zhǎng)2執(zhí)行的結(jié) 果與調(diào)度L1相同，Y的值都等于T2的值，X的值都等于 T3的值 封鎖協(xié)議 運(yùn)用封鎖方法時(shí)，對(duì)數(shù)據(jù)對(duì)象加鎖時(shí)需要約定一些規(guī)則 何時(shí)申請(qǐng)封鎖 持鎖時(shí)間 何時(shí)釋放封鎖等 兩段封鎖協(xié)議(Two-Phase Locking，簡(jiǎn)稱2PL)是最常用 的一種封鎖協(xié)議，理論上證明使用兩段封鎖協(xié)議產(chǎn)生的是 可串行化

31、調(diào)度 兩段鎖協(xié)議 指所有事務(wù)必須分兩個(gè)階段對(duì)數(shù)據(jù)項(xiàng)加鎖和解鎖 n在對(duì)任何數(shù)據(jù)進(jìn)行讀、寫(xiě)操作之前，事務(wù)首先要獲得 對(duì)該數(shù)據(jù)的封鎖 n 在釋放一個(gè)封鎖之后，事務(wù)不再申請(qǐng)和獲得任何其他 封鎖 “兩段”鎖的含義 事務(wù)分為兩個(gè)階段 第一階段是獲得封鎖，也稱為擴(kuò)展階段 事務(wù)可以申請(qǐng)獲得任何數(shù)據(jù)項(xiàng)上的任何類型的鎖， 但是不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段 事務(wù)可以釋放任何數(shù)據(jù)項(xiàng)上的任何類型的鎖，但是 不能再申請(qǐng)任何鎖 例 事務(wù)Ti遵守兩段鎖協(xié)議，其封鎖序列是 ： Slock A Slock B Xlock C Unlock B Unlock A Unlock C； |擴(kuò)展階段| 收縮階段 |

32、 事務(wù)Tj不遵守兩段鎖協(xié)議，其封鎖序列是： Slock A Unlock A Slock B Xlock C Unlock C Unlock B； 圖 可串行化調(diào)度 如圖中如圖中,(a)和和(b)都是可串行化的調(diào)度，都是可串行化的調(diào)度， 但但(a) 中中T 1和和T 2都是遵守兩段鎖協(xié)議，都是遵守兩段鎖協(xié)議， (b)中中T1和和T 2不是遵守兩段鎖協(xié)議。不是遵守兩段鎖協(xié)議。 事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是 必要條件。 若并發(fā)事務(wù)都遵守兩段鎖協(xié)議，則對(duì)這些事務(wù)的任何并發(fā) 調(diào)度策略都是可串行化的 若并發(fā)事務(wù)的一個(gè)調(diào)度是可串行化的，不一定所有事務(wù)都 符合兩段鎖協(xié)議 兩段鎖協(xié)議與防

33、止死鎖的一次封鎖法 一次封鎖法要求每個(gè)事務(wù)必須一次將所有要使用的數(shù) 據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封鎖法 遵守兩段鎖協(xié)議 但是兩段鎖協(xié)議并不要求事務(wù)必須一次將所有要使用 的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務(wù)可能發(fā) 生死鎖 例 遵守兩段鎖協(xié)議的事務(wù)發(fā)生死鎖 T1 Slock B R(B)=2 Xlock A 等待等待 等待等待 T2 Slock A R(A)=2 Xlock A 等待等待 遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖 封鎖對(duì)象的大小稱為封鎖粒度(Granularity) 封鎖的對(duì)象：邏輯單元，物理單元 例：在關(guān)系數(shù)據(jù)庫(kù)中，封鎖對(duì)象： 邏輯單元: 屬性值、屬性值集合、元組、關(guān)系、

34、索引項(xiàng)、 整個(gè)索引、整個(gè)數(shù)據(jù)庫(kù)等 物理單元：頁(yè)（數(shù)據(jù)頁(yè)或索引頁(yè)）、物理記錄等 封鎖粒度與系統(tǒng)的并發(fā)度和并發(fā)控制的開(kāi)銷密切相關(guān)。 封鎖的粒度越大，數(shù)據(jù)庫(kù)所能夠封鎖的數(shù)據(jù)單元就越 少，并發(fā)度就越小，系統(tǒng)開(kāi)銷也越??； 封鎖的粒度越小，并發(fā)度較高，但系統(tǒng)開(kāi)銷也就越大 例 若封鎖粒度是數(shù)據(jù)頁(yè)，事務(wù)T1需要修改元組L1，則T1必 須對(duì)包含L1的整個(gè)數(shù)據(jù)頁(yè)A加鎖。如果T1對(duì)A加鎖后事務(wù) T2要修改A中元組L2，則T2被迫等待，直到T1釋放A。 如果封鎖粒度是元組，則T1和T2可以同時(shí)對(duì)L1和L2加鎖， 不需要互相等待，提高了系統(tǒng)的并行度。 事務(wù)T需要讀取整個(gè)表，若封鎖粒度是元組，T必須對(duì)表中 的每一個(gè)元組加

35、鎖，開(kāi)銷極大 多粒度封鎖(Multiple Granularity Locking) 在一個(gè)系統(tǒng)中同時(shí)支持多種封鎖粒度供不同的事務(wù)選擇 選擇封鎖粒度 同時(shí)考慮封鎖開(kāi)銷和并發(fā)度兩個(gè)因素，適當(dāng)選擇封鎖粒 度 需要處理多個(gè)關(guān)系的大量元組的用戶事務(wù)：以數(shù)據(jù)庫(kù) 為封鎖單位 需要處理大量元組的用戶事務(wù)：以關(guān)系為封鎖單元 只處理少量元組的用戶事務(wù)：以元組為封鎖單位 多粒度樹(shù) 以樹(shù)形結(jié)構(gòu)來(lái)表示多級(jí)封鎖粒度 根結(jié)點(diǎn)是整個(gè)數(shù)據(jù)庫(kù)，表示最大的數(shù)據(jù)粒度 葉結(jié)點(diǎn)表示最小的數(shù)據(jù)粒度 例：三級(jí)粒度樹(shù)。根結(jié)點(diǎn)為數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)的子結(jié)點(diǎn)為關(guān)系， 關(guān)系的子結(jié)點(diǎn)為元組。 數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù) 關(guān)系關(guān)系Rn 關(guān)系關(guān)系R1 元組元組元組元組元組

36、元組元組元組 三級(jí)粒度樹(shù)三級(jí)粒度樹(shù) T 允許多粒度樹(shù)中的每個(gè)結(jié)點(diǎn)被獨(dú)立地加鎖允許多粒度樹(shù)中的每個(gè)結(jié)點(diǎn)被獨(dú)立地加鎖 T 對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)的所有對(duì)一個(gè)結(jié)點(diǎn)加鎖意味著這個(gè)結(jié)點(diǎn)的所有后裔結(jié)點(diǎn)也被加以后裔結(jié)點(diǎn)也被加以 同樣類型的鎖同樣類型的鎖 T 在多粒度封鎖中一個(gè)數(shù)據(jù)對(duì)象可能以兩種方式封鎖：在多粒度封鎖中一個(gè)數(shù)據(jù)對(duì)象可能以兩種方式封鎖：顯式顯式 封鎖和隱式封鎖封鎖和隱式封鎖 顯式封鎖顯式封鎖: 直接加到數(shù)據(jù)對(duì)象上的封鎖直接加到數(shù)據(jù)對(duì)象上的封鎖 隱式封鎖隱式封鎖: 該數(shù)據(jù)對(duì)象沒(méi)有獨(dú)立加鎖，是由于其上級(jí)結(jié)點(diǎn)該數(shù)據(jù)對(duì)象沒(méi)有獨(dú)立加鎖，是由于其上級(jí)結(jié)點(diǎn) 加鎖而使該數(shù)據(jù)對(duì)象加上了鎖加鎖而使該數(shù)據(jù)對(duì)象加

37、上了鎖 顯式封鎖和隱式封鎖的效果是一樣的顯式封鎖和隱式封鎖的效果是一樣的 T 系統(tǒng)檢查封鎖沖突時(shí)系統(tǒng)檢查封鎖沖突時(shí) n要檢查顯式封鎖要檢查顯式封鎖 n還要檢查隱式封鎖還要檢查隱式封鎖 例如事務(wù)例如事務(wù)T要對(duì)關(guān)系要對(duì)關(guān)系R1加加X(jué)鎖鎖 系統(tǒng)必須搜索其上級(jí)結(jié)點(diǎn)數(shù)據(jù)庫(kù)、關(guān)系系統(tǒng)必須搜索其上級(jí)結(jié)點(diǎn)數(shù)據(jù)庫(kù)、關(guān)系R1 還要搜索還要搜索R1的下級(jí)結(jié)點(diǎn)，即的下級(jí)結(jié)點(diǎn)，即R1中的每一個(gè)元組中的每一個(gè)元組 如果其中某一個(gè)數(shù)據(jù)對(duì)象已經(jīng)加了不相容鎖，則如果其中某一個(gè)數(shù)據(jù)對(duì)象已經(jīng)加了不相容鎖，則T必須必須 等待等待 T 對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖，系統(tǒng)要檢查對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖，系統(tǒng)要檢查 該數(shù)據(jù)對(duì)象該數(shù)據(jù)對(duì)象 有無(wú)顯式封鎖與之

38、沖突有無(wú)顯式封鎖與之沖突 所有上級(jí)結(jié)點(diǎn)所有上級(jí)結(jié)點(diǎn) 檢查本事務(wù)的顯式封鎖是否與該數(shù)據(jù)對(duì)象上的隱式檢查本事務(wù)的顯式封鎖是否與該數(shù)據(jù)對(duì)象上的隱式 封鎖沖突：封鎖沖突：(由上級(jí)結(jié)點(diǎn)已加的封鎖造成的）由上級(jí)結(jié)點(diǎn)已加的封鎖造成的） 所有下級(jí)結(jié)點(diǎn)所有下級(jí)結(jié)點(diǎn) 看上面的顯式封鎖是否與本事務(wù)的隱式封鎖看上面的顯式封鎖是否與本事務(wù)的隱式封鎖（將加將加 到下級(jí)結(jié)點(diǎn)的封鎖到下級(jí)結(jié)點(diǎn)的封鎖）沖突沖突 引進(jìn)意向鎖（intention lock）目的 提高對(duì)某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí)系統(tǒng)的檢查效率 T 如果對(duì)一個(gè)結(jié)點(diǎn)加意向鎖，則說(shuō)明該結(jié)點(diǎn)的如果對(duì)一個(gè)結(jié)點(diǎn)加意向鎖，則說(shuō)明該結(jié)點(diǎn)的下層結(jié)點(diǎn)下層結(jié)點(diǎn)正在正在 被加鎖被加鎖 T 對(duì)任一結(jié)

39、點(diǎn)加基本鎖，必須對(duì)任一結(jié)點(diǎn)加基本鎖，必須先先對(duì)它的上層結(jié)點(diǎn)對(duì)它的上層結(jié)點(diǎn)加意向鎖加意向鎖 T 例如，對(duì)任一元組加鎖時(shí)，必須先對(duì)它所在的數(shù)據(jù)庫(kù)和關(guān)例如，對(duì)任一元組加鎖時(shí)，必須先對(duì)它所在的數(shù)據(jù)庫(kù)和關(guān) 系加意向鎖系加意向鎖 意向共享鎖意向共享鎖(Intent Share Lock，簡(jiǎn)稱，簡(jiǎn)稱IS鎖鎖) 意向排它鎖意向排它鎖(Intent Exclusive Lock，簡(jiǎn)稱，簡(jiǎn)稱IX鎖鎖) 共享意向排它鎖共享意向排它鎖(Share Intent Exclusive Lock，簡(jiǎn)稱，簡(jiǎn)稱 SIX鎖鎖) IS鎖鎖 如果對(duì)一個(gè)數(shù)據(jù)對(duì)象加如果對(duì)一個(gè)數(shù)據(jù)對(duì)象加IS鎖，表示它的后裔結(jié)點(diǎn)擬鎖，表示它的后裔結(jié)點(diǎn)擬 （意向）加（意向）加S鎖。鎖。 例如：事