package cn.daheww.demo.juc.reentrylock;
import sun.misc.Unsafe;
import java.lang.reflect.Field;
import java.util.concurrent.locks.LockSupport;
/**
* @author daheww
* @date 2022/7/7
*/
public class MiniReentryLock implements Lock {
/**
* 锁的是什么 --> 资源 --> state
* 0 --> 未加锁
* >0 -> 加锁
*/
private volatile int state;
/**
* 独占模式
* 同一时刻只有一个线程可以持有锁，其它线程在未获取到锁的时候会被阻塞
*
* 当前独占锁的线程（占用锁的线程）
*/
private Thread exclusiveOwnerThread;
/**
* 需要有两个节点去维护阻塞队列
* Head 指向队列的头节点
* Tail 指向队列的尾节点
*
* 比较特殊：Head节点对应的线程就是当前占用锁的线程
*/
private Node head;
private Node tail;
/**
* 获取锁
* 假设当前锁被占用，则会阻塞调用者线程，直到它抢占到锁为止
*
* 模拟公平锁
* --> 先来后到
*
* lock的过程
* 情景1.线程进来后发现，当前state == 0 --> 直接去抢锁
* 情景2.线程进来后发现，当前state > 0 --> 将当前线程入队
*/
@Override
public void lock() {
// 第一次获取到锁时，将state设置为1
// 第n次重入时，将state设置为n
acquire(1);
}
@Override
public void unlock() {
release(1);
}
private void release(int arg) {
// 条件成立：说明线程已经完全释放锁了
if (tryRelease(arg)) {
// 阻塞队列里面，还有睡觉的线程，应该唤醒一个线程
// 首先需要知道有没有等待的node --> head.next == null
Node head = this.head;
if (head.nx != null) {
// 公平锁，唤醒head.nx节点
unparkSuccessor(head);
}
}
}
private void unparkSuccessor(Node node) {
Node s = node.nx;
if (s != null && s.thread != null) {
LockSupport.unpark(s.thread);
}
}
/**
* 完全释放锁成功则返回true
*/
private boolean tryRelease(int arg) {
int c = getState() - arg;
if (getExclusiveOwnerThread() != Thread.currentThread()) {
throw new RuntimeException("must get lock first");
}
// 如果执行到这里，不存在并发，只会有一个线程会来到这里
// 条件成立，则说明当前线程持有的lock锁已经完全释放了
if (c == 0) {
this.exclusiveOwnerThread = null;
this.state = c;
return true;
} else {
this.state = c;
return false;
}
}
/**
* 竞争资源
* 1.尝试获取锁。成功则占用锁，且返回
* 2.抢占锁失败，阻塞当前线程
* @param arg
*/
private void acquire(int arg) {
if (!tryAcquire(arg)) {
// 抢锁失败
// step1.将当前线程封装成node，加入到阻塞队列中
Node node = addWaiter();
// step2.将当前线程park，使线程处于挂起状态
acquireQueued(node, arg);
}
// 抢锁成功
// 1.抢到了锁
// 2.重入了锁
}
/**
* 尝试抢锁失败，需要做的事：
* 1.需要将当前线程封装成node，加入到阻塞队列中
* 2.需要将当前线程park，使线程处于挂起状态
*
* 唤醒的流程：
* 1.检查当前node是否为head.next节点
* head.next是拥有抢占权限的线程，其它node都没有抢占的权限
* 2.抢占：
* 成功：
* 1.将当前node设置为node，将老的head出队，返回到业务层面
* 2.继续park等待被唤醒
*
* ----------------------------------------------
* 1.添加到阻塞队列的逻辑 addWaiter()
* 2.竞争资源的逻辑 acquireQueued()
*/
private void acquireQueued(Node node, int arg) {
// 当前线程已经放到queue中了
// 只有当前node成功获取到锁以后才会跳出自旋
for (; ; ) {
// 什么情况下，当前node被唤醒后可以尝试去获取锁呢？
// 只有一种情况，当前node是head的后继节点，才有这个权限
// 不是就先来后到
Node pvNode = node.pv;
// 条件1：pvNode == head
// true --> 说明当前node拥有抢占权限
// queue中的第一个节点代表的是当前锁正在执行的线程 --> head指向的线程
// head后面的线程代表的是正在排队的线程 --> 所以只有head.nx节点拥有抢锁的权利
// 条件2：tryAcquire(arg)
// true --> 当前线程获取到了锁
//
if (pvNode == head && tryAcquire(arg)) {
// 进入到这里面说明当前线程竞争锁成功了
// 需要做的操作：
// 1.设置当前head为当前线程的node
// 2.协助原来的对象出队
setHead(node);
pvNode.nx = null;
// 因为获取到了锁，所以就return了
return;
}
// 当前不是head.nx节点，或者去尝试获取锁失败了，这个时候都需要去把当前线程park掉
System.out.println("线程：" + Thread.currentThread().getName() + " 挂起");
LockSupport.park();
// 直到某个线程做了当前线程的unPark操作，这个线程才会继续执行
/*
所以总结一下，lock的逻辑就是：
1.在没锁的情况下，如果有个线程调用了lock方法，它就会改变lock中的state值。此时state值就不会为0了。
那么其它线程调用lock方法时，会看到这个state不为0。
2.然后这个线程会被封装成一个node节点
3.然后会去尝试竞争一下锁，做一下最后的挽救工作，如果实在挽救不了，就park了
--> 线程就在这个lock的lock()方法里被阻塞了。就达到了锁的效果
--> 所有调用这个锁对象lock的方法只能有一个线程能继续执行，然后其它线程会被阻塞，直到这个线程做了unlock操作
*/
System.out.println("线程：" + Thread.currentThread().getName() + " 唤醒");
// 什么时候唤醒被park的线程？--> unlock()
}
}
/**
* 把当前线程入队
* 返回当前线程对应的node节点
*
* addWaiter执行完成后，保证当前线程已经入队成功
*/
private Node addWaiter() {
Node newNode = new Node(Thread.currentThread());
// 如何入队？
// Case1.当前node不是第一个入队的node，队列已经有等待的node了
// 1.找到newNode的pv节点
// 2.更新newNode.pvNode = pv节点
// 3.CAS更新tail为newNode
// 4.更新pv节点
Node pvNode = tail;
if (pvNode != null) {
newNode.pv = pvNode;
// 条件成立，说明当前线程成功入队
if (compareAndSetTail(pvNode, newNode)) {
pvNode.nx = newNode;
return newNode;
}
}
// 执行到这里的几种情况
// 1.tail == null队列是空
// 2.cas设置当前newNode为tail时失败了 --> 循环入队 --> 自旋
enq(newNode);
return newNode;
}
/**
* 自旋入队，只有成功之后才返回
* 1.tail == null 队列是空队列
* 2.cas设置当前newNode为tail时失败了
*/
private void enq(Node node) {
for (; ; ) {
// 第一种情况：队列是空队列
// --> 当前线程是第一个抢占锁的线程...
// 当前持有锁的线程，并没有设置过任何node，所以作为该线程的第一个后驱节点
// 需要给他擦屁股
// 给当前持有锁的线程补充一个node作为head节点
// head节点任何时候都代表当前占用锁的线程
if (tail == null) {
// 条件成立：说明当前线程给当前持有锁的线程补充head操作成功了
if (compareAndSetHead(new Node())) {
tail = head;
// 注意，并没有直接返回，而是会继续自旋
}
} else {
// 当前队列中已经有node了，说明这是一个追加node的过程
// 如何入队呢？
// 1.找到newNode的pv节点 --> 最新的tail节点
// 2.更新newNode.pvNode = pv节点
// 3.CAS更新tail为newNode
// 4.更新pv节点
Node pvNode = tail;
node.pv = pvNode;
// 条件成立，说明当前线程成功入队
if (compareAndSetTail(pvNode, node)) {
pvNode.nx = node;
return;
}
}
}
}
/**
* 尝试获取锁，不会去阻塞线程
* true --> 抢占成功
* false --> 抢占失败
*/
private boolean tryAcquire(int arg) {
if (state == 0) {
// 当前state为0
// 不能直接抢锁 --> 公平锁 --> 先来后到
// 条件一：!hasQueuedPredecessors() ---> 取反之后为true，表示当前线程前面没有等待着的线程
// 条件二：compareAndSetState(0, arg) -> 使用cas的原因：lock方法可能有多线程调用的情况
// true --> 当前线程抢锁成功
// (1) volatile --> state被volatile修饰了，所以其它线程能第一时间知道这个值不为0了 --> 缓存能够一致了
// (2) cas -------> state从0变为arg的操作用cas实现，用于保证只会有一个线程能够改变state的值（0->arg） --> 只会有一个线程能够执行接下来的操作 --> 锁
// 1.如果cas的变量不用volatile修饰就没有意义：
// 因为A线程改变了state的值，但是B线程并不知道
// （可见性，volatile会让B线程中的副本马上失效，然后获取最新的state的值，此时B线程工作空间中的state值就不为0了）
// 2.如果volatile的变量不用cas去改变它的值的话，也没有意义：
//· step1.A线程，B线程都拿到了state的副本信息，此时state值为0
// step2.A线程改变了state的值。B线程还在写，因为state的值改变了，所以B线程工作空间中的state值改变，然后B继续写。
// 所以所有判断出state值为0的线程都能写成功，并且能执行写成功后续的操作
// 所以要用cas+volatile去保证只会有一个线程能够写成功这个值
// Ps.可以看到，如果这些线程想写的值都是同一个值的话，多写了几次，但是结果和只写一次是一致的
// cas+volatile主要还是去控制写成功之后的操作只会被执行一次，这样就像一个锁一样了
if (!hasQueuedPredecessors() && compareAndSetState(0, arg)) {
// 抢锁成功
// 1.将exclusiveOwnerThread设置为当前线程
this.exclusiveOwnerThread = Thread.currentThread();
return true;
// 不会入队任何node，接返回true
// 接下来第一个竞争失败的线程会先去帮忙创建一个node，然后再执行后续的操作
}
// 当前线程前面有线程在等待 || 多个线程和当前线程一起在尝试获取这个锁，然后当前线程失败了 --> return false;
} else if (Thread.currentThread() == this.exclusiveOwnerThread) {
// 执行的时机：
// 1.当前锁被占用
// 2.当前线程即为持锁线程
// 这里面不存在并发。只有当前加锁的线程才有权限修改state
// 即使是同一个线程多次进入到这，设置state的值，那么它们都是使用的同一个工作空间
// 不存在不同工作空间下，这个值的不一样的情况（因为没有了缓存）
// 锁重入的流程
int c = getState();
c += arg;
// TODO 越界判断
this.state = c;
return true;
}
// 什么时候会返回false？
// 1.cas加锁失败
// 2.state大于0，且当前线程不是持锁线程
return false;
}
/**
* 当前线程前面是否有等待着的线程
* true --> 当前线程前面有等待着的线程
* false -> 当前线程前面没有其它等待着的线程
*
* 调用链
* lock --> acquire -> tryAcquire -> hasQueuedPredecessors(state值为0时，即当前lock为无主状态)
*
* 什么时候返回false？
* 1.当前队列是空
* 2.当前线程为head.next节点 --> head.next在任何时候都有权力去争取lock
*/
private boolean hasQueuedPredecessors() {
Node h = head;
Node t = tail;
Node s;
// 条件一：h != t
// true --> 当前队列已经有node了
// false -> h == t
// case1. h == t == null --> 还没初始化过queue
// case2. h == t == head
// 第一个获取锁失败的线程会为当前持有锁的线程补充创建一个head node
// 条件二：
// 前置条件：条件一成立
// 排除几种情况：
// 条件2.1：极端情况 --> 第一个获取锁失败的线程，会为持锁的线程补充创建head节点，然后在自旋入队
// step1.cas设置tail成功了
// step2.head.next = node
// 在这两步中间的时候，有线程来检查前面是否有等待的线程
// 这种情况应该返回true：已经有head.next节点了，其它线程来这的时候需要返回true
// 条件2.2：
// 前置条件：h.next不是null
// true --> 条件成立说明当前线程就是持有锁的线程
// false -> 说明当前线程就是h.next节点对应的线程，需要返回false。回头线程就会去竞争锁了
return h != t && ((s = h.nx) == null || s.thread != Thread.currentThread());
}
private static final Unsafe UNSAFE;
private static final long STATE_OFFSET;
private static final long HEAD_OFFSET;
private static final long TAIL_OFFSET;
static {
try {
Field f = Unsafe.class.getDeclaredField("theUnsafe");
f.setAccessible(true);
UNSAFE = (Unsafe) f.get(null);
STATE_OFFSET = UNSAFE.objectFieldOffset(MiniReentryLock.class.getDeclaredField("state"));
HEAD_OFFSET = UNSAFE.objectFieldOffset(MiniReentryLock.class.getDeclaredField("head"));
TAIL_OFFSET = UNSAFE.objectFieldOffset(MiniReentryLock.class.getDeclaredField("tail"));
} catch (Exception e) {
throw new Error(e);
}
}
private boolean compareAndSetHead(Node update) {
return UNSAFE.compareAndSwapObject(this, HEAD_OFFSET, null, update);
}
private boolean compareAndSetTail(Node expect, Node update) {
return UNSAFE.compareAndSwapObject(this, TAIL_OFFSET, expect, update);
}
private boolean compareAndSetState(int expect, int update) {
return UNSAFE.compareAndSwapInt(this, STATE_OFFSET, expect, update);
}
/**
* 阻塞的线程被封装成node节点，然后放进FIFO队列
*/
static final class Node {
/**
* 封装的线程本身
*/
Thread thread;
/**
* 前置节点引用
*/
Node pv;
/**
* 后置节点引用
*/
Node nx;
public Node(Thread thread) {
this.thread = thread;
}
public Node() {
}
}
public int getState() {
return state;
}
private void setHead(Node node) {
this.head = node;
// 当前线程已经是获取到锁的线程
node.thread = null;
node.pv = null;
}
public void setState(int state) {
this.state = state;
}
public Thread getExclusiveOwnerThread() {
return exclusiveOwnerThread;
}
public void setExclusiveOwnerThread(Thread exclusiveOwnerThread) {
this.exclusiveOwnerThread = exclusiveOwnerThread;
}
public Node getHead() {
return head;
}
public Node getTail() {
return tail;
}
public void setTail(Node tail) {
this.tail = tail;
}
}
手写一个模拟的ReentrantLock的更多相关文章
- 放弃antd table，基于React手写一个虚拟滚动的表格
缘起 标题有点夸张,并不是完全放弃antd-table,毕竟在react的生态圈里,对国人来说,比较好用的PC端组件库,也就antd了.即便经历了2018年圣诞彩蛋事件,antd的使用者也不仅不减,反 ...
- 只会用就out了，手写一个符合规范的Promise
Promise是什么 所谓Promise,简单说就是一个容器,里面保存着某个未来才会结束的事件(通常是一个异步操作)的结果.从语法上说,Promise 是一个对象,从它可以获取异步操作的消息.Prom ...
- 利用SpringBoot+Logback手写一个简单的链路追踪
目录 一.实现原理 二.代码实战 三.测试 最近线上排查问题时候,发现请求太多导致日志错综复杂,没办法把用户在一次或多次请求的日志关联在一起,所以就利用SpringBoot+Logback手写了一个简 ...
- 手写一个线程池，带你学习ThreadPoolExecutor线程池实现原理
摘要:从手写线程池开始,逐步的分析这些代码在Java的线程池中是如何实现的. 本文分享自华为云社区<手写线程池,对照学习ThreadPoolExecutor线程池实现原理!>,作者:小傅哥 ...
- 『练手』手写一个独立Json算法 JsonHelper
背景: > 一直使用 Newtonsoft.Json.dll 也算挺稳定的. > 但这个框架也挺闹心的: > 1.影响编译失败:https://www.cnblogs.com/zih ...
- 教你如何使用Java手写一个基于链表的队列
在上一篇博客[教你如何使用Java手写一个基于数组的队列]中已经介绍了队列,以及Java语言中对队列的实现,对队列不是很了解的可以我上一篇文章.那么,现在就直接进入主题吧. 这篇博客主要讲解的是如何使 ...
- 【spring】-- 手写一个最简单的IOC框架
1.什么是springIOC IOC就是把每一个bean(实体类)与bean(实体了)之间的关系交给第三方容器进行管理. 如果我们手写一个最最简单的IOC,最终效果是怎样呢? xml配置: <b ...
- 搞定redis面试--Redis的过期策略？手写一个LRU？
1 面试题 Redis的过期策略都有哪些?内存淘汰机制都有哪些?手写一下LRU代码实现? 2 考点分析 1)我往redis里写的数据怎么没了? 我们生产环境的redis怎么经常会丢掉一些数据?写进去了 ...
- 手写一个简单的ElasticSearch SQL转换器(一)
一.前言 之前有个需求,是使ElasticSearch支持使用SQL进行简单查询,较新版本的ES已经支持该特性(不过貌似还是实验性质的?) ,而且git上也有elasticsearch-sql 插件, ...
- 看年薪50W的架构师如何手写一个SpringMVC框架
前言 做 Java Web 开发的你,一定听说过SpringMVC的大名,作为现在运用最广泛的Java框架,它到目前为止依然保持着强大的活力和广泛的用户群. 本文介绍如何用eclipse一步一步搭建S ...
随机推荐
- DevExpress GridControl使用方法总结（转）
一.如何解决单击记录整行选中的问题 View->OptionsBehavior->EditorShowMode 设置为:Click 二.如何新增一条记录 (1).gridView.AddN ...
- jenkins持续集成工具
jenkins是开源的 持续集成.持续构建的可视化web工具,持续构建说直白,就是各种项目的自动化编译.打包.分发部署. 好很多优点: 1.支持多语言 2.跟svn.git能无缝集成 3.直接与知名源 ...
- 实习笔记-3：ef实体操作错误篇
学习笔记 1.json序列化ef实体是报错:“序列化类型为“System.Data.Entity.DynamicProxies.XXXX.... 对象时检测到循环引用.” 公司里用ef来生成实体.但是 ...
- Omi v1.0震撼发布 - 令人窒息的Web组件化框架
原文链接--https://github.com/AlloyTeam/omi 写在前面 Omi框架经过几十个版本的迭代,越来越简便易用和强大. 经过周末的连续通宵加班加点,Omi v1.0版本终于问世 ...
- 201521123103 《Java学习笔记》 第四周学习总结
一.本周学习总结 1.1 尝试使用思维导图总结有关继承的知识点. 1.2 使用常规方法总结其他上课内容. (1)多态性:相同形态,不同行为(不同的定义): (2)多态绑定:运行时能够自动地选择调用哪个 ...
- 6. 深度克隆_ES7**_arr.includes('孙悟空')
1. 如何实现深度克隆 利用 JSON 方法 (没办法克隆函数数据) `JSON.parse(JSON.stringify(xxx))` 自定义方法 检查所有数据类型的方法 `Object.proto ...
- hive函数--编码解码
以UTF-8为例: 测试字符串:️午后咖啡️ 一.编码 hive"); 输出: %E2%98%95%EF%B8%8F%E5%8D%88%E5%90%8E%E5%92%96%E5%95%A ...
- windows解决访问github慢问题
·1.更改host文件 文件地址: C:\Windows\System32\Drivers\etc 如果不能直接修改,可拷贝到桌面修改后再复制回去 2.在host文件追加 #github 19 ...
- 用react编写一个可以编辑的表格
这只一个雏形,但是可以用了.难点是如何点击每行后面的编辑按钮,让当前行的格子都变成input. import {Component} from 'react' const Action = props ...
- python singleton design pattern super() 多继承
python singleton design pattern decorate baseclass metaclass import module super() 一.A decorator de ...
![Cause analysis and solution of too laggy page of [test interview questions]](/img/8d/3ca92ce5f9cdc85d52dbcd826e477d.jpg)
