實(shí)時(shí)數(shù)據(jù)庫(kù)事務(wù)模型及處理技術(shù)要點(diǎn)探討

1、文章來(lái)源 畢業(yè)論文網(wǎng) 實(shí)時(shí)數(shù)據(jù)庫(kù)事務(wù)模型及處理技術(shù)要點(diǎn)探討文章來(lái)源 畢業(yè)論文網(wǎng) 以下是一篇關(guān)于實(shí)時(shí)數(shù)據(jù)庫(kù)事務(wù)模型及處理技術(shù)要點(diǎn)探討的畢業(yè)論文，歡迎瀏覽！ 摘要：論文概述了嵌入式實(shí)時(shí)數(shù)據(jù)庫(kù)（ertdbms）及事務(wù)特點(diǎn)的研究現(xiàn)狀，分析了ertdbms事務(wù)與分析、代替/補(bǔ)償、基于價(jià)值函數(shù)和面向?qū)ο罂蚣艿氖聞?wù)模型，探討了ertdbms事務(wù)調(diào)度策略和并發(fā)控制，闡明了該問(wèn)題的研究意義。 中圖分類號(hào)：tp393       文獻(xiàn)標(biāo)志碼：a 1 引言     目前，數(shù)字化產(chǎn)品繼pc

2、之后成為信息處理的又一個(gè)主要工具,在這些嵌入式設(shè)備中，需要具備成熟的數(shù)據(jù)管理能力，所需的功能非常復(fù)雜，以至于文件系統(tǒng)不足以處理和操縱這些數(shù)據(jù)，這就促進(jìn)了對(duì)嵌入式數(shù)據(jù)庫(kù)系統(tǒng)的需求。嵌入式數(shù)據(jù)庫(kù)系統(tǒng)的設(shè)計(jì)目的是在最小系統(tǒng)影響下進(jìn)行數(shù)據(jù)存儲(chǔ)和恢復(fù)。由于常常需要對(duì)環(huán)境做出實(shí)時(shí)反應(yīng)，此概念建立在實(shí)時(shí)或近似實(shí)時(shí)的嵌入式計(jì)算機(jī)中，準(zhǔn)確地講更多的需求是嵌入式實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)1。 2 ertdbms事務(wù)的特點(diǎn)及研究現(xiàn)狀 2.1 ertdbms事務(wù)的特點(diǎn)     嵌入式實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)模型的操作也是以事務(wù)的形式出現(xiàn)，系統(tǒng)以事務(wù)為單位分配cpu、數(shù)據(jù)等資源，進(jìn)

3、行優(yōu)先級(jí)的分配、調(diào)度處理等。同時(shí)，ertdbms中的事務(wù)與傳統(tǒng)事務(wù)又有所不同，其事務(wù)可以有定時(shí)限制，系統(tǒng)追求的目標(biāo)是單個(gè)事務(wù)定時(shí)限制的滿足，本文來(lái)自論文之家:,轉(zhuǎn)載請(qǐng)保留此標(biāo)記以使?jié)M足定時(shí)限制的事務(wù)比率最大，要求采用“識(shí)時(shí)”機(jī)制來(lái)處理事務(wù)的調(diào)度或并發(fā)控制，而不是傳統(tǒng)的先來(lái)先服務(wù)方式。     ertdbms中事務(wù)與傳統(tǒng)事務(wù)的根本性區(qū)別表現(xiàn)在： （1）事務(wù)的正確性不僅在于邏輯結(jié)果的正確性，而且要求在時(shí)間上必須在給定的截止期之內(nèi)完成；（2）事務(wù)的可預(yù)測(cè)性；（3）可恢復(fù)（補(bǔ)償）性。 2.2 ertdbms及其事務(wù)模型

4、的研究現(xiàn)狀     目前的嵌入式實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)可分為兩大類：一類是商用級(jí)的嵌入式實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)（如美國(guó)mcobject公司提供的extremedb內(nèi)存式實(shí)時(shí)數(shù)據(jù)庫(kù)）；另一類是用戶針對(duì)具體的應(yīng)用對(duì)象而自行設(shè)計(jì)開(kāi)發(fā)的嵌入式實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)。     kim建立了一個(gè)實(shí)時(shí)數(shù)據(jù)庫(kù)事務(wù)模型，而braoudakis采取不同方法，將事務(wù)與一個(gè)價(jià)值函數(shù)關(guān)聯(lián)，zhou，rundensteiner和shin將面向?qū)ο蟮挠^點(diǎn)結(jié)合到實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)中，提出了rompp，用面向?qū)ο蟮目蚣芴接懥藭r(shí)態(tài)和邏輯的一致性和正確性。目前嵌入式實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)

