第五章

事務(wù)處理、并發(fā)控制與故障恢復(fù)技術(shù)5.1事務(wù)處理35.1事務(wù)處理5.1.1事務(wù)5.1.2事務(wù)的性質(zhì)5.1.3事務(wù)活動(dòng)5.1.4有關(guān)事務(wù)的語(yǔ)句5.1.5事務(wù)的組成45.1.1事務(wù)事務(wù)（transaction）由某個(gè)用戶所執(zhí)行的一個(gè)不能被打斷的對(duì)數(shù)據(jù)庫(kù)的操作序列被稱為‘事務(wù)’‘事務(wù)’是應(yīng)用程序訪問(wèn)數(shù)據(jù)庫(kù)的基本邏輯工作單位‘事務(wù)’通常由一組對(duì)于數(shù)據(jù)庫(kù)的訪問(wèn)操作組成，在執(zhí)行過(guò)程中按照預(yù)定的次序順序執(zhí)行一個(gè)‘事務(wù)’的執(zhí)行過(guò)程是串行的，它將數(shù)據(jù)庫(kù)從一個(gè)舊的一致性狀態(tài)轉(zhuǎn)換到一個(gè)新的一致性狀態(tài)。在‘事務(wù)’的執(zhí)行過(guò)程中，數(shù)據(jù)庫(kù)中的數(shù)據(jù)可能有不一致的現(xiàn)象，但在‘事務(wù)’執(zhí)行結(jié)束時(shí)，系統(tǒng)將保證數(shù)據(jù)庫(kù)中數(shù)據(jù)的一致性55.1.1事務(wù)[例]銀行的轉(zhuǎn)帳業(yè)務(wù)：根據(jù)輸入的兩個(gè)銀行存款帳號(hào)A和B，以及轉(zhuǎn)帳金額X，將帳號(hào)A的金額減去X，帳號(hào)B的金額增加X(jué)。其處理過(guò)程如下(其中READ(A)表示將帳號(hào)A的金額讀入內(nèi)存變量A，WRITE(A)表示將內(nèi)存變量A的值作為帳號(hào)A的金額寫入數(shù)據(jù)庫(kù))：READ(A);IF(A>=X)THENBEGINA:=A–X;WRITE(A);READ(B);B:=B+X;WRITE(B);END

該事務(wù)的DB訪問(wèn)操作為：READ(A);WRITE(A);READ(B);WRITE(B);對(duì)該事務(wù)而言，數(shù)據(jù)庫(kù)中數(shù)據(jù)的一致性就是指：帳號(hào)A和帳號(hào)B的總金額之和不變65.1.2事務(wù)的性質(zhì)

事務(wù)具有四個(gè)特性，簡(jiǎn)稱為事務(wù)的ACID

特性，也被稱為事務(wù)的執(zhí)行過(guò)程必須滿足的四條準(zhǔn)則原子性（Atomicity）一致性（Consistency）隔離性（Isolation）持久性（Durability）75.1.2事務(wù)的性質(zhì)原子性（Atomicity）在一個(gè)事務(wù)中，所有的數(shù)據(jù)庫(kù)訪問(wèn)操作構(gòu)成一個(gè)不可分割的操作序列，這些操作要么全部執(zhí)行結(jié)束，要么一個(gè)都不要執(zhí)行。(例：銀行轉(zhuǎn)帳）數(shù)據(jù)庫(kù)管理系統(tǒng)會(huì)自動(dòng)維護(hù)用戶事務(wù)執(zhí)行的原子性事務(wù)管理子系統(tǒng)事務(wù)日志85.1.2事務(wù)的性質(zhì)2．一致性（Consistency）一個(gè)事務(wù)的成功執(zhí)行總是將數(shù)據(jù)庫(kù)從一個(gè)一致的狀態(tài)轉(zhuǎn)換到另一個(gè)一致的狀態(tài)數(shù)據(jù)庫(kù)的‘狀態(tài)’：指數(shù)據(jù)庫(kù)中所有數(shù)據(jù)對(duì)象的當(dāng)前取值情況數(shù)據(jù)庫(kù)的一致的狀態(tài)可以理解為數(shù)據(jù)庫(kù)中所有數(shù)據(jù)的正確性，它要求數(shù)據(jù)庫(kù)中的數(shù)據(jù)必須滿足：在數(shù)據(jù)庫(kù)中顯式定義的各種完整性約束用戶心目中的隱式數(shù)據(jù)約束95.1.2事務(wù)的性質(zhì)2．一致性（續(xù)）事務(wù)執(zhí)行的‘一致性’原則基于這樣一個(gè)假設(shè)：在一個(gè)事務(wù)開(kāi)始執(zhí)行之前數(shù)據(jù)庫(kù)處于一個(gè)一致的狀態(tài)，如果沒(méi)有‘其它事務(wù)的干擾和系統(tǒng)故障’，那么當(dāng)該事務(wù)執(zhí)行結(jié)束時(shí)數(shù)據(jù)庫(kù)仍然處于一致的狀態(tài)事務(wù)的‘一致性’特性由兩方面完成DBMS中的‘?dāng)?shù)據(jù)完整性保護(hù)’子系統(tǒng)編寫事務(wù)的應(yīng)用程序員105.1.2事務(wù)的性質(zhì)3．隔離性（Isolation）一個(gè)事務(wù)的執(zhí)行與并發(fā)執(zhí)行的其它事務(wù)之間是相互獨(dú)立的，互不干擾，這被稱為事務(wù)執(zhí)行的‘隔離性’事務(wù)執(zhí)行的‘隔離性’要求：多個(gè)事務(wù)并發(fā)執(zhí)行的最終結(jié)果，應(yīng)該與它們的某種串行執(zhí)行的最終結(jié)果相等，這被稱為并發(fā)事務(wù)的可串行化115.1.2事務(wù)的性質(zhì)3．隔離性（續(xù)）事務(wù)執(zhí)行的‘隔離性’是由DBMS的并發(fā)控制子系統(tǒng)來(lái)實(shí)現(xiàn)的。在數(shù)據(jù)庫(kù)系統(tǒng)中，當(dāng)多個(gè)事務(wù)并發(fā)執(zhí)行時(shí)，每個(gè)事務(wù)都可以看成只有自己在執(zhí)行，只有當(dāng)它與其它事務(wù)發(fā)生封鎖沖突時(shí)，才會(huì)感覺(jué)到其它事務(wù)的存在例如：12306聯(lián)網(wǎng)售票系統(tǒng)125.1.2事務(wù)的性質(zhì)4．持久性（Durability）一個(gè)事務(wù)一旦完成其全部操作后，它對(duì)數(shù)據(jù)庫(kù)的所有更新應(yīng)永久地反映在數(shù)據(jù)庫(kù)中，即使以后系統(tǒng)發(fā)生故障也應(yīng)該能夠通過(guò)故障恢復(fù)來(lái)保留這個(gè)事務(wù)的執(zhí)行結(jié)果事務(wù)的‘持久性’是由DBMS的恢復(fù)管理子系統(tǒng)實(shí)現(xiàn)的數(shù)據(jù)庫(kù)管理系統(tǒng)通過(guò)其‘事務(wù)管理’子系統(tǒng)（含‘并發(fā)控制’子系統(tǒng)）、‘恢復(fù)管理’子系統(tǒng)、‘?dāng)?shù)據(jù)完整性保護(hù)’子系統(tǒng)來(lái)實(shí)現(xiàn)事務(wù)的原子性(A)、一致性(C)、隔離性(I)和持久性(D)135.1.3事務(wù)活動(dòng)事務(wù)開(kāi)始事務(wù)執(zhí)行正常結(jié)束提交Read/Write回滾非正常結(jié)束圖5.1

事務(wù)活動(dòng)過(guò)程圖145.1.3事務(wù)活動(dòng)為了精確地描述一個(gè)事務(wù)的工作過(guò)程，我們建立了一個(gè)抽象的事務(wù)模型，以表示事務(wù)的狀態(tài)變遷情況Read/Write

活

動(dòng)

Begin

失

敗

Abort

Abort

提

交

Commit

異常中止

Rollback

事務(wù)執(zhí)行結(jié)束

重新啟動(dòng)該事務(wù)事務(wù)的狀態(tài)變遷圖預(yù)

提

交

End

