xylz,imxylz

关注后端架构、中间件、分布式和并发编程

   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  111 随笔 :: 10 文章 :: 2679 评论 :: 0 Trackbacks

07 2010 档案

     摘要:
在Set中有一个排序的集合SortedSet,用来保存按照自然顺序排列的对象。Queue中同样引入了一个支持排序的FIFO模型。
并发队列与Queue简介 中介绍了,PriorityQueue和PriorityBlockingQueue就是支持排序的Queue。显然一个支持阻塞的排序Queue要比一个非线程安全的Queue实现起来要复杂的多,因此下面只介绍PriorityBlockingQueue,至于PriorityQueue只需要去掉Blocking功能就基本相同了。  阅读全文
posted @ 2010-07-30 16:15 imxylz 阅读(12724) | 评论 (0)  编辑

     摘要: 在上一节中详细分析了LinkedBlockingQueue 的实现原理。实现一个可扩展的队列通常有两种方式:一种方式就像LinkedBlockingQueue一样使用链表,也就是每一个元素带有下一个元素的引用,这样的队列原生就是可扩展的;另外一种就是通过数组实现,一旦队列的大小达到数组的容量的时候就将数组扩充一倍(或者一定的系数倍),从而达到扩容的目的。常见的ArrayList就属于第二种。前面章节介绍过的HashMap确是综合使用了这两种方式。
对于一个Queue而言,同样可以使用数组实现。使用数组的好处在于各个元素之间原生就是通过数组的索引关联起来的,一次元素之间就是有序的,在通过索引操作数组就方便多了。当然也有它不利的一面,扩容起来比较麻烦,同时删除一个元素也比较低效。
ArrayBlockingQueue 就是Queue的一种数组实现。  阅读全文
posted @ 2010-07-27 22:04 imxylz 阅读(11636) | 评论 (0)  编辑

     摘要: 在《并发容器 part 4 并发队列与Queue简介》节中的类图中可以看到,对于Queue来说,BlockingQueue是主要的线程安全版本。这是一个可阻塞的版本,也就是允许添加/删除元素被阻塞,直到成功为止。
BlockingQueue相对于Queue而言增加了两个操作:put/take。下面是一张整理的表格。  阅读全文
posted @ 2010-07-24 00:02 imxylz 阅读(17018) | 评论 (6)  编辑

     摘要: ConcurrentLinkedQueue是Queue的一个线程安全实现。先来看一段文档说明。
一个基于链接节点的无界线程安全队列。此队列按照 FIFO(先进先出)原则对元素进行排序。队列的头部 是队列中时间最长的元素。队列的尾部 是队列中时间最短的元素。新的元素插入到队列的尾部,队列获取操作从队列头部获得元素。当多个线程共享访问一个公共 collection 时,ConcurrentLinkedQueue 是一个恰当的选择。此队列不允许使用 null 元素。

由于ConcurrentLinkedQueue只是简单的实现了一个队列Queue,因此从API的角度讲,没有多少值的介绍,使用起来也很简单,和前面遇到的所有FIFO队列都类似。出队列只能操作头节点,入队列只能操作尾节点,任意节点操作就需要遍历完整的队列。
重点放在解释ConcurrentLinkedQueue的原理和实现上。  阅读全文
posted @ 2010-07-23 14:11 imxylz 阅读(17788) | 评论 (2)  编辑

     摘要: Queue是JDK 5以后引入的新的集合类,它属于Java Collections Framework的成员,在Collection集合中和List/Set是同一级别的接口。通常来讲Queue描述的是一种FIFO的队列,当然不全都是,比如PriorityQueue是按照优先级的顺序(或者说是自然顺序,借助于Comparator接口)。
下图描述了Java Collections Framework中Queue的整个家族体系。
对于Queue而言是在Collection的基础上增加了offer/remove/poll/element/peek方法,另外重新定义了add方法。对于这六个方法,有不同的定义。  阅读全文
posted @ 2010-07-21 12:21 imxylz 阅读(18911) | 评论 (5)  编辑

     摘要: 在上一篇中介绍了HashMap的原理,这一节是ConcurrentMap的最后一节,所以会完整的介绍ConcurrentHashMap的实现。

ConcurrentHashMap原理

