一个特殊的无锁算法

前言

一般的无锁算法都是基于原子读写、原子 CAS 等原子操作指令实现的，其原子性通过 `LOCK#` 指令前缀锁住总线来保证，并且起到读写屏障的效果。其实在某些特定平台 (比如 x86) 和特定应用条件下可以只利用普通读写 + 编译屏障来实现完全的无锁。最近在阅读论文Scalable, High Performance Ethernet Forwarding with CUCKOOSWITCH，文中提到了一个在 x86 平台，”multiple-reader, single writer” 和 ”read-heavy workload” 条件下，只通过普通读写和编译屏障实现的无锁哈希表，在这里简单学习一下其中的无锁算法，如果理解有误欢迎留言指出。

背景

文中的算法充分利用了 x86 系列 CPU 的特性，具体来讲：

1. 所谓的“不使用原子操作”，准确地说是不利用 LOCK# 前缀这种锁总线的原子操作，本质上还是还是需要某些原子操作的。在 Intel® 64 and IA-32 Architectures Developer’s Manual: Vol. 3A 中，8.1.1 章节介绍了 Intel CPU 中支持的原子指令：

The Intel486 processor (and newer processors since) guarantees that the following basic memory operations will always be carried out atomically:

• Reading or writing a byte
• Reading or writing a word aligned on a 16-bit boundary
• Reading or writing a doubleword aligned on a 32-bit boundary

The Pentium processor (and newer processors since) guarantees that the following additional memory operations will always be carried out atomically:

• Reading or writing a quadword aligned on a 64-bit boundary
• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus

The P6 family processors (and newer processors since) guarantee that the following additional memory operation will always be carried out atomically:

• Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line

大体来讲，如果已经内存对齐，对大多数基本数据类型变量的正常读写操作都是原子的。

2. CPU 的乱序执行是多线程编程需要考虑的一个因素，因此存在各种屏障 (barrier) 来保证读写指令的顺序。而 x86 系列基本上是 strong ordering，如果使用编译屏障保证编译器不会乱序优化，大多数情况并不需要运行时的读 / 写屏障。

3. 在 Intel® 64 and IA-32 Architectures Developer’s Manual: Vol. 3A 中，8.2.2 章节阐述了多核系统中写入顺序的观测原则，其中之一是：

• Writes by a single processor are observed in the same order by all processors

这个原则保证了观测不会乱序。

算法细节

仅为了说明原理，把原文中的算法流程进行了简化，c 伪代码描述。变量 `b` 是需要同步的共享变量，v是 b 的版本。

writer 线程的流程如下：

v = v + 1;
compiler_barrier();
update(&b);
compiler_barrier();
v = v + 1;

reader 线程的流程如下：

int v1, v2;
while (true) {
    v1 = v;
    compiler_barrier();
    if (v1 % 2 == 1) {continue;}
    read(&b, &value);
    compiler_barrier();
    v2 = v;
    if (v1 != v2) {continue;}
    break;
}
do_someting(&value);

主要思想就是，如果 reader 读到两次版本值相同并且都是偶数，根据观测顺序原则，就能保证中间读到的 `b` 的值没有改变。

算法的局限性

这个算法虽然性能非常高，同时也存在局限性。第一，利用了平台相关的特性，不具备跨平台能力; 第二，只适用于 single writer 的情况; 第三，写操作不能过于频繁，因为读者线程采用回退重做的方式处理读取失败的情况，频繁的写入会导致回退开销过大