并发编程系列之CLH锁

CLH加锁&解锁流程

CLHLock作为自旋、公平并发锁，其实现思路较为简单。文中使用了ThreadLocal结构来维护每个线程的当前结点（CurrentNode)和前驱结点（PrevNode)信息。当前线程通过调用lock()方法，在前驱结点的voliate变量lock自旋，实现对共享资源的监听。

如图所示，在线程尝试取锁时，会在调用ThreadLocal.get()方法内部构造新的CLHNode，并将该CLHNode的lock字段置为true，表示当前线程"持有"锁；同时修改当前线程"指向"的前驱CLHNode结点为上一次取锁后的tail指针指向的CLHNode。如此便完成了取锁-自旋的过程。

实现

• 申明ILock接口

/**
 * Created by fujianbo on 2018/3/24.
 *
 * @author fujianbo
 * @date 2018/03/24
 */
public interface ILock {
    /**
     * 线程获取锁惭怍
     * @param thread
     * @throws InterruptedException
     */
    void lock() throws InterruptedException;

    /**
     * 线程释放锁操作
     * @param thread
     */
    void unlock();
}

• 定义CLHNode数据结构

/**
 * Created by fujianbo on 2018/3/24.
 *
 * @author fujianbo
 * @date 2018/03/24
 */
public class CLHNode {
    /** 当前结点是否被线程持有 */
    private volatile boolean isLock = false;
    /** 拥有当前结点的线程 */
    private Thread thread;

    public Thread getThread() {
        return thread;
    }

    public void setThread(Thread thread) {
        this.thread = thread;
    }

    public boolean isLock() {
        return isLock;
    }

    public void setLock(boolean lock) {
        isLock = lock;
    }
}

• 【重要】CLH取锁&释放锁逻辑

/**
 * Created by fujianbo on 2018/3/24.
 *
 * CLH锁实现
 * @author fujianbo
 * @date 2018/03/24
 */
public class CLHLock implements ILock {
    private AtomicReference<CLHNode> tail = new AtomicReference<>(new CLHNode());
    private ThreadLocal<CLHNode> current = new ThreadLocal() {
        @Override
        protected Object initialValue() {
            return new CLHNode();
        }
    };

    private ThreadLocal<CLHNode> prev = new ThreadLocal();

    @Override
    public void lock() {
        // 初始化线程上下文
        CLHNode threadCurrentNode = current.get();
        threadCurrentNode.setLock(true);
        // 获取tail地址并将tail指向新生成的CLHNode
        CLHNode threadPrevNode = tail.getAndSet(threadCurrentNode);
        this.prev.set(threadPrevNode);
        // 自旋等待
        while (this.prev.get().isLock()) {
            System.out.println("thread:" + Thread.currentThread().getName() + "is trying to get lock...!");
        }

        System.out.println("thread:" + Thread.currentThread().getName() + "succeed to get lock!");
    }

    @Override
    public void unlock() {
        CLHNode threadCurrentNode = current.get();
        current.set(null);
        prev.set(null);
        threadCurrentNode.setLock(false);
    }

• 测试用例

/**
 * Created by fujianbo on 2018/3/25.
 *
 * @author fujianbo
 * @date 2018/03/25
 */
public class CLHLockTest {
    private static final int THREAD_NUM = 10;
    private static int total = 0;

    public static void main(String[] args) {
        CLHLock clhLock = new CLHLock();
        for (int idx=0 ; idx<THREAD_NUM ; ++idx) {
            new Thread() {
                @Override
                public void run() {
                    clhLock.lock();
                    CLHLockTest.total++;
                    clhLock.unlock();
                }
            }.start();
        }
    }
}

错误分析

• 手误导致未初始化tail节点导致线程死锁

private AtomicReference<CLHNode> tail = new AtomicReference<>(new CLHNode()); //before: private AtomicReference<CLHNode> tail = new AtomicReference<>();