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的更多相关文章

  1. 放弃antd table,基于React手写一个虚拟滚动的表格

    缘起 标题有点夸张,并不是完全放弃antd-table,毕竟在react的生态圈里,对国人来说,比较好用的PC端组件库,也就antd了.即便经历了2018年圣诞彩蛋事件,antd的使用者也不仅不减,反 ...

  2. 只会用就out了,手写一个符合规范的Promise

    Promise是什么 所谓Promise,简单说就是一个容器,里面保存着某个未来才会结束的事件(通常是一个异步操作)的结果.从语法上说,Promise 是一个对象,从它可以获取异步操作的消息.Prom ...

  3. 利用SpringBoot+Logback手写一个简单的链路追踪

    目录 一.实现原理 二.代码实战 三.测试 最近线上排查问题时候,发现请求太多导致日志错综复杂,没办法把用户在一次或多次请求的日志关联在一起,所以就利用SpringBoot+Logback手写了一个简 ...

  4. 手写一个线程池,带你学习ThreadPoolExecutor线程池实现原理

    摘要:从手写线程池开始,逐步的分析这些代码在Java的线程池中是如何实现的. 本文分享自华为云社区<手写线程池,对照学习ThreadPoolExecutor线程池实现原理!>,作者:小傅哥 ...

  5. 『练手』手写一个独立Json算法 JsonHelper

    背景: > 一直使用 Newtonsoft.Json.dll 也算挺稳定的. > 但这个框架也挺闹心的: > 1.影响编译失败:https://www.cnblogs.com/zih ...

  6. 教你如何使用Java手写一个基于链表的队列

    在上一篇博客[教你如何使用Java手写一个基于数组的队列]中已经介绍了队列,以及Java语言中对队列的实现,对队列不是很了解的可以我上一篇文章.那么,现在就直接进入主题吧. 这篇博客主要讲解的是如何使 ...

  7. 【spring】-- 手写一个最简单的IOC框架

    1.什么是springIOC IOC就是把每一个bean(实体类)与bean(实体了)之间的关系交给第三方容器进行管理. 如果我们手写一个最最简单的IOC,最终效果是怎样呢? xml配置: <b ...

  8. 搞定redis面试--Redis的过期策略?手写一个LRU?

    1 面试题 Redis的过期策略都有哪些?内存淘汰机制都有哪些?手写一下LRU代码实现? 2 考点分析 1)我往redis里写的数据怎么没了? 我们生产环境的redis怎么经常会丢掉一些数据?写进去了 ...

  9. 手写一个简单的ElasticSearch SQL转换器(一)

    一.前言 之前有个需求,是使ElasticSearch支持使用SQL进行简单查询,较新版本的ES已经支持该特性(不过貌似还是实验性质的?) ,而且git上也有elasticsearch-sql 插件, ...

  10. 看年薪50W的架构师如何手写一个SpringMVC框架

    前言 做 Java Web 开发的你,一定听说过SpringMVC的大名,作为现在运用最广泛的Java框架,它到目前为止依然保持着强大的活力和广泛的用户群. 本文介绍如何用eclipse一步一步搭建S ...

随机推荐

  1. DevExpress GridControl使用方法总结(转)

    一.如何解决单击记录整行选中的问题 View->OptionsBehavior->EditorShowMode 设置为:Click 二.如何新增一条记录 (1).gridView.AddN ...

  2. jenkins持续集成工具

    jenkins是开源的 持续集成.持续构建的可视化web工具,持续构建说直白,就是各种项目的自动化编译.打包.分发部署. 好很多优点: 1.支持多语言 2.跟svn.git能无缝集成 3.直接与知名源 ...

  3. 实习笔记-3:ef实体操作错误篇

    学习笔记 1.json序列化ef实体是报错:“序列化类型为“System.Data.Entity.DynamicProxies.XXXX.... 对象时检测到循环引用.” 公司里用ef来生成实体.但是 ...

  4. Omi v1.0震撼发布 - 令人窒息的Web组件化框架

    原文链接--https://github.com/AlloyTeam/omi 写在前面 Omi框架经过几十个版本的迭代,越来越简便易用和强大. 经过周末的连续通宵加班加点,Omi v1.0版本终于问世 ...

  5. 201521123103 《Java学习笔记》 第四周学习总结

    一.本周学习总结 1.1 尝试使用思维导图总结有关继承的知识点. 1.2 使用常规方法总结其他上课内容. (1)多态性:相同形态,不同行为(不同的定义): (2)多态绑定:运行时能够自动地选择调用哪个 ...

  6. 6. 深度克隆_ES7**_arr.includes(&#39;孙悟空&#39;)

    1. 如何实现深度克隆 利用 JSON 方法 (没办法克隆函数数据) `JSON.parse(JSON.stringify(xxx))` 自定义方法 检查所有数据类型的方法 `Object.proto ...

  7. hive函数--编码解码

    以UTF-8为例: 测试字符串:️午后咖啡️ 一.编码 hive"); 输出: %E2%98%95%EF%B8%8F%E5%8D%88%E5%90%8E%E5%92%96%E5%95%A ...

  8. windows解决访问github慢问题

    ·1.更改host文件 文件地址: C:\Windows\System32\Drivers\etc ​ 如果不能直接修改,可拷贝到桌面修改后再复制回去 2.在host文件追加 ​ #github 19 ...

  9. 用react编写一个可以编辑的表格

    这只一个雏形,但是可以用了.难点是如何点击每行后面的编辑按钮,让当前行的格子都变成input. import {Component} from 'react' const Action = props ...

  10. python singleton design pattern super() 多继承

    python  singleton design pattern decorate baseclass metaclass import module super() 一.A decorator de ...