第六章：事務(wù)與并發(fā)控制

第六章

事務(wù)與并發(fā)控制一、事務(wù)的概念事務(wù)概念用戶定義的一個操作序列，這些操作要么都執(zhí)行，要么都不執(zhí)行，是一個不可分割的工作單位2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系2一、事務(wù)的概念事務(wù)與程序區(qū)別一個事務(wù)可以是一條SQL語句，一組SQL語句或整個程序一個應(yīng)用程序通常包含多個事務(wù)事務(wù)是恢復(fù)和并發(fā)控制的基本單位2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系3一、事務(wù)的概念2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系4顯式事務(wù)隱式事務(wù)事務(wù)分類一、事務(wù)的概念定義事務(wù)的語句2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系5BeginTransaction開始語句Commit—正常提交Rollback—回滾結(jié)束語句SQL語句……一、事務(wù)的概念COMMIT事務(wù)正常結(jié)束提交事務(wù)的所有操作（讀+更新）事務(wù)中所有對數(shù)據(jù)庫的更新永久生效2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系6一、事務(wù)的概念ROLLBACK事務(wù)異常終止事務(wù)運(yùn)行的過程中發(fā)生了故障，不能繼續(xù)執(zhí)行,回滾事務(wù)的所有更新操作事務(wù)滾回到開始時的狀態(tài)2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系7一、事務(wù)的概念2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系8原子性一致性事務(wù)的特性(ACID)隔離性永久性一、事務(wù)的概念2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系9特性含義實現(xiàn)原子性事務(wù)必須遵守“要么都做要么都不做”的原則DBMS的事務(wù)管理子系統(tǒng)一致性事務(wù)執(zhí)行必須使DB保持一致性的狀態(tài)DBMS的測試完整性子系統(tǒng)隔離性多個事務(wù)執(zhí)行互不干擾DBMS的并發(fā)控制子系統(tǒng)持久性事務(wù)對數(shù)據(jù)庫的改變是永久的DBMS的恢復(fù)管理子系統(tǒng)一、事務(wù)的概念銀行轉(zhuǎn)帳：從帳號A中取出一萬元，存入帳號B定義一個事務(wù)，該事務(wù)包括兩個操作這兩個操作要么全做，要么全不做2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系10

B=B+1

A=A-1BA一、事務(wù)的概念2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系11

讀A=16

A←A-3寫回A=13①讀A=16②③A←A-1

寫回A=15

④T2T1T1的修改被T2覆蓋了！(稱為"修改丟失")二、

并發(fā)控制概述事務(wù)的串行執(zhí)行多個事務(wù)操作同一數(shù)據(jù)對象按逐個順序執(zhí)行事務(wù)的并發(fā)執(zhí)行多個事務(wù)對同一數(shù)據(jù)對象同時進(jìn)行操作方式:交叉并發(fā)(單處理機(jī))；同步并發(fā)(多處理機(jī))2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系12二、并發(fā)控制概述并發(fā)執(zhí)行可能發(fā)生的4類數(shù)據(jù)的不一致性丟失修改不可重復(fù)讀讀臟數(shù)據(jù)產(chǎn)生幻影(幽靈)數(shù)據(jù)2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系13二、并發(fā)控制概述2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系14T1T2ReadA=16ReadA=16A=A-1A=A-1WriteAWriteAt1t2t3t4t5t6兩個事務(wù)T1,T2讀取并修改同一數(shù)據(jù)對象，由于T2的提交使得T1的提交覆蓋丟失丟失修改二、并發(fā)控制概述2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系15T1T2ReadA=16ReadA=16A=A-1ReadA=15WriteAt1t2t3t4t5t6T1不同時間讀取同一數(shù)據(jù)對象結(jié)果不一樣不可重復(fù)讀Commit二、并發(fā)控制概述三類不可重復(fù)讀事務(wù)2對其做了修改，當(dāng)事務(wù)1再次讀該數(shù)據(jù)時，得到與前一次不同的值。事務(wù)2刪除了其中部分記錄，當(dāng)事務(wù)1再次讀取數(shù)據(jù)時，發(fā)現(xiàn)某些記錄神密地消失了2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系16二、并發(fā)控制概述三類不可重復(fù)讀事務(wù)2插入了一些記錄，當(dāng)事務(wù)1再次按相同條件讀取數(shù)據(jù)時，發(fā)現(xiàn)多了一些記錄。后兩種不可重復(fù)讀有時也稱為幻影現(xiàn)象2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系17二、并發(fā)控制概述2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系18T1T2ReadA=16ReadA=15A=A-1RollbackWriteAt1t2t3t4t5t6T2讀取并修改T1修改過的但是并未提交的數(shù)據(jù)，而使T2讀取無用數(shù)據(jù)讀“臟”數(shù)據(jù)A=A-1WriteAt7二、并發(fā)控制概述產(chǎn)生4類數(shù)據(jù)不一致性的主要原因并發(fā)操作破壞了事務(wù)的隔離性并發(fā)控制的主要技術(shù)封鎖時間戳樂觀控制法2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系19三、封鎖封鎖事務(wù)T要操作某個數(shù)據(jù)對象R時必須先向系統(tǒng)申請加鎖，使得T對該數(shù)據(jù)擁有某種操作權(quán)而排除其他事務(wù)對該數(shù)據(jù)的某種操作權(quán)。記為LockR解鎖封鎖后可以釋放數(shù)據(jù)對象，記為UnLockR2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系20三、封鎖X鎖與S鎖X鎖（排他鎖/寫鎖）事務(wù)T對數(shù)據(jù)對象R加鎖后，T對R可以進(jìn)行讀寫操作，但其他事務(wù)對R不能進(jìn)行任何操作，而只能等到T對R解鎖后才可進(jìn)行操作。記為XLockR2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系21三、封鎖2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系22T1T2ReadA=16等待.UnLockA獲得XLockAt1t2t3t4t5t6X鎖A=A-1WriteAt7XLockAXLock

