向 軍

(湖北民族學(xué)院 信息工程學(xué)院，湖北 恩施 445000)

實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)中不同分類事務(wù)由于不同的時(shí)間性要求[1]，錯(cuò)過相應(yīng)的截止期給系統(tǒng)性能帶來的損失不同，同時(shí)調(diào)度它們帶給系統(tǒng)價(jià)值也不同.因此，在實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)中應(yīng)根據(jù)實(shí)時(shí)事務(wù)帶給系統(tǒng)的價(jià)值有區(qū)別的調(diào)度，價(jià)值大且時(shí)間要求緊迫的優(yōu)先調(diào)度，價(jià)值小或時(shí)間不緊迫的暫緩調(diào)度.但是，對(duì)于復(fù)雜的嵌套硬實(shí)時(shí)事務(wù)，系統(tǒng)盡可能提供它們必需的如CPU、網(wǎng)絡(luò)帶寬等系統(tǒng)資源，這樣才可能滿足它們的截止期，同時(shí)也應(yīng)盡可能采用一些策略降低能量消耗，如采用DVS技術(shù)[2]加以控制.為提高系統(tǒng)性能和防止系統(tǒng)超載，應(yīng)該采用差分服務(wù)[3].

1 事務(wù)分類和系統(tǒng)價(jià)值模型

1.1 事務(wù)分類

實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)中，根據(jù)使用數(shù)據(jù)的方式實(shí)時(shí)事務(wù)分為以下兩類：用戶事務(wù)[4]和更新事務(wù)，用戶事務(wù)多用于讀或?qū)懛菚r(shí)序數(shù)據(jù)，同時(shí)到達(dá)是非周期性的；而更新事務(wù)更新時(shí)序數(shù)據(jù)對(duì)象是有一定周期的，其目標(biāo)是使得數(shù)據(jù)庫系統(tǒng)中時(shí)序?qū)ο蟮闹的苷鎸?shí)反映物理世界相應(yīng)數(shù)據(jù)對(duì)象的變化.另外，按照事務(wù)時(shí)間限制的性質(zhì)，可將實(shí)時(shí)事務(wù)分為三類：硬截止期實(shí)時(shí)事務(wù)、軟截止期實(shí)時(shí)事務(wù)和固截止期實(shí)時(shí)事務(wù)[4]，這三類事務(wù)分別有不同的時(shí)間限制要求，它們錯(cuò)過截止期后帶給系統(tǒng)的損失不同.當(dāng)硬實(shí)時(shí)事務(wù)錯(cuò)過截止期時(shí)，帶給系統(tǒng)將會(huì)是最嚴(yán)重的后果，因此這類事務(wù)優(yōu)先級(jí)最高；當(dāng)軟截止期實(shí)時(shí)事務(wù)錯(cuò)過截止期時(shí)，帶給系統(tǒng)仍然還有一定的價(jià)值，且不斷逐漸遞減直到價(jià)值為零；而對(duì)于固截止期實(shí)時(shí)事務(wù)一旦錯(cuò)過截止期，其價(jià)值馬上驟變?yōu)榱?當(dāng)同時(shí)有多個(gè)事務(wù)等待系統(tǒng)調(diào)度時(shí)，實(shí)時(shí)事務(wù)錯(cuò)過截止期帶給系統(tǒng)的損失和價(jià)值是指派優(yōu)先級(jí)的兩個(gè)重要參考依據(jù).

1.2 系統(tǒng)價(jià)值模型

為比較不同事務(wù)調(diào)度策略帶給系統(tǒng)的價(jià)值和性能上的變化，論文提出一套評(píng)價(jià)系統(tǒng)性能的價(jià)值模型.價(jià)值模型中主要考慮事務(wù)錯(cuò)過截止期比率、系統(tǒng)能耗、數(shù)據(jù)新鮮度等幾個(gè)因素.實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)中影響數(shù)據(jù)的新鮮度有很多原因，如網(wǎng)絡(luò)連接中斷、資源有限等可能造成的訪問數(shù)據(jù)時(shí)間延遲.但是，滿足實(shí)時(shí)事務(wù)截止期比數(shù)據(jù)的絕對(duì)正確性更為重要.論文提出的價(jià)值模型中的事務(wù)錯(cuò)過截止期比率簡(jiǎn)稱為Md(Deadline Miss Ratio of Transactions)，錯(cuò)過截止期的事務(wù)數(shù)量用Nd(k)表示，訪問數(shù)據(jù)的事務(wù)總數(shù)用Nt(k)表示，事務(wù)錯(cuò)過截止期的比率定義為：

