【自省】你可思考过 AQS 中的同步队列为何这样设计?

简介: 【自省】你可思考过 AQS 中的同步队列为何这样设计?

一、前情概要

多线程大师 Doug Lea 被称为 世界上对Java影响力最大的个人,这个鼻梁挂着眼镜,留着德王威廉二世的胡子,脸上永远挂着谦逊腼腆笑容,服务于纽约州立大学Oswego分校计算机科学系的老大爷。

本篇是学习 Doug Lea大师的论文《The java.util.concurrent Synchronizer Framework》 JUC 同步器框架(AQS 框架)原文翻译 ,并结合对 AQS 的源码的梳理后的形成的一些思考总结,记录下来。在对 AQS 的 ReentrantLock 的源码阅读分析后,也整理出了核心流程脑图 ,感兴趣的 》》》【点击查看脑图】

本篇是自省的方式来梳理论文原文,非学术那么严谨,目的是为了更方便理解其设计与实现,如对 AQS 不太了解,也可以直接阅读本篇,但需要耐心。若是对 AQS 比较熟悉,那更欢迎阅读本篇,很期待读者老师的交流指正。

二、概念认知对齐

2.1 互斥

互斥,是让线程交替执行一段代码,而不能同时执行;换一个说法就是线程抢到锁后就执行同步代码,抢不到锁(同步状态)就不能执行同步代码,只能等待;而等待可以表现出 3 种方式:

  • 争取不到锁,线程休眠等待
  • 争取不到锁,线程自旋等待
  • 争取不到锁,线程先自旋等待一会儿,不行再休眠等待(AQS 的做法)

2.2 AQS 中锁的关键特征描述

1)锁状态

在 AQS 中锁状态,使用 int 类型的状态变量来记录,通过 CAS 操作来修改其值;

  • 0表示无锁
  • 1表示加锁
  • >1 表示重入,重入时执行++操作,记录重入次数
  • 释放锁时执行--操作,直到减到0才表示锁被完全释放,可被其他线程抢占

2)休眠与唤醒

休眠和唤醒使用unsafe中的park(休眠线程)和unpark(唤醒线程)方法。

3)自旋

自旋使用for循环,循环次数是有限的。

4)等待

等待使用双向队列的结构来实现排队等待的效果,不能插队的模式是公平模式,可插队模式是非公平模式。

三、单向队列的需求及设计的思考

从原文这一段开始:

在原始版本的 CLH 锁中,节点间甚至都没有互相链接。自旋锁中,pred 变量可以是一个局部变量。然而,Scott 和 Scherer 证明了通过在节点中显式地维护前驱节点,CLH 锁就可以处理“超时”和各种形式的“取消”:如果一个节点的前驱节点取消了,这个节点就可以滑动去使用前面一个节点的状态字段。

理解原文:【单向队列】可以比较容易的处理超时和取消请求,在队列的组织结构下,前一个请求节点因为取消或者超时而变得报废无效后,后边的请求有往前推进需求和能力,可以把无效的请求节点移除队列,以便让处于存活有效状态的向前移动。

  • 问题:为什么选择 tail 向 head 方向(pre 链路)?
从tail到head,即pre方向更自然,队末的更有需求让队伍往前走,因为自己的事还没办;队首的自己的事已经办完了,后边排队的跟自己关系不大。
复制代码
  • 想象一下现实开车时的超车状态:你要往前走,前车若因异常(类比线程超时、取消状态)不能前进,你在后边能感知到,因为有继续前行的需求,你会绕开继续前行。但若是你的后车有问题,你应该是不管的吧。
  • 问题: 自旋修改为自旋+阻塞
  1. 原文说:

第二个对 CLH 队列主要的修改是将每个节点都有的状态字段用于控制阻塞而非自旋”,... “取消”状态必须存在于状态字段中"。

  • 这句话的关键之处在于【把面向自旋的设计修改为了面向阻塞】,自旋的设计要理解的关键点在于:每一个节点的“释放”状态,是保存在其前驱节点中;因此,自旋锁的“自旋”操作就如下:
while (pred.status != RELEASED); //自旋后的出队操作只需将head字段指向刚刚得到锁的节点:
head = node;
复制代码
  • 但是全部是自旋挺浪费 CPU ,于是考虑修改成阻塞试试:
