本章要求：1、了解并發(fā)操作可能產(chǎn)生的數(shù)據(jù)不一致性2、掌握并發(fā)控制的技術(shù)：封鎖機(jī)制、三級封鎖協(xié)議、活鎖的避免、死鎖的預(yù)防、診斷及解除3、掌握并發(fā)調(diào)度的正確性標(biāo)準(zhǔn)和技術(shù)（可串行性、兩段鎖協(xié)議）11/26/20221數(shù)據(jù)庫系統(tǒng)本章要求：1、了解并發(fā)操作可能產(chǎn)生的數(shù)據(jù)不一致性11/22/§1并發(fā)控制概述

在多用戶數(shù)據(jù)庫系統(tǒng)中，當(dāng)多個(gè)用戶并發(fā)存取數(shù)據(jù)庫時(shí)就會(huì)產(chǎn)生多個(gè)事務(wù)同時(shí)存取同一數(shù)據(jù)的情形。若不加控制，可能會(huì)存取和存儲不正確的數(shù)據(jù)，造成數(shù)據(jù)庫的不一致性。在并發(fā)操作情況下，對事務(wù)的操作序列的調(diào)度是隨機(jī)的，考慮飛機(jī)訂票系統(tǒng)，若按下面的序列調(diào)度：考慮飛機(jī)訂票系統(tǒng)中的一個(gè)活動(dòng)序列：甲售票點(diǎn)讀出某航班的機(jī)票余額A，設(shè)A=16，乙售票點(diǎn)讀出同一航班的機(jī)票余額A，也為16，11/26/20222數(shù)據(jù)庫系統(tǒng)§1并發(fā)控制概述在多用戶數(shù)據(jù)庫系統(tǒng)中，當(dāng)甲售票點(diǎn)賣出一張機(jī)票，修改余額AA—1，A變?yōu)?5，把A寫回?cái)?shù)據(jù)庫乙售票點(diǎn)也賣出一張機(jī)票，修改余額AA—1，A也為15，把A寫回?cái)?shù)據(jù)庫。賣出兩張機(jī)票，而余額只減少1。錯(cuò)誤！

這種情況就造成數(shù)據(jù)庫的不一致性，這種不一致性是由并發(fā)操作引起的。并發(fā)操作帶來的數(shù)據(jù)不一致性包括三類：11/26/20223數(shù)據(jù)庫系統(tǒng)甲售票點(diǎn)賣出一張機(jī)票，修改余額AA—1，賣出兩張機(jī)一、并發(fā)操作可能造成的不一致性

1、丟失修改：兩事務(wù)讀出同一數(shù)據(jù)并修改，先寫回的數(shù)據(jù)修改丟失時(shí)間事務(wù)T1事務(wù)T2A16讀出A=讀出A=AA—1寫回A=AA—1寫回A=15AT1的修改丟失1615151615A

我的數(shù)據(jù)呢？11/26/20224數(shù)據(jù)庫系統(tǒng)一、并發(fā)操作可能造成的不一致性時(shí)間事務(wù)T12、不可重復(fù)讀事務(wù)T1讀取某一數(shù)據(jù)，事務(wù)T2讀取并修改了同一數(shù)據(jù)；事務(wù)T1為了對讀取值進(jìn)行校對再讀此數(shù)據(jù)，得到了不同的結(jié)果。時(shí)間事務(wù)T1事務(wù)T2讀出A=50，B=100求和=150讀出B=100計(jì)算BB2，寫回B讀出A=50，B=求和=200250T1讀出B的值與原來的不符，驗(yàn)算結(jié)果不對11/26/20225數(shù)據(jù)庫系統(tǒng)2、不可重復(fù)讀時(shí)間事務(wù)T1有三種情況可造成不可重復(fù)讀（1）事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對其做了修改，事務(wù)T1再次讀取該數(shù)據(jù)時(shí)，發(fā)現(xiàn)與前次不同；（2）事務(wù)T1按一定條件讀取了某些數(shù)據(jù)記錄后，事務(wù)T2刪除了其中的部分記錄，事務(wù)T1再次按相同條件讀取記錄時(shí)，發(fā)現(xiàn)有些記錄不存在；（3）事務(wù)T1按一定條件讀取了某些數(shù)據(jù)記錄后，事務(wù)T2插入了一些記錄，事務(wù)T1再次按相同條件讀取記錄時(shí)，發(fā)現(xiàn)多了一些記錄。11/26/20226數(shù)據(jù)庫系統(tǒng)有三種情況可造成不可重復(fù)讀11/22/20226數(shù)據(jù)庫系統(tǒng)3、讀出“臟”數(shù)據(jù)事務(wù)T1修改某一數(shù)據(jù)，事務(wù)T2讀取同一數(shù)據(jù)；事務(wù)T1由于某種原因被撤消，則T2讀到的就是“臟”數(shù)據(jù)。時(shí)間事務(wù)T1事務(wù)T2讀出C=100計(jì)算CC2，寫回CROLLBACKC恢復(fù)為100“臟”數(shù)據(jù)讀出C=200T2讀出的數(shù)據(jù)無效C=20011/26/20227數(shù)據(jù)庫系統(tǒng)3、讀出“臟”數(shù)據(jù)時(shí)間事務(wù)T1產(chǎn)生上述三類不一致性的主要原因就是并發(fā)操作破壞了事務(wù)的隔離性。并發(fā)控制就是要用正確的方式調(diào)度并發(fā)操作，使某個(gè)事務(wù)的執(zhí)行不受其它事務(wù)的干擾。

