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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(LeastSlackFest)。

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

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

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

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

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

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

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