基于替代補償的實時事務調度算法研究

張超欽，馬江濤

ZHANG Chao-qin 1, MA Jiang-tao 2

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

0 引言

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

1 補償任務的調度時機

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

替代失敗后，如果該替代是可補償的，則系統會執行相應的補償任務，因此，下面情況之一發生時意味著事務完成了執行：主任務(替代)成功完成，該事務成功提交；或主任務(所有替代)不成功但其補償任務完成，該事務安全地結束。

根據執行補償的時機，補償行為分為立即補償和延遲補償，而延遲補償又可以分為事務內補償和事務外補償。

1.1 立即補償

立即補償指在替代失敗后立即調度補償任務，在消除了該替代的影響后再執行其它替代，立即補償使用于某些必須立即消除影響的場合。如圖1.1給出了立即補償的實時事務調度方式。

圖1 立即補償的實時事務調度

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

1.2 延遲補償——事務內補償

事務內補償指在某替代失敗后暫時不執行補償，在該事務提交前補償。為了說明這個問題，我們將“End”操作提煉出來，事務在結束運行時，有一個“End”操作，在“End”之后才提交。事務內補償意味著某替代失敗后繼續執行其它替代，一直到該事務成功或失敗時才一次性執行所有補償任務[3]。如圖2給出了事務內補償的調度方式。

圖2 事務內補償的實時事務調度

1.3 延遲補償——事務外補償

事務外補償指在該事務提交或夭折后執行所有的補償，執行補償時對應的事務是成功的。這種補償似乎與前面所說的補償含義有矛盾，前面的討論指出，事務要么安全結束(補償)，要么成功提交，不可能存在提交后還需要補償。問題的關鍵在于實時事務的多替代，實時事務T的一個替代成功執行，則T可提交，但是在此替代前可能有其它替代已經執行但失敗，這些失敗的替代是需要補償的。為了保證事務的截止期，優先提交已成功完成的事務，提交后再執行該事務失敗替代對應的補償任務。也可以在處理夭折后再進行補償[4]。如圖3給出了事務外補償的調度方式。

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

1）事務提交后立即補償。事務提交處理完畢立即對該事務所有失敗且可補償的替代進行補償。

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

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

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

圖3 事務外補償的實時事務調度

2 支持替代/補償的實時事務調度策略

類似于主任務，補償任務的調度基于優先級，補償任務優先級分派策略有以下幾種：

1）優先級繼承策略。補償任務繼承主任務的優先級。

2）最早觸發最優先。將最高優先級指派給具有最早觸發時間的補償任務。

3）截止期最早最優先。具有最早截止期者優先級最高。

4）價值最高者最優先。優先調度規避價值高的補償任務。

調度支持替代/補償的實時事務時需遵循以下兩個原則：

1）補償任務優先原則。系統優先執行補償任務，只有當所有補償任務都完成時才執行主任務。

2）不可搶占原則。補償任務在執行過程中不可被搶占。

在實現調度時，系統將主任務和補償任務分別放置在不同的隊列中，只有補償任務隊列為空時才調度主任務隊列中的成員運行。系統維護的主要隊列有：

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

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

3）主任務就緒隊列MRQ。由就緒的主任務組成。

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

當CRQ中有補償任務結束時，釋放相關的鎖，CWQ中解除阻礙的成員進入CRQ，只有補償任務隊列CRQ和CWQ為空時才調度主任務執行[6]。調度時機不同其調度算法有些許區別。

3 仿真與結論

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

本實驗按照立即補償的調度算法, 事務內補償的調度算法, 事務外補償的調度算法來設計事務子系統的實時調度，就調度的事務進行對比， 依次完成插入100、1000、10000、100000條記錄的事務。使用此3種算法做比較，結果如圖4所示。

從圖4可以看出：立即補償的調度算法, 事務內補償的調度算法, 事務外補償的調度算法的性能依次提高。延遲調度算法要比立即補償性能稍高。

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

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