155.1.3事務(wù)活動(dòng)‘活動(dòng)’狀態(tài)事務(wù)在開(kāi)始執(zhí)行后，立即進(jìn)入’活動(dòng)’狀態(tài)。在’活動(dòng)’狀態(tài)中，事務(wù)將執(zhí)行對(duì)數(shù)據(jù)庫(kù)的訪問(wèn)操作在DBMS的事務(wù)管理子系統(tǒng)看來(lái)，用戶事務(wù)對(duì)數(shù)據(jù)庫(kù)的訪問(wèn)操作就是對(duì)數(shù)據(jù)庫(kù)中數(shù)據(jù)的讀/寫操作165.1.3事務(wù)活動(dòng)(cont.)‘讀’操作將數(shù)據(jù)讀入用戶事務(wù)的私有工作區(qū)間如果該數(shù)據(jù)當(dāng)前不在DBMS的系統(tǒng)緩沖區(qū)中，那么DBMS首先將該數(shù)據(jù)從磁盤讀入系統(tǒng)緩沖區(qū)，然后再將其拷貝到用戶事務(wù)的私有工作區(qū)‘寫’操作將修改后的數(shù)據(jù)‘寫入’數(shù)據(jù)庫(kù)這里的‘寫’操作并不是立即將數(shù)據(jù)永久性地寫入磁盤，很可能暫時(shí)存放在DBMS的系統(tǒng)緩沖區(qū)中175.1.3事務(wù)活動(dòng)‘預(yù)提交’狀態(tài)當(dāng)事務(wù)的最后一條訪問(wèn)語(yǔ)句執(zhí)行結(jié)束之后，事務(wù)進(jìn)入‘預(yù)提交’狀態(tài)。此時(shí)事務(wù)對(duì)于數(shù)據(jù)庫(kù)的訪問(wèn)操作雖然已經(jīng)執(zhí)行結(jié)束，但其對(duì)于數(shù)據(jù)的修改結(jié)果可能還在內(nèi)存的系統(tǒng)緩沖區(qū)中，必須將其真正寫入數(shù)據(jù)庫(kù)的磁盤185.1.3事務(wù)活動(dòng)(cont.)事務(wù)在‘預(yù)提交’階段，必須確保將當(dāng)前事務(wù)的所有修改操作的執(zhí)行結(jié)果被真正寫入到數(shù)據(jù)庫(kù)的磁盤中去在所有‘寫’磁盤操作執(zhí)行結(jié)束后，事務(wù)就進(jìn)入‘提交’狀態(tài)在‘預(yù)提交’階段，雖然事務(wù)本身的操作命令已經(jīng)執(zhí)行結(jié)束，但是在寫磁盤的過(guò)程中仍然會(huì)發(fā)生系統(tǒng)故障，從而導(dǎo)致當(dāng)前事務(wù)的執(zhí)行失敗在‘預(yù)提交’失敗后，當(dāng)前事務(wù)也將被放棄(abort)，事務(wù)轉(zhuǎn)而進(jìn)入‘失敗’狀態(tài)195.1.3事務(wù)活動(dòng)‘失敗’狀態(tài)處于’活動(dòng)’狀態(tài)的事務(wù)在順利到達(dá)并執(zhí)行完最后一條語(yǔ)句之前就中止執(zhí)行，或者在’預(yù)提交’狀態(tài)下因發(fā)生系統(tǒng)故障而中止執(zhí)行時(shí)，我們稱事務(wù)進(jìn)入’失敗’狀態(tài)事務(wù)從’活動(dòng)’狀態(tài)轉(zhuǎn)變?yōu)椤　癄顟B(tài)的原因應(yīng)用程序(或用戶)主動(dòng)放棄(abort)當(dāng)前事務(wù)因并發(fā)控制的原因而被放棄的事務(wù)，如：封鎖申請(qǐng)的超時(shí)等待死鎖發(fā)生系統(tǒng)故障事務(wù)從’預(yù)提交’狀態(tài)轉(zhuǎn)變?yōu)椤　癄顟B(tài)的原因發(fā)生系統(tǒng)故障205.1.3事務(wù)活動(dòng)‘異常中止’狀態(tài)處于’失敗’狀態(tài)的事務(wù)，很可能已對(duì)磁盤中的數(shù)據(jù)進(jìn)行了一部分修改。為了保證事務(wù)的原子性，系統(tǒng)應(yīng)該撤消(undo操作)該事務(wù)對(duì)數(shù)據(jù)庫(kù)已作的修改。在撤消操作完成以后，事務(wù)將被打上一個(gè)放棄的標(biāo)志(aborted)，轉(zhuǎn)而進(jìn)入’異常中止’狀態(tài)回退(rollback)對(duì)事務(wù)的撤消操作也稱為事務(wù)的’回退’或’回滾’事務(wù)的’回退’由DBMS的’恢復(fù)子系統(tǒng)’實(shí)現(xiàn)在事務(wù)進(jìn)入’異常中止’狀態(tài)后，系統(tǒng)有兩種選擇：作為一個(gè)新的事務(wù)，重新啟動(dòng)取消事務(wù)215.1.3事務(wù)活動(dòng)‘提交’狀態(tài)事務(wù)進(jìn)入’預(yù)提交’狀態(tài)后，’并發(fā)控制子系統(tǒng)’將檢查該事務(wù)與并發(fā)執(zhí)行的其它事務(wù)之間是否發(fā)生干擾現(xiàn)象在檢查通過(guò)以后，系統(tǒng)執(zhí)行提交(commit)操作，把對(duì)數(shù)據(jù)庫(kù)的修改全部寫到磁盤上，并通知系統(tǒng)，事務(wù)已成功地結(jié)束為事務(wù)打上一個(gè)提交標(biāo)志(committed)，事務(wù)就進(jìn)入‘提交’狀態(tài)不論是‘提交’狀態(tài)，還是‘異常中止’狀態(tài)，都意味著一個(gè)事務(wù)的執(zhí)行結(jié)束225.1.4有關(guān)事務(wù)的語(yǔ)句‘事務(wù)’除了由一組對(duì)于數(shù)據(jù)庫(kù)的訪問(wèn)操作構(gòu)成以外，通常還應(yīng)該包括少量的事務(wù)控制語(yǔ)句，用于定義一個(gè)事務(wù)的開(kāi)始和結(jié)束(包括正常結(jié)束和非正常結(jié)束)。因此，與事務(wù)有關(guān)的控制語(yǔ)句主要有三條：事務(wù)的開(kāi)始(begintransaction)事務(wù)的結(jié)束正常結(jié)束提交事務(wù)(committransaction)非正常結(jié)束回退事務(wù)(rollbacktransaction)235.1.4有關(guān)事務(wù)的語(yǔ)句Begintransaction現(xiàn)有的關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)并沒(méi)有提供一個(gè)用于定義從什么時(shí)候開(kāi)始一個(gè)事務(wù)的控制語(yǔ)句，事務(wù)的啟動(dòng)是隱式的可以通過(guò)三種方式來(lái)啟動(dòng)一個(gè)新的事務(wù)：數(shù)據(jù)定義命令(DDL)將系統(tǒng)設(shè)為自動(dòng)提交方式（打開(kāi)自動(dòng)提交標(biāo)志）數(shù)據(jù)操縱命令(DML)245.1.4有關(guān)事務(wù)的語(yǔ)句事務(wù)的啟動(dòng)方式數(shù)據(jù)定義命令(DDL)每一條數(shù)據(jù)定義命令都將被作為一個(gè)單獨(dú)的事務(wù)來(lái)執(zhí)行在此之前的用戶事務(wù)將被提動(dòng)提交將系統(tǒng)設(shè)為自動(dòng)提交方式（打開(kāi)自動(dòng)提交標(biāo)志）每一條數(shù)據(jù)庫(kù)訪問(wèn)命令都將被作為一個(gè)單獨(dú)的事務(wù)來(lái)執(zhí)行，并根據(jù)執(zhí)行結(jié)果自動(dòng)提交或回退數(shù)據(jù)操縱命令(DML)在當(dāng)前用戶的前一個(gè)事務(wù)執(zhí)行結(jié)束之后，在用戶提交的下一條數(shù)據(jù)庫(kù)訪問(wèn)操作之前，數(shù)據(jù)庫(kù)管理系統(tǒng)將自動(dòng)啟動(dòng)一個(gè)新的事務(wù)255.1.4有關(guān)事務(wù)的語(yǔ)句Committransaction提交當(dāng)前事務(wù)，事務(wù)在執(zhí)行過(guò)程中對(duì)于數(shù)據(jù)庫(kù)的所有修改操作都將永久地反應(yīng)到數(shù)據(jù)庫(kù)中，并且不可被取消事務(wù)的提交操作也可能失敗，其原因包括：發(fā)生系統(tǒng)故障在提交階段執(zhí)行的數(shù)據(jù)完整性檢查在事務(wù)提交失敗后，用戶可以通過(guò)回退(Rollback)操作來(lái)取消當(dāng)前事務(wù)由系統(tǒng)自動(dòng)提交的事務(wù)，如果提交失敗，系統(tǒng)將自動(dòng)執(zhí)行事務(wù)的回退操作265.1.4有關(guān)事務(wù)的語(yǔ)句Rollbacktransaction取消在該事務(wù)執(zhí)行過(guò)程中的所有操作，回滾該事務(wù)至事務(wù)的起點(diǎn)，以便重新執(zhí)行或放棄（abort）該事務(wù)檢查點(diǎn)(savepoint)在事務(wù)的執(zhí)行過(guò)程中，系統(tǒng)可以為該事務(wù)設(shè)置若干個(gè)檢查點(diǎn)用戶事務(wù)可以使用Rollback命令將當(dāng)前事務(wù)回退到前面的某個(gè)檢查點(diǎn)sp，放棄“在檢查點(diǎn)sp之后，回退操作之前”執(zhí)行的對(duì)數(shù)據(jù)庫(kù)的所有訪問(wèn)操作，并繼續(xù)執(zhí)行當(dāng)前事務(wù)不帶檢查點(diǎn)的回退操作將結(jié)束并放棄整個(gè)事務(wù)275.1.4有關(guān)事務(wù)的語(yǔ)句除了上述三條事務(wù)控制語(yǔ)句外，數(shù)據(jù)庫(kù)管理系統(tǒng)通常還會(huì)提供下述幾條與事務(wù)有關(guān)的控制命令(DCL)設(shè)置事務(wù)的自動(dòng)提交命令SETAUTOCOMMITON|OFF設(shè)置事務(wù)的類型SETTRANSACTIONREADONLY|READWRITE設(shè)置事務(wù)的隔離級(jí)別SETTRANSACTIONISOLATIONLEVEL READUNCOMMITTED|READCOMMITTED| READREPEATABLE|SERIALIZABLE285.1.4有關(guān)事務(wù)的語(yǔ)句SETTRANSACTIONREADONLY|READWRITE定義在這之后啟動(dòng)的所有事務(wù)在執(zhí)行過(guò)程中對(duì)數(shù)據(jù)庫(kù)的訪問(wèn)方式READONLY：只讀型事務(wù)在事務(wù)的運(yùn)行過(guò)程中只能執(zhí)行對(duì)數(shù)據(jù)庫(kù)的‘讀’操作，而不能執(zhí)行‘更新’類型的操作直到定義新的事務(wù)類型READWRITE：讀/寫型事務(wù)在事務(wù)的運(yùn)行過(guò)程中可以執(zhí)行對(duì)數(shù)據(jù)庫(kù)的‘讀/寫’操作這是事務(wù)的缺省類型定義295.1.4有關(guān)事務(wù)的語(yǔ)句SETTRANSACTIONISOLATIONLEVEL READUNCOMMITTED|READCOMMITTED| READREPEATABLE|SERIALIZABLE定義當(dāng)前用戶的事務(wù)與其它并發(fā)執(zhí)行事務(wù)之間的隔離級(jí)別事務(wù)的隔離級(jí)別與所采用的封鎖策略緊密相關(guān)。選擇不同的隔離級(jí)別，系統(tǒng)所采用的封鎖策略則不同有四種不同的隔離級(jí)別可供選擇305.1.4有關(guān)事務(wù)的語(yǔ)句READUNCOMMITTED：未提交讀在該方式下，當(dāng)前事務(wù)不需要申請(qǐng)任何類型的封鎖，因而可能會(huì)‘讀’到未提交的修改結(jié)果禁止一個(gè)事務(wù)以該方式去執(zhí)行對(duì)數(shù)據(jù)的‘寫’操作，以避免與其它并發(fā)事務(wù)的‘寫’沖突現(xiàn)象READCOMMITTED：提交讀在‘讀’數(shù)據(jù)對(duì)象A之前需要先申請(qǐng)對(duì)數(shù)據(jù)對(duì)象A的‘共享性’封鎖，在‘讀’操作執(zhí)行結(jié)束之后立即釋放該封鎖以避免讀取到其它并發(fā)事務(wù)未提交的修改結(jié)果315.1.4有關(guān)事務(wù)的語(yǔ)句READREPEATABLE：可重復(fù)讀在‘讀’數(shù)據(jù)對(duì)象A之前需要先申請(qǐng)對(duì)數(shù)據(jù)對(duì)象A的‘共享性’封鎖，并將該封鎖維持到當(dāng)前事務(wù)的結(jié)束可以避免其它的并發(fā)事務(wù)對(duì)當(dāng)前事務(wù)正在使用的數(shù)據(jù)對(duì)象的修改SERIALIZABLE：可序列化(可串行化)并發(fā)事務(wù)以一種可串行化的調(diào)度策略實(shí)現(xiàn)其并發(fā)執(zhí)行，以避免它們相互之間的干擾現(xiàn)象325.1.4有關(guān)事務(wù)的語(yǔ)句不管采用何種隔離級(jí)別，在事務(wù)‘寫’數(shù)據(jù)對(duì)象A之前需要先申請(qǐng)對(duì)數(shù)據(jù)對(duì)象A的‘排它性’封鎖，并將該封鎖維持到當(dāng)前事務(wù)的結(jié)束。（事務(wù)的隔離級(jí)別與封鎖策略之間的關(guān)系）33三種數(shù)據(jù)不一致現(xiàn)象在事務(wù)的并發(fā)執(zhí)行過(guò)程中，如果采用了不合理的調(diào)度方法，就會(huì)出現(xiàn)并發(fā)執(zhí)行錯(cuò)誤，破壞數(shù)據(jù)庫(kù)中數(shù)據(jù)的一致性常見(jiàn)的并發(fā)執(zhí)行錯(cuò)誤有三種：丟失修改（lostupdata）臟讀（dirtyread）不可重復(fù)讀（non-repeatableread）34例：飛機(jī)售票業(yè)務(wù)假設(shè)某個(gè)航班的剩余機(jī)票的張數(shù)保存在數(shù)據(jù)庫(kù)對(duì)象X（初始值為5）中，則出售一張?jiān)摵桨鄼C(jī)票的事務(wù)的執(zhí)行流程是：Read(X,t); /*t是該事務(wù)使用的內(nèi)存變量*/t:=t–1;Write(X,t);35丟失修改現(xiàn)象：一個(gè)事務(wù)的修改結(jié)果破壞了另一個(gè)事務(wù)的修改結(jié)果原因：對(duì)多個(gè)事務(wù)并發(fā)修改同一個(gè)數(shù)據(jù)對(duì)象的情況未加控制步驟甲售票點(diǎn)變量t1乙售票點(diǎn)變量t2剩余機(jī)票X1Read(X,t1);552t1:=t1–1;43Read(X,t2);54t2:=t2–1;45Write(X,t1);46Write(X,t2);436臟讀現(xiàn)象：讀到了錯(cuò)誤的數(shù)據(jù)(即與數(shù)據(jù)庫(kù)中的情況不相符的數(shù)據(jù))原因：一個(gè)事務(wù)讀取了另一個(gè)事務(wù)未提交的修改結(jié)果步驟甲售票點(diǎn)變量t1乙售票點(diǎn)變量t2剩余機(jī)票X1Read(X,t1);552t1:=t1–1;43Write(X,t1);444Read(X,t2);45放棄當(dāng)前的售票操作，取消對(duì)X的修改537不可重復(fù)讀現(xiàn)象： 在一個(gè)事務(wù)的執(zhí)行過(guò)程中，前后兩次讀同一個(gè)數(shù)據(jù)對(duì)象所獲得的值出現(xiàn)了不一致原因： 在兩次’讀’操作之間插入了另一個(gè)事務(wù)的’寫’操作步驟甲售票點(diǎn)變量t1乙售票點(diǎn)變量t2剩余機(jī)票X1Read(X,t1);552Read(X,t2);53t2:=t2–1;44Write(X,t2);445Read(X,t1);4Example10.3.3BlindWritesT1:W1(A,50);W1(B,50);C1;T2:W2(A,80);W2(B,20);C2;H3:W1(A,50);W2(A,80);W2(B,20);W1(B,50);C1;C2;scheduleH3T1&T2T2&T1valueofA808050valueofB502050隔離級(jí)別及對(duì)應(yīng)的可能或不可能出現(xiàn)的現(xiàn)象更新丟失臟讀不可重復(fù)讀幻像（phantomread）同一查詢?cè)谕皇聞?wù)中多次進(jìn)行，由于其他提交事務(wù)所做的插入操作，每次返回不同的結(jié)果集，此時(shí)發(fā)生幻像讀39DirtyreadNon-repeatablereadPhantomreadReadmittedPossiblePossiblePossibleReadcommittedNotpossiblePossiblePossibleRepeatablereadNotpossibleNotpossiblePossibleSerializableNotpossibleNotpossibleNotpossible405.1.5事務(wù)的組成數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象的大小可以是一個(gè)屬性值、一個(gè)元組、一張表（元組的集合）或整個(gè)數(shù)據(jù)庫(kù)，也可以是一個(gè)磁盤塊在這里我們并不嚴(yán)格區(qū)分它們，而是簡(jiǎn)單稱其為‘?dāng)?shù)據(jù)對(duì)象A’，或簡(jiǎn)稱‘?dāng)?shù)據(jù)A’415.1.5事務(wù)的組成(cont.)數(shù)據(jù)對(duì)象的地址空間在用戶事務(wù)與數(shù)據(jù)庫(kù)進(jìn)行數(shù)據(jù)交換時(shí)，存在三種與數(shù)據(jù)有關(guān)的地址空間概念：保存這些數(shù)據(jù)對(duì)象的磁盤空間數(shù)據(jù)庫(kù)管理系統(tǒng)所使用的內(nèi)存緩沖區(qū)事務(wù)的局部地址空間(內(nèi)存變量)同一個(gè)數(shù)據(jù)對(duì)象在不同的地方可能具有不同的值425.1.5事務(wù)的組成操作1)事務(wù)控制2)數(shù)據(jù)訪問(wèn)1)事務(wù)控制操作事務(wù)的開(kāi)始：STARTT0提交事務(wù)：COMMITT0回退(放棄)事物：ABORTT0435.1.5事務(wù)的組成2)數(shù)據(jù)訪問(wèn)操作INPUT(A)：將數(shù)據(jù)對(duì)象A的值從磁盤中讀入內(nèi)存緩沖區(qū)OUTPUT(A)：將內(nèi)存緩沖區(qū)中數(shù)據(jù)對(duì)象A的值寫入磁盤READ(A,t)：將內(nèi)存緩沖區(qū)中數(shù)據(jù)對(duì)象A的值讀入內(nèi)存變量t在一個(gè)READ操作中，有可能隱含著一個(gè)INPUT操作WRITE(A,t)：將內(nèi)存變量t的值寫入內(nèi)存緩沖區(qū)中數(shù)據(jù)對(duì)象A44[例]轉(zhuǎn)帳事務(wù)(A=10000,B=20000,轉(zhuǎn)帳金額5000)5.1.5事務(wù)的組成READ(A,t);t:=t–5000;WRITE(A,t);READ(B,t);t:=t+5000;WRITE(B,t);COMMITT1;用戶事務(wù)STARTT1;READ(A,t);t:=t–5000;WRITE(A,t);READ(B,t);t:=t+5000;WRITE(B,t);OUTPUT(A);OUTPUT(B);COMMITT1;數(shù)據(jù)庫(kù)日志45[例]轉(zhuǎn)帳事務(wù)(A=10000,B=20000,轉(zhuǎn)帳金額5000)STARTT1;READ(A,t);WRITE(A,t);READ(B,t);WRITE(B,t);OUTPUT(A);OUTPUT(B);COMMITT1;5.1.5事務(wù)的組成事務(wù)的開(kāi)始語(yǔ)句，由數(shù)據(jù)庫(kù)管理系統(tǒng)自動(dòng)加入各自隱含一個(gè)INPUT操作將修改結(jié)果寫入數(shù)據(jù)庫(kù)緩沖進(jìn)入預(yù)提交狀態(tài)，將修改結(jié)果從數(shù)據(jù)庫(kù)緩沖寫入磁盤寫磁盤結(jié)束，提交當(dāng)前事務(wù)第五章事務(wù)處理、并發(fā)控制與故障恢復(fù)技術(shù)5.2并發(fā)控制技術(shù)475.2并發(fā)控制技術(shù)5.2.1事務(wù)的并發(fā)執(zhí)行5.2.2封鎖5.2.3封鎖協(xié)議5.2.4兩階段封鎖協(xié)議5.2.5封鎖粒度5.2.6活鎖與死鎖485.2.1事務(wù)的并發(fā)執(zhí)行并發(fā)性數(shù)據(jù)庫(kù)是一個(gè)多用戶共享系統(tǒng)每個(gè)用戶（或用戶程序）都是以‘事務(wù)’為單位訪問(wèn)數(shù)據(jù)庫(kù)用于實(shí)現(xiàn)多個(gè)用戶事務(wù)的并發(fā)執(zhí)行的技術(shù)被稱為并發(fā)控制(ConcurrentControl)技術(shù)495.2.1事務(wù)的并發(fā)執(zhí)行多個(gè)事務(wù)的執(zhí)行方式串行執(zhí)行以事務(wù)為單位，多個(gè)事務(wù)依次順序執(zhí)行前一個(gè)事務(wù)對(duì)數(shù)據(jù)庫(kù)的訪問(wèn)操作執(zhí)行結(jié)束后，再去處理下一個(gè)事務(wù)對(duì)數(shù)據(jù)庫(kù)的訪問(wèn)操作并發(fā)執(zhí)行按一定調(diào)度策略交替執(zhí)行并發(fā)執(zhí)行的可串行化(Serializability)如果一組事務(wù)并發(fā)執(zhí)行的結(jié)果等價(jià)于它們之間的某種串行執(zhí)行的結(jié)果，則稱其為可串行化調(diào)度并發(fā)控制的目標(biāo)：實(shí)現(xiàn)并發(fā)事務(wù)的可串行化調(diào)度505.2.1事務(wù)的并發(fā)執(zhí)行515.2.1事務(wù)的并發(fā)執(zhí)行幾個(gè)概念調(diào)度(historyorschedule)串行調(diào)度(serialschedule)可串行化調(diào)度(SerializabilitySchedule)事務(wù)及其調(diào)度的表示方法沖突可串行化沖突(Conflict)優(yōu)先圖沖突可串行性判斷525.2.1事務(wù)的并發(fā)執(zhí)行調(diào)度一個(gè)或多個(gè)事務(wù)中的數(shù)據(jù)庫(kù)訪問(wèn)操作，按照這些操作被執(zhí)行的時(shí)間排序所形成的一個(gè)操作序列535.2.1事務(wù)的并發(fā)執(zhí)行數(shù)據(jù)庫(kù)訪問(wèn)操作用戶事務(wù)對(duì)于數(shù)據(jù)庫(kù)的訪問(wèn)操作包括READ和WRITE，這是事務(wù)對(duì)數(shù)據(jù)庫(kù)緩沖區(qū)中的數(shù)據(jù)的‘讀’和‘寫’操作。(在這里我們忽略了對(duì)于磁盤的INPUT和OUTPUT操作)駐留在內(nèi)存緩沖區(qū)中的同一個(gè)數(shù)據(jù)對(duì)象A，有可能同時(shí)被若干個(gè)事務(wù)‘讀’或‘寫’。我們?cè)诳紤]一個(gè)‘調(diào)度’時(shí)，最關(guān)心的是這一組事務(wù)以一種什么樣的順序來(lái)‘讀/寫’內(nèi)存緩沖區(qū)中的數(shù)據(jù)同一個(gè)事務(wù)的一組‘讀/寫’操作在‘調(diào)度’中的執(zhí)行順序是固定不變的，但是并發(fā)事務(wù)的不同交叉執(zhí)行方式就構(gòu)成了不同的‘調(diào)度’545.2.1事務(wù)的并發(fā)執(zhí)行串行調(diào)度如果一個(gè)調(diào)度的操作組成方式如下：首先是一個(gè)事務(wù)的所有操作，然后是另一個(gè)事務(wù)的所有操作，依此類推，則我們稱該調(diào)度是串行的，或稱為‘串行調(diào)度’每一個(gè)事務(wù)中的所有操作，都是按照其預(yù)定的順序依次執(zhí)行的555.2.1事務(wù)的并發(fā)執(zhí)行串行調(diào)度任何一個(gè)串行調(diào)度均具有以下性質(zhì)在該調(diào)度中任意取兩個(gè)事務(wù)X和Y，如果X的某個(gè)操作在Y的某個(gè)操作之前，則X的所有操作都在Y的所有操作之前不存在不同事務(wù)之間的交叉執(zhí)行現(xiàn)象并發(fā)事務(wù)的串行調(diào)度執(zhí)行方式不會(huì)破壞數(shù)據(jù)庫(kù)狀態(tài)的一致性56調(diào)度2：T2，T1