while (pred.status  != RELEASED){
  阻塞休眠
}
复制代码
  • 但让所有线程节点一上来看到状态不满足,就阻塞也不合适;比如第一个排队的,跟其他后续排队的情况不同,对于第一个排队的,其前边的可能已经或者很快就结束,这种情况下最好先自旋几次尝试去抢锁,如果没抢成功再阻塞,而其他后续排队的节点一看前边有排队的了,自己则可以直接排队阻塞。
    原文中”检查当前节点的前驱是否为head来确定权限"也是这个意思,即不用判断前驱节点的release状态,只需要判断是不是head,是head就尝试竞争锁,不是head就阻塞(park)排队,等着被唤醒。

四、变成双向队列的需求及设计的思考

  • 问题:为什么要变成双向队列?
    线程拿不到锁会排队等待,当前边线程释放锁之后,后续就需要【被唤醒】继续工作。【那如何唤醒后继的节点】,前边提到 队列被设计为tail -> head方向的链路,如果从tail顺着prehead方向一直盯着,总能感知到是否轮到自己了,但这样性能不高,可以优化一下,若释放锁的节点能直接找到自己的后继节点,通知它拿锁干活儿就会更方便。所以增加 next 方向,队列就变成了双向。
    但是双向的链路控制并非原子性的,总得有取舍,AQS 采取保证pre方向及时有效,next方向略有延迟,所以,在next方向找不到的情况下,会尝试从tail沿着pre方向往前找一下。
  • 问题: 后继节点如何阻塞,如何唤醒?
    当前节点release后,后继节点可能正在自旋竞争锁,这种情况下没有必要去唤醒它(虽然unpark唤醒操作也不会出错,但也是有成本的);出于成本考虑再优化一下,在休眠之前,最好给前驱节点个“唤醒(signal me)”自己的信号。
    所以线程调用park前,给前驱节点设置一个“唤醒(signal me)”标志,并再尝试一次去拿锁,如果竞争到了锁,就避免了一次不必要的阻塞;如果竞争不到锁,才去真的休眠。
  • 问题:队列为何是延迟初始化?
    只有一个线程的时候,或者多个线程之间是交替执行,且线程的执行在时序无重叠,这种情况下,线程都不需要排队,只需要判断同步状态,修改同步状态;因此队列是在首次需要的时候才进行初始化(构建一个虚拟节点,headtail都指向它)。
  • 问题:公平与非公平是排队策略不同?
  • 非公平:插队模式,往队首插队,插不进去,才追加到队尾。
  • 公平:不可插队模式,到队尾排队。

五、最后说一句

我是石页兄,如果这篇文章对您有帮助,或者有所启发的话,欢迎关注笔者的微信公众号【 架构染色 】进行交流和学习。您的支持是我坚持写作最大的动力。


相关文章
|
2月前
|
存储 安全 API
源码解密协程队列和线程队列的实现原理(二)
源码解密协程队列和线程队列的实现原理(二)
35 1
|
2月前
|
存储 运维 API
源码解密协程队列和线程队列的实现原理(一)
源码解密协程队列和线程队列的实现原理(一)
35 1
|
2月前
多线程通信和同步的方式有哪些?
【10月更文挑战第6天】
104 0
|
7月前
|
Java C++
Java实现信号量机制(生产者消费者问题)的三种方式
Java实现信号量机制(生产者消费者问题)的三种方式
106 0
|
安全 Java 容器
多线程案例(2)-阻塞式队列
多线程案例(2)-阻塞式队列
69 0
|
存储
什么是队列,如何实现?
什么是队列,如何实现?
113 0
什么是队列,如何实现?
并发编程-18AQS同步组件之 CyclicBarrier 同步屏障
并发编程-18AQS同步组件之 CyclicBarrier 同步屏障
72 0
并发编程-17AQS同步组件之 Semaphore 控制并发线程数的信号量
并发编程-17AQS同步组件之 Semaphore 控制并发线程数的信号量
71 0
|
Java 程序员 API
AQS抽象队列同步器
AQS抽象队列同步器
AQS抽象队列同步器
|
存储 缓存 Java
JUC并发编程学习(十)-阻塞队列、同步队列
JUC并发编程学习(十)-阻塞队列、同步队列
JUC并发编程学习(十)-阻塞队列、同步队列