1、數(shù)據(jù)庫系統(tǒng)概論,1,數(shù)據(jù)庫系統(tǒng)概論,并發(fā)控制,數(shù)據(jù)庫系統(tǒng)概論,2,7.1 事務的基本概念,一、什么是事務 二、如何定義事務 三、事務的特性,數(shù)據(jù)庫系統(tǒng)概論,3,一、什么是事務,事務(Transaction)是用戶定義的一個數(shù)據(jù)庫操作序列，這些操作要么全做，要么全不做，是一個不可分割的工作單位 事務和程序是兩個概念 在關系數(shù)據(jù)庫中，一個事務可以是一條SQL語句，一組SQL語句或整個程序 一個應用程序通常包含多個事務 事務是恢復和并發(fā)控制的基本單位,數(shù)據(jù)庫系統(tǒng)概論,4,二、如何定義事務,顯式定義方式 BEGIN TRANSACTION BEGIN TRANSACTION SQL 語句1 SQL 語

2、句1 SQL 語句2 SQL 語句2 。 。 COMMIT ROLLBACK 隱式方式 當用戶沒有顯式地定義事務時， DBMS按缺省規(guī)定自動劃分事務,數(shù)據(jù)庫系統(tǒng)概論,5,事務結束,COMMIT 事務正常結束 提交事務的所有操作（讀+更新） 事務中所有對數(shù)據(jù)庫的更新永久生效 ROLLBACK 事務異常終止 事務運行的過程中發(fā)生了故障，不能繼續(xù)執(zhí)行 回滾事務的所有更新操作 事務滾回到開始時的狀態(tài),數(shù)據(jù)庫系統(tǒng)概論,6,三、事務的特性(ACID特性),事務的ACID特性： 原子性（Atomicity） 一致性（Consistency） 隔離性（Isolation） 持續(xù)性（Durability ）,數(shù)

3、據(jù)庫系統(tǒng)概論,7,1. 原子性,事務是數(shù)據(jù)庫的邏輯工作單位 事務中包括的諸操作要么都做，要么都不做,數(shù)據(jù)庫系統(tǒng)概論,8,2. 一致性,事務執(zhí)行的結果必須是使數(shù)據(jù)庫從一個 一致性狀態(tài)變到另一個一致性狀態(tài) 一致性狀態(tài)： 數(shù)據(jù)庫中只包含成功事務提交的結果 不一致狀態(tài)： 數(shù)據(jù)庫中包含失敗事務的結果,數(shù)據(jù)庫系統(tǒng)概論,9,一致性與原子性,銀行轉帳：從帳號A中取出一萬元，存入帳號B。 定義一個事務，該事務包括兩個操作 這兩個操作要么全做，要么全不做 全做或者全不做，數(shù)據(jù)庫都處于一致性狀態(tài)。 如果只做一個操作，數(shù)據(jù)庫就處于不一致性狀態(tài)。,數(shù)據(jù)庫系統(tǒng)概論,10,3. 隔離性,對并發(fā)執(zhí)行而言 一個事務的執(zhí)行不能被

4、其他事務干擾 一個事務內(nèi)部的操作及使用的數(shù)據(jù)對其他并發(fā)事務是隔離的 并發(fā)執(zhí)行的各個事務之間不能互相干擾,數(shù)據(jù)庫系統(tǒng)概論,11,T1的修改被T2覆蓋了！,數(shù)據(jù)庫系統(tǒng)概論,12,4. 持續(xù)性,持續(xù)性也稱永久性（Permanence） 一個事務一旦提交，它對數(shù)據(jù)庫中數(shù)據(jù)的改變就應該是永久性的。 接下來的其他操作或故障不應該對其執(zhí)行結果有任何影響。,數(shù)據(jù)庫系統(tǒng)概論,13,事務的特性,保證事務ACID特性是事務處理的任務 破壞事務ACID特性的因素 多個事務并行運行時，不同事務的操作交叉執(zhí)行 事務在運行過程中被強行停止,數(shù)據(jù)庫系統(tǒng)概論,14,內(nèi)容提要,并發(fā)控制是數(shù)據(jù)庫管理系統(tǒng)的重要組成部分，通過本章的學