5、的事務(wù)模型以華中科技大學(xué)劉云生教授及其博士生夏家莉教授的基于功能替代/補(bǔ)償?shù)膶?shí)時(shí)事務(wù)模型最為成熟3。     基于功能替代的實(shí)時(shí)事務(wù)模型以替代作為并發(fā)控制和調(diào)度的基本單位，可以提高事務(wù)的成功率。在支持補(bǔ)償?shù)膶?shí)時(shí)事務(wù)模型中，替代提高了事務(wù)的成功率，但不能保證事務(wù)的絕對(duì)成功，當(dāng)所有替代都失敗或在其截止期前不能成功執(zhí)行替代時(shí)，需要采取補(bǔ)償措施，特別是某些不具備替代性的實(shí)時(shí)事務(wù)在失敗時(shí)需要補(bǔ)償。 3 ertdbms事務(wù)模型及處理的技術(shù)要點(diǎn) 3.1 ertdbms事務(wù)預(yù)分析     ertdbms中的實(shí)時(shí)

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

7、1）在事務(wù)到達(dá)系統(tǒng)或在系統(tǒng)生成時(shí)對(duì)其進(jìn)行預(yù)分析，提取關(guān)于事務(wù)的替代集、數(shù)據(jù)集、操作邏輯（類型和順序）、定時(shí)性要求、緊迫性與關(guān)鍵性、運(yùn)行時(shí)間估算、可能觸發(fā)的活動(dòng)/事務(wù)等的信息，以及各事務(wù)間在結(jié)構(gòu)、行為、數(shù)據(jù)和定時(shí)等方面的相關(guān)性信息。 （2）在系統(tǒng)運(yùn)行時(shí)的適當(dāng)時(shí)機(jī)，采用一定的算法對(duì)當(dāng)前活躍事務(wù)進(jìn)行相關(guān)性分析，以支持和輔助調(diào)度算法與并發(fā)控制策略的實(shí)施。 （3）在執(zhí)行調(diào)度與并發(fā)控制前，動(dòng)態(tài)地進(jìn)行“可調(diào)度性”預(yù)測(cè)，確定它們能正常完成的可能性或程度，以便采取相應(yīng)的措施來(lái)盡可能保證其實(shí)現(xiàn)。 （4）必要時(shí)采取相應(yīng)措施，如動(dòng)態(tài)調(diào)整優(yōu)先級(jí)與調(diào)度算法、執(zhí)行&ld

8、quo;功能替代”或“補(bǔ)償”等活動(dòng)。     截止期是ertdbms事務(wù)的一個(gè)重要特性，確定事務(wù)的截止期是事務(wù)預(yù)分析的首要工作。從確定方式來(lái)說(shuō)，主要有賦值截止期、演繹截止期和隱式截止期等。在ertdbms中，精確的事務(wù)調(diào)度策略涉及事務(wù)的截止期和執(zhí)行時(shí)間。與截止期一樣，程序的執(zhí)行時(shí)間成為事務(wù)預(yù)分析要解決的又一個(gè)重要難題。文獻(xiàn)中提出了一種程序執(zhí)行時(shí)間的估算方法，將其分為兩步：一是靜態(tài)地wcet （worst case execution time）估算，說(shuō)明程序的執(zhí)行在x秒內(nèi)完成，調(diào)度的精確性依賴于此區(qū)間的緊密性；二是利用

9、灰色系統(tǒng)理論，通過(guò)分析灰色信息找出規(guī)律，從而預(yù)測(cè)事務(wù)的執(zhí)行事件，得到動(dòng)態(tài)的時(shí)間估算5。 3.2 ertdbms的替代/補(bǔ)償事務(wù)     一個(gè)具有時(shí)間限制的應(yīng)用為一個(gè)實(shí)時(shí)事務(wù)，它有若干個(gè)任務(wù)組成，某些任務(wù)可以完成實(shí)時(shí)事務(wù)的功能。實(shí)時(shí)事務(wù)具有功能替代的特性，一個(gè)實(shí)時(shí)事務(wù)包含有多個(gè)任務(wù)集，它們是功能等價(jià)的，稱為任務(wù)替代集。每個(gè)任務(wù)又包含了一組功能等價(jià)的子事務(wù)。在實(shí)時(shí)事務(wù)的一個(gè)任務(wù)替代集中，由每一個(gè)任務(wù)中的一個(gè)成員所組成的集合稱為該事務(wù)的一個(gè)功能替代集。實(shí)時(shí)事務(wù)有多個(gè)功能替代集組成，在每次調(diào)度到該事務(wù)時(shí)，該實(shí)時(shí)事務(wù)中挑選一個(gè)合適的功能替代集，一旦此功能

