深入探索并发编程系列(三)-自己动手实现轻量级锁

在上一篇文章中，我强调了使用轻量级锁的重要性。还提到如果你能容忍某些弊端的话，自己动手实现轻量级锁也是可以的。

为什么要这么做呢？ 在过去，一些平台(如BeOS)的本地API中并没有提供轻量级锁的实现。如今，这已经不再是要担心的问题了。那我还要重点提这些主要是觉得深入了解同步原语的实现很有意思。作为一个好奇心比较重的人，我就这么做了，实现的轻量级锁在非竞争条件下相比Windows Critical Section能减少50%的开销。[更新：更进一步研究表明，在高竞争条件下，Windows Critical Section的表现还是要好很多]。

准确地说，有许多方法可以完全在用户空间下实现互斥量(锁)，每种方法也都有自己的tradeoffs：

• Spin锁. 采用一种忙则等待的策略。可能会浪费CPU时间，最坏的情况是当多个线程运行在同一个CPU核时会导致活锁^注1。尽管如此，一些程序员也已经在一些特定场景下找到了当切换到spin锁如何加速的方法。^注2
• Peterson算法. 像是为两个线程准备的spin锁^注3。可以说是一个很巧妙的技巧，但似乎在当今平台上并没什么用处。值得注意的是由于Bartosz Milewski 在讨论x86内存模型细节的时候将Peterson算法作为案例研究(case study).其他人也在类似的语境下讨论过Peterson算法
• Charles Bloom写了篇很长的文章讨论不同锁的实现。文章提供了非常有价值的信息，但对那些对C++ 11原子库和Relacy不熟悉的人来说可能会望而却步。

其中不乏非常先进的实现^注4。本文则介绍一种相对简单的技术，会用到信号量和一些原子操作。当我写锁不慢;锁竞争慢这篇文章时突然想到了这种方法,但不久后发现在1996年就已经有人用过了，那时候一些工程师把它叫做Benaphore. 下面是其在Win32平台下的C++实现(假设你使用的是X86 CPU架构).

#include <windows.h>
#include <intrin.h>

class Benaphore
{
private:
    LONG m_counter;
    HANDLE m_semaphore;

public:
    Benaphore()
    {
        m_counter = 0;
        m_semaphore = CreateSemaphore(NULL, 0, 1, NULL);
    }

    ~Benaphore()
    {
        CloseHandle(m_semaphore);
    }

    void Lock()    {
    
        if (_InterlockedIncrement(&m_counter) > 1) // x86/64 guarantees acquire semantics
        {
            WaitForSingleObject(m_semaphore, INFINITE);
        }
    }

    void Unlock()    {
    
        if (_InterlockedDecrement(&m_counter) > 0) // x86/64 guarantees release semantics
        {
            ReleaseSemaphore(m_semaphore, 1, NULL);
        }
    }
};

这种实现也可以作为对原子操作的简单介绍，它是许多无锁算法的核心。

_InterlockedIncrement是Win32平台下的原子读改写(read-modify-write(RMW))操作^注5. 在同一块数据上，如果多个线程同时执行原子RMW操作，需要排队等候，每次执行其中一个线程。这样一来，也能推断出到底发生了什么以确保正确性。它也能工作在多核与多处理器系统上。

每个现代处理器都提供了一些原子RMW指令，尽管其工具链提供的API在返回值上可能代表不同的含义。在Win32平台下，_InterlockedIncrement对整型数据执行加1操作并返回更新后的整型值。m_counter被初始化为0，第一个调用Lock的线程会从_InterlockedIncrement中得到返回值1. 这样就会跳过WaitForSingleObject调用，并立即返回。这把锁现在属于这个线程了，生活如此美好！

如果另一个线程调用Lock，而此时第一个线程正持有这把锁，此线程将会从_InterlockedIncrement中得到返回值2。这就意味着这把锁现在处于忙碌状态。此时，再继续执行下去是不安全的，我们只好自食其果，让其跳转到某个开销比较大的内核调用中：WaitForSingleObject 。其会对信号量执行减1操作。我们在CreateSemaphore中将信号量初始化为0，因此此线程现在会被强制等待直到另一个线程出现并将信号量增加，才能继续执行。

