嵌入式实时数据库系统的事务模型与处理技术

6　嵌入式实时数据库系统的并发控制协议

6.1　基于FATM事务的并发控制特点

我们不能沿用传统数据库系统的并发控制协议，因为它们强调所有事务具有平等的地位和相同的调度机会。对于嵌入式实时数据库系统而言，为了使尽可能多的事务满足它们的截止期，应该将事务的时间信息加入到调度中来，事务越紧急应越早地投入运行。当一个事务正在运行时，如果新到了一个更为紧急的事务，该执行事务应该让出处理机及对所有资源的控制权，使新到的紧急事务优先执行。

嵌入式实时数据库系统并发控制机制的新特点主要体现在以下几个方面：

（1）并发执行的事务具有时间约束和依赖性

嵌入式实时数据库系统中的事务具有显示的时间约束，必须满足其截止期，这是最基本的要求，一切实时事务调度和并发控制都围绕着这个目的。除此以外，当它们并发执行时，事务之间可能存在与时间有关的依赖关系，比如，事务T1必须在事务T2开始执行之前（或提交前/后）开始/提交；一个事务在运行过程中可能触发其他子事务，被触发事务与此触发事务并发执行，当触发事务完成时，可能不能立即提交，需要等到被它触发的事务也完成以便一起提交，等等。

在传统数据库系统中，并发执行的事务间也存在关联，但主要是由于事务间通讯产生的，与我们所指的关联显然具有根本区别。

（2）必须满足硬实时事务的截止期要求，尽可能满足软实时事务的截止期要求

在嵌入式实时数据库系统中，事务不是平等的，通常按截止期的特性将实时事务分为硬实时事务和软实时事务。它们的紧迫程度不同，因此优先级也不同，系统必须保证硬实时事务的截止期，否则，该事务在截止期后可能对系统产生危害；同时，虽然软实时事务超过截止期后不会对系统产生危害，但该事务的价值也会急剧下降，由此，并发控制在保证数据一致性的前提下，为了满足事务的截止期要求，应区别对待不同特性的实时事务。通常硬实时事务的优先级最高，非实时事务（无时间限制的事务）的优先级最低。

（3）一个正在运行的事务可以被更为紧急的事务抢占系统资源和CPU控制权

由于事务的紧迫程度不同，当一个紧急事务到达时，为了处理该紧急事务，使之满足截止期要求，系统可能必须使正在执行（还未完成）的事务夭折，转而执行该紧急事务。紧急事务抢占系统资源和CPU控制权，在执行完成后将它们释放，系统再执行其他的事务，抢占可能导致被抢占的事务因此而超过其截止期。一般而言，硬实时事务可以抢占软实时事务，同样性质的实时事务中，高优先级事务可以抢占低优先级事务。如果系统允许硬实时事务被更高优先级的硬实时事务抢占，则被抢占的硬实时事务夭折将带来系统损失，很难避免硬实时事务之间发生冲突，系统能做的是衡量得失，使总体收益最大。

（4）由于必须保证事务的原子性，被抢占的事务夭折重启

嵌入式实时数据库系统的事务与传统数据库系统中的事务相比，具有更为复杂的结构和更强的描述能力，它已不再是平淡的操作序列，典型的事务模型具有分裂结构、嵌套结构等。似乎不必维持事务的原子性，其实不然，整体上来说，由于事务可以嵌套（或分裂）甚至触发多个子事务，其原子性被破坏了，但对于组成该复杂事务的基本事务（子事务）来说，依然应保持原子性，因此，当一个基本事务被抢占后，必须重启。

（5）事务处理的正确性不仅依赖于逻辑结果，而且依赖于逻辑结果产生的时间

对于实时事务而言，超过截止期所得到的结果可能是无效的。例如，在水库检测系统中，昨天的水位数据对于今天的闸门控制可能是无意义的；自动驾驶汽车在高速行驶过程中，其探测器在过去1小时得到的车前信息也可能是无效的，甚至根据该信息驾驶有可能发生事故。因此，实时事务处理的结果不仅要满足逻辑正确性，而且必须满足截止期要求。

（6）系统宁愿要及时的部分正确的结果，也不要过时的精确的结果

