当前位置: 首页 > news >正文

AQS 为什么要使用双向链表?

双向链表

双向链表的特点是它有两个指针,一个指针指向前置节点,一个指针指向后继节点。所以,双向链表可以支持 常量 O(1) 时间复杂度的情况下找到前驱结点,基于这样的特点。双向链表在插入和删除操作的时候,要比单向链表简单、高效。

AQS使用双向链表

因此,从双向链表的特性来看,我认为 AQS 使用双向链表有三个方面的考虑:
第一个方面,没有竞争到锁的线程加入到阻塞队列,并且阻塞等待的前提是,当前线程所在节点的前置节点是正常状态,这样设计是为了避免链表中存在异常线程导致无法唤醒后续线程的问题(如图)所以线程阻塞之前需要判断前置节点的状态,如果没有指针指向前置节点,就需要从 head 节点开始遍历,性能非常低。

第二个方面,在 Lock 接口里面有一个,lockInterruptibly()方法,这个方法表示处于锁阻塞的线程允许被中断。也就是说,没有竞争到锁的线程加入到同步队列等待以后,是允许外部线程通过interrupt()方法触发唤醒并中断的。这个时候,被中断的线程的状态会修改成 CANCELLED。(如图)被标记为 CANCELLED 状态的线程,是不需要去竞争锁的,但是它仍然存在于双向链表里面。意味着在后续的锁竞争中,需要把这个节点从链表里面移除,否则会导致锁阻塞的线程无法被正常唤醒。在这种情况下,如果是单向链表,就需要从 Head 节点开始往下逐个遍历,找到并移除异常状态的节点。同样效率也比较低,还会导致锁唤醒的操作和遍历操作之间的竞争

第三个方面,为了避免线程阻塞和唤醒的开销,所以刚加入到链表的线程,首先会通过自旋的方式尝试去竞争锁。但是实际上按照公平锁的设计,只有头节点的下一个节点才有必要去竞争锁,后续的节点竞争锁的意义不大。否则,就会造成羊群效应,也就是大量的线程在阻塞之前尝试去竞争锁带来比较大的性能开销。所以,(如图)为了避免这个问题,加入到链表中的节点在尝试竞争锁之前,需要判断前置节点是不是头节点,如果不是头节点,就没必要再去触发锁竞争的动作。所以这里会涉及到前置节点的查找,如果是单向链表,那么这个功能的实现会非常复杂。

相关文章:

AQS 为什么要使用双向链表?

双向链表 双向链表的特点是它有两个指针,一个指针指向前置节点,一个指针指向后继节点。所以,双向链表可以支持 常量 O(1) 时间复杂度的情况下找到前驱结点,基于这样的特点。双向链表在插入和删除操作的时候,要比单向链…...

Golang 自定义函数库(个人笔记)

1.用字符串连接切片元素(类似php implode) package mainimport ("fmt""strconv""strings" )func main() {data : []int{104, 101, 108, 108, 111}fmt.Println(IntSliceToString(data, ",")) }func IntSliceToS…...

openlayers 地图组件封装

openlayers 地图组件封装 <template><div class"mapBox"><!-- 地图 --><div ref"map" id"map" class"map"></div><!-- 点位弹窗 --><div id"popup" class"ol-popup">…...

【算法设计与分析】—— 分治算法

&#x1f383;个人专栏&#xff1a; &#x1f42c; 算法设计与分析&#xff1a;算法设计与分析_IT闫的博客-CSDN博客 &#x1f433;Java基础&#xff1a;Java基础_IT闫的博客-CSDN博客 &#x1f40b;c语言&#xff1a;c语言_IT闫的博客-CSDN博客 &#x1f41f;MySQL&#xff1a…...

Unable to find GatewayFilterFactory with name TokenRelay

目录 问题分析解决方案参考文档开源项目微服务商城项目前后端分离项目 问题分析 Spring Cloud Gateway 网关作为代理资源服务器&#xff0c;需要将 JWT 传递给下游资源服务器&#xff0c;下面是网关的配置 spring:cloud:gateway:discovery:locator:enabled: true # 启用服务发…...

竞赛 深度学习大数据物流平台 python

文章目录 0 前言1 课题背景2 物流大数据平台的架构与设计3 智能车货匹配推荐算法的实现**1\. 问题陈述****2\. 算法模型**3\. 模型构建总览 **4 司机标签体系的搭建及算法****1\. 冷启动**2\. LSTM多标签模型算法 5 货运价格预测6 总结7 部分核心代码8 最后 0 前言 &#x1f5…...

git基础及原理相关解析

git入门 结构基本操作help提交分支git merge和git rebase对比 拉取 git文档 结构 工作区&#xff1a;电脑目录中能看到的文件暂存区&#xff1a;使用git add *操作提交文件的位置&#xff0c;一般位于.git\index&#xff0c;这个文件里面存储了当前位于暂存区的所有文件的校验…...

【Python机器学习】零基础掌握isotonic_regression等渗回归

遇到了数据不一致的困扰吗? 在市场分析、医疗研究或者其他数据密集型领域,经常会遇到一个问题:如何从一组不完全一致或者有噪音的数据中提取出有用的信息?例如,假设一家餐厅想要根据顾客的评分和消费金额来调整菜单。 顾客评分消费金额(元)顾客年龄访问次数4.21002533.…...

