數(shù)據(jù)庫系統(tǒng)概論 第十一章并發(fā)控制

《數(shù)據(jù)庫系統(tǒng)概論 第十一章并發(fā)控制》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)庫系統(tǒng)概論 第十一章并發(fā)控制（120頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、An Introduction to Database System 數(shù) 據(jù) 庫 系 統(tǒng) 概 論An Introduction to Database System第 十 一 章 并 發(fā) 控 制 An Introduction to Database System 問 題 的 產(chǎn) 生v多 用 戶 數(shù) 據(jù) 庫 系 統(tǒng) 的 存 在 允 許 多 個(gè) 用 戶 同 時(shí) 使 用 的 數(shù) 據(jù) 庫 系 統(tǒng)n飛 機(jī) 定 票 數(shù) 據(jù) 庫 系 統(tǒng)n銀 行 數(shù) 據(jù) 庫 系 統(tǒng) 特 點(diǎn) ： 在 同 一 時(shí) 刻 并 發(fā) 運(yùn) 行 的 事 務(wù) 數(shù) 可 達(dá) 數(shù) 百 個(gè) An Introduction to Database S

2、ystem 問 題 的 產(chǎn) 生 （ 續(xù) ）v不 同 的 多 事 務(wù) 執(zhí) 行 方 式 (1)事 務(wù) 串 行 執(zhí) 行 每 個(gè) 時(shí) 刻 只 有 一 個(gè) 事 務(wù) 運(yùn) 行 ， 其 他 事 務(wù)必 須 等 到 這 個(gè) 事 務(wù) 結(jié) 束 以 后 方 能 運(yùn) 行 不 能 充 分 利 用 系 統(tǒng) 資 源 ， 發(fā) 揮 數(shù) 據(jù) 庫 共享 資 源 的 特 點(diǎn) T1T2T3 事 務(wù) 的 串 行 執(zhí) 行 方 式 An Introduction to Database System 問 題 的 產(chǎn) 生 （ 續(xù) ）(2)交 叉 并 發(fā) 方 式 （ Interleaved Concurrency） 在 單 處 理 機(jī) 系 統(tǒng) 中

3、， 事 務(wù) 的 并 行 執(zhí) 行 是 這 些 并 行 事 務(wù)的 并 行 操 作 輪 流 交 叉 運(yùn) 行 單 處 理 機(jī) 系 統(tǒng) 中 的 并 行 事 務(wù) 并 沒 有 真 正 地 并 行 運(yùn) 行 ，但 能 夠 減 少 處 理 機(jī) 的 空 閑 時(shí) 間 ， 提 高 系 統(tǒng) 的 效 率 An Introduction to Database System 問 題 的 產(chǎn) 生 （ 續(xù) ） 事 務(wù) 的 交 叉 并 發(fā) 執(zhí) 行 方 式 An Introduction to Database System 問 題 的 產(chǎn) 生 （ 續(xù) ） (3)同 時(shí) 并 發(fā) 方 式 （ simultaneous concurre

4、ncy） 多 處 理 機(jī) 系 統(tǒng) 中 ， 每 個(gè) 處 理 機(jī) 可 以 運(yùn) 行 一 個(gè) 事 務(wù) ，多 個(gè) 處 理 機(jī) 可 以 同 時(shí) 運(yùn) 行 多 個(gè) 事 務(wù) ， 實(shí) 現(xiàn) 多 個(gè) 事 務(wù)真 正 的 并 行 運(yùn) 行 An Introduction to Database System 問 題 的 產(chǎn) 生 （ 續(xù) ）v事 務(wù) 并 發(fā) 執(zhí) 行 帶 來 的 問 題 會(huì) 產(chǎn) 生 多 個(gè) 事 務(wù) 同 時(shí) 存 取 同 一 數(shù) 據(jù) 的 情 況 可 能 會(huì) 存 取 和 存 儲(chǔ) 不 正 確 的 數(shù) 據(jù) ， 破 壞 事 務(wù) 一 致 性和 數(shù) 據(jù) 庫 的 一 致 性vDBMS必 須 提 供 并 發(fā) 控 制 機(jī) 制v并 發(fā)

5、 控 制 機(jī) 制 是 衡 量 一 個(gè) DBMS性 能 的 重 要 標(biāo) 志之 一 An Introduction to Database System 第 十 一 章 并 發(fā) 控 制11.1 并 發(fā) 控 制 概 述11.2 封 鎖11.3 活 鎖 和 死 鎖11.4 并 發(fā) 調(diào) 度 的 可 串 行 性11.5 兩 段 鎖 協(xié) 議11.6 封 鎖 的 粒 度11.7 小 結(jié) An Introduction to Database System 11.1 并 發(fā) 控 制 概 述v并 發(fā) 控 制 機(jī) 制 的 任 務(wù) 對(duì) 并 發(fā) 操 作 進(jìn) 行 正 確 調(diào) 度 保 證 事 務(wù) 的 隔 離 性 保 證 數(shù)

6、 據(jù) 庫 的 一 致 性 An Introduction to Database SystemT1的 修 改 被 T2覆 蓋 了 ！ 并 發(fā) 控 制 概 述 （ 續(xù) ）并 發(fā) 操 作 帶 來 數(shù) 據(jù) 的 不 一 致 性 實(shí) 例例 1飛 機(jī) 訂 票 系 統(tǒng) 中 的 一 個(gè) 活 動(dòng) 序 列 甲 售 票 點(diǎn) (甲 事 務(wù) )讀 出 某 航 班 的 機(jī) 票 余 額 A， 設(shè) A=16； 乙 售 票 點(diǎn) (乙 事 務(wù) )讀 出 同 一 航 班 的 機(jī) 票 余 額 A， 也 為 16； 甲 售 票 點(diǎn) 賣 出 一 張 機(jī) 票 ， 修 改 余 額 AA-1， 所 以 A為 15， 把 A寫 回?cái)?shù) 據(jù) 庫 ；

7、 乙 售 票 點(diǎn) 賣 出 三 張 機(jī) 票 ， 修 改 余 額 AA-1， 所 以 A為 15， 把 A寫 回?cái)?shù) 據(jù) 庫 n 結(jié) 果 明 明 賣 出 兩 張 機(jī) 票 ， 數(shù) 據(jù) 庫 中 機(jī) 票 余 額 只 減 少 1 An Introduction to Database System 并 發(fā) 控 制 概 述 （ 續(xù) ）v這 種 情 況 稱 為 數(shù) 據(jù) 庫 的 不 一 致 性 ， 是 由 并 發(fā) 操 作 引 起的 。v在 并 發(fā) 操 作 情 況 下 ， 對(duì) 甲 、 乙 兩 個(gè) 事 務(wù) 的 操 作 序 列 的調(diào) 度 是 隨 機(jī) 的 。v若 按 上 面 的 調(diào) 度 序 列 執(zhí) 行 ， 甲 事 務(wù) 的