在资源受限的实时数据库系统中，并发事务竞争系统资源，当系统超载时，必然存在某些事务不能在其截止期内完成，对于某些实时应用环境，在截止期之后的精确结果是无效的，那么，在截止期内，即使得不到精确结果，如果能得到近似结果也比根本没有结果要好得多。例如，在股票交易系统中，某股票价位变化如下：

时刻t1：p1＝13．2元

时刻t2：p2＝13．3元

t1＝t2＋2（分）

如果事务不能在截止期前查询到p1，完全可以直接使用p2，因为用户在2分钟内对0．1元的差别也许不会很在意。

（7）数据一致性标准有所放松

传统的数据库一致性标准是可串行化，并发控制的目的是保证数据的逻辑一致性，要求事务是平坦的，具有ACID特性。对于嵌入式实时数据库系统而言，要求满足数据的时态一致性和逻辑一致性，则此标准过于严格，因为在并发控制算法中，由于事务的重启和/或受阻可能导致无法预计的延迟。为了使尽可能多的事务满足截止期，需要放松正确性标准以满足或兼顾时间一致性要求。

（8）并发控制分化为两级

替代是执行单位，因而也是并发控制的基本单位，系统只需满足实时事务某个替代的资源需求，而不需要满足该事务的资源需求，前者是后者的子集，因此，降低了资源竞争的激烈程度。在单机系统中，在某一时刻，系统可以允许每个事务的一个替代执行，也可以允许每个事务的多个替代并发执行；在多机系统中，一般会允许每个事务的多个替代并行，以此提高了事务的成功率。

（9）评价性能的标准不是反应时间和系统吞吐率，而是系统的成功率

6.2　正确性标准

6.2.1　正确性标准

传统事务必须满足逻辑正确性和内部一致性，其并发控制的正确性标准为可串行化，它有3种逐渐严格的形式：

（1）效果可串行化（ESR）

要求一个正确的并发调度产生与相同事务的一个串行调度一样的状态转换。即从相同的数据库初始状态，产生相同的数据库终结状态。

（2）视图可串行化（VSR）

不仅要求效果是可串行化的，而且两个调度有相同的数据视图（各事务读的数据及其顺序在两个调度中是一样的）。

调度S1和S2如果满足下列条件，则它们是视图等价的：

①S1和S2有相同的事务和相同的操作；

②对于任意数据项x，如果Ti在S1中读来自于Tj的x，则在S2中读来自于Tj的x；

③对于每个x，如果wi（x）是S1中X的最后写，则它也是S2中的最后写。

如果一个调度等价于某些串行调度，则该调度是视图串行化的。

（3）冲突可串行化（CSR）

冲突可串行化要求一个正确的并发调度对于任意两个冲突操作的排序与相同事务的一个串行调度相同。

实时事务除了满足传统的逻辑正确性标准外，还必须满足时间一致性要求。传统的正确性标准针对于实时事务来说显得过于严格。实时数据库系统的典型应用是计算机集成制造系统，数据库要跟踪物理机器的状态、控制流水线的处理、收集制造操作中的统计信息。对于某些实时应用，并发事务可能并不需要串行，例如，表示一个对象当前状态的信息可能在机器人利用它工作之前就需要修改，只有当机器人的视图中进行了一致性的变化，并且该变化在特定的时间内完成，该修改事务才被认为是成功的。既然嵌入式实时数据库系统中的硬实时事务常常用于响应外部事件，及时有用的结果比串行但超时的结果更受关注，为便于及时执行和满足截止期，我们希望放松正确性的定义，只要事务的最终状态与真实世界的情形吻合，该事务是否与其他事务串行在应用中不是主要问题。

下面举例说明实时数据库系统中同时满足逻辑一致性和时态一致性是很困难的。

例6．1：如图6．1所示，调度H0不是冲突可串行化的，当执行W1（y）时，事务T1或T3将夭折并重启以保证冲突可串行化，然而，因为只有在截止期后的调度才是可串行化的，所以重启的事务不能满足其截止期。

图6.1　事务并发处理