5、習，應重點掌握： 并發(fā)控制帶來的新問題 封鎖及封鎖協(xié)議 并發(fā)調(diào)度的可串行性 兩段鎖協(xié)議,數(shù)據(jù)庫系統(tǒng)概論,15,概述,在單處理機系統(tǒng)中，事務的并行執(zhí)行實際上是這些并行事務的并行操作輪流交叉運行，稱為交叉并發(fā)方式。 在多處理機系統(tǒng)中，每個處理機可以運行一個事務，多個處理機可以同時運行多個事務，實現(xiàn)多個事務真正的并行運行，稱為同時并發(fā)方式。 并發(fā)的目的： 改善系統(tǒng)的資源利用率 改善短事務的響應時間,數(shù)據(jù)庫系統(tǒng)概論,16,例子,飛機訂票系統(tǒng)中的活動序列： 甲售票點讀出某航班的機票余額A，設A=16 乙售票點讀出同一航班的機票余額A，也為16 甲售票點賣出一張機票，修改余額AA-1，把A=15寫回數(shù)據(jù)庫

6、 乙售票點也賣出一張機票，修改余額AA-1，把A=15寫回數(shù)據(jù)庫 這種情況稱為數(shù)據(jù)庫的不一致性，是由并發(fā)控制引起的。,數(shù)據(jù)庫系統(tǒng)概論,17,數(shù)據(jù)不一致性（1）,丟失修改：兩個事務T1和T2讀入同一數(shù)據(jù)并修改，T2提交的結果破壞了T1提交的結果，導致T1的修改被丟失?！皩憣憶_突” 讀“臟”數(shù)據(jù)：事務T1修改某一數(shù)據(jù)，并將其寫回磁盤，事務T2讀取同一數(shù)據(jù)后，T1由于某種原因被撤銷，這時T1已修改過的數(shù)據(jù)恢復原值，T2讀到的數(shù)據(jù)就與數(shù)據(jù)庫中的數(shù)據(jù)不一致，則T2讀到的數(shù)據(jù)就為“臟”數(shù)據(jù)，即不正確的數(shù)據(jù)。 “讀寫沖突”,數(shù)據(jù)庫系統(tǒng)概論,18,數(shù)據(jù)不一致性（2）,不可重復讀：事務T1讀取數(shù)據(jù)后，事務T2執(zhí)

7、行更新操作，使T1無法再現(xiàn)前一次的讀取結果。 “讀寫沖突” 產(chǎn)生原因：并發(fā)操作破壞了事務的隔離性 并發(fā)控制的任務：用正確的方式調(diào)度并發(fā)操作，使一個用戶事務的執(zhí)行不受其它事務的干擾，避免造成數(shù)據(jù)的不一致性。 并發(fā)控制的主要方法：封鎖,數(shù)據(jù)庫系統(tǒng)概論,19,三種數(shù)據(jù)不一致性,數(shù)據(jù)庫系統(tǒng)概論,20,封鎖（Locking）(1),封鎖：事務T在對某個數(shù)據(jù)對象操作之前，先向系統(tǒng)發(fā)出請求，對其加鎖。 封鎖類型：排它鎖（X鎖）和共享鎖（S鎖） 排它鎖：又稱寫鎖，若事務T對數(shù)據(jù)對象A加上X鎖，則只允許T讀取和修改A，其它任何事務都不能再對A加任何類型的鎖，直到T釋放A上的X鎖。 共享鎖：又稱讀鎖，若事務T對數(shù)

8、據(jù)對象A加上S鎖，則事務T可以讀A但不能修改A，其它事務只能再對A加S鎖，而不能加X鎖，直到T釋放A上的S鎖。,數(shù)據(jù)庫系統(tǒng)概論,21,封鎖（Locking）(2),X鎖和S鎖的控制方式可有相容矩陣表示。 最左邊表示T1已經(jīng)獲得的鎖的類型，最上面表示T2的封鎖請求, -表示沒有加鎖。 Y表示相容，請求可以滿足；N表示沖突，請求被拒絕。,數(shù)據(jù)庫系統(tǒng)概論,22,一級封鎖協(xié)議,加鎖必須遵守一定的規(guī)則，稱為封鎖協(xié)議。 一級封鎖協(xié)議：事務T在修改數(shù)據(jù)R之前必須先對其加X鎖，直到事務結束才釋放。事務結束包括正常結束（COMMIT）和非正常結束（ROLLBACK）。 一級封鎖協(xié)議中，如果是讀數(shù)據(jù)不修改，是不需

