前言

一般的无锁算法都是基于原子读写、原子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的情况;第三，写操作不能过于频繁，因为读者线程采用回退重做的方式处理读取失败的情况，频繁的写入会导致回退开销过大;第四，虽然x86的内存模型保证了读者观测结果的因果顺序，但由于CPU write-buffer、cache等原因，不能保证读者一定能读取到最新的值，要保证新写入的值第一时间被读取到，还需要加入mfence或LOCK#，利用缓存一致性协议实现。