由此可见，冲突可串行化太严格了。我们需要采用一些放松的正确性标准，产生语义正确但非可串行化的实时数据库调度。

H0：W1（x）R2（x）W2（z）R3（z）W3（y）W1（y）

实时数据库系统并发控制采用的正确性标准通常有以下几种：

（1）ε—可串行化并发控制

ε—可串行化（Epsilon－Serializability）是事务处理中的一种正确性标准，它是一种更一般的误差受限的串行化。它允许不一致性数据被读取，并控制不一致性的程度，使误差量限制在一个指定范围，而使数据最终能达到一个一致性状态。ε—可串行化需要数据库的数据空间是一可度量空间，使用ε—可串行化放松逻辑一致性要求以期满足时间一致性要求。

（2）Δ—可串行性并发控制

Δ—可串行性是基于“相似性”概念的正规可串行性的扩展。相似性是指在时间和精确性上有微略差别的数据可以彼此替换地作为事务的读数据。“相似”是内在地依赖于应用的概念，不同的事务对同样的数据对象可以有不同的相似性要求，两个值有多大的“微细差别”才能算相似，应依特定的应用而定。“相似”是一种二元关系，它是自反的、对称的，但不一定是可传递的。

一个数据对象的两个值是相似的，如果所有要读它们的事务都将其当做是相似的。

（3）基于语义的并发控制

可串行化不是维护逻辑一致性的惟一方法，还可以依据事务在数据库中的操作语义将事务分类，使用兼容集而非可串行化作为正确性标准。在Rhode Island大学开发的RTSORAC（Real－time Semantic Objects and Constraints model）系统中使用了基于语义的并发控制技术。

（4）Statewise串行化

一个调度S是Statewise串行化的（SSR）当且仅当：

①S产生与一个串行调度相同的数据库状态。

②如果存在一个无效读操作Rinvalid，则Rinvalid不影响数据库状态的改变。

例6．2：假设T3的W3（y）值依赖操作，即W3（z）依赖于读操作R3 （y），显然H1既不是VSR也不是CSR。

H1：W1（x）W2（x）W2（y）R3（y）W3（z）W1（z）

表6.1　调度H1的执行

H1有与T3T1T2同样的结果，但没有同样的“读自于”（read－from）关系。R3（y）读的值由T2的W2（y）产生。由于T3读串行调度T3T1T2中的一个原始值，H2的操作R3（y）是无效读操作。值依赖操作W3（z）可能写一个由R3（y）引起的非一致性值，然而，W3（z）写的值立即被W1（z）覆盖，最终的数据库状态是一致的。最后，值依赖写操作W3（z）（依赖于R3 （y））不影响数据库状态的变化，所以H1产生正确的数据库状态。

6.2.2　正确性标准分析

已知调度H涉及事务T1和T2，可能还有其他事务，如果在调度H中有T1的操作A1和T2的操作A2满足条件：

①在H中A1在A2前；

②A1和A2都涉及同一个数据库元素；

③A1和A2中至少有一个是写操作。

称T1优先于T2。记为：T1＜HT2。

这种情况下不能交换A1和A2的顺序。因此，在任何冲突等价于H的调度中，A1将出现在A2前面，如果这些调度中有一个是串行的，则调度必然使T1在T2前面。

事务执行顺序常常用串行图来描述，串行图包含两个要素：

①结点：表示调度中的事务；

②箭头：表示执行顺序，当事务T1执行后紧接着执行T2时（即：T1 ＜HT2），则有一个从T1结点到T2结点的箭头。

判断一个调度H是否是冲突可串行化有一条简单的规则：构造H的串行图，并判断H中是否有环，如果有环，则H不是冲突可串行化的，如果无环，则H是冲突可串行化的，而且结点的任一拓扑顺序都是一个冲突等价的串行顺序。

例如，调度H0的串行图如图6．2所示：

图6.2　H0的串行图

前面已经分析得到结论：H0不是冲突可串行化的。

看调度H2：W1（x）R2（x）W2（z）R3（z）W1（y）W3（y）

其串行图如图6．3所示，H2是冲突可串行化的。

图6.3　H0的串行图

我们将一致性分为6个级别，如表6．2所示，它们都能保证正确的数据库状态：

