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

張超欽，馬江濤

ZHANG Chao-qin 1, MA Jiang-tao 2

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

0 引言

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

1 補償任務(wù)的調(diào)度時機

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

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

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

1.1 立即補償

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

圖1 立即補償?shù)膶崟r事務(wù)調(diào)度

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

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

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

圖2 事務(wù)內(nèi)補償?shù)膶崟r事務(wù)調(diào)度

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

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

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

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

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

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

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

圖3 事務(wù)外補償?shù)膶崟r事務(wù)調(diào)度

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真與結(jié)論

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

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

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

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

圖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.