8、 修 改 就 被 丟 失 。 原 因 ： 第 4步 中 乙 事 務(wù) 修 改 A并 寫 回 后 覆 蓋 了 甲 事 務(wù)的 修 改 An Introduction to Database System 并 發(fā) 控 制 概 述 （ 續(xù) ）v并 發(fā) 操 作 帶 來 的 數(shù) 據(jù) 不 一 致 性 丟 失 修 改 （ Lost Update） 不 可 重 復(fù) 讀 （ Non-repeatable Read） 讀 “ 臟 ” 數(shù) 據(jù) （ Dirty Read）v記 號(hào) R(x):讀 數(shù) 據(jù) x W(x):寫 數(shù) 據(jù) x An Introduction to Database System 1. 丟 失 修 改

9、v丟 失 修 改 是 指 兩 個(gè) 事 務(wù) T1和 T2從 數(shù) 據(jù) 庫 中 讀 入 同一 數(shù) 據(jù) 并 修 改 ， 事 務(wù) T2的 提 交 結(jié) 果 破 壞 了 事 務(wù) T1提 交 的 結(jié) 果 ， 導(dǎo) 致 T1的 修 改 被 丟 失 。v上 面 飛 機(jī) 訂 票 例 子 就 屬 此 類 An Introduction to Database System 丟 失 修 改 （ 續(xù) ）T1 T2 R(A)=16 R(A)=16 AA-1 W(A)=15 AA-3W(A)=13 丟 失 修 改T1的 修 改 被 T2覆 蓋 了 ！ An Introduction to Database System 2.

10、不 可 重 復(fù) 讀v不 可 重 復(fù) 讀 是 指 事 務(wù) T1讀 取 數(shù) 據(jù) 后 ， 事 務(wù) T2 執(zhí) 行 更 新 操 作 ， 使 T1無 法 再 現(xiàn) 前 一 次 讀 取 結(jié) 果 。 An Introduction to Database System 不 可 重 復(fù) 讀 （ 續(xù) ）v事 務(wù) 1讀 取 某 一 數(shù) 據(jù) 后 ：v1。 事 務(wù) 2對(duì) 其 做 了 修 改 ， 當(dāng) 事 務(wù) 1再 次 讀 該 數(shù) 據(jù)時(shí) ， 得 到 與 前 一 次 不 同 的 值 。v2. 事 務(wù) 2刪 除 了 其 中 部 分 記 錄 ， 當(dāng) 事 務(wù) 1再 次 讀 取數(shù) 據(jù) 時(shí) ， 發(fā) 現(xiàn) 某 些 記 錄 神 密 地 消 失

11、 了 。v3. 事 務(wù) 2插 入 了 一 些 記 錄 ， 當(dāng) 事 務(wù) 1再 次 按 相 同 條件 讀 取 數(shù) 據(jù) 時(shí) ， 發(fā) 現(xiàn) 多 了 一 些 記 錄 。后 兩 種 不 可 重 復(fù) 讀 有 時(shí) 也 稱 為 幻 影 現(xiàn) 象 （ phantom row） An Introduction to Database System 不 可 重 復(fù) 讀 （ 續(xù) ）n T1讀 取 B=100進(jìn) 行 運(yùn) 算n T2讀 取 同 一 數(shù) 據(jù) B， 對(duì) 其 進(jìn)行 修 改 后 將 B=200寫 回 數(shù) 據(jù)庫 。n T1為 了 對(duì) 讀 取 值 校 對(duì) 重 讀 B，B已 為 200， 與 第 一 次 讀 取 值不 一 致

12、 T1 T2 R(A)=50 R(B)=100求 和 =150 R(B)=100BB*2(B)=200 R(A)=50R(B)=200 和 =250(驗(yàn) 算 不 對(duì) )不 可 重 復(fù) 讀 例 如 ： An Introduction to Database System 3. 讀 “ 臟 ” 數(shù) 據(jù) 讀 “ 臟 ” 數(shù) 據(jù) 是 指 ：n事 務(wù) T1修 改 某 一 數(shù) 據(jù) ， 并 將 其 寫 回 磁 盤n事 務(wù) T2讀 取 同 一 數(shù) 據(jù) 后 ， T1由 于 某 種 原 因 被 撤 銷n這 時(shí) T1已 修 改 過 的 數(shù) 據(jù) 恢 復(fù) 原 值 ， T2讀 到 的 數(shù) 據(jù) 就 與數(shù) 據(jù) 庫 中 的 數(shù)

13、 據(jù) 不 一 致nT2讀 到 的 數(shù) 據(jù) 就 為 “ 臟 ” 數(shù) 據(jù) ， 即 不 正 確 的 數(shù) 據(jù) An Introduction to Database System 讀 “ 臟 ” 數(shù) 據(jù) （ 續(xù) ）T1 T2 R(C)=100 CC*2 W(C)=200 R(C)=200 ROLLBACK C恢 復(fù) 為 100例 如 讀 “ 臟 ” 數(shù) 據(jù) n T1將 C值 修 改 為 200，T2讀 到 C為 200n T1由 于 某 種 原 因 撤銷 ， 其 修 改 作 廢 ， C恢 復(fù) 原 值 100n 這 時(shí) T2讀 到 的 C為200， 與 數(shù) 據(jù) 庫 內(nèi) 容不 一 致 ， 就 是 “ 臟

14、”數(shù) 據(jù) An Introduction to Database System 并 發(fā) 控 制 概 述 （ 續(xù) ）v數(shù) 據(jù) 不 一 致 性 ： 由 于 并 發(fā) 操 作 破 壞 了 事 務(wù) 的 隔 離 性v并 發(fā) 控 制 就 是 要 用 正 確 的 方 式 調(diào) 度 并 發(fā) 操 作 ， 使 一個(gè) 用 戶 事 務(wù) 的 執(zhí) 行 不 受 其 他 事 務(wù) 的 干 擾 ， 從 而 避 免造 成 數(shù) 據(jù) 的 不 一 致 性 An Introduction to Database System 并 發(fā) 控 制 概 述 （ 續(xù) ）v并 發(fā) 控 制 的 主 要 技 術(shù) 有 封 鎖 (Locking) 時(shí) 間 戳 (

15、Timestamp) 樂 觀 控 制 法v商 用 的 DBMS一 般 都 采 用 封 鎖 方 法 An Introduction to Database System 第 十 一 章 并 發(fā) 控 制11.1 并 發(fā) 控 制 概 述11.2 封 鎖11.3 活 鎖 和 死 鎖11.4 并 發(fā) 調(diào) 度 的 可 串 行 性11.5 兩 段 鎖 協(xié) 議11.6 封 鎖 的 粒 度11.7 小 結(jié) An Introduction to Database System 11.2 封 鎖v什 么 是 封 鎖v基 本 封 鎖 類 型v鎖 的 相 容 矩 陣 An Introduction to Databas

16、e System 什 么 是 封 鎖v封 鎖 就 是 事 務(wù) T在 對(duì) 某 個(gè) 數(shù) 據(jù) 對(duì) 象 （ 例 如 表 、 記 錄等 ） 操 作 之 前 ， 先 向 系 統(tǒng) 發(fā) 出 請(qǐng) 求 ， 對(duì) 其 加 鎖v加 鎖 后 事 務(wù) T就 對(duì) 該 數(shù) 據(jù) 對(duì) 象 有 了 一 定 的 控 制 ， 在事 務(wù) T釋 放 它 的 鎖 之 前 ， 其 它 的 事 務(wù) 不 能 更 新 此 數(shù)據(jù) 對(duì) 象 。 An Introduction to Database System 基 本 封 鎖 類 型v一 個(gè) 事 務(wù) 對(duì) 某 個(gè) 數(shù) 據(jù) 對(duì) 象 加 鎖 后 究 竟 擁 有 什 么 樣的 控 制 由 封 鎖 的 類 型 決

