數(shù)據(jù)庫原理與應(yīng)用 課件 第7章 數(shù)據(jù)庫并發(fā)控制

第7章數(shù)據(jù)庫并發(fā)控制主要內(nèi)容7.1并發(fā)控制概述7.2封鎖7.3封鎖協(xié)議7.4活鎖和死鎖7.5并發(fā)調(diào)度的可串行性7.6兩段鎖協(xié)議7.7鎖的粒度7.8并發(fā)控制的時間戳方法7.9本章小結(jié)7.1并發(fā)控制概述

第7章數(shù)據(jù)庫并發(fā)控制7.1并發(fā)控制概述7.1并發(fā)控制概述允許多個用戶同時使用的數(shù)據(jù)庫系統(tǒng)稱為多用戶數(shù)據(jù)庫系統(tǒng)。例如飛機訂票數(shù)據(jù)庫系統(tǒng)、銀行數(shù)據(jù)庫系統(tǒng)等都是多用戶數(shù)據(jù)庫系統(tǒng)。在這樣的系統(tǒng)中，在同一時刻并發(fā)運行的事務(wù)數(shù)可達數(shù)百個。事務(wù)可以一個一個地串行執(zhí)行，即每個時刻只有一個事務(wù)運行，其他事務(wù)必須等到這個事務(wù)結(jié)束以后方能運行。事務(wù)在執(zhí)行過程中需要不同的資源，有時需要CPU，有時需要存取數(shù)據(jù)庫，有時需要I/O，有時需要通信。如果事務(wù)串行執(zhí)行，則許多系統(tǒng)資源將處于空閑狀態(tài)。因此，為了充分利用系統(tǒng)資源發(fā)揮數(shù)據(jù)庫共享資源的特點，應(yīng)該允許多個事務(wù)并行地執(zhí)行。47.1并發(fā)控制概述例題7.1設(shè)T1，T2，T3是如下三個事務(wù)，其中R為數(shù)據(jù)庫中某個數(shù)據(jù)項，設(shè)R的初值為0。T1：R：=R+5

T2：R：=R*3

T3：R：=2若允許三個事務(wù)并行執(zhí)行，試列出所有可能的正確結(jié)果。例題解析：有6種可能的情況（1）T1-T2-T3：R=2（2）T1-T3-T2：R=6（3）T2-T1-T3：R=2（4）T2-T3-T1：R=7（5）T3-T1-T2：R=21（6）T3-T2-T1：R=115事務(wù)并發(fā)執(zhí)行帶來的問題：會產(chǎn)生多個事務(wù)同時存取同一數(shù)據(jù)的情況；可能會存取和存儲不正確的數(shù)據(jù)，破壞事務(wù)一致性和數(shù)據(jù)庫的一致性。下面看一個實例，說明并發(fā)操作帶來的數(shù)據(jù)不一致問題：例題7.2飛機訂票系統(tǒng)中的一個活動序列

