基于替代補(bǔ)償?shù)膶?shí)時(shí)事務(wù)調(diào)度算法研究

張超欽，馬江濤

ZHANG Chao-qin 1, MA Jiang-tao 2

（1. 鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)通信與工程學(xué)院，鄭州 450002；2. 鄭州輕工業(yè)學(xué)院 國(guó)際教育學(xué)院，鄭州 450002）

0 引言

根據(jù)嵌入式實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)及其事務(wù)特點(diǎn)，以及替代的實(shí)時(shí)事務(wù)模型的特性和可調(diào)度性特征來研究它的調(diào)度算法。一方面，替代的資源需求集是事務(wù)資源需求集的子集，系統(tǒng)只需滿足子集就能執(zhí)行該事務(wù)；另一方面，即使某個(gè)替代失敗，還可能調(diào)度其它替代而不是立即夭折該事務(wù)，提高了事務(wù)的成功率。但是，還有一個(gè)問題不容忽視：在嵌入式實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)中，有些實(shí)時(shí)事務(wù)對(duì)外部環(huán)境作出即時(shí)反應(yīng)，在它提交之前就有可能啟動(dòng)各種外部活動(dòng)，對(duì)外部環(huán)境產(chǎn)生了影響，當(dāng)該事務(wù)夭折時(shí)，無法通過傳統(tǒng)意義下的“還原”（undo）來消除它所產(chǎn)生的影響，這就需要由“補(bǔ)償”事務(wù)來完成這個(gè)任務(wù)[1]。

1 補(bǔ)償任務(wù)的調(diào)度時(shí)機(jī)

替代是實(shí)時(shí)調(diào)度和并發(fā)控制的基本單位，使實(shí)時(shí)事務(wù)調(diào)度具有二重性，分為內(nèi)部調(diào)度和外部調(diào)度。當(dāng)內(nèi)部調(diào)度的結(jié)果為空集時(shí)，該實(shí)時(shí)事務(wù)不可調(diào)度；當(dāng)實(shí)時(shí)事務(wù)執(zhí)行失敗時(shí)，不能立即夭折，必須重新轉(zhuǎn)入內(nèi)部調(diào)度，直到當(dāng)下列情況之一時(shí)才停止調(diào)度活動(dòng)：事務(wù)截止期到；由特殊操作強(qiáng)制停止；該事務(wù)的所有功能替代集經(jīng)內(nèi)部調(diào)度后可調(diào)度集均為空；有一個(gè)功能替代集成功執(zhí)行而提交處理[2]。

替代失敗后，如果該替代是可補(bǔ)償?shù)?，則系統(tǒng)會(huì)執(zhí)行相應(yīng)的補(bǔ)償任務(wù)，因此，下面情況之一發(fā)生時(shí)意味著事務(wù)完成了執(zhí)行：主任務(wù)(替代)成功完成，該事務(wù)成功提交；或主任務(wù)(所有替代)不成功但其補(bǔ)償任務(wù)完成，該事務(wù)安全地結(jié)束。

根據(jù)執(zhí)行補(bǔ)償?shù)臅r(shí)機(jī)，補(bǔ)償行為分為立即補(bǔ)償和延遲補(bǔ)償，而延遲補(bǔ)償又可以分為事務(wù)內(nèi)補(bǔ)償和事務(wù)外補(bǔ)償。

1.1 立即補(bǔ)償

立即補(bǔ)償指在替代失敗后立即調(diào)度補(bǔ)償任務(wù)，在消除了該替代的影響后再執(zhí)行其它替代，立即補(bǔ)償使用于某些必須立即消除影響的場(chǎng)合。如圖1.1給出了立即補(bǔ)償?shù)膶?shí)時(shí)事務(wù)調(diào)度方式。

圖1 立即補(bǔ)償?shù)膶?shí)時(shí)事務(wù)調(diào)度

延遲補(bǔ)償指某替代失敗后，直接執(zhí)行其他替代，在合適的時(shí)機(jī)執(zhí)行補(bǔ)償，這樣有利于將CPU優(yōu)先分配給替代，盡快執(zhí)行替代，提高事務(wù)成功率。延遲補(bǔ)償又可分為事務(wù)內(nèi)補(bǔ)償和事務(wù)外補(bǔ)償兩種方式。

