Electronic Joint Business

Solution for E-Business

lock

无锁双向链表

基于锁的同步机制总是受到象优先级反转(priority inversion )和死锁的困扰,即使这样,无锁同步还未引起重视。原因是要编写正确且高效的无锁代码实在困难1。本文演示了一个无锁双向链表的实现,实用且易于理解。第一个无锁双向链表是由 H°akan Sundell 实现的,本文中的方案利用了单字 (single-word) 的比较并转换(CAS — compare-and-swap)原子原语。在附录中提供了本方案与 H°akan Sundell 实现的链表的比较结果。 2

背景: 原子操作与 CAS
原子操作是指一系列必须整体完成的操作步骤,如果任何一步操作没有完成,那么所有完成的步骤都必须回滚,这样就可以保证要么所有操作步骤都未完成,要么所有操作步骤都被完成。在单核系统里,单个的机器指令可以看成是原子操作(如果有编译器优化、乱序执行等情况除外);在多核系统中,单个的机器指令就不是原子操作,因为多核系统里是多指令流并行运行的,一个核在执行一个指令时,其他核同时执行的指令有可能操作同一块内存区域,从而出现数据竞争现象。多核系统中的原子操作通常使用内存栅障(memory barrier)来实现,即一个 CPU 核在执行原子操作时,其他 CPU 核必须停止对内存操作或者不对指定的内存进行操作,这样才能避免数据竞争问题。3

因此在 X86 平台上,Intel 提供了在指令执行期间对总线加锁的手段。CPU 芯片上有一条引线 #HLOCKpin,如果汇编程序中的某条指令带了前缀 “LOCK”,CPU 执行到这条指令时就会 #HLOCKpin 的电位拉低直到该指令结束,从而将总线锁住,这样同一总线上其它 CPU 就暂时不能通过总线访问内存了,这样保证了指令在多处理器环境中的原子性。

所谓比较并交换 (CAS) 是在多线程中可用来获得同步的原子指令。CAS 操作包含三个操作数 —— 目标值(V)、原值(A)和新值(B)。CAS 指令会先将目标值 V 与原值 A 进行比较,如果二者相同,那么就可以新值 B 赋予目标值。

在 Windows 和 .NET 平台,由于历史原因,CAS 被写做 Interlocked API。原子操作在 Intel 架构 CPU 对应的汇编指令有 XCHG、CMPXCHG、INC 等,当然还得加上 LOCK 作为前缀。

>>> 阅读全文

 

, , ,