【正文】 ol simultaneously) 1） 需常存取多個關(guān)系的大量元組時宜采用 DB級粒度； 2） 需常存取單個關(guān)系大量元組時宜采用關(guān)系級粒度； 3） 需常存取單個關(guān)系少量元組時宜采用元組級粒度； 4） 一般不采用屬性級粒度； 5） 物理單元一般不宜采用 。 （ Locking protocol） 1) 概念 （ 何謂封鎖協(xié)議 ） —— 申請 、 持有和釋放鎖的規(guī)則 。 2) 目的 —— 實現(xiàn)正確的并發(fā)操作調(diào)度 。 3) 類別 ① 支持一致性維護的 三級封鎖協(xié)議 ； ② 支持并行調(diào)度可串行化的 兩段鎖協(xié)議 ； ③ 避免死鎖協(xié)議 。 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 三級封鎖協(xié)議 1． 1級封鎖協(xié)議 1） 策略 事務(wù) Ti在修改數(shù)據(jù) Di之前須先對 Di加 X鎖 ， 直到事務(wù) Ti結(jié)束（ mit/rollback） 才釋放 。 2） 功能 防止丟失修改； 保證 Ti可恢復 （ 若意外終止 ， 則 rollback后才可釋放 ） 。 3） 問題 : 不能防止不可重復讀和讀 ? 臟 ? 數(shù)據(jù) 。 （ 1級協(xié)議僅對修改操作 ， 若讀則不加鎖 ） 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 遵循一級封鎖協(xié)議的一種調(diào)度 T1 T2 T1 T2 T1 T2 1)Xlock(A)= T讀 A=16 A=50 B=100 Xlock(C)=T C=100 2） Xlock(A)=F C:=2*C=200 3)A:=A1=15 Xlock(S)=T S:=A+B=150 B=200 C=200 4)Xlock(A)= F ROLLBACK 5） COMMIT COMMIT UNLOCK（ C） 6)Xlock(A)= F Unlock（ B） 7） Unlock（ A） A=50 B=200 8） Xlock(A)=T 讀 A＝ 15 Xlock(S1)=T S1:=A+B=250 9) A:=A1=14 10） COMMIT S！＝ S1 寫丟失避免了！ 不可重復讀 讀“臟” 數(shù)據(jù) 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 2． 2級封鎖協(xié)議 1) 策略 1級封鎖協(xié)議加上事務(wù) Ti在讀取 Di之前必須對 Di加 S鎖 ， 讀完后即可釋放該 S鎖 。 2) 功能 防止丟失修改； 防止讀臟 。 3)問題 :不能防止讀不可重復 （ 讀完即釋放 ， 重讀時可能其它事務(wù)對之修改 ） 。 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 遵循二級封鎖協(xié)議的一種調(diào)度 T1 T2 T1 T2 1) SLOCK(A)=.T. A=50 SLOCK(B)=.T. B=100 Xlock(C)=.T. C=100C:=2*C=200 2) Unlock(A) Unlock(B) SLOCK(C)=.F. 3) Xlock(S)=.T. S:=A+B=150 ROLLBACK 4) Xlock（ B） =.T. B=100B=B*2=200 SLOCK(C)=.F. 5) COMMIT UNLOCK(C) 6) Unlock（ B） SLOCK(C)=.T 7) SLOCK(A)=.T. SLOCK(B)=.T. A=50 B=200 Unlock(A) Unlock(B) C=100 8) 9) Xlock(S1)=.T. S1:=A+B=250 S?。?S1 不可重復讀不能避免 讀“臟”數(shù)據(jù)避免了 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 3． 3級封鎖協(xié)議 1) 策略 在 1級封鎖協(xié)議上加上事務(wù) Ti讀 Di前須先對 Di加 S鎖 ， 直至 Ti結(jié)束后才釋放該 S鎖 。 2) 功能 防止丟失修改； 防止讀 ? 臟 ? ； 防止讀不可重復 。 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 遵循三級封鎖協(xié)議的一種調(diào)度 T1 T2 T1 T2 1) SLOCK(A)=.T. A=50 SLOCK(B)=.T. B=100 Xlock(C)=.T. C=100C:=2*C=200 2) Xlock（ B） =.F. SLOCK(C)=.F. 3) Xlock(S)=.T. S:=A+B=150 ROLLBACK 4) SLOCK(C)=.F. 5) Xlock(S1)=.T. A=50 B=100 S1:=A+B=150 COMMIT UNLOCK(C) 6) Unlock(A) Unlock(B) Unlock（ B） SLOCK(C)=.T 7) Xlock（ B） =.T. B=100 B=B*2=200 C=100 8) S＝ S1 可重復讀 讀“臟”數(shù)據(jù)避免了 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 三級封鎖協(xié)議的主要區(qū)別在于 何種操作需要申請封鎖 ， 以及獲得封鎖后何時釋放鎖 （ 持鎖時間 ） 。 分別采用三級封鎖協(xié)議中不同級別的協(xié)議 ， 得到的一致性保證是不同的 。 X鎖 S鎖 一致性保證 操作結(jié)束釋放 事務(wù)結(jié)束釋放 操作結(jié)束釋放 事務(wù)結(jié)束釋放 不丟失修改 不讀臟數(shù)據(jù) 可重復讀 一級 √ √ 二級 √ √ √ √ 三級 √ √ √ √ √ 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 死鎖 （ dead lock） 1． 含義 兩個或兩個以上事務(wù)均處于等待狀態(tài) ， 每個事務(wù)都在等待其中另一個事務(wù)封鎖的數(shù)據(jù) ， 導致任何事務(wù)都不能繼續(xù)執(zhí)行的現(xiàn)象稱為死鎖 。 2． 產(chǎn)生條件 ① 互斥 （ 排它性控制 ） ； ② 不可剝奪 （ 釋放鎖前 ， 其它事務(wù)不能剝奪 ） ； ③ 部分分配 （ 每次申請一部分 ， 申請新的鎖時 ， 又占用已 獲得者 ） ； ④ 環(huán)路 （ 循環(huán)鏈中 ， 每事務(wù)獲得的數(shù)據(jù)同時又被另一事務(wù) 請求 ） 。 下載 并發(fā)控制技術(shù) (technology of control simultaneously) T T2是兩個均須修改數(shù)據(jù) A、 B的事務(wù) ， 如果用戶程序遵循三級封鎖協(xié)議 ， 但申請鎖的順序是隨機的 ， 則有可能出現(xiàn)下列情況 —— 死鎖 T1 T2 XLOCK（ A）＝ .T. READA(A) XLOCK(B)=.T. READ(B) XLOCK(B)=.F.（等待） T1等待獲得 B的鎖 XLOCK(A)=.F.(等待） T2等待獲得 A的鎖 XLOCK(B)=.F.（等待） T1等待獲得 B的鎖 … （等待） XLOCK(A)=.F.(等待） T2等待獲得 A的鎖 … （等待） 一直等待下去 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 3． 預防 : —— 防止產(chǎn)生條件之一發(fā)生 （ 破壞產(chǎn)生死鎖的條件 ） ① 一次封鎖法 —— 每個事務(wù)事先一次獲得所需數(shù)據(jù)的全部鎖 。 如： T1獲得所有數(shù)據(jù) A、 B鎖 ， T1連續(xù)執(zhí)行 ， T2等待； T1執(zhí)行完后釋放 A、 B鎖 ， T2繼續(xù)執(zhí)行 ， 不會發(fā)生死鎖 。 特征： 簡單；無死鎖；粒度大；并發(fā)度低； 難以確定封鎖對象 。 （ DB數(shù)據(jù)變化 ， 不能預先確定封鎖對象 ， 只好擴大封鎖范圍 ） ② 順序封鎖法 —— 事務(wù)按預先確定的數(shù)據(jù)封鎖順序?qū)嵭蟹怄i 。 如： B樹從根開始 特征： 無死鎖； 順序難以確定； （ 運行中才發(fā)現(xiàn)要封鎖對象 ） 封鎖對象難以確定 。 下載 并發(fā)控制技術(shù) (technology of control simultaneously) ① 等待圖法 ； ? 構(gòu)造事務(wù)的等待圖； ? 周期性檢測該等待圖； ? 判斷存在回路否； ? 存在 ， 則撤消某一事務(wù)； ? 選擇一個處理死鎖代價最小的事務(wù) （ NP難度問題 ） ； ? 釋放所有鎖 ， 使其它事務(wù)繼續(xù)運行 。 ② 超時法 當一個事務(wù)的等待時間超過規(guī)定的時限 ， 則認為發(fā)生死鎖 ，撤銷該事務(wù) 。 ? 實現(xiàn)簡單 ? 存在問題 可能誤判死鎖；時限標準難以把握 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 活鎖 （ live lock） 含義 —— 事務(wù)因故永遠處于等待狀態(tài) 。 如： T1 T2 T3 T4 …Tn LOCK(R)=.T. LOCK(R)=.F. LOCK(R)=.F. LOCK(R)=.F. UNLOCK(R) LOCK(R)=.F. LOCK(R)=.T. LOCK(R)=.F. LOCK(R)=.F. … LOCK(R)=.F. LOCK(R)=.F. UNLOCK(R) LOCK(R)=.F. … （等待） LOCK(R)=.T. 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 預防方法 FCFS:First Come First Server先來先服務(wù) 。 對于事務(wù)有優(yōu)先級的系統(tǒng) ， 可設(shè)置一個最長等待時間 ， 與優(yōu)先級結(jié)合 ， 調(diào)度事務(wù)的執(zhí)行 。 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 兩段鎖協(xié)議 2PL： twophase locking 1． 可串行性 可串行性是事務(wù)并發(fā)執(zhí)行正確性的判斷準則 ， 給定一個并發(fā)調(diào)度 ， 當且僅當它是可串行化的 ， 才認為它是正確的 。 假設(shè)有兩個事務(wù)： T1 T2,數(shù)據(jù)庫中 A、 B的初值均為 2； T1：讀 B； A＝ B＋ 1；寫回 A T2：讀 A； B＝ A＋ 1；寫回 B 串行調(diào)度只有兩種可能： T1――T 2 結(jié)果為： A＝ 3， B＝ 4 T2――T 1 結(jié)果為： A＝ 4， B＝ 3 下載 并發(fā)控制技術(shù) (technology of control simultaneously) 下面給出幾種不同的調(diào)度策略 T1 T2 T1 T2 T1 T2 T1 T2 SLOCK(B) Y=B=2 Unlock(B) Xlock(A) A=Y+1=3 寫回 A Unlock(A) SLOCK(A) X=A=3 Unlock(A) Xlock(B) B=X+1=4 寫回 B Unlock(B) SLOCK(B) Y=B=3 Unlock(B) Xlock(A) A=Y+1=4 寫回 A Unlock(A) SLOCK(A) X=A=2 Unlock(A) Xlock(B) B=X+1=3 寫回 B Unlock(B) SLOCK(B) Y=