并發(fā)控制的技術(shù)是封鎖，即事務(wù)在修改某個(gè)對象前，先鎖住該對象，不允許其它事務(wù)讀取或修改該對象，修改完畢或事務(wù)完成后再將鎖打開。11/26/20228數(shù)據(jù)庫系統(tǒng)產(chǎn)生上述三類不一致性的主要原因就是并發(fā)操作破§2封鎖（Locking）封鎖的類型：排它鎖（ExclusiveLock，簡稱X鎖，又稱互斥鎖）：若事務(wù)T對數(shù)據(jù)對象R加上X鎖，則只允許T讀、寫R，禁止其它事務(wù)對R加任何鎖，相應(yīng)地其它事務(wù)就無法讀、寫對象R。共享鎖（SharedLock，簡稱S鎖）：

若事務(wù)T對數(shù)據(jù)對象R加上S鎖，則T可以讀R，但不可以寫R，且其它事務(wù)可以對R加S鎖、但禁止加X鎖。這保證了事務(wù)T在釋放R的S鎖之前，其它事務(wù)只可以讀R，不可以修改R。11/26/20229數(shù)據(jù)庫系統(tǒng)§2封鎖（Locking）封鎖的類型：排它鎖（Exclu附加知識點(diǎn)（參見P295例2圖11.4）：1、封鎖協(xié)議（LockingProtocol）

在運(yùn)用X鎖和S鎖對數(shù)據(jù)對象加鎖時(shí)，對何時(shí)申請X鎖或S鎖、持鎖時(shí)間、何時(shí)釋放等的一些約定。2、三級封鎖協(xié)議基本方法：事務(wù)在讀數(shù)據(jù)對象R時(shí)先上S鎖，封鎖后才能讀R，否則需等待；

事務(wù)在寫數(shù)據(jù)對象R時(shí)先上X鎖，封鎖后才能寫R，否則需等待；

何時(shí)釋放鎖（Unlock）？11/26/202210數(shù)據(jù)庫系統(tǒng)附加知識點(diǎn)（參見P295例2圖11.4）：2、三級封鎖協(xié)議根據(jù)上鎖的類型和釋放鎖的時(shí)機(jī)，分為三種情況。1級封鎖協(xié)議:事務(wù)T在修改數(shù)據(jù)對象R之前必須先對其加X鎖，直到事務(wù)結(jié)束才釋放。2級封鎖協(xié)議:1級封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)對象R之前必須先對其加S鎖，讀完即釋放S鎖。3級封鎖協(xié)議:1級封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)對象R之前必須先對其加S鎖，S鎖也是直到事務(wù)結(jié)束才釋放。11/26/202211數(shù)據(jù)庫系統(tǒng)根據(jù)上鎖的類型和釋放鎖的時(shí)機(jī)，分為三種情況。1級封鎖協(xié)議:21級封鎖協(xié)議:事務(wù)T在修改數(shù)據(jù)對象R之前必須先對其加X鎖，直到事務(wù)結(jié)束才釋放。分析：時(shí)間事務(wù)T1事務(wù)T2請求X鎖

對A加X鎖讀出A=16請求X鎖等待AA—1寫回A=15Commit

釋放X鎖

對A加X鎖讀出A=15AA—1寫回A=14Commit

釋放X鎖……作用：

防止丟失修改

保證事務(wù)是可恢復(fù)的11/26/202212數(shù)據(jù)庫系統(tǒng)1級封鎖協(xié)議:分析：時(shí)間事務(wù)T1事務(wù)2級封鎖協(xié)議:1級封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)對象R之前必須先對其加S鎖，讀完即釋放S鎖。分析：作用：

防止丟失修改時(shí)間事務(wù)T1事務(wù)T2請求X鎖

對C加X鎖讀出C=100計(jì)算CC2,寫回CROLLBACK（C恢復(fù)為100）釋放X鎖請求S鎖等待

防止讀“臟”數(shù)據(jù)

對C加S鎖讀出C=100

釋放S鎖……

保證事務(wù)是可恢復(fù)的11/26/202213數(shù)據(jù)庫系統(tǒng)2級封鎖協(xié)議:分析：作用：防止丟失修改時(shí)間3級封鎖協(xié)議:1級封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)對象R之前必須先對其加S鎖，S鎖也是直到事務(wù)結(jié)束才釋放。分析：作用：

防止丟失修改對A加S鎖對B加S鎖

讀出A=50，B=100求和=150對B請求X鎖等待

讀出A=50，B=100求和=150Commit釋放A、B上的S鎖時(shí)間事務(wù)T1事務(wù)T2

對B加X鎖讀出B=100計(jì)算BB2，寫回BCommit

釋放X鎖

防止讀“臟”數(shù)據(jù)保證可重復(fù)讀………

