實時數據庫系統服務質量管理研究

郭里城

?

實時數據庫系統服務質量管理研究

郭里城

（漳州職業技術學院 計算機工程系，福建 漳州 363000）

以實時數據庫事務調度為典型應用背景，研究和分析了不精確性計算方法，給出了一個基于不精確性計算的事務模型，并基于該事務模型提出了一種基于反饋控制的實時事務調度體系結構以及建模方法，為最終提高在超載環境下實時數據庫系統的服務質量提供了有效的解決方案。

實時數據庫；服務質量；事務調度；反饋控制；不精確計算

引言

隨著實時數據庫系統在電子商務、工廠生產過程控制和證券交易等軟實時應用領域的推廣，這些應用中數據的時間限制性也逐步凸顯，對于數據庫系統需用新鮮的數據去反映物理世界對象狀態的最新變化也有了進一步的要求。同時由于實時數據庫系統中的事務有著嚴格的時間限制，事務必須在其截止期內提交，否則系統會產生極大損失甚至帶來災難。

負載的不可預測甚至可能的超載以及資源的有限性，是實時數據庫系統應用中面臨的又一難題。近來，基于反饋控制的實時調度方法應用于軟實時系統的研究取得了較大的進展。反饋控制實時調度把反饋控制理論和調度算法結合在一起，采用控制理論分析和建立實時系統的調度模型及實時系統的性能評價體系，通過連續地調整控制器來保持最優的性能。然而這些文獻很少對系統處于超載情況下的調度進行研究。

本文以實時數據庫事務調度為典型應用背景，研究和分析了不精確性計算方法，給出了一個基于不精確性計算的事務模型，并基于該模型提出了一種基于反饋控制的事務調度體系結構以及建模方法，為最終提高在超載環境下實時數據庫系統的服務質量提供了有效的解決方案。

1 不精確性計算實時數據庫事務模型

實時數據庫系統必須能夠并發地處理包括硬實時事務、固實時事務與軟實時事務，而這些事務又可分為更新事務和用戶事務。文中假設更新事務周期性到達，往數據庫中寫入從傳感器采集來的數據；用戶事務非周期地到達并且可以讀時序數據和讀/寫非時序數據（“有效期”是任意長的數據）。然而，當系統超載運行時，系統無足夠的時間來調度每個事務的實時執行，就會導致一些實時事務超過截止期，經典的RM，EDF，LLF等算法都無法直接處理這種超載情況。

文中把不精確計算方法之一的里程碑方法[1]應用到事務的不精確調度服務中，根據該方法將一個事務分割成若干子事務。假定事務Ti有一個關鍵子事務（Mi）和n個可選子事務Oi,j（0≤j≤n）組成。ti∈{Mi,Oi,1,…,Oi,n}表示事務Ti的子事務。同時假設事務Ti的所有子事務在同一時刻到達，當其關鍵子事務Mi完成時，第一個可選子事務Oi,1才執行。通常，一個可選子事務Oi,j在Oi,j-1（2≤j≤|Oi|）完成的時候才執行。設定每個子事務ti的截止期為事務Ti的截止期。如果一個子事務已經完成或者錯過它的截止期那么這個子事務就終止。一個事務Ti終止的條件是當子事務Oi,|Oi|完成或者事務Ti中的一個子事務錯過它的截止期。

2 反饋控制調度體系結構

由于實時數據庫更新一個數據對象的時間總有一定的延遲，并且系統的負載難以預知，因此系統可能出現超載的情況。先前的一些研究通過采用反饋控制調度[2]和動態更新策略[3]，用戶事務和更新事務能夠得到一個動態的平衡。在這些方法中，側重點在于保持用戶事務具有低的錯失率上。然而，當負載比較小時，需要把精力用在保持數據的新鮮度和一致性上。因此，文中提出了一種適應不精確事務模型的反饋控制調度體系結構FCS，見圖1。

圖1 反饋控制調度體系結構

2.1 準入控制器

準入控制器決定用戶事務是否可以提交給系統。工程技術人員設定一個總估計請求利用率（UE），當提交的子事務的估計利用率之和EETi≤UE時，準入控制器接受該用戶事務Ti并插入到就緒隊列中。

2.2 事務處理器

事務處理器由一個新鮮度管理器（FM）、并發控制器（CC）和基本的調度器（BS）組成，用來處理一個事務的執行。

新鮮度管理器決定用戶事務是否使用不新鮮的數據；并發控制器使用高優先級（具有更早截止期的事務）兩階段鎖（2PL-HP）的并發控制方法解決沖突；基本調度器根據一個調度策略（例如，EDF和RM）調度已提交的事務。