10、替代集夭折而事務(wù)的截止期未到，系統(tǒng)將試圖選取該實(shí)時(shí)事務(wù)的另一個(gè)功能替代集繼續(xù)投入調(diào)度，如果能使系統(tǒng)有意識(shí)地選取成功率高的功能替代集，就能提高系統(tǒng)的執(zhí)行效率。     基于功能替代的實(shí)時(shí)事務(wù)模型（function alternative transaction model，fatm）的建立，充分表明一個(gè)實(shí)時(shí)事務(wù)實(shí)際上具有復(fù)雜的三維結(jié)構(gòu)。從而在預(yù)分析時(shí)采取三個(gè)步驟：分解事務(wù)得到其所有功能替代集；逐個(gè)分析提取與運(yùn)行有關(guān)的信息和知識(shí)；考察調(diào)度性能并排序?yàn)檎{(diào)度提供直接信息。功能替代集的預(yù)分析過(guò)程如圖1所示。系統(tǒng)調(diào)度時(shí)，首先從強(qiáng)調(diào)度樹(shù)中選取一個(gè)對(duì)象，若無(wú)強(qiáng)調(diào)度樹(shù)，則

11、從弱調(diào)度樹(shù)中選取一個(gè)對(duì)象，在軟實(shí)時(shí)環(huán)境下，有可能從普通調(diào)度樹(shù)中選取一個(gè)對(duì)象。  圖1 實(shí)時(shí)事務(wù)功能替代集預(yù)分析圖解     基于功能替代的ertdbms事務(wù)模型有利于對(duì)事務(wù)的預(yù)分析，作為調(diào)度的先期調(diào)度，直接關(guān)系到其執(zhí)行成功率，從而節(jié)省系統(tǒng)的運(yùn)行時(shí)間。同時(shí)，事務(wù)的可替代性使事務(wù)的執(zhí)行具有多條路徑，提高了事務(wù)的成功率。但是，如果事務(wù)的所有替代集都不能（或者時(shí)間不允許）成功執(zhí)行，則其依然要夭折。為了避免因此引起的系統(tǒng)災(zāi)難，有必要對(duì)fatm進(jìn)行擴(kuò)充，使之支持補(bǔ)償性，即事務(wù)有主任務(wù)和補(bǔ)償任務(wù)組成，當(dāng)主任務(wù)不能成功執(zhí)行時(shí)，由補(bǔ)償任務(wù)使之安全結(jié)束（

12、當(dāng)然并非每個(gè)事務(wù)都是可補(bǔ)償?shù)模?nbsp;3.3 基于價(jià)值函數(shù)的實(shí)時(shí)事務(wù)模型     具有功能替代的事務(wù)模型具有定時(shí)性、功能等價(jià)性、同構(gòu)性等特點(diǎn)6。用一致的觀點(diǎn)看待系統(tǒng)中的實(shí)時(shí)和非實(shí)時(shí)事務(wù)，將事務(wù)的價(jià)值函數(shù)引入事務(wù)模型中，使實(shí)時(shí)事務(wù)模型滿足更好的特性。實(shí)時(shí)事務(wù)的價(jià)值函數(shù)如圖2所示。  圖2 實(shí)時(shí)事務(wù)的價(jià)值函數(shù)     非實(shí)時(shí)事務(wù)可視為實(shí)時(shí)事務(wù)的一種特列（沒(méi)有di的要求），其價(jià)值不隨時(shí)間的變化而變化，恒為vi。實(shí)時(shí)事務(wù)的價(jià)值函數(shù)分情況討論如下： （1）t<di 時(shí)，vti&isi

13、n;rt，有v(ti)=vi（vi為常數(shù)）； （2）t>di時(shí)，vti∈ht，有v(ti)=-p(p為常數(shù)）； vti∈ft，有v(ti)=0；vti∈st ，有v(ti)=0(tzi-t)tan。 3.4 ertdbms事務(wù)調(diào)度策略與并發(fā)控制     在ertdbms事務(wù)調(diào)度中，主要利用兩方面的因素：事務(wù)到達(dá)時(shí)間和事務(wù)截止期。調(diào)度策略中大部分采用優(yōu)先級(jí)調(diào)度法，如最早放行最優(yōu)先（earliest release first，erf）、截止期最早最優(yōu)先（earliest deadline f

14、irst，edf）、可達(dá)截止期最早優(yōu)先（earliest feasible-deadline first，efdf）、最小松弛時(shí)間最優(yōu)先（minimum slack first，msf）、價(jià)值最高優(yōu)先（highest-value first，hvf）等7。并由此派生出一些新策略，如自適應(yīng)最早最終時(shí)間（aed）協(xié)議，它是基于edf分配策略的，把事務(wù)分成兩組，根據(jù)預(yù)先設(shè)定的控制變量，進(jìn)行關(guān)鍵性值的排序，按照列表中的關(guān)鍵值排序進(jìn)行調(diào)度。     并發(fā)控制是要控制并發(fā)事務(wù)之間的相互作用（或者協(xié)調(diào)調(diào)度），使數(shù)據(jù)庫(kù)一致性（ertdbms中特別是事務(wù)的時(shí)間一致性）不被

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

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

17、數(shù)據(jù)庫(kù)技術(shù)m 北京：科學(xué)技術(shù)出版社，2007，203-230. 2 pan yi ,lu yan-sheng. nested transaction concurrency control in parallel real-time databases j . j of donghua univ, 22(2) :2005, 114. 3劉去生，丁力嵌入式實(shí)時(shí)數(shù)據(jù)庫(kù)管理系統(tǒng)的設(shè)計(jì)j.計(jì)算機(jī)應(yīng)用研究，2006，8：230-231. 4 abhott r k, garcir-molina h. scheduling real-time transactions :a performance evaluation j. acm trans on