系統(tǒng)實(shí)現(xiàn)技術(shù)課件

第八章系統(tǒng)實(shí)現(xiàn)技術(shù)

——事務(wù)和鎖本章重要概念

（1）事務(wù)的定義，COMMIT和ROLLBACK的語義，事務(wù)的ACID性質(zhì)，事務(wù)的狀態(tài)變遷圖。（2）存儲器類型，穩(wěn)定存儲器的實(shí)現(xiàn)，數(shù)據(jù)傳送過程。（3）恢復(fù)的定義、基本原則和實(shí)現(xiàn)方法，故障的類型，檢查點(diǎn)技術(shù)，REDO和UNDO操作，運(yùn)行記錄優(yōu)先原則。（4）并發(fā)操作帶來的三個問題，X鎖、S鎖、使用X鎖和S鎖的操作，封鎖協(xié)議，活鎖、餓死和死鎖，并發(fā)調(diào)度、串行調(diào)度、并發(fā)調(diào)度的可串行化，SQL中事務(wù)的存取模式和隔離級別，基于時標(biāo)的并發(fā)控制。第8章系統(tǒng)實(shí)現(xiàn)技術(shù)8.1事務(wù)8.2數(shù)據(jù)庫的恢復(fù)8.3數(shù)據(jù)庫的并發(fā)控制為什么需要事務(wù)8.1-1例如，銀行轉(zhuǎn)帳問題：假定資金從帳戶A轉(zhuǎn)到帳戶B，至少需要兩步：帳戶A的資金減少然后帳戶B的資金相應(yīng)增加銀行轉(zhuǎn)帳帳戶A帳戶B為什么需要事務(wù)8.1-2CREATETABLEbank(customerNameCHAR(10),--顧客姓名

currentMoneyMONEY--當(dāng)前余額)GOALTERTABLEbank

ADDCONSTRAINTCK_currentMoneyCHECK(currentMoney>=1)GOINSERTINTObank(customerName,currentMoney)VALUES('張三',1000)INSERTINTObank(customerName,currentMoney)VALUES('李四',1)創(chuàng)建帳戶表，存放用戶的帳戶信息添加約束：根據(jù)銀行規(guī)定，帳戶余額不能少于1元，否則視為銷戶張三開戶，開戶金額為1000元；李四開戶，開戶金額1元為什么需要事務(wù)8.1-3目前兩個帳戶的余額總和為：1000+1=1001元

為什么需要事務(wù)8.1-5--張三的帳戶減少1000元，李四的帳戶增加1000元UPDATEbankSETcurrentMoney=currentMoney-1000WHEREcustomerName='張三'UPDATEbankSETcurrentMoney=currentMoney+1000WHEREcustomerName='李四'GO錯誤原因分析：UPDATE語句違反約束：

余額>=1元執(zhí)行失敗，所以張三還是1000元繼續(xù)往下執(zhí)行：執(zhí)行成功，所以李四變?yōu)?001元如何解決呢？使用事務(wù)8.1.1

事務(wù)的定義(1)定義8.1事務(wù)（transaction）是構(gòu)成單一邏輯工作單元的操作集合，要么完整地執(zhí)行，要么完全不執(zhí)行。不論發(fā)生何種情況，DBS必須保證事務(wù)能正確、完整地執(zhí)行。在程序中，事務(wù)以BEGINTRANSACTION語句開始，以COMMIT語句或ROLLBACK語句結(jié)束。

COMMIT語句表示事務(wù)執(zhí)行成功地結(jié)束（提交），此時告訴系統(tǒng)，數(shù)據(jù)庫要進(jìn)入一個新的正確狀態(tài)，該事務(wù)對數(shù)據(jù)庫的所有更新都已交付實(shí)施（寫入磁盤）。