1．甲售票點(甲事務(wù))讀出某航班的機票余額A，設(shè)A=100；2．乙售票點(乙事務(wù))讀出同一航班的機票余額A，也為100；3．甲售票點賣出十張機票，修改余額A←A-10，所以A為90，把A寫回數(shù)據(jù)庫；4．乙售票點也賣出十張機票，修改余額A←A-10，所以A為90，把A寫回數(shù)據(jù)庫。6結(jié)果明明賣出二十張機票，數(shù)據(jù)庫中機票余額只減少10。這種情況稱為數(shù)據(jù)這種情況稱為數(shù)據(jù)庫的不一致性，是由并發(fā)操作引起的。在并發(fā)操作情況下，對甲、乙兩個事務(wù)的操作序列的調(diào)度是隨機的。若按上面的調(diào)度序列執(zhí)行，甲事務(wù)的修改就被丟失。原因：第4步中乙事務(wù)修改A并寫回后覆蓋了甲事務(wù)的修改。當(dāng)并發(fā)事物以不受控制的方式進行執(zhí)行時，可能會出現(xiàn)一些問題。并發(fā)操作帶來的數(shù)據(jù)不一致性包括三類：丟失更新問題（LostUpdate），不可重復(fù)讀問題（Non-repeatableRead）和讀“臟”數(shù)據(jù)問題（DirtyRead）。77.1.1丟失更新問題當(dāng)兩個事物訪問相同的數(shù)據(jù)庫項時就會出現(xiàn)丟失更新的問題，使得某些數(shù)據(jù)庫項的值會不正確。換句話說，如果事務(wù)T1和事務(wù)T2都是先讀一條記錄，然后進行修改，那么第一個更新的影響將被第二個更新所覆蓋。上面的例題7.2飛機訂票的例子就屬此類。8表7.1說明了有丟失更新問題發(fā)生的執(zhí)行順序，從這個表中可以觀察到，當(dāng)?shù)诙€事務(wù)T2開始讀取A的值時，第一個事務(wù)T1還沒有提交。因此，事務(wù)T2仍然是在A=100這個值上進行操作，得到結(jié)果A=90。同時，事務(wù)T1將A=90這個值寫回到磁盤存儲中，這樣它就立即被事務(wù)T2重寫了。因此，在整個過程中丟失了賣出10張票。97.1.2不可重復(fù)讀問題當(dāng)某個事務(wù)在一些數(shù)據(jù)集上計算一些匯總（集合）函數(shù)，而其他的事務(wù)正在修改這些數(shù)據(jù)時就會出現(xiàn)不可重復(fù)讀（或者更新不一致的檢索）問題。這個問題是事務(wù)可能在一些數(shù)據(jù)被更改之前讀取而另一些數(shù)據(jù)是在被更改之后讀取，因此產(chǎn)生了不一致的結(jié)果。在不可重復(fù)讀中，事務(wù)T1讀取一個記錄，然后在事務(wù)T2更改這個記錄時進行一些其他的處理?，F(xiàn)在，如果事物T1重新讀取這個記錄，則新的值將和之前的值不一致。10不可重復(fù)讀包括三種情況：（1）事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對其做了修改，當(dāng)事務(wù)T1再次讀該數(shù)據(jù)時，得到與前一次不同的值。（2）事務(wù)T1按一定條件從數(shù)據(jù)庫中讀取了某些數(shù)據(jù)記錄后，事務(wù)T2刪除了其中部分記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時，發(fā)現(xiàn)某些記錄消失了。（3）事務(wù)T1按一定條件從數(shù)據(jù)庫中讀取某些數(shù)據(jù)記錄后，事務(wù)T2插入了一些記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時，發(fā)現(xiàn)多了一些記錄。后兩種不可重復(fù)讀有時也稱為幻影現(xiàn)象（PhantomRow）。11127.1.3讀“臟”數(shù)據(jù)問題當(dāng)一個事務(wù)修改數(shù)據(jù)庫項，卻由于某些原因使得事務(wù)失敗了，而被修改的數(shù)據(jù)庫項在被修改回原來的原始值之前又被其他的事務(wù)訪問了，這是就會出現(xiàn)讀“臟”數(shù)據(jù)的問題。也就是說，事務(wù)T1修改某一數(shù)據(jù)，并將其寫回磁盤，事務(wù)T2讀取同一數(shù)據(jù)后，T1由于某種原因被撤銷，這時T1已修改過的數(shù)據(jù)恢復(fù)原值，T2讀到的數(shù)據(jù)就與數(shù)據(jù)庫中的數(shù)據(jù)不一致，T2讀到的數(shù)據(jù)就為“臟”數(shù)據(jù)，即不正確的數(shù)據(jù)。13147.2封鎖