在读写锁章节部分介绍过一种是用读写锁实现Map的方法。此种方法看起来可以实现Map响应的功能,而且吞吐量也应该不错。但是通过前面对读写锁原理的分析后知道,读写锁的适合场景是读操作>>写操作,也就是读操作应该占据大部分操作,另外读写锁存在一个很严重的问题是读写操作不能同时发生。要想解决读写同时进行问题(至少不同元素的读写分离),那么就只能将锁拆分,不同的元素拥有不同的锁,这种技术就是“锁分离”技术。
默认情况下ConcurrentHashMap是用了16个类似HashMap 的结构,其中每一个HashMap拥有一个独占锁。也就是说最终的效果就是通过某种Hash算法,将任何一个元素均匀的映射到某个HashMap的Map.Entry上面,而对某个一个元素的操作就集中在其分布的HashMap上,与其它HashMap无关。这样就支持最多16个并发的写操作。  阅读全文
posted @ 2010-07-20 17:48 imxylz 阅读(18365) | 评论 (9)  编辑

     摘要: 本来想比较全面和深入的谈谈ConcurrentHashMap的,发现网上有很多对HashMap和ConcurrentHashMap分析的文章,因此本小节尽可能的分析其中的细节,少一点理论的东西,多谈谈内部设计的原理和思想。
要谈ConcurrentHashMap的构造,就不得不谈HashMap的构造,因此先从HashMap开始简单介绍。

HashMap原理
我们从头开始设想。要将对象存放在一起,如何设计这个容器。目前只有两条路可以走,一种是采用分格技术,每一个对象存放于一个格子中,这样通过对格子的编号就能取到或者遍历对象;另一种技术就是采用串联的方式,将各个对象串联起来,这需要各个对象至少带有下一个对象的索引(或者指针)。显然第一种就是数组的概念,第二种就是链表的概念。所有的容器的实现其实都是基于这两种方式的,不管是数组还是链表,或者二者俱有。HashMap采用的就是数组的方式。
有了存取对象的容器后还需要以下两个条件才能完成Map所需要的条件。  阅读全文
posted @ 2010-07-20 00:22 imxylz 阅读(20152) | 评论 (3)  编辑

     摘要: 从这一节开始正式进入并发容器的部分,来看看JDK 6带来了哪些并发容器。
在JDK 1.4以下只有Vector和Hashtable是线程安全的集合(也称并发容器,Collections.synchronized*系列也可以看作是线程安全的实现)。从JDK 5开始增加了线程安全的Map接口ConcurrentMap和线程安全的队列BlockingQueue(尽管Queue也是同时期引入的新的集合,但是规范并没有规定一定是线程安全的,事实上一些实现也不是线程安全的,比如PriorityQueue、ArrayDeque、LinkedList等,在Queue章节中会具体讨论这些队列的结构图和实现)。

在介绍ConcurrencyMap之前先来回顾下Map的体系结构。下图描述了Map的体系结构,其中蓝色字体的是JDK 5以后新增的并发容器。  阅读全文
posted @ 2010-07-19 15:25 imxylz 阅读(20168) | 评论 (8)  编辑

posted @ 2010-07-16 11:59 imxylz 阅读(8889) | 评论 (4)  编辑

     摘要:
主要谈谈锁的性能以及其它一些理论知识,内容主要的出处是《Java Concurrency in Practice》,结合自己的理解和实际应用对锁机制进行一个小小的总结。

首先需要强调的一点是:所有锁(包括内置锁和高级锁)都是有性能消耗的,也就是说在高并发的情况下,由于锁机制带来的上下文切换、资源同步等消耗是非常可观的。在某些极端情况下,线程在锁上的消耗可能比线程本身的消耗还要多。所以如果可能的话,在任何情况下都尽量少用锁,如果不可避免那么采用非阻塞算法是一个不错的解决方案,但是却也不是绝对的。  阅读全文
posted @ 2010-07-16 00:15 imxylz 阅读(14489) | 评论 (2)  编辑

     摘要:
这一节主要是谈谈读写锁的实现。
上一节中提到,ReadWriteLock看起来有两个锁:readLock/writeLock。如果真的是两个锁的话,它们之间又是如何相互影响的呢?
事实上在ReentrantReadWriteLock里锁的实现是靠java.util.concurrent.locks.ReentrantReadWriteLock.Sync完成的。这个类看起来比较眼熟,实际上它是AQS的一个子类,这中类似的结构在CountDownLatch、ReentrantLock、Semaphore里面都存在。同样它也有两种实现:公平锁和非公平锁,也就是java.util.concurrent.locks.ReentrantReadWriteLock.FairSync和java.util.concurrent.locks.ReentrantReadWriteLock.NonfairSync。这里暂且不提。
在ReentrantReadWriteLock里面的锁主体就是一个Sync,也就是上面提到的FairSync或者NonfairSync,所以说实际  阅读全文
posted @ 2010-07-15 00:41 imxylz 阅读(17963) | 评论 (1)  编辑

     摘要: 从这一节开始介绍锁里面的最后一个工具:读写锁(ReadWriteLock)。
