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

1、第八章并發(fā)控制習(xí)題解答和解析1. 1. 在數(shù)據(jù)庫中為什么要并發(fā)控制答：數(shù)據(jù)庫是共享資源, 通常有許多個(gè)事務(wù)同時(shí)在運(yùn)行。當(dāng)多個(gè)事務(wù)并發(fā)地存取數(shù)據(jù)庫時(shí)就會產(chǎn)生同時(shí)讀取和/ 或修改同一數(shù)據(jù)的情況。若對并發(fā)操作不加控制就可能會存取和存儲不正確的數(shù)據(jù), 破壞數(shù)據(jù)庫的一致性。所以數(shù)據(jù)庫管理系統(tǒng)必須提供并發(fā)控制機(jī)制。2. 2. 并發(fā)操作可能會產(chǎn)生哪幾類數(shù)據(jù)不一致用什么方法能避免各種不一致的情況答：并發(fā)操作帶來的數(shù)據(jù)不一致性包括三類：丟失修改、不可重復(fù)讀和讀"臟" 數(shù)據(jù)。(1) 丟失修改 (LostUpdate) 兩個(gè)事務(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由于某種原因被撤銷, 這時(shí)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)中可以采用時(shí)間戳方法來進(jìn)行并發(fā)控制。3.3. 什么是封鎖答：封鎖就是事務(wù)對其加鎖 。加鎖后事務(wù)T 在對某個(gè)數(shù)據(jù)對象例如表、記錄等操作之前T 就對該數(shù)據(jù)對象有了一定的控制, 在事務(wù), 先向系統(tǒng)發(fā)出請求,T 釋放它的鎖之前, 其他的事務(wù)不能更新此數(shù)據(jù)對象。封鎖是實(shí)現(xiàn)并發(fā)控制的一個(gè)非常重要的技術(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. 如何用封鎖機(jī)制保證數(shù)據(jù)的一致性答：DBMS在對數(shù)據(jù)進(jìn)行讀 、寫操作之前首先對該數(shù)據(jù)執(zhí)行封鎖操作, 例如下圖中事務(wù)T1在對 A 進(jìn)行修改之前先對

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

6、定何時(shí)申請X 鎖或 S 鎖、何時(shí)釋放封鎖等。這些約定或者規(guī)則稱為封鎖協(xié)議(locking Protocol)。對封鎖方式約定不同的規(guī)則, 就形成了各種不同的封鎖協(xié)議、不同級別的封鎖協(xié)議 , 例如概論中介紹的三級封鎖協(xié)議, 三級協(xié)議的主要區(qū)別在于什么操作需要申請封鎖 , 何時(shí)申請封鎖以及何時(shí)釋放鎖( 即持鎖時(shí)間的長短) 。一級封鎖協(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é)議除防止了丟失修改, 還可進(jìn)一步防止讀" 臟 " 數(shù)據(jù)。在二級封鎖協(xié)議中, 由于讀完數(shù)據(jù)后立即釋放S 鎖 , 所以它不能保證可重復(fù)讀。在三級封鎖協(xié)議中, 無論是讀數(shù)據(jù)還是寫數(shù)據(jù)都加長鎖，即都要到事務(wù)結(jié)束才釋放封鎖。所以三級封鎖協(xié)議除防止了丟失修改和不讀" 臟 " 數(shù)據(jù)外 , 還進(jìn)一

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 有可能永遠(yuǎn)等待 , 這就是活鎖的情形?；铈i的含義是該等待事務(wù)等待時(shí)間太長，似乎被鎖住了, 實(shí)際上可能被激活。如果事務(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 兩個(gè)事務(wù)永遠(yuǎn)不能結(jié)束 , 形成死鎖。T1T

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

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

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

13、2,T3 是如下的 3 個(gè)事務(wù)：T1:A:=A+2;T2:A:=A*2;T3:A:=A*2;設(shè) A 的初值為 0。(1) 若這 3 個(gè)事務(wù)允許并行執(zhí)行 , 則有多少可能的正確結(jié)果 , 請一一列舉出來。答 :A 的最終結(jié)果可能有 2、 4、 8、 16。因?yàn)榇袌?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) 請給出一個(gè)可串行化的調(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) 請給出一個(gè)非串行化的調(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 個(gè)事務(wù)都遵守兩段鎖協(xié)議 , 請給出一個(gè)不產(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 個(gè)事務(wù)都遵守兩段鎖協(xié)議 , 請給出一個(gè)產(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ù)必須分兩個(gè)階段對數(shù)據(jù)項(xiàng)加鎖和解鎖。? 在對任何數(shù)據(jù)進(jìn)行讀、寫操作之前, 首先要申請并獲得對該數(shù)據(jù)的封鎖；? 在釋放一個(gè)封鎖之后, 事務(wù)不再申請和獲得任何其他封鎖。" 兩段 " 的含義是 , 事務(wù)分為兩個(gè)階段：第一階段是獲得封鎖 , 也稱為擴(kuò)展階段 , 在這階段 , 事務(wù)可以申請獲得任何 數(shù)據(jù)項(xiàng)上的任何類型的鎖 , 但是不能釋放任何鎖；第二階段是釋放封鎖 , 也稱為收縮階段 , 在這階段 , 事務(wù)釋放已經(jīng)獲得的鎖 , 但是不能再申請任何鎖。15. 試證明 ,

17、若并發(fā)事務(wù)遵守兩段鎖協(xié)議 , 則對這些事務(wù)的并發(fā)調(diào)度是可串行化的。證明：首先以兩個(gè)并發(fā)事務(wù)T1 和 T2 為例 , 存在多個(gè)并發(fā)事務(wù)的情形可以類推。根據(jù)可串行化定義可知, 事務(wù)不可串行化只可能發(fā)生在下列兩種情況：(1) 事務(wù) T1 寫某個(gè)數(shù)據(jù)對象A,T2 讀或?qū)?A；(2) 事務(wù) Tl 讀或?qū)懩硞€(gè)數(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 中全部對象及非潛在沖突對象的鎖后, 才會釋放鎖。這時(shí)如果否則 ,T1wX 或 Y,T2 已獲得 w 的鎖