（圖3）5.2.1事務(wù)的并發(fā)執(zhí)行例1：銀行轉(zhuǎn)賬事務(wù)T1：從賬號(hào)A轉(zhuǎn)10000至賬號(hào)B事務(wù)T2

：從賬號(hào)A轉(zhuǎn)10%的款項(xiàng)至賬號(hào)B設(shè)帳號(hào)A與帳號(hào)B的初值都是20000，數(shù)據(jù)庫(kù)狀態(tài)的一致性要求是：A+B=40000事務(wù)T1與事務(wù)T2的串行調(diào)度如下：調(diào)度1：T1，T2

（圖2）在調(diào)度1或調(diào)度2執(zhí)行結(jié)束后，數(shù)據(jù)庫(kù)的狀態(tài)是不同的，但都滿足狀態(tài)的一致性要求57調(diào)度1（初值：A=B=20000）圖2串行執(zhí)行之一(結(jié)果：A=9000,B=31000)T1T2TempAB1Read(A)20000200002A:=A-100003Write(A)100004Read(B)5B:=B6Write(B)300007Read(A)8Temp:=A*0.110009A:=A-Temp10Write(A)900011Read(B)12B:=B+Temp13Write(B)3100058調(diào)度2（初值：A=B=20000）T1T2TempAB1Read(A)20000200002Temp:=A*0.120003A:=A-Temp4Write(A)180005Read(B)6B:=B+Temp7Write(B)220008Read(A)9A:=A-1000010Write(A)800011Read(B)12B:=B13Write(B)32000圖3串行執(zhí)行之二(結(jié)果：A=8000,B=32000)595.2.1事務(wù)的并發(fā)執(zhí)行可串行化調(diào)度每個(gè)串行調(diào)度都將保持?jǐn)?shù)據(jù)庫(kù)狀態(tài)的一致性。但也存在其它的調(diào)度（非串行調(diào)度）能夠保證數(shù)據(jù)庫(kù)狀態(tài)的一致性如果一個(gè)調(diào)度對(duì)數(shù)據(jù)庫(kù)狀態(tài)的影響和某個(gè)串行調(diào)度相同，則我們稱該調(diào)度是可串行化的，或稱為‘可串行化調(diào)度’605.2.1事務(wù)的并發(fā)執(zhí)行調(diào)度4（圖5）：不正確的并發(fā)調(diào)度并發(fā)調(diào)度的例子：調(diào)度3（圖4）：并發(fā)事務(wù)的可串行化調(diào)度從最后的執(zhí)行結(jié)果上來(lái)看調(diào)度3等價(jià)于串行調(diào)度1，因而是一個(gè)可串行化調(diào)度調(diào)度4與調(diào)度1和調(diào)度2都不等價(jià)，因而是一個(gè)不正確的并發(fā)調(diào)度61調(diào)度3（初值：A=B=20000）T1T2xyTempAB1Read(A,x)20000-20000200002x:=x-10000100003Write(A,x)100004Read(A,y)100005Temp:=y*0.110006y:=y-Temp90007Write(A,y)90008Read(B,x)200009x:=x3000010Write(B,x)3000011Read(B,y)3000012y:=y+Temp3100013Write(B,y)31000圖4并發(fā)執(zhí)行可串行化(結(jié)果：A=9000,B=31000)62調(diào)度4（初值：A=B=20000）T1T2xyTempAB1Read(A,x)20000-20000200002x:=x-10000100003Read(A,y)200004Temp:=y*0.120005y:=y-Temp180006Write(A,y)180007Read(B,y)200008Write(A,x)100009Read(B,x)2000010x:=x3000011Write(B,x)3000012y:=y+Temp2200013Write(B,y)22000圖5不正確的并發(fā)執(zhí)行(結(jié)果：A=10000,B=22000)635.2.1事務(wù)的并發(fā)執(zhí)行事務(wù)及調(diào)度的表示方法在事務(wù)的執(zhí)行過(guò)程中，我們只關(guān)心它對(duì)數(shù)據(jù)庫(kù)中的哪些數(shù)據(jù)對(duì)象進(jìn)行了讀/寫操作，并不在意每次讀/寫的值是多少，也不關(guān)心在用戶事務(wù)中對(duì)這些數(shù)據(jù)對(duì)象的值做了怎樣的處理另外，如果兩個(gè)事務(wù)對(duì)同一個(gè)數(shù)據(jù)對(duì)象進(jìn)行‘寫’操作，則我們認(rèn)為它們‘寫’后的值總是不相等的事務(wù)及調(diào)度的記法事務(wù)用符號(hào)T1,T2,…

