xyZGHio

樱花同载酒，终似少年游

0%

浅谈自旋锁的Java实现

发表于 更新于 阅读数： 评论数：
本文字数： 5.9k 阅读时长 ≈ 12 分钟

本文介绍下几种常见自旋锁的Java实现，包括CLH、MCS等队列锁

abstract.jpeg

非公平自旋锁

实现一个自旋锁最朴素的思路就是直接利用CAS来保证加锁、解锁的原子性。具体到Java中，则可以利用原子类来实现。下面即是非公平自旋锁的实现，可以看到其实现过程非常简单。为了进一步支持锁重入，还提供了一个count变量记录锁重入的次数。但该实现的缺点也很明显，首先加锁线程需要不停自旋来检测锁的状态。此举会明显浪费CPU，当然这也是自旋锁方案的通用弊端；其次该实现方式是一个非公平的自旋锁，即无法保证公平性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 非公平自旋锁
 */
public class SpinLock {

    /**
     * 锁的持有者
     */
    private AtomicReference<Thread> owner = new AtomicReference<>();

    /**
     * 记录锁重入次数
     */
    private volatile int count = 0;

    public void lock() {
        Thread current = Thread.currentThread();
        // 当前线程已经持有锁, 则记录重入次数即可
        if( current == owner.get() ) {
            count++;
            return;
        }

        while ( !owner.compareAndSet(null, current) );
    }

    public void unlock() {
        Thread current = Thread.currentThread();
        if( current == owner.get() ) {
            if( count>0 ) {
                // 锁重入, 直接自减即可
                count--;
            } else {
                owner.set(null);
            }
        }
    }

}

公平自旋锁

为了解决实现自旋锁的公平性，我们需要额外引入一个排队机制。具体地，分别用两个原子变量表示排队号码、当前服务号码（即持有锁的号码）。基本原理类似于银行服务窗口的取号、叫号机制。加锁过程：会先给当前线程分配一个排队号码，然后该线程开始自旋。直到被它叫到号才退出自旋，即它的排队号码等于当前服务号码。解锁过程：计算、更新当前服务号码的值。以便下一个线程能够结束自旋、获取到锁。下面即是一个基于排队机制的公平自旋锁实现，可以看到每次调用requestTicketNum方法即可获得一个单调递增的排队号码，并通过一个ThreadLocal类型的threadLocalNum变量来保存各线程所获得的排队号码。进一步地，这里还增加了一个count变量以实现锁重入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * 公平自旋锁
 */
public class TicketLock {

    /**
     * 当前持有锁的号码
     */
    private AtomicInteger serviceNum = new AtomicInteger(0);

    /**
     * 记录锁重入次数
     */
    private volatile int count = 0;

    /**
     * 排队号码
     */
    private AtomicInteger ticketNum = new AtomicInteger(0);

    /**
     * 各线程存放自己所申请的排队号码
     */
    private static ThreadLocal<Integer> threadLocalNum = new ThreadLocal<>();

    public void lock() {
        Integer num = threadLocalNum.get();
        if( num!=null && num==serviceNum.get() ) {
            // 当前线程已经持有锁, 则记录重入次数即可
            count++;
            return;
        }

        // 申请一个排队号码
        num = requestTicketNum();
        threadLocalNum.set( num );
        // 自旋等待, 直到该排队号码与serviceNum相等
        while ( num != this.serviceNum.get() );
    }

    public void unlock() {
        Integer num = threadLocalNum.get();
        if( num!=null && num==serviceNum.get() ) {
            if( count>0 ) {
                // 锁重入, 直接自减即可
                count--;
            } else {
                threadLocalNum.remove();
                // 自增serviceNum, 以便下一个排队号码的线程能够退出自旋
                serviceNum.set( num+1 );
            }
        }
    }

    /**
     * 申请一个排队号码
     */
    private int requestTicketNum() {
        return ticketNum.getAndIncrement();
    }

}

队列锁

SMP 与 NUMA

在进一步介绍队列锁之前，我们先来了解下计算机中常见的两种体系结构：SMP、NUMA。SMP(Symmetric Multi Processing)对称多处理器结构，所谓对称指的就是多个CPU的地位是平等的、一致性的。它们共享全部的资源，包括内存、IO、总线等。所以如果多个CPU同时访问某个资源(例如某部分内存)，就需要锁机制来解决资源争用的问题。事实上，我们日常所使用的计算机大部分都是SMP结构的

而在NUMA(Non-Uniform Memory Access)非一致存储访问结构下，其基本特征是含有多个CPU模块。而每个CPU模块则由多个CPU、独立的本地内存、IO组成，各CPU模块则通过所谓的互联模块进行连接。这样一个CPU访问其自身CPU模块的本地内存的速度将远远高于访问其他CPU模块的本地内存，即所谓访问存储表现上具有非一致性

CLH队列锁

队列锁较为常见的是CLH队列锁，其由Craig、Landin 和 Hagersten三位发明，并以他们的名字缩写进行组合而命名。Java中的AQS就是使用了CLH队列锁的变体。在之前的两种自旋锁实现SpinLock、TicketLock中，实际上存在一个明显性能问题。各线程均在同一个共享变量上进行自旋，竞争非常激烈时，其会导致非常繁重的总线、内存流量。因为当一个线程释放锁、更新共享变量时，会引发其他CPU中该共享变量对应的Cache Line缓存行失效，并重新经由总线、内存读取

