計算機信息管理論文發(fā)表期刊推薦《中國信息化》雜志由新聞出版總署正式批準、中華人民共和國工業(yè)和信息化部主管主辦的一本國家批準創(chuàng)刊的唯一一份以關(guān)注工業(yè)化與信息化融合，推進信息化進 程為使命的國家級信息化媒體國公開刊物。國際標準刊號：ISSN1672-5158，國內(nèi)統(tǒng)一刊號：CN11-5119/TP。郵發(fā)代號82-898. 《中國信息化》雜志立足經(jīng)濟與社會發(fā)展大背景和信息化發(fā)展趨勢，廣度反映信息化實踐，深度體現(xiàn)信息產(chǎn)業(yè)與信息化相互促進。主要面向和服務于政府信息化推進 部門的決策層，重點領(lǐng)域應用機構(gòu)的領(lǐng)導層，企業(yè)的CIO及管理層，信息化實施部門的主導層，以及關(guān)注信息化的專家、學者等。集思想性、知識性、可讀性為一 體的權(quán)威雜志傳媒。
　　摘要：論文概述了嵌入式實時數(shù)據(jù)庫（ERTDBMS）及事務特點的研究現(xiàn)狀，分析了ERTDBMS事務與分析、代替/補償、基于價值函數(shù)和面向?qū)ο罂蚣艿氖聞漳Ｐ�，探討了ERTDBMS事務調(diào)度策略和并發(fā)控制，闡明了該問題的研究意義。

　　關(guān)鍵詞：嵌入式,實時數(shù)據(jù)庫,模型

　　1引言

　　目前，數(shù)字化產(chǎn)品繼PC之后成為信息處理的又一個主要工具,在這些嵌入式設備中，需要具備成熟的數(shù)據(jù)管理能力，所需的功能非常復雜，以至于文件系統(tǒng)不足以處理和操縱這些數(shù)據(jù)，這就促進了對嵌入式數(shù)據(jù)庫系統(tǒng)的需求。嵌入式數(shù)據(jù)庫系統(tǒng)的設計目的是在最小系統(tǒng)影響下進行數(shù)據(jù)存儲和恢復。由于常常需要對環(huán)境做出實時反應，此概念建立在實時或近似實時的嵌入式計算機中，準確地講更多的需求是嵌入式實時數(shù)據(jù)庫系統(tǒng)[1]。

　　2ERTDBMS事務的特點及研究現(xiàn)狀

　　2.1ERTDBMS事務的特點

　　嵌入式實時數(shù)據(jù)庫系統(tǒng)模型的操作也是以事務的形式出現(xiàn)，系統(tǒng)以事務為單位分配CPU、數(shù)據(jù)等資源，進行優(yōu)先級的分配、調(diào)度處理等。同時，ERTDBMS中的事務與傳統(tǒng)事務又有所不同，其事務可以有定時限制，系統(tǒng)追求的目標是單個事務定時限制的滿足，以使?jié)M足定時限制的事務比率最大，要求采用“識時”機制來處理事務的調(diào)度或并發(fā)控制，而不是傳統(tǒng)的先來先服務方式。

　　ERTDBMS中事務與傳統(tǒng)事務的根本性區(qū)別表現(xiàn)在：

　　（1）事務的正確性不僅在于邏輯結(jié)果的正確性，而且要求在時間上必須在給定的截止期之內(nèi)完成；（2）事務的可預測性；（3）可恢復（補償）性。

　　2.2ERTDBMS及其事務模型的研究現(xiàn)狀

　　目前的嵌入式實時數(shù)據(jù)庫系統(tǒng)可分為兩大類：一類是商用級的嵌入式實時數(shù)據(jù)庫系統(tǒng)（如美國McObject公司提供的eXtremeDB內(nèi)存式實時數(shù)據(jù)庫）；另一類是用戶針對具體的應用對象而自行設計開發(fā)的嵌入式實時數(shù)據(jù)庫系統(tǒng)。

