关于java:面经手册-第16篇码农会锁ReentrantLock之公平锁讲解和实现

2次阅读

共计 5529 个字符，预计需要花费 14 分钟才能阅读完成。

作者：小傅哥
<br/> 博客：https://bugstack.cn
<br/> 专题：面经手册

积淀、分享、成长，让本人和别人都能有所播种！????

Java 学多少能力找到工作？

最近常常有小伙伴问我，认为我的教训来看，学多少够，如同更多的是看你的野心有多大。如果你只是想找个 10k 以内的二线城市的工作，那还是比拟容易的。也不须要学数据结构、也不须要会算法、也须要懂源码、更不要有多少我的项目教训。

但反之我遇到一个国内大学 TOP2 毕业的娃，这货兼职是 Offer 收割机：腾讯、阿里、字节还有国外新加坡的工作机会等等，薪资待遇也是贼高，可能超过你对白菜价的认知。上学无用、学习无用，纯属扯淡！

你能在这条路上能付出的越多，能致力的越早，播种就会越大！

谢飞机，小记，刚去冬巴拉泡完脚放松的飞机，因为耐克袜子丢了，骂骂咧咧的赴约面试官。

面试官：咋了，飞机，怎么看上去不快乐。

谢飞机：没事，没事，我心理我学的 synchronized 呢！

面试官：那正好，飞机你会锁吗？

谢飞机 ：啊。。。我没去会所呀！！！ 你咋晓得

面试官：我说 Java 锁，你想啥呢！你理解偏心锁吗，晓得怎么实现的吗，给我说说！

谢飞机：偏心锁！？嗯，是不 ReentrantLock 中用到了，我怎么感觉仿佛有印象，然而不记得了。

面试官：哎，回家搜搜 CLH 吧！

鉴于上一篇小傅哥曾经基于，HotSpot 虚拟机源码剖析 synchronized 实现和相应外围知识点，原本想在本章间接介绍下 ReentrantLock。但因为 ReentrantLock 知识点较多，因而会分几篇别离解说，突出每一篇重点，防止猪八戒吞枣。

介绍：ReentrantLock 是一个可重入且独占式锁，具备与 synchronized 监视器(monitor enter、monitor exit) 锁基本相同的行为和语意。但与 synchronized 相比，它更加灵便、弱小、减少了轮训、超时、中断等高级性能以及能够创立偏心和非偏心锁。

ReentrantLock 是基于 Lock 实现的可重入锁，所有的 Lock 都是基于 AQS 实现的，AQS 和 Condition 各自保护不同的对象，在应用 Lock 和 Condition 时，其实就是两个队列的相互挪动。它所提供的共享锁、互斥锁都是基于对 state 的操作。而它的可重入是因为实现了同步器 Sync，在 Sync 的两个实现类中，包含了偏心锁和非偏心锁。

这个偏心锁的具体实现，就是咱们本章节要介绍的重点，理解什么是偏心锁、偏心锁的具体实现。学习完根底的常识能够更好的了解 ReentrantLock

ReentrantLock lock = new ReentrantLock(true);  // true：偏心锁
lock.lock();
try {// todo} finally {lock.unlock();
}

初始化构造函数入参，抉择是否为初始化偏心锁。
其实个别状况下并不需要偏心锁，除非你的场景中须要保障程序性。
应用 ReentrantLock 切记须要在 finally 中敞开，lock.unlock()。

public ReentrantLock(boolean fair) {sync = fair ? new FairSync() : new NonfairSync();}

构造函数中抉择偏心锁（FairSync）、非偏心锁（NonfairSync）。

static final class FairSync extends Sync {protected final boolean tryAcquire(int acquires) {final Thread current = Thread.currentThread();
        int c = getState();
        if (c == 0) {if (!hasQueuedPredecessors() &&
                compareAndSetState(0, acquires)) {setExclusiveOwnerThread(current);
                return true;
            }
        }
        ...
    }
}

偏心锁和非偏心锁，次要是在办法 tryAcquire 中，是否有 !hasQueuedPredecessors() 判断。

public final boolean hasQueuedPredecessors() {
    Node t = tail; // Read fields in reverse initialization order
    Node h = head;
    Node s;
    return h != t &&
        ((s = h.next) == null || s.thread != Thread.currentThread());
}