表示用ri(X)表示事務(wù)Ti讀數(shù)據(jù)庫(kù)對(duì)象X用wi(X)表示事務(wù)Ti寫數(shù)據(jù)庫(kù)對(duì)象X645.2.1事務(wù)的并發(fā)執(zhí)行事務(wù)及調(diào)度的表示方法（續(xù)）例1中的兩個(gè)事務(wù)可以分別表示為：事務(wù)T1：r1(A);w1(A);r1(B);w1(B);事務(wù)T2：r2(A);w2(A);r2(B);w2(B);調(diào)度1(圖2)可以表示為：r1(A);w1(A);r1(B);w1(B);r2(A);w2(A);r2(B);w2(B);該串行調(diào)度可以簡(jiǎn)化表示為：T1,T2調(diào)度2(圖3)可以表示為：r2(A);w2(A);r2(B);w2(B);r1(A);w1(A);r1(B);w1(B);該串行調(diào)度可以簡(jiǎn)化表示為：T2,T1655.2.1事務(wù)的并發(fā)執(zhí)行事務(wù)及調(diào)度的表示方法（續(xù)）事務(wù)T1：r1(A);w1(A);r1(B);w1(B);事務(wù)T2：r2(A);w2(A);r2(B);w2(B);調(diào)度3(圖4)可以表示為：r1(A);w1(A);r2(A);w2(A);r1(B);w1(B);r2(B);w2(B);調(diào)度4(圖5)可以表示為：r1(A);r2(A);w2(A);r2(B);w1(A);r1(B);w1(B);w2(B);66T1T2xyTempAB1Read(A,x)20000-20000200002x:=x-10000100003Write(A,x)100004Read(A,y)100005Temp:=y*0.110006y:=y-Temp90007Write(A,y)90008Read(B,x)200009x:=x3000010Write(B,x)3000011Read(B,y)3000012y:=y+Temp3100013Write(B,y)31000調(diào)度3(圖4)可以表示為：r1(A);w1(A);r2(A);w2(A);r1(B);w1(B);r2(B);w2(B);67T1T2xyTempAB1Read(A,x)20000-20000200002x:=x-10000100003Read(A,y)200004Temp:=y*0.120005y:=y-Temp180006Write(A,y)180007Read(B,y)200008Write(A,x)100009Read(B,x)2000010x:=x3000011Write(B,x)3000012y:=y+Temp2200013Write(B,y)22000調(diào)度4(圖5)可以表示為：r1(A);r2(A);w2(A);r2(B);w1(A);r1(B);w1(B);w2(B);685.2.1事務(wù)的并發(fā)執(zhí)行沖突可串行化沖突是指調(diào)度中的一對(duì)連續(xù)操作(op1;op2)，它們滿足如下的條件：如果交換它們兩者的執(zhí)行順序，那么涉及的事務(wù)中至少有一個(gè)的行為會(huì)改變符合上述條件的一對(duì)連續(xù)的操作(op1;op2)被稱為‘沖突’69沖突的判斷假設(shè)Ti和Tj是兩個(gè)不同的事務(wù)(即i

j)，則：ri(X);rj(Y)不是沖突(即使X=Y也不會(huì)是沖突)如果X