表6.2　一致性的形式

①严格一致性：有一个非循环串行图来描述，事务的修改顺序与其提交顺序保持一致。

②强一致性：仅由一个非循环图描述。

③弱一致性：通过允许只读事务与修改事务独立的串行来放松强一致性，它允许串行图包含由多个只读事务以及至少一个修改事务组成的环，但是依然禁止包含单个只读事务以及至少一个修改事务（单个查询环）的环，以及仅仅涉及修改事务（修改事务环）的环。

④修改一致性：如果一个只读事务与一个修改事务串行，而修改事务产生的值能被该事务看见，则该只读事务具有修改一致性。即一个修改一致性查询可能与修改事务不串行，它依然能保证得到一个事务一致的数据库。如果只读事务与修改事务串行，而该只读事务看得见修改事务产生的值，则它允许串行图中有单查询环。

⑤写一致性：保证修改事务之间是串行的，只读事务不需与其他事务保持串行。它允许所有的单查询环和多查询环，如果只读事务可以输入一些非一致性数据且修改事务可以输出一些非一致性数据，则该串行化可以归结这种一致性形式。

⑥状态一致性：只要能保证数据库的正确状态，状态（state）一致性允许修改事务环、单个或多个查询环。它还允许被调度器控制的时态数据库非一致性，但是，数据库保证从一个正确状态转换到另一个正确状态。

6.3　基于替代的并发控制策略

嵌入式实时数据库系统常常在无人工干预情况下运行，系统不仅需要较高的成功率，而且应具有较高的预见性，是一个自适应能力很强的实时系统。如前所述，为了支持这些特点，其事务模型具备功能替代性，事务的结构更加复杂，语义更加丰富；与之相适应，系统需要相应的与传统实时数据库系统不同的并发控制机制。

前述的实时数据库系统并发控制机制基本上是从非实时数据库系统中将假设和结果转换过来，带来的问题是人们在设计并发控制机制时，将注意力集中在时间限制特性上，忽视实时事务的功能替代特性。

嵌入式实时数据库系统应尽量保证硬实时事务满足其截止期约束，通常的措施是使硬实时事务具有较高的优先级，但是，如果系统中有大量硬实时事务，而这些硬实时事务本身发生资源冲突时，还是有些硬实时事务被牺牲，系统灾难在所难免。因此，除了在分派优先级时给硬实时事务特殊优惠外，应考虑增强硬实时事务本身的应变能力。下面介绍的FHC策略就考虑了多个硬实时事务之间的资源冲突，允许硬实时事务的多个替代并发执行，提高事务成功率，降低风险。

CCCP策略则在一个事务中选取一个最佳替代参与系统调度，其“最佳”体现在适应系统动态环境上（成功执行的可能性最大），从另一个方面提高了事务的成功率。

实施并发控制主要依据下列三类信息，它们需要在编译阶段通过预分析得到。

①有关事务实时特性的信息：

第一，事务的实时性。事务的实时性指事务是硬实时事务、软实时事务、固实时事务还是非实时事务。通常而言，系统应首先满足硬实时事务的截止期要求，依次是固实时事务、软实时事务，事务的实时性越强，其优先级越高，非实时事务可以在系统空闲时再处理。

第二，事务的截止期。实时数据库系统的主要目标就是满足实时事务的截止期，所以，截止期是实施并发控制和调度必须考虑的因素。

第三，事务的估算执行时间。由事务的估算执行时间和截止期共同决定事务的空余时间，由此判定该事务的紧迫性以及事务的可调度性。

②有关事务数据资源的信息，在编译阶段可分析出事务所需的读写数据集，只有无冲突的事务才能并发执行，使CPU作为宝贵的系统资源得到充分利用。

③有关事务替代性的信息，替代是并发控制的基本单位，这类信息至关重要。

下面的并发控制策略涉及以下约定：

①活跃事务包括正在执行的事务和就绪的事务，活跃事务的全集记为active（T），活跃替代包括正在执行的替代和就绪的替代，活跃替代的全集记为active（FX）。

②数据对象（关系）在系统中有惟一标识。