9、要加鎖的，可防止丟失修改。,數(shù)據(jù)庫系統(tǒng)概論,23,二級封鎖協(xié)議,二級封鎖協(xié)議：在一級封鎖協(xié)議基礎上，加上事務T在讀數(shù)據(jù)R之前必須先對其加上S鎖，讀完后即可釋放S鎖。 在二級封鎖協(xié)議中，由于讀完數(shù)據(jù)后即可釋放S鎖，所以它不能保證可重復讀。,數(shù)據(jù)庫系統(tǒng)概論,24,三級封鎖協(xié)議,三級封鎖協(xié)議：一級封鎖協(xié)議加上事務T在讀取數(shù)據(jù)R之前必須先對其加S鎖，直到事務結束才釋放。 三級封鎖協(xié)議除了防止了丟失修改和不讀“臟”數(shù)據(jù)外，還進一步防止了不可重復讀。 上述三級協(xié)議的主要區(qū)別在于：什么操作需要申請封鎖，以及何時釋放鎖。,數(shù)據(jù)庫系統(tǒng)概論,25,不同級別的封鎖協(xié)議,數(shù)據(jù)庫系統(tǒng)概論,26,活鎖,若某數(shù)據(jù)對象加了S

10、鎖，這時若有其它事務申請對它的X鎖，則需等待。但此時若有其它事務申請對它的S鎖，按相容矩陣，應可獲準。如果不斷有事務申請對此數(shù)據(jù)對象的S鎖，以致它始終被S鎖占有，而X鎖的申請遲遲不能獲準。這種現(xiàn)象叫活鎖。 避免活鎖的簡單方法是采用“先來先服務”的策略。,數(shù)據(jù)庫系統(tǒng)概論,27,死鎖,一個事務如果申請鎖而未獲準，則需等待其它事務釋放鎖。如果事務中出現(xiàn)循環(huán)等待時，如果不加干預，則會一直等待下去，這叫死鎖。 對付死鎖的方法： 檢測死鎖，發(fā)現(xiàn)死鎖后處理死鎖 防止死鎖,數(shù)據(jù)庫系統(tǒng)概論,28,死鎖的診斷（1）,超時法：如果一個事務的等待時間超過了某個時限，就認為發(fā)生死鎖。 特點： 優(yōu)點：簡單 缺點：一是事務

11、因其它原因（如系統(tǒng)負荷太重、通信受阻等）而使事務等待時間超過時限，可能被誤判死鎖。二是時限的設置。,數(shù)據(jù)庫系統(tǒng)概論,29,死鎖的診斷（2）,等待圖法：等待圖是一個有向圖G=(T,U)。 T為結點的集合，每個結點表示正在運行的事務 U為邊的集合，每條邊表示事務等待的情況 當且僅當?shù)却龍D中出現(xiàn)回路時，死鎖發(fā)生。 當運行的事務比較多時，維護等待圖和檢測回路的開銷較大，影響系統(tǒng)的性能。 方法是周期性的進行死鎖檢測。死鎖檢測周期的確定用實驗方法確定最佳值。,數(shù)據(jù)庫系統(tǒng)概論,30,死鎖的解除（1）,出現(xiàn)死鎖后，必須由DBMS干預。處理如下： 在循環(huán)等待的事務中，選一個事務作為“犧牲者”，給其它事務讓路 撤