17、 定 。v基 本 封 鎖 類 型 排 它 鎖 （ Exclusive Locks， 簡 記 為 X鎖 ） 共 享 鎖 （ Share Locks， 簡 記 為 S鎖 ） An Introduction to Database System 排 它 鎖v排 它 鎖 又 稱 為 寫 鎖v若 事 務(wù) T對(duì) 數(shù) 據(jù) 對(duì) 象 A加 上 X鎖 ， 則 只 允 許 T讀 取 和修 改 A， 其 它 任 何 事 務(wù) 都 不 能 再 對(duì) A加 任 何 類 型 的鎖 ， 直 到 T釋 放 A上 的 鎖v保 證 其 他 事 務(wù) 在 T釋 放 A上 的 鎖 之 前 不 能 再 讀 取 和修 改 A An Introd

18、uction to Database System 共 享 鎖v共 享 鎖 又 稱 為 讀 鎖v若 事 務(wù) T對(duì) 數(shù) 據(jù) 對(duì) 象 A加 上 S鎖 ， 則 其 它 事 務(wù) 只 能再 對(duì) A加 S鎖 ， 而 不 能 加 X鎖 ， 直 到 T釋 放 A上 的 S鎖v保 證 其 他 事 務(wù) 可 以 讀 A， 但 在 T釋 放 A上 的 S鎖 之 前不 能 對(duì) A做 任 何 修 改 An Introduction to Database System 鎖 的 相 容 矩 陣Y=Yes， 相 容 的 請(qǐng) 求N=No， 不 相 容 的 請(qǐng) 求 T2 T1 X S -X N N YS N Y Y- Y Y Y

19、 An Introduction to Database System 鎖 的 相 容 矩 陣 （ 續(xù) ）在 鎖 的 相 容 矩 陣 中 ：v最 左 邊 一 列 表 示 事 務(wù) T1已 經(jīng) 獲 得 的 數(shù) 據(jù) 對(duì) 象 上 的 鎖 的 類 型 ，其 中 橫 線 表 示 沒 有 加 鎖 。v最 上 面 一 行 表 示 另 一 事 務(wù) T2對(duì) 同 一 數(shù) 據(jù) 對(duì) 象 發(fā) 出 的 封 鎖 請(qǐng)求 。vT2的 封 鎖 請(qǐng) 求 能 否 被 滿 足 用 矩 陣 中 的 Y和 N表 示 Y表 示 事 務(wù) T2的 封 鎖 要 求 與 T1已 持 有 的 鎖 相 容 ， 封 鎖 請(qǐng) 求 可以 滿 足 N表 示 T2

20、的 封 鎖 請(qǐng) 求 與 T1已 持 有 的 鎖 沖 突 ， T2的 請(qǐng) 求 被 拒絕 An Introduction to Database System 續(xù) ： 封 鎖 協(xié) 議v在 運(yùn) 用 X鎖 和 S鎖 對(duì) 數(shù) 據(jù) 對(duì) 象 加 鎖 時(shí) ， 需 要 約 定 一 些 規(guī) 則 ：封 鎖 協(xié) 議 （ Locking Protocol） 何 時(shí) 申 請(qǐng) X鎖 或 S鎖 持 鎖 時(shí) 間 、 何 時(shí) 釋 放v 不 同 的 封 鎖 協(xié) 議 ， 在 不 同 的 程 度 上 為 并 發(fā) 操 作 的 正 確 調(diào) 度 提 供 一 定 的 保 證v常 用 的 封 鎖 協(xié) 議 ： 三 級(jí) 封 鎖 協(xié) 議 An Int

21、roduction to Database System 1級(jí) 封 鎖 協(xié) 議v事 務(wù) T在 修 改 數(shù) 據(jù) R之 前 必 須 先 對(duì) 其 加 X鎖 ， 直 到事 務(wù) 結(jié) 束 才 釋 放 正 常 結(jié) 束 （ COMMIT） 非 正 常 結(jié) 束 （ ROLLBACK）v1級(jí) 封 鎖 協(xié) 議 可 防 止 丟 失 修 改v在 1級(jí) 封 鎖 協(xié) 議 中 ， 如 果 是 讀 數(shù) 據(jù) ， 不 需 要 加 鎖 的 ， 所 以它 不 能 保 證 可 重 復(fù) 讀 和 不 讀 “ 臟 ” 數(shù) 據(jù) 。 An Introduction to Database System 1級(jí) 封 鎖 協(xié) 議T1 T2 Xlock

22、A 獲 得 讀 A=16 AA-1 寫 回 A=15 Commit Unlock A Xlock A等 待等 待等 待等 待獲 得 Xlock A讀 A=15AA-1寫 回 A=14CommitUnlock A 沒 有 丟 失 修 改 n 事 務(wù) T1在 讀 A進(jìn) 行 修 改之 前 先 對(duì) A加 X鎖n 當(dāng) T2再 請(qǐng) 求 對(duì) A加 X鎖 時(shí)被 拒 絕n T2只 能 等 待 T1釋 放 A上的 鎖 后 T2獲 得 對(duì) A的 X鎖n 這 時(shí) T2讀 到 的 A已 經(jīng) 是T1更 新 過 的 值 15n T2按 此 新 的 A值 進(jìn) 行 運(yùn)算 ， 并 將 結(jié) 果 值 A=14送回 到 磁 盤 。 避

23、 免 了 丟 失T1的 更 新 。 An Introduction to Database System 1級(jí) 封 鎖 協(xié) 議 讀 A=15 Xlock A 獲 得 讀 A=16 AA-1 寫 回 A=15 Rollback Unlock A T2T1 讀 “ 臟 ” 數(shù) 據(jù) An Introduction to Database System 1級(jí) 封 鎖 協(xié) 議 Xlock B 獲 得 讀 B=100 BB*2 寫 回 B=200 Commit Unlock B 讀 A=50 讀 B=100 求 和 =150 讀 A=50 讀 B=200 求 和 =250 (驗(yàn) 算 不 對(duì) ) T2T1

24、不 可 重 復(fù) 讀 An Introduction to Database System 2級(jí) 封 鎖 協(xié) 議v1級(jí) 封 鎖 協(xié) 議 +事 務(wù) T在 讀 取 數(shù) 據(jù) R前 必 須 先 加 S鎖 ，讀 完 后 即 可 釋 放 S鎖v2級(jí) 封 鎖 協(xié) 議 可 以 防 止 丟 失 修 改 和 讀 “ 臟 ” 數(shù) 據(jù) 。v在 2級(jí) 封 鎖 協(xié) 議 中 ， 由 于 讀 完 數(shù) 據(jù) 后 即 可 釋 放 S鎖 ，所 以 它 不 能 保 證 可 重 復(fù) 讀 。 An Introduction to Database System 2級(jí) 封 鎖 協(xié) 議不 可 重 復(fù) 讀 Sclock A 獲 得 讀 A=50

