分布式实时数据库系统基于截止时间的优先级分配策略

　　摘 要： 分布式实时数据库系统设计的两个主要方面包括优先级的安排和并发控制算法。然而大量的文献主要关注并发控制算法，对优先级分配策略研究较少。本文在阐述了相关概念和建立系统模型后，通过仿真实验对比分析了不同的基于截止时间的优先级分配策略算法的性能。
　　关键词： 分布式实时数据库系统 截止时间 优先级分配策略
　　
　　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.