【多线程系列】CAS 不得不知的两个升级版本 CLH、MCS

原创

Lorin 洛林

发布于 2023-11-05 13:47:55

3060

发布于 2023-11-05 13:47:55

文章被收录于专栏：Java 技术小屋

导读

普通自旋锁可能存在的一些问题：饥饿、如何实现公平、CPU 高速缓存频繁同步
CLH 锁和 MCS 锁是什么？以及使用场景

环境及版本

运行版本：JDK8

普通自旋锁存在的问题

自旋锁是 Java 并发编程中的常见解决方案，当互斥资源被其它线程占用时，通过自旋的方式尝试获取锁，避免阻塞和唤醒线程带来的上下文切换开销，但普通的自旋锁存在以下几方面问题：1、非公平锁，可能导致饥饿 2、依赖一个互斥标记，线程较多时竞技激烈，且多个CPU高速缓存同步频繁 3、实现非公平锁需要额外的字段

CLH 锁和 MCS 锁

解决上述问题，我们可以用 CLH 锁 MCS 锁通过队列实现。

CLH 锁

CLH 是一种逻辑队列自旋锁，由 Craig、Landin 和 Hagersten 三位作者提出，具体内容在《Building FIFO and Priority-Queuing Spin Locks from Atomic Swap》论文中有详细介绍。
Java 中 AQS 就是基于变种 CLH 实现。

流程

下面是 CLH 锁加锁和解锁的大致流程：

加锁

维护队列的尾节点，通过 CAS 操作将线程入队，并将前置节点置为上一个尾节点（逻辑连接），lock 状态置为 true (lock 状态为 true 表示正在获取锁或已经成功获取锁，需要结合前置节点 lock 状态判断)。
入队后的节点，自旋轮询前一个尾节点（即当前节点的前置节点）lock 状态，当前置节点为空或 lock 为 false 时，当前节点成功获取锁。

解锁

解锁时将当前节点的 lock 状态置为 false。

示例代码

interface Lock {
    void lock();

    void unlock() throws Exception;
}

class CLHLock implements Lock {

    /**
     * tailNode 尾节点原子操作保证线程安全
     */
    private final AtomicReference<Node> tailNode = new AtomicReference<>();

    private final ThreadLocal<Node> currentNodeLocal = new ThreadLocal<>();

    private static class Node {
        /**
         * 前驱节点
         */
        private Node preNode;
        /**
         * 当前节点状态
         * volatile 保证对后置线程的可见性
         */
        private volatile Boolean lockState;

        public Node(Boolean lockState) {
            this.lockState = lockState;
        }
    }

    @Override
    public void lock() {
        Node currentNode = currentNodeLocal.get();
        if (currentNode == null) {
            currentNodeLocal.set(new Node(true));
            currentNode = currentNodeLocal.get();
        }

        // 拿到当前节点的前置节点 形成逻辑连接 无实际连接
        Node preNode = tailNode.getAndSet(currentNode);
        // 检查前置节点 lock state
        while (currentNode.preNode != null && preNode.lockState) {
            System.out.println(Thread.currentThread().getName() + " 自旋等待获取锁");
        }
        System.out.println(Thread.currentThread().getName() + " 获取锁成功");
    }

    @Override
    public void unlock() throws Exception {
        Node currentNode = currentNodeLocal.get();
        if (!currentNode.lockState || (currentNode.preNode != null && currentNode.preNode.lockState)) {
            throw new Exception("current thread is not locked");
        }
        currentNode.lockState = false;
        // 清除线程 ThreadLocal 本次锁信息 避免拿到已经释放的锁信息
        currentNodeLocal.remove();
        System.out.println(Thread.currentThread().getName() + " 释放锁");
    }
}

CLH 的优点

性能优异，获取和释放锁开销小。CLH 的锁状态不再是单一的原子变量，而是分散在每个节点的状态中，降低了自旋锁在竞争激烈时频繁同步的开销。释放锁的开销也因为不需要使用 CAS 指令而降低。
公平锁。
实现简单，可用于拓展，如 AQS 就是基于变种 CLH实现。

CLH 的不足

对于锁长时间持有的场景会造成 CPU 自旋损耗。
过于简单，实现复杂功能需要进行拓展。

MCS 锁

