［返回］
计算机世界1999年第40期
刘云生 李国徽 卢炎生
实时事务模型
1 ．系统模型与传统数据库系统相类似，实时数据库系统的操作也是以事务的形式出现。事务就是包含在BEGIN/COMMIT/ABORT 之间的操作序列。系统以事务为单位分配CPU、数据等资源，进行优先级的分配、调度处理等。
实时数据库系统中的事务与传统事务有很大的不同，其事务可以有定时限制（典型地为截止期），系统追求的目标不是系统的吞吐量，而是单个事务定时限制的满足，以使满足定时限制的事务比率最大；传统事务的原子性、一致性、隔离性及永久性在实时环境下变得太严格或不可能；要求采用" 识时" 机制来处理事务的调度或并发控制，而不是传统的先来先服务方式。
2 ．结构模型
传统数据库中事务就是一个平坦的操作序列，事务的执行要么顺利执行到提交，要么夭折而不在系统的任何部分留有痕迹。在实时应用环境下则不同：
* 应用语义有时显式地要求结构上的一个事务为另一个事务的子事务。例如，在CAD 工程中，一个工程事务划分成若干个设计事务，而每一设计事务又可分成若干个子任务而分配给各设计者。
* 实时应用中被触发的活动依应用要求可以是触发它的事务的子事务。在过程控制、自动化等领域这种情形很普遍。
* 在分布式应用环境中，一个事务可能要分出若干在不同节点上执行的代理事务，它们分工合作且都作为原事务的子事务。
* 在工程应用中，普遍存在长寿事务或开端事务。这种事务会造成系统资源需求的瓶颈。为此，可将这种事务划分成若干逻辑相对独立的子事务，以便当其结束时能提前释放占用的资源。
所以，实时应用要求系统提供事务嵌套机制。包含其他事务的事务称为" 父事务"，被包含的事务称为" 子事务"，没有父事务的事务为" 根事务"。事务之间可以形成嵌套关系。
实时事务的特征
1 ．定时性
实时应用中事务的定时性来源于两方面：一是外部环境显式给出的反应时间要求，如截止期等；二是由于系统中的数据随时间变化而转嫁来的。
定时性包括了两方面的含义：
定时限制事务的执行具有显式的时限，如期限、截止时间等。这是由于控制系统要随时紧紧地跟踪被控系统而引起的，它要求RTDB 必须有时间处理机构。时限还可有软硬之分。
定时正确性事务能按合适的时间要求正确执行。这是由于要求数据对于控制系统的各种决策活动随时有效而引起的，它要求权衡定时限制与数据一致性等多方面因素，提供合适的调度算法。
实时事务有不同的定时限制，其中最重要的有：
截止时间实时事务完成的最后期限。它可以有硬、软之分，具有硬截止时间的事务（称为硬实时事务），必须在其截止时间以前完成，否则将带来灾难性的后果，故到达其截止时间还不能完成的硬实时事务必须夭折。具有软截止时间的事务（称为软实时事务），应该在其截止期完成，但超过其截止时间也还有一定意义（尽管不断下降），故软实时事务到达其截止时间后不必立即夭折它。
到达时间事务在系统中生成的时间。它可以是可预报的，也可以是不可预报的。可预报的到达时间可显式地给出或者作为一个导出函数，如周期事务的到达时间是可预报的。不可预报的到达时间是指当相应事务到达系统时才能知道，非周期事务的到达时间就是不可预报的。
期望执行时间估算的最坏情况执行时间。由于各种不可预报性因素，它很难做到准确，估算的最坏情况执行时间可能与实际情况相差很大。然而，为了合理地得到事务的截止时间及适当地调度以使其满足，又必须事先较准确地估算其执行时间。
2 ．语义相关性
实时数据库事务之间存在着各种关系，包括结构关系、数据与通信关系、时间关系等，这些关系带来了事务间的各种相关性。
(1) 结构相关
它来自于复杂事务模型的结构特征，用来建模复杂事务内部并发事务行为的一种约束。不同的复杂事务模型有不同的结构相关性，但它们可以通过事务间的" 执行依赖性" 来定义，实时嵌套事务中基本的事务依赖有：
* 子事务对父事务的开始依赖（BD）：子事务开始前父事务已经开始；
* 父事务对子事务的提交依赖(CD）：父事务提交前子事务已经结束（提交或夭折）；
* 子事务对父事务的夭折依赖（AD）：父事务夭折则子事务一定夭折。
(2) 数据相关
数据相关就是不同事务间的共享数据联系，但此" 共享" 概念比传统的具有更广的意义：实时嵌套事务中的子事务共享父事务数据，子事务提交时其对数据库的更改委托给父事务，只有父事务提交时才能真正地写入数据库。
(3) 功能替代/ 结果补偿
一个实时应用常常由若干任务组成，而一个任务有时可以通过不同途径来实现。一个应用建模为一个事务，一个任务则建模为一组功能等价的子事务，称为该任务的替代集。若一个任务的替代集中的子事务之一能成功执行，则该任务是可完成的。若对应一个事务的所有任务可完成，则该事务是成功的（可提交）。功能替代导致了事务执行路径的不确定性，即一个事务成功执行的路径依赖于执行过程中（子事务）失败的发生，且即使某些子事务失败了，事务仍可能顺利提交。这还体现了实时事务的健壮性，即有的事务（任务）不能失败。
由于前面所述的事务的结构复杂性和功能替代性，因此，事务的执行经历不确定，一个子事务的执行直到提交时还不能确定它是否需要。若一个（子）事务提交后，发现它是不需要的，该怎么办？另一方面，一个实时事务可以物理改变现实世界的状态，换句话说，事务可以启动各种活动，这些活动在它提交前就已经影响了现实世界，因而当这种事务夭折时，不能进行传统意义下的" 还原"（Undo）。于是需要一种" 补偿" 活动来抵消它所有的影响，这种补偿活动也是事务。对于一个（子）事务，若存在能抵消它提交后所产生的所有影响的（子）事务，则称其为是可补偿的，否则是不可补偿的。当然，不是每一个（子）事务都是可补偿的，不可补偿的（子）事务在知道它确实是需要的以前，一定不能提交。
实时事务分类
实时事务可以从不同的侧面进行分类。
1 ．按关键性分类
也就是按事务时限（截止期）的性质，即事务超截止期对系统带来的影响分类。而这种时限的性质可以很好地用价值函数来建模，于是我们有：
硬（截止期/ 实时）事务超截止期会导致恶果（价值函数取大且可能不断增加的负值）。它对应于安全危急性活动。
软（截止期/ 实时）事务超截止期仍有一定的价值，且价值不断下降，直到某一时刻（称为最终有效时间）降到零，此后保持为零（不会为负）。
固（截止期/ 实时）事务一旦到达截止时间，其价值立即降为零，此后固定为零（也不会为负）。显然，它是软实时事务在最终有效时间与截止时间重合情况的特例。
2 ．按功能分类
一个实时数据库系统以两种方式直接与现实世界交互作用，一是关于现实世界状态或事件的信息被记录到数据库中，二是事务可以启动各种影响现实世界的活动。这就给予我们一种如下事务分类：
数据接收事务记录现实世界的状态或发生的事件到数据库中。它是简单的只写事务；为了保持数据库的" 外部一致" 和跟踪记录，它应是短的、周期的，且应是被立即执行（不能等待和阻塞）的硬实时事务。为了保证其定时限制的满足，它可能会引起对数据库一致性的破坏。
数据处理事务类似传统数据库的事务。它用来恢复已违反了一致性（可能由于数据接收事务的结果）的数据库的状态。这种事务可看作维护正常运行的监控器，它可能是" 长寿" 的。
控制事务引起现实世界中有关活动的执行。像数据接收事务一样，这种事务是很短的，尽管所引起的现实活动可能要执行很长时间。它通常也是硬实时的。这种事务还可以作为数据处理事务的子事务而被调用，而它本身也可以触发子事务，比如以一子事务来检测所引起的现实活动。
实时事务的正确性
1 ．正确性概念及内涵实时事务与传统事务的本质区别就在于其有定时限制，因此，事务处理必须同时满足一致性要求和定时限制。虽然实时事务的正确性与传统事务一样，也包括数据库状态正确性和事务执行正确性两个方面，但其含义与内容有很大的不同。数据库状态正确性包含内部一致和时间一致，事务执行正确性则包含其结果正确性、行为正确性、结构正确性和时间正确性。
2 ．正确性标准
传统数据库中的原子性和可串行化包含了事务正确性的所有概念。而实时嵌套事务正确性的内容更为丰富，实现的手段也就更为复杂。传统可串行化标准在实时环境下太严格或不适合，限制了系统中事务执行的并发度，对于满足事务定时限制是不利的。我们开发了一种新颖的准一致性可串行化并发控制策略，事务执行给系统带来的不一致被限定在一定的范围内，并在一定的时机恢复数据库到一致状态。而实时事务的时间正确性需要" 识时" 协议实现，结构正确性需要事务管理检查事务间的结构相关性来实现。
实时事务处理
1 ．实时事务优先级分配
实时事务的调度和并发控制都是基于事务的优先级进行的，因此，如何分配事务的优先级是一个重要的问题。
常见的事务优先级分配算法有以下几种：
最早放行最优先（Earliest Release First）该策略将最高优先级指派给具有最早" 放行"（Release）时间的事务。所谓放行时间就是事务可以开始执行的最早时间，与此相联的有事务到达（Arrive）时间、事务接纳（Admission）时间。
截止期最早最优先（Earliest Deadline First）即具有最早截止期者优先级最高。
可达截止期最早最优先（Earliest Feasible Deadline First）具有最早的可达截止期者优先级最高。所谓一个事务t 的截止期是当前时间" 可达到" 的，乃指τ＋（E －P）≤d。这里τ为当前时间，E、P 分别为事务T 的执行时间估算和已执行时间，d 为其截止期。
空余时间最短最优先（Least Slack First）事务t 的空余时间S=d －（τ＋E －P），即推迟T 的执行而仍然满足其截止期的可推迟时间量估算。
价值最高最优先（Highest Value First）每一事务都有一价值函数，其值最大者最优先。问题是如何合理地构造价值函数，一个例子是：
V（t）=c（w1（τ－τS）－w2d ＋w3P －w4S）
其中τ、d、P、S 的意义同上，c、τs 分别为t 的危急度、开始时间，wi 为加权因子。
价值密度最大最优先（Greatest
Value Density First）价值密度函数为：
即事务完成时的期望价值与实现该价值所需计算量的比最大者优先级最高。显然，对于期望价值一样的事务，该策略偏向较短者，因为它每单位消耗时间所获得的价值更大。与上面的HVF 策略一样，这里也有如何设计价值函数的问题。
2 ．实时事务并发控制和调度
在实时应用环境中，如果处理不当，可能造成" 优先级颠倒"，即优先级高的事务等待优先级低的事务，这对实现事务的定时限制是不利的。为此，我们提出了以下几种改进方案：
(1) 优先级继承
优先级继承的基本思想是：当发生优先级颠倒时，将占有者tH 的优先级提高到与tR 的一样（即继承tR 的优先级），tH 继续执行直到结束（提交或夭折）。在tH 因某种原因（如成为死锁的牺牲者）而重启动时，它恢复原来的优先级。让tH 继承tR 优先级是为了让它尽快完成，因为tH 的进展也意味着tR 的进展。这种策略称为优先继承（PI）。
(2) 高优先级夭折
这种策略的思想是，当发生优先级颠倒时，夭折低优先级的tH 而让高优先级的tR 执行。该策略称" 高优先" 法（HP）。
这种策略可以消除死锁，但它的问题是：
* 对那些已执行时间很长而还需执行的时间已很短的tH，夭折的代价很大。尤其是当dH（截止时间）－ct（当前时间）与tH 的" 剩余执行时间估算"el(tH) 相差不大时，重启动必然导致其超截止时间，而且浪费大量系统资源，使整个系统性能下降。
* 若采用像LSF 这样的动态优先级分配策略，则被夭折而重启动的tH 可能马上会有比tR 更高的优先级。为此，当重启动的tH 再次与tR 冲突时，tR 可能又被tH 夭折，这样就导致循环夭折。
为了解决上述两个问题，人们提出了不同的改进策略，在此限于篇幅不再详细叙述。