實時數(shù)據(jù)庫事物

3.1.1定時性實時事務(wù)具有定時限制的特征,定時可以是絕對、相對或周期時間。在實時應(yīng)用中,事務(wù)的定時性來源于兩方面:

一是外部環(huán)境顯式給出的反應(yīng)時間要求,這時它典型地取施加于非周期事務(wù)的截止時間限制的形式(截止期),如若溫度達到1000度,則在5秒內(nèi)加冷卻劑到反應(yīng)堆;二是由于系統(tǒng)中的數(shù)據(jù)隨時間變化而轉(zhuǎn)嫁來的

(即由數(shù)據(jù)的時間一致性引起的),此時它往往取周期或定期性限制的形式,如每5秒取樣一次、7:00啟動機器人等。三、實時事務(wù)

3.1實時事務(wù)的特征實時事務(wù)的定時限制有多種,其中最重要的有:(1)截止時間:實時事務(wù)完成的最后期限。它可以有硬、軟、固之分(見圖1)。硬實時事務(wù):具有硬截止時間的事務(wù),必須在其截止時間以前完成,否則將帶來災(zāi)難性的后果,故到達其截止時間還不能完成的硬實時事務(wù)必須夭折。軟實時事務(wù):具有軟截止時間的事務(wù),應(yīng)該在其截止期完成,但超過其截止時間也還有一定意義(盡管不斷下降),故軟實時事務(wù)到達其截止時間后不必立即夭折它。固實時事務(wù):一旦事務(wù)到達截止期,則對系統(tǒng)失去意義,其價值為零。實際上,它是軟實時事務(wù)的一種特例。

(2)到達時間:事務(wù)在系統(tǒng)中生成的時間?？深A(yù)報的到達時間可顯式地給出或者作為一個導(dǎo)出函數(shù),

例如：周期事務(wù)的到達時間是可預(yù)報的。不可預(yù)報的到達時間是指當相應(yīng)事務(wù)到達系統(tǒng)時才能知道,例如：非周期事務(wù)的到達時間就是不可預(yù)報的。(3)期望執(zhí)行時間:估算在最壞情況的執(zhí)行時間。

由于各種不可預(yù)報性因素,它很難做到準確,估算的最壞情況執(zhí)行時間可能與實際情況相差很大。