12、銷犧牲的事務，釋放其獲得的鎖及其它資源 將釋放的鎖讓給等待它的事務 被犧牲的事務可以有兩種處理： 發(fā)消息給有關用戶，由用戶向系統(tǒng)再交付該事務 由DBMS重新啟動該事務 注：被犧牲的事務應等待一段時間才能交付系統(tǒng)，否則可能再發(fā)生死鎖。,數(shù)據(jù)庫系統(tǒng)概論,31,死鎖的解除（2）,選擇哪個事務作為犧牲者，由下列幾種選法： 選擇最遲交付的事務作為犧牲者 選擇獲得鎖最少的事務作為犧牲者 選擇撤銷代價最小的事務作為犧牲者,數(shù)據(jù)庫系統(tǒng)概論,32,死鎖的預防一次封鎖法,一次封鎖法：要求每個事務必須一次將所有要使用的數(shù)據(jù)全部加鎖。 缺點： 有些數(shù)據(jù)對象過早的加鎖，降低了并發(fā)度 如果有些事務需要訪問的“熱點”數(shù)據(jù)比

13、較多，其它事務總是不斷的占有其中某些數(shù)據(jù)，不能一次獲得所需要數(shù)據(jù)的全部，就會一直等待下去，易發(fā)生活鎖。,數(shù)據(jù)庫系統(tǒng)概論,33,死鎖的預防順序封鎖法,順序封鎖法：預先對數(shù)據(jù)對象規(guī)定一個封鎖順序，所有事務都按這個順序實行封鎖。 缺點： 數(shù)據(jù)庫中一般是按內(nèi)容訪問，而不是按名訪問，所以很難預先確定所有的訪問對象 數(shù)據(jù)經(jīng)常變動，次序也經(jīng)常調(diào)整 上述兩種方法用于數(shù)據(jù)庫系統(tǒng)不實際。,數(shù)據(jù)庫系統(tǒng)概論,34,死鎖的預防事務重執(zhí)（1）,事務重執(zhí)：當事務申請鎖而未獲準時，不是一律等待，而是讓一些事務撤銷重執(zhí)。 為區(qū)別事務開始執(zhí)行的先后，每個事務開始執(zhí)行時，賦予一個唯一的、隨時間增長的整數(shù)，稱為時間標記，記為ts。如

14、兩個事務TA和TB，若ts（TA） ts（TB），表明TA比TB“年老” 事務重執(zhí)有兩種策略 等待死亡策略 擊傷等待策略,數(shù)據(jù)庫系統(tǒng)概論,35,死鎖的預防事務重執(zhí)（2）,等待死亡策略 設TB持有某對象數(shù)據(jù)的鎖，當TA申請同一數(shù)據(jù)的鎖發(fā)生沖突時，按如下規(guī)則處理： If ts(TA)ts(TB) then TA waits; else rollback TA； / *die* / restrat TA with the same ts(TA); 總是年老的事務等待年輕的事務。,數(shù)據(jù)庫系統(tǒng)概論,36,死鎖的預防事務重執(zhí)（3）,擊傷等待策略 設TB持有某對象數(shù)據(jù)的鎖，當TA申請同一數(shù)據(jù)的鎖發(fā)生沖突時，

15、按如下規(guī)則處理： If ts(TA)ts(TB) then TA waits; else rollback TB； / *wound* / restrat TB with the same ts(TB); 總是年輕的事務等待年老的事務。,數(shù)據(jù)庫系統(tǒng)概論,37,死鎖的預防事務重執(zhí)（4）,上述兩種策略中，當沖突發(fā)生時，總是以年輕的事務作為犧牲品。因為年輕的事務隨著時間的流逝，總會變成年老的事務，不致永遠成為犧牲品。,數(shù)據(jù)庫系統(tǒng)概論,38,并發(fā)調(diào)度的可串行性（1）,定義：多個事務的并發(fā)執(zhí)行是正確的，當且僅當其結果與按某一次序串行地執(zhí)行它們時的結果相同，稱這種調(diào)度策略為可串行化的調(diào)度。 可串行性是并發(fā)

