实时事务调度策略及实现

7　事务调度策略

与两级并发控制相对应，在支持替代的嵌入式实时数据库系统中，替代成为了调度的基本单位，由此，实时事务调度应分为对替代的调度和对事务的调度。

根据替代之间的性能差异，对该事务的所有可调度的替代做出调度，此调度有别于传统的实时事务调度，称为内部调度。内部调度的目的是在一个实时事务中选取最佳的替代，它实际上包括预分析和预调度两部分。外部调度对应于传统的实时事务调度，针对于多个实时事务，目的是在多个实时事务中分配系统资源（包括CPU、数据对象等）。

7.1　替代的优先级分派

内部调度的目标是选取受阻的可能性最小、造成资源阻塞的可能性最小、成功率最高的替代参与外部调度，以最小的系统代价提高外部调度的成功率。

与外部调度相似，内部调度基于替代的优先级，根据替代的特性，典型的优先级分派策略有如下几种：

（1）适应能力最强者优先

最能符合系统当前运行状态的替代与其他事务发生资源冲突的可能性最小、成功率最高，系统将最高优先级赋予它。从理论上说，确实存在这样的替代，但是，由于系统运行的动态性，最适应系统环境的替代不是一成不变的，准确确定最佳替代需要时时检测系统状态，花费大量时间，会严重降低系统性能。

具体来说，基于以下原因，难以寻找这个最佳替代：

①有时难以及时确定系统的运行状态。

②系统运行状态分析需要动态进行，花费大量的CPU时间，延长了事务的执行时间，间接造成阻塞。

既然确定各项指标都最佳的替代几乎不可能，只能退而求其次，系统分别从不同的指标考察替代，得到以下策略。

（2）运行时间最短优先

由于有内存数据库支持，不确定的因素减少，使估算事务执行时间成为可能，我们可以确定各个替代的估算执行时间，根据替代的执行时间为替代分派优先级，估算执行时间最短的替代将获得最高优先级。

此策略的优点是：

①有利于各事务以最短的路径执行，尽可能少地占用CPU时间，尽可能快地释放占用的系统资源，减少阻塞机会。

②执行时间最短空余时间就最长，成功的机会会更多。

③即使运行失败，将发现错误的时间尽可能提早，将有较多的时间重新调度该事务的其他替代。

（3）资源需求最少者优先

较多的资源需求蕴涵着较强的资源竞争和较多的受阻机会，从而导致因资源等待而超过截止期的机会增大；将最高优先级赋予资源需求最少的替代，有利于减少资源冲突的机会。

替代的资源需求信息在事务预分析中得到，由于事务处理的资源冲突集中在存取的数据对象上，系统将重点分析替代在数据资源上的需求，在嵌入式实时数据库系统中，锁的力度是表，而且，在高速CPU处理的支持下，可以忽视对同一个表的访问次数，即：对表的多次访问在资源需求分析中不重复记数，因而资源需求比较实际上是比较不同替代访问表的个数。花费的时间短，则可操作性强。

（4）加权平衡优先

该策略综合考虑多方面的因素，通过构造一个优先级函数来分派优先级，比如：

P（FTi）＝α1eti＋α2Ri/R＋α3NE）/（α1＋α2＋α3）

其中，α1、α2、α3是权值，NE是FTi的嵌套层次。

7.2　事务的二重调度策略与实现

设有实时事务集TS＝｛Ti｜1≤i≤m｝，Ti＝｛fxij｜1≤j≤D（GTi）｝，用Schrin和Schrex分别表示内部调度和外部调度，则：

对于事务Ti的一个内部调度：

Schrin（Ti）＝（fxiq1，fxiq2，…，fxiqc，…，fxiqp），fxiq1∈Ti，1≤qp≤Dg （GTi）

对应的一个外部调度分别为：

Schrex（TT）＝scheduling（Schrin（T1），Schrin（T2），…，Schrin （Ti），…，Schrin（Tm））