1.2 延遲補(bǔ)償——事務(wù)內(nèi)補(bǔ)償

事務(wù)內(nèi)補(bǔ)償指在某替代失敗后暫時(shí)不執(zhí)行補(bǔ)償，在該事務(wù)提交前補(bǔ)償。為了說明這個(gè)問題，我們將“End”操作提煉出來，事務(wù)在結(jié)束運(yùn)行時(shí)，有一個(gè)“End”操作，在“End”之后才提交。事務(wù)內(nèi)補(bǔ)償意味著某替代失敗后繼續(xù)執(zhí)行其它替代，一直到該事務(wù)成功或失敗時(shí)才一次性執(zhí)行所有補(bǔ)償任務(wù)[3]。如圖2給出了事務(wù)內(nèi)補(bǔ)償?shù)恼{(diào)度方式。

圖2 事務(wù)內(nèi)補(bǔ)償?shù)膶?shí)時(shí)事務(wù)調(diào)度

1.3 延遲補(bǔ)償——事務(wù)外補(bǔ)償

事務(wù)外補(bǔ)償指在該事務(wù)提交或夭折后執(zhí)行所有的補(bǔ)償，執(zhí)行補(bǔ)償時(shí)對(duì)應(yīng)的事務(wù)是成功的。這種補(bǔ)償似乎與前面所說的補(bǔ)償含義有矛盾，前面的討論指出，事務(wù)要么安全結(jié)束(補(bǔ)償)，要么成功提交，不可能存在提交后還需要補(bǔ)償。問題的關(guān)鍵在于實(shí)時(shí)事務(wù)的多替代，實(shí)時(shí)事務(wù)T的一個(gè)替代成功執(zhí)行，則T可提交，但是在此替代前可能有其它替代已經(jīng)執(zhí)行但失敗，這些失敗的替代是需要補(bǔ)償?shù)摹榱吮ＷC事務(wù)的截止期，優(yōu)先提交已成功完成的事務(wù)，提交后再執(zhí)行該事務(wù)失敗替代對(duì)應(yīng)的補(bǔ)償任務(wù)。也可以在處理夭折后再進(jìn)行補(bǔ)償[4]。如圖3給出了事務(wù)外補(bǔ)償?shù)恼{(diào)度方式。

事務(wù)外補(bǔ)償方法又可以分為以下4種：

1）事務(wù)提交后立即補(bǔ)償。事務(wù)提交處理完畢立即對(duì)該事務(wù)所有失敗且可補(bǔ)償?shù)奶娲M(jìn)行補(bǔ)償。

2）截止期處補(bǔ)償。調(diào)度補(bǔ)償任務(wù)從截止期開始執(zhí)行，事務(wù)在系統(tǒng)中的保留時(shí)間較短，夭折的主任務(wù)浪費(fèi)系統(tǒng)資源(CPU)的機(jī)會(huì)更少。

3）臨界點(diǎn)處補(bǔ)償。調(diào)度補(bǔ)償任務(wù)從臨界點(diǎn)開始執(zhí)行，事務(wù)在系統(tǒng)中保留到超過截止期,有機(jī)會(huì)獲得降低的價(jià)值，雖其事務(wù)價(jià)值由可能小于事務(wù)在截止期之前提交的價(jià)值，但依然大于在截止期處安全結(jié)束時(shí)的價(jià)值。

4）臨界點(diǎn)后補(bǔ)償。調(diào)度補(bǔ)償任務(wù)在臨界點(diǎn)后開始執(zhí)行，事務(wù)T在臨界點(diǎn)后提交，將帶給系統(tǒng)負(fù)的價(jià)值，系統(tǒng)損失的實(shí)際價(jià)值取決于事務(wù)距離截止期多遠(yuǎn)。事務(wù)完成(提交或安全結(jié)束)的時(shí)間部分依賴于相關(guān)補(bǔ)償任務(wù)的調(diào)度[5]。

圖3 事務(wù)外補(bǔ)償?shù)膶?shí)時(shí)事務(wù)調(diào)度

