郭里城

?

實時數(shù)據(jù)庫系統(tǒng)服務(wù)質(zhì)量管理研究

郭里城

（漳州職業(yè)技術(shù)學(xué)院 計算機(jī)工程系，福建 漳州 363000）

以實時數(shù)據(jù)庫事務(wù)調(diào)度為典型應(yīng)用背景，研究和分析了不精確性計算方法，給出了一個基于不精確性計算的事務(wù)模型，并基于該事務(wù)模型提出了一種基于反饋控制的實時事務(wù)調(diào)度體系結(jié)構(gòu)以及建模方法，為最終提高在超載環(huán)境下實時數(shù)據(jù)庫系統(tǒng)的服務(wù)質(zhì)量提供了有效的解決方案。

實時數(shù)據(jù)庫；服務(wù)質(zhì)量；事務(wù)調(diào)度；反饋控制；不精確計算

引言

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

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

本文以實時數(shù)據(jù)庫事務(wù)調(diào)度為典型應(yīng)用背景，研究和分析了不精確性計算方法，給出了一個基于不精確性計算的事務(wù)模型，并基于該模型提出了一種基于反饋控制的事務(wù)調(diào)度體系結(jié)構(gòu)以及建模方法，為最終提高在超載環(huán)境下實時數(shù)據(jù)庫系統(tǒng)的服務(wù)質(zhì)量提供了有效的解決方案。

1 不精確性計算實時數(shù)據(jù)庫事務(wù)模型

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

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

2 反饋控制調(diào)度體系結(jié)構(gòu)

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

圖1 反饋控制調(diào)度體系結(jié)構(gòu)

2.1 準(zhǔn)入控制器

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

2.2 事務(wù)處理器

事務(wù)處理器由一個新鮮度管理器（FM）、并發(fā)控制器（CC）和基本的調(diào)度器（BS）組成，用來處理一個事務(wù)的執(zhí)行。

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

2.3 精確度控制器

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

2.4 監(jiān)視器

2.5 QoD控制器

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

3 受控系統(tǒng)的建模

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

圖2 受控系統(tǒng)模型

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

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

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

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

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

GMM和GMO分別表示關(guān)鍵子事務(wù)和可選子事務(wù)的錯失率因子。因此，在可調(diào)度利用率極限附近，有

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

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

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

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

因此，根據(jù)上面得出的GMM、GMO從而可以得出利用率控制器、關(guān)鍵子事務(wù)控制器、可選子事務(wù)控制器在各自線性區(qū)域內(nèi)的傳遞函數(shù)：PU、PMM和PMO。

圖3 實際負(fù)載與錯失率關(guān)系

4 反饋控制器算法設(shè)計和調(diào)整

由于PI調(diào)整器并不需要一個受控系統(tǒng)的精確模型，因此，文中采用PI控制器來調(diào)整系統(tǒng)性能。文獻(xiàn)[2]中已經(jīng)有一些FCS策略，像FC－U，F(xiàn)C－M和FC－UM。文中的反饋控制器的算法，使用FC－M和FC－UM來控制數(shù)據(jù)和用戶事務(wù)的質(zhì)量。圖4顯示了錯失率（含關(guān)鍵子事務(wù)和可選子事務(wù)控制器）和利用率控制器的概況。

圖4 錯失率、利用率控制器結(jié)構(gòu)

采用同一個標(biāo)記E（k）來表示EM（k）和EUtil三個性能誤差。文中使用PI控制函數(shù)來計算控制輸入△U（k），同時加入積分控制器來改善系統(tǒng)的穩(wěn)態(tài)性能[7]。

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

對等式（9）進(jìn)行z變換后得到：

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

4.1 控制器參數(shù)的調(diào)整

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

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

可以根據(jù)公式（9）和（11），采用根軌跡法在matlab7.1中手動調(diào)整各個控制器的P參數(shù)和I參數(shù)。調(diào)整P、I參數(shù)的過程中，設(shè)定系統(tǒng)的性能參數(shù)為：穩(wěn)定時間Ts≤30s、超調(diào)量Mp≤20。

圖5 調(diào)整關(guān)鍵子事務(wù)控制器后的階躍響應(yīng)曲線

圖6 調(diào)整關(guān)鍵子事務(wù)控制器后的根軌跡圖

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

表1 控制器參數(shù)

4.2 算法描述

使用FC-U調(diào)度算法使用一個利用率控制回路控制利用率U（k），如圖4中控制決策選擇利用率回路，斷開錯失率回路；FC-M調(diào)度算法使用一個錯失率回路控制錯失率M（k）（含關(guān)鍵子事務(wù)MM（k）和可選子事務(wù)MO（k）），斷開利用率回路。由于單純采用FC-U和FC-M控制，實時數(shù)據(jù)庫系統(tǒng)均會不同程度的進(jìn)入非線性飽和區(qū)[8]，因此提出如下調(diào)度解決方案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；

把調(diào)整后的信息提供給準(zhǔn)入控制器；

Else

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

降級QoD；

把調(diào)整后的信息提供給準(zhǔn)入控制器；

Else

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

拒絕事務(wù)的進(jìn)入；

End If

5 結(jié)語

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

[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] 王榮輝,王戰(zhàn)鐸.計算機(jī)控制系統(tǒng)中采樣周期的選擇方法[J].陜西工學(xué)院學(xué)報,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] 王翼.現(xiàn)代控制理論[M].北京:機(jī)械工業(yè)出版社,2005.

[8] 魏立峰,馬衛(wèi)國,于海斌.反饋控制實時調(diào)度中采樣周期的研究[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

（責(zé)任編輯：季平）