事务内存中的非干扰、局部正确性与多版本STM算法解析

### 事务内存中的非干扰、局部正确性与多版本STM算法解析 #### 1. 事务内存中的非干扰研究 在事务内存领域，非干扰是一个重要的概念。P - 非干扰的核心思想是，没有事务会因为已中止或未完成的事务而中止。也就是说，移除一些已中止或未完成的事务，在不违反给定的正确性准则P的情况下，不能将之前已中止的事务转变为已提交的事务。研究发现，没有事务内存（TM）实现能够提供不透明性 - 非干扰。 不过，任何局部正确性准则的宽容实现也是非干扰的。这里讨论了两个局部准则：虚拟世界一致性（VWC）和局部不透明性（LO）。与VWC不同，LO不允许注定要中止的事务浪费系统资源。有趣的是，对于原子事务操作，LO似乎与TMS1相吻合。 接着考虑了CLO，它是LO的一种限制，要求每个局部序列化都要尊重原始子历史的冲突顺序。并且提出了一种宽容的、因此也是非干扰的CLO实现，这似乎是目前已知的唯一非平凡的宽容实现。 #### 2. 多版本STM系统的提出背景 软件事务内存系统（STM）是共享内存系统中并发控制的一种有前途的替代方案。多版本STM系统为每个事务对象（t - 对象）维护多个版本，这样做的好处是能让更多的读操作成功执行。多版本宽容性（mv - 宽容性）是多版本STM的一个进展条件，即只读事务永远不会中止。 最近有一个只维护单一版本但具有mv - 宽容性的STM系统被提出，这就引出了一个问题：多版本STM能实现多大的并发度？研究表明，多版本STM中中止的事务比单版本系统少。并且，任何对不透明性具有宽容性的STM系统必须维护至少与活动事务数量相同的版本数，这意味着单版本或任何有界版本的STM都不能对不透明性具有宽容性。 #### 3. 系统模型与基本概念 假设一个由n个进程组成的系统，这些进程通过原子事务访问一组对象。进程有四个事务操作：write(x, v)将对象x更新为值v；read(x)返回从x读取的值；tryC()尝试提交事务，返回提交（C）或中止（A）；tryA()中止事务并返回A。 - **事务操作**：操作write、read和tryC()可能会强制中止，否则表示操作成功执行。每个操作都有唯一的事务标识符，事务从第一个操作开始，当其中一个操作返回a或c时完成，中止和提交操作称为终端操作。 - **历史**：历史是事务操作的调用和响应序列。为简单起见，只考虑顺序历史，即每个事务操作的调用紧接着匹配的响应。将历史H表示为元组⟨evts(H), <H⟩。 - **事务顺序**：对于两个事务Tk和Tm，如果Tk在H中完成且Tk的最后一个事件先于Tm的第一个事件，则Tk在H的实时顺序中先于Tm，记为Tk ≺RT H Tm。如果两者都不满足，则Tk和Tm在H中重叠。如果H中没有重叠的事务，则H是t - 顺序的。 - **有效和合法历史**：成功的读操作rk(x, v)（v ≠ A）是有效的，如果在H中有一个事务Tj在rk之前提交且wj(x, v)在Tj的事件中。如果包含rk的lastWrite的事务Tj也将v写入x，则rk(x, v)是合法的。如果H中所有成功的读操作都是有效的，则H是有效的；如果都是合法的，则H是合法的，合法历史一定是有效的。 - **不透明性**：历史H是不透明的，如果H是有效的，并且存在一个t - 顺序的合法历史S，使得S与H等价且S尊重H的实时顺序。不透明性是一个正确性准则，它将所有活动事务视为已中止。 - **实现和线性化**：STM实现为进程提供读、写、tryC（可能还有tryA）函数。如果一个实现I生成的所有历史都在正确性准则C中，则称I相对于C是正确的。由于STM实现生成的历史通常不是顺序的，为了推理实现的正确性，需要对非顺序历史中的事件进行排序以获得等效的顺序历史，这个总排序称为线性化。 - **进展条件**：如果将历史H中已中止的事务Ta提交会导致H违反正确性准则C，则称H相对于C是宽容的。如果STM实现I生成的每个历史H相对于某个正确性准则C（如不透明性）都是宽容的，则称I相对于C是宽容的。如果STM实现强制中止与另一个更新事务冲突的更新事务，且不中止只读事务，则称其具有mv - 宽容性。 下面用表格总结这些基本概念： | 概念 | 定义 | | --- | -