Y，則ri(X);wj(Y)不會(huì)是沖突如果X

Y，則wi(X);rj(Y)不會(huì)是沖突如果X

Y，則wi(X);wj(Y)不會(huì)是沖突同一事務(wù)的任意兩個(gè)相鄰的操作都是沖突，如：(ri(X);wi(Y))、(wi(X);ri(Y))、(ri(X);ri(Y))等不同事務(wù)對(duì)同一數(shù)據(jù)對(duì)象的‘寫’沖突：wi(X);wj(X)不同事務(wù)對(duì)同一數(shù)據(jù)對(duì)象的‘讀-寫’沖突：

ri(X);wj(X) wi(X);rj(X)705.2.1事務(wù)的并發(fā)執(zhí)行概括起來(lái)講同一事務(wù)中的任意兩個(gè)操作不可以交換它們的執(zhí)行順序(是沖突)不同事務(wù)中的任何兩個(gè)操作在執(zhí)行順序上是可以交換的，除非：它們涉及同一個(gè)數(shù)據(jù)對(duì)象；并且至少有一個(gè)是‘寫’操作對(duì)于初始給定的一個(gè)調(diào)度，如果通過(guò)一組‘非沖突’操作的交換，能夠?qū)⒃撜{(diào)度轉(zhuǎn)換為一個(gè)串行調(diào)度，則我們認(rèn)為最初的調(diào)度就是一個(gè)可串行化調(diào)度715.2.1事務(wù)的并發(fā)執(zhí)行沖突等價(jià)如果通過(guò)一系列相鄰操作的非沖突交換能夠?qū)⒁粋€(gè)調(diào)度轉(zhuǎn)換為另一個(gè)調(diào)度，則我們稱這兩個(gè)調(diào)度是沖突等價(jià)的沖突可串行化如果一個(gè)調(diào)度S沖突等價(jià)于一個(gè)串行調(diào)度，則我們稱調(diào)度S是“沖突可串行化”的‘沖突可串行化’是‘可串行化’的一個(gè)充分條件，而非必要條件‘沖突可串行化’調(diào)度必定也是一個(gè)’可串行化’調(diào)度一個(gè)’可串行化’調(diào)度并不一定是’沖突可串行化’的725.2.1事務(wù)的并發(fā)執(zhí)行例：將調(diào)度3通過(guò)一系列非沖突交換可以轉(zhuǎn)換成一個(gè)串行調(diào)度（調(diào)度1）（事務(wù)T2中的操作被標(biāo)上下劃線）步驟1(原調(diào)度3)r1(A);w1(A);r2(A);w2(A);r1(B);w1(B);r2(B);w2(B);步驟2：r1(A);w1(A);r2(A);r1(B);w2(A);w1(B);r2(B);w2(B);步驟3：r1(A);w1(A);r1(B);r2(A);w2(A);w1(B);r2(B);w2(B);步驟4：r1(A);w1(A);r1(B);r2(A);w1(B);w2(A);r2(B);w2(B);步驟5(串行調(diào)度1)r1(A);w1(A);r1(B);w1(B);r2(A);w2(A);r2(B);w2(B);T2T1735.2.1事務(wù)的并發(fā)執(zhí)行優(yōu)先圖思想：沖突操作反映了給定事務(wù)在沖突等價(jià)的串行調(diào)度（如果存在的話）中的執(zhí)行順序定義：已知在調(diào)度S中存在兩個(gè)事務(wù)T1和T2，如果有T1的一個(gè)動(dòng)作A1和T2的一個(gè)動(dòng)作A2滿足：在調(diào)度S中A1在A2前A1和A2涉及數(shù)據(jù)庫(kù)中的同一數(shù)據(jù)對(duì)象，且至少有一個(gè)是‘寫’動(dòng)作則我們稱T1優(yōu)先于T2，記為T1

<s

T2在上述情況下，A1和A2是兩個(gè)不能交換的動(dòng)作，如果存在一個(gè)沖突等價(jià)于S的串行調(diào)度，則在該串行調(diào)度中T1必在T2之前745.2.1事務(wù)的并發(fā)執(zhí)行優(yōu)先圖【定義】以調(diào)度S中的事務(wù)作為優(yōu)先圖中的結(jié)點(diǎn)（事務(wù)Ti可簡(jiǎn)記為i），如果Ti<sTj，則從結(jié)點(diǎn)i到結(jié)點(diǎn)j引一條有向邊。依此類推構(gòu)成的一個(gè)有向圖被稱為調(diào)度S的事務(wù)優(yōu)先圖。例：r2(A);r1(B);w2(A);r3(A);w1(B);w3(A);r2(B);w2(B)例：r2(A);r1(B);w2(A);r2(B);r3(A);w1(B);w3(A);w2(B)其優(yōu)先圖是：1→2→3其優(yōu)先圖是：

1→2→3755.2.1事務(wù)的并發(fā)執(zhí)行沖突可串行化的判斷規(guī)則構(gòu)造調(diào)度S的事務(wù)優(yōu)先圖，如果該圖是無(wú)環(huán)的，則調(diào)度S是沖突可串行化的。如果有環(huán)，則調(diào)度S不是沖突可串行化的例：r2(A);r1(B);w2(A);r3(A);w1(B);w3(A);r2(B);w2(B)例：r2(A);r1(B);w2(A);r2(B);r3(A);w1(B);w3(A);w2(B)其優(yōu)先圖是：