25、Unlock A Sclock B 獲 得 讀 B=100 Unlock B 求 和 =150 Xlock B等 待等 待獲 得 Xlock B讀 B=100BB*2 寫 回 B=200CommitUnlock BT2T1 Sclock A 獲 得 讀 A=50 Unlock A Sclock B 獲 得 讀 B=200 Unlock B 求 和 =250 (驗(yàn) 算 不 對(duì) ) T2T1 (續(xù) ) An Introduction to Database System 3級(jí) 封 鎖 協(xié) 議v1級(jí) 封 鎖 協(xié) 議 + 事 務(wù) T在 讀 取 數(shù) 據(jù) R之 前 必 須 先 對(duì)其 加 S鎖 ， 直 到

26、事 務(wù) 結(jié) 束 才 釋 放v3級(jí) 封 鎖 協(xié) 議 可 防 止 丟 失 修 改 、 讀 臟 數(shù) 據(jù) 和 不 可 重 復(fù) 讀 。 An Introduction to Database System 3級(jí) 封 鎖 協(xié) 議T1 T2 Slock A 讀 A=50 Slock B 讀 B=100 求 和 =150 讀 A=50 讀 B=100 求 和 =150 Commit Unlock A Unlock B Xlock B等 待等 待等 待 等 待等 待等 待等 待等 待獲 得 Xlock B讀 B=100BB*2寫 回 B=200CommitUnlock B 可 重 復(fù) 讀 n 事 務(wù) T1在 讀

27、 A， B之 前 ， 先 對(duì) A，B加 S鎖n 其 他 事 務(wù) 只 能 再 對(duì) A， B加 S鎖 ，而 不 能 加 X鎖 ， 即 其 他 事 務(wù) 只 能讀 A， B， 而 不 能 修 改n 當(dāng) T2為 修 改 B而 申 請(qǐng) 對(duì) B的 X鎖 時(shí)被 拒 絕 只 能 等 待 T1釋 放 B上 的 鎖n T1為 驗(yàn) 算 再 讀 A， B， 這 時(shí) 讀 出 的B仍 是 100， 求 和 結(jié) 果 仍 為 150， 即可 重 復(fù) 讀n T1結(jié) 束 才 釋 放 A， B上 的 S鎖 。 T2才 獲 得 對(duì) B的 X鎖 An Introduction to Database System 3級(jí) 封 鎖 協(xié) 議T

28、1 T2 Xlock C 讀 C= 100 CC*2 寫 回 C=200 ROLLBACK (C恢 復(fù) 為 100) Unlock C Slock C等 待等 待等 待等 待獲 得 Slock C讀 C=100Commit CUnlock C 不 讀 “ 臟 ” 數(shù) 據(jù) n 事 務(wù) T1在 對(duì) C進(jìn) 行 修 改 之 前 ， 先對(duì) C加 X鎖 ， 修 改 其 值 后 寫 回 磁 盤n T2請(qǐng) 求 在 C上 加 S鎖 ， 因 T1已 在 C上 加 了 X鎖 ， T2只 能 等 待n T1因 某 種 原 因 被 撤 銷 ， C恢 復(fù) 為原 值 100n T1釋 放 C上 的 X鎖 后 T2獲 得 C

29、上 的S鎖 ， 讀 C=100。 避 免 了 T2讀“ 臟 ” 數(shù) 據(jù) An Introduction to Database System 4 封 鎖 協(xié) 議 小 結(jié)v三 級(jí) 協(xié) 議 的 主 要 區(qū) 別 什 么 操 作 需 要 申 請(qǐng) 封 鎖 何 時(shí) 釋 放 鎖 （ 即 持 鎖 時(shí) 間 ） An Introduction to Database System 封 鎖 協(xié) 議 小 結(jié) (續(xù) ) An Introduction to Database System 使 用 封 鎖 機(jī) 制 解 決 讀 “ 臟 ” 數(shù) 據(jù) 問題T1 T2 Xlock CR(C)=100CC*2W(C)=200 Sl

30、ock C等 待 ROLLBACK 等 待 (C恢 復(fù) 為 100) 等 待Unlock C 等 待 獲 得 Slock CR(C)=100 Commit CUnlock C例 n 事 務(wù) T1在 對(duì) C進(jìn) 行 修 改 之 前 ， 先對(duì) C加 X鎖 ， 修 改 其 值 后 寫 回 磁 盤n T2請(qǐng) 求 在 C上 加 S鎖 ， 因 T1已 在 C上 加 了 X鎖 ， T2只 能 等 待n T1因 某 種 原 因 被 撤 銷 ， C恢 復(fù) 為原 值 100n T1釋 放 C上 的 X鎖 后 T2獲 得 C上 的S鎖 ， 讀 C=100。 避 免 了 T2讀“ 臟 ” 數(shù) 據(jù)不 讀 “ 臟 ” 數(shù)

31、據(jù) An Introduction to Database System 第 十 一 章 并 發(fā) 控 制11.1 并 發(fā) 控 制 概 述11.2 封 鎖11.3 活 鎖 和 死 鎖11.4 并 發(fā) 調(diào) 度 的 可 串 行 性11.5 兩 段 鎖 協(xié) 議11.6 封 鎖 的 粒 度11.7 小 結(jié) An Introduction to Database System 11.3 活 鎖 和 死 鎖v封 鎖 技 術(shù) 可 以 有 效 地 解 決 并 行 操 作 的 一 致 性 問 題 ，但 也 帶 來 一 些 新 的 問 題 死 鎖 活 鎖 An Introduction to Database Sy

32、stem 11.3.1 活 鎖v事 務(wù) T1封 鎖 了 數(shù) 據(jù) Rv事 務(wù) T2又 請(qǐng) 求 封 鎖 R， 于 是 T2等 待 。vT3也 請(qǐng) 求 封 鎖 R， 當(dāng) T1釋 放 了 R上 的 封 鎖 之 后 系 統(tǒng) 首 先 批準(zhǔn) 了 T3的 請(qǐng) 求 ， T2仍 然 等 待 。vT4又 請(qǐng) 求 封 鎖 R， 當(dāng) T3釋 放 了 R上 的 封 鎖 之 后 系 統(tǒng) 又 批 準(zhǔn)了 T4的 請(qǐng) 求 vT2有 可 能 永 遠(yuǎn) 等 待 ， 這 就 是 活 鎖 的 情 形 An Introduction to Database System 活 鎖 （ 續(xù) ） 活 鎖 An Introduction to Da

33、tabase System 如 何 避 免 活 鎖 （ 續(xù) ）v采 用 先 來 先 服 務(wù) 的 策 略當(dāng) 多 個(gè) 事 務(wù) 請(qǐng) 求 封 鎖 同 一 數(shù) 據(jù) 對(duì) 象 時(shí) 按 請(qǐng) 求 封 鎖 的 先 后 次 序 對(duì) 這 些 事 務(wù) 排 隊(duì) 該 數(shù) 據(jù) 對(duì) 象 上 的 鎖 一 旦 釋 放 ， 首 先 批 準(zhǔn) 申 請(qǐng) 隊(duì) 列 中 第一 個(gè) 事 務(wù) 獲 得 鎖 An Introduction to Database System 11.3.2 死 鎖v事 務(wù) T1封 鎖 了 數(shù) 據(jù) R1vT2封 鎖 了 數(shù) 據(jù) R2vT1又 請(qǐng) 求 封 鎖 R2， 因 T2已 封 鎖 了 R2， 于 是 T1等 待 T2

