典型可扩展的哈希表即一个可调整大小的桶数组(buckets), 每一个桶存放预期数量的元素，因此哈希表平均在常量时间内进行插入，删除，查询操作。哈希表调整大小的主要成本—–在于新旧桶(buckets)之间进行重新分配操作，该操作被分摊到所有表操作上，所以平均操作时间也是常量的。哈希表调整大小就是扩容，在实践中，哈希表仅需要增加数组大小即可。
Michael实现了一个可并发，不可扩展的哈希表(通过对哈希表中每个桶进行读写锁约束)。然而，为了保证元素数量增长时的性能，哈希表必须可扩展。
阅读全文
并发的优先队列是一个可线性化到顺序优先队列的数据结构，能够通过常用的优先队列语义提供insert和delete-min操作。
基于堆的优先队列
许多文献中提到的并发优先队列结构，其实是本书前面提到的可线性化堆结构。再一次的，这种结构的基本思想是在个别堆节点上使用细粒度锁，使线程在并行下也能够尽可能的访问数据结构的不同部分。设计这种并发堆的关键问题，在于传统自底向上的insert和自顶向下的delete-min操作有可能造成死锁。Biswas和Brown[17]提出基于锁的堆算法，通过专门的“清理”线程解决死锁。Rao和Kumar[116]建议通过一个将insert和delete-min操作都自顶向下处理的算法[17]来解决问题。Ayani[11]在他们算法基础上做了改善，即通过一种方式在堆两侧进行连续插入。Jones[68]提出一种基于类似斜堆的方案[116]。
阅读全文
一个被广泛研究的方向是在理想化模型，如并行随机存取机上分析并发数据结构和算法的渐进复杂度[35, 122, 135]。然而，很少有将这些数据结构放在一个真实的多处理器上进行建模的。这里有多种原因，大部分原因跟系统硬件架构与线程异步执行的相互作用有关。想想组合树(combining tree)的例子，虽然我们能通过计算（指令数）得到O(P/logP)的加速比，但这无法反映在实证研究中[52, 129]。真实世界的行为是被上述其他因素支配的，如竞争开销，缓存行为，同步操作(例如CAS)开销，请求到达率，退避延时，数据结构在内存中的布局等等。这些因素很难用一个精确的涵盖目前所有架构的模型来量化。 阅读全文
正如前面讨论的那样，非阻塞实现主要目的是为了消除由锁带来的相关问题，为了形式化研究这一概念，多种非阻塞演进条件已经在相关文献有所研究了，如wait-freedom演进条件，lock-freedom演进条件，和obstruction-freedom演进条件。满足wait-free演进条件的操作是指在执行自身包含的有限步骤之后，保证操作必须完成，而不用考虑其他操作发生的时序，满足lock-free演进条件的操作是指在执行自身包含的有限步骤之后，保证某些操作完成。满足obstruction-free演进条件的操作是指在不受其他操作干扰的情况下，执行它包含的有限步骤之后，保证其完成。
本文首发于InfoQ。
Java 8在Lambda表达式、接口默认方式、新的日期API等方面引入的新特性广受关注，同时在并发编程方面也做出了大量改进。以往的几个Java版本都对java.util.concurrent做了不同程度的增强，比如Java 7的Fork/Join框架，而Java 8则进一步在java.util.concurrent下增加了新的接口、类与方法。目前java.util.concurrent的官方文档已经更新，变更部分总结如下： 阅读全文
在很多数据结构中，内存竞争所带来的不良现象和前文所说的顺序瓶颈带来的影响都可以通过使用细粒度锁机制来减小。在细粒度锁机制中，我们用多个粒度较小的锁来保护数据结构中的不同部分。这样做的目的是允许并发操作在它们不访问数据结构的相同部分时并行执行。这种方法也可以用于避免独立内存位置访问的额外竞争。在一些数据结构中，这种现象经常发生；举个例子，在哈希表中，对那些被哈希到不同哈希桶中的值的操作自然访问的是数据结构中的一部分。 阅读全文
一个因中断或者超时的调用可能会引起数据丢失和CPU爆满。
前几天读LinkedTransferQueue（以下简称ltq)的源码，想加深下对松弛型双重队列的理解，无意中发现了这个问题:），经过仔细检查后确认了这是个bug，存在于JDK1.7.0_40和刚发布的JDK8中，去google和oracle官方似乎也没有搜索到这个问题。
重现bug：先来重现下这个bug，由于对并发线程的执行顺序预先不能做任何假设，所以很可能根本就不存在所谓的重现错误的“测试用例”，或者说这个测试用例应该是某种“执行顺序”。所以我一开始的做法是copy了一份ltq的源码，通过某个地方加自旋…但是这种方法毕竟要修改源码，后来我发现直接debug进源码就可以轻易重现bug了。 阅读全文
本文是JSR-133规范，即JavaTM内存模型与线程规范，由JSR-133专家组开发。本规范是JSR-176（定义了JavaTM平台 Tiger（5.0）发布版的主要特性）的一部分。本规范的标准内容将合并到JavaTM语言规范、JavaTM虚拟机规范以及java.lang包的类说明中。本JSR-133规范将不再通过JCP维护和修改。未来所有对这些标准化内容的更新、修正以及说明都会出现在上述这些文档中。
本规范的标准化内容包含在第5, 7, 9.2, 9.3, 11, 12, 14, 15以及16节。其它章节，以及上述提到的章节的部分内容，属非标准化内容，用于解释和说明标准化内容。如果标准化内容和非标准化内容有冲突，以标准化内容为准。
本规范的讨论与开发异常复杂且专业性强，需要对一些学术论题有深刻的见解并了解它们的发展过程。这些讨论在JMM web站点上都有存档。该站点提供了额外的信息，可以帮助理解本规范形成的过程。
阅读全文
因最近hashmap误用引起的死循环又发生了一些案例，左耳朵浩子写了一篇blog 疫苗：Java HashMap的死循环，看了一下，大家的分析如出一辙。这篇blog也是好几年前写的了，之前在平台技术部的博客上贴过，随着组织结构的调整，那个博客可能不再维护，把这篇文章在这儿也保存一下。
李鹏同学在blog里写了篇关于HashMap死锁模拟的文章: http://blog.csdn.net/madding/archive/2010/08/25/5838477.aspx 做个纠正,那个不是死锁问题,而是死循环。
这个问题,我们以前讨论过。 校长之前的博客和淘宝的毕玄的《分布式Java应用:基础与实践》一书中都提到过 velocity导致cpu 100% 的bug,起因是HashMap的使用不当所致。
经过之前的铺垫，现在可以进入正题了。
我们关注的操作有：get，put，remove 这3个操作。
对于哈希表，Java中采用链表的方式来解决hash冲突的。
一个HashMap的数据结构看起来类似下图：
实现了同步的HashTable也是这样的结构，它的同步使用锁来保证的，并且所有同步操作使用的是同一个锁对象。这样若有n个线程同时在get时，这n个线程要串行的等待来获取锁。
原文是09年时写的，在公司的邮件列表发过，同事一粟 和清英 创建的并发编程网 对这方面概念和实战有更好的文章，贴出来仅供参考。pdf格式在：http://www.slideshare.net/hongjiang/concurrent-hashmap 可以获取
ConcurrentHashMap是Java5中新增加的一个线程安全的Map集合，可以用来替代HashTable。对于ConcurrentHashMap是如何提高其效率的，可能大多人只是知道它使用了多个锁代替HashTable中的单个锁，也就是锁分离技术（Lock Stripping）。实际上，ConcurrentHashMap对提高并发方面的优化，还有一些其它的技巧在里面（比如你是否知道在get操作的时候，它是否也使用了锁来保护？）。
我会试图用通俗一点的方法讲解一下 ConcurrentHashMap的实现方式，不过因为水平有限，在整理这篇文档的过程中，发现了更多自己未曾深入思考过的地方，使得我不得不从新调整了自己的讲解方式。我假设受众者大多是对Java存储模型(JMM)认识并不很深的（我本人也是）。如果我们不断的对ConcurrentHashMap中一些实现追问下去，最终还是要归到JMM层面甚至更底层的。这篇文章的关注点主要在同步方面，并不去分析HashMap中的一些数据结构方面的实现。
版权声明：本文为本作者原创文章，转载请注明出处。感谢 码梦为生| 刘锟洋 的投稿
今天看到 这篇文章：您还有心跳吗？超时机制分析 觉得挺有意思，有兴趣的同学可以先看看他的文章，简单记录了下自己的一个想法，无论好坏，权当参与讨论，共同进步吧。
其实 lz 一直限制在了取系统时间耗时的问题上，所以，一直想变相的通过各种手法排除掉获取系统时间的逻辑，比如使用“次数”来对连接实现超时控制，但其实，使用次数来表示超时控制本身就是个伪命题， 比如，在超时次数的阀值是100，如果在90次后，就一直没有被其他线程使用，一直不到阀值，那怎么去将这个连接释放掉呢？
所以，我想到了另外一种方式解决这个问题： 阅读全文
Loading...