支持宏的文本编辑器提高生产力

场景 我们知道很多文本/代码编辑器支持宏的录制、重放、保存&#xff0c;甚至可以与快捷键命令结合的功能&#xff0c;快速实现重放宏的操作。 如果您的编辑器支持宏这项功能&#xff0c;请多使用 &#x1f603; 宏化自动步骤相当于对编辑器的自动化编程&#xff0c;宏录制可…...

JS中面向对象的程序设计

面向对象&#xff08;Object-Oriented&#xff0c;OO&#xff09;的语言有一个标志&#xff0c;那就是它们都有类的概念&#xff0c;而通过类可以创建任意多个具有相同属性和方法的对象。但在ECMAScript 中没有类的概念&#xff0c;因此它的对象也与基于类的语言中的对象有所不…...

云耀服务器L实例搭配负载均衡部署Linux 可视化宝塔面板

云耀服务器L实例搭配负载均衡部署Linux 可视化宝塔面板 1. 华为云云耀服务器L实例介绍 华为云云耀服务器L实例是一种高性能、高可靠性的云服务器实例&#xff0c;适用于大规模企业级应用、大数据分析等场景。它基于华为最新一代的硬件虚拟化技术&#xff0c;提供了更高的计算…...

mac pycharm配置autopep8

mac终端安装autopep8 pip install autopep8pycharm配置autopep8 在Pycharm中点击 File–Settings—Tools–External Tools, 点击图中绿色加号图标添加扩展工具&#xff0c;填写相关参数配置。 Name&#xff1a;Autopep8&#xff08;可以随便取&#xff09; Tools setting&…...

Vue $nextTick

我们用一个例子来说明$nextTick的作用&#xff1a; 我们用一个变量showIpt来控制input框的显示和隐藏&#xff0c;默认是隐藏。 我们点击一个按钮后显示这个输入框的同时&#xff0c;input还要自动获取焦点。 但是我们点击按钮过后并没有生效。 为什么&#xff1f;this.show…...

linux配置dns

服务器有网&#xff0c;ping IP 地址可以ping的通&#xff0c;但是ping网站域名ping不通&#xff0c;需要配置dns 使用公共dns服务器 1、设置dns服务器地址 vi /etc/resolv.conf 将谷歌的dns服务器地址添加到dns解析配置中 nameserver 8.8.8.8 nameserver 8.8.4.4 保存后&…...

12 原子性|可见性|有序性|JMM内存模型

1 并发三大特性 1.1 原子性 一个或多个操作&#xff0c;要么全部执行&#xff0c;要么全部不执行。Java中&#xff0c;对基本数据类型的变量的读取和赋值操作是原子性操作&#xff0c;但不采取任何原子性保障措施的自增操作不是原子性的&#xff0c;如&#xff1a;i public c…...

pytorch代码复现1(基础知识)

创建矩阵 全零矩阵 In [4]: import torch torch.__version__ xtorch.empty(5,3) xOut[4]: tensor([[0.0000e00, 0.0000e00, 4.6430e-23],[1.4013e-45, 1.2612e-44, 0.0000e00],[3.5733e-43, 0.0000e00, 0.0000e00],[0.0000e00, 0.0000e00, 0.0000e00],[0.0000e00, 0.0000e00, 0…...

PostGreSQL模式schema

问题引入 之前在做数据库设计时&#xff0c;经常会忽略schema模式&#xff0c;直接在数据库下的public模式下建立各类数据表。如果数据表命名不够规范&#xff0c;后期寻找某张表时就会比较麻烦。通过 所幸&#xff0c;PostgreSQL 的模式schema管理&#xff0c;可以对这个问题…...

大厂面试题-什么是JVM

JVM全称是Java虚拟机&#xff0c;在聊什么是JVM之前&#xff0c;我们不妨看⼀下这张图。 从这张图中可以看出JVM所处的位置&#xff0c;同时也能看出它两个作用&#xff1a; 1、运⾏并管理Java源码⽂件所⽣成的Class⽂件&#xff0c; 2、在不同的操作系统上安装不同的JVM&#…...

rest参数

Rest参数是ES6中新增的一个语法特性&#xff0c;也称为剩余参数。其语法形式为三个点&#xff08;...&#xff09;加上一个名称&#xff0c;用于表示函数的参数个数不确定&#xff0c;可以将多余的参数收集到一个数组中。Rest参数只能作为最后一个参数出现&#xff0c;且一个函…...

Hadoop3.0大数据处理学习3(MapReduce原理分析、日志归集、序列化机制、Yarn资源调度器)

MapReduce原理分析 什么是MapReduce 前言&#xff1a;如果想知道一堆牌中有多少张红桃&#xff0c;直接的方式是一张张的检查&#xff0c;并数出有多少张红桃。 而MapReduce的方法是&#xff0c;给所有的节点分配这堆牌&#xff0c;让每个节点计算自己手中有几张是红桃&#…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

Linux-进程间的通信

1、IPC&#xff1a; Inter Process Communication&#xff08;进程间通信&#xff09;&#xff1a; 由于每个进程在操作系统中有独立的地址空间&#xff0c;它们不能像线程那样直接访问彼此的内存&#xff0c;所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...