按照一个事务内的多个替代是否可以并发执行，外部调度分别为：

①在一个事务内不允许多个替代并发执行时，对应的外部调度是：

Schrex（TT）＝（fxk1q1，fxk2q2，…，fxkiqi，…，fxkmqm）

满足条件：

Aki，qi，fxkiqi∈Schrex（TT）E｜j（fxkiqi∈Schrin（Tj））

②在一个事务内允许多个替代并发执行时，对应的外部调度是：

Schrex（TT）＝（fxk1q1，fxk2q2，…，fxkiqi，…，fxksqy）ks≥m，qy≤max（GTi）

满足条件：

内部调度与外部调度紧密联系，内部调度是基础，只有通过内部调度才能选出可调度的替代参与外部调度，外部调度是最终目的，只有通过外部调度，实时事务才能真正投入执行。

如图7．1所示，当内部调度的结果为空集时，该实时事务不可调度，当事务执行失败时，不能立即夭折，必须重新转入内部调度。停止调度活动的原因有：

①事务的截止期已到；

②由特殊操作强迫停止；

③该事务的所有替代都夭折；

图7.1　实时事务调度

④有一个替代成功执行并提交。

系统调度时，首先从强调度树中选取一个（或多个）对象，若无强调度树，则从弱调度树中选取一个对象。在软实时环境下，若无强调度树和弱调度树，有可能从普通调度树中选取一个对象。调度算法形式说明如下：

Choice（hh1，hh2，hh3）

输入：Ss（T）——T的强调度树集，Sw（T）——T的弱调度树集，

输出：实时事务T的一个替代ob

步骤：

7.3　基于系统收益的可抢占调度策略

毋庸置疑，有效的实时调度需要考虑事务的执行时间，通常的做法是估算事务的最坏执行时间WCET，记做ts（即tstatic），它是事务在孤立环境下所需要的执行时间，在不同的系统负载下，事务花费在因并发而等待以及重启上的时间是不同的，即事务的实际执行时间是依据系统负载而定的一个动态值，记做td（即tdynamic）。

前面的有关章节中已经介绍了利用灰色系统理论分析在不同系统环境下事务动态执行时间的估算方法，这里，我们将系统的负载因子直接与事务的动态执行时间联系在一起，确定具有特定静态执行时间的事务在不同的系统负载下的动态执行时间。

虽然很难确定td的准确值，但其近似值依然有助于提高调度性能，已经有一些计算系统负载因子的方法，基本思想是根据经验值进行推算，我们根据事务的当前状况确定系统负载，结果更加精确。

定义7．1：事务的有效执行时间是事务已经花费在其对象操作和事务操作上的时间，不包含因并发而等待和重启的时间，记做te。

事务Ti的剩余执行时间rti为：rti＝tsi－tei

设系统中就绪事务集合为TR＝｛Ti1＜i＜n｝，则系统负载因子LF：

td＝LF＊ts

在优先级分派时，用td替代ts可以提高调度的准确性，为了尽力保证硬实时事务成功执行，除了考虑系统负载外，还需要考虑事务的性质。用一个参数描述事务的时限特性，称为事务的时限因子β，根据应用需求或经验分别为硬实时事务、固实时事务、软实时事务和非实时事务设定不同的β值，这样，事务Ti的优先级分配函数为：

Pi＝－（Di＋LF＊tsi）＊βi

每当一个事务到达和结束，系统都修改LF，调整有关事务的优先级。

7.3.1　系统收益计算

系统得到的收益就是系统中所有事务给系统带来的价值总和，设系统中就绪事务集为TR，在新的紧急事务Ti到达时，系统近期可能得到的收益为：

定义7．2：事务Ti的动态冲突集Tcsi定义为：Tcsi＝｛Tj｜TjTR，com （Ti，Tj）｝

