【文章內容簡介】 予 Ti 在 D上的 lockX write(D) end。 ? 所有鎖在提交 /夭折之后釋放 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 鎖管理器 ? 鎖管理器 可實現(xiàn)為單獨的進程 , 事務向它發(fā)送加鎖與釋放鎖請求 ? 鎖管理器通過發(fā)送鎖授予消息來回答鎖請求 (或死鎖時發(fā)送請事務回滾的消息 ) ? 請求事務等待 , 直至它的請求被回答 ? 鎖管理器維護一個稱為 鎖表 的數據結構來記錄授予的鎖和掛起的請求 ? 鎖表通常實現(xiàn)為以被鎖數據項的名字為索引的內存散列表 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 鎖管理器 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 鎖表 (Hash表實現(xiàn) , 高效 ) ? 黑色矩形表示已授予的鎖 , 白色矩形表示等待的請求 ? 鎖表記錄授予或請求的鎖的類型 ? 新請求加入到對某數據項的請求隊列的末尾 , 并且如果與所有以前的鎖兼容則被授予 ? 釋放鎖請求導致請求被刪除 , 并且其后的請求被檢查看看現(xiàn)在是否可以授予 ? 如果事務夭折 , 則該事務的所有等待或已批準的請求都被刪除 ? 鎖管理器可能保存每個事務持有的鎖的列表 , 以便對此高效地實現(xiàn) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 鎖表 (Hash表實現(xiàn) , 高效 ) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 基于圖的協(xié)議 ?基于圖的協(xié)議是相對于兩階段鎖協(xié)議的另一選擇 ?在所有數據項集合 D = {d1, d2 ,..., dh} 上定義一個偏序 ?(讀作 goes to 或 先于 ) ?如果 di ? dj 則存取 di 和 dj 的任何事務都必須先存取 di 后存取 dj ?集合 D可視為 有向無圈圖 (特例為樹 (有根的圖 ),表示數據的加工流程 )稱為數據庫圖 ?樹協(xié)議 是圖協(xié)議的一種簡單形式 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 樹協(xié)議 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 樹協(xié)議 ? 樹協(xié)議確保沖突可串行化且可避免死鎖 ? 樹協(xié)議中釋放鎖可比兩階段鎖協(xié)議更早發(fā)生 ?較短等待時間 , 增加并發(fā)度 ?協(xié)議無死鎖 , 不需回滾 ?事務的夭折仍然可能導致級聯(lián)回滾 (教材中對此有改進方法 ) ? 然而 , 在樹封鎖協(xié)議中 , 事務可能對它不需要存取的數據項加鎖 (可能誅連 (冤枉封鎖了 )太多子孫，誅九族 ) ?增加鎖開銷以及額外的等待時間 ?潛在的并發(fā)度降低 ? 樹協(xié)議可產生兩階段鎖協(xié)議不能產生的調度 , 反之亦然 . ?樹協(xié)議與 2PL沒絕對的強弱，各有用武之地 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 基于時間戳的協(xié)議 ? 兩種時間戳，分別對事務，對數據 ? 每個事務進入系統(tǒng)時被賦予一個時間戳，若一個老事務 Ti 具有時間戳 TS(Ti)，則一個新事務 Tj 被賦予時間戳 TS(Tj) 使得 TS(Ti) TS(Tj) ? 該協(xié)議管理并發(fā)執(zhí)行 , 使得時間戳決定了串行化次序 ? 為了保證這種行為 , 該協(xié)議為每個數據 Q維護兩個時間戳值 ?Wtimestamp(Q):成功執(zhí)行了 write(Q)的所有事務中的最大時間戳 ?Rtimestamp(Q):成功執(zhí)行了 read(Q)的所有事務中的最大時間戳 ? 注 :學習時間戳協(xié)議的方法 ?聽講課，有時不能立即反應和理解 ?需用例子，畫出時間軸，調度，需要細心體會 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 基于時間戳的協(xié)議 ? 假設事務 Ti 發(fā)出了 read(Q) 1. 若 TS(Ti) Wtimestamp(Q)，則 Ti 需要讀 Q 的已經被寫覆蓋了的一個值，因此， read 操作被拒絕， Ti 回滾 2. 若 TS(Ti) ? Rtimestamp(Q)，則 read 操作執(zhí)行，并且 Rtimestamp(Q) 置為 Rtimestamp(Q) 與 TS(Ti)的最大值 ? 時戳讀法則：讀舊回卷（ Roll Back原義，電影膠片卷回重放） 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 基于時間戳的協(xié)議 ? 假設事務 Ti 發(fā)出 write(Q): ?若 TS(Ti) Rtimestamp(Q), 則 Ti 要產生的 Q 值是過去曾需要的 , 而系統(tǒng)假設該值永遠不會產生 . 于是 , write 操作被拒絕 , Ti 回滾 ?若 TS(Ti) Wtimestamp(Q), 則 Ti 試圖寫一個過時的 Q值 ,因此 , 這個 write 操作被拒絕 , Ti 回滾 ?否則 ,執(zhí)行 write 操作 , 且 Wtimestamp(Q) 置為TS(Ti) ? 時間戳寫法則：寫先于讀或以舊蓋新，否則回卷 ? 結論 : 時間戳排序協(xié)議可確保任何沖突的 read 和 write 操作都能按照時間戳序執(zhí)行 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 協(xié)議例 ? 針對若干數據項的、時間戳為 1, 2, 3, 4, 5的事務的一個部分調度 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 時間戳排序協(xié)議的正確性 ? 時間戳保證了可串行性，有絕對時間戳，等候圖不會有循環(huán)（ 按資歷分配資源） ? 因此 , 優(yōu)先圖中沒有圈 ? 時間戳協(xié)議確保沒有死鎖 , 因為沒有事務會等待 ? 但是 , 調度可能導致級聯(lián)回滾 , 并且甚至可能不可恢復 ? 先生沒有晉升成功，后生晉升后也要作廢 較小時間 戳事務 較大時間 戳事務 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 可恢復性與避免級聯(lián)回滾 ? 時間戳排序協(xié)議的問題 : ?假如 Ti 夭折，但 Tj 已經讀了 Ti 所寫的一個數據項 ?則 Tj 必須夭折，若 Tj 已被允許較早提交，則該調度是不可恢復的 ?進一步，任何讀了 Tj 所寫的數據項的事務必須夭折 ?這可能導致級聯(lián)回滾：即一個回滾鏈 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 可恢復性與避免級聯(lián)回滾 ?解決方案 : 到 最后才寫 (at the end of its processing) （定先進 和 發(fā)獎金一起寫盤） ，且重新給時間戳 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition Thomas寫規(guī)則 ? 是時間戳排序協(xié)議的修正版本，其中過時 write 操作在某些情況下可以忽略 ? 當 Ti 試圖寫數據項 Q, 若 TS(Ti) Wtimestamp(Q), 則Ti 正試圖寫一個過時的 Q值。因此，不是按時間戳排序協(xié)議要求的那樣回滾 Ti，這個 write 操作可以忽略（其他情況下此協(xié)議與按時間戳排序協(xié)議相同） ? Thomas寫規(guī)則允許更多的潛在并發(fā)性，但不同于前面的協(xié)議，它允許做某些非沖突可串行化但是視圖可串行化的調度（即最終結果等價于某個串行調度） 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 基于有效性檢查的協(xié)議 ? 思路 :大膽先做，做了再驗證，即不要坐而論道，遲遲不動 ?事務 Ti 的執(zhí)行分成三個階段 : 1. 讀與執(zhí)行階段 : 事務 Ti 的 write操作只寫到臨時局部變量 2. 有效性檢查階段 : 事務 Ti 執(zhí)行“有效性檢查 ‖來決定局部變量的值是否可以寫到數據庫而不違反可串行化 3. 寫階段 : 若 Ti 通過有效性檢查 , 則更新數據庫 。 否則 Ti 回滾 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 基于有效性檢查的協(xié)議 ?并發(fā)執(zhí)行的各事務的三個階段可以交叉 , 但是每個事務必須按順序通過三個階段 ?也稱為 樂觀并發(fā)控制 ，因為事務執(zhí)行時完全寄希望于在有效性檢查時一切都好 ?樂觀控制，適合 ‖成多敗少 ‖的場合 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 基于有效性檢查的協(xié)議 ? 每個事務 Ti 有三個時間戳 ? Start(Ti): Ti 開始執(zhí)行的時間 ? Validation(Ti): Ti 進入有效性檢查階段的時間 ? Finish(Ti): Ti 完成寫階段的時間 ? 為了增加并發(fā)性，可串行化次序由有效性檢查時的時間戳次序決定 , 因此 TS(Ti) 被賦予 Validation(Ti)的值 ? 如果沖突的概率較小 , 本協(xié)議很有用 , 能帶來更大程度的并發(fā)性 , 這是因為可串行化次序不是預先決定的 , 只有相對較少的事務會被回滾 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 事務 Tj 的有效性檢查 ? 若對所有滿足 TS (Ti) TS (Tj)的 Ti 都有下列任一條件成立 : ?finish(Ti) start(Tj) ?start(Tj) finish(Ti) validation(Tj) 并且 Ti 所寫的數據項集合與 Tj 所讀的數據項集合不相交 則通過有效性檢查 , Tj 可以提交 。否則有效性檢查失敗 , Tj 夭折 ? 正確性說明 : 要么滿足第一個條件 , 沒有重疊的執(zhí)行 。 要么滿足第二個條件 , 并且 1. Tj 的寫不影響 Ti 的讀 , 因為它們發(fā)生在 Ti 開始讀操作之后 2. Ti 的寫不影響 Tj 的讀 , 因為 Tj 不讀 Ti 所寫的任何數據項 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 事務 Tj 的有效性檢查 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 有效性檢查所產生的調度 T14 T15 read(B) read(B) B: B50 read(A) A: A+50 read(A) (validate) display (A+B) (validate) write (B) write (A) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 多粒度 ? 允許數據項具有不同大小，從而定義一個數據粒度層次 , 小粒度嵌入在大粒度中 ? 可圖示為一棵樹 C (勿與樹封鎖協(xié)議混淆 )