ROLLBACK語句表示事務(wù)執(zhí)行不成功地結(jié)束（應(yīng)該“回退”），此時告訴系統(tǒng)，已發(fā)生錯誤，數(shù)據(jù)庫可能處在不正確的狀態(tài)，該事務(wù)對數(shù)據(jù)庫的所有更新必須被撤消，數(shù)據(jù)庫應(yīng)恢復(fù)該事務(wù)到初始狀態(tài)。用戶定義的一個對數(shù)據(jù)庫讀寫操作序列一個不可分割的工作單位數(shù)據(jù)庫恢復(fù)和并發(fā)控制的基本單位數(shù)據(jù)庫系統(tǒng)中通常有多個事務(wù)并行運(yùn)行事務(wù)和程序比較在關(guān)系數(shù)據(jù)庫中，一個事務(wù)可以是一條或多條SQL語句,也可以包含一個或多個程序。一個程序通常包含多個事務(wù)轉(zhuǎn)帳過程就是一個事務(wù)。它需要兩條UPDATE語句來完成，這兩條語句是一個整體，如果其中任一條出現(xiàn)錯誤，則整個轉(zhuǎn)帳業(yè)務(wù)也應(yīng)取消，兩個帳戶中的余額應(yīng)恢復(fù)到原來的數(shù)據(jù)，從而確保轉(zhuǎn)帳前和轉(zhuǎn)帳后的余額不變，即都是1001元。8.1.1

事務(wù)的定義(2)8.1.1

事務(wù)的定義(4)對數(shù)據(jù)庫的訪問是建立在讀和寫兩個操作的基礎(chǔ)上的：read（X）：把數(shù)據(jù)X，從磁盤的數(shù)據(jù)庫中讀到內(nèi)存的緩沖區(qū)中。write（X）：把數(shù)據(jù)X，從內(nèi)存緩沖區(qū)中寫回磁盤的數(shù)據(jù)庫。在系統(tǒng)運(yùn)行時，write操作未必導(dǎo)致數(shù)據(jù)立即寫回磁盤，很可能先暫存在內(nèi)存緩沖區(qū)中，稍后再寫回磁盤。這件事情是DBMS實(shí)現(xiàn)時必須注意的問題。8.1.2

事務(wù)的ACID性質(zhì)性質(zhì):原子性(Atomicity):事務(wù)是一個不可分割的工作單元，事務(wù)中的操作要么都做，要么都不做(AllorNone)

一致性(Consistency):即數(shù)據(jù)不會應(yīng)事務(wù)的執(zhí)行而遭受破壞。事務(wù)執(zhí)行的結(jié)果必須使數(shù)據(jù)庫從一個一致性狀態(tài)變到另一個一致性狀態(tài)。與原子性密切相關(guān)。隔離性(Isolation):在多個事務(wù)并發(fā)執(zhí)行時，系統(tǒng)應(yīng)保證與這些事務(wù)先后單獨(dú)執(zhí)行時的結(jié)果一樣。持久性(Durability):一個事務(wù)一旦完成全部操作后，它對數(shù)據(jù)庫的所有更新應(yīng)永久地反映在數(shù)據(jù)庫中。8.2數(shù)據(jù)庫的恢復(fù)8.2.1存儲器結(jié)構(gòu)8.2.2恢復(fù)的基本原則和實(shí)現(xiàn)方法8.2.3故障類型和恢復(fù)方法8.2.4檢查點(diǎn)技術(shù)8.2.5SQL對事務(wù)的支持8.2.1存儲器結(jié)構(gòu)(2)3.數(shù)據(jù)訪問塊、物理塊和緩沖塊塊的操作input（A）：把物理塊A的內(nèi)容傳送到內(nèi)存的緩沖塊中。Output（B）：把緩沖塊B的內(nèi)容傳送到磁盤中恰當(dāng)?shù)奈锢韷K中