A（不批準(zhǔn)）Committ8...三、封鎖X鎖與S鎖S鎖（共享鎖/讀鎖）事務(wù)T對操作對象R加鎖后，T只能對R進(jìn)行讀操作，也允許其他事務(wù)對R進(jìn)行加同樣鎖并可進(jìn)行讀操作。記為SLockR2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系23三、封鎖2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系24T1T2ReadAReadAt1t2t3S鎖SLockASLock

A三、封鎖2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系25X鎖與S鎖的兼容性XS--XNNYSNYY--YYYT2T1三、封鎖2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系26T1T2ReadA=16..UnLockA獲得XLockAt1t2t3t4t5t6A=A-1WriteAt7XLockAXLock

A（等待）Committ8..ReadA=15A=A-1t9t10t11WriteACommit解決不一致性問題—丟失修改三、封鎖2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系27T1T2ReadA=16UnLockA獲得XLockAt1t2t3t4t5t6ReadA=16t7SLockAXLock

A（等待）Committ8ReadA=16A=A-1t9t10t11WriteACommit解決不一致性問題—不可重復(fù)讀三、封鎖2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系28T1T2ReadA=16UnLockA獲得XLockAt1t2t3t4t5t6WriteAt7XLockAXLock

A（等待）Rollbackt8ReadA=16A=A-1t9t10t11WriteACommitA=A-1解決不一致性問題—讀臟數(shù)據(jù)三、封鎖封鎖協(xié)議概念所有事務(wù)都要遵守的加鎖規(guī)則在運(yùn)用X鎖和S鎖對數(shù)據(jù)對象加鎖時，需要約定一些規(guī)則何時申請X鎖或S鎖持鎖時間、何時釋放2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系29三、封鎖一級封鎖協(xié)議事務(wù)T在修改數(shù)據(jù)對象R之前必須對R加X鎖，直到事務(wù)結(jié)束（Commit或Rollback）才可解鎖。當(dāng)T對R加X鎖后到解鎖之前，其他事務(wù)對R可以申請X鎖，但是只能等待2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系30三、封鎖一級封鎖協(xié)議一級封鎖協(xié)議可防止丟失修改在一級封鎖協(xié)議中，如果是讀數(shù)據(jù)，不需要加鎖的，所以它不能保證可重復(fù)讀和不讀“臟”數(shù)據(jù)。2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系31三、封鎖2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系32

讀A=15①

XlockA

獲得②

讀A=16

A←A-1

寫回A=15③

④RollbackUnlockAT2T1讀“臟”數(shù)據(jù)三、封鎖2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系33不可重復(fù)讀

XlockB

讀B=100B←B*2B=200CommitUnlockB①讀A=50,B=100

求和=150②③讀A=50,B=200

求和=250(驗算不對)T2T1三、封鎖二級封鎖協(xié)議在一級封鎖協(xié)議的基礎(chǔ)上，事務(wù)T在讀取數(shù)據(jù)之前必須加S鎖，讀取后即可解S鎖二級封鎖協(xié)議可以防止丟失修改和讀“臟”數(shù)據(jù)在二級封鎖協(xié)議中，由于讀完數(shù)據(jù)后即可釋放S鎖，所以它不能保證可重復(fù)讀2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系342023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系35④SclockA