为了使系统收益最大化，当然希望在不影响Tcsi成功执行的前提下，Ti也能成功执行，如图7．2所示。如果在Tcsi成功执行后仍然能完全执行Ti，则系统的总收益最大，这样，让Tcsi继承Ti的优先级，以此高优先级运行，避免了回滚造成的资源浪费。

图7.2　优先级继承示意图

在新事务Ti到达时，事务Tj的剩余执行时间为：esj＝LF＊rtj

事务Ti的空余时间为：ssti＝Di－t0－tsi＊LF

当下列条件成立时，事务Ti的空余时间足够执行Tj（Tj∈Tcsi），可以实现优先级继承。

当条件1不成立时，Tcsi中的某些事务可能不能成功执行，需要分析抢占的代价，这又分为两种情况：

①Tcsi中有一部分事务满足条件1，它们可以继续执行，另外一部分事务必须被抢占。执行图如图7．3所示，将Tcsi中可以继续执行的事务集记为Tcci，被抢占的事务集记为Tssi，为了尽可能地保证Tcci中的事务满足其截止期，在执行完Tcci后，回滚Tssi，执行Ti后再执行Tssi，此时，Tssi中可能有些事务会超过截止期。

图7.3　抢占示意图

在图7．4中，有：

其中，thgj是回滚Tssi所需的时间。

在时间t3后，被阻塞的事务继续运行，它们带给系统的价值是不同的，可能有某些Tssi中的事务能成功执行，给系统带来正价值，可能有些事务不能在其截止期之前成功执行，如果这些事务是硬实时事务，将给系统带来负价值，如果是固实时事务，将不产生价值，如果是软实时事务，可能带来降低了的价值。对于那些可以成功执行的事务，其价值维持在截止期前的价值，也是它的最大价值，对于那些不能在截止期前成功执行的事务，其价值由价值函数决定。

在抢占后，系统可能增加的收益为：只有抢占后系统收益上升，该抢占才有意义，即抢占必须满足条件2：

②Tcsi中所有事务都不能满足条件1，全部被抢占。图7．4表示了抢占的过程，当事务Ti抢占了Tcsi中的事务时，首先使Tcsi中的事务回滚，在执行完事务Ti后，才可能继续执行Tcsi中的事务。

图7.4　抢占示意图

在图7．4中有：t1＝t0＋thgj＊LF

t2＝t0＋thgj＊LF＋eti＊LF在抢占后，系统可能增加的收益为：

同样，只有当抢占后带给系统的总收益更大，该抢占才是有意义的。

即：该抢占应满足条件3：

7.3.2　调度算法

当一个高优先级事务Ti到来，如果存在Ti的动态冲突集Tcsi，则系统根据不同的情形采取不同的策略：

①优先级继承策略。如果有足够的时间完全执行Ti和Tcsi，则系统使Tcsi继承Ti的优先级，以此高优先级执行。

②抢占策略。当时间不允许全部按时执行Ti和Tcsi，系统衡量抢占代价，只有抢占能给系统带来更大的收益，才实施抢占。

基于系统收益的冲突解决过程如下：

7.4　存取时态数据的事务调度策略

7.4.1　实时事务对时态数据的操作

事务的优先级根据其截止期和所访问时态数据对象的时间约束来决定，被事务读的数据必须在该事务完成时是有效的，这就导致在完成时间上除了事务截止期外还有另外的约束——数据截止期，当所调度的事务的数据截止期小于事务截止期时，调度算法将考虑数据截止期。

图7.5　数据截止期的解释

在图7．5中，事务T要读两个时态数据对象Y和Z，T分别在时间t2和t3读它们。T的截止期是t6，数据Y在区间［t0，t5］有效，Z在区间［t0，t4］有效。T开始于t1，在此时没有数据截止期，在时间t2，T读数据Y，T的数据截止期变成t5，为了满足时态一致性，T必须在时间t5之前被调度提交。