B內(nèi)存AB磁盤input(A)output(B)圖8.2塊操作8.2.1存儲器結(jié)構(gòu)(3)xiwrite(X)包含x的塊Bx存在，read(X)事務(wù)系統(tǒng)開始請求read(X)事務(wù)工作區(qū)分配X磁盤緩沖區(qū)掃描內(nèi)存磁盤包含x的塊Bx存在，input(B)8.2.1存儲器結(jié)構(gòu)(4)銀行轉(zhuǎn)賬系統(tǒng)A=2000B=1000事務(wù)A=A-100B=B+100output(A)output(B)斷電或其他故障假設(shè)沒有事務(wù)的原子性，那么重新啟動事務(wù)時，要么A因?yàn)樵賵?zhí)行一遍而為1800，要么B因從未執(zhí)行而保持原值。4.恢復(fù)和原子性的聯(lián)系8.2.3故障類型和恢復(fù)方法(1)1.事務(wù)故障可以預(yù)期的事務(wù)故障，如存款余額透支等非預(yù)期事務(wù)故障，如運(yùn)算溢出、數(shù)據(jù)錯誤、死鎖等2.系統(tǒng)故障：硬件故障、軟件錯誤或掉電等,重新啟動時，具體處理分兩種情況考慮。對未完成事務(wù)作UNDO處理；對已提交事務(wù)但更新還留在緩沖區(qū)的事務(wù)進(jìn)行REDO處理。8.2.3故障類型和恢復(fù)方法(2)3．介質(zhì)故障在發(fā)生介質(zhì)故障和遭受病毒破壞時，磁盤上的物理數(shù)據(jù)庫遭到毀滅性破壞。此時恢復(fù)的過程如下：重裝最近轉(zhuǎn)儲的后備副本到新的磁盤，使數(shù)據(jù)庫恢復(fù)到轉(zhuǎn)儲時的一致狀態(tài)。在日志中找出最近轉(zhuǎn)儲以后所有已提交的事務(wù)。對這些已提交的事務(wù)進(jìn)行REDO處理，將數(shù)據(jù)庫恢復(fù)到故障前某一時刻的一致狀態(tài)。在實(shí)際中，系統(tǒng)故障通常稱為軟故障(SoftCrash)，介質(zhì)故障通常稱為硬故障(HardCrash)。8.2.4檢查點(diǎn)技術(shù)(1)1．檢查點(diǎn)方法

在DBS運(yùn)行時，DBMS定時設(shè)置檢查點(diǎn)。在檢查點(diǎn)時刻才真正做到把對DB的修改寫到磁盤，并在日志文件寫入一條檢查點(diǎn)記錄(以便恢復(fù)時使用)。當(dāng)DB需要恢復(fù)時，只有那些在檢查點(diǎn)后面的事務(wù)需要恢復(fù)。事務(wù)T1不必恢復(fù)；事務(wù)T2和事務(wù)T4必須重做(REDO)；事務(wù)T3和事務(wù)T5必須撤消(UNDO)。事務(wù)檢查點(diǎn)故障點(diǎn)t檢查點(diǎn)T1T3T2T5T48.2.5SQL對事務(wù)的支持無begintransactionCommitRollback8.3數(shù)據(jù)庫的并發(fā)控制8.3.1并發(fā)操作帶來的三個問題8.3.2封鎖技術(shù)8.3.3封鎖帶來的問題8.3.4并發(fā)操作的調(diào)度8.3.5SQL對事務(wù)處理的支持8.3.1并發(fā)操作帶來的三個問題(1)圖8.5在時間t8丟失了事務(wù)T1的更新（FIND表示從DB中讀值，UPD表示把值寫回到DB）

1．丟失更新問題（例8.2）時間更新事務(wù)T1數(shù)據(jù)庫中A的值更新事務(wù)T2t0

100

t1FINDA

t2

FINDAt3A:=A-30

t4

A:=A*2t5UPDA

t6

80UPDAt8

200

8.3.1并發(fā)操作帶來的三個問題(3)圖8.8事務(wù)T2在時間t4讀了未提交的A值，并在時間t8丟失了自己的更新2．讀臟數(shù)據(jù)問題（例8.4，用戶讀了“臟數(shù)據(jù)”，引起自身的更新操作被丟失，破壞了數(shù)據(jù)庫的完整性）時間更新事務(wù)T1數(shù)據(jù)庫中A的值更新事務(wù)T2t0

100

t1FINDA

t2A:=A-30

t3UPDA

t4

80FINDAt5

A:=A*2t6

UPDAt8