獲得讀A=50UnlockASclockB

獲得讀B=200UnlockB

求和=250(驗算不對)

T2T1(續(xù))①

SclockA

獲得讀A=50UnlockA②SclockB

獲得讀B=100UnlockB③求和=150

XlockB等待等待獲得XlockB讀B=100B←B*2寫回B=200CommitUnlockBT2T1三、封鎖三級封鎖協(xié)議在一級封鎖協(xié)議的基礎(chǔ)上，事務(wù)T在讀取數(shù)據(jù)對象R之前必須加S鎖，直到事務(wù)結(jié)束才可解鎖三級封鎖協(xié)議可防止丟失修改、讀臟數(shù)據(jù)和不可重復(fù)讀2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系36三、封鎖三級協(xié)議的主要區(qū)別什么操作需要申請封鎖何時釋放鎖（即持鎖時間）2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系37三、封鎖2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系38四、活鎖和死鎖活鎖多個事務(wù)對同一數(shù)據(jù)對象加鎖結(jié)果使某個事務(wù)永遠(yuǎn)處于等待狀態(tài)（非公平分配，餓死）2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系39T1T2UnlockAXLockAXLockA(等待)T3XLockA(等待)XLockA四、活鎖和死鎖活鎖活鎖預(yù)防—先來先服務(wù)按請求封鎖的先后次序?qū)@些事務(wù)排隊該數(shù)據(jù)對象上的鎖一旦釋放，首先批準(zhǔn)申請隊列中第一個事務(wù)獲得鎖。2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系40四、活鎖和死鎖死鎖多個事務(wù)相互等待對方釋放自己所需要的資源而又無法獲得，使得事務(wù)無法執(zhí)行下去的現(xiàn)象2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系41T1T2XLockAXLockBXLockB(等待)XLockA(等待)四、活鎖和死鎖死鎖死鎖的預(yù)防：一次封鎖法順序封鎖法2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系42四、活鎖和死鎖一次封鎖法要求每個事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行一次封鎖法存在的問題：降低并發(fā)度將以后要用到的全部數(shù)據(jù)加鎖，勢必擴(kuò)大了封鎖的范圍，從而降低了系統(tǒng)的并發(fā)度2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系43四、活鎖和死鎖順序封鎖法預(yù)先對數(shù)據(jù)對象規(guī)定一個封鎖順序，所有事務(wù)都按這個順序?qū)嵭蟹怄i事務(wù)的封鎖請求可以隨著事務(wù)的執(zhí)行而動態(tài)地決定，很難事先確定每一個事務(wù)要封鎖哪些對象，因此也就很難按規(guī)定的順序去施加封鎖2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系44四、活鎖和死鎖死鎖的診斷與解除診斷超時法等待圖法2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系45四、活鎖和死鎖超時法如果一個事務(wù)的等待時間超過了規(guī)定的時限，就認(rèn)為發(fā)生了死鎖優(yōu)點(diǎn)：實現(xiàn)簡單2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系46四、活鎖和死鎖等待圖法用事務(wù)等待圖動態(tài)反映所有事務(wù)的等待情況事務(wù)等待圖是一個有向圖G=(T，U)T為結(jié)點(diǎn)的集合，每個結(jié)點(diǎn)表示正運(yùn)行的事務(wù)U為邊的集合，每條邊表示事務(wù)等待的情況若T1等待T2，則它們之間劃一條T1指向T2有向邊2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系47四、活鎖和死鎖等待圖法并發(fā)控制子系統(tǒng)周期性地（比如每隔1min）檢測事務(wù)等待圖，如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中出現(xiàn)了死鎖。2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系48四、活鎖和死鎖死鎖的診斷與解除解除撤銷處理代價最小的事務(wù)，釋放該事務(wù)持有的鎖，使其他事務(wù)得以繼續(xù)運(yùn)行2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系49五、并發(fā)調(diào)度的可串行性調(diào)度：一個事務(wù)集所有基本操作的一個序列例：現(xiàn)在有兩個事務(wù)，分別包含下列操作：事務(wù)2：讀B；A=B+1；寫回A；事務(wù)1：讀A；B=A+1；寫回B；2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系50五、并發(fā)調(diào)度的可串行性調(diào)度：一個事務(wù)集所有基本操作的一個序列2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系51T1T2B=A+1WriteBReadAA=B+1WriteAReadBT1T2B=A+1WriteBReadAA=B+1WriteAReadB例：初始狀態(tài)：A=2,B=2五、并發(fā)調(diào)度的可串行性串行調(diào)度與并發(fā)調(diào)度串行調(diào)度：事務(wù)逐個執(zhí)行并發(fā)調(diào)度：事務(wù)交叉執(zhí)行可串行化的調(diào)度若并發(fā)調(diào)度的結(jié)果與某次串行調(diào)度的結(jié)果一樣，則稱這種調(diào)度策略為可串行化的調(diào)度2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系52可串行性是并發(fā)事務(wù)正確性的準(zhǔn)則五、并發(fā)調(diào)度的可串行性2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系53T1T2SlockBY=B=2UnlockBXlockAA=Y+1writeA=3UnlockA