2.3 精確度控制器

精確度控制器用來決定是丟棄還是執行一個更新事務。如果DEi≤MDE，（DEi是將要被事務Tj更新的數據對象di的當前數據誤差），那么這個更新事務將被丟棄；如果di的數據誤差大于MDE，那么就執行這個更新事務。同時在這兩種情況下，di的時間戳也被更新，保證數據的外部（或絕對）一致性不被違背。

2.4 監視器

2.5 QoD控制器

QoD管理器根據受控變量M（k）、U（k）與性能參考值MrM、MrO和Ur進行比較后得到的△U調整數據質量等級MDE，然后基于該MDE調度更新事務的執行。

3 受控系統的建模

實時數據庫系統通常是一個非線性的和時變的系統，由于PI控制器方法的健壯性，因此可以用PI控制器來模擬一個以控制為目的的線性化模型的系統。受控系統模型如圖2。

圖2 受控系統模型

從控制輸入開始，第k＋1個周期的估計請求利用率可用下式表示，它是在第k個周期中的估計請求利用率（UE（k））和估計利用率調整量△U（k）的和。

UE（k+1）= UE（k）+△U（k） (1)

由于受控系統可能存在未知的事務和數據沖突的執行時間，因此，實際CPU利用率UA（k）可能和估計CPU利用率UE（k）不同。所以UA（k）根據下式來計算：

Ga(k)表示執行時間因子，它是一個時變的變量，表示總請求利用率的負載變化范圍。由于Ga(k)是時變的，為了保證系統的穩定性，文獻[2]采用Ga(k)的最大值GA=max{ Ga(k)}=2來替代系統模型Ga(k)。

由于飽和原因，UA和U之間的關系是非線性的。當UA>100%（CPU超載）時，即使△U改變了，U也不會有變化。等式（4）描述了這樣的一種關系：

GMM和GMO分別表示關鍵子事務和可選子事務的錯失率因子。因此，在可調度利用率極限附近，有

從等式(1)－(8)，可以進一步得出每一個受控變量在飽和區外時的傳遞函數：

利用率控制器： PU=GA/z-1，UA≤100%；關鍵子事務錯失率控制器： PMM= GAGMM/z-1，UA>UthM；可選子事務錯失率控制器：PMO= GAGMO/z-1，UA>UthO。模擬最壞情況下的系統[6]，可以獲得錯失率因子GMM和GMO。

文中的實驗設置采用在事務負載到達率的范圍從5tps～70tps，并以5tps遞增，并且用戶事務包含的可選子事務個數滿足1≤NOi≤3。圖3表示了在不同負載情況下的錯失率。

從圖3中可以看出可選子事務和關鍵子事務的可調度極限分別為UthO=15tps、UthM=45tps。因此，當負載在50tps～55tps和25tps～30tps之間增加時，可以根據公式（5）和公式（6）可以推導出GMM=1.66和GMO=2.23。

因此，根據上面得出的GMM、GMO從而可以得出利用率控制器、關鍵子事務控制器、可選子事務控制器在各自線性區域內的傳遞函數：PU、PMM和PMO。

圖3 實際負載與錯失率關系

4 反饋控制器算法設計和調整

由于PI調整器并不需要一個受控系統的精確模型，因此，文中采用PI控制器來調整系統性能。文獻[2]中已經有一些FCS策略，像FC－U，FC－M和FC－UM。文中的反饋控制器的算法，使用FC－M和FC－UM來控制數據和用戶事務的質量。圖4顯示了錯失率（含關鍵子事務和可選子事務控制器）和利用率控制器的概況。

圖4 錯失率、利用率控制器結構

采用同一個標記E（k）來表示EM（k）和EUtil三個性能誤差。文中使用PI控制函數來計算控制輸入△U（k），同時加入積分控制器來改善系統的穩態性能[7]。

△U(k)=△U(k-1)+KP((KI+1)E(k)-E(k-1)) (9)

對等式（9）進行z變換后得到：

C(Z)=g(z-r)/z-1 其中：g=(KP(KI+1)),r=1/KI+1

4.1 控制器參數的調整

用C（z）來表示關鍵子事務控制器、可選子事務控制器和利用率控制器，M（z）和Mr（z）分別來表示實際錯失率的z函數和錯失率參考值的z函數。那么每個反饋控制環的傳遞函數就能得出：

從而，可以根據等式(10)得出錯失率和利用率的閉環傳遞函數為：

