基于自旋的CLH锁

Posted by RussXia on June 1, 2018

基于自旋的CLH锁

什么是CLH锁

CLH锁满足一下几个特点

  • CLH锁是利用链表实现的无界队列,公平的(FIFO队列),自旋锁
  • 线程在局部变量上自旋,不断轮询前置节点的状态,如果发现前置节点已经释放了锁,则结束自旋获取锁。
  • AQS(AbstractQueuedSynchronizer)源码中使用的是CLH锁的一个变种。

CLH算法

CLH算法的数据结构及实现

数据结构

CLHLock内部有两个ThreadLocal变量,一个指向自己的节点(myNode),另一个指向前一节点(myPred)。(链表)一个原子引用变量(AtomicReference)指向队列的队尾。

CLH锁的基本数据结构如下图所示: CLH-数据结构

CLH获取和释放锁过程

  1. 创建一个QNode节点,设置当前节点为true,表示尝试获取锁。
  2. 将tail指向自己,表示自己为当前队列的末尾(tail是原子性的,可以保证并发安全),获取前置节点locked字段的引用。
  3. 在前置节点的locked字段上自旋,直到获取锁。
  4. 当前线程释放锁时,将locked设置为false,将自身节点指向前置节点(相当于出队操作)

CLH-示意图

1. 初始状态 tail指向一个node(head)节点
  +------+  
  | head | <---- tail
  +------+
  
2. lock-thread加入等待队列: tail指向新的Node,同时Prev指向tail之前指向的节点
  +----------+
  | Thread-A |
  | := Node  | <---- tail
  | := Prev  | -----> +------+
  +----------+        | head |
                      +------+ 

tail一直指向链表的最后一个Node元素。
              +----------+            +----------+
              | Thread-B |            | Thread-A |
  tail ---->  | := Node  |      |---->| := Node  |         +------+
              | := Prev  | -----|     | := Prev  | ----->  | head |
              +----------+            +----------+         +------+

3. 当前线程在自己的Prev Node(即链表的上一个节点)上自旋。
  

Java代码实现

CLH Lock是独占式锁的一种,并且是不可重入的锁。下面是CLH Lock的Java实现。

package com.xzy.lock;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;

public class CLHLock implements Lock {

    private AtomicReference<QNode> tail = new AtomicReference<>(new QNode());

    private ThreadLocal<QNode> myPred;
    private ThreadLocal<QNode> myNode;

    public CLHLock() {
        tail = new AtomicReference<>(new QNode());
        myNode = ThreadLocal.withInitial(QNode::new);
        myPred = ThreadLocal.withInitial(() -> null);
    }

    @Override
    public void lock() {
        QNode qNode = myNode.get();
        qNode.lock = true;
        QNode pred = tail.getAndSet(qNode);
        myPred.set(pred);
        while (pred.lock) ;
    }

    @Override
    public void lockInterruptibly() throws InterruptedException {

    }

    @Override
    public boolean tryLock() {
        return false;
    }

    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        return false;
    }

    @Override
    public void unlock() {
        QNode qnode = myNode.get();
        qnode.lock = false;
        myNode.set(myPred.get());
    }

    @Override
    public Condition newCondition() {
        return null;
    }

    class QNode {
        volatile boolean lock;
    }
}

测试CLH Lock

package com.xzy.lock;

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.locks.Lock;

public class CLHLockTest {

    static int count = 0;

    public static void main(String[] args) throws InterruptedException {
        final CyclicBarrier cb = new CyclicBarrier(10, new Runnable() {
            @Override
            public void run() {
                System.out.println(count);
            }
        });
        CLHLock clhLock = new CLHLock();
        for (int i = 0; i < 10; i++) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    testLock(clhLock);
                    try {
                        cb.await();
                    } catch (InterruptedException | BrokenBarrierException e) {
                        e.printStackTrace();
                    }
                }
            }).start();

        }
    }

    public static void testLock(Lock lock) {
        System.out.println(Thread.currentThread().getName() + ": ready to lock");
        try {
            lock.lock();
            for (int i = 0; i < 100000; i++) ++count;
        } finally {
            System.out.println(Thread.currentThread().getName() + ": unlocked");
            lock.unlock();
        }
    }
}

输出结果:

Thread-0: ready to lock
Thread-0: locked
Thread-1: ready to lock
Thread-0: unlocked
Thread-1: locked
Thread-2: ready to lock
Thread-3: ready to lock
Thread-1: unlocked
Thread-2: locked
Thread-4: ready to lock
Thread-2: unlocked
Thread-3: locked
Thread-5: ready to lock
Thread-3: unlocked
Thread-4: locked
Thread-4: unlocked
Thread-5: locked
Thread-6: ready to lock
Thread-5: unlocked
Thread-6: locked
Thread-7: ready to lock
Thread-6: unlocked
Thread-7: locked
Thread-8: ready to lock
Thread-7: unlocked
Thread-8: locked
Thread-8: unlocked
Thread-9: ready to lock
Thread-9: locked
Thread-9: unlocked
1000000

总结

  • 关于可重入锁和不可重入锁:
    1. 可重入锁指可重复可递归调用的锁,并且不发生死锁。典型代表:ReentrantLock、synchronized
    2. 不可重入锁:与可重入锁相反。自旋锁一般都是不可重入锁。CLH就是不可重入锁。
  • 由于锁对象是释放锁以后,没有指针引用,所以当前线程结束后,会被自动gc回收。
  • CLH的队列是隐式的,无解的。