在这个判断中次要就是看以后线程是不是同步队列的首位，是：true、否：false
这部分就波及到了偏心锁的实现，CLH（Craig，Landin andHagersten）。三个作者的首字母组合

偏心锁就像是马路边上的卫生间，上厕所须要排队。当然如果有人不排队，那么就是非偏心锁了，比方领导要先上。

CLH 是一种基于单向链表的高性能、偏心的自旋锁。AQS 中的队列是 CLH 变体的虚构双向队列（FIFO），AQS 是通过将每条申请共享资源的线程封装成一个节点来实现锁的调配。

为了更好的学习了解 CLH 的原理，就须要有实际的代码。接下来一 CLH 为外围别离介绍 4 种偏心锁的实现，从而把握最根本的技术栈常识。

public class CLHLock implements Lock {

    private final ThreadLocal<CLHLock.Node> prev;
    private final ThreadLocal<CLHLock.Node> node;
    private final AtomicReference<CLHLock.Node> tail = new AtomicReference<>(new CLHLock.Node());

    private static class Node {private volatile boolean locked;}

    public CLHLock() {this.prev = ThreadLocal.withInitial(() -> null);
        this.node = ThreadLocal.withInitial(CLHLock.Node::new);
    }

    @Override
    public void lock() {final Node node = this.node.get();
        node.locked = true;
        Node pred_node = this.tail.getAndSet(node);
        this.prev.set(pred_node);
        // 自旋
        while (pred_node.locked);
    }

    @Override
    public void unlock() {final Node node = this.node.get();
        node.locked = false;
        this.node.set(this.prev.get());
    }

}

CLH（Craig，Landin and Hagersten），是一种基于链表的可扩大、高性能、偏心的自旋锁。

在这段代码的实现过程中，相当于是虚构进去一个链表构造，由 AtomicReference 的办法 getAndSet 进行连接。getAndSet 获取以后元素，设置新的元素

lock()

通过 this.node.get() 获取以后节点，并设置 locked 为 true。
接着调用 this.tail.getAndSet(node)，获取以后尾部节点 pred_node，同时把新退出的节点设置成尾部节点。
之后就是把 this.prev 设置为之前的尾部节点，也就相当于链路的指向。
最初就是自旋 while (pred_node.locked)，直至程序开释。

unlock()

开释锁的过程就是拆链，把开释锁的节点设置为 false node.locked = false。
之后最重要的是把以后节点设置为上一个节点，这样就相当于把本人的节点拆下来了，等着垃圾回收。

CLH队列锁的长处是空间复杂度低，在 SMP（Symmetric Multi-Processor）对称多处理器构造（一台计算机由多个 CPU 组成，并共享内存和其余资源，所有的 CPU 都能够平等地拜访内存、I/ O 和内部中断）成果还是不错的。但在 NUMA(Non-Uniform Memory Access) 下成果就不太好了，这部分常识能够自行扩大。

public class MCSLock implements Lock {private AtomicReference<MCSLock.Node> tail = new AtomicReference<>(null);
    ;
    private ThreadLocal<MCSLock.Node> node;

    private static class Node {
        private volatile boolean locked = false;
        private volatile Node next = null;
    }

    public MCSLock() {node = ThreadLocal.withInitial(Node::new);
    }

    @Override
    public void lock() {Node node = this.node.get();
        Node preNode = tail.getAndSet(node);
        if (null == preNode) {
            node.locked = true;
            return;
        }
        node.locked = false;
        preNode.next = node;
        while (!node.locked) ;
    }

    @Override
    public void unlock() {Node node = this.node.get();
        if (null != node.next) {
            node.next.locked = true;
            node.next = null;
            return;
        }
        if (tail.compareAndSet(node, null)) {return;}
        while (node.next == null) ;
    }

}

MCS 来自于发明人名字的首字母：John Mellor-Crummey 和 Michael Scott。

它也是一种基于链表的可扩大、高性能、偏心的自旋锁，但与 CLH 不同。它是真的有下一个节点 next，增加这个实在节点后，它就能够只在本地变量上自旋，而 CLH 是前驱节点的属性上自旋。

