ITKeyword,专注技术干货聚合推荐

注册 | 登录

不正确使用HashMap,造成CPU 100%的问题

yangjun2 分享于 2011-06-13

2019阿里云全部产品优惠券(新购或升级都可以使用,强烈推荐)
领取地址https://promotion.aliyun.com/ntms/yunparter/invite.html

今天也碰到这个问题,需要纠正,很多人说是死锁,应该是死循环,而不是死锁,HashMap是线程不安全的,所以不会出现死锁。

参考http://hongjiang.wordpress.com/2010/08/26/不正当使用hashmap导致cpu-100的问题追究/

同事madding同学在blog里写了篇关于HashMap死锁模拟的文章:http://blog.csdn.net/madding/archive/2010/08/25/5838477.aspx

(做个纠正,那个不是死锁问题,而是死循环。)

这个问题,我们以前在技术部邮件组讨论过。

校长之前的blog:http://sdh5724.javaeye.com/blog/619130

和淘宝的毕玄的《分布式Java应用:基础与实践》一书中都提到过 velocity导致cpu 100%的bug,起因是HashMap的使用不当所致。

在之前的邮件列表里,校长提出过这个问题,当时我没仔细看,不清楚这个问题究竟是对HashMap的误用,还是HashMap的潜在问题,

当时感觉不太可能是HashMap自身的问题,否则问题大了。应该是属于在并发的场景下错误的使用了HashMap。

昨天看了madding的blog后,觉得这个事情还是应该搞清楚一下;虽然我推测是链表形成闭环,但没有去证明过。

从网上找了一下:

http://blog.csdn.net/autoinspired/archive/2008/07/16/2662290.aspx??里面也有提到:

产生这个死循环的根源在于对一个未保护的共享变量 — 一个"HashMap"数据结构的操作。当在所有操作的方法上加了"synchronized"后,一切恢复了正常。检查"HashMap"(Java SE 5.0)的源码,我们发现有潜在的破坏其内部结构最终造成死循环的可能。在下面的代码中,如果我们使得HashMap中的entries进入循环,那 么"e.next()"永远都不会为null。

不仅get()方法会这样,put()以及其他对外暴露的方法都会有这个风险,这算jvm的bug吗?应该说不是的,这个现象很早以前就报告出来了(详细见:http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6423457)。Sun的工程师并不认为这是bug,而是建议在这样的场景下应采用"ConcurrentHashMap",在构建可扩展的系统时应将这点纳入规范中。

这篇翻译提到了对 HashMap的误用,但它没有点破HashMap内部结构在什么样误用情况下怎么被破坏的;我想要一个有力的场景来弄清楚。

再从madding的blog来看,用了2个线程来put就模拟出来了,最后堆栈是在 transfer 方法上(该方法是数据扩容时将数据从旧容器转移到新容器)。

仔细分析了一下里面的代码,基本得出了原因,也证明了我之前的推测。

假设扩容时的一个场景如下(右边的容器是一个长度2倍于当前容器的数组)

单线程情况:

clip_image001

我们分析数据转移的过程,主要是链表的转移。

clip_image002

执行过一次后的状态:

clip_image003

最终的结果:

clip_image004

两个线程并发情况下,扩容时可能会创建出2个新数组容器。

clip_image005

顺利的话,最终转移完可能是这样的结果

clip_image006

出现死循环的可能场景,还要详细的分析一下代码,下面的代码中重点在 do/while 循环结构中(完成链表的转移)。

// 扩容操作,从一个数组转移到另一个数组

1?void?transfer(Entry[] newTable) {
2?????Entry[] src = table;
3?????int?newCapacity = newTable.length;
4?????for?(int?j = 0; j < src.length; j++) {
5?????????Entry e = src[j];
6?????????if?(e !=?null) {
7???????????src[j] =?null;
8???????????do?{
9?????????????Entry next = e.next;?//假设第一个线程执行到这里
10????????????int?i = indexFor(e.hash, newCapacity);
11????????????e.next = newTable[i];?
12????????????newTable[i] = e;
13????????????e = next;
14?????????}?while?(e !=?null);?// 可能导致死循环
15???????}
16????}
17 }

2个线程并发情况下, 当线程1 执行到上面第9行时,而线程2已经完成了一轮 do/while 操作,那么它的状态如下图:

(上面的数组时线程1的,已经完成了链表数据的转移;下面的是线程2的,它即将开始进行对链表数据的转移,此时它记录 E1和E2的首位已经被线程1翻转了)

clip_image007

后续的步骤如下:

1) 插入 E1节点,E1节点的next指向新容器索引位置上的值(null或entry)

clip_image008

2) 插入 E2节点,E2的next指向当前索引位置上的引用值E1

clip_image009

3)因为next不为null,链表继续移动,此时2节点之间形成了闭环。造成了死循环。

clip_image010

上面只是一种情况,造成单线程死循环,双核cpu的话占用率是50%,还有导致100%的情况,应该也都是链表的闭环所致。

最终,这并不是HashMap的问题,是使用场景的不当,在并发情况下选择非线程安全的容器是没有保障的。

今天也碰到这个问题,需要纠正,很多人说是死锁,应该是死循环,而不是死锁,HashMap是线程不安全的,所以不会出现死锁。 参考http://hongjiang.wordpress.com/2010/08/26/不正当使用hashmap导

相关阅读排行


用户评论

游客

相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。