向 軍

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

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

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

1.1 事務分類

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

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

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

(1)

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

(2)

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

2 事務的差分服務

2.1 差分服務

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

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

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

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

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

2.2 系統(tǒng)控制結構

圖1 系統(tǒng)控制結構

2.3 算法設計

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

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

InputMdR,UR,FdR

For τ(x) in Qac

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

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 仿真實驗

圖2 不同下平均Fd變化

圖3 不同下事務平均Md的變化

4 結語

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

[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ù)庫技術[M].北京:國防工業(yè)出版社,2001：100-129.

[5]向軍.移動實時數(shù)據(jù)庫系統(tǒng)服務質量管理[D].武漢：華中科技大學，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.