分布式数据库技术：深入探讨并取得进一步成果

2023-10-28 理论教育版权反馈

【摘要】：操作的响应记作〈x termA〉，其中，term表示终止条件，res*表示一系列结果值。OK表示正常终止。如果inv在inv之前和res在res之前，则H中的操作e0落在另一个操作e1里。第四个事件是满足终止条件Ok后返回响应。除最后一个启动操作外，H1是完整的。定义11.1 可线性化。一个历史H，若操作间存在一个非自反的偏序＜H，且满足：e0＜H e1 if resprecedes invin H.则与＜H不相干的操作称为是并发的（操作）。

简单来说，并发系统由一组进程构成，它们借助共享数据结构（对象）来实现通信。每个对象有其名字和类型。类型上定义了一组可能的值和操纵对象的一组元操作。并发系统的执行过程可以用一段历史（history）表示，历史是操作的启动和响应事件的有限序列。历史H的子历史（subhistory）是H中事件的子序列。

操作的启动记作〈x op（args*）A〉，其中，x是对象名，op是操作名，args*表示一系列参数值，A为进程名。操作的响应记作〈x term（res*）A〉，其中，term表示终止条件，res*表示一系列结果值。OK表示正常终止。

我们用complete（H）表示H中启动和响应都匹配的最大序列。

若历史H是顺序的（sequential），则

（1）H的第一个事件是启动；

（2）除最后一个事件外，每个事件的启动直接跟着对应的响应，每个响应直接跟在对应的启动后面。

非顺序的历史是并发的（concurrent）。

进程子历史（process subhistory）记作H｜P（H at P），是历史H中名字为P的进程的所有事件的子序列。对象x的子历史的定义与其类似。如果对每个进程P，H｜P=H′｜P，则两个历史H和H′是等价的。如果H的每个进程子历史H｜P是顺序的，则历史H是良型的（well-formed）。

历史中的操作e由事件对构成，分别是启动inv（）和对应的响应res（），我们记作［q inv/res A］。这里，q是对象，A是进程。如果inv（e1）在inv（e0）之前和res（e0）在res（e1）之前，则H中的操作e0落在另一个操作e1里。

例如，（下面省略尖括弧〈〉）q是一个FIFO（先进先出）队列，则H1是良型的（令Enq（x）为x入列操作，Deq（）为出列操作，Ok（）为操作响应）：

q Enq（x）A

q Enq（y）B

q Ok（）B

q Ok（）A(www.chuimin.cn)

q Deq（）B

q Ok（x）B

q Deq（）A

q Ok（y）A

q Enq（z）A

这里，H1的第一个事件是启动进程A的操作Eng，参数为x。第四个事件是满足终止条件Ok后返回响应。［q Enq（y）/Ok（）B］操作发生在［q Enq（x）/Ok（）A］操作之前。除最后一个启动操作外，H1是完整的。

历史集合S是前缀闭合的（prefix-closed），指无论何时，H都在S里，H的每个前缀也在S里。单对象历史（single-objecthistory）是指历史中的所有事件都与同一个对象相关。对象的顺序说明（sequential specification）是指该对象为单对象顺序化历史的一个前缀闭合集。如果每个对象的子历史H｜x属于x的顺序说明，则顺序化历史H是合法的（legal）。

定义11.1 可线性化。

一个历史H，若操作间存在一个非自反的偏序＜H，且满足：

e0＜H e1 if res（e0）precedes inv（e1）in H.则与＜H不相干的操作称为是并发的（操作）。如果H是顺序的，则＜H是一个全序。

如果历史H可以扩展（通过添加零个或多个响应事件）为H′，且满足：

L1：完整的（H′）等价于某个合法顺序历史S；

L2：＜H⊂＜S。

分布式数据库技术：深入探讨并取得进一步成果

相关推荐