第7章數(shù)據(jù)庫并發(fā)控制7.2封鎖封鎖是并發(fā)控制中的加鎖方法，是實現(xiàn)并發(fā)控制的一個非常重要的技術(shù)。鎖是與數(shù)據(jù)項有關(guān)的一個變量，它描述了數(shù)據(jù)項的狀態(tài)，這個狀態(tài)反映了在數(shù)據(jù)項上可進行的操作。它防止第二個事務(wù)在第一個事務(wù)完成它全部活動之前，對數(shù)據(jù)庫記錄進行訪問。打個比方，事務(wù)T在對某個數(shù)據(jù)對象例如表、記錄等操作之前，先向系統(tǒng)發(fā)出請求，對其加鎖。加鎖后事務(wù)T就對該數(shù)據(jù)對象有了一定的控制，在事務(wù)T釋放它的鎖之前，其他的事務(wù)不能更新此數(shù)據(jù)對象。通常，在數(shù)據(jù)庫中每個數(shù)據(jù)項都有一個鎖。鎖作為同步化并發(fā)事務(wù)對數(shù)據(jù)庫訪問的一種手段而被廣泛使用。因此，封鎖模式用于允許并發(fā)執(zhí)行兼容的操作。換句話說，可交換的活動是兼容的。封鎖是并發(fā)控制最常使用的形式，而且它也是大多數(shù)應(yīng)用程序所選擇的方法。167.2封鎖基本的封鎖類型有兩種:排他鎖(ExclusiveLocks，簡稱X鎖，也稱寫鎖)和共享鎖(ShareLocks，簡稱S鎖，也稱讀鎖)。排他鎖又稱為寫鎖。若事務(wù)T對數(shù)據(jù)對象A加上X鎖，則只允許T讀取和修改A，其他任何事務(wù)都不能再對A加任何類型的鎖，直到T釋放A上的鎖。這就保證了其他事務(wù)在T釋放A上的鎖之前不能再讀取和修改A。

共享鎖又稱為讀鎖。若事務(wù)T對數(shù)據(jù)對象A加上S鎖，則事務(wù)T可以讀A但不能修改A，其他事務(wù)只能再對A加S鎖，而不能加X鎖，直到T釋放A上的S鎖。這就保證了其他事務(wù)可以讀A，但在T釋放A上的S鎖之前不能對A做任何修改。177.2封鎖在鎖的相容矩陣中，如表7.4所示，最左邊一列表示事務(wù)T1已經(jīng)獲得的數(shù)據(jù)對象上的鎖的類型，其中橫線表示沒有加鎖。最上面一行表示另一事務(wù)T2對同一數(shù)據(jù)對象發(fā)出的封鎖請求。T2的封鎖請求能否被滿足用矩陣中的Y和N表示，Y表示事務(wù)T2的封鎖要求與T1已持有的鎖相容，封鎖請求可以滿足，N表示T2的封鎖請求與T1已持有的鎖沖突，T2的請求被拒絕。187.3封鎖協(xié)議在運用X鎖和S鎖這兩種基本鎖對數(shù)據(jù)對象加鎖時，還需要約定一些規(guī)則，例如何時申請X鎖或S鎖、持鎖時間、何時釋放等。這些規(guī)則被稱為封鎖協(xié)議（LockingProtocol）。對封鎖方式規(guī)定不同的規(guī)則，就形成了各種不同的封鎖協(xié)議。下面介紹三級封鎖協(xié)議。197.3封鎖協(xié)議7.3.1一級封鎖協(xié)議一級封鎖協(xié)議是：事務(wù)T在修改數(shù)據(jù)R之前必須先對其加X鎖，直到事務(wù)結(jié)束才釋放。事務(wù)結(jié)束包括正常結(jié)束（COMMIT）和非正常結(jié)束（ROLLBACK）。一級封鎖協(xié)議可防止丟失修改，并保證事務(wù)T是可恢復(fù)的。在一級封鎖協(xié)議中，如果僅僅是讀數(shù)據(jù)不對其進行修改，是不需要加鎖的，所以它不能保證可重復(fù)讀和不讀“臟”數(shù)據(jù)。207.3封鎖協(xié)議7.3.2二級封鎖協(xié)議二級封鎖協(xié)議是：在一級封鎖協(xié)議基礎(chǔ)上，事務(wù)T在讀取數(shù)據(jù)R之前必須先對其加S鎖，讀完后即可釋放S鎖。二級封鎖協(xié)議除防止了丟失修改，還可進一步防止讀“臟”數(shù)據(jù)。在二級封鎖協(xié)議中，由于讀完數(shù)據(jù)后即可釋放S鎖，所以它不能保證可重復(fù)讀。217.3封鎖協(xié)議7.3.3三級封鎖協(xié)議三級封鎖協(xié)議是：在一級封鎖協(xié)議基礎(chǔ)上，事務(wù)T在讀取數(shù)據(jù)R之前必須先對其加S鎖，直到事務(wù)結(jié)束才釋放。三級封鎖協(xié)議除防止了丟失修改和讀“臟”數(shù)據(jù)外，還進一步防止了不可重復(fù)讀。上述三級協(xié)議的主要區(qū)別在于什么操作需要申請封鎖，以及何時釋放鎖(即持鎖時間)。227.3封鎖協(xié)議237.4活鎖和死鎖

