基于封鎖的并發(fā)控制(數(shù)據(jù)庫)

時(shí)間：2022-12-28 10:30:01 | 來源：信息時(shí)代

時(shí)間：2022-12-28 10:30:01 來源：信息時(shí)代

    基于封鎖的并發(fā)控制 : 利用封鎖機(jī)制(加鎖和解鎖)來控制多個(gè)事務(wù)的并發(fā)執(zhí)行,以保證該多個(gè)事務(wù)并發(fā)執(zhí)行的正確性。
封鎖(locking),顧名思義就是對(duì)一個(gè)數(shù)據(jù)對(duì)象在一定時(shí)間一定強(qiáng)度的獨(dú)占。事務(wù)在對(duì)某個(gè)數(shù)據(jù)對(duì)象(例如表、元組等)操作之前,向DBMS發(fā)出申請(qǐng),對(duì)其加鎖。在這個(gè)事務(wù)對(duì)該對(duì)象解鎖之前,其他事務(wù)就不可以更新該對(duì)象。
利用封鎖就可以強(qiáng)制地讓那些競爭同一資源的事務(wù)之間形成等待關(guān)系,而讓那些相互沒有資源競爭關(guān)系的事務(wù)之間可以隨意地執(zhí)行。
根據(jù)對(duì)封鎖對(duì)象的獨(dú)占強(qiáng)度,封鎖可以分為排他鎖和共享鎖。排他鎖(exclusive lock)也稱寫鎖或X鎖,是指對(duì)資源的獨(dú)占性封鎖,當(dāng)一個(gè)數(shù)據(jù)對(duì)象被加了排他鎖后,其他事務(wù)就不能讀或者更新該對(duì)象。有的時(shí)候,排他鎖顯得過于嚴(yán)格,不利于提高事務(wù)執(zhí)行的并發(fā)度。比如,兩個(gè)事務(wù)對(duì)同一個(gè)對(duì)象A都是讀操作,并不修改這個(gè)對(duì)象,那么就沒有必要相互阻塞,可以同時(shí)讀取。將這樣的鎖稱為共享鎖(shared lock),也稱讀鎖或S鎖。當(dāng)一個(gè)數(shù)據(jù)對(duì)象被加了共享鎖后,允許其他事務(wù)讀該數(shù)據(jù)對(duì)象,但是不允許修改。
讀鎖和寫鎖之間的關(guān)系可以用下面的相容矩陣來描述:

	X-LOCK	S-LOCK
X-LOCK	N	N
S-LOCK	N	Y