　　Kim建立了一個實時數(shù)據(jù)庫事務模型，而Braoudakis采取不同方法，將事務與一個價值函數(shù)關(guān)聯(lián)，Zhou，Rundensteiner和Shin將面向?qū)ο蟮挠^點結(jié)合到實時數(shù)據(jù)庫系統(tǒng)中，提出了ROMPP，用面向?qū)ο蟮目蚣芴接懥藭r態(tài)和邏輯的一致性和正確性。目前嵌入式實時數(shù)據(jù)庫系統(tǒng)的事務模型以華中科技大學劉云生教授及其博士生夏家莉教授的基于功能替代/補償?shù)膶崟r事務模型最為成熟[3]。

　　基于功能替代的實時事務模型以替代作為并發(fā)控制和調(diào)度的基本單位，可以提高事務的成功率。在支持補償?shù)膶崟r事務模型中，替代提高了事務的成功率，但不能保證事務的絕對成功，當所有替代都失敗或在其截止期前不能成功執(zhí)行替代時，需要采取補償措施，特別是某些不具備替代性的實時事務在失敗時需要補償。

　　3ERTDBMS事務模型及處理的技術(shù)要點

　　3.1ERTDBMS事務預分析

　　ERTDBMS中的實時應用包含了豐富的數(shù)據(jù)、事務語義及復雜結(jié)構(gòu)，具有許多與傳統(tǒng)應用不同的特征，在事務處理時必須考慮到數(shù)據(jù)和資源的沖突、事務間的相互依賴性、新活動（事務）的動態(tài)“產(chǎn)生”以及事務的夭折因素[4]，事務的實際執(zhí)行時間和估算的最壞情況下執(zhí)行時間的誤差很大，所以系統(tǒng)必須要有一定的預測和處理能力，能進行“可調(diào)度性”分析和預測，事先知道一個事務滿足其定時限制特別是截止時間的可能性，是否有“危險”性而采取專門措施，以便保證它正常完成。

　　BRTDBMS事務的預分析至少包含以下四方面的內(nèi)容：

　�。�1）在事務到達系統(tǒng)或在系統(tǒng)生成時對其進行預分析，提取關(guān)于事務的替代集、數(shù)據(jù)集、操作邏輯（類型和順序）、定時性要求、緊迫性與關(guān)鍵性、運行時間估算、可能觸發(fā)的活動/事務等的信息，以及各事務間在結(jié)構(gòu)、行為、數(shù)據(jù)和定時等方面的相關(guān)性信息。

　�。�2）在系統(tǒng)運行時的適當時機，采用一定的算法對當前活躍事務進行相關(guān)性分析，以支持和輔助調(diào)度算法與并發(fā)控制策略的實施。

　　（3）在執(zhí)行調(diào)度與并發(fā)控制前，動態(tài)地進行“可調(diào)度性”預測，確定它們能正常完成的可能性或程度，以便采取相應的措施來盡可能保證其實現(xiàn)。

　�。�4）必要時采取相應措施，如動態(tài)調(diào)整優(yōu)先級與調(diào)度算法、執(zhí)行“功能替代”或“補償”等活動。

　　截止期是ERTDBMS事務的一個重要特性，確定事務的截止期是事務預分析的首要工作。從確定方式來說，主要有賦值截止期、演繹截止期和隱式截止期等。在ERTDBMS中，精確的事務調(diào)度策略涉及事務的截止期和執(zhí)行時間。與截止期一樣，程序的執(zhí)行時間成為事務預分析要解決的又一個重要難題。文獻中提出了一種程序執(zhí)行時間的估算方法，將其分為兩步：一是靜態(tài)地WCET（WorstCaseExecutionTime）估算，說明程序的執(zhí)行在X秒內(nèi)完成，調(diào)度的精確性依賴于此區(qū)間的緊密性；二是利用灰色系統(tǒng)理論，通過分析灰色信息找出規(guī)律，從而預測事務的執(zhí)行事件，得到動態(tài)的時間估算[5]。