保證事務(wù)是可恢復(fù)的11/26/202214數(shù)據(jù)庫系統(tǒng)3級封鎖協(xié)議:分析：作用：防止丟失修改對A加S鎖對R1上X鎖

對R2上X鎖對R2請求X鎖等待

對R1請求X鎖

等待§3活鎖和死鎖使用封鎖機(jī)制，得不到鎖的事務(wù)就要等待，這可能出現(xiàn)下述局面：T1

T2………

T1和T2將永遠(yuǎn)等待下去11/26/202215數(shù)據(jù)庫系統(tǒng)對R1上X鎖§3活鎖和死鎖使用封鎖1、活鎖（Livelock）：數(shù)據(jù)對象不斷處于上鎖、開鎖的交替狀態(tài)，某個(gè)事務(wù)有可能為該對象上鎖，但始終沒有得到上鎖機(jī)會(huì)而永久等待下去的情形。例如：T1T2T3T4…….封鎖R請求封鎖R請求封鎖R等待請求封鎖R等待釋放鎖封鎖R等待釋放鎖封鎖R………………………如此下去，T2可能永遠(yuǎn)不能封鎖R。11/26/202216數(shù)據(jù)庫系統(tǒng)1、活鎖（Livelock）：T1避免活鎖：如采用先來先服務(wù)策略。2、死鎖（Deadlock）：多個(gè)事務(wù)因封鎖沖突（競爭資源）而永遠(yuǎn)等待下去的情形。如（課件p15例子）死鎖問題的解決方法預(yù)防死鎖診斷死鎖并解除一次封鎖法順序封鎖法超時(shí)法等待圖法（1）一次封鎖法每個(gè)事務(wù)必須將所要求的數(shù)據(jù)對象全部上鎖后才能執(zhí)行讀寫操作，否則釋放占用的資源。存在的問題使數(shù)據(jù)的上鎖時(shí)間增長，降低了系統(tǒng)的并發(fā)度。11/26/202217數(shù)據(jù)庫系統(tǒng)避免活鎖：如采用先來先服務(wù)策略。2、死鎖（Deadloc很難確定事務(wù)執(zhí)行期間需封鎖的數(shù)據(jù)對象。有些一開始不需要封鎖的對象，隨著數(shù)據(jù)庫數(shù)據(jù)的變化，可能變成封鎖對象，為避免此種情況發(fā)生，只能擴(kuò)大封鎖范圍。（2）順序封鎖法對所有數(shù)據(jù)對象規(guī)定一個(gè)封鎖順序，所有事務(wù)均按這個(gè)順序?qū)嵭蟹怄i。存在的問題：很難維護(hù)數(shù)據(jù)對象的封鎖順序，因?yàn)閿?shù)據(jù)對象很多并在不斷地增加、減少。很難確定事務(wù)需封鎖那些對象，從而很難按規(guī)定的順序封鎖。預(yù)防死鎖的策略不很適合數(shù)據(jù)庫的特點(diǎn)，DBMS普遍采用診斷死鎖并解除的方法。11/26/202218數(shù)據(jù)庫系統(tǒng)很難確定事務(wù)執(zhí)行期間需封鎖的數(shù)據(jù)對象。有些一開始不需要（3）超時(shí)法

當(dāng)一個(gè)事務(wù)的等待時(shí)間超過了規(guī)定的時(shí)限，就認(rèn)為發(fā)生了死鎖。存在的問題：時(shí)限規(guī)定的太短，可能誤判死鎖，規(guī)定的太長，又不能及時(shí)發(fā)現(xiàn)死鎖。因此很難確定一個(gè)合理的時(shí)限。（4）等待圖法用一個(gè)有向圖表示事務(wù)等待的情況。圖中節(jié)點(diǎn)表示事務(wù)，邊表示事務(wù)間的等待關(guān)系。并發(fā)控制子系統(tǒng)定時(shí)檢查此圖，若發(fā)現(xiàn)有回路，則產(chǎn)生死鎖。發(fā)生死鎖時(shí)，解除死鎖的方法：選擇一個(gè)處理代價(jià)最小的事務(wù)，將其撤消。ROLLBACK11/26/202219數(shù)據(jù)庫系統(tǒng)（3）超時(shí)法（4）等待圖法發(fā)生死鎖時(shí)，解除死鎖的方法：ROL§4并發(fā)調(diào)度的可串行性多事務(wù)并發(fā)執(zhí)行，對并發(fā)操作的調(diào)度是隨機(jī)的，如何保證正確性？1、調(diào)度（Schedule）：若干個(gè)事務(wù)的操作構(gòu)成的序列。2、串行與并發(fā)對調(diào)度S中的兩個(gè)事務(wù)Ti和Tj，若S中Ti的操作都在Tj的操作之前（或反之），則稱Ti、Tj是串行執(zhí)行的；否則稱作是并發(fā)執(zhí)行的。若調(diào)度S中的所有事務(wù)都是串行執(zhí)行的，則稱S是串行的（Serial）。11/26/202220數(shù)據(jù)庫系統(tǒng)§4并發(fā)調(diào)度的可串行性多事務(wù)并發(fā)執(zhí)行，對并3、可串行化（Serializable）多個(gè)事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行它們時(shí)的結(jié)果相同，稱這種調(diào)度為可串行化的調(diào)度。調(diào)度可串行化的不可串行化的串行的并發(fā)的并發(fā)的所有事務(wù)串行起來的調(diào)度策略一定是正確的調(diào)度策略。盡管一組事務(wù)可能有多個(gè)串行調(diào)度序列，且產(chǎn)生的執(zhí)行結(jié)果不一定相同，但每個(gè)序列都不會(huì)將數(shù)據(jù)庫置于不一致狀態(tài)。11/26/202221數(shù)據(jù)庫系統(tǒng)3、可串行化（Serializable）調(diào)度可串行化的串行的4、一點(diǎn)說明：對若干個(gè)事務(wù)，不同的并發(fā)調(diào)度策略其最終的執(zhí)行結(jié)果不一定完全相同。但只要它們的調(diào)度是可串行化的，則都是正確調(diào)度。如：事務(wù)T1：讀B；AB+1；寫回A。事務(wù)T2：讀A；BA+1；寫回B。T1T2讀BAB+1寫A讀ABA+1寫B(tài)T1T2讀ABA+1寫B(tài)讀BAB+1寫AT1T2讀B讀AAB+1寫ABA+1寫B(tài)結(jié)果A=3B=4假設(shè)T1、T2執(zhí)行前A=2，B=2A=4B=3A=3B=311/26/202222數(shù)據(jù)庫系統(tǒng)4、一點(diǎn)說明：如：事務(wù)T1：讀B；AB+1；寫回A。TT1T2讀B讀AAB+1寫ABA+1寫B(tài)T1T2讀B讀AAB+1寫A

