实时数据库系统之实时事务调度算法

《实时数据库系统之实时事务调度算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实时数据库系统之实时事务调度算法实时数据库技术是实时系统和数据库技术相结合的产物，研究人员希望利用数据库技术来解决实时系统中的数据管理问题，同时利用实时技术为实时数据库提供时间驱动调度和资源分配算法。然而，实时数据库并非是两者在概念、结构和方法上的简单集成。需要针对不同的应用需求和应用特点，对实时数据模型、实时事务调度与资源分配策略、实时数据查询语言、实时数据通信等大量问题作深入的理论研究。实时事务调度策略定义如何为事务分配优先级，而调度的最重要目标是保证尽可能多的事务能够满足截止期。大部分实时任务调度算法并不能直接用于调度实时事务，原因在于：这些算法

2、通常要求任务到达时间、截止期与最坏情况执行时间与关键性等参数是已知的。而实时事务调度中广泛存在的不可预测因素，主要包括数据存取的动态性、磁盘I/O、事务夭折与回滚等，导致事务的最坏情况执行时间很难估计。因此，很多实时数据库采用主内存数据库模型，以消除I/O操作所带来的影响。另一方面，实时数据库通常应用于开放环境，系统的负载变化是不可预知的且可能在较大范围内变化，给实时事务调度带来更多的困难。Abbott等[ABB88]最先基于一个内存驻留的实时数据库模型，综合研究了FCFS（FirstComeFirstServe）、EDF（EarliestDeadli

3、neFirst）与LSF（LeastSlackFirst）三种优先级分配方法以及串行执行（SerialExecution）、2PL-HP（2PL-HighPriority）与2PL-CR（2PL-ConditionalRestart）三种并发控制协议，仿真实验结果表明：就调度算法而言，EDF算法表现出最好的性能；并发控制中2PL-CR表现出最好的性能，但是其性能很大程度地受到事务估计执行时间精度的影响。进一步地，Abbott等[ABB92]也在磁盘驻留的实时数据库模型之上对上面的算法与协议进行了测试，结果表明LSF优先级分配算法表现出最好的性能，而2P

4、L-WP协议与LSF或者EDF配合使用都优于2PL-HP协议，并且采用优先级驱动的I/O调度相对于FIFO方式具有很大的性能改进。无论如何，当系统负载采用步进方式递增时，EDF算法是性能最好的调度算法，而2PL-HP协议表现最佳。最后，Abbott等指出CPU调度算法是实时事务调度处理中最重要的策略，而在并发控制中使用优先级信息解决数据冲突有利于改进系统的性能。Huang等[HUA89]基于一个实时数据库测试床RT-CARAT，针对实时事务调度算法与冲突解决策略进行了实验研究，结果表明：实时事务调度算法必须综合考虑事务的截止期与关键性（或者价值），并且

5、在冲突解决策略中考虑这些信息能够改进系统性能；事务截止期与关键性的分布情况也在很大程度上影响系统的性能。因此，在随后的研究中，许多算法都把事务的关键性或者重要性看作调度算法中必须考虑的重要因素。上个世纪九十年代，实时事务调度的研究基本上是从基于价值的事务调度、基于准入控制的事务调度、满足时态一致性的事务调度等几个方面发展，并且进一步地在调度中考虑不同的事务模型以及过载消解方法。最近几年，反馈控制方法也被应用到实时事务的调度中，并取得了相当多的研究成果。另一方面，混合事务的也得到了越来越多的研究。1基于价值的事务调度在许多现实的应用中，不同的事务具有不同

6、的价值或者不同的关键程度。在实时数据库领域，先前的一些研究也已经考虑调度具有不同价值的事务，而系统的主要性能指标通常也转换为最大化系统的实现价值。最初，Huang等[HUA89]使用一个实时数据库测试床RT-CARAT评估了MCF（MostCriticalFirst）、EDF与CDF（Criticalness-DeadlineFirst）三种调度算法的性能，其中CDF算法中事务的优先级按照（相对截止期÷关键性）进行分配，结果表明综合考虑事务的截止期与关键性在很大上改进了系统的综合性能。Haritsa等[HAR91,HAR93]给出了不同的基于价值的优先

7、级分配算法：HighestValueFirst（HVF）、Value-InflatedDeadline（VD）、Value-InflatedRelativeDeadline（VRD）以及桶算法（BA：BucketAlgorithm），其中VD算法中事务的优先级按照（截止期÷关键性）进行分配，VRD算法等同于CDF算法。实验结果表明，EDF算法在负载较轻时表现最佳，HVF与VD算法在较高负载下性能较好，而VRD算法表现出最好的综合性能。不过，通过对BA算法的性能测试表明，没有一个固定的截止期-价值的折衷能够适用于所有负载情况，根据负载情况合理选择参数能够

8、产生最好的性能。此外，研究也表明了在采用综合截止期与价值的调度算法进行固定截止期事务调度时OC