140

t8*ROLLBACK*

t9

100

8.3.1并發(fā)操作帶來的三個問題(4)圖8.8事務(wù)T1兩次讀取A的值，卻得到了不同的結(jié)果3.不可重復(fù)讀問題（例8.5）時間讀事務(wù)T1數(shù)據(jù)庫中A的值更新事務(wù)T2t0

100

t1FINDA

t2

XFINDAt3

A:=A*2t4

UPDAt5

200COMMITt6FINDA

8.3.1并發(fā)操作帶來的三個問題(5)時間更新事務(wù)T1數(shù)據(jù)庫中A值更新事務(wù)T2t0

100

t1FINDA

t2

FINDAt3A:=A-30

t4

A:=A*2t5UPDA

t6

80UPDAt8

200

圖8.5在時間t8丟失了事務(wù)T1的更新①②③解決方法：8.3.2

封鎖技術(shù)(1)定義8.3鎖（lock）是一個與數(shù)據(jù)項(xiàng)相關(guān)的變量，對可能應(yīng)用于該數(shù)據(jù)項(xiàng)上的操作而言，鎖描述了該數(shù)據(jù)項(xiàng)的狀態(tài)。通常在數(shù)據(jù)庫中每個數(shù)據(jù)項(xiàng)都有一個鎖。鎖的作用是使并發(fā)事務(wù)對數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)的訪問能夠同步。封鎖技術(shù)中主要有兩種封鎖：●排他型封鎖●共享型封鎖8.3.2

封鎖技術(shù)(2)1.排他型封鎖（X鎖，寫鎖）X鎖定義：如果事務(wù)T對某個數(shù)據(jù)R（可以是數(shù)據(jù)項(xiàng)、記錄、數(shù)據(jù)集乃至整個數(shù)據(jù)庫）實(shí)現(xiàn)了X鎖，那么在T對數(shù)據(jù)R解除封鎖之前，不允許其他事務(wù)T再對該數(shù)據(jù)加任何類型的鎖。這種鎖稱為“X鎖”。X鎖的操作有兩個：封鎖操作“XFINDR”：表示事務(wù)對數(shù)據(jù)R申請加X鎖，若成功，則可以讀或?qū)憯?shù)據(jù)R，若不成功，那么這個事務(wù)將進(jìn)入等待隊(duì)列，直到獲得X鎖，事務(wù)才繼續(xù)做下去。解鎖操作“XRELEASER”：表示事務(wù)要解除對數(shù)據(jù)R的X鎖

X鎖的解除操作應(yīng)該合并到事務(wù)的結(jié)束（COMMIT或ROLLBACK）操作中。時間更新事務(wù)T1DB中A的值更新事務(wù)T2t0

100

t1XFINDA

t2

XFINDA(失敗)

wait(等待)t3A:=A-30

waitt4

waitt5UPDA

waitt6

80waitt8COMMIT(含解鎖)

waitt8

XFINDA(重做)t9

A:=A*2t10

UPDAt11

140COMMIT(含解鎖)8.3.2

封鎖技術(shù)(3)例8.6使用X鎖技術(shù)，可以解決圖8.5的丟失更新問題。圖8.9等事務(wù)T1更新完成后再執(zhí)行事務(wù)T22．共享型封鎖（S鎖，讀鎖）定義8.5如果事務(wù)T對某數(shù)據(jù)加上S鎖后，仍允許其他事務(wù)再對該數(shù)據(jù)加S鎖，但在對該數(shù)據(jù)的所有S鎖都解除之前決不允許任何事務(wù)對該數(shù)據(jù)加X鎖。S鎖的操作有三個：封鎖操作“SFINDR升級和寫操作“UPDXR”解鎖操作“SRELEASER”可以看出，獲準(zhǔn)S鎖的事務(wù)只能讀數(shù)據(jù)，不能更新數(shù)據(jù)，若要更新，則先要把S鎖升級為X鎖。另外，由于S鎖只允許讀數(shù)據(jù)，因此解除S鎖的操作不必非要合并到事務(wù)的結(jié)束操作中去，可以隨時根據(jù)需要解除S鎖。8.3.2