注意：T的截止期比t5晚。下一步，T处理并读Z（Z在时间t4无效），现在，T的数据截止期调整为时间t4，在t4，T没有完成，于是它夭折。

注意：可能重启T并用Y和Z的后续版本满足截止期t6。

7.4.2　基于执行截止期的调度算法

涉及的事务T的有关属性如下：

bt（T）：T的开始时间；

dd（t）：T在时间t的数据截止期；

Rt（T）：T在时间t的估算剩余响应时间；（T）：T在时间t的读集，该集合包含了所有被T读的时态数据对象的版本。

对于读取时态数据d（value，＜tbi，tei＞）的实时事务T而言，T不仅要满足本身的截止期要求，而且要满足d（value，＜tbi，tei＞）的时间要求，即：在T提交前确保d（value，＜tbi，tei＞）没有被更改，处于其有效期内。

T在时刻t时的数据截止期ddt（T）定义为：

其中，te（d）是时态数据对象d当前版本的截止期。

定义7．3：实时事务T的执行截止期ed（T）定义为：ed（Ti）＝min （ddt，Di）

由此，读取时态数据的实时事务需要满足执行截止期。(www.xing528.com)

在传统的最早截止期优先和最短空余时间优先调度策略中加入时态数据信息，得到如下调度策略：

①最早执行截止期优先Earliest Execution－Deadline First（EEDF）。事务的优先级与其执行截止期保持一致，执行截止期越紧的事务优先级越高。

Pt（T）＝ed（T）＝min（ddt，d（Ti））

②基于执行截止期的最小空余优先Execution－Deadline based Least Stack First（EDLSF）。事务的空余时间计算基于事务的执行截止期，空余时间越小优先级越高。

7.4.3　强制等待策略

读取时态数据di的实时事务可能在其事务截止期前因超过数据截止期而不能提交，如果该时态数据是更新型时态数据，则只要能保证不超过事务的截止期，就可强制事务等待直到di被修改，系统读取新的版本di＋1，由此，需要估算剩余执行时间和剩余响应时间。有了强制等待，事务无论何时读时态数据都会检测该事务是否会在该时态数据失效之前提交，如果在事务提交之前该数据可能失效则事务等待该数据被修改，否则事务夭折。在图7．5中，一旦T 读Z，则T的数据截止期为t4，但是如果T不能在t4之前提交则T将在t4后夭折，因为对一个事务而言，它提交时，所读的所有数据必须是有效的。代替的方法是：T可以等待到t4读Z的新版本。此方法保持了事务已经做过的工作，避免了恢复负载。

如果事务T读数据d的过程如图7．6所示，事务在时态数据的当前版本dj的截止期之前完成，则事务可以成功提交。

图7.6　事务处理时态数据示意图

如果事务T读数据d的过程如图7．7所示，事务在时态数据的当前版本dj的截止期之前不能完成，但是在其下一个版本dj＋1的截止期之前可以完成，则强制事务等待，事务在读取数据dj＋1后可以成功提交。

图7.7　事务处理时态数据示意图

如果事务T读数据d的过程如图7．8所示，事务在时态数据的当前版本dj的截止期之前不能完成，而且在其下一个版本dj＋1的截止期之前也不能完成，并且在事务截止期之前不能正确读取任何版本，则该事务夭折。

图7.8　事务处理时态数据示意图

如果事务不能在其截止期前完成，则无论数据截止期如何（见图7．9），则该事务必须夭折。

从上面的分析可以看出，强制等待应满足下列条件：

①COND7．1：（d（tej）＜t0＋rti≤d（tej＋1））＾（t0＋rti≤Di）

条件说明：从当前时间开始，如果全部CPU时间都给该事务，则必须有足够的时间使事务在其数据截止期前完成。

图7.9　事务处理时态数据示意图

②COND7．2：（d（tej）＜t0＋LF＊rti≤d（tej＋1））＾（t0＋LF＊rti≤Di）