BA+1寫B(tài)

分析右邊的調(diào)度：若采用2級封鎖協(xié)議，則可能得到這樣的調(diào)度仍是不可串行化的調(diào)度若采用3級封鎖協(xié)議，則可能得到這樣的調(diào)度永久等待，造成死鎖SlockBUnlockBSlockAUnlockAXlockAUnlockAXlockBUnlockBSlockB讀B

SlockA讀AXlockAAB+1XlockB寫AUnlockAUnlockB

BA+1寫B(tài)

UnlockA

UnlockB因此，三級封鎖協(xié)議不能保證得到可串行化的調(diào)度，也會(huì)造成死鎖。11/26/202223數(shù)據(jù)庫系統(tǒng)T1T2T1§5兩段鎖協(xié)議1、兩段封鎖協(xié)議（也稱兩相上鎖協(xié)議）（2-Phase-LockingProtocol，簡寫2PL）（1）在對任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要申請并獲得對該數(shù)據(jù)的封鎖（讀時(shí)S鎖，寫時(shí)X鎖）；（2）在釋放一個(gè)封鎖之后，事務(wù)不再申請和獲得新的封鎖。例：LockALockBLockCUnlockBUnlockAUnlockCLockALockBUnlockBLockCUnlockAUnlockC含義：事務(wù)封鎖分兩個(gè)階段第一階段是擴(kuò)展階段（GrowingPhase），只進(jìn)行上鎖第二階段是收縮階段（ShrinkingPhase）,只進(jìn)行解鎖11/26/202224數(shù)據(jù)庫系統(tǒng)§5兩段鎖協(xié)議1、兩段封鎖協(xié)議（也稱兩相上鎖協(xié)議）例：含義2、2PL的正確性

定理：若所有事務(wù)都遵守兩段封鎖協(xié)議，則對這些事務(wù)的任何并發(fā)調(diào)度策略都是可串行化的。3、說明2PL是并發(fā)控制正確性的充分條件，但不是必要條件。即若所有事務(wù)都遵守2PL，則這些事務(wù)的任何并發(fā)調(diào)度都是可串行化的，反之，一個(gè)并發(fā)調(diào)度是可串行化的，不一定所有事務(wù)都遵守2PL。（參見P299圖11.7（d））11/26/202225數(shù)據(jù)庫系統(tǒng)2、2PL的正確性3、說明2PL是并發(fā)控制正確性的充LockALockBLockCUnlockBUnlockAUnlockC允許讀寫不允許讀寫此時(shí)才允許讀寫預(yù)防死鎖的一次封鎖法2PL2PL會(huì)產(chǎn)生死鎖（參見P302圖11.9）。2PL不隱含預(yù)防死鎖的一次封鎖法，但一次封鎖法肯定遵守2PL。11/26/202226數(shù)據(jù)庫系統(tǒng)LockALockBLockC§6封鎖的粒度1、封鎖的粒度（Granularity）封鎖對象的大小。可以是數(shù)據(jù)庫、表、記錄、字段等。粒度大，封鎖開銷小，但影響共享粒度小，封鎖開銷大，但共享性好2、多粒度封鎖（MultipleGranularityLocking)

同時(shí)支持多種封鎖粒度供不同事務(wù)選擇的封鎖方法。多粒度封鎖方法依賴的數(shù)據(jù)結(jié)構(gòu)----多粒度樹