第7章數(shù)據(jù)庫并發(fā)控制7.4活鎖和死鎖和操作系統(tǒng)一樣，封鎖的方法可能引起活鎖和死鎖。死鎖(DeadLock)和活鎖(LiveLock)是并發(fā)應(yīng)用程序經(jīng)常發(fā)生的問題，也是多線程編程中的重要概念。以下是對死鎖和活鎖的形象描述。

現(xiàn)有一條路，兩個人寬，從兩個相對的方向迎面走來兩個人A和B。

死鎖的情況：A和B兩個人都不愿意給對方讓路，所以A和B都在等對方先讓路，導(dǎo)致誰也過不去。

活鎖的情況：A和B兩個人都主動給別人讓路。A往左移，同時B往右移；A往右移，同時B往左移。A和B在移動的時候，同時擋住對方，導(dǎo)致誰也過不去。

257.4活鎖和死鎖7.4.1活鎖如果事務(wù)T1封鎖了數(shù)據(jù)R，事務(wù)T2又請求封鎖R，于是T2等待。T3也請求封鎖R，當(dāng)T1釋放了R上的封鎖之后系統(tǒng)首先批準(zhǔn)了T3的請求，T2仍然等待。然后T4又請求封鎖R，當(dāng)T3釋放了R上的封鎖之后系統(tǒng)又批準(zhǔn)了T4的請求……，T2有可能永遠等待，這就是活鎖（LiveLock）的情形，如表7.5所示。267.4活鎖和死鎖277.4活鎖和死鎖避免活鎖的簡單方法是采用先來先服務(wù)的策略。當(dāng)多個事務(wù)請求封鎖同一數(shù)據(jù)對象時，封鎖子系統(tǒng)按請求封鎖的先后次序?qū)κ聞?wù)排隊，數(shù)據(jù)對象上的鎖一旦釋放就批準(zhǔn)申請隊列中第一個事務(wù)獲得鎖。287.4活鎖和死鎖7.4.2死鎖死鎖（DeadLock）是集合中的兩個（或多個）事務(wù)同時等待集合中的其他事務(wù)釋放鎖的情況。所有的事務(wù)都不能繼續(xù)執(zhí)行了，因為集合中的每個事務(wù)都在一個等待隊列中，等待集合中的一個其他事物釋放數(shù)據(jù)項上的鎖。297.4活鎖和死鎖307.4活鎖和死鎖如表7.7所示：如果事務(wù)T1封鎖了數(shù)據(jù)R1，T2封鎖了數(shù)據(jù)R2，然后T1又請求封鎖R2，因T2已封鎖了R2，于是T1等待T2釋放R2上的鎖。接著T2又申請封鎖R1，因T1已封鎖了R1，T2也只能等待T1釋放R1上的鎖。這樣就出現(xiàn)了T1在等待T2，而T2又在等待T1的局面，T1和T2兩個事務(wù)永遠不能結(jié)束，形成死鎖。死鎖也成為循環(huán)等待情形，這里兩個事物互相等待（直接或間接）資源。因此在死鎖中，兩個事物互相排斥訪問下一個所需的記錄來完成它們的事務(wù)，也稱為死亡擁抱（DeadlyEmbrace）。317.4活鎖和死鎖7.5.3死鎖的檢測和預(yù)防死鎖檢測是由DBMS實現(xiàn)的一個定期檢測，以確定是否由于某些原因使得事務(wù)的等待時間超過了預(yù)定限制的情況。死鎖出現(xiàn)的頻率主要與查詢負(fù)荷以及數(shù)據(jù)庫的物理組織有關(guān)。為了計算死鎖的發(fā)生頻率，Gray在1981年提出了每秒產(chǎn)生的死鎖是多個程序的個數(shù)的平方和事務(wù)大小的四次方的論斷。檢測和預(yù)防死鎖的基本模式有如下三種：（1）從不允許死鎖發(fā)生（死鎖預(yù)防）（2）當(dāng)某事物被阻塞時檢測死鎖（死鎖檢測）（3）定期地檢查死鎖（死鎖避免）327.5并發(fā)調(diào)度的可串行性

