让天下没有难学的技术
Bug:LinkedTransferQueue的数据暂失和CPU爆满以及修复
Bug:LinkedTransferQueue的数据暂失和CPU爆满以及修复
一个因中断或者超时的调用可能会引起数据丢失和CPU爆满。
前几天读LinkedTransferQueue（以下简称ltq)的源码，想加深下对松弛型双重队列的理解，无意中发现了这个问题:），经过仔细检查后确认了这是个bug，存在于JDK1.7.0_40和刚发布的JDK8中，去google和oracle官方似乎也没有搜索到这个问题。
重现bug：先来重现下这个bug，由于对并发线程的执行顺序预先不能做任何假设，所以很可能根本就不存在所谓的重现错误的“测试用例”，或者说这个测试用例应该是某种“执行顺序”。所以我一开始的做法是copy了一份ltq的源码，通过某个地方加自旋…但是这种方法毕竟要修改源码，后来我发现直接debug进源码就可以轻易重现bug了。
LinkedTransferQueue:xfer(E e, boolean haveData, int how, long nanos)
if (how != NOW) { // No matches available
if (s == null)
s = new Node(e, haveData);
Node pred = tryAppend(s, haveData);
if (pred == null)
// lost race vs opposite mode
if (how != ASYNC)
return awaitMatch(s, pred, e, (how == TIMED), nanos);
// not waiting
在以上06行Node pred = tryAppend(s, havaData)
断点（我是windows下用eclipse调试）；
debug以下代码：
public static void main(String[] args) {
final BlockingQueue&Long& queue = new LinkedTransferQueue&Long&();
Runnable offerTask = new Runnable(){
public void run(){
queue.offer(8L);
System.out.println(&offerTask thread has gone!&);
Runnable takeTask = new Runnable(){
public void run(){
System.out.println(Thread.currentThread().getId() + & & +queue.take());
} catch (InterruptedException e) {
e.printStackTrace();
Runnable takeTaskInterrupted = new Runnable(){
public void run(){
Thread.currentThread().interrupt();
System.out.println(Thread.currentThread().getId() + & & +queue.take());
} catch (InterruptedException e) {
System.out.println(e + & &+Thread.currentThread().getId());
new Thread(offerTask).start();
new Thread(takeTask).start();
new Thread(takeTaskInterrupted).start();
执行到断点处之后，在Debug界面里面有Thread-0、Thread-1、Thread-2三个线程分别指代代码中的offerTask、takeTask、takeTaskInterrupted三者。现在执行三步：
step 1: Resume Thread-1（没有输出，线程Thread-1自己挂起，等待数据）
step 2: Resume Thread-2（看到类似于 java.lang.InterruptedException 15 的输出）
step 3: Resume Thread-0（输出：offerTask thread has gone!）
offer线程已经执行完毕，然后我们的64L呢，明明Thread-1在等待数据，数据丢失了吗？其实不是，只不过take线程现在无法取得offer线程提交的数据了。
如果你觉得上面的数据丢失还不是什么大问题请在上面的示例下添加如下代码（和你CPU核心数相同的代码行:）
..............
new Thread(takeTask).start();
new Thread(takeTask).start();
new Thread(takeTask).start();
new Thread(takeTask).start();
把上面的3个step重新按顺序执行一遍，建议先打开任务管理器，接着忽略断点，让接下来这几个线程跑:）
CPU爆满了吧…其实是被这几个线程占据了，你去掉几行代码，CPU使用率会有相应的调整。
所以这个bug可能会引起数据暂时遗失和CPU爆满， 只不过貌似发生这种情况的概率极低。
原因：为什么会出现这个bug呢，要想了解原因必须先深入分析ltq内部所使用的数据结构和并发策略，ltq内部采用的是一种非常不同的队列，即松弛型双重队列（Dual Queues with Slack）。
数据结构：
松弛的意思是说，它的head和tail节点相较于其他并发列队要求上更放松，构造它的目的是减少CAS操作的次数（相应的会增加next域的引用次数），举个例子：某个瞬间tail指向的节点后面已经有6个节点了（以下图借用源码的注释），而其他并发队列真正的尾节点最多只能是tail的下一个节点。
* M -& M -& U -& U -& U -& U-&U-&U-&U-&U
收缩的方式是大部分情况下不会用tail的next来设置tail节点，而是第一次收缩N个next(N&=2)，然后查看能否2个一次来收缩tail。（head类似，并且head改变一次会导致前“head”节点的next域断裂即如下图）
*”prehead”
M-& U -& U -& U -& U-&U-&U-&U-&U
双重是指有两种类型相互对立的节点(Node.isData==false || true)，并且我理解的每种节点都有三种状态：
INIT(节点构造完成，刚进入队列的状态)
2 MATCHED(节点备置为“满足”状态，即入队节点标识的线程成功取得或者传递了数据)
3 CANCELED(节点被置为取消状态，即入队节点标识的线程因为超时或者中断决定放弃等待）
（bug的原因就是现有代码中将2、3都当做MATCHED处理，后面会看到把3独立出来就修复了这个问题）
并发策略：
既然使用了松弛的双重队列，那么当take、offer等方法被调用时执行的策略也稍微不同。
就我们示例中的代码的流程来看，Thread-0、Thread-1、Thread-2几乎同时进入到了xfer的调用，发现队列为空，所以都构造了自己的node希望入队，于是三者都从tail开始加入自己的node，我们在这里的顺序是Thread-1-&Thread-2-&Thread-0，因为想要入队还要和当前的tail节点进行匹配得到“认可”才能尝试入队，队列为空Thread-1理所当然入队成功并且挂起了自己的线程（park)等待相对的调用来唤醒自己（unpark)，然后Thread-2发现队列末尾的node和自己是同一类型的，于是通过了测试把自己也加入了队列，由于本身是中断的所以让自己进入MATCHED状态（bug就是这里了，上面说过CANCEL被当做MATCHED状态处理），接着我们提交数据的Thread-0来了，发现末尾节点的类型虽然对立但却是MATCHED状态（假如不为MATCHED会有退回再从head来探测一次的机会），所以认为队列已经为空，前面的调用已经被匹配完了，然后把自己的node入队，这样就形成了如下所示的场景：
REQUEST -&
好了， 现在Thread-3来了，先探测尾部发现Thread-0的node是类型相反的，于是退回从头部开始重新探测，但是又发现Thread-1的node的类型是相同的，于是再次去探测尾部看看能否入队…….结果造成CPU是停不下来的。
如上面所说，错误的本质在于当尾部的节点是CANCELED（取消）状态时不能作为被匹配完成的MATCHED状态处理，应该让后来者回退到head去重新测试一次所以重点是对源码做出如下修改（修改放在注释中）：
static final class Node {
final boolean isD // false if this is a request node
volatile O // initially non-null if isD CASed to match
volatile N
volatile T // null until waiting
static final Object CANCEL = new Object();
final void forgetWaiter(){
UNSAFE.putObject(this, waiterOffset, null);
final boolean isCanceled(){
return item == CANCEL;
在Node节点代码中加入标识取消的对象CANCEL。
private E xfer(E e, boolean haveData, int how, long nanos) {
if (item != p && (item != null) == isData
/*&& item!=Node.CANCEL*/) { // unmatched
if (isData == haveData) // can't match
在xfer函数中添加对于为状态为取消的判断。
private E xfer(E e, boolean haveData, int how, long nanos) {
Node pred = tryAppend(/*s,*/ haveData);
private Node tryAppend(Node s, boolean haveData) {
else if (p.cannotPrecede(/*s, */haveData))
/* if(p.isCanceled())
p.forgetContents();*/
if (p != t) { // update if slack now &= 2
添加对于前置节点为取消状态时当前节点的入队策略
final boolean cannotPrecede(boolean haveData) {
boolean d = isD
return d != haveData && (x = item) != this && (x != null) ==
final boolean cannotPrecede(Node node, boolean haveData) {
boolean d = isD
if(d != haveData){
Object x =
if(x != this && (x!=null) == d && x!= Node.CANCEL)
if(item == CANCEL){
if(node.next != this){
node.next =
this.forgetContents();
node.next =
这一步是关键， 当我们入队时发现前置节点是类型对立并且取消状态时，我们就需要多一次的回退探测，所以借用了一下next域来标识这个CANCEL节点，下次经过时或者可以确认它可以当做MATCHED处理（它前面没有INIT节点）或者已经有别的节点粘接在它后面，我们就进而处理那个节点，总之当我们总是能够得到正确的行为。
private E awaitMatch(Node s, Node pred, E e, boolean timed, long nanos) {
if ((w.isInterrupted() || (timed && nanos &= 0)) &&
s.casItem(e, /*Node.CANCEL*/)) { // cancel
unsplice(pred, s);
这一处关键点把item的值从原来的s本身修改为我们新增的CANCEL。
代码好乱，关于这个bug定位应该没问题，后面的原因很多方面都没讲，剩下的还有很多处大大小小的修改=_=，整个修改之后的LinkedTransferQueue，大家有兴趣的话可以参考下，已经通过了
原创文章，转载请注明： 转载自
本文链接地址:
关注JAVA并发.
Latest posts by JaonHui ()
- 2014 年 7 月 10 日
- 2014 年 4 月 15 日
Related posts:
(3 votes, average: 5.00 out of 5)
Loading...经验1718 米
在线时间177 小时
积分 2284, 距离下一级还需 2716 积分
积分 2284, 距离下一级还需 2716 积分
机型红米Note WCDMA版
签到次数19
MIUI版本5.6.4
通过手机发布
经验1720 米
在线时间135 小时
积分 2351, 距离下一级还需 2649 积分
积分 2351, 距离下一级还需 2649 积分
机型红米Note WCDMA版
签到次数29
MIUI版本5.6.2
又若干，又2.4M...
经验4216 米
在线时间225 小时
积分 5514, 距离下一级还需 14486 积分
积分 5514, 距离下一级还需 14486 积分
机型小米手机3/4 WCDMA版
签到次数28
MIUI版本5.6.8
就是修复了很多个bug。具体修复了什么bug需要自己去摸索、
经验8953 米
在线时间414 小时
积分 11789, 距离下一级还需 8211 积分
积分 11789, 距离下一级还需 8211 积分
机型红米Note WCDMA版
签到次数18
MIUI版本5.6.8
意思就是说，现在的包已经没有BUG了，因为它们把有问题的东西都删除了
经验1575 米
在线时间59 小时
积分 2021, 距离下一级还需 2979 积分
积分 2021, 距离下一级还需 2979 积分
机型红米Note TD版
签到次数17
MIUI版本5.6.4
就是删除了很多出现过bug的功能
经验1225 米
在线时间53 小时
版本5.2.13
积分 1494, 距离下一级还需 506 积分
积分 1494, 距离下一级还需 506 积分
机型红米Note TD版
签到次数19
MIUI版本5.2.13
没进内测的路过~~
经验2616 米
在线时间277 小时
积分 3667, 距离下一级还需 1333 积分
积分 3667, 距离下一级还需 1333 积分
机型红米手机 TD版
签到次数18
MIUI版本5.6.8
通过手机发布
就是没修复
经验1718 米
在线时间177 小时
积分 2284, 距离下一级还需 2716 积分
积分 2284, 距离下一级还需 2716 积分
机型红米Note WCDMA版
签到次数19
MIUI版本5.6.4
通过手机发布
原谅工程师吧，要早点放工随便应酬3G就好
经验1399 米
在线时间73 小时
积分 1974, 距离下一级还需 26 积分
积分 1974, 距离下一级还需 26 积分
机型红米Note TD版
签到次数17
MIUI版本5.6.4
通过手机发布
经验949 米
在线时间13 小时
版本5.5.15
积分 1341, 距离下一级还需 659 积分
积分 1341, 距离下一级还需 659 积分
机型红米Note TD版
签到次数13
MIUI版本5.5.15
默默回帖，早日进内测，V6指日可待， MIUI 因你更精彩！
已关注极客秀微信
已关注微信
关注腾讯微博
已关注腾讯微博
关注新浪微博
已关注新浪微博
Copyright (C) 2015 MIUI 京ICP备号【征稿】公信力的bug怎么修复？
新华网思想传播与深阅读平台
　　公信力，是指使公众信任的力量。广义的公信力，不仅针对政治系统内部，同时面向政治系统外的各个机构，渗透到社会的各个领域。　　公信力是一种无形资产，但近日，福彩延时开奖、存款蒸发反被判刑等事件相继发生，使“公信力”一词再次被推上风口浪尖。事件不仅使福彩和银行本身成为了舆论关注的焦点，也折射出社会和政府公信力不断遭到蚕食的尴尬现状，公信力似成中国社会“一戳就痛”的伤疤。　　转型期的中国，公信力现状如何？有无标准评判公信力状况？政府公信力该如何构建？有哪些挑战？公众在质疑社会公信力和政府公信力时，是理性诉求，还是感性发泄？对政府、制度的批评质疑是否应该有合理的底线？提升政府、司法公信力的路径在哪？如何提升整体社会公信力？欢迎来稿与我们分享你的真知灼见。[征稿时间]　　日～日[征稿要求]　　1、投稿须是独家原创文章，字为宜。　　2、投稿邮件标题请以“征稿”开头，并加上稿件标题；正文注明撰稿人姓名、联系方式（如有可附上作者微信公众号）、供职单位（如在岗请标明）。　　3、投稿请发至思客编辑部邮箱，一经采用，我们将与您联系并寄奉稿酬。
推荐本文42
阅读(4449) 评论()
最新鲜，最热辣的时事评论。无惧冲突辛辣，只忧平庸逐流。当前访客身份：游客 [
当前位置：
WebStorm 9.0.3 发布，Bug 修复版本
WebStorm 9.0.3 (build 139.1112) 发布，现已提供。此版本对 IDE 的每个部分都进行了大量的 bug 修复和改进。详情请看。这是 WebStorm 9 的最后一次更新，WebStorm 10 EAP 版本很快就会发布了！Develop with pleasure!– JetBrains WebStorm Team
WebStorm 是 JetBrains 推出的一款商业的 JavaScript 开发工具。
WebStorm 的详细介绍：
WebStorm 的下载地址：
想通过手机客户端（支持 Android、iPhone 和 Windows Phone）访问开源中国：
旧一篇： 5个月前
新一篇： 5个月前
相关讨论话题
你也许会喜欢
IDE搭配编辑器再好不过了.Linux上用Geany,Windows用EverEdit.据说
30天试用到期后,只弹提示框,没做其他限制:默认安装位置: C:\Users\NAME\AppData\Local\EverEdit下载绿色版EverEdit: http://cn.everedit.net/download.htmlEverEdit右键打开菜单注册表EverEdit.reg:Windows Registry Editor Version 5.00[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit]@=&Open with EverEdit&&Icon&=&D:\\EverEdit\\EverEdit.exe&[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit\command]@=&\&D:\\EverEdit\\EverEdit.exe\& \&%1\&&
2楼：Ruchee
引用来自“eechen”的评论IDE搭配编辑器再好不过了.Linux上用Geany,Windows用EverEdit.据说
30天试用到期后,只弹提示框,没做其他限制:默认安装位置: C:\Users\NAME\AppData\Local\EverEdit下载绿色版EverEdit: http://cn.everedit.net/download.htmlEverEdit右键打开菜单注册表EverEdit.reg:Windows Registry Editor Version 5.00[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit]@=&Open with EverEdit&&Icon&=&D:\\EverEdit\\EverEdit.exe&[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit\command]@=&\&D:\\EverEdit\\EverEdit.exe\& \&%1\&&百科大婶，Linux上Vim都不提的吗
3楼：chenwenli
引用来自“eechen”的评论IDE搭配编辑器再好不过了.Linux上用Geany,Windows用EverEdit.据说
30天试用到期后,只弹提示框,没做其他限制:默认安装位置: C:\Users\NAME\AppData\Local\EverEdit下载绿色版EverEdit: http://cn.everedit.net/download.htmlEverEdit右键打开菜单注册表EverEdit.reg:Windows Registry Editor Version 5.00[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit]@=&Open with EverEdit&&Icon&=&D:\\EverEdit\\EverEdit.exe&[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit\command]@=&\&D:\\EverEdit\\EverEdit.exe\& \&%1\&&我想让ee在crossover上跑，可惜没装成功~
4楼：紫电清霜
引用来自“eechen”的评论IDE搭配编辑器再好不过了.Linux上用Geany,Windows用EverEdit.据说
30天试用到期后,只弹提示框,没做其他限制:默认安装位置: C:\Users\NAME\AppData\Local\EverEdit下载绿色版EverEdit: http://cn.everedit.net/download.htmlEverEdit右键打开菜单注册表EverEdit.reg:Windows Registry Editor Version 5.00[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit]@=&Open with EverEdit&&Icon&=&D:\\EverEdit\\EverEdit.exe&[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit\command]@=&\&D:\\EverEdit\\EverEdit.exe\& \&%1\&&刚刚看了官网介绍了，EverEdit30天后就无法使用，必须购买啊。
5楼：eechen
引用来自“eechen”的评论IDE搭配编辑器再好不过了.Linux上用Geany,Windows用EverEdit.据说
30天试用到期后,只弹提示框,没做其他限制:默认安装位置: C:\Users\NAME\AppData\Local\EverEdit下载绿色版EverEdit: http://cn.everedit.net/download.htmlEverEdit右键打开菜单注册表EverEdit.reg:Windows Registry Editor Version 5.00[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit]@=&Open with EverEdit&&Icon&=&D:\\EverEdit\\EverEdit.exe&[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit\command]@=&\&D:\\EverEdit\\EverEdit.exe\& \&%1\&&引用来自“紫电清霜”的评论刚刚看了官网介绍了，EverEdit30天后就无法使用，必须购买啊。你把系统时间调到一个月后,然后重新打开EverEdit,它会弹出&关于EverEdit&对话框,上面提供有&购买链接&,点击&确定&后是可以正常使用的,并没有做什么限制,SublimeText2也是会提示用户购买的,不是很多人一样用.
6楼：iehyou
引用来自“eechen”的评论IDE搭配编辑器再好不过了.Linux上用Geany,Windows用EverEdit.据说
30天试用到期后,只弹提示框,没做其他限制:默认安装位置: C:\Users\NAME\AppData\Local\EverEdit下载绿色版EverEdit: http://cn.everedit.net/download.htmlEverEdit右键打开菜单注册表EverEdit.reg:Windows Registry Editor Version 5.00[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit]@=&Open with EverEdit&&Icon&=&D:\\EverEdit\\EverEdit.exe&[HKEY_CLASSES_ROOT\*\shell\OpenWithEverEdit\command]@=&\&D:\\EverEdit\\EverEdit.exe\& \&%1\&&引用来自“紫电清霜”的评论刚刚看了官网介绍了，EverEdit30天后就无法使用，必须购买啊。引用来自“eechen”的评论你把系统时间调到一个月后,然后重新打开EverEdit,它会弹出&关于EverEdit&对话框,上面提供有&购买链接&,点击&确定&后是可以正常使用的,并没有做什么限制,SublimeText2也是会提示用户购买的,不是很多人一样用.......修改系统时间
那还有什么意思
7楼：eechen
你没看明白.我的意思是说,如果你想看看过期后是什么效果,你就把时间调到30天后.事实证明除了启动时弹出购买提示,并不影响使用.
8楼：紫电清霜
引用来自“eechen”的评论
你没看明白.我的意思是说,如果你想看看过期后是什么效果,你就把时间调到30天后.事实证明除了启动时弹出购买提示,并不影响使用.额，明白了，多谢指导，这个软件写的确实不错，比sublime美观易用
9楼：Klaus88 来自
10楼：iehyou
引用来自“eechen”的评论
你没看明白.我的意思是说,如果你想看看过期后是什么效果,你就把时间调到30天后.事实证明除了启动时弹出购买提示,并不影响使用.引用来自“紫电清霜”的评论额，明白了，多谢指导，这个软件写的确实不错，比sublime美观易用对于大部分有强迫症的程序员来说，弹窗很纠结
11楼：紫电清霜
引用来自“eechen”的评论
你没看明白.我的意思是说,如果你想看看过期后是什么效果,你就把时间调到30天后.事实证明除了启动时弹出购买提示,并不影响使用.引用来自“紫电清霜”的评论额，明白了，多谢指导，这个软件写的确实不错，比sublime美观易用引用来自“iehyou”的评论对于大部分有强迫症的程序员来说，弹窗很纠结可以接受，人家也要养家糊口啊
12楼：郑柯 来自
引用来自“eechen”的评论
你没看明白.我的意思是说,如果你想看看过期后是什么效果,你就把时间调到30天后.事实证明除了启动时弹出购买提示,并不影响使用.引用来自“紫电清霜”的评论额，明白了，多谢指导，这个软件写的确实不错，比sublime美观易用你搞错了了吧，美观上能和sublime比？就这界面和字体？我装N回都因为界面和字体不行卸载了
与内容无关的评论将被删除，严重者禁用帐号
本周热点资讯
本站最新资讯