將數(shù)據(jù)庫中的數(shù)據(jù)對象按相互關(guān)系和粒度大小組織成的樹型結(jié)構(gòu)，其中根結(jié)點(diǎn)表示最大數(shù)據(jù)粒度，通常為整個(gè)數(shù)據(jù)庫，葉結(jié)點(diǎn)表示最小數(shù)據(jù)粒度。11/26/202227數(shù)據(jù)庫系統(tǒng)§6封鎖的粒度1、封鎖的粒度（Granularity）粒度多粒度封鎖協(xié)議允許對多粒度樹中的每個(gè)結(jié)點(diǎn)獨(dú)立地加鎖，并且對每一個(gè)結(jié)點(diǎn)加鎖隱含著對其后裔結(jié)點(diǎn)也加以同樣的鎖。由事務(wù)直接加到數(shù)據(jù)對象上的封鎖稱為顯式封鎖，因上級結(jié)點(diǎn)加鎖而引起下級對象被封鎖，稱為隱式封鎖。顯式封鎖與隱式封鎖的效果是一樣的。多粒度封鎖方法

為對某數(shù)據(jù)對象加鎖，系統(tǒng)要檢查：該對象有無顯式封鎖與之沖突；該對象的上級結(jié)點(diǎn)有無顯式封鎖與之沖突；該對象的下級結(jié)點(diǎn)有無顯式封鎖與之沖突；當(dāng)無任何沖突時(shí)方能加鎖成功。3、意向鎖用來指示下級結(jié)點(diǎn)正在被加鎖的鎖。對任一結(jié)點(diǎn)加鎖時(shí)，必須先對其上級結(jié)點(diǎn)加意向鎖。11/26/202228數(shù)據(jù)庫系統(tǒng)多粒度封鎖協(xié)議當(dāng)無任何沖3、意向鎖11/22/202228數(shù)作用：減少加鎖時(shí)的封鎖沖突檢查工作量。只需檢查上級結(jié)點(diǎn)與本結(jié)點(diǎn)是否已加了不相容的鎖，并通過本結(jié)點(diǎn)的意向鎖了解下級結(jié)點(diǎn)是否有不相容的鎖，從而不必再檢查下級結(jié)點(diǎn)。三種意向鎖意向共享鎖（IS鎖）如果要對某個(gè)對象加S鎖，需先對其上級對象加IS鎖。意向排它鎖（IX鎖）如果要對某個(gè)對象加X鎖，需先對其上級對象加IX鎖。共享意向排它鎖（SIX鎖）如果要對某對象加S鎖，并對其下級對象加X鎖，則應(yīng)對該對象加SIX鎖。意向鎖的封鎖和釋放順序封鎖：自上而下釋放：自下而上11/26/202229數(shù)據(jù)庫系統(tǒng)作用：減少加鎖時(shí)的封鎖沖突檢查工作量。只需檢查上級結(jié)點(diǎn)與本章要求：1、了解并發(fā)操作可能產(chǎn)生的數(shù)據(jù)不一致性2、掌握并發(fā)控制的技術(shù)：封鎖機(jī)制、三級封鎖協(xié)議、活鎖的避免、死鎖的預(yù)防、診斷及解除3、掌握并發(fā)調(diào)度的正確性標(biāo)準(zhǔn)和技術(shù)（可串行性、兩段鎖協(xié)議）11/26/202230數(shù)據(jù)庫系統(tǒng)本章要求：1、了解并發(fā)操作可能產(chǎn)生的數(shù)據(jù)不一致性11/22/§1并發(fā)控制概述

在多用戶數(shù)據(jù)庫系統(tǒng)中，當(dāng)多個(gè)用戶并發(fā)存取數(shù)據(jù)庫時(shí)就會(huì)產(chǎn)生多個(gè)事務(wù)同時(shí)存取同一數(shù)據(jù)的情形。若不加控制，可能會(huì)存取和存儲不正確的數(shù)據(jù)，造成數(shù)據(jù)庫的不一致性。在并發(fā)操作情況下，對事務(wù)的操作序列的調(diào)度是隨機(jī)的，考慮飛機(jī)訂票系統(tǒng)，若按下面的序列調(diào)度：考慮飛機(jī)訂票系統(tǒng)中的一個(gè)活動(dòng)序列：甲售票點(diǎn)讀出某航班的機(jī)票余額A，設(shè)A=16，乙售票點(diǎn)讀出同一航班的機(jī)票余額A，也為16，11/26/202231數(shù)據(jù)庫系統(tǒng)§1并發(fā)控制概述在多用戶數(shù)據(jù)庫系統(tǒng)中，當(dāng)甲售票點(diǎn)賣出一張機(jī)票，修改余額AA—1，A變?yōu)?5，把A寫回?cái)?shù)據(jù)庫乙售票點(diǎn)也賣出一張機(jī)票，修改余額AA—1，A也為15，把A寫回?cái)?shù)據(jù)庫。賣出兩張機(jī)票，而余額只減少1。錯(cuò)誤！

這種情況就造成數(shù)據(jù)庫的不一致性，這種不一致性是由并發(fā)操作引起的。并發(fā)操作帶來的數(shù)據(jù)不一致性包括三類：11/26/202232數(shù)據(jù)庫系統(tǒng)甲售票點(diǎn)賣出一張機(jī)票，修改余額AA—1，賣出兩張機(jī)一、并發(fā)操作可能造成的不一致性