下一步，假设第一个线程调用Unlock。_InterlockedDecrement的返回值就是1. 这就意味着另一个线程正在等待这把锁，此时我们必须使用ReleaseSemaphore增加信号量。第二个线程才能继续执行，并拿到锁的持有权。

尽管时间很短，在第二个线程调用WaitForSingleObject之前第一个线程会调用ReleaseSemaphore，所有的过程都会正常执行。如果你此时添加第三个线程，第四个线程或者任意数量的线程，也无所谓。为了更好的测试，你可以在实现中增加一个TryLock函数

bool TryLock(){

    LONG result = _InterlockedCompareExchange(&m_counter, 1, 0);
    return (result == 0);
}

性能与弊端

你可能已经注意到_InterlockedIncrement前面的下划线。这是InterlockedIncrement的编译器独有版本. 它会在适当的地方输出lock xadd指令。由于Lock正好定义在Benaphore类内部，编译器将其看作是一个内联函数。当调用Benaphore::Lock的时候，编译器在默认的发行版设置会将其编译成10条指令，而在无竞争的情况下，则不会出现函数调用。以下是反汇编代码：

在无竞争的情况下，Benaphore甚至比Win32平台下的Critical Section性能还要好。就像我在上一篇文章对Mutex和Critical Section做过的测试一样，我也测试了Benaphore在无竞争情况下一对lock/unlock操作的时间。结果如下：

在Win32平台下，如果你有一个程序每秒钟使用一百万次锁，Benaphore的实现能将程序整体的性能提升几个百分点。 如果你使用原子操作的常规版本而非内置版本，会发生一次跳转到kernel32.dll，这是Benaphore就没什么优势了：在我的多核处理器上测试需要49.8ns.

并且，只要修改部分代码，你就可以在进程间共享Benaphore–这是Critical Section无法做到的。这时你必须将m_counter变量放进共享内存,并使用一个已经命名的信号量。然而，依赖于你使用的实例情况，这可能会破坏隔离进程的初衷。如果一个进程在不恰当的时间终止，可能会将Benaphore置于一种不一致的状态，然后终止其它进程.

这种实现是不可递归的.如果一些线程试图将同一个Benaphore锁上两次，就会出现死锁情况。我会在下一篇文章中，将这种实现扩展成可递归的.

如果将这些代码放到另一种CPU架构中运行，比如Xbox 360或者多核的i0S设备，必须把_InterlockedIncrement宏替换成可以显示提供acquire和release语义的东西。

最后，如果你将Benaphore应用到其它平台，要当心它可能会出现优先级反转(priority inversion)问题^注6。举个例子，MacOS X和Linux在使用POSIX锁的时候通过优先级继承机制能避免优先级反转问题。 如果你使用的是Benaphore,会绕过这种操作系统机制，这并不会帮到你。但在Windows上情况是不一样的：不管你使用哪种同步原语，Windows都会通过提升饥饿进程的优先级来避免优先级反转问题。^注7

译者注

注1：考虑单处理器上运行两个线程A和B，其中A持有spin lock；而B的优先级较高，当B在自旋时，由于它具有较高的优先级，导致A得不到调度因此无法释放锁，于是B也无法获得锁，出现活锁。

注意到作者说的是最坏的情况，实际上上述所说的这种情况一般不会出现，因为一般来说现代操作系统对线程的管理中，除了优先级之外还有时间片机制，不会出现A得不到调度的情况。

不知道作者所说的活锁是不是这种情况。如果我所说有错，恳请读者指正。

注2：一般说来，在实现spin lock的时候有一些优化的点。首先，需要区分单处理器和多处理器的情况；其次，在多处理器下，在自旋的过程中，随着尝试拿锁的失败次数越来越多，拿锁的间隔也应该越来越长，常用的是Exponential Backoff策略，间隔呈指数级上升。pause指令也常常在这个地方被使用，一是为了优化性能(和cpu指令预取有关)，二是节能减排。

注3：peterson算法原先是为两个线程互斥访问而设计的算法，它的出发点和核心是仅仅使用store和load(写读操作，不使用CAS也就是compare and swap原子操作等)来实现互斥访问。由于在现有体系结构下，为了性能，乱序执行已经是常态，因此仅仅使用读写操作而不用其他的机制例如Memory Barrier来实现peterson算法非常困难，再加上推广到多个线程的方法并不明显，因此在业界鲜为人用。