34、釋 放R2上 的 鎖v接 著 T2又 申 請(qǐng) 封 鎖 R1， 因 T1已 封 鎖 了 R1， T2也 只 能 等 待T1釋 放 R1上 的 鎖v這 樣 T1在 等 待 T2， 而 T2又 在 等 待 T1， T1和 T2兩 個(gè) 事 務(wù) 永遠(yuǎn) 不 能 結(jié) 束 ， 形 成 死 鎖 An Introduction to Database System 死 鎖 （ 續(xù) ）T1 T2lock R1 Lock R2 Lock R2. 等 待 等 待 Lock R 1等 待 等 待等 待 等 待死 鎖 An Introduction to Database System 解 決 死 鎖 的 方 法兩 類 方

35、 法1. 預(yù) 防 死 鎖2. 死 鎖 的 診 斷 與 解 除 An Introduction to Database System 1. 死 鎖 的 預(yù) 防v產(chǎn) 生 死 鎖 的 原 因 是 兩 個(gè) 或 多 個(gè) 事 務(wù) 都 已 封 鎖 了 一 些 數(shù) 據(jù) 對(duì)象 ， 然 后 又 都 請(qǐng) 求 對(duì) 已 為 其 他 事 務(wù) 封 鎖 的 數(shù) 據(jù) 對(duì) 象 加 鎖 ，從 而 出 現(xiàn) 死 等 待 。v預(yù) 防 死 鎖 的 發(fā) 生 就 是 要 破 壞 產(chǎn) 生 死 鎖 的 條 件 An Introduction to Database System 死 鎖 的 預(yù) 防 （ 續(xù) ）預(yù) 防 死 鎖 的 方 法v 一 次

36、封 鎖 法v 順 序 封 鎖 法 An Introduction to Database System (1)一 次 封 鎖 法v要 求 每 個(gè) 事 務(wù) 必 須 一 次 將 所 有 要 使 用 的 數(shù) 據(jù) 全部 加 鎖 ， 否 則 就 不 能 繼 續(xù) 執(zhí) 行v存 在 的 問 題 降 低 系 統(tǒng) 并 發(fā) 度 擴(kuò) 大 封 鎖 范 圍 將 以 后 要 用 到 的 全 部 數(shù) 據(jù) 加 鎖 ， 勢(shì) 必 擴(kuò) 大 了封 鎖 的 范 圍 ， 從 而 降 低 了 系 統(tǒng) 的 并 發(fā) 度 An Introduction to Database System (1)一 次 封 鎖 法v難 于 事 先 精 確 確 定

37、 封 鎖 對(duì) 象 數(shù) 據(jù) 庫 中 數(shù) 據(jù) 是 不 斷 變 化 的 ， 原 來 不 要 求 封 鎖 的 數(shù) 據(jù) ，在 執(zhí) 行 過 程 中 可 能 會(huì) 變 成 封 鎖 對(duì) 象 ， 所 以 很 難 事 先 精確 地 確 定 每 個(gè) 事 務(wù) 所 要 封 鎖 的 數(shù) 據(jù) 對(duì) 象 解 決 方 法 ： 將 事 務(wù) 在 執(zhí) 行 過 程 中 可 能 要 封 鎖 的 數(shù) 據(jù) 對(duì)象 全 部 加 鎖 ， 這 就 進(jìn) 一 步 降 低 了 并 發(fā) 度 。 An Introduction to Database System (2)順 序 封 鎖 法v順 序 封 鎖 法 是 預(yù) 先 對(duì) 數(shù) 據(jù) 對(duì) 象 規(guī) 定 一 個(gè) 封

38、鎖 順 序 ，所 有 事 務(wù) 都 按 這 個(gè) 順 序 實(shí) 行 封 鎖 。v順 序 封 鎖 法 存 在 的 問 題 維 護(hù) 成 本 數(shù) 據(jù) 庫 系 統(tǒng) 中 可 封 鎖 的 數(shù) 據(jù) 對(duì) 象 極 其 眾 多 ， 并且 隨 數(shù) 據(jù) 的 插 入 、 刪 除 等 操 作 而 不 斷 地 變 化 ，要 維 護(hù) 這 樣 極 多 而 且 變 化 的 資 源 的 封 鎖 順 序 非常 困 難 ， 成 本 很 高 An Introduction to Database System (2)順 序 封 鎖 法 難 于 實(shí) 現(xiàn) 事 務(wù) 的 封 鎖 請(qǐng) 求 可 以 隨 著 事 務(wù) 的 執(zhí) 行 而 動(dòng) 態(tài) 地決 定 ， 很

39、 難 事 先 確 定 每 一 個(gè) 事 務(wù) 要 封 鎖 哪 些 對(duì)象 ， 因 此 也 就 很 難 按 規(guī) 定 的 順 序 去 施 加 封 鎖 。 例 ： 規(guī) 定 數(shù) 據(jù) 對(duì) 象 的 封 鎖 順 序 為 A,B,C,D,E。事 務(wù) T3起 初 要 求 封 鎖 數(shù) 據(jù) 對(duì) 象 B,C,E， 但 當(dāng) 它封 鎖 了 B,C后 ， 才 發(fā) 現(xiàn) 還 需 要 封 鎖 A， 這 樣 就 破壞 了 封 鎖 順 序 . An Introduction to Database System 死 鎖 的 預(yù) 防 （ 續(xù) ）v結(jié) 論 在 操 作 系 統(tǒng) 中 廣 為 采 用 的 預(yù) 防 死 鎖 的 策 略 并 不 很 適

40、合數(shù) 據(jù) 庫 的 特 點(diǎn) DBMS在 解 決 死 鎖 的 問 題 上 更 普 遍 采 用 的 是 診 斷 并 解 除死 鎖 的 方 法 An Introduction to Database System 死 鎖 的 預(yù) 防 （ 續(xù) ）v允 許 死 鎖 發(fā) 生v解 除 死 鎖 由 DBMS的 并 發(fā) 控 制 子 系 統(tǒng) 定 期 檢 測(cè) 系 統(tǒng) 中 是 否 存在 死 鎖 一 旦 檢 測(cè) 到 死 鎖 ， 就 要 設(shè) 法 解 除 An Introduction to Database System 2. 死 鎖 的 診 斷 與 解 除v死 鎖 的 診 斷n超 時(shí) 法n事 務(wù) 等 待 圖 法 An I

41、ntroduction to Database System (1) 超 時(shí) 法v如 果 一 個(gè) 事 務(wù) 的 等 待 時(shí) 間 超 過 了 規(guī) 定 的 時(shí) 限 ， 就 認(rèn) 為發(fā) 生 了 死 鎖v優(yōu) 點(diǎn) ： 實(shí) 現(xiàn) 簡 單v缺 點(diǎn) 有 可 能 誤 判 死 鎖 時(shí) 限 若 設(shè) 置 得 太 長 ， 死 鎖 發(fā) 生 后 不 能 及 時(shí) 發(fā) 現(xiàn) An Introduction to Database System (2)等 待 圖 法v用 事 務(wù) 等 待 圖 動(dòng) 態(tài) 反 映 所 有 事 務(wù) 的 等 待 情 況 事 務(wù) 等 待 圖 是 一 個(gè) 有 向 圖 G=(T， U) T為 結(jié) 點(diǎn) 的 集 合 ， 每