2 支持替代/補(bǔ)償?shù)膶?shí)時(shí)事務(wù)調(diào)度策略

類似于主任務(wù)，補(bǔ)償任務(wù)的調(diào)度基于優(yōu)先級(jí)，補(bǔ)償任務(wù)優(yōu)先級(jí)分派策略有以下幾種：

1）優(yōu)先級(jí)繼承策略。補(bǔ)償任務(wù)繼承主任務(wù)的優(yōu)先級(jí)。

2）最早觸發(fā)最優(yōu)先。將最高優(yōu)先級(jí)指派給具有最早觸發(fā)時(shí)間的補(bǔ)償任務(wù)。

3）截止期最早最優(yōu)先。具有最早截止期者優(yōu)先級(jí)最高。

4）價(jià)值最高者最優(yōu)先。優(yōu)先調(diào)度規(guī)避價(jià)值高的補(bǔ)償任務(wù)。

調(diào)度支持替代/補(bǔ)償?shù)膶?shí)時(shí)事務(wù)時(shí)需遵循以下兩個(gè)原則：

1）補(bǔ)償任務(wù)優(yōu)先原則。系統(tǒng)優(yōu)先執(zhí)行補(bǔ)償任務(wù)，只有當(dāng)所有補(bǔ)償任務(wù)都完成時(shí)才執(zhí)行主任務(wù)。

2）不可搶占原則。補(bǔ)償任務(wù)在執(zhí)行過程中不可被搶占。

在實(shí)現(xiàn)調(diào)度時(shí)，系統(tǒng)將主任務(wù)和補(bǔ)償任務(wù)分別放置在不同的隊(duì)列中，只有補(bǔ)償任務(wù)隊(duì)列為空時(shí)才調(diào)度主任務(wù)隊(duì)列中的成員運(yùn)行。系統(tǒng)維護(hù)的主要隊(duì)列有：

1）補(bǔ)償任務(wù)就緒隊(duì)列CRQ。由就緒的補(bǔ)償任務(wù)組成，它們被失敗的替代觸發(fā)。

2）補(bǔ)償任務(wù)等待隊(duì)列CWQ。由與CRQ沖突的補(bǔ)償任務(wù)組成，它們被失敗的替代觸發(fā)。

3）主任務(wù)就緒隊(duì)列MRQ。由就緒的主任務(wù)組成。

4）主任務(wù)等待隊(duì)列MWQ。由與MRQ中成員沖突的主任務(wù)組成。

當(dāng)CRQ中有補(bǔ)償任務(wù)結(jié)束時(shí)，釋放相關(guān)的鎖，CWQ中解除阻礙的成員進(jìn)入CRQ，只有補(bǔ)償任務(wù)隊(duì)列CRQ和CWQ為空時(shí)才調(diào)度主任務(wù)執(zhí)行[6]。調(diào)度時(shí)機(jī)不同其調(diào)度算法有些許區(qū)別。

3 仿真與結(jié)論

本文以開源嵌入式實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)——Berkeley DB為基礎(chǔ)，對(duì)它的事務(wù)子系統(tǒng)模塊進(jìn)行了模擬，采用本文的算法予以實(shí)現(xiàn)，并進(jìn)行了對(duì)比分析。Berkeley DB由五個(gè)主要的子系統(tǒng)構(gòu)成.包括： 存取管理子系統(tǒng)、內(nèi)存池管理子系統(tǒng)、事務(wù)子系統(tǒng)、鎖子系統(tǒng)以及日志子系統(tǒng)。其中存取管理子系統(tǒng)作為Berkeley DB數(shù)據(jù)庫(kù)進(jìn)程包內(nèi)部核心組件，而其他子系統(tǒng)都存在于Berkeley DB數(shù)據(jù)庫(kù)進(jìn)程包的外部。每個(gè)子系統(tǒng)支持不同的應(yīng)用級(jí)別。事務(wù)（Transaction）子系統(tǒng)為Berkeley DB提供事務(wù)管理功能。它允許把一組對(duì)數(shù)據(jù)庫(kù)的修改看作一個(gè)原子單位，這組操作要么全做，要么全不做。在默認(rèn)的情況下，系統(tǒng)將提供嚴(yán)格的ACID事務(wù)屬性，但是應(yīng)用程序可以選擇不使用系統(tǒng)所作的隔離保證。該子系統(tǒng)使用兩段鎖技術(shù)和先寫日志策略來保證數(shù)據(jù)庫(kù)數(shù)據(jù)的正確性和一致性。它也可以被應(yīng)用程序單獨(dú)使用來對(duì)其自身的數(shù)據(jù)更新進(jìn)行事務(wù)保護(hù)。事務(wù)子系統(tǒng)適用于需要事務(wù)保證數(shù)據(jù)的修改的應(yīng)用[7]。