　　3.2ERTDBMS的替代/補償事務

　　一個具有時間限制的應用為一個實時事務，它有若干個任務組成，某些任務可以完成實時事務的功能。實時事務具有功能替代的特性，一個實時事務包含有多個任務集，它們是功能等價的，稱為任務替代集。每個任務又包含了一組功能等價的子事務。在實時事務的一個任務替代集中，由每一個任務中的一個成員所組成的集合稱為該事務的一個功能替代集。實時事務有多個功能替代集組成，在每次調(diào)度到該事務時，該實時事務中挑選一個合適的功能替代集，一旦此功能替代集夭折而事務的截止期未到，系統(tǒng)將試圖選取該實時事務的另一個功能替代集繼續(xù)投入調(diào)度，如果能使系統(tǒng)有意識地選取成功率高的功能替代集，就能提高系統(tǒng)的執(zhí)行效率。

　　基于功能替代的實時事務模型（FunctionAlternativeTransactionModel，F(xiàn)ATM）的建立，充分表明一個實時事務實際上具有復雜的三維結(jié)構(gòu)。從而在預分析時采取三個步驟：分解事務得到其所有功能替代集；逐個分析提取與運行有關(guān)的信息和知識；考察調(diào)度性能并排序為調(diào)度提供直接信息。功能替代集的預分析過程如圖1所示。系統(tǒng)調(diào)度時，首先從強調(diào)度樹中選取一個對象，若無強調(diào)度樹，則從弱調(diào)度樹中選取一個對象，在軟實時環(huán)境下，有可能從普通調(diào)度樹中選取一個對象。

　　圖1實時事務功能替代集預分析圖解

　　基于功能替代的ERTDBMS事務模型有利于對事務的預分析，作為調(diào)度的先期調(diào)度，直接關(guān)系到其執(zhí)行成功率，從而節(jié)省系統(tǒng)的運行時間。同時，事務的可替代性使事務的執(zhí)行具有多條路徑，提高了事務的成功率。但是，如果事務的所有替代集都不能（或者時間不允許）成功執(zhí)行，則其依然要夭折。為了避免因此引起的系統(tǒng)災難，有必要對FATM進行擴充，使之支持補償性，即事務有主任務和補償任務組成，當主任務不能成功執(zhí)行時，由補償任務使之安全結(jié)束（當然并非每個事務都是可補償?shù)模��?/p>

　　3.3基于價值函數(shù)的實時事務模型

　　具有功能替代的事務模型具有定時性、功能等價性、同構(gòu)性等特點[6]。用一致的觀點看待系統(tǒng)中的實時和非實時事務，將事務的價值函數(shù)引入事務模型中，使實時事務模型滿足更好的特性。實時事務的價值函數(shù)如圖2所示。

　　圖2實時事務的價值函數(shù)

　　非實時事務可視為實時事務的一種特列（沒有Di的要求），其價值不隨時間的變化而變化，恒為Vi。實時事務的價值函數(shù)分情況討論如下：

　�。�1）t

