☕【Java 技术指南】「并发原理专题」AQS 的技术体系之 CLH、MCS 锁的原理及实现

李浩宇/Alex

关注

发布于: 2 小时前

☕【Java技术指南】「并发原理专题」AQS的技术体系之CLH、MCS锁的原理及实现

背景

SMP(Symmetric Multi-Processor)

对称多处理器结构，它是相对非对称多处理技术而言的、应用十分广泛的并行技术。

在这种架构中，一台计算机由多个 CPU 组成，并共享内存和其他资源，所有的 CPU 都可以平等地访问内存、I/O 和外部中断。
虽然同时使用多个 CPU，但是从管理的角度来看，它们的表现就像一台单机一样。
操作系统将任务队列对称地分布于多个 CPU 之上，从而极大地提高了整个系统的数据处理能力。
但是随着 CPU 数量的增加，每个 CPU 都要访问相同的内存资源，共享资源可能会成为系统瓶颈，导致 CPU 资源浪费。

NUMA(Non-Uniform Memory Access)

非一致存储访问，将 CPU 分为 CPU 模块，每个 CPU 模块由多个 CPU 组成，并且具有独立的本地内存、I/O 槽口等，模块之间可以通过互联模块相互访问。

访问本地内存（本 CPU 模块的内存）的速度将远远高于访问远程内存(其他 CPU 模块的内存)的速度，这也是非一致存储访问的由来。
NUMA 较好地解决 SMP 的扩展问题，当 CPU 数量增加时，因为访问远地内存的延时远远超过本地内存，系统性能无法线性增加。

CLH 锁

CLH 是一种基于单向链表的高性能、公平的自旋锁。申请加锁的线程通过前驱节点的变量进行自旋。在前置节点解锁后，当前节点会结束自旋，并进行加锁。

在 SMP 架构下，CLH 更具有优势。
在 NUMA 架构下，如果当前节点与前驱节点不在同一 CPU 模块下，跨 CPU 模块会带来额外的系统开销，而 MCS 锁更适用于 NUMA 架构。

加锁逻辑

获取当前线程的锁节点，如果为空，则进行初始化；
同步方法获取链表的尾节点，并将当前节点置为尾节点，此时原来的尾节点为当前节点的前置节点。
如果尾节点为空，表示当前节点是第一个节点，直接加锁成功。
如果尾节点不为空，则基于前置节点的锁值（locked==true）进行自旋，直到前置节点的锁值变为 false。

解锁逻辑

获取当前线程对应的锁节点，如果节点为空或者锁值为 false，则无需解锁，直接返回；
同步方法为尾节点赋空值，赋值不成功表示当前节点不是尾节点，则需要将当前节点的 locked=false 解锁节点。如果当前节点是尾节点，则无需为该节点设置。


public class CLHLock {    private final AtomicReference<Node> tail;    private final ThreadLocal<Node> myNode;    private final ThreadLocal<Node> myPred;     public CLHLock() {        tail = new AtomicReference<>(new Node());        myNode = ThreadLocal.withInitial(() -> new Node());        myPred = ThreadLocal.withInitial(() -> null);    }     public void lock(){        Node node = myNode.get();        node.locked = true;        Node pred = tail.getAndSet(node);        myPred.set(pred);        while (pred.locked){}    }     public void unLock(){        Node node = myNode.get();        node.locked=false;        myNode.set(myPred.get());    }      static class Node {        volatile boolean locked = false;    } }

复制代码

MCS 锁

MSC 与 CLH 最大的不同并不是链表是显示还是隐式，而是线程自旋的规则不同:CLH 是在前趋结点的 locked 域上自旋等待，而 MCS 是在自己的结点的 locked 域上自旋等待。正因为如此，它解决了 CLH 在 NUMA 系统架构中获取 locked 域状态内存过远的问题。

MCS 锁具体实现规则：

a. 队列初始化时没有结点，tail=null
b. 线程 A 想要获取锁，将自己置于队尾，由于它是第一个结点，它的 locked 域为 false
c. 线程 B 和 C 相继加入队列，a->next=b,b->next=c，B 和 C 没有获取锁，处于等待状态，所以 locked 域为 true，尾指针指向线程 C 对应的结点
d. 线程 A 释放锁后，顺着它的 next 指针找到了线程 B，并把 B 的 locked 域设置为 false，这一动作会触发线程 B 获取锁。

public class MCSLock {     private final AtomicReference<Node> tail;     private final ThreadLocal<Node> myNode;     public MCSLock() {        tail = new AtomicReference<>();        myNode = ThreadLocal.withInitial(() -> new Node());    }     public void lock() {         Node node = myNode.get();        Node pred = tail.getAndSet(node);        if (pred != null) {            node.locked = true;            pred.next = node;            while (node.locked) {            }        }     }     public void unLock() {        Node node = myNode.get();        if (node.next == null) {            if (tail.compareAndSet(node, null)) {                return;            }             while (node.next == null) {            }        }        node.next.locked = false;        node.next = null;    }     class Node {        volatile boolean locked = false;        Node next = null;    }     public static void main(String[] args) {         MCSLock lock = new MCSLock();         Runnable task = new Runnable() {            private int a;             @Override            public void run() {                lock.lock();                for (int i = 0; i < 10; i++) {                    a++;                    try {                        Thread.sleep(100);                    } catch (InterruptedException e) {                        e.printStackTrace();                    }                }                System.out.println(a);                lock.unLock();            }        };         new Thread(task).start();        new Thread(task).start();        new Thread(task).start();        new Thread(task).start();    }}

复制代码

发布于: 2 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/8d00bdc450e96583f0cde5c4c】。文章转载请联系作者。

李浩宇/Alex

关注

🏆2021年InfoQ写作平台-签约作者 🏆 2020.03.25 加入

👑【酷爱计算机技术、醉心开发编程、喜爱健身运动、热衷悬疑推理的”极客狂人“】 🏅 【Java技术领域，MySQL技术领域，APM全链路追踪技术及微服务、分布式方向的技术体系等】我们始于迷惘，终于更高水平的迷惘

发布

暂无评论

创作场景

☕【Java 技术指南】「并发原理专题」AQS 的技术体系之 CLH、MCS 锁的原理及实现

背景

SMP(Symmetric Multi-Processor)

NUMA(Non-Uniform Memory Access)

CLH 锁

加锁逻辑

解锁逻辑

MCS 锁

MCS 锁具体实现规则：

李浩宇/Alex

评论