由于系统中有多个事务并行，它们分享包括CPU在内的系统资源，事务的真实执行时间应该包含了资源等待时间，高于估算剩余执行时间，条件②加强了条件①，说明从系统当前时间开始，事务的响应时间必须在其数据截止期之内。

如图7．10所示，为实现强制等待，系统维护以下3个队列：

图7.10　调度示意图

·CPU－Queue：就绪队列，其中的成员满足条件②，能直接参与CPU调度；

·Sleep－Queue：睡眠队列，其中的成员不满足条件②但是满足条件①；

·Wait－Queue：等待队列，其中的成员不满足条件②和条件①。

如果条件②成立则事务继续，如果条件②不成立但条件①成立，则事务在Sleep－Queue中，Sleep－Queue中的事务只有在CPU空闲时才能运行，即：如果CPU－Queue中没有事务则运行Sleep－Queue中的事务。

如果条件①不成立则事务放置于Wait－Queue直到d被修改。一旦d被修改则重新检测条件。在它移到CPU－Queue（如果条件②为真）或Sleep－Queue（条件①为真但条件②为假）后，调度器将CPU－Queue中的最高优先级保持者调度运行。计算方法如下：

计算方法：FWR中的条件检测

if t＋Rt（T）≤te（X）then T continues；

else if（t＋Et（T）≤te（X））then Place T in Sleep－Quene；

else Place T in Wait－Quene；

7.4.4　相似性策略

在很多情况下，数据对象的值被修改后相差并不大，此时，事务读取的数据对象的不同版本仅仅有微小差异，不易被事务区别。相似性基于这样的思想：数据的旧版本不是当前版本，但接近于当前版本，如果对结果不造成相反的影响还可以用。两个数据对象是否相似由访问它们的事务决定。

定义7．4：针对于时态数据d，事务Ti给定一个阈值β，当d的两个版本di和di＋1满足条件｜di－di＋1｜β时，Ti认为di和di＋1是相似的。

相似性是数据对象域上的二元关系，它是自反的、对称的，但是没有必要传递。我们假设它是不能传递的。在图7．5中，一旦T读Z则T的截止期为t4，但是如果T不能在t4前提交则T在t4后夭折；然而，如果Z的版本在t4之前和之后是相似的，则T可以在t4后提交。根据相似性，只要事务错过其数据截止期但没错过事务截止期，系统就检测当前版本是否相似于它读取的版本，如果是，则其数据截止期延伸，事务继续运行而不夭折，否则，事务夭折。

显然，相似性和强制等待不是互不相关的观点，事实上，它们彼此对抗。例如，当一个事务存取的一个时态数据将失效时，强制等待策略可能决定等待下一个版本；然而，如果数据的下一个版本是相似的，等待就是不必要的。即如果事务无等待的执行，与这个数据版本相似的下一个数据版本可使事务满足其数据截止期。

是否采取强制等待策略或相似性策略，需要根据事务和数据的特性来决定。下面分析事务对具有不同时态特性的数据进行处理时可采取的措施。

设实时事务T读取时态数据D，则根据D的特性，如果事务T不能在其执行截止期前提交，但没有超过其事务截止期，则表示该事务操作不能满足所访问数据对象当前版本的有效期，即事务的数据截止期。根据数据本身的特性，分别做如下处理：

（1）d是定时更新型时态数据

由于定时更新型数据在每个周期都有新的版本，当数据d满足相似性策略条件时，可采取相似性策略，否则，如果事务T满足强制等待条件，可采取强制等待策略，重新读取数据对象的新版本，前者的代价较小，但是精确度较低。

如果数据d是定时更新型时态数据，则事务一开始就能预计是否满足其数据截止期，进而决定采取相应的对策，决策的时机是最早的，最大程度地减少了资源浪费。

（2）d是定时终结型时态数据