因为自旋节点的不同，导致 CLH 更适宜于 SMP 架构、MCS 能够适宜 NUMA 非统一存储拜访架构。你能够设想成 CLH 更须要线程数据在同一块内存上成果才更好，MCS 因为是在本店变量自选，所以无论数据是否扩散在不同的 CPU 模块都没有影响。

代码实现上与 CLH 没有太多差别，这里就不在叙述了，能够看代码学习。

public class TicketLock implements Lock {private AtomicInteger serviceCount = new AtomicInteger(0);
    private AtomicInteger ticketCount = new AtomicInteger(0);
    private final ThreadLocal<Integer> owner = new ThreadLocal<>();

    @Override
    public void lock() {owner.set(ticketCount.getAndIncrement());
        while (serviceCount.get() != owner.get());
    }

    @Override
    public void unlock() {serviceCount.compareAndSet(owner.get(), owner.get() + 1);
        owner.remove();}
}

TicketLock 就像你去银行、呷哺给你的一个排号卡一样，叫到你号你能力进去。属于严格的公平性实现，然而多处理器零碎上，每个过程 / 线程占用的处理器都在读写同一个变量，每次读写操作都须要进行多解决间的缓存同步，十分耗费零碎性能。

代码实现上也比较简单，lock() 中设置拥有者的号牌，并进入自旋比对。unlock() 中应用 CAS 进行解锁操作，并解决移除。

ReentrantLock 是基于 Lock 实现的可重入锁，对于偏心锁 CLH 的实现，只是这部分常识的冰山一角，但有这一脚，就能够很好热身便于后续的学习。
ReentrantLock 应用起来更加灵便，可操作性也更大，但肯定要在 finally 中开释锁，目标是保障在获取锁之后，最终可能被开释。同时不要将获取锁的过程写在 try 外面。
偏心锁的实现根据不同场景和 SMP、NUMA 的应用，会有不同的优劣成果。在理论的应用中个别默认会抉择非偏心锁，即便是自旋也是消耗性能的，个别会用在较少期待的线程中，防止自旋时过长。

synchronized 解毒，分析源码深度剖析！
面试官，ThreadLocal 你要这么问，我就挂了！
扫盲 java.util.Collections 工具包，学习排序、二分、洗牌、旋转算法
HashMap 外围常识，扰动函数、负载因子、扩容链表拆分
Netty+JavaFx 实战：仿桌面版微信聊天！

正文完

java

发表至： java

2020-11-05

0

Spring 指南（构建RESTful Web服务）

pdf png 转换超清

关于java:populate

关于java:Java基础一一抽象类接口内部类的概念及用法

关于java:深入理解JAVA并发锁

关于java:面经手册-第16篇码农会锁ReentrantLock之公平锁讲解和实现

一、前言

二、面试题

三、ReentrantLock 和偏心锁

1. ReentrantLock 介绍

2. ReentrantLock 常识链条

3. ReentrantLock 偏心锁代码

3.1 初始化

3.2 偏心锁、非偏心锁，抉择

3.3 hasQueuedPredecessors

3.4 队列首位判断

四、什么是偏心锁

五、偏心锁实现

1. CLH

1.1 看图谈话

1.2 代码实现

1.3 代码解说

2. MCSLock

2.1 代码实现

2.1 代码解说

3. TicketLock

3.1 看图谈话

3.2 代码实现

3.3 代码解说

六、总结

七、系列举荐

站内搜索

关于java:面经手册-第16篇码农会锁ReentrantLock之公平锁讲解和实现

一、前言

二、面试题

三、ReentrantLock 和 偏心锁

1. ReentrantLock 介绍

2. ReentrantLock 常识链条

3. ReentrantLock 偏心锁代码

3.1 初始化

3.2 偏心锁、非偏心锁，抉择

3.3 hasQueuedPredecessors

3.4 队列首位判断

四、什么是偏心锁

五、偏心锁实现

1. CLH

1.1 看图谈话

1.2 代码实现

1.3 代码解说

2. MCSLock

2.1 代码实现

2.1 代码解说

3. TicketLock

3.1 看图谈话

3.2 代码实现

3.3 代码解说

六、总结

七、系列举荐

站内搜索

三、ReentrantLock 和偏心锁