并發(fā)控制課后答案

1、第八章并發(fā)控制習(xí)題解答和解析1. 1. 在數(shù)據(jù)庫中為什么要并發(fā)控制答：數(shù)據(jù)庫是共享資源, 通常有許多個事務(wù)同時在運行。當(dāng)多個事務(wù)并發(fā)地存取數(shù)據(jù)庫時就會產(chǎn)生同時讀取和/ 或修改同一數(shù)據(jù)的情況。若對并發(fā)操作不加控制就可能會存取和存儲不正確的數(shù)據(jù), 破壞數(shù)據(jù)庫的一致性。所以數(shù)據(jù)庫管理系統(tǒng)必須提供并發(fā)控制機制。2. 2. 并發(fā)操作可能會產(chǎn)生哪幾類數(shù)據(jù)不一致用什么方法能避免各種不一致的情況答：并發(fā)操作帶來的數(shù)據(jù)不一致性包括三類：丟失修改、不可重復(fù)讀和讀"臟" 數(shù)據(jù)。(1) 丟失修改 (LostUpdate) 兩個事務(wù)T1 和T2 讀入同一數(shù)據(jù)并修改,T2提交的結(jié)果破壞了( 覆蓋了 )

2、T1 提交的結(jié)果 , 導(dǎo)致 T1 的修改被丟失。(2) 不可重復(fù)讀 (Non -Repeatable Read)不可重復(fù)讀是指事務(wù)T1 讀取數(shù)據(jù)后 , 事務(wù) T2執(zhí)行更新操作 , 使 T1 無法再現(xiàn)前一次讀取結(jié)果。不可重復(fù)讀包括三種情況: 詳見概論(P266)。(3) 讀 " 臟 " 數(shù)據(jù) (Dirty Read)讀 " 臟" 數(shù)據(jù)是指事務(wù)T1 修改某一數(shù)據(jù), 并將其寫回磁盤,事務(wù)T2讀取同一數(shù)據(jù)后,T1由于某種原因被撤銷, 這時T1 已修改過的數(shù)據(jù)恢復(fù)原值,T2讀到的數(shù)據(jù)就與數(shù)據(jù)庫中的數(shù)據(jù)不一致, 則 T2 讀到的數(shù)據(jù)就為" 臟"

3、數(shù)據(jù) , 即不正確的數(shù)據(jù)。避免不一致性的方法和技術(shù)就是并發(fā)控制。最常用的技術(shù)是封鎖技術(shù)。也可以用其他技術(shù)，例如在分布式數(shù)據(jù)庫系統(tǒng)中可以采用時間戳方法來進行并發(fā)控制。3.3. 什么是封鎖答：封鎖就是事務(wù)對其加鎖 。加鎖后事務(wù)T 在對某個數(shù)據(jù)對象例如表、記錄等操作之前T 就對該數(shù)據(jù)對象有了一定的控制, 在事務(wù), 先向系統(tǒng)發(fā)出請求,T 釋放它的鎖之前, 其他的事務(wù)不能更新此數(shù)據(jù)對象。封鎖是實現(xiàn)并發(fā)控制的一個非常重要的技術(shù)。4. 4. 基本的封鎖類型有幾種試述它們的含義。答：基本的封鎖類型有兩種：排它鎖(Exclusive Locks,簡稱X鎖)和共享鎖(ShareLocks,簡稱S鎖 ) 。排它鎖又

4、稱為寫鎖。若事務(wù)T 對數(shù)據(jù)對象A 加上X 鎖, 則只允許T 讀取和修改A，其他任何事務(wù)都不能再對A 加任何類型的鎖, 直到T 釋放A 上的鎖。這就保證了其他事務(wù)在T 釋放 A 上的鎖之前不能再讀取和修改A。共享鎖又稱為讀鎖。若事務(wù)T 對數(shù)據(jù)對象A 加上S 鎖, 則事務(wù)T 可以讀A 但不能修改A,其他事務(wù)只能再對A 加S 鎖, 而不能加X鎖,直到T 釋放A 上的S 鎖。這就保證了其他事務(wù)可以讀A, 但在T 釋放A 上的S 鎖之前不能對A 做任何修改。5. 如何用封鎖機制保證數(shù)據(jù)的一致性答：DBMS在對數(shù)據(jù)進行讀 、寫操作之前首先對該數(shù)據(jù)執(zhí)行封鎖操作, 例如下圖中事務(wù)T1在對 A 進行修改之前先對