封鎖技術(shù)(4)時間更新事務(wù)T1DB中A的值更新事務(wù)T2t0

100

t1SFINDA

t2

SFINDAt3A:=A-30

t4

A:=A*2t5UPDXA(失敗)

t6wait

UPDXA(失敗)t8wait

waitt8wait

wait8.3.2

封鎖技術(shù)(5)例8.8

使用S鎖技術(shù),也可以解決圖8.5的丟失更新問題。圖8.10

更新未丟失,但在時間t6發(fā)生了死鎖注：①N=NO，不相容的請求

Y=YES，相容的請求②X、S、－：分別表示X鎖，S鎖，無鎖③如果兩個封鎖是不相容的，則后提出封鎖的事務(wù)要等待。XS—XNNYSNYY—YYYT1T28.3.2

封鎖技術(shù)(6)3．封鎖的相容矩陣4．封鎖的粒度定義8.6

封鎖對象的大小稱為封鎖的粒度。封鎖的對象邏輯單元:屬性值、屬性值集合、元組、關(guān)系、索引項(xiàng)、整個索引、整個數(shù)據(jù)庫

物理單元

:頁（數(shù)據(jù)頁或索引頁）、塊

封鎖粒度與系統(tǒng)并發(fā)度和并發(fā)控制開銷密切相關(guān)。粒度越大，系統(tǒng)中能被封鎖的對象就越少，并發(fā)度就越小，但同時系統(tǒng)的開銷也就越??；相反，粒度越小，并發(fā)度越高，系統(tǒng)開銷越大。選擇封鎖粒度時必須同時考慮封鎖機(jī)構(gòu)與并發(fā)度兩個因素，對系統(tǒng)開銷與并發(fā)度進(jìn)行權(quán)衡。8.3.2

封鎖技術(shù)(8)5．封鎖協(xié)議：三級封鎖協(xié)議，分別在不同程度上解決了并發(fā)操作帶來的各種問題，為并發(fā)操作的正確調(diào)度提供一定的保證。8.3.2

封鎖技術(shù)(8)表8.1封鎖協(xié)議的內(nèi)容和優(yōu)缺點(diǎn)級別內(nèi)容優(yōu)點(diǎn)缺點(diǎn)一級封鎖協(xié)議事務(wù)在修改數(shù)據(jù)之前，必須先對該數(shù)據(jù)加X鎖,直到事務(wù)結(jié)束時才釋放但只讀數(shù)據(jù)的事務(wù)可以不加鎖防止“丟失修改”不加鎖的事務(wù)，可能“讀臟數(shù)據(jù)”，也可能“不可重復(fù)讀”二級封鎖協(xié)議但其他事務(wù)在讀數(shù)據(jù)之前必需先加S鎖讀完數(shù)據(jù)后即可釋放S鎖防止“丟失修改”，防止“讀臟數(shù)據(jù)”對加S鎖的事務(wù),可能“不可重復(fù)讀”三級封鎖協(xié)議直到事務(wù)結(jié)束時才釋放S鎖防止“丟失修改”，防止“讀臟數(shù)據(jù)”，防止“不可重復(fù)讀”8.3數(shù)據(jù)庫的并發(fā)控制8.3.1并發(fā)操作帶來的三個問題8.3.2封鎖技術(shù)8.3.3封鎖帶來的問題8.3.4并發(fā)操作的調(diào)度8.3.5SQL對事務(wù)處理的支持8.3.3

封鎖帶來的問題(1)1．“活鎖”問題定義8.8系統(tǒng)可能使某個事務(wù)永遠(yuǎn)處于等待狀態(tài)，得不到封鎖的機(jī)會，這種現(xiàn)象稱為“活鎖”（LiveLock）。解決活鎖問題的一種簡單的方法是采用“先來先服務(wù)”的策略，也就是簡單的排隊(duì)方式。如果運(yùn)行時，事務(wù)有優(yōu)先級，那么很可能使優(yōu)先級低的事務(wù)，既使排隊(duì)也很難輪上封鎖的機(jī)會。此時可采用“升級”方法來解決，也就是當(dāng)一個事務(wù)等待若干時間（譬如5分鐘）還輪不上封鎖時，可以提高其優(yōu)先級別，這樣總能輪上封鎖。8.3.3