ReentrantLock 实现了标准的互斥操作,也就是一次只能有一个线程持有锁,也即所谓独占锁的概念。前面的章节中一直在强调这个特点。显然这个特点在一定程度上面减低了吞吐量,实际上独占锁是一种保守的锁策略,在这种情况下任何“读/读”,“写/读”,“写/写”操作都不能同时发生。但是同样需要强调的一个概念是,锁是有一定的开销的,当并发比较大的时候,锁的开销就比较客观了。所以如果可能的话就尽量少用锁,非要用锁的话就尝试看能否改造为读写锁。
ReadWriteLock描述的是:一个资源能够被多个读线程访问,或者被一个写线程访问,但是不能同时存在读写线程。也就是说读写锁使用的场合是一个共享资源被大量读取操作,而只有少量的写操作(修改数据)。清单1描述了ReadWriteLock的API。  阅读全文
posted @ 2010-07-14 14:18 imxylz 阅读(21043) | 评论 (4)  编辑

     摘要: Semaphore 是一个计数信号量。从概念上讲,信号量维护了一个许可集。如有必要,在许可可用前会阻塞每一个 acquire(),然后再获取该许可。每个 release() 添加一个许可,从而可能释放一个正在阻塞的获取者。但是,不使用实际的许可对象,Semaphore 只对可用许可的号码进行计数,并采取相应的行动。
说白了,Semaphore是一个计数器,在计数器不为0的时候对线程就放行,一旦达到0,那么所有请求资源的新线程都会被阻塞,包括增加请求到许可的线程,也就是说Semaphore不是可重入的。每一次请求一个许可都会导致计数器减少1,同样每次释放一个许可都会导致计数器增加1,一旦达到了0,新的许可请求线程将被挂起。
缓存池整好使用此思想来实现的,比如链接池、对象池等。  阅读全文
posted @ 2010-07-13 22:41 imxylz 阅读(20162) | 评论 (2)  编辑

     摘要:
如果说CountDownLatch是一次性的,那么CyclicBarrier正好可以循环使用。它允许一组线程互相等待,直到到达某个公共屏障点 (common barrier point)。所谓屏障点就是一组任务执行完毕的时刻。
  阅读全文
posted @ 2010-07-12 23:33 imxylz 阅读(19257) | 评论 (2)  编辑

     摘要: 此小节介绍几个与锁有关的有用工具。
闭锁(Latch)
闭锁(Latch):一种同步方法,可以延迟线程的进度直到线程到达某个终点状态。通俗的讲就是,一个闭锁相当于一扇大门,在大门打开之前所有线程都被阻断,一旦大门打开所有线程都将通过,但是一旦大门打开,所有线程都通过了,那么这个闭锁的状态就失效了,门的状态也就不能变了,只能是打开状态。也就是说闭锁的状态是一次性的,它确保在闭锁打开之前所有特定的活动都需要在闭锁打开之后才能完成。
CountDownLatch是JDK 5+里面闭锁的一个实现,允许一个或者多个线程等待某个事件的发生。CountDownLatch有一个正数计数器,countDown方法对计数器做减操作,await方法等待计数器达到0。所有await的线程都会阻塞直到计数器为0或者等待线程中断或者超时。  阅读全文
posted @ 2010-07-09 09:21 imxylz 阅读(25233) | 评论 (6)  编辑

     摘要: 这是一份完整的Java 并发整理笔记,记录了我最近几年学习Java并发的一些心得和体会。  阅读全文
posted @ 2010-07-08 19:17 imxylz 阅读(97494) | 评论 (43)  编辑

     摘要: 本小节介绍锁释放Lock.unlock()。
Release/TryRelease
unlock操作实际上就调用了AQS的release操作,释放持有的锁。  阅读全文
posted @ 2010-07-08 12:33 imxylz 阅读(25344) | 评论 (11)  编辑

     摘要: 接上篇,这篇从Lock.lock/unlock开始。特别说明在没有特殊情况下所有程序、API、文档都是基于JDK 6.0的。
在没有深入了解内部机制及实现之前,先了解下为什么会存在公平锁和非公平锁。公平锁保证一个阻塞的线程最终能够获得锁,因为是有序的,所以总是可以按照请求的顺序获得锁。不公平锁意味着后请求锁的线程可能在其前面排列的休眠线程恢复前拿到锁,这样就有可能提高并发的性能。这是因为通常情况下挂起的线程重新开始与它真正开始运行,二者之间会产生严重的延时。因此非公平锁就可以利用这段时间完成操作。这是非公平锁在某些时候比公平锁性能要好的原因之一。  阅读全文
posted @ 2010-07-07 00:05 imxylz 阅读(32711) | 评论 (6)  编辑

     摘要: 在理解J.U.C原理以及锁机制之前,我们来介绍J.U.C框架最核心也是最复杂的一个基础类:java.util.concurrent.locks.AbstractQueuedSynchronizer。

