高效时空长寿命测试与设置对象及WFR-TM算法解析

### 高效时空长寿命测试与设置对象及WFR - TM算法解析 #### 1. 长寿命测试与设置对象的线性化证明 在标准共享内存模型中，对于长寿命测试与设置（TAS）对象的实现，我们需要证明其操作的线性化。假设存在一个允许的历史记录H，其中有重叠的Reset()调用。设ra和rb分别是最早和第二早调用且与其他Reset()调用重叠的调用，执行它们的进程分别为pa和pb。显然，ra和rb相互重叠，所以pa和pb是不同的进程。 设H′是H的最长前缀，其中没有两个Reset()调用重叠，即H′在rb调用之前结束。此时，ra在历史记录H′中处于未完成状态。根据引理2，H′有一个线性化S，且ra是S中的最后一个方法。 在H中，进程pb在H′完成后立即调用Reset() rb，所以pb在H′中的最后一个TAS()调用mb在H′中必须返回0。那么在S中，pb的最后一个方法调用也是mb，并且特别地，pb在mb之后不会在S中调用Reset()。根据TAS的顺序规范，S中mb（返回0）之后的第一个Reset()调用必须由同一个进程pb执行。然而，mb是pb在S中的最后一个方法调用，而进程pa的Reset()调用ra出现在mb之后，这就产生了矛盾。 由此，引理2和引理3表明，T上的任何允许历史记录都是线性化的，即实现T是线性化的。 #### 2. 事务性内存（TM）概述 事务性内存（TM）是一种有前途的并发编程范式，它使用事务来实现对公共数据（即事务性变量）的同步访问。事务可以通过将其对事务性变量的更新可见化来提交，也可以通过丢弃所有更改来中止。 大多数TM系统是乐观的，它们会推测性地执行事务，并在“怀疑”事务执行可能危及一致性时主动中止事务。然而，这种主动行为常常导致大量的虚假中止，即事务在不违反一致性的情况下也会被中止，从而降低了性能。 悲观TM算法使用锁来确保每个事务在提交前只执行一次，即悲观TM从不中止任何事务，但锁的使用可能导致事务无法在有限步骤内成功终止。大多数现有的悲观TM算法通过“悲观地”对更新事务施加顺序执行来确保所有事务提交，这在很多情况下会显著限制并行性，从而导致性能下降。 #### 3. WFR - TM算法介绍 WFR - TM算法试图结合悲观和乐观TM的优点，同时避免它们的缺点。在WFR - TM中，只读事务是无等待的，并且从不执行像CAS、Fetch&Increment、Swap等昂贵的同步操作，同时不牺牲更新事务之间的并行性。更新事务与并发执行的只读事务进行悲观同步，彼此之间进行乐观同步。 ##### 3.1 主要思想 每个事务开始时会在一个公告数组的相应元素中宣布自己。更新事务采用推测执行，并使用细粒度锁来确保更新事务性变量时的一致性。每个事务T通过维护一个读集和一个写集来跟踪它访问的事务性变量。在提交时，T会尝试获取其读集和写集中每个事务性变量的锁，为避免死锁，锁按事务性变量地址的升序获取。 获取锁后，T进入更新阶段，实际更新写集中记录的事务性变量，然后进入等待阶段，等待已宣布的活动只读事务提交，最后释放所有获取的锁。WFR - TM保证如果T进入更新阶段，它将在有限步骤内提交。 对于每个事务T，WFR - TM维护一个记录，包含T的状态（模拟、更新、等待、提交或中止）、读集、写集以及一个名为beforeMe的活动事务集，该集用于确保读操作的一致性。 对于每个事务性变量x，WFR - TM维护一个记录，包含x的当前值、版本（一个严格递增的序列号）以及一个指向某个事务记录的指针owner，用于指示x是否被锁定。 为了确保只读事务Tr的无等待性，当事务性变量x未被锁定时，Tr从x的记录中读取其值；当x被某个更新事务Tw锁定时，我们定义x的旧值和新值。Tr在初始化时会获取公告数组的快照，根据这个快照决定是否读取或忽略活动更新事务写入的值。 ##### 3.2 数据结构 WFR - TM使用以下数据结构： | 数据结构 | 描述 | | ---- | ---- | | tvarrec | 对于每个事务性变量x，存储一个CAS对象，包含x的值val、版本ver和指向txrec记录的指针owner | | txrec | 对于每个事务T，存储一个记录，包含进程标识符pid、事务状态status、读集rset、写集wset和beforeMe集 | | rnode | 读集元素，包含指向tvarrec记录的指针tvar、读取的值val和版本ver | | wnode | 写集元素，包含指向tvarrec记录的指针tvar、当前时间的旧值oldval、旧版本oldver和要存储的新值newval | | A | 公告数组，初始时所有条目都为空 | ```plaintext 1 typedef statval {SIMULATING, UPDATING, WAITING, COMMITTED, ABORTED} 2 type tvarrec 3 value val 4 uint ver 5 txrec *owner Shared variable: 21 txrec *A[1..n] 6 type txrec 7 uint pid 8 statval status 9 set of rnode elements rset 10 set of wnode elements wset 11 set of pointers to txrec elements beforeMe 12 type rnode 13 tvarrec *tvar 14 value val 15 uint ver 16 type wnode 17 tvarrec *tvar 18 value oldval 19 uint oldver 20 value newval ``` ##### 3.3 伪代码描述 - **BeginTx**：当进程p为事务T调用BeginTx时，它会创建并初始化T的txrec记录，然后在A[p]中宣布T，最后调用CheckIfPerformed来初始化T的beforeMe集。CheckIfPerformed会不断读取公告数组A的所有元素，并将状态为等待或已提交的新更新事务添加到T的beforeMe集中。由于在CheckIfPerformed执行期间，在T宣布之后宣布的任何事务T′在CheckIfPerformed完成之前都无法提交，所以CheckIfPerformed会在有限步骤内终止。 ```plaintext 22 txrec *BeginTx() by process p: 23 txrec *newTx := new txrec 24 newTx →pid := p 25 newTx →status = SIMULATING 26 newTx →rset := empty set of rnode elements 27 newTx →wset := empty set of wnode elements 28 newTx →beforeMe := empty set of pointers to txrec elements 29 A[p] := newTx /* T announces itself */ 30 CheckIfPerformed(newTx) /* initialize set beforeMe */ 31 return (newTx ```