Update on 2012-12-26: 加入了跟 pthread mutex 的比较，伸缩性胜过其他 spinlock。用户态程序想要有更好的伸缩性关键还是在设计时避免共享，同步原语无特殊需要还是直接使用现成的吧。更多介绍请参考我的另一篇博文。

Update on 2013-03-22: 解决问题的关键还是在避免竞争，让锁变得可伸缩只不过可以晚一点对程序中引起竞争的部分进行改写。

Update on 2014-02-14: 基于 cmpxchg 的 spinlock 性能差的原因是我实现的问题。在尝试拿锁失败之后应该等待锁被释放之后再尝试拿锁，而现在的实现会马上再次尝试拿锁。由于 cmpxchg 是写操作，每次执行都要申请独占 cache line，因此多个核竞争时会产生大量的 cache traffic，导致锁的伸缩性非常差。改成等待锁释放之后再尝试拿锁之后 cmpxchg 的性能就与 xchg 的相似了。

之前自己写的程序遇到了伸缩性问题，怀疑是自己实现的锁在使用的核数增加时会产生严重的竞争，所以对这篇 Spinlocks and Read-Write Locks 里介绍的各种 spinlock 测试了下性能。(当然，根本的办法是避免在锁上竞争，比较 spinlock 实现的性能更多是出于好奇。)

各种 spinlock 的实现和测试程序都在 github 上。（除了 cmpxchg 以外都是 copy 那篇文章里的。）为了使用方便，spinlock 所需要的原子指令等都在各自的头文件里。

首先要说明的是，下面的测试结果以及结论依赖于具体的 CPU。选择 spinlock 的实现的时候还是要自己测试一下。

测试程序非常简单，多个线程做 counter++ 操作，保证总的 lock/unlock 操作数相等，以此来测试 lock/unlock 操作的开销，counter 只是用来验证 spinlock 实现的正确性。

在给出测试结果之前，先对各个 spinlock 的实现做简单的说明，Spinlocks and Read-Write Locks 中有详细的说明。

• 最简单的两个实现分别是用 cmpxchg 和 xchg 指令，其中 cmpxchg 需要加 lock prefix 保证原子性，而 xchg 指令执行的时候会自动加 lock (简化的描述，实际情况参考 Intel 的文档。)

• Ticket spinlock 是 Linux 内核里使用的一种 spinlock，保证先到先得的顺序拿锁，保证公平性

• MCS spinlock 设计的目的是防止竞争严重时产生大量的处理器总线开销而降低性能。

  普通的 spinlock lock/unlock 使用的是同一个内存地址，多个 core 同时访问时需要由 cache coherence protocol 来保证每个 core 从各自的 cache 里看到的都是正确的数据。当竞争严重时会产生大量的 cache coherence message。

  MCS spinlock 设计的关键是让每个等待拿锁的 core 在自己的等待变量上 spin，这个变量只会出现在自己 cache 中，从而减少了 cache coherence message。

• K42 spinlock 解决了 MCS spinlock 的接口需要多传递一个等待变量的问题。简单来说它把 lock 函数桟上的内容作为等待变量，其实现与 MCS spinlock 非常相似。

我在一台有 4 颗 Intel Xeon CPU, 10 cores/CPU（一共 40 核）运行 Debian 6 的服务器上运行了测试程序，测试方法如下：

• 每种 spinlock 实现都测试使用 1, 2, 4, 8, 16, 32 个线程的执行时间，执行三遍取平均数
• 测试分成两组：
  • 由 OS 控制线程在哪个核上执行
  • 绑定线程到特定的 core 上，目标是使用尽可能少的 CPU。这么做是考虑到单个CPU 内部的 cache coherence message 开销比跨 CPU 的开销要小很多。
• 只统计某一个线程的执行所有 lock/unlock 操作的时间
  • 为了让所有的线程基本上同时开始执行，用了一个 ad hoc 的同步，这可能对统计整个程序执行时间造成影响
  • 尽可能忽略程序启动和退出的时间的影响
  • 统计单个线程的时间可能不太精确，但对于比较伸缩性来说应该足够

下面是运行时间的测试结果，标记 bind core 的为绑定核的测试结果。ticket spinlock 由于运行时间比较长，单独在一张图中给出。另外单独分析一个程序的数据比较容易看清问题，所以先分析 ticket spinlock 的运行数据。

• 先看第一张图中绑核的结果（绿色），注意到绑定在单个 CPU 8 核到两个 CPU 16 核运行时间的明显上升，而从 2~8 个核时间变化不大。猜想 ticket spinlock 的伸缩性取决于竞争的 CPU 的数目。主要原因是跨 CPU 的cache coherence 开销远大于 CPU 内部的开销。从 16 核到 32 核的运行时间上升也体现了这一点。

• 为了验证上面的结论，进行了另外的测试：使用 10 个核，但采用不同的绑定方式。9+1 代表把 9 个线程绑定在一个 CPU 的 9 个核上，而第十个线程绑定在另一个 CPU 上； 8+2, 7+3 以此类推。

  从结果来看，的确是随着使用的 CPU 数量增加，运行时间增加。

• 再来看不绑核的情况。2 个线程的时间跟 9+1 的接近，而 4 线程及以上的时间几乎相同，都接近于 7+3 的时间。

  结合 htop 来看执行测试时的 CPU 使用情况，默认情况下 Linux 会把线程放到不同的 CPU 上执行。这种方式可以避免线程/进程间的 cache 污染，同时也可以利用更多的 CPU cache，但是对这种 lock contention 严重的情况来说，这种策略不是最优的。

分析完 ticket spinlock，再来看其他 spinlock 实现的运行时间情况：

从上面的两张图里可以看到：

• xchg 实现的 spinlock 无论是否绑核，性能都很好，且没有严重的伸缩性问题
• cmpxchg 无论是在单个还是多个 CPU 之间竞争，随着核数的增多，性能会变得很差
• MCS 和 K42 的伸缩性类似 ticket spinlock，也取决于竞争的 CPU 的数目。而且由于自身的复杂性，在使用的核数少的时候其性能相比 cmpxchg 也并没有优势。

总的来说：

• 实现 spinlock 还是用 xchg 最为高效且不用担心伸缩性的问题
• 尽量避免 cmpxchg
• 如果不要求公平性，避免 ticket spinlock
• MCS, K42 本身过于复杂，性能相比其他锁要差。这可能是它们没有被广泛使用的原因吧。也可能以前的 CPU cache coherence 实现的比较差，在核数多的情况下它们的性能更好