③事务对数据对象的操作有三种方式：写（w）、读（r）和无操作（n）。

④规定每种对象操作的语义值：osv（“n”）＝0，osv（“r”）＝1，osv（“w”）＝2。

由此，写的级别高于读，而读的级别高于无操作，这将有利于判定事务之间的冲突。

如前所述，在实时数据库系统中，如果系统不能满足硬实时事务的截止期，则可能导致系统灾难，如果系统不能满足软实时事务的截止期，则事务的价值下降，比较而言，系统灾难造成的损失最大，是所有系统都应避免发生的。因此，并发控制的重点应是首先满足所有硬实时事务的截止期。传统的并发控制策略也注意保护硬实时事务，它们采取的措施是提高硬实时事务的优先级并允许资源抢占。但是，当有若干硬实时事务发生冲突时，这些策略并没有适当的措施保护优先级相对较低的硬实时事务，它们有可能因被抢占资源或等待而夭折，系统灾难在所难免。要改善这种情况，需要从事务的内因寻找突破口。

6.3.1　替代的相容性分析

根据预分析得到事务（替代）的读写集，我们可以静态分析替代间是否存在数据资源冲突，这将有利于消除同一事务内的冲突。

定义6．1：设cg（Ti，dj）表示事务（替代）Ti对数据对象dj的操作类型，Ti对dj的操作集为：

ops（Ti，dj）＝｛cgk（Ti，dj）｜0≤k≤2，cgk（Ti，dj）∈｛“n”，“r”，“w”｝｝

即事务Ti要么写对象dj，要么读对象dj，即使事务Ti对对象dj不做任何实质性的操作，我们也认为是一种特殊的“无操作”类型“n”。这样，可以用一致的观点在所有事务和所有对象之间建立联系。

对于系统中全体事务的集合TS和全体数据对象的集合OB，存在如下关系：

如果事务Ti既读对象dj过后又写dj，系统怎样判定其操作类型呢？这个问题和封锁的力度有关，如果封锁力度小，读dj操作和写dj操作不在一个临界区内，则应该分别计算其操作类型：在前一个临界区中事务Ti对dj进行的是读操作，在后一个临界区，事务Ti对dj进行的是写操作，这两个操作相对独立。如果封锁的力度大，两个操作在一个临界区内，则系统应注重对发生资源冲突的影响更大的操作。

嵌入式实时数据库系统采用内存数据库技术，通常锁的力度较大，可以定在关系级。(www.xing528.com)

为了考查读和写操作在冲突中所起的作用，我们重申数据资源冲突的情形：

“冲突”的含义是：在调度中有一对动作，如果交换它们的顺序，则涉及的事务中至少有一个的行为会改变。假设Ti和Tj是两个不同的事务，X和Y是数据对象，ri（X）表示Ti读X，wi（X）表示Ti写X，它们的行为可能是以下几种：

①ri（X）；rj（Y）无论X≠Y还是X＝Y都不会冲突，因为它们没有改变数据对象的值。

②ri（X）；wj（Y）在X≠Y时不会冲突，因为是Tj在Ti读X之前Y，X的值不会改变，而且Ti读X对Tj没有影响，它不会影响Tj为Y写的值。在X＝Y时会冲突，因为wj（Y）改变了Y的值，ri（X）会得出与前面不同的结果。

③wi（X）；rj（Y）在X≠Y时不会冲突，否则冲突，理由同上。

④wi（X）；wj（Y）在X≠Y时不会冲突，因为X和Y互不影响。在X ＝Y时冲突，因为这两个动作的次序不同，数据的结果也不同。

⑤ri（X）；ri（Y）无论X≠Y还是X＝Y都不会冲突。

⑥ri（X）；wi（Y）在X≠Y时不会冲突，在X＝Y时冲突。

⑦wi（X）；ri（Y）在X≠Y时不会冲突，在X＝Y时冲突。

⑧wi（X）；wi（Y）在X≠Y时不会冲突，在X＝Y时冲突。

可见，事务的两个动作在满足下列条件时是冲突的：

其一，它们涉及同一个数据元素。

其二，至少有一个是写。

在上述⑤～⑧的情况中，两个操作是不能交换的。