而CLH队列锁则是将各个加锁线程包装为Node节点并构建为一个隐式链表。各Node不断自旋检查其前驱节点的状态，当某线程进行解锁操作时，则会修改自身Node节点的状态以让其后继节点结束自旋、获取到锁。其实现过程如下所示，之所以称之为隐式链表，是因为所谓的链表事实上是通过每个线程利用ThreadLocal类型的prevNode变量保存其前驱节点来维护的。由前文可知，各线程是在其前驱节点的status变量上进行自旋的，故在构建CLH队列锁实例的过程中首先向隐式链表中添加了一个哨兵节点，以便处理第一个加锁线程。值得一提的是，在解锁过程时，执行currentNode.remove() 是必要的。其目的是为了保证该线程在下一次加锁调用lock()时，能够通过 currentNode.get() 获取到一个新的Node实例，防止死锁。至此可以看出CLH队列锁是一个公平的自旋锁实现，其次由于各线程自旋在不同Node实例的status变量上避免了繁重的总线、内存流量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class CLHLock {
    /**
     * 隐式链表的队尾指针
     */
    private AtomicReference<Node> tail;

    /**
     * 隐式链表的当前节点
     */
    private ThreadLocal<Node> currentNode;

    /**
     * 隐式链表的前驱节点
     */
    private ThreadLocal<Node> prevNode;

    public CLHLock() {
        // 向隐式链表添加第一个节点, 其是哨兵节点
        tail = new AtomicReference<>( new Node() );
        currentNode = ThreadLocal.withInitial( Node::new );
        prevNode = new ThreadLocal<>();
    }

    public void lock() {
        // 每次第一次加锁都会获取一个新的Node实例, 作为当前节点
        Node node = currentNode.get();
        node.status = true;
        // 将当前节点加入隐式链表的队尾, 具体实现方式:
        // 通过队尾指针tail获取隐式链表的队尾节点prev, 并将其作为当前节点node的前驱节点;
        // 同时将队尾指针tail 指向 当前节点node
        Node prev = tail.getAndSet( node );
        prevNode.set( prev );
        // 当前线程在其前驱节点prev的status变量上进行自旋
        // 直到前驱节点释放锁时, 其status变量修改为false结束自旋
        while( prev.status );
    }

    public void unlock() {
        // 将当前节点的status变量修改为false, 使得其后继节点能够退出自旋
        Node node = currentNode.get();
        node.status = false;

        prevNode.remove();
        // 防止死锁
        currentNode.remove();
    }

    private static class Node {
        private volatile boolean status = false;
    }
}

MCS队列锁

前面提到了CLH队列锁的各种好处，看上去好像一切都很完美。其实不然，CLH在SMP结构性下非常有效。但在NUMA结构中，如果其前驱节点不是位于该CPU自身模块的本地内存中，而是位于其他CPU模块的本地内存中，则会导致效率大幅降低。 故John M. Mellor-Crummey、Michael L. Scott提出、发明了MCS队列锁。其与CLH队列锁的最大不同在于，MCS队列锁中各加锁线程是在自身的Node节点上进行自旋。这一改进使得其在NUMA结构下也具有很好的性能表现。具体地，其同样是先将各加锁线程包装为Node节点，然后通过Node的next变量指向其后继节点来显式地维护链表。当某线程进行解锁操作时，则会通过next指针找到当前节点的后继节点，并修改后继节点的状态以让其后继节点结束自旋、获取到锁。实现过程如下所示，当然MCS队列锁同样是一个公平的自旋锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class MCSLock {
    /**
     * 链表的队尾指针
     */
    private AtomicReference<Node> tail;

    /**
     * 链表的当前节点
     */
    private ThreadLocal<Node> currentNode;

    public MCSLock() {
        tail = new AtomicReference<>(null);
        currentNode = ThreadLocal.withInitial( Node::new );
    }

    public void lock() {
        // 每次加锁获取一个新的Node实例, 作为当前节点
        Node node = currentNode.get();
        node.status = true;
        // 通过队尾指针tail获取链表的队尾节点prev, 并将队尾指针tail指向当前节点
        Node prev = tail.getAndSet( node ); // (1)
        // 旧的队尾节点(即prev)存在, 说明链表不为空
        if( prev!=null ) {
            // 当前节点加入链表
            prev.next = node;               // (2)
            // 当前线程在其自身节点的status变量上进行自旋
            // 直到前驱节点prev释放锁时, 将当前节点node的status修改为false
            while( node.status );
        }
    }

    public void unlock() {
        Node node = currentNode.get();
        // 如果当前节点的后继节点为空, 则需要清空队列, 即将队尾指针tail置空
        if( node.next==null ) {
            // 通过CAS的方式安全地将队尾指针tail置空
            if( !tail.compareAndSet(node, null) ) {
                //  如果这个CAS操作失败, 则说明有节点突然入队, 即刚刚执行完lock方法的(1)代码                
                //  此时需要等待lock方法的(2)代码完成
                while( node.next==null );
            }
        }

        // 当前节点的后继节点存在
        if( node.next!=null ) {
            // 将当前节点的后继节点的status变量修改为false
            node.next.status = false;
            node.next = null;
        }
        currentNode.remove();
    }

    private static class Node {
        private volatile boolean status = false;

        private volatile Node next = null;
    }
}

Note

本文为了行文简便、实现清晰，故在队列锁实现中均未实现锁重入这一特性。事实上，可以通过添加额外的辅助变量来拓展、实现

推荐文章
请我喝杯咖啡捏～

欢迎关注我的微信公众号：青灯抽丝