第7章數(shù)據(jù)庫并發(fā)控制7.5并發(fā)調(diào)度的可串行性定義：多個事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行它們時的結(jié)果相同，我們稱這種調(diào)度策略為可串行化（Serializable）的調(diào)度?？纱行裕⊿erializability）是并發(fā)事務(wù)正確性的準(zhǔn)則。按這個準(zhǔn)則規(guī)定，一個給定的并發(fā)調(diào)度，當(dāng)且僅當(dāng)它是可串行化的，才認(rèn)為是正確調(diào)度。為了保證并發(fā)操作的正確性，DBMS的并發(fā)控制機制必須提供一定的手段來保證調(diào)度是可串行化的。347.5并發(fā)調(diào)度的可串行性從理論上講，在某一事務(wù)執(zhí)行時禁止其他事務(wù)執(zhí)行的調(diào)度策略一定是可串行化的調(diào)度，這也是最簡單的調(diào)度策略。但這種方法實際上是不可取的，因為它使得用戶不能充分共享數(shù)據(jù)庫資源。目前DBMS普遍采用封鎖方法實現(xiàn)并發(fā)操作調(diào)度的可串行性，從而保證調(diào)度的正確性。兩段鎖（Two-PhaseLocking，簡稱2PL）協(xié)議就是保證并發(fā)調(diào)度可串行性的封鎖協(xié)議。除此之外還有其他一些方法，如時間方法、樂觀方法等來保證調(diào)度的正確性。357.6兩段鎖協(xié)議

