Herlihy–Moss 1993：事务内存怎样用体系结构支持无锁数据结构

破除误解：事务内存不是去掉锁这个词，也不是数据库事务搬进缓存#

第一层误解把标题听成「代码里不要出现锁」，或听成 1991 年的等待自由。论文给无锁下的定义很窄：操作不要求互斥；一人在操作中途被打断，不得因此挡住别人继续操作同一对象。互斥锁直接违反它——持锁者若被抢占、缺页或用尽时间片，等待者只能停。无锁要躲开的，正是优先级反转、护航与死锁这三类锁病。可是把锁删掉，并不自动得到这篇的装置。等待自由要求每一个进程都能靠自己的有限步完成操作，哪怕别人已经停机。本页的硬件实现并不担保这一点：互相争夺所有权的事务可以反复中止，论文自己写明理论上可能饿死，活性交给自适应退避，而不是交给共识数表。把 1993 年听成 1991 年，会把一条关于缓存侦测的提案收成对象分层。

第二层误解把「事务」收进 数据库事务，或收进两阶段提交。论文自己点出亲戚：可串行化与原子性这两个形式性质，来自数据库文献，格雷 1978 年的讲义被点名为出处。差别立刻划开。数据库事务要覆盖磁盘、日志与崩溃恢复，持续时间可以跨越多次调度，数据集合可以远大于一级缓存。本页的事务被写成短命活动：应当能在一个调度量子内跑完，访问的单元数不应超过处理器缓存给出的上限。提交与中止是缓存本地操作，明确避开分布式提交协议。没有持久性合同，没有「已准备」字据，也没有协调者去广播全局决定。把事务缓存听成把锁表搬进芯片，类型就错了。隔离与原子在这里靠的是所有权冲突，不是锁项。

第三层误解把这组指令听成比较并交换循环，或听成「把加载链接与条件存储多写几遍」。论文把事务内存写成加载链接与条件存储的直接推广：加载链接近似独占事务加载，条件存储是「暂存再提交」收成单字的那种组合。单字读—改—写仍然不够。跨过一个字的对象，用现有原语往往只好再做一把锁，无锁软件实现在没有反转、护航与死锁时，实验上又常常跑不过带锁的对手。本页要卖的，是一次事务可以覆盖多个彼此独立选出的字。摩托罗拉 68000 的双字比较并交换被点名为前驱，仍然停在固定的两处。把提案读成无锁队列手册，会把存在性的硬件合同写成某一种数据结构的重试步骤。本页拒绝步骤。

第四层误解把 1993 年听成后来的软件事务内存，或听成某代商用处理器上的锁省略功能。软件把冲突侦测与版本管理搬进运行时，是另一条后继路线，不是本页的对象。商用硬件事务扩展、用事务去投机执行原来的临界区，同样是后话。本页不写指令编码，不写如何把互斥锁改成投机执行，也不写如何用中止去干扰别人的进展。容量溢出、缺页、时间片到期都可以合法地中止当前事务——这是提案写下的实现自由，不是一份攻击清单。把后来的产品页或软件库读回 1993 年，会把一份 ISCA 提案收成使用说明。

指令、读写集合，以及用所有权侦测冲突#

事务被写成单个进程执行的一串有限机器指令。两条合同同时成立。可串行化：各事务的步骤看起来并不交错；已经提交的事务，不得被不同处理器观察成两种顺序。原子性：改动先是暂态的；结束时要么提交，使写集合对别人（有效地）瞬间可见，要么中止，把暂态写丢弃。模型假定一个进程一次只跑一笔事务。可以重叠或嵌套，论文说还没见到需要。

访存一侧有三条指令。事务加载（LT）把共享单元读进私有寄存器，该单元进入读集合。独占事务加载（LTX）同样读取，但提示这里很可能随后被更新，该单元进入写集合。事务存储（ST）把寄存器里的值暂写入共享单元，在成功提交之前，新值对别的处理器不可见，该单元也进入写集合。数据集合是读集合与写集合的并。非事务的普通加载与存储仍然存在，它们不进入这些集合。事务性访问与非事务性访问落到同一地址时如何相互作用，论文故意留给实现；一种说得通的讲法，是把普通加载或存储看成一笔总是提交的事务，从而强迫冲突的事务中止。

控制一侧另有三条。提交（COMMIT）试图把暂态改动做成永久。它成功，仅当没有别的事务更新过本事务的数据集合，也没有别的事务读过本事务的写集合。成功则写集合对别人可见；失败则丢弃。无论成败都返回一个成败码。中止（ABORT）只丢弃写集合上的更新。校验（VALIDATE）探测当前事务是否仍未中止。成功返回真，只说明此刻还没中止，以后仍可能中止；失败返回假，并丢掉已经写下的暂态值。校验的动机是孤儿：一笔事务在读集合已被别人提交更新之后仍继续跑。无法担保孤儿看见的值集合仍能由某次串行执行产生。孤儿永远提交不成，却可能拿着不一致的输入去越界写、除以零。一次成功的校验，担保此前读到的值是一致的。它不是总需要，但把一致性变成可询问的状态，而不是临时发明的检查。

