郭里城

?

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

郭里城

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

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

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

引言

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

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

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

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

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

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

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

由于實(shí)時(shí)數(shù)據(jù)庫更新一個(gè)數(shù)據(jù)對象的時(shí)間總有一定的延遲，并且系統(tǒng)的負(fù)載難以預(yù)知，因此系統(tǒng)可能出現(xiàn)超載的情況。先前的一些研究通過采用反饋控制調(diào)度[2]和動(dòng)態(tài)更新策略[3]，用戶事務(wù)和更新事務(wù)能夠得到一個(gè)動(dòng)態(tài)的平衡。在這些方法中，側(cè)重點(diǎn)在于保持用戶事務(wù)具有低的錯(cuò)失率上。然而，當(dāng)負(fù)載比較小時(shí)，需要把精力用在保持?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è)定一個(gè)總估計(jì)請求利用率（UE），當(dāng)提交的子事務(wù)的估計(jì)利用率之和EETi≤UE時(shí)，準(zhǔn)入控制器接受該用戶事務(wù)Ti并插入到就緒隊(duì)列中。

2.2 事務(wù)處理器

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

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

2.3 精確度控制器

精確度控制器用來決定是丟棄還是執(zhí)行一個(gè)更新事務(wù)。如果DEi≤MDE，（DEi是將要被事務(wù)Tj更新的數(shù)據(jù)對象di的當(dāng)前數(shù)據(jù)誤差），那么這個(gè)更新事務(wù)將被丟棄；如果di的數(shù)據(jù)誤差大于MDE，那么就執(zhí)行這個(gè)更新事務(wù)。同時(shí)在這兩種情況下，di的時(shí)間戳也被更新，保證數(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ì)量等級(jí)MDE，然后基于該MDE調(diào)度更新事務(wù)的執(zhí)行。

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

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

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

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

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

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

Ga(k)表示執(zhí)行時(shí)間因子，它是一個(gè)時(shí)變的變量，表示總請求利用率的負(fù)載變化范圍。由于Ga(k)是時(shí)變的，為了保證系統(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超載）時(shí)，即使△U改變了，U也不會(huì)有變化。等式（4）描述了這樣的一種關(guān)系：

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

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

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

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

從圖3中可以看出可選子事務(wù)和關(guān)鍵子事務(wù)的可調(diào)度極限分別為UthO=15tps、UthM=45tps。因此，當(dāng)負(fù)載在50tps～55tps和25tps～30tps之間增加時(shí)，可以根據(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 實(shí)際負(fù)載與錯(cuò)失率關(guān)系

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

由于PI調(diào)整器并不需要一個(gè)受控系統(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顯示了錯(cuò)失率（含關(guān)鍵子事務(wù)和可選子事務(wù)控制器）和利用率控制器的概況。

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

采用同一個(gè)標(biāo)記E（k）來表示EM（k）和EUtil三個(gè)性能誤差。文中使用PI控制函數(shù)來計(jì)算控制輸入△U（k），同時(shí)加入積分控制器來改善系統(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）分別來表示實(shí)際錯(cuò)失率的z函數(shù)和錯(cuò)失率參考值的z函數(shù)。那么每個(gè)反饋控制環(huán)的傳遞函數(shù)就能得出：

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

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

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

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

圖5顯示了關(guān)鍵子事務(wù)錯(cuò)失率控制器的階躍響應(yīng)圖，從圖中可以看到overshoot＝18.9％，settletime＝14.2s，滿足系統(tǒng)的性能要求。從圖6可看出極點(diǎn)在單位圓內(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)度算法使用一個(gè)利用率控制回路控制利用率U（k），如圖4中控制決策選擇利用率回路，斷開錯(cuò)失率回路；FC-M調(diào)度算法使用一個(gè)錯(cuò)失率回路控制錯(cuò)失率M（k）（含關(guān)鍵子事務(wù)MM（k）和可選子事務(wù)MO（k）），斷開利用率回路。由于單純采用FC-U和FC-M控制，實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)均會(huì)不同程度的進(jìn)入非線性飽和區(qū)[8]，因此提出如下調(diào)度解決方案FCS-UM。

獲取每個(gè)采樣周期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

升級(jí)QoD；

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

Else

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

降級(jí)QoD；

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

Else

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

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

End If

5 結(jié)語

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

[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ì)算機(jī)控制系統(tǒng)中采樣周期的選擇方法[J].陜西工學(xué)院學(xué)報(bào),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)國,于海斌.反饋控制實(shí)時(shí)調(diào)度中采樣周期的研究[J].自動(dòng)化儀表,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é)任編輯：季平）