1、丟失修改：兩事務(wù)讀出同一數(shù)據(jù)并修改，先寫回的數(shù)據(jù)修改丟失時(shí)間事務(wù)T1事務(wù)T2A16讀出A=讀出A=AA—1寫回A=AA—1寫回A=15AT1的修改丟失1615151615A

我的數(shù)據(jù)呢？11/26/202233數(shù)據(jù)庫系統(tǒng)一、并發(fā)操作可能造成的不一致性時(shí)間事務(wù)T12、不可重復(fù)讀事務(wù)T1讀取某一數(shù)據(jù)，事務(wù)T2讀取并修改了同一數(shù)據(jù)；事務(wù)T1為了對讀取值進(jìn)行校對再讀此數(shù)據(jù)，得到了不同的結(jié)果。時(shí)間事務(wù)T1事務(wù)T2讀出A=50，B=100求和=150讀出B=100計(jì)算BB2，寫回B讀出A=50，B=求和=200250T1讀出B的值與原來的不符，驗(yàn)算結(jié)果不對11/26/202234數(shù)據(jù)庫系統(tǒng)2、不可重復(fù)讀時(shí)間事務(wù)T1有三種情況可造成不可重復(fù)讀（1）事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對其做了修改，事務(wù)T1再次讀取該數(shù)據(jù)時(shí)，發(fā)現(xiàn)與前次不同；（2）事務(wù)T1按一定條件讀取了某些數(shù)據(jù)記錄后，事務(wù)T2刪除了其中的部分記錄，事務(wù)T1再次按相同條件讀取記錄時(shí)，發(fā)現(xiàn)有些記錄不存在；（3）事務(wù)T1按一定條件讀取了某些數(shù)據(jù)記錄后，事務(wù)T2插入了一些記錄，事務(wù)T1再次按相同條件讀取記錄時(shí)，發(fā)現(xiàn)多了一些記錄。11/26/202235數(shù)據(jù)庫系統(tǒng)有三種情況可造成不可重復(fù)讀11/22/20226數(shù)據(jù)庫系統(tǒng)3、讀出“臟”數(shù)據(jù)事務(wù)T1修改某一數(shù)據(jù)，事務(wù)T2讀取同一數(shù)據(jù)；事務(wù)T1由于某種原因被撤消，則T2讀到的就是“臟”數(shù)據(jù)。時(shí)間事務(wù)T1事務(wù)T2讀出C=100計(jì)算CC2，寫回CROLLBACKC恢復(fù)為100“臟”數(shù)據(jù)讀出C=200T2讀出的數(shù)據(jù)無效C=20011/26/202236數(shù)據(jù)庫系統(tǒng)3、讀出“臟”數(shù)據(jù)時(shí)間事務(wù)T1產(chǎn)生上述三類不一致性的主要原因就是并發(fā)操作破壞了事務(wù)的隔離性。并發(fā)控制就是要用正確的方式調(diào)度并發(fā)操作，使某個(gè)事務(wù)的執(zhí)行不受其它事務(wù)的干擾。

并發(fā)控制的技術(shù)是封鎖，即事務(wù)在修改某個(gè)對象前，先鎖住該對象，不允許其它事務(wù)讀取或修改該對象，修改完畢或事務(wù)完成后再將鎖打開。11/26/202237數(shù)據(jù)庫系統(tǒng)產(chǎn)生上述三類不一致性的主要原因就是并發(fā)操作破§2封鎖（Locking）封鎖的類型：排它鎖（ExclusiveLock，簡稱X鎖，又稱互斥鎖）：若事務(wù)T對數(shù)據(jù)對象R加上X鎖，則只允許T讀、寫R，禁止其它事務(wù)對R加任何鎖，相應(yīng)地其它事務(wù)就無法讀、寫對象R。共享鎖（SharedLock，簡稱S鎖）：

若事務(wù)T對數(shù)據(jù)對象R加上S鎖，則T可以讀R，但不可以寫R，且其它事務(wù)可以對R加S鎖、但禁止加X鎖。這保證了事務(wù)T在釋放R的S鎖之前，其它事務(wù)只可以讀R，不可以修改R。11/26/202238數(shù)據(jù)庫系統(tǒng)§2封鎖（Locking）封鎖的類型：排它鎖（Exclu附加知識點(diǎn)（參見P295例2圖11.4）：1、封鎖協(xié)議（LockingProtocol）

在運(yùn)用X鎖和S鎖對數(shù)據(jù)對象加鎖時(shí)，對何時(shí)申請X鎖或S鎖、持鎖時(shí)間、何時(shí)釋放等的一些約定。2、三級封鎖協(xié)議基本方法：事務(wù)在讀數(shù)據(jù)對象R時(shí)先上S鎖，封鎖后才能讀R，否則需等待；

事務(wù)在寫數(shù)據(jù)對象R時(shí)先上X鎖，封鎖后才能寫R，否則需等待；

