Lock-Free 编程


文章索引

  • Lock-Free 编程是什么?
  • Lock-Free 编程技术
    • 读改写原子操作(Atomic Read-Modify-Write Operations)
    • Compare-And-Swap 循环(CAS Loops)
    • ABA 问题(ABA Problem)
  • 内存模型(Memory Model)对细粒度锁的影响
  • 代码实践
    • 实现普通的栈 SimpleStack 类
    • 实现普通的加锁的栈 SimpleLockedStack 类
    • 实现 Lock-Free 的栈 LockFreeStack 类
    • 实现 ConcurrentStack 类

Lock-Free 编程的一部分内容。本质上说,Lock-Free 编程仅描述了代码所表述的性质,而没有限定或要求代码该如何编写。

基本上,如果程序中的某一部分符合下面的条件判定描述,则我们称这部分程序是符合 Lock-Free 的。反过来说,如果某一部分程序不符合下面的条件描述,则称这部分程序是不符合 Lock-Free 的。

从这个意义上来说,Lock-Free 中的 "Lock" 并没有直接涉及 Mutex 或 Lock 等互斥量结构,而是描述了应用程序因某种原因被锁定的可能性,例如可能因为死锁(DeadLock)、活锁(LiveLock)或线程调度(Thread Scheduling)导致优先级被抢占等。

Lock-Free 编程的一个重要效果就是,在一系列访问 Lock-Free 操作的线程中,如果某一个线程被挂起,那么其绝对不会阻止其他线程继续运行(Non-Blocking)。

下面的这段简单的程序片段中,没有使用任何互斥量结构,但却不符合 Lock-Free 的性质要求。如果用两个线程同时执行这段代码,在线程以某种特定的调度方式运行时,非常有可能两个线程同时陷入死循环,也就是互相阻塞了对方。

  while (x == 0)
  {
    x = 1 - x;
  }

所以说,Lock-Free 编程所带来的挑战不仅来自于其任务本身的复杂性,还要始终着眼于对事物本质的洞察。

通常,应该没有人会期待一个大型的应用程序中全部采用 Lock-Free 技术,而都是在有特定需求的类的设计上采用 Lock-Free 技术。例如,如果需要一个 Stack 类应对多线程并发访问的场景,可以使用 Lock-Free 相关技术实现 ConcurrentStack 类,在其 Push 和 Pop 操作中进行具体的实现。所以,在使用 Lock-Free 技术前,需要预先考虑一些软件工程方面的成本:

  • Lock-Free 技术很容易被错误的使用,代码后期的维护中也不容易意识到,所以非常容易引入 Bug,而且这样的 Bug 还非常难定位。
  • Lock-Free 技术的细节上依赖于内存系统模型、编译器优化、CPU架构等,而这在使用 Lock 机制时是不相关的,所以也增加了理解和维护的难度。