封鎖帶來的問題(2)2．“餓死”問題定義8.8有可能存在一個事務(wù)序列，其中每個事務(wù)都申請對某數(shù)據(jù)項(xiàng)加S鎖，且每個事務(wù)在授權(quán)加鎖后一小段時內(nèi)釋放封鎖，此時若另有一個事務(wù)T2欲在該數(shù)據(jù)項(xiàng)上加X鎖，則將永遠(yuǎn)輪不上封鎖的機(jī)會。這種現(xiàn)象稱為“餓死”（starvation）。可以用下列方式授權(quán)加鎖來避免事務(wù)餓死。當(dāng)事務(wù)T2中請對數(shù)據(jù)項(xiàng)Q加S鎖時，授權(quán)加鎖的條件是：①不存在在數(shù)據(jù)項(xiàng)Q上持有X鎖的其他事務(wù)；②不存在等待對數(shù)據(jù)項(xiàng)Q加鎖且先于T2申請加鎖的事務(wù)。8.3.3

封鎖帶來的問題(3)3.“死鎖”問題定義8.9系統(tǒng)中有兩個或兩個以上的事務(wù)都處于等待狀態(tài)，并且每個事務(wù)都在等待其中另一個事務(wù)解除封鎖，它才能繼續(xù)執(zhí)行下去，結(jié)果造成任何一個事務(wù)都無法繼續(xù)執(zhí)行，這種現(xiàn)象稱系統(tǒng)進(jìn)入了“死鎖”（DeadLock）狀態(tài)。時間事務(wù)T1事務(wù)T2t0XFINDA

t1

XFINDBt2XFINDB

t3waitXFINDAt4waitwait圖8.12在時間t4兩個事務(wù)發(fā)生死鎖8.3.3

封鎖帶來的問題(4)我們可以用事務(wù)依賴圖的形式測試系統(tǒng)中是否存在死鎖。圖中每一個結(jié)點(diǎn)是“事務(wù)”，箭頭表示事務(wù)間的依賴關(guān)系。圖8.14為無環(huán)依賴圖，表示系統(tǒng)未進(jìn)入死鎖狀態(tài)；而圖8.15為有環(huán)依賴圖，則表示系統(tǒng)進(jìn)入死鎖狀態(tài)。數(shù)據(jù)B數(shù)據(jù)A8.3.3

封鎖帶來的問題(5)DBMS中有一個死鎖測試程序，每隔一段時間檢查并發(fā)的事務(wù)之間是否發(fā)生死鎖。如果發(fā)生死鎖，那么只能抽取某個事務(wù)作為犧牲品，把它撤消，做回退操作，解除它的所有封鎖，恢復(fù)到該事務(wù)的初始狀態(tài)。釋放出來的資源就可以分配給其他事務(wù)，使其他事務(wù)有可能繼續(xù)運(yùn)行下去，就有可能消除死鎖現(xiàn)象。理論上，系統(tǒng)進(jìn)入死鎖狀態(tài)時可能會有許多事務(wù)在相互等待，但是SystemR的實(shí)驗(yàn)表明，實(shí)際上絕大部分的死鎖只涉及到兩個事務(wù)，也就是事務(wù)依賴圖中的循環(huán)里只有兩個事務(wù)。有時，死鎖也被形象地稱作“死死擁抱”（DeadlyEmbrace）。8.3數(shù)據(jù)庫的并發(fā)控制8.3.1并發(fā)操作帶來的三個問題8.3.2封鎖技術(shù)8.3.3封鎖帶來的問題8.3.4并發(fā)操作的調(diào)度8.3.5SQL對事務(wù)處理的支持事務(wù)的調(diào)度：事務(wù)的執(zhí)行次序稱為“調(diào)度”。串行調(diào)度：如果多個事務(wù)依次