AQS为什么用双向链表?

news/2024/5/17 12:11:54/文章来源:https://blog.csdn.net/qq_33129875/article/details/129340385

首先,在AQS中,等待队列是通过Node类来表示的,每个Node节点包含了等待线程的信息以及等待状态。下面是Node类的部分源码:

static final class Node {// 等待状态volatile int waitStatus;// 前驱节点volatile Node prev;// 后继节点volatile Node next;// 等待线程volatile Thread thread;// 等待条件Node nextWaiter;// ...省略其他代码...
}

从上面的代码可以看出,每个Node节点都有一个指向前驱节点和后继节点的指针,这样可以在O(1)时间内查找前驱和后继节点。

接下来,我们来看看AQS是如何使用双向链表来管理等待队列的。AQS内部有一个成员变量volatile Node head,它表示等待队列的头节点。当一个线程需要等待锁或条件时,它会创建一个Node节点并插入到等待队列的尾部。这个过程是通过以下方法实现的:

private Node addWaiter(Node mode) {// 创建一个Node节点,表示当前线程Node node = new Node(Thread.currentThread(), mode);// 尝试通过CAS操作将Node节点插入到等待队列的尾部Node pred = tail;if (pred != null) {node.prev = pred;if (compareAndSetTail(pred, node)) {pred.next = node;return node;}}enq(node);return node;
}

在上面的代码中,首先创建了一个Node节点表示当前线程,然后尝试通过CAS操作将它插入到等待队列的尾部。如果CAS操作失败,说明有其他线程正在修改等待队列,此时会调用enq()方法来将节点插入到队列中。