1→2→3（存在環(huán)狀結(jié)構(gòu)），因此該調(diào)度不是沖突可串行化的其優(yōu)先圖是：1→2→3（無(wú)環(huán)），因此該調(diào)度是沖突可串行化的76[結(jié)論1]如果在優(yōu)先圖中存在環(huán)，則該調(diào)度不是沖突可串行化的。證明（反證法）：設(shè)有一個(gè)由T1,T2,…,Tn等n個(gè)事務(wù)構(gòu)成的調(diào)度H，其優(yōu)先圖中存在一個(gè)涉及這n個(gè)事務(wù)的環(huán)狀結(jié)構(gòu)：T1→T2→…→Tn→T1。假設(shè)存在一個(gè)與調(diào)度H沖突等價(jià)的串行調(diào)度S∵在優(yōu)先圖中T1優(yōu)先于T2的前提條件是存在T1的一個(gè)動(dòng)作A1和T2的一個(gè)動(dòng)作A2，在調(diào)度H中A1先于A2，且A1與A2不可交換（沖突）∴在調(diào)度S中，A1也應(yīng)先于A2。即在串行調(diào)度S中T1應(yīng)該先于T2執(zhí)行。依此類推：T1先于T2，T2先于T3，…，Tn-1先于Tn，Tn先于T1∴得到一對(duì)矛盾的關(guān)系：T1先于Tn，Tn先于T1∴假設(shè)不成立，不可能存在一個(gè)與調(diào)度H沖突等價(jià)的串行調(diào)度，即不是沖突可串行化的77[結(jié)論2]如果調(diào)度S的優(yōu)先圖中無(wú)環(huán)，則調(diào)度S是沖突可串行化的。證明(歸納法)設(shè)由n個(gè)事務(wù)T1,T2,……,Tn構(gòu)成一個(gè)調(diào)度Hn當(dāng)n=1時(shí)，調(diào)度H1只有一個(gè)事務(wù)組成，因此H1是一個(gè)串行調(diào)度，因而也是沖突可串行化的假設(shè)n=(k-1)時(shí)結(jié)論成立，即：如果存在一個(gè)由(k-1)個(gè)事務(wù)T1,T2,……,Tk-1所構(gòu)成的調(diào)度Hk-1，其事務(wù)優(yōu)先圖是無(wú)環(huán)的，則調(diào)度Hk-1是沖突可串行化的，即調(diào)度Hk-1沖突等價(jià)于它們的某個(gè)串行調(diào)度Sk-1當(dāng)n=k時(shí)，如果由k個(gè)事務(wù)T1,T2,……,Tk所構(gòu)成的調(diào)度Hk的事務(wù)優(yōu)先圖G是無(wú)環(huán)的，則有如下結(jié)論：∵優(yōu)先圖G是一個(gè)有向無(wú)環(huán)圖∴在圖G中至少存在一個(gè)結(jié)點(diǎn)i(事務(wù)Ti所對(duì)應(yīng)的結(jié)點(diǎn))，不存在指向該結(jié)點(diǎn)的有向邊∴在調(diào)度Hk中不存在這樣一個(gè)動(dòng)作A：是Ti之外的某個(gè)事務(wù)Tj的動(dòng)作動(dòng)作A位于Ti的某個(gè)動(dòng)作Ai之前動(dòng)作A與動(dòng)作Ai是沖突∴可以通過(guò)非沖突動(dòng)作的交換將事務(wù)Ti的所有動(dòng)作交換到調(diào)度的最前面，并保持它們的原有順序不變。即將調(diào)度Hk轉(zhuǎn)換成下述的調(diào)度Sk：(Ti的所有動(dòng)作)(其它k-1個(gè)事務(wù)的動(dòng)作)且調(diào)度Hk與調(diào)度Sk是沖突等價(jià)的78結(jié)論2的證明(續(xù))79考慮調(diào)度Sk的后半部分：(Ti的所有動(dòng)作)(其它k-1個(gè)事務(wù)的動(dòng)作)由Ti之外的其它(k-1)個(gè)事務(wù)中的動(dòng)作所構(gòu)成的調(diào)度Hk-1∵調(diào)度Hk-1中的所有動(dòng)作均保持了它們?cè)谡{(diào)度Hk中的排列順序∴從優(yōu)先圖G中去刪除結(jié)點(diǎn)i以及與其相關(guān)的所有有向邊，就構(gòu)成了調(diào)度Hk-1的事務(wù)優(yōu)先圖G’(即：圖G’是圖G的一個(gè)子圖)∵圖G是有向無(wú)環(huán)圖∴圖G’也是一個(gè)有向無(wú)環(huán)圖Hk-1結(jié)論2的證明(續(xù))80 根據(jù)步驟2的假設(shè)：如果由(k-1)個(gè)事務(wù)所構(gòu)成的調(diào)度的事務(wù)優(yōu)先圖是無(wú)環(huán)的，則該調(diào)度是沖突可串行化的∴上述的調(diào)度Hk-1是沖突可串行化的，即調(diào)度Hk-1沖突等價(jià)于這(k-1)個(gè)事務(wù)的某個(gè)串行調(diào)度Sk-1∵調(diào)度Sk等于：(事務(wù)Ti的所有動(dòng)作)+調(diào)度Hk-1

調(diào)度Hk-1沖突等價(jià)于某個(gè)串行調(diào)度Sk-1∴調(diào)度Sk沖突等價(jià)于一個(gè)串行調(diào)度(Ti,Sk-1)∵調(diào)度Hk沖突等價(jià)于調(diào)度Sk

調(diào)度Sk沖突等價(jià)于串行調(diào)度(Ti,Sk-1)∴調(diào)度Hk沖突等價(jià)于串行調(diào)度(Ti,Sk-1)∴調(diào)度Hk是沖突可串行化的。 證畢結(jié)論2的證明(續(xù))815.2.1事務(wù)的并發(fā)執(zhí)行三種數(shù)據(jù)不一致現(xiàn)象在事務(wù)的并發(fā)執(zhí)行過(guò)程中，如果采用了不合理的調(diào)度方法，就會(huì)出現(xiàn)并發(fā)執(zhí)行錯(cuò)誤，破壞數(shù)據(jù)庫(kù)中數(shù)據(jù)的一致性。常見(jiàn)的并發(fā)執(zhí)行錯(cuò)誤有三種：丟失修改（lostupdata）臟讀（dirtyread）不可重復(fù)讀（non-repeatableread）825.2.1事務(wù)的并發(fā)執(zhí)行例：飛機(jī)售票業(yè)務(wù)假設(shè)某個(gè)航班的剩余機(jī)票的張數(shù)保存在數(shù)據(jù)庫(kù)對(duì)象X（初始值為5）中，則出售一張?jiān)摵桨鄼C(jī)票的事務(wù)的執(zhí)行流程是：Read(X,t); /*t是該事務(wù)使用的內(nèi)存變量*/t:=t–1;Write(X,t);83丟失修改現(xiàn)象：一個(gè)事務(wù)的修改結(jié)果破壞了另一個(gè)事務(wù)的修改結(jié)果原因：對(duì)多個(gè)事務(wù)并發(fā)修改同一個(gè)數(shù)據(jù)對(duì)象的情況未加控制步驟甲售票點(diǎn)變量t1乙售票點(diǎn)變量t2剩余機(jī)票X1Read(X,t1);552t1:=t1–1;43Read(X,t2);54t1:=t2–1;45Write(X,t1);46Write(X,t2);484臟讀現(xiàn)象：讀到了錯(cuò)誤的數(shù)據(jù)(即與數(shù)據(jù)庫(kù)中的情況不相符的數(shù)據(jù))原因：一個(gè)事務(wù)讀取了另一個(gè)事務(wù)未提交的修改結(jié)果步驟甲售票點(diǎn)變量t1乙售票點(diǎn)變量t2剩余機(jī)票X1Read(X,t1);552t1:=t1–1;43Write(X,t1);444Read(X,t2);45放棄當(dāng)前的售票操作，取消對(duì)X的修改585不可重復(fù)讀現(xiàn)象： 在一個(gè)事務(wù)的執(zhí)行過(guò)程中，前后兩次讀同一個(gè)數(shù)據(jù)對(duì)象所獲得的值出現(xiàn)了不一致原因： 在兩次’讀’操作之間插入了另一個(gè)事務(wù)的’寫’操作步驟甲售票點(diǎn)變量t1乙售票點(diǎn)變量t2剩余機(jī)票X1Read(X,t1);552Read(X,t2);53t2:=t2–1;44Write(X,t2);445Read(X,t1);4Example10.3.3BlindWritesT1:W1(A,50);W1(B,50);C1;T2:W2(A,80);W2(B,20);C2;H3:W1(A,50);W2(A,80);W2(B,20);W1(B,50);C1;C2;scheduleH3T1&T2T2&T1valueofA808050valueofB502050875.2.1事務(wù)的并發(fā)執(zhí)行出現(xiàn)上述三種數(shù)據(jù)不一致現(xiàn)象的原因在于：多個(gè)并發(fā)執(zhí)行的事務(wù)反復(fù)交叉使用同一個(gè)數(shù)據(jù)庫(kù)（數(shù)據(jù)對(duì)象），而數(shù)據(jù)庫(kù)管理系統(tǒng)又沒(méi)有提供必要的控制手段合理組織調(diào)度多個(gè)用戶的并發(fā)操作，避免產(chǎn)生數(shù)據(jù)不一致現(xiàn)象的工作也被稱為‘并發(fā)控制’常用的并發(fā)控制技術(shù)是：封鎖885.2并發(fā)控制技術(shù)5.2.1事務(wù)的并發(fā)執(zhí)行5.2.2封鎖5.2.3封鎖協(xié)議5.2.4兩階段封鎖協(xié)議5.2.5封鎖粒度5.2.6活鎖與死鎖895.2.2封鎖主要內(nèi)容封鎖（lock）封鎖類型常用的兩種類型封鎖鎖相容矩陣申請(qǐng)封鎖和釋放封鎖的處理過(guò)程使用封鎖技術(shù)實(shí)現(xiàn)并發(fā)控制的方法905.2.2封鎖封鎖（lock）使用封鎖技術(shù)的前提在一個(gè)事務(wù)訪問(wèn)數(shù)據(jù)庫(kù)中的數(shù)據(jù)時(shí)，必須先獲得被訪問(wèn)的數(shù)據(jù)對(duì)象上的封鎖，以保證數(shù)據(jù)訪問(wèn)操作的正確性和一致性。封鎖的作用在一段時(shí)間內(nèi)禁止其它事務(wù)在被封鎖的數(shù)據(jù)對(duì)象上執(zhí)行某些類型的操作（由封鎖的類型決定）同時(shí)也表明：持有該封鎖的事務(wù)在被封鎖的數(shù)據(jù)對(duì)象上將要執(zhí)行什么類型的操作（由系統(tǒng)所采用的封鎖協(xié)議來(lái)決定）‘封鎖’是多用戶環(huán)境中最常采用的一種并發(fā)控制技術(shù)915.2.2封鎖封鎖類型常用的封鎖類型有兩種排它鎖

eXclusivelock，又簡(jiǎn)稱為：X鎖共享鎖