AQS
AbstractQueuedSynchronizer,简称AQS,是J.U.C最复杂的一个类,导致绝大多数讲解并发原理或者实战的时候都不会提到此类。但是虚心的作者愿意借助自己有限的能力和精力来探讨一二(参考资源中也有一些作者做了部分的分析。)。
首先从理论知识开始,在了解了相关原理后会针对源码进行一些分析,最后加上一些实战来描述。  阅读全文
posted @ 2010-07-06 18:29 imxylz 阅读(40876) | 评论 (3)  编辑

     摘要: 前面的章节主要谈谈原子操作,至于与原子操作一些相关的问题或者说陷阱就放到最后的总结篇来整体说明。从这一章开始花少量的篇幅谈谈锁机制。
上一个章节中谈到了锁机制,并且针对于原子操作谈了一些相关的概念和设计思想。接下来的文章中,尽可能的深入研究锁机制,并且理解里面的原理和实际应用场合。
尽管synchronized在语法上已经足够简单了,在JDK 5之前只能借助此实现,但是由于是独占锁,性能却不高,因此JDK 5以后就开始借助于JNI来完成更高级的锁实现。
JDK 5中的锁是接口java.util.concurrent.locks.Lock。另外java.util.concurrent.locks.ReadWriteLock提供了一对可供读写并发的锁。根据前面的规则,我们从java.util.concurrent.locks.Lock的API开始。  阅读全文
posted @ 2010-07-05 13:37 imxylz 阅读(33502) | 评论 (11)  编辑

     摘要: 在JDK 5之前Java语言是靠synchronized关键字保证同步的,这会导致有锁(后面的章节还会谈到锁)。
锁机制存在以下问题:
(1)在多线程竞争下,加锁、释放锁会导致比较多的上下文切换和调度延时,引起性能问题。
(2)一个线程持有锁会导致其它所有需要此锁的线程挂起。
(3)如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置,引起性能风险。
volatile是不错的机制,但是volatile不能保证原子性。因此对于同步最终还是要回到锁机制上来。
独占锁是一种悲观锁,synchronized就是一种独占锁,会导致其它所有需要锁的线程挂起,等待持有锁的线程释放锁。而另一个更加有效的锁就是乐观锁。所谓乐观锁就是,每次不加锁而是假设没有冲突而去完成某项操作,如果因为冲突失败就重试,直到成功为止。  阅读全文
posted @ 2010-07-04 18:03 imxylz 阅读(36106) | 评论 (19)  编辑

     摘要: 在这个小结里面重点讨论原子操作的原理和设计思想。
由于在下一个章节中会谈到锁机制,因此此小节中会适当引入锁的概念。
在Java Concurrency in Practice中是这样定义线程安全的:
当多个线程访问一个类时,如果不用考虑这些线程在运行时环境下的调度和交替运行,并且不需要额外的同步及在调用方代码不必做其他的协调,这个类的行为仍然是正确的,那么这个类就是线程安全的。  阅读全文
posted @ 2010-07-03 20:40 imxylz 阅读(36359) | 评论 (16)  编辑

     摘要: 在这一部分开始讨论数组原子操作和一些其他的原子操作。
AtomicIntegerArray/AtomicLongArray/AtomicReferenceArray的API类似,选择有代表性的AtomicIntegerArray来描述这些问题。
int get(int i)
获取位置 i 的当前值。很显然,由于这个是数组操作,就有索引越界的问题(IndexOutOfBoundsException异常)。

对于下面的API起始和AtomicInteger是类似的,这种通过方法、参数的名称就能够得到函数意义的写法是非常值得称赞的。在《重构:改善既有代码的设计》和《代码整洁之道》中都非常推崇这种做法。  阅读全文
posted @ 2010-07-02 14:19 imxylz 阅读(35328) | 评论 (6)  编辑

     摘要: 从相对简单的Atomic入手(java.util.concurrent是基于Queue的并发包,而Queue,很多情况下使用到了Atomic操作,因此首先从这里开始)。很多情况下我们只是需要一个简单的、高效的、线程安全的递增递减方案。注意,这里有三个条件:简单,意味着程序员尽可能少的操作底层或者实现起来要比较容易;高效意味着耗用资源要少,程序处理速度要快;线程安全也非常重要,这个在多线程下能保证数据的正确性。这三个条件看起来比较简单,但是实现起来却难以令人满意。
通常情况下,在Java里面,++i或者--i不是线程安全的,这里面有三个独立的操作:或者变量当前值,为该值+1/-1,然后写回新的值。在没有额外资源可以利用的情况下,只能使用加锁才能保证读-改-写这三个操作时“原子性”的。  阅读全文
posted @ 2010-07-01 15:21 imxylz 阅读(45496) | 评论 (2)  编辑


©2009-2014 IMXYLZ