　�。�2）t>Di時，VTi∈HT，有V(Ti)=-P(P為常數(shù)）；

　　VTi∈FT，有V(Ti)=0；VTi∈ST，有V(Ti)=0(TZi-t)tanɑ。

　　3.4ERTDBMS事務調(diào)度策略與并發(fā)控制

　　在ERTDBMS事務調(diào)度中，主要利用兩方面的因素：事務到達時間和事務截止期。調(diào)度策略中大部分采用優(yōu)先級調(diào)度法，如最早放行最優(yōu)先（EarliestReleaseFirst，ERF）、截止期最早最優(yōu)先（EarliestDeadlineFirst，EDF）、可達截止期最早優(yōu)先（EarliestFeasible-DeadlineFirst，EFDF）、最小松弛時間最優(yōu)先（MinimumSlackFirst，MSF）、價值最高優(yōu)先（Highest-ValueFirst，HVF）等[7]。并由此派生出一些新策略，如自適應最早最終時間（AED）協(xié)議，它是基于EDF分配策略的，把事務分成兩組，根據(jù)預先設定的控制變量，進行關(guān)鍵性值的排序，按照列表中的關(guān)鍵值排序進行調(diào)度。

　　并發(fā)控制是要控制并發(fā)事務之間的相互作用（或者協(xié)調(diào)調(diào)度），使數(shù)據(jù)庫一致性（ERTDBMS中特別是事務的時間一致性）不被破壞。ERTDBMS的并發(fā)控制是在傳統(tǒng)數(shù)據(jù)庫基礎上考慮時間因素，提出有悲觀并發(fā)控制、樂觀并發(fā)控制以及多版本并發(fā)控制協(xié)議等。階段鎖定是最大眾化的悲觀并發(fā)控制協(xié)議，使用此方法，事務在獲得鎖之前禁止訪問數(shù)據(jù)庫目標，事務執(zhí)行由獲得鎖和釋放鎖兩部分組成。包括優(yōu)先級中止、優(yōu)先級繼承和有條件優(yōu)先級繼承等。樂觀并發(fā)控制協(xié)議允許事務無障礙執(zhí)行直到全部操作完成，然后在提交時驗證，如果通過就提交否則重啟。在多版本并發(fā)控制協(xié)議中，每個數(shù)據(jù)由多個版本，讀操作中事務可以讀取沒有被覆蓋的舊版本來保證調(diào)度的可串行性，從而增加并發(fā)度，減少拒絕操作。

　　4結(jié)束語

　　本文主要討論了嵌入式實時數(shù)據(jù)庫的特點和其事務模型及其處理的有關(guān)理論、技術(shù)和實現(xiàn)方法等，包括ERTDBMS的特點、ERTDBMS事務模型的特點和研究現(xiàn)狀、基于替代/補償?shù)氖聞漳Ｐ�、基于價值函數(shù)的事務模型、基于面向?qū)ο蟮氖聞漳Ｐ鸵约癊RTDBMS事務的調(diào)度策略和并發(fā)控制。嵌入式實時數(shù)據(jù)庫系統(tǒng)作為嵌入式實時操作系統(tǒng)的一個用戶進程，其事務執(zhí)行在時間和空間上必然產(chǎn)生重大矛盾，如何解決它們之間的沖突可以從事務模型的改進及其調(diào)度策略和并發(fā)機制上逐步部分地解決。因此，比較深入地研究ERTDBMS的事務模型及其處理成為目前研究熱點，也具有較高的研究價值和現(xiàn)實意義。

　　參考文獻：

　　[1]何新貴，劉云生．特種數(shù)據(jù)庫技術(shù)[M]．北京：科學技術(shù)出版社，2007，203-230.

　　[2]PanYi,LuYan-sheng.Nestedtransactionconcurrencycontrolinparallelreal-timedatabases[J].JofDonghuaUniv,22(2):2005,114.

　　[3]劉去生，丁力．嵌入式實時數(shù)據(jù)庫管理系統(tǒng)的設計[J].計算機應用研究，2006，8：230-231.

　　[4]AbhottRK,Garcir-MolinaH.Schedulingreal-timetransactions:aperformanceevaluation[J].ACMTransonDatabaseSyst,17(3):1992,513.

　　[5]夏家莉．基于替代/補償?shù)膶崟r事務模型[J].計算機工程與應用，2003，39（34）：25-27.

　　[6]夏家莉，劉云生．滿足嵌入式實時數(shù)據(jù)庫系統(tǒng)的可預見能力[J].小型微型計算機系統(tǒng)，2003.24（2）：234-237.

　　[7]Braoudakis,TimelinessViaSpeculationforReal-timeDatabase,InPro.ofIEEEReal-timeSystemSymposium,1994.

---

轉(zhuǎn)載請注明來自：http://www.jinnzone.com/jisuanjixinxiguanlilw/21112.html