一个特殊的无锁算法

07 Jun 2016 | 无锁, 原子操作 | | ˚C

前言

一般的无锁算法都是基于原子读写、原子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是需要同步的共享变量,vb的版本。

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#,利用缓存一致性协议实现。


Older · View Archive (10)

OpenSUSE Leap在线更新到Tumbleweed小记

Newer

博客还是不能丢的