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

实时数据库系统之实时事务调度算法实时数据库技术是实时系统和数据库技术相结合的产物，研究人员希望利用数据库技术来解决实时系统中的数据管理问题，同时利用实时技术为实时数据库提供时间驱动调度和资源分配算法。然而，实时数据库并非是两者在概念、结构和方法上的简单集成。需要针对不同的应用需求和应用特点，对实时数据模型、实时事务调度与资源分配策略、实时数据查询语言、实时数据通信等大量问题作深入的理论研究。实时事务调度策略定义如何为事务分配优先级，而调度的最重要目标是保证尽可能多的事务能够满足截止期。大部分实时任务调度算法并不能直接用于调度实时事务，原因在于：这些算法通常要求任务到达时间、截止期与最坏情况执行时间与关键性等参数是已知的。而实时事务调度中广泛存在的不可预测因素，主要包括数据存取的动态性、磁盘I/O、事务夭折与回滚等，导致事务的最坏情况执行时间很难估计。因此，很多实时数据库采用主内存数据库模型，以消除I/O操作所带来的影响。另一方面，实时数据库通常应用于开放环境，系统的负载变化是不可预知的且可能在较大范围内变化，给实时事务调度带来更多的困难。Abbott等ABB88最先基于一个内存驻留的实时数据库模型，综合研究了FCFS（First Come First Serve）、EDF（Earliest Deadline First）与LSF（Least Slack First）三种优先级分配方法以及串行执行（Serial Execution）、2PL-HP（2PL-High Priority）与2PL-CR（2PL-Conditional Restart）三种并发控制协议，仿真实验结果表明：就调度算法而言，EDF算法表现出最好的性能；并发控制中2PL-CR表现出最好的性能，但是其性能很大程度地受到事务估计执行时间精度的影响。进一步地，Abbott等ABB92也在磁盘驻留的实时数据库模型之上对上面的算法与协议进行了测试，结果表明LSF优先级分配算法表现出最好的性能，而2PL-WP协议与LSF或者EDF配合使用都优于2PL-HP协议，并且采用优先级驱动的I/O调度相对于FIFO方式具有很大的性能改进。无论如何，当系统负载采用步进方式递增时，EDF算法是性能最好的调度算法，而2PL-HP协议表现最佳。最后，Abbott等指出CPU调度算法是实时事务调度处理中最重要的策略，而在并发控制中使用优先级信息解决数据冲突有利于改进系统的性能。Huang等HUA89基于一个实时数据库测试床RT-CARAT，针对实时事务调度算法与冲突解决策略进行了实验研究，结果表明：实时事务调度算法必须综合考虑事务的截止期与关键性（或者价值），并且在冲突解决策略中考虑这些信息能够改进系统性能；事务截止期与关键性的分布情况也在很大程度上影响系统的性能。因此，在随后的研究中，许多算法都把事务的关键性或者重要性看作调度算法中必须考虑的重要因素。上个世纪九十年代，实时事务调度的研究基本上是从基于价值的事务调度、基于准入控制的事务调度、满足时态一致性的事务调度等几个方面发展，并且进一步地在调度中考虑不同的事务模型以及过载消解方法。最近几年，反馈控制方法也被应用到实时事务的调度中，并取得了相当多的研究成果。另一方面，混合事务的也得到了越来越多的研究。1基于价值的事务调度在许多现实的应用中，不同的事务具有不同的价值或者不同的关键程度。在实时数据库领域，先前的一些研究也已经考虑调度具有不同价值的事务，而系统的主要性能指标通常也转换为最大化系统的实现价值。最初，Huang等HUA89使用一个实时数据库测试床RT-CARAT评估了MCF（Most Critical First）、EDF与CDF（Criticalness-Deadline First）三种调度算法的性能，其中CDF算法中事务的优先级按照（相对截止期关键性）进行分配，结果表明综合考虑事务的截止期与关键性在很大上改进了系统的综合性能。Haritsa等HAR91,HAR93给出了不同的基于价值的优先级分配算法：Highest Value First（HVF）、Value-Inflated Deadline（VD）、Value-Inflated Relative Deadline（VRD）以及桶算法（BA：Bucket Algorithm），其中VD算法中事务的优先级按照（截止期关键性）进行分配，VRD算法等同于CDF算法。实验结果表明，EDF算法在负载较轻时表现最佳，HVF与VD算法在较高负载下性能较好，而VRD算法表现出最好的综合性能。不过，通过对BA算法的性能测试表明，没有一个固定的截止期-价值的折衷能够适用于所有负载情况，根据负载情况合理选择参数能够产生最好的性能。此外，研究也表明了在采用综合截止期与价值的调度算法进行固定截止期事务调度时OCC-Wait协议的性能也优于2PL-HP协议。Tseng等TSE95提出了另一种基于价值的调度算法HRF（Highest Reward First），其中事务的优先级按照（价值剩余执行时间）进行分配，因此这种优先级是时变的。Haritsa与Tseng等HAR93,TSE95对于基于价值的调度算法进行了广泛研究，认为：如果事务的价值是偏斜分布，其中10的事务提供90的价值，则在正常负载下算法性能排序为EDFHRF HVFVRD，在系统过载时性能排序为HRFHVFVRDEDF。进一步，Tseng等TSE96研究了不同基于价值的实时事务调度算法在实时主内存数据库（RTMMDB）与部分驻留内存的实时数据库中的性能，目标在于评估并比较这些算法在主内存数据库环境中的性能，以及研究只存储部分数据在主内存中的效果。Tseng等的实验结果表明：当只有部分数据驻留内存时，增加内存的大小能够产生改进系统的性能，从而实现更高的价值。任务的价值也被用于准入控制中，决定任务的接纳或者移除先前接纳的任务，这将在下一小节讨论。此外，Bestavros等BES95研究了在软实时数据库中如何利用价值函数确定提交事务或者延迟提交事务，这种在并发控制中综合考虑事务的截止期与价值的问题能够归结为如何为竞争的事务定量配给冗余的资源，以便实现更大的系统价值。Hong与Chakravarthy等HON92,CHJ94在他们的研究工作中引入代价意识（Cost Consciousness）的概念，提出并评估了一个CCA-ALF（Cost Conscious Approach with Average Load Factor）调度策略，这是一个最大努力的方法，调度决策中既考虑了事务的静态方面（软/固截止期），也考虑了事务执行的动态方面（系统负载）。在Braoudakis的研究中BRA94，假设每个事务关联一个价值函数，标识了这个事务的时间需求与重要性。在这个框架下，事务的不同特征能够被描述，包括硬、固定、软或者无截止期事务，从而允许单个的事务处理协议在所有类型的事务上一致地执行。2基于准入的事务调度实时事务调度面临的一个主要挑战是事务执行所需要的资源是事先未知的。例如，事务读/写的数据对象可能依赖于用户的输入或者传感器输入，因此为事务预留资源以保证事务的最坏情况执行时间WCET（Worst Case Execution Time）是非常困难的。考虑当前在实时事务调度与实时并发控制方面众多的研究成果，其中包括许多时间认知的并发控制协议被提出，目的在于最大化满足截止期的事务数量。这些算法或者协议的优势只有当系统出现过载时才被具体地体现，它们的性能在系统欠载的情况下通常与非常简单的算法（如EDF与2PL-HP）相当。既然当一个实时数据库系统过载时，大量的事务错失了截止期，如果通过准入控制与过载管理策略拒绝一些事务进入系统，就能够避免有限的资源浪费在执行不可能及时完成的事务上。正是基于这种思想，一些研究针对准入控制技术进行了较深入的研究。Bestavros等BES96给出一个实时数据库模型，并在此基础上研究了硬截止期事务的准入控制与过载管理问题。由于硬实时事务错失截止期可能产生严重的后果，因此硬实时事务的执行需求必须预先知道，或者定义一些补救活动，以保证系统不会出现灾难性的后果。Bestavros等定义的事务模型中，每个事务由两个部分组成：基本子事务与补偿子事务。准入控制器用于决定是否接纳新到达的事务。这里，准入控制器由两个部分组成：并发准入控制器（CACM：Concurrency ACM）与负载准入控制器（WACM：Workload ACM）。为了保证补偿事务的完成，系统采用两层优先级模式进行调度。系统总是为补偿子事务分配一个更高的优先级，并且一个补偿子事务不能够被一个基本子事务或者另一个补偿子事务抢占。WACM基于估计系统负载确定是否接纳一个事务，特别是，如果用于补偿子事务的处理器带宽比较高，则应该谨慎地拒绝新到达的事务。为了确保补偿子事务无阻碍地执行，CACM保证被接纳事务的补偿子事务不与系统中已经接纳事务的补偿子事务存在冲突。Bestavros等BES96提出了一些不同的方法用于WACM并通过模拟实验比较了它们的性能。这些方法包括First-Fit（FF）、Latest-Fit（LF）、Latest-Marginal-Fit（LMF）、Latest-Adaptable-Fit（LAF）以及Value-Adaptable-Fit（VAF），其中前面四种方法都是通过判断补偿事务的可调度性或者给定补偿子事务处理器阈值下处理器带宽的可得到性决定接纳或者拒绝事务。VAF方法中准入控制分为两个部分：（1）评估接纳一个事务进入系统的预期价值，这是通过对比接纳这个事务潜在的价值与损失达到的；（2）通过动态计算分配给补偿事务的处理器带宽，对比补偿事务的处理器利用率，确定是否接纳这个事务。LAF与VAF都具有一定的自适应能力，但是其参数必须通过离线的仿真确定。虽然上面的论文研究了并发控制、准入控制与事务调度之间的相互作用，但是这些工作依然不够。例如，CCM应该能够使用CACM中的信息更好的进行并发控制决策；反之，CACM能够利用基本子事务的读写集确定是否执行特定的补偿事务。3动态过载消解方法准入控制通常作为过载管理的一部分，也存在一些研究通过不精确计算模型或者剔除部分已经接纳但是价值较小的事务来控制系统过载。在不精确计算模型LLS91,SHI89,SHI92中，任务分为必须与可选两部分，前者用于计算出一个满足最小系统需求的结果，而后者用于提高这个结果的质量。通常，必须的子任务具有硬截止期而可选子任务具有固定截止期。其实，基本/补偿事务BES96、主事务/附带事务HAN98、嵌套事务ELM92以及自适应事务Do96都与不精确计算模型基于相同的思想。Hansson等HAN98,HAN99给出了一个新的事务调度框架与过载管理算法，这个算法面向具有多类事务负载的主内存数据库系统。当准入控制器检测到系统过载，会调用过载消解器给出一个规划，从接纳的事务中解除足够的资源分配以便接纳新的事务，并且也确定执行这个规划是否有利于系统目标。Hansson等研究工作的优点之一在于把过载管理与事务调度、准入控制分开，进一步地，过载消解能够通过平衡多种策略并确定最优或者接近最优的方法。但是，其中存在的问题在于没有很好地讨论并解决并发控制与事务调度、系统过载之间的相互影响。另一方面，许多应用如协同工作系统等要求事务之间的协调与并行性，这些复杂的事务可以归类为扩展事务模型（ETM：Extended Transaction Model）ELM92。使用嵌套事务的驱动力之一是表达长寿事务，嵌套事务提供了事务内的并行性，具有较好的失效恢复能力。Fortier等FOR94通过扩展标准SQL语言描述了一个扩展事务模型，增加了前置条件与后置条件以定义事务的语义正确性。尽管基本/补偿事务BES96、主事务/附带事务HAN98可以归结为嵌套事务，但是这些研究更加偏重于成为一种满足事务截止期的策略。Dodu等Do96,Do96b给出了一种自适应实时事务模型，并提出了几种面向自适应事务的调度策略。自适应事务是具有可选与必需子事务的嵌套事务，构造为一个事务树，并通过时间约束来支持实时应用。每个自适应事务具有一个最小执行子集（MES：Minimal Execution Set），这个子集是从根结点开始连通所有必需子事务的一棵子树。自适应事务能够动态适应系统的负载情形，从而事务处理系统能够根据系统需求自动调节事务，有助于其它事务的完成。但是，调度自适应事务存在两个矛盾的方面：（1）最大化完成的事务数量，即事务成功率；（2）最大化每个自适应事务完成的部分，即事务子集完成率。因此，调度自适应事务的性能评估要求一个平衡的性能尺度。仿真结果也表明了基于优先级的事务调度如果考虑事务的结构能够改进系统性能。4面向时态一致性的调度机制在许多实时数据库应用中，不仅事务具有截止期，而且数据具有时态一致性需求。就维护数据的时态一致性方面，Song等SON95综合研究了RM、EDF调度算法与2PL、OCC并发控制协议，结果表明RM与EDF算法在较大负载下具有相似的性能，而在较高的负载下EDF算法在维护时态一致性方面优于RM算法；另一方面，尽管OCC协议允许更多的事务满足截止期，但是在维护时态一致性方面不如基于锁的协议。进一步地，Xiong等XIO96,XIO96b提出了数据截止期（Data-deadline）与时间认知的强迫等待（Forced Wait）的策略。由于事务存取的数据具有时态一致性需求，使得事务隐含地得到了数据截止期；如果一个事务所要访问的某项数据已经过时，则能够采用强迫等待方法推迟事务的执行直到这个数据项的新版本出现，或者利用数据相似性继续执行。研究表明，在调度事务时如果只考虑事务的数据截止期，性能具有一定的改进，而如果进一步结合强迫等待策略，则性能会有很大提高。当不采用强迫等待而利用数据相似性时，系统性能也有很大的提高，但是两种同时使用时，数据相似性没有明显地影响系统性能。5基于反馈控制的事务调度由于实时数据库越来越多地应用到开放与不可预测的环境中，特别是实时事务的执行时间与数据需求通常是不确定的，因此，一些自适应的算法被提出并应用到实时数据库中的许多方面，包括调度算法、索引机制以及内存管理等。最初，Haritsa等HAR91b给出了两种基于反馈机制的调度算法自适应的最早截止期（AED：Adaptive Earliest Deadline）与层次最早截止期（HED：Hierarchical Earliest Deadline）调度算法，这两种算法被用于固定截止期实时数据库环境中稳定EDF算法在过载情况下的性能降级。仿真实验的结果表明，AED与HED算法都具有很好的综合性能。尽管AED与HED算法能够通过连续的反馈提供一定的自适应性，但是参数调整公式都是经验式的，不能够根据系统中的负载与应用环境自动进行调整。Goyal等GOY95通过实验发现B-link算法能通过增加负载控制机制而改进性能，因此提出了LAB-link（Load Adaptive B-link）算法，其中采用的机制类似与AED算法，利用反馈机制监视系统资源的利用率，如果瓶颈资源的利用率超过MaxUtil，则拒绝新的事