并发编程的艺术04-TAS自旋锁

3 年前

黑帽子技术

本章会介绍自旋锁的概念以及TAS(test-and-set),TTAS(test-test-and-set),BackoffLock自旋锁算法，并深入讨论这些算法优缺点。文中会结合生活举例，代码，图示，图表说明帮助读者理解。

什么是自旋锁

首先让我来理解"自旋"这个术语名词，其实自旋这个词可以理解为一种行为。下面来举一个生活中的例子来说明什么叫"自旋"。

大多数人可能都遇到过这样的场景，当你去理发店想要剪头发的时候，发现店里人很多没有空的位子不少人都在等待。这时候你该怎么办呢？这时候你会如何做决定？通常情况下有两种选择：

和其他人一样在理发店里等待直到有空闲的理发师来给你剪头发。
不在理发店等待而是去做别的事情，过一段时间再过来理发店看一看有没有位置。

很显然这是两种不同的处理方式， 其中第一种处理方式就称为“自旋”或是“忙等待” 。我们在接着讨论这个问题，当你询问服务人员前面还有几个人的时候（其实你是在询问自己需要等待的时长），大多数人会根据服务人员所给的答案决定是否继续等待，如果前面排队的人少说明等待的时间少值得等待，如果人太多说明等待需要消耗大量时间，这时候就不值得等待了。这时候你很可能就选择第二种处理方法，先搁置剪头发这件事，转而先去做别的事情。

在抽象层面讨论了自旋后，现在我们回到计算机世界中。任何的互斥协议都会产生这样的问题：如果不能获得锁，应该怎么做？对此我们有两种选择：

1. 让其继续尝试，这种称为自旋锁，对锁的反复测试过程称为自旋或忙等待。（在希望锁延迟较短的情形下，选择自旋的方式似乎比较合理）

2. 挂起自己，请求操作系统的线程调度器调度另外一个线程，这种方式称为阻塞。从一个线程切换到另一个线程的代价较大（涉及到 switch_context）,所以只有在允许锁延迟较长的情形下，阻塞才有意义。

TASLock & TTASLock

TAS（test-and-set）, test-and-set 是早期多处理器系统结构提供的主要同步指令。java 中的 getAndSet() 就如同传统的 test-and-set 指令。

public class TASLock implements Lock {
    AtomicBoolean state = new AtomicBoolean(false);
    public void lock() {
        while (state.getAndSet(true)) {
    public void unlock() {
        state.set(false);
}

TTAS (test-test-and-set)

public class TTASLock implements Lock {
    AtomicBoolean state = new AtomicBoolean(false);
    public void lock() {
        while (true) {
            while (state.get()) {
           if (! state.getAndSet(true)) {
               return;
    public void unlock() {
        state.set(false);
}

TAS & TTAS 深入分析

TAS & TTAS 正确性是一样的，都保障了无死锁的互斥，但是性能却存在着显著差异。接下来我们主要探究为什么会存在这样的性能差异。

首先我们会简要介绍以下基于共享总线的计算机结构，这部分知识将有助于我们理解为什么 TAS 与 TTAS 算法之间性能差异产生的原因。

首先明确关于总线的两个知识点：

CPU 可以在总线上发送广播消息，而这个消息将被连接在总线上的其他设备接收到。
同一时刻只能有一个 CPU 占用总线。

下面我们会使用一些图片和对图片做出解释的简要文字来帮助读者理解 CPU 读写数据的过程。

上述过程简要说明了多处理器之间是如何对数据进行读/写操作的，如果你想要再深入研究可以去学习"缓存一致性协议"的相关内容，或者参考这篇文章 《带你了解缓存一致性协议MESI》 ,仔细阅读后会对上述过程有更深入的理解。

接下来还是回归到我们的话题中，为什么 TAS 的性能要比 TTAS 的性能差了这么多？根本原因是因为 TAS 每一次的执行都是在总线上发送了一个广播消息，这个消息表明执行 TAS 指令的 CPU 想要修改数据，首先需要让其他CPU缓存中的数据副本失效，然后它才可以修改这个数据。这个信息通过总线发出，所以当总线被一个线程占用后，将会延迟其他所有的线程，包括哪些没有等待锁的线程。而且这个消息发出后其他CPU接收到了该消息会删除掉它们本地缓存中的数据副本，而再次去读取的时候产生了 cache miss ，这时候就要通过总线来获取这个数据，这时候总线再次被占用。同时当某个线程试图释放锁的时候，由于总线正在被其他线程占用，释放锁的操作也被延迟了。当某个线程试图获取一个空闲的锁时也会由于总线被占用而延迟。 所以结论是：TAS算法存在着大量的总线占用，每个线程每一次自旋都会产生大量的总线流量，从而延迟其他线程（因为其他线程也需要使用总线） 。

找到了 TAS 为什么慢的原因接下来我们会分析 TTAS 的优势是什么？ TTAS ：test-test-and-set , 其实 TTAS 的优势在于第一步的 test ，test 只是执行读指令，而读取数据每次都从CPU cache 中进行读取，而不会占用总线 。不会占用总线也就不会影响到其他线程，不会导致其他线程的指令延迟。

但是 TTAS 并非完美的算法它也有缺陷，就是在释放锁的过程中，锁的持有者会将值修改为 false ，这会导致自旋线程的CPU cache 失效。这时候它们都会去执行一次 test-and-set 指令以获取锁，于是总线流量升高。第一个成功获取锁的线程会使得其他线程失效，这些失效的线程接下来又重读那个值，从而引起一场总线流量风暴。最终，所有线程归于平静，进入本地自旋（本地自旋指反复的读取CPU cache 中的值而不是使用总线）。

后退策略改进 TTASLock

首先需要说明几个专业术语：

争用：指多个线程试图获取同一个锁。
高争用：意味着存在大量正在争用的线程。
低争用：与高争用相反。

在 TTASLock 中，lock() 函数有两个步骤：

不断的读取锁检查该锁是否被释放。
当锁看似空闲时执行 test-and-set 来获取锁。

一个重要的结论：如果其他的某个线程在第一步和第二步之间获取了锁，那么该锁极有可能存在高争用 。

显然为了提高性能，我们应该避免高争用的情形。此时线程获得锁的机会非常小，因此这种尝试将会导致总线流量增加。相反如果让线程后退一段时间，给正在竞争的线程以结束的机会，将会更加有效。

public class Backoff {
    final int minDelay , maxDelay;
    int limit;
    final Random random;
    public Backoff(int min , int max) {
        minDelay = min;
        maxDelay = max;
        limit = minDelay;
       random = new Random(); 
    public void backoff() throw Exception {
        int delay = random.nextInt(limit);
        limit = Math.min(maxDelay , 2 * limit);
        Thread.sleep(delay);
public class BackoffLock implements Lock {
    AtomicBoolean state = new AtomicBoolean(false);
    private static final int MIN_DELAY = ...;
    private static final int MAX_DELAY = ...;
    public void lock() {
        Backoff backoff = new Backoff(MIN_DELAY , MAX_DELAY );
        while (true) {
            while (state.get()) {
           if (! state.getAndSet(true)) {
               return;
           } else {
               backoff.backoff();