X=A=3UnlockAwriteB=4UnlockBSlockAXlockBB=X+1a串行調(diào)度T1T2SlockBY=B=3UnlockBXlockAA=Y+1writeA=4UnlockA

X=A=2UnlockAWriteB=3UnlockBSlockAXlockBB=X+1b串行調(diào)度T1:讀B;A=B+1;寫回A;T2:讀A;B=A+1;寫回B;A,B初值均為2五、并發(fā)調(diào)度的可串行性2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系54T1T2SlockBY=B=2A=Y+1writeA=3UnlockA

X=A=2writeB=3UnlockBSlockAXlockBB=X+1c不可串行化的調(diào)度(結(jié)果與a,b不同，錯誤調(diào)度)T1T2SlockBY=B=2UnlockBXlockAA=Y+1writeA=3UnlockA

X=A=3UnlockAWriteB=4UnlockBSlockAXlockBB=X+1T1:讀B;A=B+1;寫回A;T2:讀A;B=A+1;寫回B;A,B初值均為2XlockAUnlockAUnlockB等待等待等待d可串行化的調(diào)度(結(jié)果與a相同，正確調(diào)度)五、并發(fā)調(diào)度的可串行性從理論上來講，在某一事務(wù)執(zhí)行時禁止其他事務(wù)執(zhí)行的調(diào)度策略一定是可串行化的調(diào)度兩段鎖（2PL）協(xié)議就是保證并發(fā)調(diào)度可串行性的封鎖協(xié)議。2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系55五、并發(fā)調(diào)度的可串行性兩段鎖（2PL）協(xié)議每個事務(wù)在讀寫數(shù)據(jù)對象之前必須封鎖并獲得鎖（擴(kuò)展階段）每個事務(wù)在釋放一個鎖后就不能再加鎖（收縮階段）2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系56五、并發(fā)調(diào)度的可串行性遵守兩段鎖協(xié)議的事務(wù)SlockA…SlockB…XlockC...UnlockB…UnlockA…UnlockC不遵守兩段鎖協(xié)議的事務(wù)SlockA…UnlockA…SlockB...XlockC…UnlockC…UnlockB2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系57五、并發(fā)調(diào)度的可串行性如果所有事務(wù)都遵守2PL，則并發(fā)調(diào)度可串行化說明：只有加鎖而無解鎖，也滿足2PL；2PL也增加了死鎖的可能性。2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系582023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系59T1SlockB讀B=2Y=BXlockA

A=Y+1寫回A=3UnlockBUnlockA

T2

SlockA

等待等待等待等待等待SlockA讀A=3Y=AXlockBB=Y+1寫回B=4UnlockBUnlockA

T1SlockB讀B=2Y=BUnlockBXlockA

A=Y+1寫回A=3UnlockA

T2

SlockA等待等待等待等待SlockA讀A=3X=AUnlockAXlockBB=X+1寫回B=4UnlockB

(a)遵守兩段鎖協(xié)議(b)不遵守兩段鎖協(xié)議T1SlockB讀B=2Y=BUnlockBXlockAA=Y+1寫回A=3UnlockAT2

SlockA讀A=2X=AUnlockAXlockB等待XlockBB=X+1寫回B=3UnlockB

(c)不遵守兩段鎖協(xié)議(b)可串行化(c)不可串行化六、時間戳法時間戳是由DBMS創(chuàng)建的唯一標(biāo)識符，用于標(biāo)識事務(wù)的相對啟動時間一般被賦予時間戳值的順序就是事務(wù)提交給系統(tǒng)的順序。時間戳性質(zhì)：唯一性；單調(diào)性2023/7/11福州大學(xué)陽光學(xué)院計算機(jī)工程系60七、樂觀控制法悲觀并發(fā)控制一個鎖定系統(tǒng)，可以阻止用戶以影響其他用戶的方式修改數(shù)據(jù)。如果用戶執(zhí)行的操作導(dǎo)致應(yīng)用了某個鎖，只有這個鎖的所有者釋放該鎖，其他用戶才能執(zhí)行與該鎖沖突的操作。2023/7/11福州大學(xué)陽光