42、個(gè) 結(jié) 點(diǎn) 表 示 正 運(yùn) 行 的 事 務(wù) U為 邊 的 集 合 ， 每 條 邊 表 示 事 務(wù) 等 待 的 情 況 若 T 1等 待 T2， 則 T1， T2之 間 劃 一 條 有 向 邊 ， 從 T1指 向 T2 An Introduction to Database System 等 待 圖 法 （ 續(xù) ） 事 務(wù) 等 待 圖n 圖 (a)中 ， 事 務(wù) T1等 待 T2， T2等 待 T1， 產(chǎn) 生 了 死 鎖n 圖 (b)中 ， 事 務(wù) T1等 待 T2， T2等 待 T3， T3等 待 T4， T4又 等 待T1， 產(chǎn) 生 了 死 鎖 n 圖 (b)中 ， 事 務(wù) T3可 能 還

43、等 待 T2， 在 大 回 路 中 又 有 小 的 回 路 An Introduction to Database System 等 待 圖 法 （ 續(xù) ）v并 發(fā) 控 制 子 系 統(tǒng) 周 期 性 地 （ 比 如 每 隔 數(shù) 秒 ） 生 成事 務(wù) 等 待 圖 ， 檢 測(cè) 事 務(wù) 。 如 果 發(fā) 現(xiàn) 圖 中 存 在 回 路 ，則 表 示 系 統(tǒng) 中 出 現(xiàn) 了 死 鎖 。 An Introduction to Database System 死 鎖 的 診 斷 與 解 除 （ 續(xù) ）v解 除 死 鎖 選 擇 一 個(gè) 處 理 死 鎖 代 價(jià) 最 小 的 事 務(wù) ， 將 其 撤 消 釋 放 此 事

44、務(wù) 持 有 的 所 有 的 鎖 ， 使 其 它 事 務(wù) 能 繼續(xù) 運(yùn) 行 下 去 An Introduction to Database System 第 十 一 章 并 發(fā) 控 制11.1 并 發(fā) 控 制 概 述11.2 封 鎖11.3 活 鎖 和 死 鎖11.4 并 發(fā) 調(diào) 度 的 可 串 行 性11.5 兩 段 鎖 協(xié) 議11.6 封 鎖 的 粒 度11.7 小 結(jié) An Introduction to Database System 11.4 并 發(fā) 調(diào) 度 的 可 串 行 性vDBMS對(duì) 并 發(fā) 事 務(wù) 不 同 的 調(diào) 度 可 能 會(huì) 產(chǎn) 生 不 同 的結(jié) 果一 、 什 么 樣 的

45、并 發(fā) 操 作 調(diào) 度 是 正 確 的二 、 如 何 保 證 并 發(fā) 操 作 的 調(diào) 度 是 正 確 的 An Introduction to Database System 一 、 什 么 樣 的 并 發(fā) 操 作 調(diào) 度 是 正 確 的v計(jì) 算 機(jī) 系 統(tǒng) 對(duì) 并 行 事 務(wù) 中 并 行 操 作 的 調(diào) 度 是 的隨 機(jī) 的 ， 而 不 同 的 調(diào) 度 可 能 會(huì) 產(chǎn) 生 不 同 的 結(jié) 果 。v將 所 有 事 務(wù) 串 行 起 來 的 調(diào) 度 策 略 一 定 是 正 確 的調(diào) 度 策 略 。 如 果 一 個(gè) 事 務(wù) 運(yùn) 行 過 程 中 沒 有 其 他 事 務(wù) 在 同 時(shí) 運(yùn) 行 ，也 就 是

46、 說 它 沒 有 受 到 其 他 事 務(wù) 的 干 擾 ， 那 么 就 可 以認(rèn) 為 該 事 務(wù) 的 運(yùn) 行 結(jié) 果 是 正 常 的 或 者 預(yù) 想 的 An Introduction to Database System 一 、 什 么 樣 的 并 發(fā) 操 作 調(diào) 度 是 正 確 的v以 不 同 的 順 序 串 行 執(zhí) 行 事 務(wù) 也 有 可 能 會(huì) 產(chǎn)生 不 同 的 結(jié) 果 ， 但 由 于 不 會(huì) 將 數(shù) 據(jù) 庫 置 于不 一 致 狀 態(tài) ， 所 以 都 可 以 認(rèn) 為 是 正 確 的 。v 幾 個(gè) 事 務(wù) 的 并 行 執(zhí) 行 是 正 確 的 ， 當(dāng) 且 僅 當(dāng)其 結(jié) 果 與 按 某 一 次

47、 序 串 行 地 執(zhí) 行 它 們 時(shí) 的結(jié) 果 相 同 。 這 種 并 行 調(diào) 度 策 略 稱 為 可 串 行化 （ Serializable） 的 調(diào) 度 。 An Introduction to Database System 11.4.1 可 串 行 化 調(diào) 度v可 串 行 性 是 并 行 事 務(wù) 正 確 性 的 唯 一 準(zhǔn) 則v可 串 行 化 (Serializable)調(diào) 度n 多 個(gè) 事 務(wù) 的 并 發(fā) 執(zhí) 行 是 正 確 的 ， 當(dāng) 且 僅 當(dāng) 其 結(jié) 果 與按 某 一 次 序 串 行 地 執(zhí) 行 這 些 事 務(wù) 時(shí) 的 結(jié) 果 相 同v可 串 行 性 (Serializabil

48、ity) 是 并 發(fā) 事 務(wù) 正 確 調(diào) 度 的 準(zhǔn) 則 一 個(gè) 給 定 的 并 發(fā) 調(diào) 度 ， 當(dāng) 且 僅 當(dāng) 它 是 可 串 行 化 的 ，才 認(rèn) 為 是 正 確 調(diào) 度 An Introduction to Database System 可 串 行 化 調(diào) 度 （ 續(xù) ）例 現(xiàn) 在 有 兩 個(gè) 事 務(wù) ， 分 別 包 含 下 列 操 作 ： 事 務(wù) T1： 讀 B； A=B+1； 寫 回 A 事 務(wù) T2： 讀 A； B=A+1； 寫 回 B假 設(shè) A的 初 值 為 2， B的 初 值 為 2。現(xiàn) 給 出 對(duì) 這 兩 個(gè) 事 務(wù) 不 同 的 調(diào) 度 策 略 An Introductio

49、n to Database System 可 串 行 化 調(diào) 度 （ 續(xù) ） 對(duì) 這 兩 個(gè) 事 務(wù) 的 不 同 調(diào) 度 策 略 串 行 執(zhí) 行串 行 調(diào) 度 策 略 1串 行 調(diào) 度 策 略 2 交 錯(cuò) 執(zhí) 行不 可 串 行 化 的 調(diào) 度可 串 行 化 的 調(diào) 度 An Introduction to Database System 串 行 化 調(diào) 度 ,正 確 的 調(diào) 度T1 T2Slock BY=R(B)=2Unlock BXlock AA=Y+1=3W(A)Unlock A Slock AX=R(A)=3Unlock A Xlock BB=X+1=4W(B)Unlock B串 行 調(diào)

