基于替代补偿的实时事务调度算法研究

张超钦，马江涛

ZHANG Chao-qin 1, MA Jiang-tao 2

（1. 郑州轻工业学院 计算机通信与工程学院，郑州 450002；2. 郑州轻工业学院 国际教育学院，郑州 450002）

0 引言

根据嵌入式实时数据库系统及其事务特点，以及替代的实时事务模型的特性和可调度性特征来研究它的调度算法。一方面，替代的资源需求集是事务资源需求集的子集，系统只需满足子集就能执行该事务；另一方面，即使某个替代失败，还可能调度其它替代而不是立即夭折该事务，提高了事务的成功率。但是，还有一个问题不容忽视：在嵌入式实时数据库系统中，有些实时事务对外部环境作出即时反应，在它提交之前就有可能启动各种外部活动，对外部环境产生了影响，当该事务夭折时，无法通过传统意义下的“还原”（undo）来消除它所产生的影响，这就需要由“补偿”事务来完成这个任务[1]。

1 补偿任务的调度时机

替代是实时调度和并发控制的基本单位，使实时事务调度具有二重性，分为内部调度和外部调度。当内部调度的结果为空集时，该实时事务不可调度；当实时事务执行失败时，不能立即夭折，必须重新转入内部调度，直到当下列情况之一时才停止调度活动：事务截止期到；由特殊操作强制停止；该事务的所有功能替代集经内部调度后可调度集均为空；有一个功能替代集成功执行而提交处理[2]。

替代失败后，如果该替代是可补偿的，则系统会执行相应的补偿任务，因此，下面情况之一发生时意味着事务完成了执行：主任务(替代)成功完成，该事务成功提交；或主任务(所有替代)不成功但其补偿任务完成，该事务安全地结束。

根据执行补偿的时机，补偿行为分为立即补偿和延迟补偿，而延迟补偿又可以分为事务内补偿和事务外补偿。

1.1 立即补偿

立即补偿指在替代失败后立即调度补偿任务，在消除了该替代的影响后再执行其它替代，立即补偿使用于某些必须立即消除影响的场合。如图1.1给出了立即补偿的实时事务调度方式。

图1 立即补偿的实时事务调度

延迟补偿指某替代失败后，直接执行其他替代，在合适的时机执行补偿，这样有利于将CPU优先分配给替代，尽快执行替代，提高事务成功率。延迟补偿又可分为事务内补偿和事务外补偿两种方式。

1.2 延迟补偿——事务内补偿

事务内补偿指在某替代失败后暂时不执行补偿，在该事务提交前补偿。为了说明这个问题，我们将“End”操作提炼出来，事务在结束运行时，有一个“End”操作，在“End”之后才提交。事务内补偿意味着某替代失败后继续执行其它替代，一直到该事务成功或失败时才一次性执行所有补偿任务[3]。如图2给出了事务内补偿的调度方式。

图2 事务内补偿的实时事务调度

1.3 延迟补偿——事务外补偿

事务外补偿指在该事务提交或夭折后执行所有的补偿，执行补偿时对应的事务是成功的。这种补偿似乎与前面所说的补偿含义有矛盾，前面的讨论指出，事务要么安全结束(补偿)，要么成功提交，不可能存在提交后还需要补偿。问题的关键在于实时事务的多替代，实时事务T的一个替代成功执行，则T可提交，但是在此替代前可能有其它替代已经执行但失败，这些失败的替代是需要补偿的。为了保证事务的截止期，优先提交已成功完成的事务，提交后再执行该事务失败替代对应的补偿任务。也可以在处理夭折后再进行补偿[4]。如图3给出了事务外补偿的调度方式。

事务外补偿方法又可以分为以下4种：

1）事务提交后立即补偿。事务提交处理完毕立即对该事务所有失败且可补偿的替代进行补偿。

2）截止期处补偿。调度补偿任务从截止期开始执行，事务在系统中的保留时间较短，夭折的主任务浪费系统资源(CPU)的机会更少。

3）临界点处补偿。调度补偿任务从临界点开始执行，事务在系统中保留到超过截止期,有机会获得降低的价值，虽其事务价值由可能小于事务在截止期之前提交的价值，但依然大于在截止期处安全结束时的价值。

4）临界点后补偿。调度补偿任务在临界点后开始执行，事务T在临界点后提交，将带给系统负的价值，系统损失的实际价值取决于事务距离截止期多远。事务完成(提交或安全结束)的时间部分依赖于相关补偿任务的调度[5]。

图3 事务外补偿的实时事务调度

2 支持替代/补偿的实时事务调度策略

类似于主任务，补偿任务的调度基于优先级，补偿任务优先级分派策略有以下几种：