第7章數(shù)據(jù)庫并發(fā)控制7.6兩段鎖協(xié)議兩段鎖協(xié)議(Two-PhaseLocking，簡稱2PL)是控制并發(fā)處理的一個方法或一個協(xié)議。在兩段鎖中，所有的封鎖操作都在第一個解鎖操作之前。因此，如果事務(wù)中的所有加鎖操作（比如read_lock、write_lock）都在第一個解鎖操作之前，則稱此事務(wù)是遵循兩段鎖協(xié)議的。所謂兩段鎖協(xié)議是指所有事務(wù)必須分兩個階段對數(shù)據(jù)項加鎖和解鎖。在對任何數(shù)據(jù)進行讀、寫操作之前，首先要申請并獲得對該數(shù)據(jù)的封鎖；在釋放一個封鎖之后，事務(wù)不再申請和獲得任何其他封鎖。377.6兩段鎖協(xié)議事務(wù)分為兩個階段，第一階段是獲得封鎖，也稱為增長階段，在這個階段事務(wù)獲得所有需要的鎖而不釋放任何數(shù)據(jù)上的鎖。一旦獲得了所有的鎖，事務(wù)就處在它的鎖定點。第二階段是釋放封鎖，也稱為收縮階段，在這個階段事務(wù)釋放全部的鎖，并且不能再獲得任何新鎖。2PL的兩個階段如圖7.3所示：387.6兩段鎖協(xié)議397.6兩段鎖協(xié)議上述兩階段鎖有下述規(guī)則保證：（1）兩個事務(wù)不能有沖突的鎖。（2）在同一個事務(wù)中，任何解鎖操作都不能在加鎖操作之前。（3）在獲得所有的鎖之前不影響任何數(shù)據(jù)，即在事務(wù)處于它的鎖定點時才能影響數(shù)據(jù)。圖7.3說明了兩段鎖的示意圖，在嚴(yán)格的兩階段鎖中不允許有交叉。407.7鎖的粒度

第7章數(shù)據(jù)庫并發(fā)控制7.7鎖的粒度數(shù)據(jù)庫基本上是作為命名的數(shù)據(jù)項的集合，由并發(fā)控制程序選擇的作為保護單位的數(shù)據(jù)項的大小稱為粒度（Granularity）。封鎖對象可以是邏輯單元，也可以是物理單元。粒度是由并發(fā)控制子系統(tǒng)控制的獨立的數(shù)據(jù)單位，在基于鎖的并發(fā)控制機制中，粒度是一個可加鎖單位。鎖的粒度表明加鎖使用的級別。在最通常的情況下，鎖的粒度是數(shù)據(jù)頁。大多數(shù)商業(yè)數(shù)據(jù)庫系統(tǒng)都提供了不同的加鎖粒度。加鎖可以發(fā)生在下述級別上：數(shù)據(jù)庫級

表級頁級行（元組）級屬性（字段）級427.7鎖的粒度1．?dāng)?shù)據(jù)庫級鎖在數(shù)據(jù)庫級鎖上，整個數(shù)據(jù)庫被加鎖。因此，在事務(wù)T1執(zhí)行期間拒絕事務(wù)T2使用數(shù)據(jù)庫中的任何表。2．表級鎖在表級鎖上，對整個表進行加鎖。因此，在事務(wù)T1使用這個表時拒絕事務(wù)T2訪問表中的任何行（元組）。如果某個事務(wù)希望訪問一些表，則每個表都被加鎖。但兩個事物可以訪問相同的數(shù)據(jù)庫，只要它們訪問的表不同即可。表級鎖的限制比數(shù)據(jù)庫級鎖少，但當(dāng)有很多事務(wù)等待訪問相同的表時會引起阻塞，尤其是當(dāng)事務(wù)需要訪問相同表的不同部分而且彼此沒有相互干擾時，這個條件就成為一個問題。表級鎖不適合多用戶DBMS。437.7鎖的粒度3．頁級鎖在頁級鎖上，整個磁盤頁（或磁盤塊）被加鎖。一個表能夠跨多個頁，而一個頁也可以包含一個或者多個表的若干行（元組）。頁級鎖最適合多用戶DBMS。4．行級鎖在行級鎖上，對特定的行（或元組）進行加鎖，對數(shù)據(jù)庫中的每個表的每一行進行加鎖。DBMS允許并發(fā)事務(wù)訪問同一個表的不同行，即使這些行位于相同的頁上。行級鎖比數(shù)據(jù)庫級鎖、表級鎖或頁級鎖的限制要少很多，行級鎖提高了數(shù)據(jù)的可獲得性，但是對于行級鎖的管理需要很高的成本。5．屬性（或字段）級鎖在屬性級鎖上，對特定的屬性（或字段）進行加鎖。屬性級鎖允許并發(fā)事務(wù)訪問相同的行，只要這些事務(wù)是訪問行中的不同屬性即可。屬性集鎖為多用戶數(shù)據(jù)訪問產(chǎn)生了最大的靈活性，但它需要很高的系統(tǒng)開銷。447.8并發(fā)控制的時間戳方法