相容矩陣中的Y表示相容,也就是可以同時(shí)加于同一個(gè)數(shù)據(jù)對(duì)象上,而N表示不相容。
若一個(gè)事務(wù)對(duì)數(shù)據(jù)對(duì)象A加了X鎖,那么只允許該事務(wù)對(duì)該數(shù)據(jù)對(duì)象進(jìn)行讀取和更新,其他任何事務(wù)都不能再對(duì)A加任何類型的鎖,也不能進(jìn)行任何類型的操作,直到事務(wù)釋放了對(duì)A的鎖。
若一個(gè)事務(wù)對(duì)數(shù)據(jù)對(duì)象A加了S鎖,那么該事務(wù)可以讀但是不能寫A,其他事務(wù)只能再對(duì)A加S鎖,而不能加X鎖。這就保證了其他事務(wù)可以讀A,但是不能修改。
封鎖僅僅提供了一種調(diào)度并發(fā)事務(wù)的基本的手段,并不能解決調(diào)度的正確性問題,而且還會(huì)引起一些新的問題,包括死鎖和活鎖。
死鎖(deadlock):是多個(gè)事務(wù)之間在競爭同一個(gè)共享對(duì)象的封鎖時(shí),形成一種相互等待的現(xiàn)象,造成事務(wù)的停滯。死鎖的發(fā)生可能出現(xiàn)在多個(gè)事務(wù)同時(shí)運(yùn)行時(shí)。
活鎖(livelock): 一個(gè)事務(wù)長時(shí)間不能獲得對(duì)某個(gè)對(duì)象的封鎖,從而造成事實(shí)上的長時(shí)間停滯。這種情況也稱餓死(starvation)。
假如有兩個(gè)事務(wù)A和B,事務(wù)A已經(jīng)擁有對(duì)數(shù)據(jù)對(duì)象O₁的封鎖,并等待對(duì)O₂的封鎖,而事務(wù)B相反,已經(jīng)擁有對(duì)O₂的封鎖并在等待對(duì)O₁的封鎖。兩者形成了相互等待的這樣一種狀態(tài),事務(wù)執(zhí)行被阻塞。這種狀態(tài)稱為死鎖。假如有一個(gè)事務(wù)A在等待對(duì)數(shù)據(jù)對(duì)象O的封鎖,有另一個(gè)事務(wù)B₁目前擁有對(duì)O的封鎖,在B₁釋放了對(duì)O的封鎖后,由于某種原因,事務(wù)A沒有獲得對(duì)O的封鎖,而是另一個(gè)新的事務(wù)B₂獲得了對(duì)O的封鎖,如果這種狀況一直持續(xù)下去,事務(wù)A總是不能獲得對(duì)O的封鎖,那么事務(wù)A形成了事實(shí)上的被阻塞,這種狀態(tài)稱為活鎖。
死鎖和活鎖都會(huì)造成事務(wù)執(zhí)行被阻塞,影響系統(tǒng)的正常運(yùn)行,都是并發(fā)控制必須解決的問題。但是造成這些問題原因不在封鎖本身,而是出在使用封鎖的方式上。因此,什么樣的封鎖約定(協(xié)議)能夠確保調(diào)度的正確性,合理解決死鎖/活鎖問題,同時(shí)又有高的性能是數(shù)據(jù)庫并發(fā)控制部件最為關(guān)心的。
封鎖協(xié)議(locking protocol)是關(guān)于系統(tǒng)如何運(yùn)用封鎖機(jī)制實(shí)現(xiàn)正確高效并發(fā)控制的約定。封鎖協(xié)議要保證事務(wù)被正確執(zhí)行,避免死鎖發(fā)生,并具有滿意的性能。這些要求中,保證正確性是最重要的,在保證正確性的前提下,如何提高系統(tǒng)的事務(wù)處理吞吐量也是一個(gè)重要的方面。下面的封鎖協(xié)議能保證事務(wù)的正確執(zhí)行,但執(zhí)行效率不一定很高:
加鎖規(guī)則1: 對(duì)修改的數(shù)據(jù)對(duì)象要加X鎖,對(duì)只讀的數(shù)據(jù)對(duì)象要加S鎖,一個(gè)數(shù)據(jù)對(duì)象如果已經(jīng)被加了鎖,那么就不能再對(duì)其加其他不相容的鎖。
持鎖規(guī)則2: 事務(wù)一旦獲得某個(gè)封鎖就一直保持到事務(wù)結(jié)束。
解鎖規(guī)則3: 事務(wù)不能對(duì)沒有加鎖的數(shù)據(jù)對(duì)象解鎖,在事務(wù)結(jié)束的時(shí)候要釋放其擁有的全部的鎖。
影響最大的封鎖協(xié)議是1976年由Eswaran提出的兩階段封鎖協(xié)議(two-phase locking protocol,2PL)。它可以認(rèn)為是對(duì)上述封鎖協(xié)議中持鎖協(xié)議規(guī)則的一個(gè)改進(jìn)。
所有事務(wù)的執(zhí)行都區(qū)分為加鎖和解鎖兩個(gè)階段: 在對(duì)任何數(shù)據(jù)進(jìn)行讀寫操作之前,首先要申請(qǐng)并獲得對(duì)該數(shù)據(jù)的相應(yīng)的封鎖。在釋放了一個(gè)封鎖之后,該事務(wù)不再申請(qǐng)和獲得任何其他封鎖。
已經(jīng)證明了遵循2PL的調(diào)度是一種可串行化調(diào)度算法,因此2PL是正確的。但是,必須說明的是,2PL協(xié)議可能造成死鎖。正確性和活鎖/死鎖是不同的兩件事情,正確的調(diào)度也不能保證不出現(xiàn)死鎖。反過來,不出現(xiàn)死鎖的調(diào)度也不一定是正確的調(diào)度。
死鎖預(yù)防也可以通過遵循一定的協(xié)議方式來避免。以下規(guī)則中的任何一條都可以用來作為死鎖預(yù)防協(xié)議:
(1)預(yù)先資源申明規(guī)則: 在事務(wù)開始執(zhí)行之前,要求預(yù)先申請(qǐng)到全部資源。
(2)預(yù)先資源排序規(guī)則: 預(yù)先對(duì)全部數(shù)據(jù)對(duì)象進(jìn)行排序,任何事務(wù)都要求按照這個(gè)順序?qū)?shù)據(jù)對(duì)象加鎖。
(3)預(yù)先事務(wù)排序規(guī)則: 對(duì)競爭資源的事務(wù)進(jìn)行排序,按照這個(gè)順序進(jìn)行執(zhí)行。
(4)事務(wù)回滾規(guī)則: 一個(gè)事務(wù)在申請(qǐng)加鎖時(shí)如果被拒絕,不是等待而是采取回滾的方式,將已經(jīng)占有的資源退出來,重新啟動(dòng)該事務(wù)的執(zhí)行。
需要說明的是,由于死鎖發(fā)生的幾率并不大,按照上述協(xié)議來執(zhí)行,限制較多,影響了實(shí)際系統(tǒng)的效率,因此,在很多實(shí)際的數(shù)據(jù)庫系統(tǒng)中并不采用協(xié)議這種方式來避免死鎖,而是采用檢測(cè)的方法發(fā)現(xiàn)死鎖,然后采用其他補(bǔ)救措施,比如,取消處于死鎖中的某個(gè)事務(wù),然后再重新啟動(dòng)該事務(wù)的執(zhí)行。
數(shù)據(jù)庫的封鎖對(duì)象可以是邏輯單元(如關(guān)系的屬性值、元組、關(guān)系、索引項(xiàng))也可以是物理單元(數(shù)據(jù)塊)。這些對(duì)象有大有小,封鎖對(duì)象的大小,直接影響到封鎖的代價(jià)和并發(fā)度。一般而言,封鎖的粒度越大,并發(fā)度就越小,同時(shí)所需要的鎖資源就越少,封鎖的代價(jià)就越小。反之,封鎖粒度越小,并發(fā)度就越大,所需的鎖資源就越多,封鎖的代價(jià)就越大。因此,如果系統(tǒng)能夠根據(jù)事務(wù)的特征,選擇合適的封鎖粒度,并且在必要時(shí)進(jìn)行封鎖粒度的轉(zhuǎn)換,將是非常理想的。這種封鎖方法稱為多粒度封鎖。
數(shù)據(jù)庫中的對(duì)象,從數(shù)據(jù)庫到關(guān)系再到元組形成一個(gè)自然的層次結(jié)構(gòu)(樹),這個(gè)層次結(jié)構(gòu)以數(shù)據(jù)庫為根結(jié)點(diǎn),以元組為葉結(jié)點(diǎn)。這個(gè)層次結(jié)構(gòu)稱為多粒度樹。
樹中的每一個(gè)結(jié)點(diǎn)都可以被加鎖,對(duì)一個(gè)結(jié)點(diǎn)加鎖,意味著對(duì)這個(gè)結(jié)點(diǎn)的全部后代結(jié)點(diǎn)也加上了同樣類型的鎖。該結(jié)點(diǎn)上加的鎖為顯式封鎖,而后代結(jié)點(diǎn)上的鎖為隱式封鎖。盡管有這種稱呼上的區(qū)別,但是其效果是一樣的。因此,系統(tǒng)在檢查封鎖之間的相容性的時(shí)候,不僅要檢查顯式封鎖,還要檢查隱式封鎖。這樣一來,給檢查工作帶來了很大的麻煩。當(dāng)試圖給某個(gè)數(shù)據(jù)對(duì)象加鎖時(shí),系統(tǒng)要檢查這個(gè)數(shù)據(jù)對(duì)象上的所有顯式封鎖,還要檢查其所有的祖先結(jié)點(diǎn),看本結(jié)點(diǎn)的所有隱式封鎖是否與擬加的鎖沖突。不僅如此,還要檢查其所有的下屬結(jié)點(diǎn)上的顯式封鎖是否與擬加的封鎖沖突。顯然,這樣的檢查方法的效率是很低的。
為了解決上述問題,引進(jìn)一種新的封鎖類型,稱為意向鎖(intension lock)。當(dāng)系統(tǒng)要對(duì)某一個(gè)數(shù)據(jù)對(duì)象加鎖時(shí),必須首先對(duì)該對(duì)象的上層結(jié)點(diǎn)加意向鎖。有三種意向鎖:
(1)意向共享鎖(IS鎖): 當(dāng)某結(jié)點(diǎn)擬加S鎖時(shí),它的全部祖先結(jié)點(diǎn)要加IS鎖。
(2)意向排他鎖(IX鎖):當(dāng)某結(jié)點(diǎn)擬加X鎖時(shí),它的全部祖先結(jié)點(diǎn)要加IX鎖。
(3)共享意向排他鎖(SIX鎖): 當(dāng)一個(gè)對(duì)象加SIX鎖時(shí),表示對(duì)它既加S鎖又加IX鎖,即SIX=S+IX。
這些鎖的相容矩陣如下:

	S	X	IS	IX	SIX
S	Y	N	Y	N	N
X	N	N	N	N	N
IS	Y	N	Y	Y	Y
IX	N	N	Y	Y	N
SIX	N	N	Y	N	N

多粒度封鎖協(xié)議提高了系統(tǒng)的并發(fā)度,同時(shí)減少了開銷。它已經(jīng)在實(shí)際的數(shù)據(jù)庫產(chǎn)品中得到了廣泛的應(yīng)用。
封鎖是通過一個(gè)鎖表來實(shí)現(xiàn)的。一個(gè)鎖表的記錄就是某個(gè)數(shù)據(jù)庫元素及與之相應(yīng)的封鎖信息。通常按照數(shù)據(jù)庫元素來組織,每一個(gè)記錄包括對(duì)該數(shù)據(jù)庫元素施加了封鎖的全部事務(wù)的封鎖類型和狀態(tài)等信息。