(1)

同時(shí)，實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)中滿足事務(wù)的定時(shí)限制是其基本的設(shè)計(jì)準(zhǔn)則.價(jià)值模型中的數(shù)據(jù)新鮮度用Fd表示，主要是用來衡量數(shù)據(jù)庫系統(tǒng)中所有的數(shù)據(jù)(包括傳感器數(shù)據(jù))的新鮮程度.為討論方便，實(shí)時(shí)事務(wù)訪問新鮮數(shù)據(jù)的數(shù)量用Nf(k)表示，實(shí)時(shí)事務(wù)訪問到的所有數(shù)據(jù)數(shù)量用Na(k)表示，數(shù)據(jù)新鮮度形式定義如下：

(2)

實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)新鮮度，論文主要從價(jià)值域(value domain)和時(shí)間域(time domain)兩個(gè)角度分析.在時(shí)間域內(nèi)討論數(shù)據(jù)的時(shí)間有效性時(shí)，主要通過當(dāng)前時(shí)間和數(shù)據(jù)采用時(shí)間的時(shí)間差判斷數(shù)據(jù)對(duì)象是否新鮮.雖然物理世界數(shù)據(jù)對(duì)象的值隨著時(shí)間不斷在變化，如天氣的溫度、股票的價(jià)格等，但是有時(shí)數(shù)據(jù)對(duì)象值變化幅度卻非常小，甚至不會(huì)影響到系統(tǒng)性能.此時(shí)，如果按照時(shí)間域內(nèi)的數(shù)據(jù)新鮮度要求實(shí)時(shí)事務(wù)去更新相應(yīng)的數(shù)據(jù)對(duì)象，這樣可能會(huì)極大地增加系統(tǒng)負(fù)載，浪費(fèi)系統(tǒng)資源做了無用功.如果在值域范圍內(nèi)每個(gè)數(shù)據(jù)對(duì)象都有一個(gè)可容許偏差的標(biāo)準(zhǔn)值，只要物理世界數(shù)據(jù)對(duì)象值域變化小于這個(gè)標(biāo)準(zhǔn)值，實(shí)時(shí)事務(wù)對(duì)那些數(shù)據(jù)對(duì)象的更新就可以舍棄.這樣既一定程度上維持了數(shù)據(jù)的新鮮度，同時(shí)又降低了系統(tǒng)負(fù)載.為提高系統(tǒng)性能和調(diào)度事務(wù)帶給系統(tǒng)的價(jià)值，還應(yīng)該預(yù)留系統(tǒng)資源，系統(tǒng)資源利用率主要是對(duì)CPU的評(píng)測(cè)，它的價(jià)值模型可參考文獻(xiàn)[5].

2 事務(wù)的差分服務(wù)

2.1 差分服務(wù)

實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)中負(fù)載不可預(yù)測(cè)和可能會(huì)出現(xiàn)的超載，使得很多事務(wù)都有可能錯(cuò)過截止期或違反數(shù)據(jù)新鮮度限制.因?yàn)檎{(diào)度系統(tǒng)中的不同的事務(wù)帶給系統(tǒng)的價(jià)值，或者實(shí)時(shí)事務(wù)錯(cuò)過截止期后造成的損失是有差異的，因此所有的實(shí)時(shí)事務(wù)不能完全等同處理.為提高實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)性能和調(diào)度實(shí)時(shí)事務(wù)帶給系統(tǒng)的價(jià)值，有必要對(duì)系統(tǒng)中的實(shí)時(shí)事務(wù)采用差分服務(wù).具體方法是：從服務(wù)角度將實(shí)時(shí)事務(wù)分為特級(jí)、適中、一般三類，分別編號(hào)為0、1、2，并且規(guī)定編號(hào)數(shù)字越小服務(wù)的級(jí)別越高.下面的就是三類事務(wù)的性能測(cè)度.

0類：Md0≤1%,Fd0≥98%,U0≤10%

1類：Md1≤6%,Fd1≥95%,U1≤13%

2類：Md2≤10%,Fd2≥92%,U2≤15%