Sharinglock，又簡(jiǎn)稱為：S鎖92排它鎖（X鎖）特性只有當(dāng)數(shù)據(jù)對(duì)象A沒(méi)有被其它事務(wù)封鎖時(shí)，事務(wù)T才能在數(shù)據(jù)對(duì)象A上施加‘X鎖’如果事務(wù)T對(duì)數(shù)據(jù)對(duì)象A施加了’X鎖’，則其它任何事務(wù)都不能在數(shù)據(jù)對(duì)象A上再施加任何類型的封鎖作用如果一個(gè)事務(wù)T申請(qǐng)?jiān)跀?shù)據(jù)對(duì)象A上施加‘X鎖’并得到滿足，則：事務(wù)T自身可以對(duì)數(shù)據(jù)對(duì)象A作讀、寫操作，而其它事務(wù)則被禁止訪問(wèn)數(shù)據(jù)對(duì)象A這樣可以讓事務(wù)T獨(dú)占該數(shù)據(jù)對(duì)象A，從而保證了事務(wù)T對(duì)數(shù)據(jù)對(duì)象A的訪問(wèn)操作的正確性和一致性缺點(diǎn)：降低了整個(gè)系統(tǒng)的并行性‘X鎖’必須維持到事務(wù)T的執(zhí)行結(jié)束93共享鎖（S鎖）特性如果數(shù)據(jù)對(duì)象A沒(méi)有被其它事務(wù)封鎖，或者其它事務(wù)僅僅以‘S鎖’的方式來(lái)封鎖數(shù)據(jù)對(duì)象A時(shí)，事務(wù)T才能在數(shù)據(jù)對(duì)象A上施加‘S鎖’作用如果一個(gè)事務(wù)T申請(qǐng)?jiān)跀?shù)據(jù)對(duì)象A上施加‘S鎖’并得到滿足，則：事務(wù)T可以對(duì)‘讀’數(shù)據(jù)對(duì)象A，但不能‘寫’數(shù)據(jù)對(duì)象A不同事務(wù)所申請(qǐng)的‘S鎖’可以共存于同一個(gè)數(shù)據(jù)對(duì)象A上，從而保證了多個(gè)事務(wù)可以同時(shí)‘讀’數(shù)據(jù)對(duì)象A，有利于提高整個(gè)系統(tǒng)的并發(fā)性在持有封鎖的事務(wù)釋放數(shù)據(jù)對(duì)象A上的所有‘S鎖’之前，任何事務(wù)都不能‘寫’數(shù)據(jù)對(duì)象A‘S鎖’不必維持到事務(wù)T的執(zhí)行結(jié)束(依封鎖協(xié)議而定)94‘排它鎖’與‘共享鎖’的相互關(guān)系可以用如下圖所示的‘鎖相容矩陣’來(lái)表示合適(wellformed)事務(wù)如果一個(gè)事務(wù)在訪問(wèn)數(shù)據(jù)庫(kù)中的數(shù)據(jù)對(duì)象A之前按照要求申請(qǐng)對(duì)A的封鎖，在操作結(jié)束后釋放A上的封鎖，這種事務(wù)被稱為合適事務(wù)‘合適事務(wù)’是保證并發(fā)事務(wù)的正確執(zhí)行的基本條件當(dāng)前事務(wù)申請(qǐng)的鎖其它事務(wù)已持有的鎖YesYesNoS鎖YesNoNoX鎖-S鎖X鎖圖5.8