可见，两个操作中，只要有一个操作是“写”，则它们必定发生冲突，因此，起关键作用的是写操作，其次是读操作，其关键性正好和上述的操作语义值的级别吻合。

不管事务Ti对对象dj有什么操作，我们关注的是这些操作中最关键的操作，用操作顶表示。

定义6．2：事务（替代）Ti的操作顶定义为maxop（Ti，dj）＝cgk，它使下列条件成立：

osv（cgk（Ti，dj））＝max（osv（ops（Ti，dj）））

表6．3举例说明了操作顶的判定。

表6.3　操作顶示例

替代是事务的特例，具有事务的一切特性，上述事务与数据对象的关系同样适用于替代。

表6．4表示了事务T1和T2对数据对象X的所有操作，从表中可看出，分析事务间是否发生资源冲突，只需要分析它们对数据对象的操作顶是否冲突即可。

假如数据库db中关系的个数记为numdb（db），有下列定义：

定义6．3：替代fxij的存取模式AMA（CCCPess model of alternative）是一个线形表，定义为：

表6.4

AMA（fxij）＝（CG，R）

CG＝｛maxop（fxij，dq）｜1≤q≤numdb（db）｝

R＝｛ROW｝

ROW＝｛＜maxop（fxij，dq），maxop（fxij，dq＋1）＞｜1≤q＜numdb（db）｝

关系R是一个序偶的集合，它表示AMA中元素之间的相邻关系。即：maxop（fxij，dq）领先于maxop（fxij，dq＋1）。

例6．1：假设系统中有6个数据对象：d1，d2，d3，d4，d5，d6，则事务Ti的替代fxij对这6个数据对象的操作顶分别是：n，r，w，w，r，n，则fxij的存取模式为：

（n，r，w，w，r，n）

定义6．4：当两个存取模式AMA（fxik）和AMA（fxjg）符合条件：

∧（maxop（fxik，dλ）＝“r”→（maxop（fxjg，dλ）≡“n”∨maxop （fxjg，dλ）≡“r”））

∧（maxop（fxjg，dλ）＝“w”→（maxop（fxik，dλ）≡“n”））

∧（maxop（fxjg，dλ）＝“r”→（maxop（fxik，dλ）≡“n”∨maxop （fxik，dλ）≡“r”））

则fxik和fxjg是相容替代，记做：com（fxik，fxjg）。

例6．2：fxik和fxig是实时事务Ti的两个替代，它们的存取模式分别是：

AMA（fxik）＝（n，w，r，r，n，r）

AMA（fxig）＝（w，n，r，r，w，r）

根据定义6．4，fxik和fxig是相容的。

反复对事务进行相容性检测需要耗费CPU时间，该检测算法的高效低耗显得非常重要。下面提出一个简单的算法可以达到这个目的。

为每种对象操作op设置一个代码id（op），其代码值如表6．5所示。

两个来自于不同事务的操作同时作用于一个数据对象时，CCCP将它们的代码进行“与”运算，表6．6列出了运算结果。从表6．6可见，两个操作冲突时其代码值的“与”运算结果为“10”，因此，判定对同一对象的两个操作是否冲突时，只需将它们的操作代码进行“与”运算便可。

表6.5　操作代码表

表6.6　操作冲突表

这样，替代的存取模式就可以用一个由二进制数组成的记录来表示，称为标志记录。为每个事务的每个替代保留一个长度是2＊number（db）个bit的标志记录，标志记录中每两个bit是一个标志段，对应数据库中的一个关系。判断替代FXi和FXj是否相容时，只需将它们的标志记录按位做“与”运算，如果有标志段的值为10，表示它们在对应的数据对象上冲突，fxik和fxjg不相容（见图6．4）。

图6.4　相容性检测示意图

事务的标志记录数等于它所包含的替代数，创建新的关系时，新的标志记录就变长，由于它们只与后面到达的新事务有关，原有事务的标志记录不变。删除记录时，只对相应的标志段做删除标志，系统空闲时再重整，这种检测方法简洁有效。

替代的相容性分析是静态分析，不需要占用事务的执行时间。