可以根據公式（9）和（11），采用根軌跡法在matlab7.1中手動調整各個控制器的P參數和I參數。調整P、I參數的過程中，設定系統的性能參數為：穩定時間Ts≤30s、超調量Mp≤20。

圖5 調整關鍵子事務控制器后的階躍響應曲線

圖6 調整關鍵子事務控制器后的根軌跡圖

圖5顯示了關鍵子事務錯失率控制器的階躍響應圖，從圖中可以看到overshoot＝18.9％，settletime＝14.2s，滿足系統的性能要求。從圖6可看出極點在單位圓內，因此系統是穩定的[7]。從圖6中還可以得出KP=0.9738，KI=0.541；獲取可選子事務的和利用率控制器的KP和KI的方法同上。表1給出了最后調整的結果。

表1 控制器參數

4.2 算法描述

使用FC-U調度算法使用一個利用率控制回路控制利用率U（k），如圖4中控制決策選擇利用率回路，斷開錯失率回路；FC-M調度算法使用一個錯失率回路控制錯失率M（k）（含關鍵子事務MM（k）和可選子事務MO（k）），斷開利用率回路。由于單純采用FC-U和FC-M控制，實時數據庫系統均會不同程度的進入非線性飽和區[8]，因此提出如下調度解決方案FCS-UM。

獲取每個采樣周期MM（k）、MO（k）和U（k）的值

If △UM（k）<0∧△UO（k）<0 then

△UMP=△UM+△UO

Else △UMP=min（△UM，△UO）；

△U（k）=min（△UMP，△UUtil）；

If (△U（k）>0∧MDE（k）>0) then

升級QoD；

把調整后的信息提供給準入控制器；

Else

If (△U（k）<0∧MDE（k）

降級QoD；

把調整后的信息提供給準入控制器；

Else

If (△U（k）<0∧MDE（k）=MDEr×MP) then

拒絕事務的進入；

End If

5 結語

基于反饋控制的實時事務調度框架提供了一個通用的軟件架構，通過將實時系統映射成反饋系統的結構，進而采用控制理論較容易對實時系統進行分析和設計。然而在運用這些理論時，有些并不能完全適合實時數據庫系統的事務調度。本文將不精確性計算引入實時數據庫事務的模型構造中，并基于該模型將反饋控制理論加入實時數據庫事務調度的分析中，給出了一個基于反饋控制的實時事務調度體系結構及其建模方法，這將有助于完善反饋控制實時事務調度框架理論的設計分析。

[1] K.J.Lin,et a1.Imprecise results:utilizing partial computation in real-time systems[J].Proc.Real-Time Systems Symp.Dec, 1987:210-217.

[2] C. Lu, J.A. Stankovic, G. Tao, and S.H. Son.Feedback Control Real-Time Scheduling: Framework, Modeling and Algorithms[J]. Real-Time Systems, Vol.23, nos. 1/2, July/Sept. 2002:85-126

[3] K.Kang, S.H.Son, J.A.Stankovic, and T.F.Abdelzaher. A qossensitive approach for timeliness and freshness guarantees in real-time databases[C].14th Euromicro Conference on Real-time System, June 19-21,2002.

[4] Abdul, J.Jerri.The Shannon Sampling theorem-Its Various extension and applications: A tutoral review[J].Proc.of the IEEE, Vol.66,NO.11,Nov,1977:1565-1596.

[5] 王榮輝,王戰鐸.計算機控制系統中采樣周期的選擇方法[J].陜西工學院學報,1997(2):39-44.

[6] Joseph L. Hellerstein, Yixin Diao, Sujay Parekh, Dawn M.Tilbury. Feedback Control of Computing Systems[M].Publisher: Wiley, John & Sons, Incorporated. August 2004.

[7] 王翼.現代控制理論[M].北京:機械工業出版社,2005.

[8] 魏立峰,馬衛國,于海斌.反饋控制實時調度中采樣周期的研究[J].自動化儀表,2002,23(9):25-29.

Study on QoS in the real-time database system

GUO Li-cheng

(Computer Department of Zhangzhou Technical Institute, Fujian Zhangzhou 363000, China)

With the scheduling of real-time database transaction as typical application background, we study and analyze on imprecise computing thesis and present the real-time transaction model based on imprecise computing. Based on this transaction model structure of scheduling of real-time database and method of modeling scheduling structure of real-time transaction based on feedback control thesis was presented, which improve the QoS of real-time database system in the overload environment.

Real-time database; Quality of service; Scheduling of transaction; Feedback control;Imprecise computing

2012－09－25

郭里城（1979－），男，福建漳州人，助教，碩士。

TP392

A

1673-1417（2012）04-0001-06

（責任編輯：季平）