分布式實時數據庫系統基于截止時間的優先級分配策略

　　摘 要： 分布式實時數據庫系統設計的兩個主要方面包括優先級的安排和并發控制算法。然而大量的文獻主要關注并發控制算法，對優先級分配策略研究較少。本文在闡述了相關概念和建立系統模型后，通過仿真實驗對比分析了不同的基于截止時間的優先級分配策略算法的性能。
　　關鍵詞： 分布式實時數據庫系統 截止時間 優先級分配策略
　　
　　1.引言
　　數據庫和數據庫系統如今已成為人們日常生活中的一部分，以處理海量交易信息為特征的現代電子服務業和電子商務應用離不開計算機系統和數據庫技術的支持。數據庫系統在管理和處理不斷增長的數據發揮著重要的作用。新的應用領域的出現對數據庫系統提出了新的功能需求，其不僅要求數據庫系統處理數據，而且應提供新的處理策略。
　　實時數據庫系統（Real-Time Database System，RTDBS）是數據和事務都有顯示定時限制的數據庫系統。系統的正確性不僅依賴于邏輯結果，而且依賴于邏輯結果產生的時間［１］。許多實時應用系統（如先進指揮和控制系統）本質上是分布的，分布式實時數據庫系統（Distributed real-time database systems）允許事務通過網絡在場點之間存取共享的數據。由于其事務調度是有時限的（通常表示為截止時間），且必須維護數據庫全局和局部的一致性，決定了分布式實時數據庫系統在執行事務的場點間交換需包含調度信息的消息［2］。因消息交換導致通信的延時使得系統對事務響應時間的開銷大增，反過來使得分布式實時數據庫滿足時限的要求難度增加。
　　是否能在截止時間到達前完成事務是衡量分布式實時數據庫系統最重要的性能指標之一，影響該性能指標的因素很多，執行事務過程中的發生的數據沖突則是主要原因。數據沖突將導致事務出現執行—提交沖突，為了解決執行—提交沖突，保證事務的原子性，大量的專家學者提出了諸多實時并發控制算法［3-11］，而很少關注事務調度的優先級分配策略。我在此則在優先級分配策略方面做出初步探討。
　　2.分布式實時數據庫系統模型
　　在分布式實時數據庫系統中，信息存儲在由可靠通訊網絡連接的場點中。每個場點唯一標識，彼此間發送消息通訊，所有的消息均要求在規定的時間按照發送順序到達。各場點內部具有邏輯時鐘，是松弛同步的，系統則根據場點的標識和場點的本地時鐘產生時間戳。
　　分布式事務可視為由執行在不同場點的子事務的集合，每個事務根據各自的實時約束指定一個全局唯一優先級，其子事務的優先級相等。事務以一定順序執行，且每次執行一個事務，各事務的子事務存取數據對象和執行處理過程是相互獨立的。
　　事務的執行分三個階段（如圖1所示）［１1］：讀階段、驗證階段、寫階段。在讀階段，從數據庫讀取被請求的數據對象，寫操作在其他事務不可訪問的私有空間執行。在驗證階段，確保待驗證的事務可串行化。在寫階段，完成更新操作，使得更新后的結果對其他事務可見。
　　事務根據獲取資源（如CPU，數據對象等）的優先級進行調度，事務的優先級與優先級的分配策略緊密相關。事務的優先級分配策略既可以是靜態的也可以是動態的［１2］。文獻［１3］通過實驗說明大多數情況下動態的優先級分配策略比靜態的優先級分配策略獲得更佳的系統性能。最佳的優先級分配策略之一是基于事務的截止時間，本文采用此方法。
　　分布式實時數據庫的模型（如圖2所示）由8部分組成：事務生成器TG、事務管理器TM、事務調度器TS和并發控制器CC（由就緒隊列RQ和阻塞隊列BQ組成）、數據管理器DM、資源管理器RM、數據庫DB，以及網絡管理器NM。
　　3.分布式實時數據庫系統仿真實驗
　　在實驗過程中，選取EDF ［１４］、UD［１5］、ED［１5］、GDPA［１6］共4個基于截止時間的優先級分配策略進行對比分析。其中，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實驗參數
　　3.2實驗結果
　　從圖3可以看出，無論是系統工作在正常負荷狀態還是超負荷狀態（通常認為Miss Rate在0%～20%范圍內系統工作在正常負荷狀態，21%～100%系統工作在超負荷狀態），隨著arrival rate的減少，有利于系統性能的改善。在正常負荷狀態時4種算法的性能相差很小，但在超負荷狀態下性能差異較大。總體而言，在選擇的4個基于截止時間的優先級分配策略中，性能最好的是GDPA，其次是ED、UD，經典的EDF則需改進。
　　4.結語
　　分布式實時數據庫系統在現代社會發揮著重要的作用，已有大量的文獻在不同事務管理條件下通過仿真分析其性能。事務合理的調度有利與事務在截止時間前完成事務，最小化失誤率。本文闡述了分布式實時數據庫系統的基本概念，建立了分布式實時數據庫系統的模型，并通過實驗對比分析了4種基于截止時間的優先級分配策略算法的性能優劣。
　　
　　參考文獻：
　　［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.