定义6．5：针对于实时事务T的替代FXi，其同类替代集SK（fxij）定义为：

SK（fxij）＝｛fxik｜fxik∈Ti，

其异类替代集DK（fxij）定义为：DK（fxij）＝T－SK（fxij）

同类替代之间没有资源冲突，异类替代之间存在资源冲突。

6.3.2　FHC并发控制策略

有利于硬实时事务的并发控制策略FHC允许硬实时事务的多个替代并发执行，借以提高成功率，这些替代也是该事务替代集中的一部分，当其中有一个替代成功则该事务成功，其他替代终止执行；如果不幸正在运行着的所有替代都夭折，则能够选取其他替代运行。当然，事务此时的成功率往往较低。多个替代并发增加了系统负担，可能在一定程度上增加了整个系统中资源竞争的程度，但是，对于该硬实时事务而言是十分有利的，系统牺牲其他他类型事务的利益而保全硬实时事务。

BHC基于实时事务功能替代性，允许多个替代并发执行，某事务并发执行的替代之间不发生数据资源冲突，只要一个替代成功则该实时事务提交，某些替代夭折后有可能继续执行该事务的其他替代，由此避开资源阻塞。

BHC基于这样的事实：一个硬实时事务有可能有多个替代并发执行，每个替代代表一个执行路径，只要其中一个替代成功则该硬实时事务可以提交；一个替代夭折，不表示该事务夭折，甚至并发执行的所有替代夭折，也不一定表示该硬实时事务夭折，该事务有可能会从另外的替代重启。由此，从根本上提高了事务的适应能力，从而提高了事务的成功率。

为实现这一目标，我们提出的并发控制机制基于数据资源预报，采用内存数据库技术，我们将锁的力度放大为关系，它将使我们的并发控制机制变得简单而有效。

针对事务的替代性，并发控制分为两个步骤：

①替代级控制。在实时事务内部对替代进行并发控制，在静态环境下将事务的替代进行分组，不同组的替代存在资源冲突，同组的替代不存在资源冲突。这些替代组根据优先级进行排序，系统首先选优先级最高的替代组参与后续执行，当该替代组的所有替代在事务级并发控制中被阻塞时，系统选取下一组替代继续参与事务级控制。

②事务级控制。通过替代级控制的诸替代作为事务特例各自独立地执行，系统对它们所做的并发控制称为事务级控制。

从并发控制的范围来看，图6．5描述了替代级控制和事务级控制之间的关系。

在允许多替代并行的情况下，首要问题是要保证这些并行的替代之间没有数据资源冲突，它们是同类替代，否则替代并行增加了阻塞机会，该事务可能会因为自身内部的冲突而受阻直至夭折；此时，同一事务多替代并行就没有意义。结合优先级信息，同类替代集的选择应遵循两个原则：

①优先级高者优先。按优先级从高到低的顺序，优先选取高优先级的替代。

②淘汰不相容替代。生成替代的同类替代集。

例6．3：有实时事务Ti，其替代序列为：

FXrpri＝（FXS，R）；

图6.5　事务并发控制层次图

FXS＝｛fxij｜fxij∈Ti，1≤j≤n｝

R＝｛＜fxij，FXij＋1＞｜Pri（fxij）＞Pri（fxij＋1），1≤j＜n｝；

Pri（fxij）表示fxij的优先级。

取优先级最高者fxij，保留SK（fxij），淘汰其他替代。

事务Ti的所有替代用集合FX－S表示，则选择替代组的算法如下：

①在事务FX－S中选择优先级最高的替代Fxij；

②将Fxij与所有的其他替代进行相容性检测，所有与Fxij相容的替代组成一个替代组，并将被选中的替代移出FX－S；

③重复以上过程直到所有FX－S为空。

为上面生成的每个替代组赋一个优先级，其优先级等于该组中替代优先级的最高值。

事务在系统中的控制流程如图6．6所示。事务经过静态预分析，由形态1变为形态2，在形态2中，事务的同类替代集形成，并且，按优先级对这些替代组进行了排序，替代组的优先级取该组最高优先级，在每个事务Ti中选取一个最优的（优先级最高的）替代组进入就绪队列，当该替代组中的所有替代都夭折，但Ti仍然有足够时间时，继续选取Ti的下一个替代组运行。