实现把侦测冲突的工作交给已经存在的所有权协议。要读，须取得非独占所有权；要写，须取得独占所有权，因而必须发现并撤销别人的所有权。把这些步骤换成事务性对应物，能侦测所有权冲突的协议也就能侦测事务冲突，不必另造一套分布式握手。提交与中止停在本机缓存：不必写信给别人，也不必把新值立刻写回内存。非事务操作不为此付税，仍走原来的缓存与一致性协议。定制硬件被限制在缓存及其控制器，外加与控制器通信的指令。

具体装置是两块一级缓存。常规缓存承接普通访存；事务缓存承接事务性访存。二者互斥：一行只住其中一块。仿真里，常规缓存是直映射，事务缓存是容量很小的全相联缓存，并带并行逻辑，使提交或中止可以在一个缓存周期内改标签。事务性操作给同一行准备两个条目：一份提交时丢弃，用来保住旧值；一份中止时丢弃，用来承接暂态新值。提交把后者标成已提交的正常行，把前者作废；中止则相反。冲突如何收场，提案选了一种简单策略：谁试图从另一笔仍活动的事务手里撤销事务性条目的所有权，谁就中止。页错误、时间片到期一类中断，被假定会在固定时限后中止卡住的事务，因而没有人能把资源永久扣住。总线上增加事务性读、事务性独占读，以及忙碌应答。收到忙碌则中止并稍后重试，用来挡住互相打断的死结。策略在理论上仍可能饿死；论文说若饿死在实践里成了问题，可以再叠排队。

仿真用的是麻省理工学院布鲁尔与德拉罗卡斯等人的 Proteus。两条实现：一条基于古德曼 1983 年的总线监听协议，一条基于蔡肯目录协议、对着模拟的 Alewife。都是 32 个处理器。常规缓存 2048 行、每行 8 字节；事务缓存 64 行、每行 8 字节。无争用时一次访存 4 周期。对照对象包括带指数退避的自旋锁、软件排队锁、单字加载链接与条件存储，以及硬件排队。三组基准把完成量钉在 \(2^{16}\) 次量级：共享计数器、有界先进先出缓冲、头尾指针锚定的双向链表。论文报告：即使不引入优先级反转、护航与死锁，事务内存在这些简单基准上匹配或超过当时最好的加锁技术。主要原因被说成少了一把显式锁，因而少了几次共享访存。双向链表被单独标出：非空时入队只碰尾、出队只碰头，原则上可重叠；空时必须两头一起改。用一把锁很难按状态打开这点并发，对空队列两边同时加锁还会死锁。事务内存的自然写法允许非空时的重叠。这是提案里的证据，不是操作单。

它证明了什么，也就划出了它没有覆盖什么。它证明：多字原子更新可以被写成缓存本地的提交或中止；所有权式一致性协议足以侦测冲突；在短事务、小数据集合的假定下，无锁同步可以不必先付一把锁的访存税。它没有证明等待自由。实现不担保进展，长短不一的事务里，长的更容易被中止。它没有给出任意对象的等待自由实现——那是共识数的工作。它没有覆盖 ABD 1995 那种把原子寄存器装到邮路上的仿真，也没有把 分布式共识算法 收进缓存。它没有给弱内存模型写出完整的栅栏合同：仿真停在顺序一致，栅栏如何稀疏化只是一句延伸。更大、更长的事务——例如在大节点的 B 链树上行走——被明确标成需要另一套硬件。容量上限是提案的界限，不是后来某次硅实现的故障说明。

概念证据到此为止。本页不提供如何布置事务重试、如何把临界区改成锁省略、如何用中止干扰并发的步骤。指令回答的是「一次定制的多字读—改—写在芯片上是什么合同」；忙碌与退避回答的是「冲突被侦测之后，提案选择怎样拆开互相卡住」。两句都不是操作单。

跨域连接#