由于数据d在其截止期后无新的版本，并且事务T提交时数据d已无效，事务T对数据d所做的任何操作在事务提交时都无效，因此，事务T必须夭折。

如果数据d是定时终结型时态数据，事务在开始时也能预计其数据截止期，发现不能满足其数据截止期要求时，系统不让该事务开始，最大程度减少资源浪费。

（3）d是非定时更新型时态数据

与第一种情况相似，如果数据d满足相似性条件，则可采取相似性策略，但是，由于事务T无法预计d当前版本的截止期，不能采取强制等待策略。

如果数据d是非定时更新型时态数据，事务T开始时不能预计数据d当前版本的截止期，只有当d被修改时才通知事务T做相应的处理；万一该事务既不能满足其数据截止期，读d的新版本后又不能满足其事务截止期，则该事务只能夭折，由于决策的滞后，在一定程度上浪费了系统资源。

（4）d是非定时终结型时态数据

如果数据d是非定时终结型时态数据，事务开始时不能预知数据d的截止期，只有当d的截止期到来时才通知事务T，由于d再没有新的数据版本，T所做的关于d的操作都无效，T必须夭折。

7.5　补偿任务调度

如前所述，在嵌入式实时数据库系统中，实时事务在提交前就有可能对外部环境造成一定的影响，一旦事务夭折，这种影响必须依赖于相应的补偿任务才能消除。并非所有事务都是可补偿的，但是，对于可补偿事务而言，要么成功提交，要么主任务失败得到及时补偿，当下面两个情况之一发生时，事务被认为完成了执行：

①主任务完成，该事务成功提交；

②主任务不成功但其补偿任务完成，该事务安全地结束。

一个已提交事务给系统带来正面的效益，但是一个安全结束的事务不给系统带来效益。

图7.11　实时事务示意图

通常，主任务到达临界点时，事务继续执行不再给系统带来效益，该事务必须夭折，面临补偿问题。图7．11表示了各种实时事务的执行与其效益的关系，对于硬实时事务，其截止期也是临界点；软实时事务的临界点滞后于截止期，事务待到截止期后其效益下降，但是继续执行依然可以带来正效益，因此，在其截止期处不一定夭折该事务，如果让它继续执行，则其夭折点必定在其截止期后，补偿任务也可以在其截止期后；固实时事务的截止期和临界点在同一时刻，但是临界点后，不会给系统带来负面影响。根据补偿的时机不同，补偿任务的调度策略典型的有以下三种：

策略1：调度补偿任务从Di开始执行。采用该策略，成功的主任务将在截止期前提交，带给系统最大价值，否则，补偿任务从截止期Di处开始执行，这样，事务在系统中的保留时间较短，夭折的主任务浪费系统资源（CPU）的机会更少。

策略2：调度补偿任务从Zi开始执行。采用该策略，主任务在系统中保留到超过截止期，有机会获得降低的价值，补偿任务从Zi开始执行，虽然该价值小于事务在截止期之前提交的价值，但依然大于在截止期处安全结束时的价值。

策略3：调度补偿任务在Zi后开始执行。采用该策略，事务T在Zi后提交，将带给系统负的价值，系统损失的实际价值取决于事务距离截止期的远近。事务完成（提交或安全结束）的时间部分依赖于相关补偿任务的调度。

针对于事务T，这似乎是不可思议的，因为它带给系统的价值是负值。但是从全局看，设系统中的事务集为TS，则从这些事务中，系统得到的总价值为：。补偿任务与其他事务一起，按优先级排队，竞争CPU，某事务不能及时补偿确实获得了负价值，但是，系统优先执行能够带给系统高效益的其他事务的主任务，所带来的正效益足够补偿该损失，即系统宁愿优先执行高价值的主任务使它们成功提交，也好于执行低价值事务的补偿任务。

针对于不同的实时事务，其补偿任务的调度策略有所不同：

