實時數(shù)據(jù)庫系統(tǒng)

實時數(shù)據(jù)庫系統(tǒng)之實時并發(fā)掌握合同實時數(shù)據(jù)庫技術(shù)是實時系統(tǒng)和數(shù)據(jù)庫技術(shù)相結(jié)合的產(chǎn)物，討論人員盼望采用數(shù)據(jù)庫技術(shù)來解決實時系統(tǒng)中的數(shù)據(jù)管理問題，同時采用實時技術(shù)為實時數(shù)據(jù)庫供應(yīng)時間驅(qū)動調(diào)度和資源安排算法。然而，實時數(shù)據(jù)庫并非是兩者在概念、結(jié)構(gòu)和方法上的簡潔集成。需要針對不同的應(yīng)用需求和應(yīng)用特點，對實時數(shù)據(jù)模型、實時事務(wù)調(diào)度與資源安排策略、實時數(shù)據(jù)查詢語言、實時數(shù)據(jù)通信等大量問題作深化的理論討論。并發(fā)掌握用于掌握并發(fā)執(zhí)行的事務(wù)之間的交互操作以避開數(shù)據(jù)庫的全都性被破壞［KOR86］。在傳統(tǒng)數(shù)據(jù)庫系統(tǒng)中，針對這個問題上有大量的討論工作【PAP8%實時數(shù)據(jù)庫中的并發(fā)掌握合同不僅要求保證數(shù)據(jù)的規(guī)律全都性，而且必需考慮滿意并發(fā)事務(wù)的截止期。優(yōu)先級反轉(zhuǎn)是傳統(tǒng)的并發(fā)掌握合同應(yīng)用于實時數(shù)據(jù)庫所表現(xiàn)出的主要問題［Sha%］。目前，很多面對實時數(shù)據(jù)庫的并發(fā)掌握合同已經(jīng)被提出［ABB88,HAR90,HUA91，LAM95,LAMO。，LIN99］,這些合同大多數(shù)可以歸結(jié)為基于鎖的方法與樂觀的并發(fā)掌握合同。1基于鎖的并發(fā)掌握合同保證可串行性的一種鎖機制是兩階段鎖(2PL：Two-PhaseLocking)合同，這個合同要求事務(wù)分為兩個階段提出加鎖與解鎖懇求。傳統(tǒng)數(shù)據(jù)庫系統(tǒng)中的討論表明，在大部分操作環(huán)境中基于鎖的合同性能優(yōu)于樂觀的合同［AGR87］。在實時數(shù)據(jù)庫中事務(wù)依據(jù)截止期或者重要性被安排優(yōu)先級，沖突解決機制偏向于具有較高優(yōu)先級的事務(wù)。但是2PL并未考慮事務(wù)的優(yōu)先級，當應(yīng)用于優(yōu)先級驅(qū)動的事務(wù)調(diào)度系統(tǒng)時，傾向于導(dǎo)致優(yōu)先級反轉(zhuǎn)與死鎖問題，因此一些討論在2PL合同中引入了基于優(yōu)先級的沖突解決機制以及優(yōu)先級繼承或者優(yōu)先級頂機制。基于優(yōu)先級的2PL變體合同主要包括：2PL-HP、2PL-WP、2PL-CPL2PL-CR等等。2PL-HP(2PL-HighPriority)fABB88,HAR90h也稱為2PL-PA(2PL-PriorityAbort),采納偏向于高優(yōu)先級事務(wù)的沖突解決方法，一旦檢測到?jīng)_突就馬上通過夭折低優(yōu)先級的事務(wù)解決全部的數(shù)據(jù)沖突。而2PL-WP(2PL-WaitPromote)lABB92,SHA9()l,也稱為2PL-PI(PriorityInheritance)lHUA92h是通過堵塞鎖懇求事務(wù)來解決沖突，其中包含了一種優(yōu)先級繼承機制。針對2PL-HP所進行的試驗結(jié)果［ABB89,HUA9網(wǎng)表明基于優(yōu)先級夭折方法的實時并發(fā)掌握合同相對于基于優(yōu)先級繼承方法的合同性能顯著要好。Stankovic等四人9舊也發(fā)覺2PL-HP在實時數(shù)據(jù)庫環(huán)境中優(yōu)于2PL-WP合同，并且認為基本的優(yōu)先級繼承并不適合于2PL合同中的沖突解決。Haritsa等〔HAR92］認為2PL-WP削減了高優(yōu)先級事務(wù)的堵塞時間，但是這種堵塞時間仍舊不確定。并且，在較高的數(shù)據(jù)競爭條件下，2PL-WP可能導(dǎo)致系統(tǒng)中的大部分事務(wù)在同樣的優(yōu)先級上執(zhí)行［LEE96］。毫無疑問，重啟接近完成的事務(wù)會導(dǎo)致CPU資源的鋪張，由于重啟要求被夭折事務(wù)的全部操作必需重做。而另一方面，堵塞可能導(dǎo)致較高優(yōu)先級的事務(wù)錯失截止期。因此，2PL-CPI(2PL-ConditionalPriorityInheritance)小出,幻是2PL-HP與2PL-WP的組合。在這種合同中，只有當沖突的低優(yōu)先級事務(wù)接近完成時才采納優(yōu)先級繼承，否則這個低優(yōu)先級事務(wù)被夭折。與2PL-CR特別類似的一個合同是2PL-CR(2PL-ConditionalRestart),依據(jù)下面的方法打算是否夭折較低優(yōu)先級的事務(wù):假如較高優(yōu)先級的事務(wù)的松弛時間大于其剩余執(zhí)行時間，則較低優(yōu)先級的事務(wù)連續(xù)執(zhí)行，否則夭折。在實時系統(tǒng)中，優(yōu)先級頂合同(PCP：PriorityCeilingProtocol)由叢峋能夠限制優(yōu)先級反轉(zhuǎn)不超過單個關(guān)鍵段的執(zhí)行時間，并且能夠避開死鎖。一些討論通過擴展優(yōu)先級頂合同來調(diào)度處理實時事務(wù)的并發(fā)執(zhí)行，最初L.Sha等1SHA%］使用讀/寫語義改進了PCP合同的性能,提出了RW-PCP(Read/WritePriorityCeilingProtocol)合同。為了進一步削減事務(wù)堵塞時間，K-W.Lam等在LAM。。］中引入了動態(tài)調(diào)整串行化挨次的思想增加了RW-PCP合同來處理硬實時事務(wù)。Tei-WeiKuo等［KUO98］則采納兩版本方法擴展了RW-PCP合同，重點是采用數(shù)據(jù)項的全都版本削減事務(wù)之間的寫-讀沖突。這些基于優(yōu)先級頂?shù)暮贤闹饕獌?yōu)點在于能夠供應(yīng)單堵塞與無死鎖特性，從而支持對硬實時事務(wù)進行可調(diào)度性分析。王宏安等［電子學報2005］通過引入靜態(tài)搶占等級的概念，基于EDF動態(tài)優(yōu)先級事務(wù)調(diào)度系統(tǒng)，提出了一種新的并發(fā)掌握合同MV-PL(Multi-Versiontwo-phaselockingbasedonPreemptionLevel)合同。合同中采納多版本機制，使得事務(wù)的串行化挨次不再由沖突的鎖懇求的挨次打算，而是能夠依據(jù)事務(wù)的優(yōu)先級進行動態(tài)地調(diào)整，因此能夠最小化不必要的事務(wù)堵塞，增加高優(yōu)先級事務(wù)的搶占力量。2樂觀的并發(fā)掌握合同基于鎖的并發(fā)掌握屬于悲觀的方法，總是假定事務(wù)沖突常常發(fā)生，而實際上鎖只在最壞情形下才是必要的。樂觀并發(fā)掌握基于相反的假設(shè)，事務(wù)沖突很少發(fā)生，因此允許事務(wù)無阻礙地執(zhí)行直到全部操作完成，然后在提交時進行驗證，假如通過了檢驗就提交，否則夭折。假如系統(tǒng)中事務(wù)之間的數(shù)據(jù)競爭很弱，大部分事務(wù)能夠通過驗證并提交；而假如事務(wù)之間的競爭越激烈，越多的事務(wù)就將被夭折并重啟，從而降低系統(tǒng)資源采用率［AGR87，BHG87,ELM95］。OCC合同中，事務(wù)的執(zhí)行分為三個階段：讀階段(Readphase)、驗證階段(Validationphase)與寫階段(Writephase)。而為了進行事務(wù)驗證，需要對每一活躍的事務(wù)Ti紀錄其讀和寫數(shù)據(jù)集：RS"］與WS［Ti］。OCC合同的關(guān)鍵是如何驗證事務(wù)，驗證方法包括：(1)后向驗證(Backwardvalidation)：針對最近提交的事務(wù)驗證要提交的事務(wù)。這種方法的缺點是檢驗沖突太遲，它實際上是檢驗全部已完成事務(wù)間的沖突，因此夭折與重啟的代價較大。(2)前向驗證(ForwardValidation)：針對活躍的事務(wù)驗證要提交的事務(wù)，當沖突存在時,有三種解決方法：1)夭折沖突的未完成的事務(wù)而讓驗證事務(wù)通過驗證而提交，OCC-BC(BroadcastCommit)就是這種策略的代表；2)夭折沖突中優(yōu)先級低的事務(wù)；3)讓驗證事務(wù)等待優(yōu)先級比它高的事務(wù)，而夭折優(yōu)先級比它低的事務(wù)。OCC合同依據(jù)驗證方法的不同，主要包括以下變體：OCC-BC(BroadcastCommit)OCC-BC合同中，當一個事務(wù)提交時，它通知全部正在運行的沖突的事務(wù)，并且這些事務(wù)將被馬上重啟。這里，沒必要檢查與已經(jīng)提交事務(wù)之間的沖突，由于當前驗證的事務(wù)假如與任何提交的事務(wù)之間存在沖突，則它必定在到達驗證階段之前已經(jīng)被重啟。這意味著一旦一個事務(wù)到達驗證階段，就能保證提交。這個合同中采納的方法是前向驗證，相對于后向驗證，會較早重啟沖突的事務(wù)，因而削減了資源鋪張，增加了事務(wù)滿意截止期的機會［haR9>HAR90b］oOCC-SacrificeOCC-Sacrifice合同【har9。，har92］修改了OCC-BC合同，結(jié)合了基于優(yōu)先級的犧牲機制。定義全部與當前驗證事務(wù)沖突的事務(wù)組成一個沖突集，假如沖突集中存在一個或者多個較高優(yōu)先級的事務(wù)，則驗證事務(wù)將被重啟，即驗證的事務(wù)為了保證較高優(yōu)先級的事務(wù)滿意截止期而犧牲。盡管這個合同能夠優(yōu)先對待較高優(yōu)先級的事務(wù)，但是也存在鋪張的重啟(Wasted-restart)問題。OCC-Wait與Wait-50OCC-Wait合同［HAR92屎納了基于優(yōu)先級的事務(wù)等待機制。在這個合同中，假如一個到達驗證階段的事務(wù)發(fā)覺其沖突集中存在較高優(yōu)先級的事務(wù)，則被迫去等待，從而給較高優(yōu)先級的事務(wù)先滿意截止期的機會。Wait-50方法是OCC-Wait的擴展，一個驗證的事務(wù)只有當其沖突集中的事務(wù)超過50%具有較高的優(yōu)先級時才等待。其實，Wait-50是BC與Wait方法的折衷，因此能夠得到更加一般性的方法Wait-x。Haritsa等〔HAR92］針對不同的犬進行了試驗，結(jié)果概括如下：(1)降低x為25%會導(dǎo)致系統(tǒng)在正常負載下性能有稍微的改進，但是隨著負載增加，性能消失降級，這時由于較低的界限增加了事務(wù)等待的因素；(2)上升x為75%導(dǎo)致正好相反的效果。因此，采用系統(tǒng)負載信息動態(tài)調(diào)整x的值能夠改進Wait-x合同的性能。OCC-TI與OCC-APROCC-TI(TimestampInterval)【lee93,lee96］合同采納時間戳間隔解決事務(wù)間的沖突，每個事務(wù)在讀階段被安排一個時間戳間隔一或者稱為時間槽，這個時間槽用于紀錄事務(wù)執(zhí)行過程中臨時的串行化挨次。無論何時，由于沖突的數(shù)據(jù)操作或者其它事務(wù)的驗證導(dǎo)致事務(wù)的串行化挨次被轉(zhuǎn)變，這個時間槽也被相應(yīng)地調(diào)整以體現(xiàn)這些相關(guān)性。因此，與其它樂觀方法不同之處在于，OCC-TI合同并不依靠于這種設(shè)想：事務(wù)串行化挨次與事務(wù)到達驗證階段的挨次一樣。Haritsa等1瓶口92］認為解決沖突時考慮事務(wù)的優(yōu)先級對于增加occ合同的性能是一個重要的打算性因素。同時，Lee等Lee93,DAT97］進行的討論表明，實時并發(fā)掌握合同的主要打算性因素是事務(wù)重啟的數(shù)量，削減重啟數(shù)量是突破這些合同性能約束的關(guān)鍵因素。為了削減事務(wù)重啟的數(shù)量，Datta等IDA?。菰噲D在OCC-TI中使用優(yōu)先級信息解決數(shù)據(jù)沖突，其中打算重啟驗證事務(wù)而允許不行調(diào)和的事務(wù)連續(xù)執(zhí)行的條件是：(1)假如正在驗證的事務(wù)的截止期足夠遠，重啟后仍能滿意截止期；(2)不行調(diào)和的事務(wù)集大的足以做出這種冒險式的犧牲。結(jié)果表明，重啟的驗證事務(wù)與不行調(diào)和的事務(wù)集都能夠更好地滿意它們的截止期。為了進一步提高重啟驗證事務(wù)并滿意其截止期的把握，Datta等PAT97］試圖約束重啟事務(wù)所要求的執(zhí)行時間。假設(shè)重啟的事務(wù)將訪問從前運行時曾經(jīng)訪問過的同樣的數(shù)據(jù)集，并且既然這個事務(wù)已經(jīng)到達其驗證階段，則內(nèi)存中必定有其全部的數(shù)據(jù)集。因此，全部的10操作能夠被消退，并且樂觀的方法不要求任何鎖/堵塞，消退了全部數(shù)據(jù)競爭可能導(dǎo)致的延誤?；诖?，Datta等提出了OCC-APR(AdaptivePriority)合同，只要不行調(diào)和的事務(wù)中至少有兩個較高優(yōu)先級的事務(wù)，將重啟正在驗證的事務(wù)。OCC-DA與OCC-DATIOCC-DA(DynamicAdjustmentofserializationorder)山am95］基于前向驗證模式，事務(wù)重啟的數(shù)量通過動態(tài)調(diào)整串行化挨次而削減，這由動態(tài)時間戳安排技術(shù)所支持。沖突檢測在事務(wù)的驗證階段進行，在事務(wù)的讀階段不必要進行時間戳調(diào)整。每個事務(wù)Ti有一個串行化挨次時間戳SOT(Ti),指示了這個事務(wù)相對于其它事務(wù)的串行化挨次，因而提交事務(wù)的串行化挨次可以不同于提交挨次。OCC-DATI(DynamicAdjustmentofserializationorderusingTimestampIntervals)lLIN99)也是基于前向驗證，事務(wù)重啟的數(shù)量通過動態(tài)調(diào)整串行化挨次而削減，但是這由OCC-TI中相像的時間槽方法所支持。但是，不像OCC-TI合同，OCC-DATI中全部的沖突檢測是在事務(wù)的驗證階段進行,把事務(wù)的沖突推遲到事務(wù)接近完成時進行，以便有更多的信息做出選擇，解決沖突。OCC-DATI也不同于OCC-DA,表現(xiàn)在：時間戳間隔被用于實現(xiàn)動態(tài)調(diào)整串行化挨次，而不是OCC-DA合同中的動態(tài)時間戳安排方法。時間戳間隔允許事務(wù)不僅進行前向調(diào)整也能夠進行后向調(diào)整。試驗結(jié)果表明這個合同中的事務(wù)重啟數(shù)量小于OCC-BC、OCC-Wait或者Wait-50合同，并且支持動態(tài)調(diào)整傳串行化挨次的開銷要小于OCC-DA合同。OCC-DAEO雖然動態(tài)調(diào)整串行化挨次能夠削減實時數(shù)據(jù)庫中的事務(wù)重啟個數(shù),但是依舊存在一些不必要的事務(wù)重啟。王永炎等［IPDPS2004］提出基于動態(tài)調(diào)整執(zhí)行挨次(DynamicAdjustmentsExecutionOrder,DAEO)方法的OCC-DAEO樂觀并發(fā)掌握算法，能夠避開更多不必要的重啟，比已有的樂觀并發(fā)掌握算法性能更好。OCC-DAEO樂觀并發(fā)掌握算法轉(zhuǎn)變了傳統(tǒng)觀念的讀、寫以及提交操作，增加半提交操作。而且從理論上證明白OCC-DAEO在保證明時數(shù)據(jù)庫全都性的前提下，能夠盡量避開了不必要的重啟，降低系統(tǒng)資源的鋪張，從而提高實時數(shù)據(jù)庫的性能。3面對混合事務(wù)的并發(fā)掌握針對具有硬實時事務(wù)與軟實時事務(wù)的混合實時數(shù)據(jù)庫系統(tǒng)，Kam-YiuLam等山口叫提出了一種新的并發(fā)掌握合同RCP(ReducedCeilingProtocol),這個合同是PCP合同〔sha90］與OCCWait-50合同IHAR92］的組合。其中，通過限制軟實時事務(wù)對硬實時事務(wù)造成的堵塞，能夠預(yù)先對硬實時事務(wù)的可調(diào)度性進行分