何時(shí)釋放鎖（Unlock）？11/26/202239數(shù)據(jù)庫系統(tǒng)附加知識點(diǎn)（參見P295例2圖11.4）：2、三級封鎖協(xié)議根據(jù)上鎖的類型和釋放鎖的時(shí)機(jī)，分為三種情況。1級封鎖協(xié)議:事務(wù)T在修改數(shù)據(jù)對象R之前必須先對其加X鎖，直到事務(wù)結(jié)束才釋放。2級封鎖協(xié)議:1級封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)對象R之前必須先對其加S鎖，讀完即釋放S鎖。3級封鎖協(xié)議:1級封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)對象R之前必須先對其加S鎖，S鎖也是直到事務(wù)結(jié)束才釋放。11/26/202240數(shù)據(jù)庫系統(tǒng)根據(jù)上鎖的類型和釋放鎖的時(shí)機(jī)，分為三種情況。1級封鎖協(xié)議:21級封鎖協(xié)議:事務(wù)T在修改數(shù)據(jù)對象R之前必須先對其加X鎖，直到事務(wù)結(jié)束才釋放。分析：時(shí)間事務(wù)T1事務(wù)T2請求X鎖

對A加X鎖讀出A=16請求X鎖等待AA—1寫回A=15Commit

釋放X鎖

對A加X鎖讀出A=15AA—1寫回A=14Commit

釋放X鎖……作用：

防止丟失修改

保證事務(wù)是可恢復(fù)的11/26/202241數(shù)據(jù)庫系統(tǒng)1級封鎖協(xié)議:分析：時(shí)間事務(wù)T1事務(wù)2級封鎖協(xié)議:1級封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)對象R之前必須先對其加S鎖，讀完即釋放S鎖。分析：作用：

防止丟失修改時(shí)間事務(wù)T1事務(wù)T2請求X鎖

對C加X鎖讀出C=100計(jì)算CC2,寫回CROLLBACK（C恢復(fù)為100）釋放X鎖請求S鎖等待

防止讀“臟”數(shù)據(jù)

對C加S鎖讀出C=100

釋放S鎖……

保證事務(wù)是可恢復(fù)的11/26/202242數(shù)據(jù)庫系統(tǒng)2級封鎖協(xié)議:分析：作用：防止丟失修改時(shí)間3級封鎖協(xié)議:1級封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)對象R之前必須先對其加S鎖，S鎖也是直到事務(wù)結(jié)束才釋放。分析：作用：

防止丟失修改對A加S鎖對B加S鎖

讀出A=50，B=100求和=150對B請求X鎖等待

讀出A=50，B=100求和=150Commit釋放A、B上的S鎖時(shí)間事務(wù)T1事務(wù)T2

對B加X鎖讀出B=100計(jì)算BB2，寫回BCommit

釋放X鎖

防止讀“臟”數(shù)據(jù)保證可重復(fù)讀………

保證事務(wù)是可恢復(fù)的11/26/202243數(shù)據(jù)庫系統(tǒng)3級封鎖協(xié)議:分析：作用：防止丟失修改對A加S鎖對R1上X鎖

對R2上X鎖對R2請求X鎖等待

對R1請求X鎖

等待§3活鎖和死鎖使用封鎖機(jī)制，得不到鎖的事務(wù)就要等待，這可能出現(xiàn)下述局面：T1

T2………

T1和T2將永遠(yuǎn)等待下去11/26/202244數(shù)據(jù)庫系統(tǒng)對R1上X鎖§3活鎖和死鎖使用封鎖1、活鎖（Livelock）：數(shù)據(jù)對象不斷處于上鎖、開鎖的交替狀態(tài)，某個(gè)事務(wù)有可能為該對象上鎖，但始終沒有得到上鎖機(jī)會(huì)而永久等待下去的情形。例如：T1T2T3T4…….封鎖R請求封鎖R請求封鎖R等待請求封鎖R等待釋放鎖封鎖R等待釋放鎖封鎖R………………………如此下去，T2可能永遠(yuǎn)不能封鎖R。11/26/202245數(shù)據(jù)庫系統(tǒng)1、活鎖（Livelock）：T1避免活鎖：如采用先來先服務(wù)策略。2、死鎖（Deadlock）：多個(gè)事務(wù)因封鎖沖突（競爭資源）而永遠(yuǎn)等待下去的情形。如（課件p15例子）死鎖問題的解決方法預(yù)防死鎖診斷死鎖并解除一次封鎖法順序封鎖法超時(shí)法等待圖法（1）一次封鎖法每個(gè)事務(wù)必須將所要求的數(shù)據(jù)對象全部上鎖后才能執(zhí)行讀寫操作，否則釋放占用的資源。存在的問題使數(shù)據(jù)的上鎖時(shí)間增長，降低了系統(tǒng)的并發(fā)度。11/26/202246數(shù)據(jù)庫系統(tǒng)避免活鎖：如采用先來先服務(wù)策略。2、死鎖（Deadloc很難確定事務(wù)執(zhí)行期間需封鎖的數(shù)據(jù)對象。有些一開始不需要封鎖的對象，隨著數(shù)據(jù)庫數(shù)據(jù)的變化，可能變成封鎖對象，為避免此種情況發(fā)生，只能擴(kuò)大封鎖范圍。（2）順序封鎖法對所有數(shù)據(jù)對象規(guī)定一個(gè)封鎖順序，所有事務(wù)均按這個(gè)順序?qū)嵭蟹怄i。存在的問題：很難維護(hù)數(shù)據(jù)對象的封鎖順序，因?yàn)閿?shù)據(jù)對象很多并在不斷地增加、減少。很難確定事務(wù)需封鎖那些對象，從而很難按規(guī)定的順序封鎖。預(yù)防死鎖的策略不很適合數(shù)據(jù)庫的特點(diǎn)，DBMS普遍采用診斷死鎖并解除的方法。11/26/202247數(shù)據(jù)庫系統(tǒng)很難確定事務(wù)執(zhí)行期間需封鎖的數(shù)據(jù)對象。有些一開始不需要（3）超時(shí)法