然而,為了合理地得到事務(wù)的截止時間及適當?shù)卣{(diào)度以使其滿足,又必須事先較準確地估算其執(zhí)行時間。實時事務(wù)的定時限制因此,在實時數(shù)據(jù)庫中,定時性包括以下兩方面的含義:(1)定時限制。事務(wù)的執(zhí)行具有顯式的時限,如期限、截止時間等。因為控制系統(tǒng)要隨時緊緊地跟蹤被控系統(tǒng),它要求RTDB（實時數(shù)據(jù)庫）必須有時間處理機構(gòu)。(2)定時正確性。事務(wù)能按合適的時間要求正確執(zhí)行。由于要求數(shù)據(jù)對于控制系統(tǒng)的各種決策活動隨時有效,所以需要權(quán)衡定時限制與數(shù)據(jù)一致性等多方面因素,提供合適的事務(wù)調(diào)度與并發(fā)控制算法。定時性含義實時數(shù)據(jù)庫事務(wù)之間存在著各種關(guān)系,包括結(jié)構(gòu)關(guān)系、數(shù)據(jù)與通信關(guān)系、時間關(guān)系等,這些關(guān)系帶來了事務(wù)間的各種相關(guān)性。
（1）結(jié)構(gòu)相關(guān)結(jié)構(gòu)相關(guān)來自于復(fù)雜事務(wù)模型的結(jié)構(gòu)特征,用來建模復(fù)雜事務(wù)內(nèi)部并發(fā)事務(wù)行為的一種約束。不同的復(fù)雜事務(wù)模型有不同的結(jié)構(gòu)相關(guān)性,但它們可以通過事務(wù)間的“執(zhí)行依賴性”來定義,實時嵌套事務(wù)中基本的事務(wù)依賴有:(1)子事務(wù)對父事務(wù)的開始依賴(BD):子事務(wù)開始前父事務(wù)已經(jīng)開始;(2)父事務(wù)對子事務(wù)的提交依賴(CD):父事務(wù)提交前子事務(wù)已經(jīng)結(jié)束(提交或夭折);(3)子事務(wù)對父事務(wù)的夭折依賴(AD):父事務(wù)夭折則子事務(wù)一定夭折。3.1.2相關(guān)性（2）數(shù)據(jù)相關(guān)數(shù)據(jù)相關(guān)就是不同事務(wù)間的共享數(shù)據(jù)聯(lián)系。除了傳統(tǒng)意義下的“共享”概念,數(shù)據(jù)相關(guān)還包括如嵌套事務(wù)模型中的數(shù)據(jù)繼承、通信事務(wù)模型的數(shù)據(jù)通信、合作模型的數(shù)據(jù)交換、分裂與合并模型的數(shù)據(jù)“委托”。每一事務(wù)都有一個與之關(guān)聯(lián)(或它所使用)的數(shù)據(jù)集,兩個事務(wù)間的數(shù)據(jù)相關(guān)性就表示它們的數(shù)據(jù)集的重疊度。（3）
行為相關(guān)事務(wù)間的行為相關(guān)性是由事務(wù)的數(shù)據(jù)相關(guān)性及在共享數(shù)據(jù)對象上的交互作用而引起的。它是由于在同一對象上不同事務(wù)操作間的同步所建立的一種間接相關(guān)性,而不像結(jié)構(gòu)相關(guān)是直接的,通常用事務(wù)的“沖突關(guān)系”來表示。
（4）

時間相關(guān)時間相關(guān)性是實時數(shù)據(jù)庫事務(wù)所特有的,它表明事務(wù)的執(zhí)行順序或緊迫度,通常以“事務(wù)事件”來表示。事務(wù)的表示：開始–BEGIN、提交--COMMIT、夭折–ABORT一般而言,時間相關(guān)性分為兩類:時序相關(guān)和帶時限的時序相關(guān)。前者表明有關(guān)事務(wù)中相應(yīng)事務(wù)事件發(fā)生的時間順序,后者是事務(wù)間帶時限的時序相關(guān)。正確性概念及內(nèi)涵實時事務(wù)與傳統(tǒng)事務(wù)的本質(zhì)區(qū)別就在于其有定時限制,

因此,事務(wù)處理必須同時滿足一致性要求和定時限制。雖然實時事務(wù)的正確性與傳統(tǒng)事務(wù)一樣,也包括數(shù)據(jù)庫狀態(tài)正確性和事務(wù)執(zhí)行正確性兩個方面,但其含義與內(nèi)容有很大的不同。

在實時事務(wù)中,數(shù)據(jù)庫狀態(tài)正確性包含內(nèi)部一致性和時間一致性,事務(wù)執(zhí)行正確性則包含其結(jié)果正確性、行為正確性、結(jié)構(gòu)正確性和時間正確性。正確性的判斷標準傳統(tǒng)數(shù)據(jù)庫中事務(wù)正確性的標準是事務(wù)的沖突可串行化執(zhí)行。而實時嵌套事務(wù)正確性的內(nèi)容更為豐富,實現(xiàn)的手段也就更為復(fù)雜。

傳統(tǒng)可串行化標準在實時環(huán)境下太嚴格或不適合,限制了系統(tǒng)中事務(wù)執(zhí)行的并發(fā)度,不利于滿足事務(wù)的定時限制;因而,產(chǎn)生了一種新穎的準一致性可串行化并以控制策略。事務(wù)執(zhí)行給系統(tǒng)帶來的不一致被限定在一定的范圍內(nèi),3.2實時事務(wù)的正確性實時事務(wù)調(diào)度是多用戶(或多事務(wù))并發(fā)存取實時數(shù)據(jù)庫的有效支持機制。它主要包含兩個部分:

事務(wù)優(yōu)先級分配和并發(fā)控制。任何一個事務(wù),如果獲得較高的優(yōu)先級,則意味著它同時獲得優(yōu)先執(zhí)行的權(quán)利。3.4.1
實時事務(wù)優(yōu)先級分配實時事務(wù)的調(diào)度和并發(fā)控制都有是基于事務(wù)的優(yōu)先級進行的,因此,如何分配事務(wù)的優(yōu)先級是一個重要的問題。3.3實時事務(wù)調(diào)度常見的事務(wù)優(yōu)先級分配方法有以下幾種:(1)最早放行最優(yōu)先(EarliestReleaseFirst)。

該方法對具有最早放行(Release)時間的事務(wù)分配最高的優(yōu)先級。所謂放行時間就是事務(wù)可以開始執(zhí)行的最早時間,與此相聯(lián)的有事務(wù)到達(Arrive)時間、事務(wù)接納(Admission)時間。如果事務(wù)放行時間等于事務(wù)到達時間,則該方法就是傳統(tǒng)的先來先服務(wù)方法。（按排隊來）

最早放行最優(yōu)先方法的吸引力在于其簡單性;主要不足是沒有利用事務(wù)“截止時間”參數(shù)。其調(diào)度效果是有利于可能并不具有緊迫的截止時間但先行到達的事務(wù),而不利于具有緊迫的截止時間且最新到達的事務(wù)。顯然,這種調(diào)度效果不適合于具有較嚴格的時間約束的實時應(yīng)用領(lǐng)域。(2)截止期最早最優(yōu)先(EarliestDeadlineFirst)。

具有最早“截止時間”事務(wù)分配最高優(yōu)先級。該算法主要優(yōu)點是算法簡單,利于緊迫”截止時間”的事務(wù)。缺點是沒考慮事務(wù)的執(zhí)行時間,可能對已經(jīng)超過截止時間或就要超過截止時間的事務(wù)賦予了最高優(yōu)先級。（馬上到點的先干）(3)空余時間最短最優(yōu)先

(LeastSlackFest)。

對于事務(wù)T,T為當前時間,E、P分別為事務(wù)T的執(zhí)行時間估算和已執(zhí)行時間,d為其截止期。事務(wù)t的空余時間S=d-(T+E-P),即按照推遲事務(wù)T的執(zhí)行而仍然滿足其截止期的可推遲時間量估算,具有最少空余時間的事務(wù)具有最高優(yōu)先級。該方法類似截止期最早最優(yōu)先方法,可能賦予已經(jīng)超過或快要到達截止時間的事務(wù)最高優(yōu)先級;該方法不同于截止期最早最優(yōu)先方法的是,其事務(wù)的優(yōu)先級依賴于該事務(wù)的剩余運行時間(E-P)。（能盡快完成的活先干）(4)價值最高最優(yōu)先(HighestValueFirst),每一事務(wù)都有一價值函數(shù),其值最大者最優(yōu)先。問題是如何合理地構(gòu)造價值函數(shù),一個例子是:V(t)=C(w1(T-Ts)-w2d+w3P-w4S)其中T、d、P、S的意義同上,c、
s分別為事務(wù)T的危急度、開始時間,wi為加權(quán)因子。（重要的活先干）(5)價值密度最大最優(yōu)先(GreatestValueDensityFirst)。在該方法中,事務(wù)完成時的期望價值與實現(xiàn)該價值所需計算量的比最大者優(yōu)先級最高。價值密度函數(shù)為:VD=V(T+c)/c=V(T+E-P)/(E-P)顯然,對于期望價值一樣的事務(wù),該方法偏向較短者,因為它每單位消耗時間所獲得的價值更大。與上面的HVF方法一樣,此處也有如何設(shè)計價值函數(shù)的問題。（綜合著來）在并發(fā)控制中,可串行化是最流行的標準。但是,在RTDB就應(yīng)用中,有時需要犧牲可串行化以改進性能;因為在實時應(yīng)用中,數(shù)據(jù)和事務(wù)都具有時間限制。

一種新穎的準一致性可串行化并以控制策略可用來實現(xiàn)RTDB中的并發(fā)控制:即將事務(wù)的不一致性限制在一定的范圍之內(nèi)。在具體實現(xiàn)上,有多種方法和技術(shù),這里就不細討論了。

針對具體的并發(fā)控制方法,采用有效的優(yōu)先級分配策略;事務(wù)分配了優(yōu)先級之后,系統(tǒng)按照優(yōu)先級進行調(diào)度。在多道程序運行環(huán)境中,由于事務(wù)對資源的競爭,不可避免地出現(xiàn)沖突問題。

它主要有兩種:優(yōu)先級顛倒問題和死鎖問題。3.3.2實時事務(wù)并發(fā)控制

優(yōu)先級顛倒設(shè)有一個鎖請求事務(wù)Tr和一個鎖持有事務(wù)Th。如果Tr的優(yōu)先級比Th的優(yōu)先級高,它必須等到低優(yōu)先級的Th完成后才能被調(diào)度執(zhí)行,這種現(xiàn)象就稱為優(yōu)先級倒置。簡述之,即優(yōu)先級高的事務(wù)等待優(yōu)先級低的事務(wù)。這對實現(xiàn)事務(wù)的定時限制是不利的。為此,提出了以下幾種改進方案:(1)優(yōu)先級繼承優(yōu)先級繼承策略的基本思想是:

當發(fā)生優(yōu)先級顛倒時,將占有者Th的優(yōu)先級提高到與Tr的一樣(即繼承Tr的優(yōu)先級),Th繼續(xù)執(zhí)行直到結(jié)束(提交或夭折)。（低的提高，干完活再說）

在Th因某種原因(如成為死鎖的犧牲者)而重啟動時,它恢復(fù)原來的優(yōu)先級。讓Th繼承Tr優(yōu)先級是為了讓它盡快完成,因為Th的進展也意味著Tr的進展。這種策略稱為優(yōu)先繼承。Tr優(yōu)先級高，Th優(yōu)先級低(2)高優(yōu)先級夭折高