5、A 執(zhí)行 XLock(A), 即對 A 加 X 鎖。這樣 , 當(dāng) T2 請求對被拒絕， T2 只能等待T1 釋放 A 上的鎖后才能獲得對A 的 X 鎖 , 這時它讀到的的值 , 再按此新的A 值進行運算。這樣就不會丟失T1 的更新。A 加 X鎖時就A是 T1更新后DBMS按照一定的封鎖協(xié)議, 對并發(fā)操作進行控制 , 使得多個并發(fā)操作有序地執(zhí)行, 就可以避免丟失修改、不可重復(fù)讀和讀" 臟 " 數(shù)據(jù)等數(shù)據(jù)不一致性。6. 什么是封鎖協(xié)議不同級別的封鎖協(xié)議的主要區(qū)別是什么答：在運用封鎖技術(shù)對數(shù)據(jù)加鎖時, 要約定一些規(guī)則 。例如 , 在運用 X 鎖和 S 鎖對數(shù)據(jù)對象加鎖時 , 要約

6、定何時申請X 鎖或 S 鎖、何時釋放封鎖等。這些約定或者規(guī)則稱為封鎖協(xié)議(locking Protocol)。對封鎖方式約定不同的規(guī)則, 就形成了各種不同的封鎖協(xié)議、不同級別的封鎖協(xié)議 , 例如概論中介紹的三級封鎖協(xié)議, 三級協(xié)議的主要區(qū)別在于什么操作需要申請封鎖 , 何時申請封鎖以及何時釋放鎖( 即持鎖時間的長短) 。一級封鎖協(xié)議：事務(wù)T 在修改數(shù)據(jù)R之前必須先對其加X 鎖 , 直到事務(wù)結(jié)束才釋放。二級封鎖協(xié)議：一級封鎖協(xié)議加上事務(wù)T 在讀取數(shù)據(jù)R之前必須先對其加S 鎖 , 讀完后即可釋放S 鎖。三級封鎖協(xié)議：一級封鎖協(xié)議加上事務(wù)T 在讀取數(shù)據(jù)R之前必須先對其加S 鎖 , 直到事務(wù)結(jié)束才釋放

7、。7. 不同封鎖協(xié)議與系統(tǒng)一致性級別的關(guān)系是什么答：不同的封鎖協(xié)議對應(yīng)不同的一致性級別。一級封鎖協(xié)議可防止丟失修改 , 并保證事務(wù) T 是可恢復(fù)的。 在一級封鎖協(xié)議中 , 對讀數(shù)據(jù)是不加 S 鎖的 , 所以它不能保證可重復(fù)讀和不讀" 臟 " 數(shù)據(jù)。二級封鎖協(xié)議除防止了丟失修改, 還可進一步防止讀" 臟 " 數(shù)據(jù)。在二級封鎖協(xié)議中, 由于讀完數(shù)據(jù)后立即釋放S 鎖 , 所以它不能保證可重復(fù)讀。在三級封鎖協(xié)議中, 無論是讀數(shù)據(jù)還是寫數(shù)據(jù)都加長鎖，即都要到事務(wù)結(jié)束才釋放封鎖。所以三級封鎖協(xié)議除防止了丟失修改和不讀" 臟 " 數(shù)據(jù)外 , 還進一

8、步防止了不可重復(fù)讀。下面的表格清楚地說明了封鎖協(xié)議與系統(tǒng)一致性的關(guān)系。X鎖S 鎖一致性保證操作結(jié)事務(wù)結(jié)操作結(jié)事務(wù)結(jié)不丟失不讀 "臟"可重束束束束修改數(shù)據(jù)復(fù)讀釋放釋放釋放釋放一級封鎖協(xié)議二級封鎖協(xié)議三級封鎖協(xié)議8. 什么是活鎖什么是死鎖答：TIT2T3T4lock R.lock R.等待lock R.Unlock等待.lock R.等待.等待.等待.等待.等待Unlock等待.等待.lock R.等待.如果事務(wù) T1 封鎖了數(shù)據(jù)R，事務(wù) T2 飛又請求封鎖R, 于是 T2 等待。 T3 也請求封鎖R，當(dāng) T1 釋放了 R上的封鎖之后系統(tǒng)首先批準(zhǔn)了 T3 的請求 ,T2 仍然等