上述不同服務(wù)類別的事務(wù)對(duì)系統(tǒng)要求不同，0類的事務(wù)錯(cuò)過截止期比率要求最高，不能高于1%，而且0類事務(wù)另外兩個(gè)參數(shù)也高于其它兩類，因此調(diào)度算法中要優(yōu)先調(diào)度這類事務(wù).同時(shí)對(duì)于實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)出現(xiàn)瞬時(shí)過載現(xiàn)象時(shí)，要求穩(wěn)定時(shí)間(Setting Time,Ts)[6]盡量短，使得系統(tǒng)盡快回復(fù)到穩(wěn)定狀態(tài).實(shí)時(shí)事務(wù)進(jìn)行差分服務(wù)分類的主要依據(jù)是：事務(wù)對(duì)時(shí)間有效性、價(jià)值函數(shù)等.通過對(duì)實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)中的事務(wù)實(shí)行差分服務(wù)，雖然事務(wù)的錯(cuò)過截止期比率可能沒有降低很多，但帶給系統(tǒng)的價(jià)值卻變大或事務(wù)因錯(cuò)過截止期給系統(tǒng)帶來的損失減小，總體來說對(duì)系統(tǒng)性能有較大地改觀，可以通過后面的仿真實(shí)驗(yàn)來證明.

2.2 系統(tǒng)控制結(jié)構(gòu)

圖1 系統(tǒng)控制結(jié)構(gòu)

2.3 算法設(shè)計(jì)

基于差分服務(wù)和降低能耗的事務(wù)調(diào)度算法思想是：數(shù)據(jù)庫管理員根據(jù)系統(tǒng)實(shí)際運(yùn)行環(huán)境和用戶本身需求設(shè)定價(jià)值模型相關(guān)參數(shù)的預(yù)置標(biāo)準(zhǔn)值(參數(shù)預(yù)置參考值符號(hào)加下標(biāo)R表示，如MdR)，并且設(shè)定可調(diào)變量的初始值.具體算法偽代碼如下：

監(jiān)測(cè)Md(k),U(k),and Fd(k)，τ表示數(shù)據(jù)項(xiàng)x的事務(wù)，Qac表示通過AC的事務(wù)隊(duì)列

InputMdR,UR,FdR

For τ(x) in Qac

If and |tc-tx|≤Tathen //判斷是否錯(cuò)過截止期

putτ(x) in the Q0

putτ(x) in the Q1

else

putτ(x) in the Q2

end if

else

discardτ(x)

end if

end for

compute Md(k),U(k),and Fd(k)

scheduleQ0,Q1,Q2

ifMd(k)≥MdRor U(k)≥URor Fd(k)≥FdRthen

end if

3 仿真實(shí)驗(yàn)

圖2 不同下平均Fd變化

圖3 不同下事務(wù)平均Md的變化

4 結(jié)語

通過對(duì)實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)中具有不同時(shí)間限制的事務(wù)進(jìn)行差分服務(wù)，同時(shí)結(jié)合對(duì)論文提出的價(jià)值模型參數(shù)的監(jiān)測(cè)和反饋控制，使得系統(tǒng)穩(wěn)態(tài)下性能有一定程度提高，特別是降低了事務(wù)錯(cuò)過截止期比率和提高了數(shù)據(jù)庫的數(shù)據(jù)新鮮度.這對(duì)于實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)應(yīng)用有著積極的促進(jìn)作用.

[1]Kyoung Don Kang,Sang H Son,John A Stankovic.Managing Deadline Miss Ration and Sensor Data Freshness in Real-time Databases[J]. IEEE Transaction on Knowledge and Data Engineering,2004,16(10):1 200-1 216.

[2]Jian Jia Chen,Tei Wei Kuo.Voltage-Scaling Scheduling for Periodic Real-Time Tasks in Reward Maximization[C]//Proceedings of the 26th IEEE Real-Time Systems Symposium, Washington: IEEE Computer Society Press,2005:355-365.

[3]Kyoung Don Kang,Sang H Son,John A Stankovic.Differentiated Real-Time Data Services for E-Commerce Applications[J]. Electronic Commerce Research, 2003,3(1/2):113-142.

[4]劉云生.現(xiàn)代數(shù)據(jù)庫技術(shù)[M].北京:國防工業(yè)出版社,2001：100-129.

[5]向軍.移動(dòng)實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)服務(wù)質(zhì)量管理[D].武漢：華中科技大學(xué)，2008.

[6]Sudha Anil Kumar,G Manimaran G,Wang Z.Energy-Aware Scheduling of Real-Time Tasks in Wireless Networked Embedded Systems[C]//Proceedings of the 28th IEEE Real-Time Systems Symposium 2007,Washington:IEEE Computer Society Press,2007:15-24.

[7]LU C,John A Stankovic,Tao Gang,et al.Feedback Control Real-time Scheduling: Framework, Modeling and Algorithms[J].Real-time Systems,2002,23(1):1-31.