private Node enq(final Node node) {for (;;) {Node t = tail;if (t == null) { // 如果队列为空,需要先初始化队列if (compareAndSetHead(new Node()))tail = head;} else { // 如果队列不为空,将节点插入到队列尾部node.prev = t;if (compareAndSetTail(t, node)) {t.next = node;return t;}}}
}

在enq()方法中,首先获取等待队列的尾节点,如果尾节点为空,说明队列还没有初始化,需要先创建一个空的头节点来初始化队列。如果尾节点不为空,就将新的节点插入到尾节点的后面。如果CAS操作失败,说明有其他线程正在修改等待队列,这时需要重新尝试。

当一个线程持有锁的线程释放锁时,它会将等待队列的头节点出队并唤醒它的后继节点,这个过程是通过以下方法实现的:

private void setHead(Node node) {head = node;node.thread = null;node.prev = null;
}private void unparkSuccessor(Node node) {int ws = node.waitStatus;if (ws < 0)compareAndSetWaitStatus(node, ws, 0);Node s = node.next;if (s == null || s.waitStatus > 0) {s = null;for (Node t = tail; t != null && t != node; t = t.prev)if (t.waitStatus <= 0)s = t;}if (s != null)LockSupport.unpark(s.thread);
}

在上面的代码中,首先将头节点设置为当前节点,然后将头节点的prev指针置为null,表示它已经出队了,将头节点的thread指针置为null,表示当前线程不再持有锁。接下来,通过unparkSuccessor()方法唤醒后继节点。这个方法中,首先检查当前节点的等待状态,如果它的等待状态小于0,说明它是一个被取消的节点,将它的等待状态置为0。然后,找到当前节点的后继节点,如果它不存在或者它的等待状态大于0,说明它不能被唤醒,这时就需要从等待队列的尾部开始往前找,找到一个等待状态小于等于0的节点来唤醒。最后,通过LockSupport.unpark()方法唤醒后继节点的线程。

从双向链表的特性来看,我认为AQS使用双向链表有三个方面的考虑。

第一个方面,没有竞争到锁的线程加入到阻塞队列,并且阻塞等待的前提是,当前线程所在节点的前置节点是正常状态,

这样设计是为了避免链表中存在异常线程导致无法唤醒后续线程的问题。

所以线程阻塞之前需要判断前置节点的状态,如果没有指针指向前置节点,就需要从head节点开始遍历,性能非常低。

第二个方面,在Lock接口里面有一个,lockInterruptibly()方法,这个方法表示处于锁阻塞的线程允许被中断。

也就是说,没有竞争到锁的线程加入到同步队列等待以后,是允许外部线程通过interrupt()方法触发唤醒并中断的。

这个时候,被中断的线程的状态会修改成CANCELLED。

被标记为CANCELLED状态的线程,是不需要去竞争锁的,但是它仍然存在于双向链表里面。

意味着在后续的锁竞争中,需要把这个节点从链表里面移除,否则会导致锁阻塞的线程无法被正常唤醒。

在这种情况下,如果是单向链表,就需要从Head节点开始往下逐个遍历,找到并移除异常状态的节点。

同样效率也比较低,还会导致锁唤醒的操作和遍历操作之间的竞争。

第三个方面,为了避免线程阻塞和唤醒的开销,所以刚加入到链表的线程,首先会通过自旋的方式尝试去竞争锁。

但是实际上按照公平锁的设计,只有头节点的下一个节点才有必要去竞争锁,后续的节点竞争锁的意义不大。

否则,就会造成羊群效应,也就是大量的线程在阻塞之前尝试去竞争锁带来比较大的性能开销。

所以为了避免这个问题,加入到链表中的节点在尝试竞争锁之前,需要判断前置节点是不是头节点,如果不是头节点,就没必要再去触发锁竞争的动作。

所以这里会涉及到前置节点的查找,如果是单向链表,那么这个功能的实现会非常复杂。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_77543.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

十一、GoF之代理模式

1 对代理模式的理解 【在程序中&#xff0c;对象A和对象B无法直接交互时。】 【在程序中&#xff0c;功能需要增强时。】 【在程序中&#xff0c;目标需要被保护时】 业务场景&#xff1a;系统中有A、B、C三个模块&#xff0c;使用这些模块的前提是需要用户登录&#xff0c;也…

总结磁共振成像的脑龄预测的人工智能模型

脑龄预测的人工智能模型 介绍基于神经影像的BA预测BA预测建模:从统计方法到DL统计方法使用统计/最大似然估计方法的BA研究的主要结果深度学习使用DL方法进行BA研究的主要结果可解释的人工智能(即可解释的深度学习方案)可解释的能力(Interpretability,)、可因果性和可解释性…

Scrapy框架(高效爬虫)

文章目录一、环境配置二、创建项目三、scrapy数据解析四、基于终端指令的持久化存储1、基于终端指令2、基于管道3、数据同时保存至本地及数据库4、基于spider爬取某网站各页面数据5、爬取本页和详情页信息&#xff08;请求传参&#xff09;6、图片数据爬取ImagesPipeline五、中…

OpenGL中的坐标系

1、2D笛卡尔坐标系2D笛卡尔坐标系跟我们高中的时候学习的坐标系一样&#xff0c;是由x、y决定的。2、3D笛卡尔坐标系3D笛卡尔坐标系坐标由x、y、z决定&#xff0c;满足右手定则。3、视口glViewport(GLint x,GLint y,GLsizei width,GLsizei height)窗口和视口大小可以相同&#…

【2023unity游戏制作-mango的冒险】-前六章API,细节,BUG总结小结

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! 本文由 秩沅 原创 收录于专栏&#xff1a;unity游戏制作 ⭐mango的冒险前六章总结⭐ 文章目录⭐mango的冒险前六章总结⭐&#x1f468;‍&a…

【图神经网络】李宏毅

GNN 引入 假如要预测一个人是否是凶手。可以通过每个角色的特征训练出一个分类器。 有没有我们忽略的信息&#xff0c;或者我们可以利用但没有完全利用的信息。就是角色的关系。 这些角色关系可以让我们在做分类的时候获得一些额外的信息&#xff0c;可以帮助我们做更好的mode…

一文带你入门,领略angular风采(上)!!!

话不多说&#xff0c;上代码&#xff01;&#xff01;&#xff01; 一、脚手架创建项目 1.安装脚手架指令 npm install -g angular/cli 2.创建项目 ng new my-app(ng new 项目名) 3.功能选择 4.切换到创建好的项目上 cd my-app 5.安装依赖 npm install 6.运行项目 npm start或…

Trace、Metrics、Logging 选型

背景分布式追踪的起源自从微服务的兴起开始&#xff0c;整个系统架构开始变得极为庞大和复杂&#xff0c;但是服务之间的调用关系&#xff0c;调用消耗时间等等信息却依然是半黑盒的状态。为了能够将调用的链路进行串联&#xff0c;将系统的各种指标数据展示出来以使得系统的链…

NLP预训练模型

Models Corpus RoBERTa: A Robustly Optimized BERT Pretraining Approach 与BERT主要区别在于&#xff1a; large mini-batches 保持总训练tokens数一致&#xff0c;使用更大的学习率、更大的batch size&#xff0c;adam β20.98\beta_20.98β2​0.98&#xff1b;dynamic ma…

Typora上传文档图片链接失效的问题+PicGo布置图床在Github

文章目录typora图片链接失效原因PicGO开源图床布置先配置Github2.1先创建新仓库、用于存放图片2.2生成一个token&#xff0c;用picGo访问github3.下载picGo,并进行配置3.1 配置v4.1typora图片链接失效原因 因为你是保存在本地的&#xff0c;因此图片是不能访问&#xff0c;可以…

语法篇--汇编语言先导浅尝

一、相关概念 1.机器语言 机器语言&#xff08;Machine Language&#xff09;是一种计算机程序语言&#xff0c;由二进制代码&#xff08;0和1&#xff09;组成&#xff0c;可被计算机直接执行。机器语言是计算机硬件能够理解和执行的唯一语言。 机器语言通常由一系列的指令组…

20230304 CF855 div3 vp

Dashboard - Codeforces Round 855 (Div. 3) - Codeforces呃呃&#xff0c;评价是&#xff0c;毫无进步呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃该加训了该加训了该加训了该加训了该加训了该加训了该加训了该加训了该加训了该加训了该加训了该加训了该加训了该加训了该加训了该加训…

RocketMQ Broker消息处理流程剩余源码解析

&#x1f34a; Java学习&#xff1a;Java从入门到精通总结 &#x1f34a; 深入浅出RocketMQ设计思想&#xff1a;深入浅出RocketMQ设计思想 &#x1f34a; 绝对不一样的职场干货&#xff1a;大厂最佳实践经验指南 &#x1f4c6; 最近更新&#xff1a;2023年3月4日 &#x1…

高性能网络I/O框架-netmap源码分析

前几天听一个朋友提到这个netmap&#xff0c;看了它的介绍和设计&#xff0c;确实是个好东西。其设计思想与业界不谋而合——因为为了提高性能&#xff0c;几个性能瓶颈放在那里&#xff0c;解决方法自然也是类似的。 netmap的出现&#xff0c;它既实现了一个高性能的网络I/O框…

aws eks 集群初始化过程中pause容器的启动逻辑

eks集群默认策略在磁盘使用量达到threshold时会清除镜像&#xff0c;其中pause镜像也可能会被清除 https://aws.amazon.com/cn/premiumsupport/knowledge-center/eks-worker-nodes-image-cache/ pause容器能够为pod创建初始的名称空间&#xff0c;pod的内的容器共享其中的网络空…

51单片机入门————数码管显示

我们在马路上看到的红绿灯&#xff0c;就是由数码管来实现的&#xff0c;就是其中可能加入了一些延时和转换数码管是通过控制138译码器与74HC245来控制数码管的亮灭与数字的显示电路原理图我们先讨论一个数码管数码管有共阳极和共阴极&#xff0c;我们现在使用的STC89C52是共阴…

通用游戏地图解决方案设计解析

前言&#xff1a; 在软件开发过程中&#xff0c;我们都希望能设计出一个稳健的&#xff0c;可维护的系统&#xff0c;为了实现这个目的&#xff0c;人们总结出了很多相关的设计原则&#xff0c;比如SOLID原则&#xff0c; KISS原则等等。SOLID每个字母代表了一种设计原则&…

Android onLayout布局流程解析

组件布局流程结论 1.&#xff09;layout流程始于ViewRootImpl的performLayout()方法&#xff0c;该方法会调用根View&#xff08;DecorView&#xff09;的layout()方法进行布局&#xff0c;因为DecorView是ViewGroup(FrameLayout),所以layout流程来到了ViewGroup&#xff08;其…

开发手册——一、编程规约_8.注释规约

这篇文章主要梳理了在java的实际开发过程中的编程规范问题。本篇文章主要借鉴于《阿里巴巴java开发手册终极版》 下面我们一起来看一下吧。 1. 【强制】类、类属性、类方法的注释必须使用 Javadoc 规范&#xff0c;使用 /**内容*/ 格式&#xff0c;不得使用 // xxx 方式。 说…

idea通过Dockerfile上传项目到服务器

Docker通过Dockerfile上传项目 文章目录Docker通过Dockerfile上传项目1.创建一个简单的springBoot项目2.写一个简单的接口3.写Dockerfile文件4.新建docker镜像5.上传代码运行1.创建一个简单的springBoot项目 点击文件–>新建–>项目 点击选择Spring Initializer &#x…