MCS 由 John M. Mellor-Crummey 和 Michael L. Scott 提出，具体内容可以在《Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors》论文中查看。
MCS 锁和 CLH 锁十分相似，都是逻辑队列自旋锁，++但 CLH 锁轮询的是前置节点的 lock 域，而 MCS 锁轮询的是自己当前节点的 lock 域，前置节点释放锁时会更新队列后置节点 lock 状态，即可以根据当前节点的 lock 状态来判断是否可以获取锁，主要是为了解决 NUMA(Non-Uniform Memory Access) 架构下读取远端内存速度较慢的问题++。

和 CLH 锁区别

CLH 锁逻辑队列之间连接无物理连接，MCS 锁存在物理连接。
核心：CLH 锁通过自旋轮询前置节点 lcok 域状态判断是否获取锁，MCS 锁判断当前节点 lock 状态。

流程

下面是 MCS 锁加锁、解锁大致流程：

加锁

维护队列的尾节点，通过 CAS 操作将线程入队，若前置节点为空，直接获取锁，若前置节点不为空，将前置节点的 next 节点指向当前节点，轮询当前节点 lock 状态。（初始值为 false 未获取锁，true 为获取到锁）

解锁

当前节点释放锁，唤醒队列中的后置节点，即将后置节点的 lock 置为 true。

示例代码

interface Lock {
    void lock();

    void unlock() throws Exception;
}

class MSCLock implements Lock {

    /**
     * tailNode 尾节点原子操作保证线程安全
     */
    final AtomicReference<Node> tailNode = new AtomicReference<>();

    private final ThreadLocal<Node> currentNodeLocal = new ThreadLocal<>();

    private static class Node {
        /**
         * 后驱节点
         * volatile 保证 nextNode 引用的可见性
         */
        private volatile Node nextNode;
        /**
         * 当前节点状态
         * volatile 保证对后置线程的可见性
         */
        private volatile Boolean lockState;

        public Node(Boolean lockState) {
            this.lockState = lockState;
        }
    }

    @Override
    public void lock() {
        Node currentNode = new Node(true);
        currentNodeLocal.set(currentNode);
        Node preNode = tailNode.getAndSet(currentNode);
        // 首节点直接获取锁
        if (preNode == null) {
            currentNode.lockState = true;
        } else {
            preNode.nextNode = currentNode;
            // 自旋检测当前节点状态
            while (!currentNode.lockState) {
                System.out.println(Thread.currentThread().getName() + " 自旋等待获取锁");
            }
        }
        System.out.println(Thread.currentThread().getName() + " 获取锁成功");
    }

    @Override
    public void unlock() {
        Node currentNode = currentNodeLocal.get();
        Node nextNode = currentNode.nextNode;

        // 若无等待线程 尝试将tailNode置为 null
        if (nextNode == null) {
            if (tailNode.compareAndSet(currentNode, null)) {
                System.out.println(Thread.currentThread().getName() + " 锁释放成功");
                return;
            } else {
                nextNode = currentNode.nextNode;
            }
        }

        // 清除线程 ThreadLocal 本次锁信息 避免拿到已经释放的锁信息
        currentNodeLocal.remove();
        // 唤醒下一个等待线程
        nextNode.lockState = true;
    }
}

参考

SMP vs NUMA vs MPP 架构简介

个人简介

👋 你好，我是 Lorin 洛林，一位 Java 后端技术开发者！座右铭：Technology has the power to make the world a better place.

🚀 我对技术的热情是我不断学习和分享的动力。我的博客是一个关于Java生态系统、后端开发和最新技术趋势的地方。

🧠 作为一个 Java 后端技术爱好者，我不仅热衷于探索语言的新特性和技术的深度，还热衷于分享我的见解和最佳实践。我相信知识的分享和社区合作可以帮助我们共同成长。

💡 在我的博客上，你将找到关于Java核心概念、JVM 底层技术、常用框架如Spring和Mybatis 、MySQL等数据库管理、RabbitMQ、Rocketmq等消息中间件、性能优化等内容的深入文章。我也将分享一些编程技巧和解决问题的方法，以帮助你更好地掌握Java编程。

🌐 我鼓励互动和建立社区，因此请留下你的问题、建议或主题请求，让我知道你感兴趣的内容。此外，我将分享最新的互联网和技术资讯，以确保你与技术世界的最新发展保持联系。我期待与你一起在技术之路上前进，一起探讨技术世界的无限可能性。

📖 保持关注我的博客，让我们共同追求技术卓越。

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java

并发编程

2023腾讯·技术创作特训营第三期

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

登录后参与评论

0 条评论

热度