封鎖的相容矩陣955.2.2封鎖封鎖的申請(qǐng)與釋放封鎖管理器的數(shù)據(jù)結(jié)構(gòu)數(shù)組LOCK(A)記錄被施加在數(shù)據(jù)對(duì)象A上的封鎖類型，其值是：Read_locked（共享鎖）Write_locked（排它鎖）Unlocked（無(wú)封鎖）數(shù)組no_of_reads(A)記錄被施加在數(shù)據(jù)對(duì)象A上的共享鎖的個(gè)數(shù)96申請(qǐng)對(duì)數(shù)據(jù)對(duì)象A的共享鎖(S鎖)：read_lock(A)B：ifLOCK(A)=‘Unlocked'{ LOCK(A):=‘Read_locked'; no_of_reads(A):=1; }else{ ifLOCK(A)=‘Read_locked’ no_of_reads(A):=no_of_reads(A)+1; else{ wait(untilLOCK(A)!=‘Write_locked' andthelockmanagerwakesup thetransaction); gotoB; } }97申請(qǐng)對(duì)數(shù)據(jù)對(duì)象A的排它鎖(X鎖)：write_lock(A)B： ifLOCK(A)=‘Unlocked’ { LOCK(A):=‘Write_locked'; } else { wait(untilLOCK(A)=‘Unlocked‘a(chǎn)ndthelock managerwakesupthetransaction); gotoB; }98釋放對(duì)數(shù)據(jù)對(duì)象A的封鎖：unlock(A)ifLOCK(A)=‘Write_locked’{ LOCK(A):=‘Unlocked'; wakeuponeofthewaitingtransaction,ifany}elseifLOCK(A)=‘Read_locked'{ no_of_reads(A):=no_of_reads(A)-1; ifno_of_reads(A)=0{ LOCK(A):=‘Unlocked' wakeuponeofthewaitingtransaction,ifany }}995.2.2封鎖使用封鎖的并發(fā)控制技術(shù)在DBMS的‘封鎖管理器’中維護(hù)著一張‘鎖表’，以記錄當(dāng)前：封鎖的持有情況有哪些‘事務(wù)’在哪些‘?dāng)?shù)據(jù)對(duì)象’上持有什么類型的‘封鎖’封鎖的申請(qǐng)情況有哪些‘事務(wù)’正在申請(qǐng)哪些‘?dāng)?shù)據(jù)對(duì)象’上的什么類型的‘封鎖’DBMS對(duì)于用戶事務(wù)的數(shù)據(jù)訪問(wèn)操作Op(A)的處理過(guò)程如下：100事務(wù)的數(shù)據(jù)訪問(wèn)操作的處理過(guò)程將訪問(wèn)操作Op(A)發(fā)送給并發(fā)控制子系統(tǒng)的‘調(diào)度器’‘調(diào)度器’根據(jù)系統(tǒng)采用的封鎖協(xié)議來(lái)決定：是否需要為該操作申請(qǐng)封鎖申請(qǐng)何種類型的封鎖 并將封鎖申請(qǐng)發(fā)送給‘封鎖管理器’‘封鎖管理器’根據(jù)鎖表中記載的情況來(lái)決定是否能夠立即滿足該封鎖申請(qǐng)，并將申請(qǐng)結(jié)果返回給‘調(diào)度器’如果封鎖申請(qǐng)得不到滿足，則‘調(diào)度器’將訪問(wèn)操作Op(A)放入‘被推遲的訪問(wèn)操作’隊(duì)列，否則將該操作發(fā)送給系統(tǒng)的執(zhí)行引擎執(zhí)行101事務(wù)的數(shù)據(jù)訪問(wèn)操作的處理過(guò)程（圖）1025.2并發(fā)控制技術(shù)5.2.1事務(wù)的并發(fā)執(zhí)行5.2.2封鎖5.2.3封鎖協(xié)議5.2.4兩階段封鎖協(xié)議5.2.5封鎖粒度5.2.6活鎖與死鎖1035.2.3封鎖協(xié)議采用‘封鎖’技術(shù)為并發(fā)事務(wù)的正確執(zhí)行提供了可能性。但是要真正確保事務(wù)并發(fā)執(zhí)行的正確性，還必須按照規(guī)定的方法來(lái)使用‘封鎖’技術(shù)，即規(guī)定事務(wù)使用‘封鎖’的方式。包括：何時(shí)申請(qǐng)封鎖？申請(qǐng)何種類型的封鎖？(S鎖/X鎖)何時(shí)釋放所持有的封鎖？1045.2.3封鎖協(xié)議封鎖協(xié)議（lockingprotocol）不同的封鎖方式構(gòu)成了不同的封鎖規(guī)則，我們稱之為‘封鎖協(xié)議’三級(jí)封鎖協(xié)議不同級(jí)別的封鎖協(xié)議可以防止不同的并發(fā)錯(cuò)誤兩階段封鎖協(xié)議105一級(jí)封鎖協(xié)議事務(wù)T在‘寫’數(shù)據(jù)對(duì)象A之前，必須先申請(qǐng)并獲得A上的‘X鎖’，并維持到事務(wù)T的執(zhí)行結(jié)束(包括Commit與Rollback)才釋放被加在A上的‘X鎖’二級(jí)封鎖協(xié)議‘一級(jí)封鎖協(xié)議’的要求；并且事務(wù)T在’讀’數(shù)據(jù)對(duì)象A之前，必須先申請(qǐng)并獲得A上的’S鎖’，在’讀’操作完成后即可釋放A上的’S鎖’這里沒(méi)有規(guī)定釋放‘S鎖’的時(shí)間三級(jí)封鎖協(xié)議‘一級(jí)封鎖協(xié)議’的要求；并且事務(wù)T在‘讀’數(shù)據(jù)對(duì)象A之前，必須先申請(qǐng)并獲得A上的‘S鎖’，并維持到事務(wù)T的執(zhí)行結(jié)束(包括Commit與Rollback)才釋放被加在A上的‘S鎖’106‘一級(jí)封鎖協(xié)議’可防止‘丟失修改’現(xiàn)象步驟甲售票點(diǎn)乙售票點(diǎn)剩余機(jī)票X1write_lock(X);52Read(X,t1);3write_lock(X);4t1:=t1–1;wait……5Write(X,t1);wait……46Commit;wait……7unlock(X);wait……8Read(X,t2);9t1:=t2–1;10Write(X,t2);311Commit;12unlock(X);107‘二級(jí)封鎖協(xié)議’可防止‘丟失修改、臟讀’現(xiàn)象步驟甲售票點(diǎn)變量t1乙售票點(diǎn)變量t2剩余機(jī)票X1write_lock(X);52Read(X,t1);53t1:=t1–1;44Write(X,t1);45read_lock(X);6wait……7Rollbackwait……58unlock(X);wait……9Read(X,t1);5……108‘三級(jí)封鎖協(xié)議’可防止‘丟失修改、臟讀、不可重復(fù)讀’現(xiàn)象步驟甲售票點(diǎn)變量t1乙售票點(diǎn)變量t2剩余機(jī)票X1read_lock(X);52Read(X,t1);53write_lock(X);4……wait……5Read(X,t1);5wait……6Commit;wait……7unlock(X);wait……8Read(X,t2);59……109‘三級(jí)封鎖協(xié)議’與三種數(shù)據(jù)不一致現(xiàn)象的關(guān)系可能出現(xiàn)的數(shù)據(jù)不一致現(xiàn)象丟失修改臟讀不可重復(fù)讀封鎖協(xié)議一級(jí)封鎖協(xié)議NoYesYes二級(jí)封鎖協(xié)議NoNoYes三級(jí)封鎖協(xié)議NoNoNo110根據(jù)對(duì)于封鎖協(xié)議的介紹我們可以得知，多個(gè)事務(wù)的并發(fā)運(yùn)行之所以會(huì)破壞數(shù)據(jù)庫(kù)狀態(tài)的一致性，其原因是：事務(wù)沒(méi)有為被訪問(wèn)的數(shù)據(jù)對(duì)象申請(qǐng)封鎖事務(wù)沒(méi)有在合適的時(shí)候釋放所持有的鎖‘三級(jí)封鎖協(xié)議’正是為解決上述問(wèn)題而定義的封鎖規(guī)則1115.2并發(fā)控制技術(shù)5.2.1事務(wù)的并發(fā)執(zhí)行5.2.2封鎖5.2.3封鎖協(xié)議5.2.4兩階段封鎖協(xié)議5.2.5封鎖粒度5.2.6活鎖與死鎖1125.2.4兩階段封鎖協(xié)議按照‘三級(jí)封鎖協(xié)議’的規(guī)定，事務(wù)T在其執(zhí)行過(guò)程中所申請(qǐng)的所有‘鎖’必須在事務(wù)T結(jié)束后才能釋放。這就意味著，在一個(gè)事務(wù)執(zhí)行過(guò)程中，必須把鎖的申請(qǐng)與釋放分為兩個(gè)階段：第一個(gè)階段：申請(qǐng)并獲得封鎖在此階段中，事務(wù)可以申請(qǐng)其整個(gè)執(zhí)行過(guò)程中所需要的鎖，此階段也可稱為‘?dāng)U展階段’第二階段：釋放所有申請(qǐng)獲得的鎖此階段也可稱為‘收縮階段’事務(wù)一旦開(kāi)始釋放封鎖，那么就不能再申請(qǐng)任何封鎖此種設(shè)置封鎖的方法稱為‘兩階段封鎖協(xié)議’two-phaselockingprotocol，簡(jiǎn)稱2PL協(xié)議1135.2.4兩階段封鎖協(xié)議兩階段封鎖事務(wù)在一個(gè)事務(wù)T中，如果所有的封鎖請(qǐng)求都先于所有的解鎖請(qǐng)求，則該事務(wù)被稱為‘兩階段封鎖事務(wù)’，簡(jiǎn)稱‘2PL事務(wù)’或者說(shuō)：采用兩階段封鎖協(xié)議的事務(wù)1145.2.4兩階段封鎖協(xié)議2PL事務(wù)的例子(圖5.12)事務(wù)T：sl(A);sl(B);sl(C);……;u(B);u(A);u(C);用sl(A)表示申請(qǐng)對(duì)A的‘S鎖’，用xl(A)表示申請(qǐng)對(duì)A的‘X鎖’，用u(A)表示釋放A上的封鎖不遵守2PL協(xié)議的例子(圖5.13)事務(wù)T’：sl(A);u(A);sl(B);xl(C);……;u(C);u(B)擴(kuò)展階段收縮階段1155.2.4兩階段封鎖協(xié)議基于前述的‘三級(jí)封鎖協(xié)議’和‘兩階段封鎖協(xié)議’的要求，我們歸納出有關(guān)封鎖技術(shù)的使用規(guī)定假設(shè)系統(tǒng)采用‘X鎖’和‘S鎖’兩種類型鎖，有關(guān)封鎖的申請(qǐng)與釋放操作表示如下：sli(A)：事務(wù)Ti申請(qǐng)數(shù)據(jù)對(duì)象A上的一個(gè)‘S鎖’xli(A)：事務(wù)Ti申請(qǐng)數(shù)據(jù)對(duì)象A上的一個(gè)‘X鎖’也可以用li(A)表示事務(wù)Ti申請(qǐng)數(shù)據(jù)對(duì)象A上的鎖ui(A)：事務(wù)Ti釋放自己在數(shù)據(jù)對(duì)象A上所持有的鎖116封鎖的使用規(guī)定在每一個(gè)事務(wù)Ti中第1點(diǎn)：采用如下的封鎖協(xié)議：讀動(dòng)作ri(A)之前必須有sli(A)或xli(A)，而且在兩者之間沒(méi)有ui(A)寫動(dòng)作wi(A)之前必須有xli(A)，而且在兩者之間沒(méi)有ui(A)每一個(gè)sli(A)或xli(A)之后必須有一個(gè)ui(A)第2點(diǎn)：必須遵循‘兩階段封鎖協(xié)議’在任何sli(A)或xli(A)之前不能有ui(B)A和B可以是同一個(gè)數(shù)據(jù)對(duì)象117封鎖的使用規(guī)定（續(xù)）如果事務(wù)Ti

在執(zhí)行過(guò)程中重復(fù)申請(qǐng)同一個(gè)數(shù)據(jù)對(duì)象A上的鎖，‘封鎖管理器’的處理方法如下：如果Ti已經(jīng)持有數(shù)據(jù)對(duì)象A上的鎖，則對(duì)sli(A)不作任何處理如果Ti已經(jīng)持有數(shù)據(jù)對(duì)象A上的‘S鎖’，在處理xli(A)請(qǐng)求時(shí)，僅僅將Ti所持有的‘S鎖’改為‘X鎖’僅當(dāng)只有事務(wù)Ti持有數(shù)據(jù)對(duì)象A上的‘S鎖’時(shí)，封鎖管理器才能將Ti所持有的‘S鎖’改為‘X鎖’如果Ti已經(jīng)持有數(shù)據(jù)對(duì)象A上的‘X鎖’，則對(duì)xli(A)不作任何處理118封鎖的使用規(guī)定（續(xù)）上述的處理過(guò)程確保一個(gè)事務(wù)在一個(gè)數(shù)據(jù)對(duì)象上只能持有一把‘鎖’如果事務(wù)Ti在執(zhí)行過(guò)程中在同一個(gè)數(shù)據(jù)對(duì)象A上執(zhí)行了若干次鎖申請(qǐng)操作：li1(A);li2(A);…;lin(A)

并且在li1(A)和lin(A)之間沒(méi)有ui(A)，則在lin(A)之后必須有且僅有一個(gè)ui(A)封鎖的重復(fù)申請(qǐng)過(guò)程只能是：sli(A);……;xli(A);119封鎖的使用規(guī)定（續(xù)）第3點(diǎn)：保證事務(wù)調(diào)度的合法性對(duì)任意兩個(gè)不同的事務(wù)Ti和Tj，其調(diào)度必須滿足：如果xli(A)出現(xiàn)在調(diào)度中，那么后面不能再有slj(A)或xlj(A)，除非中間插入了ui(A)如果sli(A)出現(xiàn)在調(diào)度中，那么后面不能再有xlj(A)，除非中間插入了ui(A)如果一個(gè)調(diào)度以及它的每個(gè)事務(wù)都滿足上述三個(gè)方面的要求，我們稱該調(diào)度是一個(gè)‘合法調(diào)度’我們可以將前述的‘調(diào)度器’和‘封鎖管理器’合并為一個(gè)‘封鎖調(diào)度器’，DBMS正是通過(guò)‘封鎖調(diào)度器’來(lái)產(chǎn)生若干個(gè)并發(fā)運(yùn)行事務(wù)之間的一個(gè)‘合法調(diào)度’的120封鎖的使用規(guī)定（續(xù)）T1T2xyTempAB1Read(A,x)20000-20000200002x:=x-10000100003Read(A,y)200004Temp:=y*0.120005y:=y-Temp180006Write(A,y)180007Read(B,y)200008Write(A,x)100009Read(B,x)2000010x:=x3000011Write(B,x)3000012y:=y+Temp2200013Write(B,y)22000圖5不正確的并發(fā)執(zhí)行(結(jié)果：A=10000,B=22000)121封鎖的使用規(guī)定（續(xù)）圖5所示的兩個(gè)轉(zhuǎn)帳事務(wù)T1和T2的執(zhí)行流程如下(只保留了對(duì)于數(shù)據(jù)庫(kù)的訪問(wèn)操作)：r1(A);r2(A);

w2(A);r2(B);w1(A);r1(B);w1(B);w2(B);該操作執(zhí)行流程被發(fā)送給’封鎖調(diào)度器’時(shí)，‘封鎖調(diào)度器’將首先根據(jù)前面介紹的‘封鎖協(xié)議’和‘2PL事務(wù)’的要求插入相應(yīng)的封鎖申請(qǐng)和釋放操作，其流程如下：xl1(A);r1(A);xl2(A);r2(A);w2(A);xl2(B);r2(B);w1(A);xl1(B);r1(B);w1(B);u1(A);u1(B);w2(B);u2(A);u2(B);122封鎖的使用規(guī)定（續(xù)）xl1(A);r1(A);

xl2(A);r2(A);w2(A);xl2(B);r2(B);

w1(A);xl1(B);r1(B);w1(B);u1(A);u1(B);

w2(B);u2(A);u2(B);在上述（預(yù)想）執(zhí)行流程中，’封鎖調(diào)度器’在處理事務(wù)T2的xl2(A)

請(qǐng)求時(shí)，因封鎖申請(qǐng)得不到滿足而將事務(wù)T2及其所有的后續(xù)操作請(qǐng)求推遲，真正的操作執(zhí)行流程是(下面的xl(A)是申請(qǐng)并獲得A上的‘X鎖’的時(shí)間

)xl1(A);r1(A);w1(A);xl1(B);r1(B);w1(B);u1(A);u1(B);xl2(A);r2(A);w2(A);xl2(B);r2(B);w2(B);u2(A);u2(B);最終產(chǎn)生的是T1和T2之間的一個(gè)串行調(diào)度1235.2.4兩階段封鎖協(xié)議定理:由2PL事務(wù)所構(gòu)成的任意合法調(diào)度S都是沖突可串行化的證明：當(dāng)調(diào)度S僅由一個(gè)事務(wù)組成時(shí)，調(diào)度S是沖突可串行化的假設(shè)：由(n-1)個(gè)2PL事務(wù)所構(gòu)成的任意一個(gè)合法調(diào)度都是沖突可串行化的設(shè)調(diào)度S涉及n個(gè)2PL事務(wù)：T1,T2,……,Tn，并且Ti是調(diào)度S中第一個(gè)有解鎖動(dòng)作的事務(wù)，則我們可以得到以下結(jié)論：

可以將Ti的所有動(dòng)作不經(jīng)過(guò)任何沖突而移動(dòng)到調(diào)度S的最前面124定理證明（續(xù)）設(shè)在Ti中有一個(gè)動(dòng)作wi(A)(或ri(A))，如果調(diào)度S在該動(dòng)作的前面有一個(gè)與之沖突的動(dòng)作wj(A)(i

j)，那么調(diào)度S的情況必是：…;wj(A);…;u