9、待 。然后 T4 又請求封鎖 R，當(dāng) T3 釋放了 R上的封鎖之后系統(tǒng)又批準(zhǔn)了 T4 的請求 T2 有可能永遠等待 , 這就是活鎖的情形。活鎖的含義是該等待事務(wù)等待時間太長，似乎被鎖住了, 實際上可能被激活。如果事務(wù) Tl 封鎖了數(shù)據(jù) R1,T2 封鎖了數(shù)據(jù) R2，然后 T1 又請求封鎖 R2,因 T2 已封鎖了 R2, 于是 T1 等待 T2 釋放 R2 上的鎖。接著 T2 又申請封鎖 R1, 因 T1 已封鎖了 R1,T2 也只能等待 T1 釋放 Rl 上的鎖。這樣就出現(xiàn)了 T1 在等待 T2, 而 T2 又在等待 Tl 的局面 ,T1 和 T2 兩個事務(wù)永遠不能結(jié)束 , 形成死鎖。T1T

10、2lock R1.lock R2.lock R2等待等待.lock R1等待等待9. 試述活鎖的產(chǎn)生原因和解決方法。答：活鎖產(chǎn)生的原因：當(dāng)一系列封鎖不能按照其先后順序執(zhí)行時, 就可能導(dǎo)致一些事務(wù)無限期等待某個封鎖, 從而導(dǎo)致活鎖。避免活鎖的簡單方法是采用先來先服務(wù)的策略。當(dāng)多個事務(wù)請求封鎖同一數(shù)據(jù)對象時 ,封鎖子系統(tǒng)按請求封鎖的先后次序?qū)κ聞?wù)排隊, 數(shù)據(jù)對象上的鎖一旦釋放就批準(zhǔn)申請隊列中第一個事務(wù)獲得鎖。10. 請給出預(yù)防死鎖的若干方法。答：在數(shù)據(jù)庫中 , 產(chǎn)生死鎖的原因是兩個或多個事務(wù)都已封鎖了一些數(shù)據(jù)對象, 然后又都請求已被其他事務(wù)封鎖的數(shù)據(jù)加鎖, 從而出現(xiàn)死等待。防止死鎖的發(fā)生其實就是要

11、破壞產(chǎn)生死鎖的條件。預(yù)防死鎖通常有兩種方法：(1) 一次封鎖法 , 要求每個事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖, 否則就不能繼續(xù)執(zhí)行；(2) 順序封鎖法 , 預(yù)先對數(shù)據(jù)對象規(guī)定一個封鎖順序, 所有事務(wù)都按這個順序?qū)嵭蟹怄i。不過 , 預(yù)防死鎖的策略不大適合數(shù)據(jù)庫系統(tǒng)的特點, 具體原因可參見概論。11. 請給出檢測死鎖發(fā)生的一種方法, 當(dāng)發(fā)生死鎖后如何解除死鎖答：數(shù)據(jù)庫系統(tǒng)一般采用允許死鎖發(fā)生,DBMS檢測到死鎖后加以解除的方法 。DBMS中診斷死鎖的方法與操作系統(tǒng)類似, 一般使用超時法或事務(wù)等待圖法。超時法是： 如果一個事務(wù)的等待時間超過了規(guī)定的時限，就認(rèn)為發(fā)生了死鎖。超時法實現(xiàn)簡單, 但有