16、事務正確性的準則。按這個規(guī)則規(guī)定，一個給定的并發(fā)調(diào)度，當且僅當它是可串行化的，才認為是正確調(diào)度。 對于n個事務，可有n!中排列次序，即有n!種串行調(diào)度。,數(shù)據(jù)庫系統(tǒng)概論,39,并發(fā)調(diào)度的可串行性（2）,一個調(diào)度S是否可串行化，可用前趨圖來測試。前趨圖是有向圖，點表示所有參與調(diào)度的事務對于邊，當滿足下列條件之一時，加入： Ri(x)在Wj(x)之前 Wi(x)在Rj(x)之前 Wi(x)在Wj(x)之前 若前趨圖中有回路，則S顯然不等價于任何串行調(diào)度，若無回路，則可用拓撲排序得到一個串行調(diào)度。,數(shù)據(jù)庫系統(tǒng)概論,40,并發(fā)調(diào)度的可串行性（3）,設有事務集T1,T2,T3,T4的一個調(diào)度： S=W3

17、(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x) 試檢驗S是否可串行化。 分別分析對x,y,z的所有操作，畫出前趨圖。 T2 T1 T4 T1,T3,T2,T4 T3,數(shù)據(jù)庫系統(tǒng)概論,41,并發(fā)調(diào)度的可串行性（4）,可串行化調(diào)度和串行調(diào)度是有區(qū)別的： 前者交叉執(zhí)行各事務操作，在效果上相當于事務的某一串行執(zhí)行 后者完全是串行執(zhí)行各事務，失去并發(fā)意義，不能充分利用系統(tǒng)資源 DBMS并發(fā)控制的任務就是保證事務執(zhí)行的可串行化，比較有效的方法是要求DBMS按一定的封鎖協(xié)議調(diào)度事務，以保證其執(zhí)行可串行化。 兩段鎖協(xié)議（2PL）就是保證并發(fā)調(diào)度可串行化的封鎖協(xié)議。,數(shù)據(jù)庫系統(tǒng)概論

18、,42,兩段鎖協(xié)議（1）,兩段鎖協(xié)議是指所有事務必須分兩個階段對是數(shù)據(jù)項加鎖和解鎖 在對任何數(shù)據(jù)進行讀、寫操作之前，首先要申請并獲得對該數(shù)據(jù)的封鎖。擴展階段 在釋放一個封鎖之后，事物不再申請和獲得任何其它封鎖。收縮階段 若并發(fā)執(zhí)行的所有事務均遵守兩段鎖協(xié)議，則對這些事務的任何并發(fā)調(diào)度策略都可是可串行化。（充分條件）（可用反證法證明）,數(shù)據(jù)庫系統(tǒng)概論,43,兩段鎖協(xié)議（2）,兩段鎖協(xié)議和一次封鎖法的異同： 一次封鎖法要求每個事務必須一次將所有要使用的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議 兩段鎖協(xié)議并不要求事務必須一次將所有要使用的數(shù)據(jù)全部加鎖，因此可能會發(fā)生死鎖,數(shù)據(jù)庫系統(tǒng)概論,44,封鎖的粒度,定

19、義：封鎖對象的大小。 封鎖的對象： 可以是邏輯單元：屬性、屬性值的集合、元組、關系、索引項、整個索引、整個數(shù)據(jù)庫 也可以是物理單元：頁（數(shù)據(jù)頁或索引頁）、塊 封鎖粒度一系統(tǒng)的并發(fā)度和并發(fā)控制開銷相關 封鎖粒度越大，并發(fā)度越小，系統(tǒng)開銷越小 封鎖粒度越小，并發(fā)度較高，系統(tǒng)開銷越大,數(shù)據(jù)庫系統(tǒng)概論,45,多粒度封鎖,如果在一個系統(tǒng)中同時支持多種封鎖粒度供不同的事務選擇，這種封鎖方法稱為多粒度封鎖 多粒度封鎖，一個數(shù)據(jù)對象可能以兩種方式被封鎖： 顯式封鎖：應事務的要求直接加鎖于該數(shù)據(jù)對象 隱式封鎖：該數(shù)據(jù)對象沒有加鎖，而是由于它的上級被封鎖，應此這個數(shù)據(jù)對象被隱含地封鎖了 為了方便加鎖引起的沖突，引進了意向鎖（INTENTIO