①硬实时事务的补偿事务调度。当事务具有硬截止期，该事务必须成功提交或在截止期前安全结束（由于错过截止期会导致系统所禁止的损失），在这种情况下，补偿任务的调度是相对直接的。我们试图调度每个补偿任务最及时地开始执行，以便给相应的主任务尽可能多的执行时间。在硬截止期系统中补偿任务具有比主任务更高的优先级，并且既然所有硬实时事务要么按时提交要么安全结束，所以该补偿任务不能被抢占。

②软实时事务的补偿任务调度。软实时事务有可能超过截止期完成（提交或结束），它使补偿任务的调度更加困难。补偿任务不必要具有比主任务更高的优先级，还可能被抢占。性能指标变为已提交事务带给系统的价值，而不管这些事务是否在其截止期之前提交。

③固实时事务的补偿任务调度。固实时事务超过截止期后其价值为0，但并不会给系统带来负面影响，所以，可以在截止期以后的任何时候执行补偿任务。

补偿的效果往往与补偿任务的执行事件有关，比如，一个事务在执行过程中触发了一个加热开关，当该事务失败不能提交时，补偿任务关闭此开关，加热效果与关闭开关的时间有关。

如果补偿在某特定时间后无意义，称之为硬补偿，记为HC；如果补偿在特定时间后效果下降，称之为软补偿，记为SC；

如果补偿效果与时间无关，称为常态补偿，记为UC。

与主任务不同的是：补偿任务不会带来负效益。

构造补偿任务的价值函数如下：

BTij∈HC则：

其中，Bi是补偿任务的被触发时间。

BTij∈SC则：

BTij∈UC 则：VBij（t）＝xi Bij≤t

我们称事务主任务的价值为事务价值，它为系统带来效益；称补偿任务的价值为事务规避价值，它为系统挽回损失。

7.5.1　支持替代的补偿任务调度

事务支持替代使事务的结构更加复杂，一个事务由多个替代组成，不同的替代可能带来不同的影响，其相应的补偿任务是不同的。既然支持替代的实时事务调度具有二重性，则其补偿任务调度也比普通的补偿任务调度更为复杂。

实时事务T的一个替代失败后，如果该替代是可补偿的，则系统会执行相应的补偿任务，并且，在时间许可的情况下，调度该事务的其他替代继续执行。因此，下面情况之一发生时意味着事务完成：一个替代成功完成，该事务成功提交；或所有替代不成功但其补偿任务完成，该事务安全地结束。

根据执行补偿的时机，补偿行为分为以下几种：

（1）立即补偿

立即补偿（见图7．12）指在替代失败后立即调度补偿任务，在消除了该替代的影响后再执行其他替代，立即补偿使用于某些必须立即消除影响的场合。

（2）延迟补偿

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

延迟补偿又可分为以下方式：

①事务内补偿。事务内补偿（见图7．13）指在某替代失败后暂时不执行补偿，在该事务提交前补偿。为了说明这个问题，我们将“End”操作提炼出来，事务在结束运行时，有一个“End”操作（相关操作内容请参考数据库实现技术的有关资料），在“End”之后才提交。事务内补偿意味着某替代失败后继续执行其他替代，一直到该事务成功或失败时才一次性执行所有补偿任务。

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

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

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

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

事务后补偿又可以分为以下4种：

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

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

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

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

7.5.2　调度策略及其实现

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

①优先级继承策略：补偿任务继承主任务的优先级。

②最早触发最优先：将最高优先级指派给具有最早“触发”（Trigger）时间的补偿任务。

③截止期最早最优先：具有最早截止期者优先级最高。

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

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

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

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

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

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

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

③主任务就绪队列MRQ：由就绪的主任务组成。

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

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

其中，Run（x）表示运行x；Release（x）表示释放x占有的资源；join （x，y）表示将x按优先级插入队列y中；Conflict（x，y）表示x与y存在资源冲突；In－sche表示内部调度；Ex－sche（）表示外部调度。