本實(shí)驗(yàn)按照立即補(bǔ)償?shù)恼{(diào)度算法, 事務(wù)內(nèi)補(bǔ)償?shù)恼{(diào)度算法, 事務(wù)外補(bǔ)償?shù)恼{(diào)度算法來設(shè)計(jì)事務(wù)子系統(tǒng)的實(shí)時(shí)調(diào)度，就調(diào)度的事務(wù)進(jìn)行對(duì)比， 依次完成插入100、1000、10000、100000條記錄的事務(wù)。使用此3種算法做比較，結(jié)果如圖4所示。

從圖4可以看出：立即補(bǔ)償?shù)恼{(diào)度算法, 事務(wù)內(nèi)補(bǔ)償?shù)恼{(diào)度算法, 事務(wù)外補(bǔ)償?shù)恼{(diào)度算法的性能依次提高。延遲調(diào)度算法要比立即補(bǔ)償性能稍高。

結(jié)果表明：1）實(shí)時(shí)數(shù)據(jù)庫(kù)事務(wù)子系統(tǒng)中，某些事務(wù)故障時(shí)，即使某個(gè)替代失敗，還可能調(diào)度其它替代而不是立即夭折該事務(wù)，立即補(bǔ)償和延遲補(bǔ)償是可行的，提高了事務(wù)的成功率。2）在事務(wù)調(diào)度中延遲調(diào)度算法要比立即補(bǔ)償性能稍高。3）設(shè)計(jì)實(shí)時(shí)數(shù)據(jù)庫(kù)事務(wù)子系統(tǒng)的關(guān)鍵是替代、補(bǔ)償?shù)膶?shí)時(shí)事務(wù)調(diào)度，系統(tǒng)并行處理能力，事務(wù)的實(shí)時(shí)性要求等。隨著更多的實(shí)時(shí)應(yīng)用需要實(shí)時(shí)數(shù)據(jù)庫(kù)的高可靠性及反應(yīng)時(shí)間可預(yù)測(cè)性，將另文探討這方面的工作。

圖4 算法性能比較

[1]Young-Kuk Kim、Sang H.Son,Supporting Predictability for Real-Time Database Systems[J],Proceedings of the 2nd IEEE Real-Time Technology and Applications Symposium,1996：122-133.

[2]SKYTJ、JENSEN C.S.,A foundation for vacuuming temporal database[J],Data and Knowledge Engineering,2003.44(1)：1-29.

[3]TANSEL A、CLIFFORD J、GADIA J S. et al,Temporald atabases：theory,design,and implementation.Database Systems and Applications eries[M],Benjamin/Cummings,1993.

[4]Young-Kuk Kim and Sang H.Son,An approsh toward predi catable Real-time transaction Processing,In Proceedings of the 5th Euromicro Workshop on Real-time Systems,Oulu,Finland,June 1993.

[5]Peter Puschner and Anton Schedl.Computing Maximum Task Execution Times -A Graph-Based Approach.Journal of Real-Time Systems,1997,13(1)：67-91.

[6]Peter Puschner and Anton Schedl.A Tool for the Computation of Worst Case Task Execution Times.In Proc.5th Euromicro Workshop on Real-Time Systems,1993,6：224-229.

[7]Haritsa J R、Carey M J、Linvy M. On bing optimistic about real—time constraints [C],Prnc of the 1990 ACM PODS Symposium,1990,4.