第7章數(shù)據(jù)庫并發(fā)控制7.8并發(fā)控制的時間戳方法時間戳是由DBMS創(chuàng)建的唯一標(biāo)識符，用于表示事務(wù)的相對啟動時間。時間戳可以看成是事務(wù)的啟動時間。由此，時間戳是并發(fā)控制的一個方法，在這個方法中，每個事務(wù)被賦予一個事務(wù)時間戳。事務(wù)時間戳是一個單調(diào)增長的數(shù)字，它通常是基于系統(tǒng)時鐘的。事務(wù)被管理成按時間戳順序進行，時間戳也可以通過每當(dāng)新事務(wù)啟動時增加一個局部計數(shù)器的方法產(chǎn)生，時間戳的值產(chǎn)生一個顯式的順序，這個順序是事務(wù)提交給DBMS的順序。時間戳必須有兩個性質(zhì)，即唯一性和單調(diào)性。唯一性假設(shè)不存在相同的時間戳值，單調(diào)性假設(shè)時間戳值總是增加的。在相同事務(wù)中對數(shù)據(jù)庫的Read和Write操作必須有相同的時間戳。DBMS按時間戳順序執(zhí)行沖突操作，因此確保了事務(wù)的可串行性。如果兩個事物沖突了，則通常是停止一個事務(wù)，重新調(diào)度這個事務(wù)并賦予一個新的時間戳值。467.8并發(fā)控制的時間戳方法1．粒度時間戳粒度時間戳是最后一個事務(wù)訪問它的時間戳的一個記錄，一個活動事務(wù)訪問的每個粒度必須有一個粒度時間戳?？梢员Ａ糇詈笠粋€讀和寫訪問的每個記錄。如果它們的存儲包括粒度，粒度時間戳可能對讀訪問引起額外的寫操作。粒度時間戳表中的每一項由粒度標(biāo)識符和事物時間戳組成，同時維護從表中刪除的包含最大（最近的）粒度時間戳的記錄。對粒度時間戳的查找可以使用粒度標(biāo)識符，也可以使用最大被刪除的時間戳。477.8并發(fā)控制的時間戳方法2．時間戳排序下述是基于時間戳的并發(fā)控制方法中的三個基本算法：（1）總時間戳排序總時間戳排序算法依賴于在時間戳排序中對訪問粒度的維護，他是在沖突訪問中終止一個事務(wù)。讀和寫的訪問之間沒有區(qū)別。因此，對每個粒度時間戳來說只需要一個值。（2）部分時間戳排序只排序不可交換的活動來提高總的時間戳排序。在這種情況下，同時存儲讀和寫粒度時間戳。這個算法允許比最后一個更改粒度的事務(wù)晚的任何事務(wù)讀取粒度。如果某個事務(wù)試圖更改之前已經(jīng)被事務(wù)訪問的粒度，則終止此事務(wù)。部分時間戳排序算法比總時間戳排序算法終止的事務(wù)少，但是其代價是需要存儲粒度時間戳的額外空間。487.8并發(fā)控制的時間戳方法（3）多版本時間戳排序此算法存儲幾個被更改粒度的版本，允許事務(wù)為它訪問的所有粒度查看一致的版本集合。因此，這個算法降低了重新啟動那些有寫—寫沖突的事務(wù)而產(chǎn)生的沖突。每次對粒度的更新都創(chuàng)建一個新的版本，這個版本包含相關(guān)的粒度時間戳。因此，多版本的時間戳等于或只剛剛小于此事務(wù)的時間戳。497.8并發(fā)控制的時間戳方法3．解決時間戳中的沖突為處理時間戳算法中的沖突，讓包含在沖突中的一些事務(wù)等待并