首页 > 代码库 > Ticket Lock, CLH Lock, MCS Lock

Ticket Lock, CLH Lock, MCS Lock

如果不用OS提供的mutex,我们该如何实现互斥锁?

 

1. naive lock

最简单的想法是,搞一个volatile类型的共享变量flag,值可以是0(无锁)或者1(有锁),竞争线程监听flag,一旦发现flag为0,那么尝试cas更新flag为1,更新成功则说明占有了这个锁,更新失败说明临界区已经被其他线程占领,继续监听flag并尝试更新。占有锁的线程退出的时候,将flag修改为0,表示释放锁。

    volatile int flag = 0;

    void lock() {
        while (!cas(flag, 0, 1)) {//返回true:占锁成功,返回false:占锁失败,继续循环尝试

        }
    }

    void unlock() {
        flag = 0;
    }

这样做有个问题是无法保证公平性,可能有的倒霉蛋空转了一辈子也无法cas成功,无法做到按竞争线程先来后到的次序占有锁。

 

2. Ticket Lock

为了提供公平,有人发明了Ticket Lock

线程想要竞争某个锁,需要先领一张ticket,然后监听flag,发现flag被更新为手上的ticket的值了,才能去占领锁

就像是在医院看病一样,医生就是临界区,病人就是线程,病人挂了号领一张单子,单子上写了一个独一无二的号码,病人等的时候就看屏幕,屏幕上显示到自己的号码了,才能进去找医生。

    AtomicInteger ticket = new AtomicInteger(0);
    volatile int flag = 0;

    void lock() {
        int my_ticket = ticket.getAndIncrement();//发号必须是一个原子操作,不能多个线程拿到同一个ticket
        while (my_ticket != flag) {

        }
    }

    void unlock() {
        flag++;
    }

现在公平性的问题没有了,但是所有的线程都在监听flag变量,而且由于为了保证flag变量变化的可见性,它必须是volatile的。也就是说如果某个线程修改了flag变量,都会引起其他所有监听线程所在的core的对应于flag变量的cache line被设为invalid,那么这些线程下一次查询flag变量的时候,就必须从主存里取最新的flag数据了,由于主存带宽有限,这个开销较为昂贵(与监听线程数成正比)。

 

3. CLH Lock

为了减少缓存一致性带来的开销,CLH Lock被发明了。

ps,CLH实际上是指三个人:Craig, Landin, and Hagersten

CLH锁的核心思想是,1. 竞争线程排队 2. 监听变量拆分

CLH锁维护了一个链表waitingList的head与tail,其节点定义如下:

    static class Node {
        volatile boolean flag;//true:当前线程正在试图占有锁或者已经占有锁,false:当前线程已经释放锁,下一个线程可以占有锁了
        Node prev;//监听前一个节点的flag字段
    }

初始时需要定义一个dummy节点(dummpy.flag == true, dummy.prev == null),head == tail == dummy

当有线程想要获取锁时,先创建一个链表节点node,然后将node挂载在waitingList的尾部(尝试cas(tail, oldTail, node),如果成功将node.prev更新为oldTail,失败则重试)

然后这个线程就监听node.prev.flag,什么时候node.prev.flag == false了,说明node的前一个节点对应的线程已经释放了锁,本线程此时可以安全的占有锁了

释放锁的时候,将对应的node.flag修改为false即可。

实现代码如下(相当粗糙,意会即可):

public class CLHLock {
    volatile Node head, tail;//waitingList

    public CLHLock() {
        head = tail = Node.DUMMY;
    }

    public Node lock() {
        //lock-free的将node添加到waitingList的尾部
        Node node = new Node(true, null);
        Node oldTail = tail;
        while (!cas(tail, oldTail, node)) {
            oldTail = tail;
        }
        node.setPrev(oldTail);

        while (node.getPrev().isLocked()) {//监听前驱节点的locked变量
        }

        return node;
    }

    public void unlock(Node node) {
        node.setLocked(false);
    }

    static class Node {
        public Node(boolean locked, Node prev) {
            this.locked = locked;
            this.prev = prev;
        }

        volatile boolean locked;//true:当前线程正在试图占有锁或者已经占有锁,false:当前线程已经释放锁,下一个线程可以占有锁了
        Node prev;//监听前一个节点的locked字段

        public boolean isLocked() {
            return locked;
        }

        public void setLocked(boolean locked) {
            this.locked = locked;
        }

        public Node getPrev() {
            return prev;
        }

        public void setPrev(Node prev) {
            this.prev = prev;
        }

        public static final Node DUMMY = new Node(false, null);
    }
}

这样做可以极大的减少缓存一致性协议所带来的开销。

CLH锁的变种被应用于Java J.U.C包下的AbstractQueuedSynchronizer

 

4. MCS锁

CLH锁并不是完美的,因为每个线程都是在前驱节点的locked字段上自旋,而在NUMA体系中,有可能多个线程工作在多个不同的socket上的core里。如果前驱节点的内存跟监听线程的core距离过远,会有性能问题。

于是MCS锁诞生了

ps,MCS也是人名简写:John M. Mellor-Crummey and Michael L. Scott

MCS与CLH最大的不同在于:CLH是在前驱节点的locked域上自旋,MCS是在自己节点上的locked域上自旋。

具体的实现是,前驱节点在释放锁之后,会主动将后继节点的locked域更新。

也就是把多次对远端内存的监听 + 一次对本地内存的更新,简化成了多次对本地内存的监听 + 一次对远端内存的更新。

具体的实现如下

public class MCSLock {
    volatile Node head, tail;//waitingList

    public MCSLock() {
        head = tail = null;
    }

    public Node lock() {
        //lock-free的将node添加到waitingList的尾部
        Node node = new Node(true, null);
        Node oldTail = tail;
        while (!cas(tail, oldTail, node)) {
            oldTail = tail;
        }

        if (null == oldTail) {//如果等待列表为空,那么获取锁成功,直接返回
            return node;
        }

        oldTail.setNext(node);
        while (node.isLocked()) {//监听当前节点的locked变量
        }

        return node;
    }

    public void unlock(Node node) {
        if (node.getNext() == null) {
            if (cas(tail, node, null)) {//即使当前节点的后继为null,也要用cas看一下队列是否真的为空
                return;
            }
            while (node.getNext() != null) {//cas失败,说明有后继节点,只是还没更新前驱节点的next域,等前驱节点看到后继节点后,即可安全更新后继节点的locked域

            }
        }
        node.getNext().setLocked(false);
    }

    static class Node {
        public Node(boolean locked, Node next) {
            this.locked = locked;
            this.next = next;
        }

        volatile boolean locked;//true:当前线程正在试图占有锁或者已经占有锁,false:当前线程已经释放锁,下一个线程可以占有锁了
        Node next;//后继节点

        public boolean isLocked() {
            return locked;
        }

        public void setLocked(boolean locked) {
            this.locked = locked;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }

 

参考资料

CLH锁 、MCS锁

基于队列的锁:mcs lock简介

Ticket Lock, CLH Lock, MCS Lock