替代夭折并不代表事务夭折，系统夭折一个替代FXi时有三种处理方法：

①夭折该事务。当事务T的所有替代都不可能满足其截止期要求时，该事务夭折。

其中，Abort（Ti）表示夭折事务Ti。

②重启一个异类替代。在事务Ti中，当所有并发执行的同类替代SK （fxij）都夭折时，如果该事务还存在可以满足截止期要求的替代，则从中选取优先级最高的同类替代组。

图6.6　多替代并发的事务控制流程

③继续执行其他同类替代。当还有被夭折替代的同类替代在系统中执行时，夭折该替代后，继续执行其未被夭折的同类替代，不做其他处理。

事务提交依赖于替代，所以，当一个替代提交时，系统停止其所有同类替代的运行。即：

当替代通过“替代级控制”独立地参与系统运作时，完全保持了事务的控制特性。因此，FHC事务级并发控制策略可以沿用现有的实时数据库系统的并发控制策略。

6.3.3　无冲突的并发控制策略（CCCP）

在CCCP中，替代依然是并发控制的主体，不同的是：每个事务中一个时刻只有一个替代在运行，该替代是最适合当前运行环境的替代，它以无冲突的方式执行。

对于系统接纳的事务Ti，CCCP分析Ti与就绪队列中的事务是否存在资源冲突，如果在Ti中所有的替代都与就绪队列中的某些事务（实际上是各事务的替代）冲突，则该事务不能进入就绪队列；如果Ti中存在某替代fxij与就绪队列中的所有事务不冲突，则该替代进入就绪队列。所以，CCCP首先分析事务间是否存在资源冲突。

定义6．6：事务T的存取模式AMT（CCCPess model of transaction）为：

AMT（Ti）＝｛AMA（fxij）｜fxij∈Ti，1≤j≤n｝，n为事务所包含替代的个数。

定义6．7：事务Ti和Tj是静态相容的，当且仅当下列条件成立：

Efxik∈TiEfxjg∈Tj（com（fxik，fxjg））

定义6．8：事务Ti和Tj是动态相容的，当且仅当Efxik∈TiEfxjg∈active （Tj）（com（fxik，fxjg））成立。

如果两个事务是静态相容的，则它们不可能发生资源冲突，但是，此要求过于苛刻，在传统的事务模型下可行，对于支持替代的实时事务而言，完全可以放松该要求。那些非活跃的替代在被激活之前对其他事务的执行是没有影响的，因此，只要求两个事务动态相容即可。

事务之间的动态相容性是随事务的执行而变化的，当某事务的活跃替代夭折，一旦系统选取了该事务的其他替代继续执行，则该事务与其他事务之间的动态相容性可能被改变，必须重新检测。

定义6．9：如果），称fxik为强相容替代，active（FXjj）表示FXjj是活跃的。

事务Ti中存在与事务Tj的强相容替代fxik，表示无论Tj怎样执行，只要fxik在执行则事务Ti和Tj就是相容的。

CCCP遵循的原则有：

①保护就绪事务。由于有内存数据库技术支持，无I/O等待，处理速度快，我们将并发控制由读/写级提高到事务级。虽然降低了事务的并发度，但同时降低了系统开销，提高了效率。系统根据事务的实时性和数据资源需求分析事务间的相容性，只有与运行事务动态相容的事务才能进入就绪。其目的是重点保护活跃事务，使它们有更多的CPU时间更快地执行，从而提高系统的吞吐率。

②基于优先级的并发控制。CCCP遵循基本的优先级调度原则，系统优先满足优先级高的事务，当新事务的优先级高于活跃事务时，新事务抢占资源。

③放行与活跃事务动态相容的事务Ti，在Ti中选取强相容替代进入就绪队列。放行强相容替代能动态地也是暂时地保证事务的动态相容。

对于接纳队列中的事务，按优先级从高到低的顺序做如下处理：

①每个新事务Ti与活跃事务进行相容性检测，如果Ti与它们动态相容，则取Ti的强相容替代进入就绪队列，否则进入②。