50、 度 (a) n 假 設(shè) A、 B的 初 值 均 為 2。n 按 T1T2次 序 執(zhí) 行 結(jié) 果為 A=3， B=4 n 串 行 調(diào) 度 策 略 ,正 確 的 調(diào) 度 An Introduction to Database System 串 行 化 調(diào) 度 ,正 確 的 調(diào) 度T1 T2Slock AX=R(A)=2Unlock AXlock BB=X+1=3W(B)Unlock BSlock BY=R(B)=3 Unlock BXlock AA=Y+1=4W(A)Unlock A 串 行 調(diào) 度 (b) n 假 設(shè) A、 B的 初 值 均 為 2。n T2T1次 序 執(zhí) 行 結(jié) 果 為 B=

51、3，A=4 n 串 行 調(diào) 度 策 略 ,正 確 的 調(diào) 度 An Introduction to Database System 不 可 串 行 化 調(diào) 度 ， 錯(cuò) 誤 的 調(diào) 度T1 T2Slock BY=R(B)=2 Slock AX=R(A)=2Unlock B Unlock AXlock AA=Y+1=3W(A) Xlock BB=X+1=3W(B)Unlock A Unlock B不 可 串 行 化 的 調(diào) 度 n 執(zhí) 行 結(jié) 果 與 (a)、 (b)的 結(jié)果 都 不 同n 是 錯(cuò) 誤 的 調(diào) 度 An Introduction to Database System 可 串 行 化

52、 調(diào) 度 ， 正 確 的 調(diào) 度T1 T2Slock BY=R(B)=2Unlock BXlock A Slock AA=Y+1=3 等 待W(A) 等 待Unlock A 等 待X=R(A)=3 Unlock AXlock BB=X+1=4W(B)Unlock B可 串 行 化 的 調(diào) 度 n 執(zhí) 行 結(jié) 果 與 串 行 調(diào) 度(a)的 執(zhí) 行 結(jié) 果 相 同n 是 正 確 的 調(diào) 度 An Introduction to Database System 11.4 并 發(fā) 調(diào) 度 的 可 串 行 性vDBMS對(duì) 并 發(fā) 事 務(wù) 不 同 的 調(diào) 度 可 能 會(huì) 產(chǎn) 生 不 同 的結(jié) 果一 、

53、什 么 樣 的 并 發(fā) 操 作 調(diào) 度 是 正 確 的二 、 如 何 保 證 并 發(fā) 操 作 的 調(diào) 度 是 正 確 的 An Introduction to Database System 二 、 如 何 保 證 并 發(fā) 操 作 的 調(diào) 度 是 正 確 的v為 了 保 證 并 行 操 作 的 正 確 性 ， DBMS的 并 行 控 制機(jī) 制 必 須 提 供 一 定 的 手 段 來 保 證 調(diào) 度 是 可 串 行 化的 。v從 理 論 上 講 ， 在 某 一 事 務(wù) 執(zhí) 行 時(shí) 禁 止 其 他 事 務(wù) 執(zhí)行 的 調(diào) 度 策 略 一 定 是 可 串 行 化 的 調(diào) 度 ， 這 也 是 最簡 單

54、的 調(diào) 度 策 略 ， 但 這 種 方 法 實(shí) 際 上 是 不 可 行 的 ，因 為 它 使 用 戶 不 能 充 分 共 享 數(shù) 據(jù) 庫 資 源 。 An Introduction to Database System 如 何 保 證 并 發(fā) 操 作 的 調(diào) 度 是 正 確 的 （ 續(xù) ）v保 證 并 發(fā) 操 作 調(diào) 度 正 確 性 的 方 法 封 鎖 方 法 ： 兩 段 鎖 （ Two-Phase Locking， 簡 稱 2PL）協(xié) 議 時(shí) 標(biāo) 方 法 樂 觀 方 法 An Introduction to Database System 11.4.2 沖 突 可 串 行 化 調(diào) 度v可 串

55、 行 化 調(diào) 度 的 充 分 條 件 一 個(gè) 調(diào) 度 Sc在 保 證 沖 突 操 作 的 次 序 不 變 的 情 況 下 ， 通 過 交換 兩 個(gè) 事 務(wù) 不 沖 突 操 作 的 次 序 得 到 另 一 個(gè) 調(diào) 度 Sc， 如 果 Sc是 串 行 的 ， 稱 調(diào) 度 Sc為 沖 突 可 串 行 化 的 調(diào) 度 一 個(gè) 調(diào) 度 是 沖 突 可 串 行 化 ， 一 定 是 可 串 行 化 的 調(diào) 度 An Introduction to Database System 沖 突 可 串 行 化 調(diào) 度 （ 續(xù) ）沖 突 操 作v沖 突 操 作 是 指 不 同 的 事 務(wù) 對(duì) 同 一 個(gè) 數(shù) 據(jù) 的

56、讀 寫 操 作 和 寫 寫操 作 Ri (x)與 Wj(x) /* 事 務(wù) Ti讀 x， Tj寫 x*/ Wi(x)與 Wj(x) /* 事 務(wù) Ti寫 x， Tj寫 x*/v其 他 操 作 是 不 沖 突 操 作v不 同 事 務(wù) 的 沖 突 操 作 和 同 一 事 務(wù) 的 兩 個(gè) 操 作 不 能 交 換(Swap) An Introduction to Database System 沖 突 可 串 行 化 調(diào) 度 （ 續(xù) ） 例 今 有 調(diào) 度Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) 把 w2(A)與 r1(B)w1(B)交 換 ， 得 到

57、： r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B) 再 把 r2(A)與 r1(B)w1(B)交 換 ： Sc2 r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) Sc2等 價(jià) 于 一 個(gè) 串 行 調(diào) 度 T1， T2， Sc1沖 突 可 串 行 化 的 調(diào) 度 An Introduction to Database System 沖 突 可 串 行 化 調(diào) 度 （ 續(xù) ）v沖 突 可 串 行 化 調(diào) 度 是 可 串 行 化 調(diào) 度 的 充 分 條 件 ， 不 是 必 要條 件 。 還 有 不 滿 足 沖 突 可 串 行 化 條

58、 件 的 可 串 行 化 調(diào) 度 。 例 有 3個(gè) 事 務(wù) T1=W1(Y)W1(X)， T2=W2(Y)W2(X)， T3=W3(X) 調(diào) 度 L1=W1(Y)W1(X)W2(Y)W2(X) W3(X)是 一 個(gè) 串 行 調(diào) 度 。 調(diào) 度 L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不 滿 足 沖 突 可 串 行化 。 但 是 調(diào) 度 L2是 可 串 行 化 的 ， 因 為 L2執(zhí) 行 的 結(jié) 果 與 調(diào) 度L1相 同 ， Y的 值 都 等 于 T2的 值 ， X的 值 都 等 于 T3的 值 An Introduction to Database System 第 十 一 章