1）优先级继承策略。补偿任务继承主任务的优先级。

2）最早触发最优先。将最高优先级指派给具有最早触发时间的补偿任务。

3）截止期最早最优先。具有最早截止期者优先级最高。

4）价值最高者最优先。优先调度规避价值高的补偿任务。

调度支持替代/补偿的实时事务时需遵循以下两个原则：

1）补偿任务优先原则。系统优先执行补偿任务，只有当所有补偿任务都完成时才执行主任务。

2）不可抢占原则。补偿任务在执行过程中不可被抢占。

在实现调度时，系统将主任务和补偿任务分别放置在不同的队列中，只有补偿任务队列为空时才调度主任务队列中的成员运行。系统维护的主要队列有：

1）补偿任务就绪队列CRQ。由就绪的补偿任务组成，它们被失败的替代触发。

2）补偿任务等待队列CWQ。由与CRQ冲突的补偿任务组成，它们被失败的替代触发。

3）主任务就绪队列MRQ。由就绪的主任务组成。

4）主任务等待队列MWQ。由与MRQ中成员冲突的主任务组成。

当CRQ中有补偿任务结束时，释放相关的锁，CWQ中解除阻碍的成员进入CRQ，只有补偿任务队列CRQ和CWQ为空时才调度主任务执行[6]。调度时机不同其调度算法有些许区别。

3 仿真与结论

本文以开源嵌入式实时数据库系统——Berkeley DB为基础，对它的事务子系统模块进行了模拟，采用本文的算法予以实现，并进行了对比分析。Berkeley DB由五个主要的子系统构成.包括： 存取管理子系统、内存池管理子系统、事务子系统、锁子系统以及日志子系统。其中存取管理子系统作为Berkeley DB数据库进程包内部核心组件，而其他子系统都存在于Berkeley DB数据库进程包的外部。每个子系统支持不同的应用级别。事务（Transaction）子系统为Berkeley DB提供事务管理功能。它允许把一组对数据库的修改看作一个原子单位，这组操作要么全做，要么全不做。在默认的情况下，系统将提供严格的ACID事务属性，但是应用程序可以选择不使用系统所作的隔离保证。该子系统使用两段锁技术和先写日志策略来保证数据库数据的正确性和一致性。它也可以被应用程序单独使用来对其自身的数据更新进行事务保护。事务子系统适用于需要事务保证数据的修改的应用[7]。

本实验按照立即补偿的调度算法, 事务内补偿的调度算法, 事务外补偿的调度算法来设计事务子系统的实时调度，就调度的事务进行对比， 依次完成插入100、1000、10000、100000条记录的事务。使用此3种算法做比较，结果如图4所示。

从图4可以看出：立即补偿的调度算法, 事务内补偿的调度算法, 事务外补偿的调度算法的性能依次提高。延迟调度算法要比立即补偿性能稍高。

结果表明：1）实时数据库事务子系统中，某些事务故障时，即使某个替代失败，还可能调度其它替代而不是立即夭折该事务，立即补偿和延迟补偿是可行的，提高了事务的成功率。2）在事务调度中延迟调度算法要比立即补偿性能稍高。3）设计实时数据库事务子系统的关键是替代、补偿的实时事务调度，系统并行处理能力，事务的实时性要求等。随着更多的实时应用需要实时数据库的高可靠性及反应时间可预测性，将另文探讨这方面的工作。

图4 算法性能比较

[1]Young-Kuk Kim、Sang H.Son,Supporting Predictability for Real-Time Database Systems[J],Proceedings of the 2nd IEEE Real-Time Technology and Applications Symposium,1996：122-133.

[2]SKYTJ、JENSEN C.S.,A foundation for vacuuming temporal database[J],Data and Knowledge Engineering,2003.44(1)：1-29.

[3]TANSEL A、CLIFFORD J、GADIA J S. et al,Temporald atabases：theory,design,and implementation.Database Systems and Applications eries[M],Benjamin/Cummings,1993.

[4]Young-Kuk Kim and Sang H.Son,An approsh toward predi catable Real-time transaction Processing,In Proceedings of the 5th Euromicro Workshop on Real-time Systems,Oulu,Finland,June 1993.

[5]Peter Puschner and Anton Schedl.Computing Maximum Task Execution Times -A Graph-Based Approach.Journal of Real-Time Systems,1997,13(1)：67-91.

[6]Peter Puschner and Anton Schedl.A Tool for the Computation of Worst Case Task Execution Times.In Proc.5th Euromicro Workshop on Real-Time Systems,1993,6：224-229.

[7]Haritsa J R、Carey M J、Linvy M. On bing optimistic about real—time constraints [C],Prnc of the 1990 ACM PODS Symposium,1990,4.