注4：实现spin lock的算法非常多，在《The Art Of Multiprocessor Programming》这本书的第七章中有详细的介绍，当contention非常严重的情况下，一种称为MCS Queue Lock的实现非常高效。另外，在实现spin lock的时候除了性能，还需要考虑多方面的指标：是否公平？是否满足先来先服务？scalability如何？等等等等。在保证公平这点上，Ticket Lock是妇孺皆知的算法，但是具有较差的scalability，更多细节感兴趣的朋友可以参考这篇论文。

注5：RMW中，有家喻户晓的CAS(Compare And Swap)、TAS(Test And Set)、FAA(Fetch And Add)等。为了实现这些原子变量，早期的Intel CPU使用锁住总线的方式(正如大家在很多资料中看到的)；现在，一般使用cache一致性来实现，先把其他CPU上对应的cache line都invalid掉，然后修改该变量的CPU把自己的cache line置为exclusive，就可以放心的更改了。

注6：为了解释优先级反转，考虑三个线程A、B、C，优先级分别为高中低。假设某时刻线程C持有锁，然后它被相对较高优先级的、cpu密集的线程B给抢占。当具有最高优先级的A尝试获得锁时，就反而被比它优先级低的B给block住了。这就是优先级反转。为了避免这种情况，除了文中介绍的常用的优先级继承这种机制外，简单的做法是线程持有spin lock的时候禁止抢占，而linux下则可以通过futex这种基础设施来避免优先级反转。

注7：本文都是考虑Windows下的实现，我们不妨一起来看看在Linux + X86下，如何利用gcc这种伟大的编译器来实现自己的锁。

不考虑scalability和性能，下面的非常简短的代码是一个简单spin lock实现：

int flag = 0;
void lock(){

  while(__sync_lock_test_and_set(&flag, 1)) {
  }
}
void unlock(){

  __sync_lock_release(&flag, 0);
}

当然，也可以通过gcc内置的__sync_bool_compare_and_swap来实现，更多原子操作可以参考这里。

为了实现一个忙则睡眠的锁，可以使用futex，不过相比，这里面的水就非常深了。以下是抛砖引玉的实现：

#include<linux/futex.h>
#include<unistd.h>
#include<sys/syscall.h>
#define CAS(address, a, b) __sync_bool_compare_and_swap(address, a, b)
#define ACCESS_ONCE(x) (*((volatile __typeof__(x) *) &x))
class MyMutex
{
public:
  MyMutex()
  {
    val = 0;
  }
  void lock()  {
  
    if (CAS(&val, 0, 1)) {
      return;
    }
    do {
      if (ACCESS_ONCE(val) == 2 || CAS(&val, 1, 2)) {
        sys_futex(&val, FUTEX_WAIT_PRIVATE, 2, NULL, NULL, 0);
      }
    } while (!CAS(&val, 0, 2));
  }
  void unlock()  {
  
    if (__sync_fetch_and_add(&val, -1) != 1) {
      val = 0;
      sys_futex(&val, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
    }
  }
private:
  static long sys_futex(void *addr1, int op, int val1, struct timespec *timeout, void *addr2, int val3)  {
  
    return syscall(SYS_futex, addr1, op, val1, timeout, addr2, val3);
  }
private:
  int val;
};

免责声明：自己拨弄futex不是一个好主意，慎重。这里提供的代码仅供参考和提供进一步学习的方向，不对正确性和安全性负责。如果用于生产环境出了问题，我们不承担任何责任。

Acknowledgement

本文由 Diting0x 与 睡眼惺忪的小叶先森 共同完成，在原文的基础上添加了许多精华注释，帮助大家理解。

感谢好友小伙伴-小伙伴儿 与skyline09_ 阅读了初稿，并给出宝贵的意见。

原文： http://preshing.com/20120226/roll-your-own-lightweight-mutex/

本文遵守Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0)
仅为学习使用，未经博主同意，请勿转载
本系列文章已经获得了原作者preshing的授权。版权归原作者和本网站共同所有