No-Blocking算法(简称NB)作为科研的主题已经有20年了,但直到1.5才被大量线上应用;
我们第一次见到CAS估计都是从那个++引入的:用AtomicInteger和带synchronized关键字的++比看谁加到1000用的时间更少,于是凭借这个小小的volatile int变量我们也就达到了把锁的粒度降到最低、进而达到高并发的目的,然而如果没有CLH队列的保证n个线程疯抢一把对象锁也是很悲剧的。
进队出队也需要CAS操作,但是没那么简单了.......昨天在看AbstractQueuedSynchronizer源码时发现了一个问题,特此拿出来讨论讨论:
private Node addWaiter(Node mode) {
Node node = new Node(Thread.currentThread(), mode);//构造代表入队线程的节点
Node pred = tail;//读取CLH队列最后一个节点(尾指针)
if (pred != null) {
node.prev = pred;//CLH是双向链表,但此步不足以入队
//如果从行3到这里尾指针没被其他线程碰过就把尾指针指向入队的那个节点
if (compareAndSetTail(pred, node)) {
pred.next = node;//此步足以入队
return node;
}
}
enq(node);//如果能执行到这里我就有话要说了,且听下文分解
return node;
}
如果哪个线程抢锁失败就不得不执行addWaiter方法了:排队吧~。
private Node enq(final Node node) {
for (;;) {
Node t = tail;//再次读取最后一个节点
if (t == null) { //当且仅当CLH是空的时候t才会为null
Node h = new Node(); //传说中的头结点(其实是个傀儡节点)
h.next = node;
node.prev = h;//入队的节点排在头结点之后
if (compareAndSetHead(h)) {
tail = node;
return h;
}
}
else {
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}
当执行到13行的时候就是亮点了!为什么会执行到这里?因为CLH不为空,再进一步,上一段代码第7行CAS失败了,为什么失败了?因为有个手脚更快的线程抢先一步入队了,尾指针被改变了,这时候就必须把那个手脚快的节点作为尾节点来参照了,剩下的代码就跟上一段的功能一模一样了。
先撇开Doug Lea的做法不说,要是让你设计插入到队尾怎么设计?当然是经典入队的方法:先把最后一个节点跟新的节点互插:
lastNode.next=newNode;
newNode.pre=lastNode;
然后再让尾指针指向新来的节点;
但是我们看看Doug Lea是怎么搞的,他先在第一段代码的第7行判定能不能把尾指针指向新节点,第8行再把新节点和老节点互插,这看起来是不是有点别扭啊?
根据我这几年的经验,别扭的流程一般都不会获得最速度的执行,我左思右想终于发现Doug Lea设计的缺陷了:一旦addWaiter方法第七行CAS失败那这个方法也就废了,所有任务都将抛给enq方法去执行,这段流程也就没有意义了,而且enq方法的设计是CAS使用的大忌:在while(true)这样的死循环里进行CAS比较,完全违背了建立CLH队列的初衷——防止线程的恶性竞争。
对此我提出了一个淫蛋一点的方法:在最开始的时候,先作如下判断:
if(tail.next==null){...
可能这时候有人会喷我了,这个用判断吗?别急,如果此判断为true,那我就放心大胆的按常规思路先走第一步,新老节点互插,完成入队,接着尾指针指向新节点;如果为false,这就说明此队列处于
不一致状态,那我就先把他置为一致状态再说,下面呈上代码:
public Node addWaiter(Node newNode) {
while (true) {
if (tail.next == null) {//看起来很“废”的判断
if (tail.next.CAS(null, newNode)) {//完成入队
CAStail(tail, newNode);//刷新尾指针
return newNode;
}
}else{
CAStail(tail,tail.next);//让队列回到一致状态
}
}
}
如果看了上述代码仍不能理解
不一致状态,那我就贴上图了
可能有人要问了,你这里不也是把CAS放到while(true)里面吗?没错,我是这么做了,但是我的这个粒度要比Doug Lea的小得多,他的addWaiter第七行在高并发情况下很容易失败,一旦失败就要全部重来(经典入队的两大步),而我的至少能保证第一步很容易完成,第二步无需完成(刷新尾指针的任务其他线程可以智能地帮我完成)。
jdk1.7已经发布了,我的发现注定赶不上这班车了,但我希望1.8能考虑一下这个小小的发现......
分享到:
相关推荐
Java并发之AQS详解.pdf
Java 并发编程中的 JUC(java.util.concurrent)库以及其核心组件 AQS(AbstractQueuedSynchronizer)在构建高性能、可伸缩性的多线程应用方面具有重要的地位。 AQS 是 JUC 中的核心组件,它提供了一个框架,让...
java并发包详解,condition重入锁;Semaphore信号量;ReadWriteLock读写锁;CountDownLatch计时器;CyclicBarrier循环栅栏; 重⼊锁可以完全替代synchronized关键字。在JDK5.0的早期版本中,重⼊锁的性能远远好于 ...
AQS抽象队列同步器,AQS抽象队列同步器
AQS是J.U.C包下AbstractQueuedSynchronizer抽象的队列式的同步器的简称,这是一个抽象类,它定义了一套多线程访问共享资源的同步器框架,J.U.C包下的许多同步类实现都依赖于它,比如ReentrantLock/Semaphore/...
Java并发编程解析 | 解析AQS基础同步器的设计与实现
第1节你真的了解并发吗? [免费观看][免费观看] 00:27:48分钟 | 第2节理解多线程与并发的之间的联系与区别 [免费观看] 00:11:59分钟 | 第3节解析多线程与多进程的联系以及上下文切换所导致资源浪费问题 [免费观看]...
使用Condition重写waitnotify案例并实现一个有界队列.mp4 深入解析Condition源码.mp4 实战:简易数据连接池.mp4 线程之间通信之join应用与实现原理剖析.mp4 ThreadLocal 使用及实现原理.mp4 并发工具类...
课程内容包括了JAVA手写线程池,UC线程池API详解,线程安全根因详解,锁与原子类,分布式锁原理与实现方式,并发编程-AQS等等针对性非常强的JAVA编程开发教程,这其中的内容对JAVA开发技能的拔尖,非常的有帮助。...
资源概要:1,多线程;2,synchronized;3,volatile;4,多线程在JVM中的实现原理剖析 导语: 什么是多线程? 多线程(multithreading...并发工具类、并发容器、阻塞队列 线程池原理剖析 线程池案例-Web容器-压力测试
JAVA并发编程与高并发解决方案-并发编程四之J.U.C之AQS.docx
龙果 java并发编程原理实战 第2节理解多线程与并发的之间的联系与区别 [免费观看] 00:11:59分钟 | 第3节解析多线程与多进程的联系以及上下文切换所导致资源浪费问题 [免费观看] 00:13:03分钟 | 第4节学习并发的四...
第13章高并发之消息队列思路 第14章高并发之应用拆分思路 第15章高并发之应用限流思路 第16章高并发之服务降级与服务熔断思路8 第17章高并发之数据库切库分库分表思路 第18章高并发之高可用手段介绍 第19章课程总结
AQS抽象队列同步器2
课程内容包括了JAVA手写线程池,UC线程池API详解,线程安全根因详解,锁与原子类,分布式锁原理与实现方式,并发编程-AQS等等针对性非常强的JAVA编程开发教程,这其中的内容对JAVA开发技能的拔尖,非常的有帮助。...
在线程获取锁时会调用AQS的acquire()方法,该方法第一次尝试获取锁如果失败,会将该线程加入到CLH队列中:public final void acqui
Java-AQS同步器 源码解读-条件队列Condition前文为什么需要条件队列Conditon Queue举个小例子分析怎么使用条件队列写个小DemoJDK中是怎么使用的Lock和ConditionLockConditionSync-Queue和Conditian-QueueAQS ...