分布式實時數(shù)據(jù)庫系統(tǒng)基于截止時間的優(yōu)先級分配策略

　　摘 要： 分布式實時數(shù)據(jù)庫系統(tǒng)設(shè)計的兩個主要方面包括優(yōu)先級的安排和并發(fā)控制算法。然而大量的文獻(xiàn)主要關(guān)注并發(fā)控制算法，對優(yōu)先級分配策略研究較少。本文在闡述了相關(guān)概念和建立系統(tǒng)模型后，通過仿真實驗對比分析了不同的基于截止時間的優(yōu)先級分配策略算法的性能。
　　關(guān)鍵詞： 分布式實時數(shù)據(jù)庫系統(tǒng) 截止時間 優(yōu)先級分配策略
　　
　　1.引言
　　數(shù)據(jù)庫和數(shù)據(jù)庫系統(tǒng)如今已成為人們?nèi)粘Ｉ钪械囊徊糠郑蕴幚砗Ａ拷灰仔畔樘卣鞯默F(xiàn)代電子服務(wù)業(yè)和電子商務(wù)應(yīng)用離不開計算機(jī)系統(tǒng)和數(shù)據(jù)庫技術(shù)的支持。數(shù)據(jù)庫系統(tǒng)在管理和處理不斷增長的數(shù)據(jù)發(fā)揮著重要的作用。新的應(yīng)用領(lǐng)域的出現(xiàn)對數(shù)據(jù)庫系統(tǒng)提出了新的功能需求，其不僅要求數(shù)據(jù)庫系統(tǒng)處理數(shù)據(jù)，而且應(yīng)提供新的處理策略。
　　實時數(shù)據(jù)庫系統(tǒng)（Real-Time Database System，RTDBS）是數(shù)據(jù)和事務(wù)都有顯示定時限制的數(shù)據(jù)庫系統(tǒng)。系統(tǒng)的正確性不僅依賴于邏輯結(jié)果，而且依賴于邏輯結(jié)果產(chǎn)生的時間［１］。許多實時應(yīng)用系統(tǒng)（如先進(jìn)指揮和控制系統(tǒng)）本質(zhì)上是分布的，分布式實時數(shù)據(jù)庫系統(tǒng)（Distributed real-time database systems）允許事務(wù)通過網(wǎng)絡(luò)在場點之間存取共享的數(shù)據(jù)。由于其事務(wù)調(diào)度是有時限的（通常表示為截止時間），且必須維護(hù)數(shù)據(jù)庫全局和局部的一致性，決定了分布式實時數(shù)據(jù)庫系統(tǒng)在執(zhí)行事務(wù)的場點間交換需包含調(diào)度信息的消息［2］。因消息交換導(dǎo)致通信的延時使得系統(tǒng)對事務(wù)響應(yīng)時間的開銷大增，反過來使得分布式實時數(shù)據(jù)庫滿足時限的要求難度增加。
　　是否能在截止時間到達(dá)前完成事務(wù)是衡量分布式實時數(shù)據(jù)庫系統(tǒng)最重要的性能指標(biāo)之一，影響該性能指標(biāo)的因素很多，執(zhí)行事務(wù)過程中的發(fā)生的數(shù)據(jù)沖突則是主要原因。數(shù)據(jù)沖突將導(dǎo)致事務(wù)出現(xiàn)執(zhí)行—提交沖突，為了解決執(zhí)行—提交沖突，保證事務(wù)的原子性，大量的專家學(xué)者提出了諸多實時并發(fā)控制算法［3-11］，而很少關(guān)注事務(wù)調(diào)度的優(yōu)先級分配策略。我在此則在優(yōu)先級分配策略方面做出初步探討。
　　2.分布式實時數(shù)據(jù)庫系統(tǒng)模型
　　在分布式實時數(shù)據(jù)庫系統(tǒng)中，信息存儲在由可靠通訊網(wǎng)絡(luò)連接的場點中。每個場點唯一標(biāo)識，彼此間發(fā)送消息通訊，所有的消息均要求在規(guī)定的時間按照發(fā)送順序到達(dá)。各場點內(nèi)部具有邏輯時鐘，是松弛同步的，系統(tǒng)則根據(jù)場點的標(biāo)識和場點的本地時鐘產(chǎn)生時間戳。
　　分布式事務(wù)可視為由執(zhí)行在不同場點的子事務(wù)的集合，每個事務(wù)根據(jù)各自的實時約束指定一個全局唯一優(yōu)先級，其子事務(wù)的優(yōu)先級相等。事務(wù)以一定順序執(zhí)行，且每次執(zhí)行一個事務(wù)，各事務(wù)的子事務(wù)存取數(shù)據(jù)對象和執(zhí)行處理過程是相互獨(dú)立的。
　　事務(wù)的執(zhí)行分三個階段（如圖1所示）［１1］：讀階段、驗證階段、寫階段。在讀階段，從數(shù)據(jù)庫讀取被請求的數(shù)據(jù)對象，寫操作在其他事務(wù)不可訪問的私有空間執(zhí)行。在驗證階段，確保待驗證的事務(wù)可串行化。在寫階段，完成更新操作，使得更新后的結(jié)果對其他事務(wù)可見。
　　事務(wù)根據(jù)獲取資源（如CPU，數(shù)據(jù)對象等）的優(yōu)先級進(jìn)行調(diào)度，事務(wù)的優(yōu)先級與優(yōu)先級的分配策略緊密相關(guān)。事務(wù)的優(yōu)先級分配策略既可以是靜態(tài)的也可以是動態(tài)的［１2］。文獻(xiàn)［１3］通過實驗說明大多數(shù)情況下動態(tài)的優(yōu)先級分配策略比靜態(tài)的優(yōu)先級分配策略獲得更佳的系統(tǒng)性能。最佳的優(yōu)先級分配策略之一是基于事務(wù)的截止時間，本文采用此方法。
　　分布式實時數(shù)據(jù)庫的模型（如圖2所示）由8部分組成：事務(wù)生成器TG、事務(wù)管理器TM、事務(wù)調(diào)度器TS和并發(fā)控制器CC（由就緒隊列RQ和阻塞隊列BQ組成）、數(shù)據(jù)管理器DM、資源管理器RM、數(shù)據(jù)庫DB，以及網(wǎng)絡(luò)管理器NM。
　　3.分布式實時數(shù)據(jù)庫系統(tǒng)仿真實驗
　　在實驗過程中，選取EDF ［１４］、UD［１5］、ED［１5］、GDPA［１6］共4個基于截止時間的優(yōu)先級分配策略進(jìn)行對比分析。其中，GDPA的算法描述如下：
　　1：Input：Ready queue ζ at contains tasks in ready state
　　2：Output：A selected task for execution
　　12：end for
　　13：=sortByShortestDistanceFirst（ζ）;
　　3.1實驗參數(shù)
　　3.2實驗結(jié)果
　　從圖3可以看出，無論是系統(tǒng)工作在正常負(fù)荷狀態(tài)還是超負(fù)荷狀態(tài)（通常認(rèn)為Miss Rate在0%～20%范圍內(nèi)系統(tǒng)工作在正常負(fù)荷狀態(tài)，21%～100%系統(tǒng)工作在超負(fù)荷狀態(tài)），隨著arrival rate的減少，有利于系統(tǒng)性能的改善。在正常負(fù)荷狀態(tài)時4種算法的性能相差很小，但在超負(fù)荷狀態(tài)下性能差異較大。總體而言，在選擇的4個基于截止時間的優(yōu)先級分配策略中，性能最好的是GDPA，其次是ED、UD，經(jīng)典的EDF則需改進(jìn)。
　　4.結(jié)語
　　分布式實時數(shù)據(jù)庫系統(tǒng)在現(xiàn)代社會發(fā)揮著重要的作用，已有大量的文獻(xiàn)在不同事務(wù)管理條件下通過仿真分析其性能。事務(wù)合理的調(diào)度有利與事務(wù)在截止時間前完成事務(wù)，最小化失誤率。本文闡述了分布式實時數(shù)據(jù)庫系統(tǒng)的基本概念，建立了分布式實時數(shù)據(jù)庫系統(tǒng)的模型，并通過實驗對比分析了4種基于截止時間的優(yōu)先級分配策略算法的性能優(yōu)劣。
　　
　　參考文獻(xiàn)：
　　［1］Kwok-Wa Lam，Victor C.S.Lee，Sheung-Lun Hung.Transaction Scheduling in distributed real-time systems，The International Journal of Time-Critical Computing Systems，19，169-193，2000.
　　［2］Son，S.H.，and Koloumbis，S.A token-based synchronization scheme for distributed real-time databases.Information Systems，1993，18，（6）：375-389.
　　［3］Stankovic，J.A.，Ramamritham，K.，Towsley，D.Scheduling in real-time transaction systems.In：van Tilborg，A.，Koob，G.（eds.）Foundations of Real-Time Computing：Scheduling and ResourceManagement，Kluwer Academic，Dordrecht，1991，157-184.
　　［4］Burger，A.，Kumar，V.，Hines，M.L.：Performance of multiversion and distributed two-phase locking concurrency control mechanisms in distributed databases.Int.J.Inf.Sci，1997.1-2：129-152.
　　［5］Chakravarthy，S.，Hong，D.，Johnson，T.：Real time transaction scheduling：a framework for synthesizing static and dynamic factors.TR-008，CISE Dept.，University of Florida，1994.
　　
　　［6］George，B.：A secure real-time transaction processing.PhD thesis，Supercomputer Education and Research Centre，I.I.Sc.Bangalore，India，December，1998.
　　［7］Haritsa，J.R.，Carey，M.J.，Linvy，M.：Dynamic real-time optimistic concurrency control.In：Proceedings of the 11th Real-Time Systems Symposium，December，1990.
　　［8］Haritsa，J.R.，George，B.：Secure real-time transaction processing.In：Kuo，T.-W.，Lam，K.-Y.（eds.） Real-time Database Systems：Architecture and Techniques.Kluwer International Series in Engineering and Computer Science，Kluwer Academic，Dordrecht，2001，vol.593：141-157.
　　［9］Datta A，Son S H.A Study of Concurrency Control in Real-time，Active Database Systems［J］.IEEE Transactions on Knowledge and Data Engineering，2002，14，（3）：465-484.
　　［10］Lindstrom J.Optimistic Concurrency Control Methods for Real-time Database Systems［D］.Finland：University of Helsinki，2003.
　　［11］Kung，H.T.，and Robinson，J.T.On optimistic methods for concurrency control. ACM Transactions on Database Systems 1981.6，（2）：213-226.
　　［12］Ramamritham，K.Real-time databases.International Journal of Distributed and Parallel Databases，1993，1：199-226.
　　［13］Abbott，R.，and Garcia-Molina，H.Scheduling real-time transactions：A performance evaluation.ACM Transactions on Database Systems，1992，17，（3）：513-560.
　　［14］C.L.Liu，and J.W Layland，“Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment，”J.ACM，1973，vol.20，no.1：46-61.
　　［15］Victor C.S.Lee，Kam-Yiu Lam，Ben Kao，The International Journal of Time-Critical Computing Systems，1999，16：31-62.
　　［16］Hyeonjoong Cho et al.Guaranteed Dynamic Priority Assignment Schemes for Real-Time Tasks with （m，k）-Firm Deadlines.ETRI Journal，2010，3，（22）：422-429.
　　［17］Ulusoy，O.，and Belford，G.G.A simulation model for distributed real-time database systems.Proceedings of 25th Annual Simulation Symposium.pp，1992：232-240.
　　［18］Lam，K.Y.，Hung，S.L.，and Son，S.H.On using real-time static locking protocols for distributed real-time databases.Real-Time Systems13，1997：141-166.