• 认识论：校验拒绝一种常见的求知程序——把已经读到的一组值直接当成世界当前的一致描述。孤儿继续执行时，本地观察可以与任何一次串行执行都对不上，而进程在提交失败之前未必知道自己已经是孤儿。沉默的缓存行既可被当成「别人还没写」，也可被当成「别人已经提交、我的所有权已被撤销」。赫利希与莫斯的对策不是先判明这两种原因，而是把「此前的读是否仍一致」做成一条可询问的指令。成功的校验仍不是关于未来的知识：它只担保到此刻为止。把「我已经看见这些地址」提升为「这些地址将按这个样子被提交」，是把欠定证据做成知识。
• 知识：事务缓存里的暂态写，还不是别人能够持有的事实。提交成功，才把写集合做成对其他处理器可见的公共更新；中止则使那些写从未发生。本地的存储返回，只说明本机缓存收下了一份尚未公开的版本。把「我已经 ST 过」误认成「所有人已经按这个顺序知道了新值」，会把局部证据做成共同知识。读集合更弱：校验刚刚成功，别人仍可能随后撤销所有权。本页管的是可见性何时闭合，不管谁觉得自己已经知道。
• 因果：中止看起来像被别人「撞」出来的。观察者看见的是总线或目录上的所有权请求，以及本机把暂态行丢掉。中间没有必须经验到的锁变量，也没有一把被谁握住的互斥力。休谟说你看不见必然连接；事务冲突同样把「使之失败」收成一致性协议上的撤销，而不是收成临界区入口处的那把锁。实时上谁先发出请求，并不自动等于规格里谁先提交——忙碌应答可以把试图撤销的那一方自己中止掉。把所有权冲突读成物理上的撞击，会把缓存协议误当成台球。本页的因果是侦测关系：能发现所有权冲突，也就能发现事务冲突。
• 概率：冲突不是掷硬币，中止也不是几乎必然终止的随机算法。所有权要么仍在，要么已被撤销；忙碌要么到来，要么不来。自适应退避被建议用来拉开互相冲突的事务，仿真表明在各事务时长大致相当时它「相当好用」。这不是一条测度论保证。论文写明实现不担保进展，长短不齐时更长的事务更容易中止。把「大多数时候提交成功」说成本页的证明，等于用频率语言替换所有权几何。看起来成功可以在某次运行里碰巧成立；几何要求的是冲突不得被漏检。退避是工程上的间距，不是把饿死收成零测例外。
• 时间哲学：提交被写成让暂态写「有效地瞬间」可见。那一个瞬间不是墙上时钟的一格，而是规格里的代表元：在提交成功之前，新值对别人尚未发生；成功之后，它们不得被观察成仍未发生。中止则把那段投机的现在整段作废，像从未流过。奥古斯丁说「现在」没有厚度；事务点同样没有必须可观察的厚度，它只保证存在一种不让已提交的写与已丢弃的写同时为真的讲法。把「最终可见」听成「再等一会儿就能看见那一周期」，会把存在量词还原成超时。本页的时间是提交与中止对可见历史的切割，不是授时。

参考文献#

• Maurice Herlihy & J. Eliot B. Moss, "Transactional Memory: Architectural Support for Lock-Free Data Structures", Proceedings of the 20th Annual International Symposium on Computer Architecture, 1993, pp. 289–300. DOI: 10.1145/165123.165164. —— 本文对象：事务性加载与存储、提交与中止、用缓存一致性侦测冲突。
• Maurice Herlihy & J. Eliot B. Moss, "Transactional Memory: Architectural Support for Lock-Free Data Structures", Technical Report CRL 92/07, Digital Equipment Corporation Cambridge Research Lab, December 1992. —— 会议前的长报告，含监听与目录两套协议细节。
• Maurice Herlihy, "Wait-Free Synchronization", ACM Transactions on Programming Languages and Systems 13(1), 1991, pp. 124–149. DOI: 10.1145/114005.102808. —— 等待自由与共识数，用以标明本页停在无锁而非等待自由。
• Maurice P. Herlihy & Jeannette M. Wing, "Linearizability: A Correctness Condition for Concurrent Objects", ACM Transactions on Programming Languages and Systems 12(3), 1990, pp. 463–492. DOI: 10.1145/78969.78972. —— 并发对象的正确性条件，用以标明本页是硬件装置而非规格本身。
• Jim Gray, "Notes on Data Base Operating Systems", in Operating Systems: An Advanced Course, Springer LNCS 60, 1978, pp. 393–481. —— 论文点名的数据库事务出处，用以对照短命内存事务不是日志提交。
• E. H. Jensen, G. W. Hagensen & J. M. Broughton, "A New Approach to Exclusive Data Access in Shared Memory Multiprocessors", Technical Report UCRL-97663, Lawrence Livermore National Laboratory, November 1987. —— 加载链接与条件存储，论文将其写成单字前驱。

延伸阅读#

• 与 等待自由层级 对读：无锁躲开的是互斥造成的挡住；等待自由还要求每个人都能靠自己的步数完成。本页不提供后一句。
• 与 线性化 对读：先看并发历史怎样被收成合法顺序，再看本页用提交瞬间去逼近多字原子性。
• 与 数据库事务 对读：可串行化与原子性被借用；持久性、锁表与分布式提交被明确排除。
• 与 内存一致性模型 对读：普通访存的可见顺序不是事务缓存上的提交合同；仿真停在顺序一致。
• 与 ABD 1995 对读：那边在邮路上仿真原子寄存器；这边在共享内存的缓存协议上装多字事务。
• 与 分布式共识算法 对读：缓存本地的提交不是多数派锁定一个值。