Compare-And-Swap (CAS) 方式来实现;
  • PowerPC、MIPS 和 ARM 架构通过 Load-Link/Store-Conditional (LL/SC) 方式来实现;
  • 例如在 x86 架构下,通过 LOCK 指令前缀可以使许多指令操作(ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, and XCHG)变成原子操作,其中 CMPXCHG 指令可用于实现 CAS 操作。

    下面是使用 LOCK 和 CMPXCHG 来实现 CAS 操作的代码示例。

    __inline int CAS(volatile int & destination, int exchange, int comperand)
    {
      __asm {
        MOV eax, comperand
        MOV ecx, exchange
        MOV edx, destination
        LOCK CMPXCHG[edx], ecx /* 如果eax与edx相等, 则ecx送edx且ZF置1;
                                  否则edx送ecx, 且ZF清0.*/
      }
    }
    
    /* Accumulator = AL, AX, EAX, or RAX depending on 
       whether a byte, word, doubleword, or
       quadword comparison is being performed */
    
    IF accumulator = DEST
      THEN
        ZF ← 1;
        DEST ← SRC;
      ELSE
        ZF ← 0;
        accumulator ← DEST;
    FI;

    _InterlockedCompareExchange 等。对 RMW 操作最常见的讨论可能就是,如何通过 CAS Loops 来完成对事务的原子处理。

    通常,开发人员会设计在一个循环中重复地执行 CAS 操作以试图完成一个事务操作。这个过程分为 3 步:

    1. 从指定的内存位置读取原始的值;
    2. 根据读取到的原始的值计算出新的值;
    3. 检测如果内存位置仍然是原始的值时,则将新值写入该内存位置;

    例如,向 LockFreeStack 中压入新的节点:

     1 void LockFreeStack::Push(Node* newHead)
     2 {
     3   for (;;)
     4   {
     5     // Read the original value from a memory location.
     6     // Copy a shared variable (m_Head) to a local.
     7     Node* oldHead = m_Head;
     8 
     9     // Compute the new value to be set.
    10     // Do some speculative work, not yet visible to other threads.
    11     newHead->next = oldHead;
    12 
    13     // Set the new value only if the memory location is still the original value.
    14     // Next, attempt to publish our changes to the shared variable.
    15     // If the shared variable hasn't changed, the CAS succeeds and we return.
    16     // Otherwise, repeat.
    17     if (_InterlockedCompareExchange(&m_Head, newHead, oldHead) == oldHead)
    18       return;
    19   }
    20 }

    上面代码中的循环操作仍然符合 Lock-Free 条件要求,因为如果 _InterlockedCompareExchange 条件测试失败,也就意味着另外的线程已经成功修改了值,而当前线程可以再下一个循环周期内继续判断以完成操作。

    ABA 问题。

    若线程对同一内存地址进行了两次读操作,而两次读操作得到了相同的值,通过判断 "值相同" 来判定 "值没变"。然而,在这两次读操作的时间间隔之内,另外的线程可能已经修改了该值,这样就相当于欺骗了前面的线程,使其认为 "值没变",实际上值已经被篡改了。

    下面是 ABA 问题发生的过程:

    1. T1 线程从共享的内存地址读取值 A;
    2. T1 线程被抢占,线程 T2 开始运行;
    3. T2 线程将共享的内存地址中的值由 A 修改成 B,然后又修改回 A;
    4. T1 线程继续执行,读取共享的内存地址中的值仍为 A,认为没有改变然后继续执行;

    由于 T1 并不知道在两次读取的值 A 已经被 "隐性" 的修改过,所以可能产生无法预期的结果。

    例如,使用 List 来存放 Item,如果将一个 Item 从 List 中移除并释放了其内存地址,然后重新创建一个新的 Item,并将其添加至 List 中,由于优化等因素,有可能新创建的 Item 的内存地址与前面删除的 Item 的内存地址是相同的,导致指向新的 Item 的指针因此也等同于指向旧的 Item 的指针,这将引发 ABA 问题。

    举个更生活化的例子:

    土豪拿了一个装满钱的 Hermes 黑色钱包去酒吧喝酒,将钱包放到吧台上后,转头和旁边的朋友聊天,小偷趁土豪转头之际拿起钱包,将钱包里的钱取出来并放入餐巾纸保持钱包厚度,然后放回原处,小偷很有职业道德,只偷钱不偷身份证,土豪转过头后发现钱包还在,并且还是他熟悉的 Hermes 黑色钱包,厚度也没什么变化,所以土豪认为什么都没发生,继续和朋友聊天,直到结账时发现钱包中的钱已经被调包成餐巾纸。

    所以,我觉得 ABA 问题还可以被俗称为 "调包问题"。那么怎么解决 "调包问题" 呢?土豪开始想办法了。

    土豪想的第一个办法是,找根绳子将钱包绑在手臂上,要打开钱包就得先把绳子割断,割绳子就会被发现。这种做法实际上就是 Load-Link/Store-Conditional (LL/SC) 架构中所做的工作。

    土豪想的另一个办法是,在钱包上安个显示屏,每次打开钱包显示屏上的数字都会 +1,这样当土豪在转头之前可以先记录下显示屏上的数字,在转过头后可以确认数字是否有变化,也就知道钱包是否被打开过。这种做法实际上就是 x86/64 架构中 Double-Word CAS Tagging 所做的工作。

    土豪还担心小偷下次会不会买一个一模一样的钱包,直接调包整个钱包,这样连银行卡和身份证都丢了怎么办,土豪决定买一个宇宙独一无二的钱包,除非把它给烧了,否则就不会再有相同的钱包出现。这种做法实际上就是 Garbage Collection (GC) 所做的工作。

    顺序一致性内存模型(Sequential Consistency Memory Model)则是内存模型规范中的一种。在这个模型中,内存与访问它的线程保持独立,通过一个控制器(Memory Controller)来保持与线程的联系,以进行读写操作。在同一个线程内的,读写操作的顺序也就是代码指定的顺序。但多个线程时,读写操作就会与其他线程中的读写操作发生交错。

    如上图中所示,Thread 1 中在写入 Value 和 Inited 的值,而 Thread 2 中在读取 Inited 和 Value 的值到 Ri 和 Rv 中。由于在内存控制器中发生重排(Memory Reordering),最终的结果可能有很多种情况,如下表所示。

    顺序一致性内存模型非常的直观,也易于理解。但实际上,由于该模型在内存硬件实现效率上的限制,导致商用的 CPU 架构基本都没有遵循该模型。一个更贴近实际的多处理器内存模型更类似于下图中的效果。

    也就是说,每个 CPU 核都会有其自己的缓存模型,例如上图中的 Level 1 Cache 和 Level 2 Cache,用以缓存最近使用的数据,以提升存取效率。同时,所有的写入数据都被缓冲到了 Write Buffer 缓冲区中,在数据在被刷新至缓存前,处理器可以继续处理其他指令。这种架构提升了处理器的效率,但同时也意味着我们不仅要关注 Memory,同时也要关注 Buffer 和 Cache,增加了复杂性。

    上图所示为缓存不一致问题(Incoherent Caches),当主存(Main Memory)中存储着 Value=5,Inited=0 时,Processor 1 就存在着新写入 Cache 的值没有被及时刷新至 Memory 的问题,而 Processor 2 则存在着读取了 Cache 中旧值的问题。

    显然,上面介绍着内存重排和缓存机制会导致混乱,所以实际的内存模型中会引入锁机制(Locking Protocol)。通常内存模型会遵循以下三个规则:

    • Rule 1:当线程在隔离状态运行时,其行为不会改变;
    • Rule 2:读操作不能被移动到获取锁操作之前;
    • Rule 3:写操作不能被移动到释放锁操作之后;

    Rule 3 保证了在释放锁之前,所有写入操作已经完成。Rule 2 保证要读取内存就必须先获取锁,不会再有其他线程修改内存。Rule 1 则保证了获得锁之后的操作行为是顺序的。

    在体现锁机制(Locking Protocol)的价值的同时,我们也会意识到它所带来的限制,也就是限制了编译器和 CPU 对程序做优化的自由。

    我们知道,.NET Framework 遵循 ECMA 标准,而 ECMA 标准中则定义了较为宽松的内存访问模型,将内存访问分为两类:

    • 常规内存访问(Ordinary Memory Access)
    • 易变内存访问(Volatile Memory Access)

    其中,易变内存访问是特意为 "volatile" 设计,它包含如下两个规则:

    1. 读和写操作不能被移动到 volatile-read 之前;
    2. 读和写操作不能被移动到 volatile-write 之后;

    对于那些没有使用 "lock" 和 "volatile" 的程序片段,编译器和硬件可以对常规内存访问做任何合理的优化。反过来讲,内存系统仅需在应对 "lock" 和 "volatile" 时采取缓存失效和刷新缓冲区等措施,这极大地提高了性能。

    顺序一致性(Sequential Consistency)的要求描述了程序代码描述的顺序与内存操作执行的顺序间的关系。多数编程语言都提供顺序一致性的支持,例如在 C# 中可以将变量标记为 volatile。

    A volatile read has "acquire semantics" meaning that the read is guaranteed to occur prior to any references to memory that occur after the read instruction in the CIL instruction sequence.
    A volatile write has "release semantics" meaning that the write is guaranteed to happen after any memory references prior to the write instruction in the CIL instruction sequence.

    下面的列表展示了 .NET 中内存读写操作的效果。

    Construct

     Refreshes 

    Thread

    Cache

    Before?

     Flushes 

    Thread

    Cache

    After?

    Notes

     Ordinary Read

     No

    No

    Read of a non-volatile field

     Ordinary Write 

     No 

    Yes

    Write of a non-volatile field

     Volatile Read

     Yes

    No

    Read of volatile field,

    or Thread.VolitelRead

     Volatile Write

     No

    Yes

    Write of volatile field

     Thread.MemoryBarrier 

     Yes

    Yes

    Special memory barrier method

     Interlocked Operations

     Yes

    Yes

    Increment, Add, Exchange, etc.

     Lock Acquire

     Yes

    No

    Monitor.Enter

    or entering a lock {} region

     Lock Release

     No

    Yes

    Monitor.Exit

    or exiting a lock {} region

    Lock-Free 编程,方能洞察机制的本质,加深理解。下面用实现栈 Stack 类的过程来完成对 Lock-Free 编程的探索。

    栈结构实际上就是 FILO 先入后出队列,通常包括两个操作:

    • Push:向栈顶压入一个元素(Item);
    • Pop:从栈顶弹出一个元素(Item);

    这里我们选用单链表结构(Singly Linked List)来实现 FILO 栈,每次入栈的都是新的链表头,每次出栈的也是链表头。

    Interlocked.CompareExchange 方法,该操作是原子的,并且有很多重载方法可供使用。

    1     private static bool CAS(
    2       ref Node location, Node newValue, Node comparand)
    3     {
    4       return comparand ==
    5         Interlocked.CompareExchange>(
    6           ref location, newValue, comparand);
    7     }

    在实现 CAS Loops 时,我们使用 do..while.. 语法来完成。

     1     public void Push(T item)
     2     {
     3       Node node = new Node();
     4       node.Item = item;
     5 
     6       do
     7       {
     8         node.Next = _head.Next;
     9       }
    10       while (!CAS(ref _head.Next, node, node.Next));
    11     }

    这样,新的 LockFreeStack 类就诞生了。

     1   public class LockFreeStack
     2   {
     3     private class Node
     4     {
     5       public Node Next;
     6       public TNode Item;
     7       public override string ToString()
     8       {
     9         return string.Format("{0}", Item);
    10       }
    11     }
    12 
    13     private Node _head;
    14 
    15     public LockFreeStack()
    16     {
    17       _head = new Node();
    18     }
    19 
    20     public void Push(T item)
    21     {
    22       Node node = new Node();
    23       node.Item = item;
    24 
    25       do
    26       {
    27         node.Next = _head.Next;
    28       }
    29       while (!CAS(ref _head.Next, node, node.Next));
    30     }
    31 
    32     public T Pop()
    33     {
    34       Node node;
    35 
    36       do
    37       {
    38         node = _head.Next;
    39 
    40         if (node == null)
    41           return default(T);
    42       }
    43       while (!CAS(ref _head.Next, node.Next, node));
    44 
    45       return node.Item;
    46     }
    47 
    48     private static bool CAS(
    49       ref Node location, Node newValue, Node comparand)
    50     {
    51       return comparand ==
    52         Interlocked.CompareExchange>(
    53           ref location, newValue, comparand);
    54     }
    55   }

    这个新的类的测试结果正如我们想象也是正确的。

    System.Collections.Concurrent.ConcurrentStack 类的基本实现过程。

    参考资料

    • Non-blocking algorithm
    • ConcurrentStack Source Code
    • C# Interlocked functions as a lock mechanism?
    • InterlockedCompareExchangePointer Intrinsic Functions 
    • Improve efficiency and fairness when combining temporally close events
    • SpinWait and Lock-Free code
    • LOCK-FREE DATA STRUCTURES: THE STACK
    • THE ABA PROBLEM
    • Interlocked operations don't solve everything
    • Volatile keyword in C# – memory model explained
    • What Interlocked.CompareExchange is used for in the dapper .net method?
    • Benefits, drawbacks of lock-free programming for multicore
    • Understand the Impact of Low-Lock Techniques in Multithreaded Apps
    • Concurrency : What Every Dev Must Know About Multithreaded Apps
    • Designing Applications for High Performance - Part II
    • Intel? 64 and IA-32 Architectures Software Developer’s Manual Volume 2A
    • x86 Instruction Set Reference - CMPXCHG
    • An Introduction to Lock-Free Programming
    • Lock-Free Programming
    • Understanding Atomic Operations
    • Introduction to Lock-free Programming with C++ and Qt
    • ECMA C# and Common Language Infrastructure Standards
    • Lock-Free Concurrent Data Structures, CAS and the ABA-Problem
    • 透过 Linux 内核看无锁编程
    • 无锁队列的实现
    • Implementing Lock-Free Queues
    • 用于并行计算的多线程数据结构,第 2 部分: 设计不使用互斥锁的并发数据结构
    • Yet another implementation of a lock-free circular array queue
    • Writing Lock-Free Code: A Corrected Queue

    本文《Lock Free 编程》由作者 Dennis Gao 发表自博客园博客,任何未经作者本人允许的人为或爬虫转载均为耍流氓。