當(dāng)一個(gè)事務(wù)的等待時(shí)間超過了規(guī)定的時(shí)限，就認(rèn)為發(fā)生了死鎖。存在的問題：時(shí)限規(guī)定的太短，可能誤判死鎖，規(guī)定的太長，又不能及時(shí)發(fā)現(xiàn)死鎖。因此很難確定一個(gè)合理的時(shí)限。（4）等待圖法用一個(gè)有向圖表示事務(wù)等待的情況。圖中節(jié)點(diǎn)表示事務(wù)，邊表示事務(wù)間的等待關(guān)系。并發(fā)控制子系統(tǒng)定時(shí)檢查此圖，若發(fā)現(xiàn)有回路，則產(chǎn)生死鎖。發(fā)生死鎖時(shí)，解除死鎖的方法：選擇一個(gè)處理代價(jià)最小的事務(wù)，將其撤消。ROLLBACK11/26/202248數(shù)據(jù)庫系統(tǒng)（3）超時(shí)法（4）等待圖法發(fā)生死鎖時(shí)，解除死鎖的方法：ROL§4并發(fā)調(diào)度的可串行性多事務(wù)并發(fā)執(zhí)行，對并發(fā)操作的調(diào)度是隨機(jī)的，如何保證正確性？1、調(diào)度（Schedule）：若干個(gè)事務(wù)的操作構(gòu)成的序列。2、串行與并發(fā)對調(diào)度S中的兩個(gè)事務(wù)Ti和Tj，若S中Ti的操作都在Tj的操作之前（或反之），則稱Ti、Tj是串行執(zhí)行的；否則稱作是并發(fā)執(zhí)行的。若調(diào)度S中的所有事務(wù)都是串行執(zhí)行的，則稱S是串行的（Serial）。11/26/202249數(shù)據(jù)庫系統(tǒng)§4并發(fā)調(diào)度的可串行性多事務(wù)并發(fā)執(zhí)行，對并3、可串行化（Serializable）多個(gè)事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行它們時(shí)的結(jié)果相同，稱這種調(diào)度為可串行化的調(diào)度。調(diào)度可串行化的不可串行化的串行的并發(fā)的并發(fā)的所有事務(wù)串行起來的調(diào)度策略一定是正確的調(diào)度策略。盡管一組事務(wù)可能有多個(gè)串行調(diào)度序列，且產(chǎn)生的執(zhí)行結(jié)果不一定相同，但每個(gè)序列都不會(huì)將數(shù)據(jù)庫置于不一致狀態(tài)。11/26/202250數(shù)據(jù)庫系統(tǒng)3、可串行化（Serializable）調(diào)度可串行化的串行的4、一點(diǎn)說明：對若干個(gè)事務(wù)，不同的并發(fā)調(diào)度策略其最終的執(zhí)行結(jié)果不一定完全相同。但只要它們的調(diào)度是可串行化的，則都是正確調(diào)度。如：事務(wù)T1：讀B；AB+1；寫回A。事務(wù)T2：讀A；BA+1；寫回B。T1T2讀BAB+1寫A讀ABA+1寫B(tài)T1T2讀ABA+1寫B(tài)讀BAB+1寫AT1T2讀B讀AAB+1寫ABA+1寫B(tài)結(jié)果A=3B=4假設(shè)T1、T2執(zhí)行前A=2，B=2A=4B=3A=3B=311/26/202251數(shù)據(jù)庫系統(tǒng)4、一點(diǎn)說明：如：事務(wù)T1：讀B；AB+1；寫回A。TT1T2讀B讀AAB+1寫ABA+1寫B(tài)T1T2讀B讀AAB+1寫A

BA+1寫B(tài)

分析右邊的調(diào)度：若采用2級封鎖協(xié)議，則可能得到這樣的調(diào)度仍是不可串行化的調(diào)度若采用3級封鎖協(xié)議，則可能得到這樣的調(diào)度永久等待，造成死鎖SlockBUnlockBSlockAUnlockAXlockAUnlockAXlockBUnlockBSlockB讀B

SlockA讀AXlockAAB+1XlockB寫AUnlockAUnlockB

BA+1寫B(tài)

UnlockA

UnlockB因此，三級封鎖協(xié)議不能保證得到可串行化的調(diào)度，也會(huì)造成死鎖。11/26/202252數(shù)據(jù)庫