59、 并 發(fā) 控 制11.1 并 發(fā) 控 制 概 述11.2 封 鎖11.3 活 鎖 和 死 鎖11.4 并 發(fā) 調(diào) 度 的 可 串 行 性11.5 兩 段 鎖 協(xié) 議11.6 封 鎖 的 粒 度11.7 小 結(jié) An Introduction to Database System 11.5 兩 段 鎖 協(xié) 議v封 鎖 協(xié) 議 運(yùn) 用 封 鎖 方 法 時(shí) ， 對(duì) 數(shù) 據(jù) 對(duì) 象 加 鎖 時(shí) 需 要 約 定 一 些 規(guī)則 何 時(shí) 申 請(qǐng) 封 鎖 持 鎖 時(shí) 間 何 時(shí) 釋 放 封 鎖 等v兩 段 封 鎖 協(xié) 議 (Two-Phase Locking， 簡 稱 2PL)是 最 常用 的 一 種 封 鎖

60、 協(xié) 議 ， 理 論 上 證 明 使 用 兩 段 封 鎖 協(xié) 議 產(chǎn)生 的 是 可 串 行 化 調(diào) 度 An Introduction to Database System 兩 段 鎖 協(xié) 議 （ 續(xù) ）v兩 段 鎖 協(xié) 議 指 所 有 事 務(wù) 必 須 分 兩 個(gè) 階 段 對(duì) 數(shù) 據(jù) 項(xiàng) 加 鎖 和 解 鎖 n在 對(duì) 任 何 數(shù) 據(jù) 進(jìn) 行 讀 、 寫 操 作 之 前 ， 事 務(wù) 首 先 要 獲 得對(duì) 該 數(shù) 據(jù) 的 封 鎖n 在 釋 放 一 個(gè) 封 鎖 之 后 ， 事 務(wù) 不 再 申 請(qǐng) 和 獲 得 任 何 其 他封 鎖 An Introduction to Database System

61、兩 段 鎖 協(xié) 議 （ 續(xù) ）v“兩 段 ” 鎖 的 含 義事 務(wù) 分 為 兩 個(gè) 階 段 第 一 階 段 是 獲 得 封 鎖 ， 也 稱 為 擴(kuò) 展 階 段事 務(wù) 可 以 申 請(qǐng) 獲 得 任 何 數(shù) 據(jù) 項(xiàng) 上 的 任 何 類 型 的 鎖 ， 但 是 不 能 釋 放 任何 鎖 第 二 階 段 是 釋 放 封 鎖 ， 也 稱 為 收 縮 階 段 事 務(wù) 可 以 釋 放 任 何 數(shù) 據(jù) 項(xiàng) 上 的 任 何 類 型 的 鎖 ， 但 是 不 能 再 申 請(qǐng) 任 何鎖 An Introduction to Database System 兩 段 鎖 協(xié) 議 （ 續(xù) ）例事 務(wù) Ti遵 守 兩 段 鎖

62、協(xié) 議 ， 其 封 鎖 序 列 是 ：Slock A Slock B Xlock C Unlock B Unlock A Unlock C；| 擴(kuò) 展 階 段 | | 收 縮 階 段 |事 務(wù) Tj不 遵 守 兩 段 鎖 協(xié) 議 ， 其 封 鎖 序 列 是 ： Slock A Unlock A Slock B Xlock C Unlock C Unlock B； An Introduction to Database System 兩 段 鎖 協(xié) 議 （ 續(xù) ）事 務(wù) T1 事 務(wù) T2Slock(A)R(A=260) Slock(C)R(C=300)Xlock(A)W(A=160) Xloc

63、k( C )W(C=250)Slock(A) Slock(B) 等 待R(B=1000) 等 待Xlock(B) 等 待W(B=1100) 等 待Unlock(A) 等 待R(A=160)Xlock(A)Unlock(B) W(A=210)Unlock( C )遵 守 兩 段 鎖 協(xié) 議 的 可 串 行 化 調(diào) 度 n 左 圖 的 調(diào) 度 是 遵 守 兩 段 鎖 協(xié) 議的 ， 因 此 一 定 是 一 個(gè) 可 串 行 化調(diào) 度 。 An Introduction to Database System 兩 段 鎖 協(xié) 議 （ 續(xù) ）v并 行 執(zhí) 行 的 所 有 事 務(wù) 均 遵 守 兩 段 鎖 協(xié)

64、議 ， 則 對(duì) 這些 事 務(wù) 的 所 有 并 行 調(diào) 度 策 略 都 是 可 串 行 化 的 。 所 有 遵 守 兩 段 鎖 協(xié) 議 的 事 務(wù) ， 其 并 行 執(zhí) 行 的 結(jié) 果一 定 是 正 確 的v事 務(wù) 遵 守 兩 段 鎖 協(xié) 議 是 可 串 行 化 調(diào) 度 的 充 分 條 件 ，而 不 是 必 要 條 件v可 串 行 化 的 調(diào) 度 中 ， 不 一 定 所 有 事 務(wù) 都 必 須 符 合兩 段 鎖 協(xié) 議 。 An Introduction to Database System 兩 段 鎖 協(xié) 議 （ 續(xù) ）v T1Slock B讀 B=2Y=BXlock A A=Y+1寫 回 A=

65、3Unlock BUnlock A T2 Slock A 等 待 等 待 等 待 等 待 等 待Slock A讀 A=3 Y=A Xlock BB=Y+1寫 回 B=4Unlock BUnlock A T1Slock B讀 B=2Y=BUnlock BXlock A A=Y+1寫 回 A=3Unlock A T2 Slock A等 待等 待等 待等 待Slock A讀 A=3X=AUnlock AXlock BB=X+1寫 回 B=4Unlock B (a) 遵 守 兩 段 鎖 協(xié) 議 (b) 不 遵 守 兩 段 鎖 協(xié) 議 T1Slock B讀 B=2Y=BUnlock BXlock AA=

66、Y+1寫 回 A=3Unlock A T2 Slock A讀 A=2X=AUnlock AXlock B等 待Xlock BB=X+1寫 回 B=3Unlock B (c) 不 遵 守 兩 段 鎖 協(xié) 議 An Introduction to Database System 兩 段 鎖 協(xié) 議 （ 續(xù) ）v兩 段 鎖 協(xié) 議 與 防 止 死 鎖 的 一 次 封 鎖 法 一 次 封 鎖 法 要 求 每 個(gè) 事 務(wù) 必 須 一 次 將 所 有 要 使 用 的 數(shù)據(jù) 全 部 加 鎖 ， 否 則 就 不 能 繼 續(xù) 執(zhí) 行 ， 因 此 一 次 封 鎖 法遵 守 兩 段 鎖 協(xié) 議 但 是 兩 段 鎖 協(xié) 議 并 不 要 求 事 務(wù) 必 須 一 次 將 所 有 要 使 用的 數(shù) 據(jù) 全 部 加 鎖 ， 因 此 遵 守 兩 段 鎖 協(xié) 議 的 事 務(wù) 可 能 發(fā)生 死 鎖 An Introduction to Database System 兩 段 鎖 協(xié) 議 （ 續(xù) ）例 遵 守 兩 段 鎖 協(xié) 議 的 事 務(wù) 發(fā) 生 死 鎖T1Slock BR(B)=2 Xlock A等 待等 待 T2 Sl