12、可能誤判死鎖, 事務(wù)因其他原因長時間等待超過時限時, 系統(tǒng)會誤認(rèn)為發(fā)生了死鎖。若時限設(shè)置得太長, 又不能及時發(fā)現(xiàn)死鎖發(fā)生。DBMS并發(fā)控制子系統(tǒng)檢測到死鎖后, 就要設(shè)法解除。通常采用的方法是選擇一個處理死鎖代價最小的事務(wù), 將其撤消 , 釋放此事務(wù)持有的所有鎖, 使其他事務(wù)得以繼續(xù)運行下去。當(dāng)然, 對撤銷的事務(wù)所執(zhí)行的數(shù)據(jù)修改操作必須加以恢復(fù)。12. 什么樣的并發(fā)調(diào)度是正確的調(diào)度答：可串行化(Sertalizable)的調(diào)度是正確的調(diào)度?？纱谢恼{(diào)度的定義：多個事務(wù)的并發(fā)執(zhí)行是正確的, 當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行執(zhí)行它們時的結(jié)果相同, 稱這種調(diào)度策略為可串行化的調(diào)度。13. 設(shè) T1,T

13、2,T3 是如下的 3 個事務(wù)：T1:A:=A+2;T2:A:=A*2;T3:A:=A*2;設(shè) A 的初值為 0。(1) 若這 3 個事務(wù)允許并行執(zhí)行 , 則有多少可能的正確結(jié)果 , 請一一列舉出來。答 :A 的最終結(jié)果可能有 2、 4、 8、 16。因為串行執(zhí)行次序有 T1 T2 T3 、T1 T3 T2 、 T2 T1 T3 、 T2 T3 T1 、T3 T1 T2 、 T3 T2 T1 。對應(yīng)的執(zhí)行結(jié)果是 16、 8、 4、 2、 4、 2。(2) 請給出一個可串行化的調(diào)度 , 并給出執(zhí)行結(jié)果答：T1T2T3slock AY=A=OUnlock AXlock ASlock AA=Y+2等

14、待寫回 A(=2)等待Unlock A等待Y=A=2Unlock AXlock ASlock AA=Y*2寫回Unlock AY=A=4Unlock AXlock AA(=4)等待等待等待寫回A(=16)Unlock A最后結(jié)果 A 為 16, 是可串行化的調(diào)度。(3) 請給出一個非串行化的調(diào)度 , 并給出執(zhí)行結(jié)果。答：T1T2T3Slock AY=A=0Unlock ASlock AY=A=0Xlock A等待Unlock AA=Y+2寫回A(=2)Slock AUnlock A等待Y=A=2Unlock AXlock AXlock A等待A=Y*2等待寫回 A(=4)等待Unlock AA

15、=Y*2寫回 A(=0)Unlock A最后結(jié)果 A為 0,為非串行化的調(diào)度。(4) 若這 3 個事務(wù)都遵守兩段鎖協(xié)議 , 請給出一個不產(chǎn)生死鎖的可串行化調(diào)度。答：T1T2T3Slock AY=A=OXlock AA=Y+2Slock A寫回 A(=2)Unlock AY=A=2Xlock A等待等待等待Slock AA=Y*2寫回Unlock AY=A=4Xlock AA=Y*2A(=4)等待等待等待寫回 A(=16)Unlock A(5) 若這 3 個事務(wù)都遵守兩段鎖協(xié)議 , 請給出一個產(chǎn)生死鎖的調(diào)度。答：T1 T2 T3 Slock AY=A=0 Slock AY=A=0Xlock A等

16、待Xlock A等待Slock AY=A=0Xlock A等待14. 試述兩段鎖協(xié)議的概念。答：兩段鎖協(xié)議是指所有事務(wù)必須分兩個階段對數(shù)據(jù)項加鎖和解鎖。? 在對任何數(shù)據(jù)進行讀、寫操作之前, 首先要申請并獲得對該數(shù)據(jù)的封鎖；? 在釋放一個封鎖之后, 事務(wù)不再申請和獲得任何其他封鎖。" 兩段 " 的含義是 , 事務(wù)分為兩個階段：第一階段是獲得封鎖 , 也稱為擴展階段 , 在這階段 , 事務(wù)可以申請獲得任何 數(shù)據(jù)項上的任何類型的鎖 , 但是不能釋放任何鎖；第二階段是釋放封鎖 , 也稱為收縮階段 , 在這階段 , 事務(wù)釋放已經(jīng)獲得的鎖 , 但是不能再申請任何鎖。15. 試證明 ,

17、若并發(fā)事務(wù)遵守兩段鎖協(xié)議 , 則對這些事務(wù)的并發(fā)調(diào)度是可串行化的。證明：首先以兩個并發(fā)事務(wù)T1 和 T2 為例 , 存在多個并發(fā)事務(wù)的情形可以類推。根據(jù)可串行化定義可知, 事務(wù)不可串行化只可能發(fā)生在下列兩種情況：(1) 事務(wù) T1 寫某個數(shù)據(jù)對象A,T2 讀或?qū)?A；(2) 事務(wù) Tl 讀或?qū)懩硞€數(shù)據(jù)對象A,T2 寫 A。下面稱A 為潛在沖突對象。設(shè) T1和T2 訪問的潛在沖突的公共對象為A1,A2, ,An。不失一般性, 假設(shè)這組潛在沖突對象中X=A1,A2,Ai均符合情況(1) 。Y=Ai+1,An符合所情況(2) 。xX,T1需要X1ock xT2 需要Slock x或Xlock x1) 1) 如果操作先執(zhí)行 , 則 T1 獲得鎖 ,T2 等待由于遵守兩段鎖協(xié)議,T1 在成功獲得X 和 Y 中全部對象及非潛在沖突對象的鎖后, 才會釋放鎖。這時如果否則 ,T1wX 或 Y,T2 已獲得 w 的鎖