<进阶-4> 并发容器类和同步工具类

4.1 同步容器类
同步容器类包括Vector和Hashtable,二者是jdk的一部分，此外还包括在jdk1.2中添加的一些功能相似的类：由Collections.synchronizedXxx等工厂方法创建的。这些类实现线程安全的方式是：将他们的状态封装起来，并对每个公有方法都进行同步，使得每次只有一个线程能访问容器的状态。
同步容器类是线程安全的，但在某些情况下可能需要额外的客户端加锁来保护复合操作。

4.1.1 ConcurrentModificationException异常
无论是直接迭代还是在java5.0引入的for-each循环语法中，对容器类进行迭代的标准方式都是使用Iterator.然而，如果有其他线程并发地修改容器，那么即使是使用迭代器也无法避免在迭代期间对容器加锁。在设计同步容器类的迭代器时并没有考虑到并发修改的问题，并且他们表现出的行为是“及时失败”的，这意味着，当他们发现容器在迭代过程中被修改时会抛出一个ConcurrentModificationException异常（如hasNext或next方法）。
虽然加锁可以防止迭代器抛出ConcurrentModificationException，但必须记住在所有对共享容器进行迭代的地方都需要加锁。实际情况更复杂，因为某些情况下，迭代器会隐藏起来。如迭代器的toString,containsAll,removeAll,retainAll,hashCode和equals方法,以及把容器作为参数的构造函数，都会隐含对容器进行迭代，都可能抛出ConcurrentModificationException。

4.2 并发容器
Java5.0提供了多种并发容器类改进同步容器的性能。并发容器是针对多个线程并发访问设计的，如ConcurrentHashMap用来替代同步且基于散列的map，以及CopyOnWriteArrayList用于在遍历操作为主要操作的情况下代替List.在新的ConcurrentMap接口中增加了对一些常见复合操作的支持，如“若没有则添加”，替换以及有条件删除等。
通过并发容器来替代同步容器，可以极大地提高伸缩性并降低风险。
1.concurrentHashMap
与HashMap一样，ConcurrentHashMap也是一个基于散列的Map，但它使用了一种完全不同的加锁策略来提高并发性和伸缩性。ConcurrentHashMap并不是将每一个方法都在同一个锁上同步并使得每次只能有一个线程访问容器，而是使用一种粒度更细的加锁机制来实现更大程度的共享，这种机制称为分段锁（Lock Striping）。在这种机制下，任意数量的读取线程可以并发地访问map,执行读取操作的线程和执行写入操作的线程可以并发地访问map，并且一定数量的写入线程可以并发地修改Map.
ConcurrentHashMap与其他并发容器一起增强了同步容器类：他们提供的迭代器不会抛出ConcurrentModificationException，因此不需要在迭代过程中对容器加锁。ConcurrentHashMap返回的迭代器具有弱一致性（Weakly Consistent）,而并非及时失败。
只有当应用程序需要加锁Map以进行独占访问时，才应该放弃使用ConcurrentHashMap。

“由于ConcurrentHashMap不能被加锁来执行独占访问，因此我们无法使用客户端加锁来创建新的原子操作。但一些常见的复合操作都提供了原子接口，如putIfAbsent,removeIfEqual,replaceIfEqual等。”这是《Java 并发编程实战》中文版里的原话，但我半天没能理解，于是找到英文版：
The one feature offered by the synchronized Map implementations but not by ConcurrentHashMap is the ability to lock the map for exclusive access. With Hashtable and synchronizedMap , acquiring the Map lock prevents any other thread from accessing it. This might be necessary in unusual cases such as adding several mappings atomically, or iterating the Map several times and needing to see the same elements in the same order. On the whole, though, this is a reasonable tradeoff : concurrent collections should be expected to change their contents continuously.

Because it has so many advantages and so few disadvantages compared to Hashtable or synchronizedMap , replacing synchronized Map implementations with ConcurrentHashMap in most cases results only in better scalability. Only if your application needs to lock the map for exclusive access [3] is ConcurrentHashMap not an appropriate drop-in replacement.
这里可以看出，“ConcurrentHashMap不能被加锁来执行独占访问”只是说ConcurrentHashMap本身内置锁没有提供一个排他的锁供线程独占访问，而是提供分段锁来提高并发性。而不是说不能获取ConcurrentHashMap的锁，如：

public class ConcurrentHashmapTest
{
    public static ConcurrentMap<String, String> map = new ConcurrentHashMap<String, String>();
    
    public static void main(String[] args)
	{
		synchronized (map)
		{
			map.put("1", "1");
		}
	}
}

还可以参考：
http://ifeve.com/concurrenthashmap/
http://ifeve.com/concurrenthashmap-weakly-consistent/

2. CopyOnWriteArrayList
CopyOnWriteArrayList用于替代同步List,在某些情况下它提供了更好的并发性能，并且在迭代期间不需要对容器进行加锁或复制（类似，CopyOnWriteArraySet的作用是替代同步Set）。
“写入时复制”容器的线程安全性在于只要正确地发布一个事实不可变的对象，那么在访问该对象时就不再需要进一步的同步。
每次修改时，都会创建并重新发布一个新的容器副本，从而实现可变性。对于修改之前的老的副本即使已经被引用，但不会被改变，因此也不需要同步。因此，多个线程可以同时对这个容器进行迭代，而不会彼此干扰或与修改容器的线程相互干扰。“写入时复制”容器返回的迭代器不会抛出ConcurrentModificationException，并且返回的元素与迭代器创建时容器的元素完全一致，不必考虑之后修改操作所带来的影响。

但是，每次修改容器时都会复制底层数组，这需要一定的开销，特别是容器的规模较大时。仅当迭代操作远远多于修改操作时，才应该使用“写入时复制”容器。

3. 阻塞队列和生产者-消费者模式
阻塞队列提供了可阻塞的put和take方法，以及支持定时的offer和poll方法。当试图向队列添加元素而队列已满，或想从队列移出元素而队列为空的时候，阻塞队列（blocking queue）导致线程阻塞。在协调多个线程之间的合作时，阻塞队列是一个有用的工具。


阻塞队列方法分为3类，这取决于当队列为空或满时他们的响应方式。
1）如果将队列当做线程管理工具来使用，将要用到put和take,不满足条件会阻塞。
2）当条件不满足（队列是空或满）时抛出异常，需要用add,remove和element.简称are.
3）当然，队列空或满时是场景常态，一定要使用offer,poll和peek替代，这时候会返回null不抛异常（所以想这种队列里插入null值是非法的）。

还有带有超时的offer方法和poll方法，如：
Boolean success = q.offer(x, 100, TimeUnit.MILLISECONDS);
尝试在100毫秒在队列的尾部插入一个元素。如果成功返回true，否则，超时后返回false.

Java.util.concurrent包（JUC）提供了阻塞队列的几个变种。
1）默认情况下,LinkedBlockingQueue的容量是没有上界的，但也可以指定最大容量。
2）LinkedBlockDeque是一个双端队列。（1）和（2）都是链表结构实现的。
3）ArrayBlockingQueue在构造时需要指定容量，并且有一个可选的boolean参数来指定是否需要公平性。若设置了公平性，则等待了最长事件的线程会优先得到处理。通常，公平性会降低性能，只有在确实非常需要时才使用它。
4）PriorityBlockingQueue是一个带优先级的队列，而不是先进先出队列。元素按他们的优先级顺序被移出。该队列没有容量上限，但是，如果队列是空的，取元素将会阻塞。
5) SynchronousQueue是这样 一种阻塞队列，其中每个 put 必须等待一个 take，反之亦然。同步队列没有任何内部容量，甚至连一个队列的容量都没有。
不能在同步队列上进行 peek，因为仅在试图要取得元素时，该元素才存在；
除非另一个线程试图移除某个元素，否则也不能（使用任何方法）添加元素；
也不能迭代队列，因为其中没有元素可用于迭代。队列的头是尝试添加到队列中的首个已排队线程元素； 如果没有已排队线程，则不添加元素并且头为 null。
SynchronousQueue可以参考：
http://blog.csdn.net/hudashi/article/details/7076814
http://hubingforever.blog.163.com/blog/static/17104057920107415915820/
http://www.oschina.net/translate/implementing-producer-consumer-using-synchronousqueue

阻塞队列支持生产者-消费者这种设计模式。当数据生成时，生产者把数据放入队列，当消费者准备处理数据时，将从队列中获取数据。BlockingQueue简化了生产者-消费者设计的实现过程，它支持任意数量的生产者和消费者。类库中包含了BlockingQueue的多种实现，其中LinkedBlockingQueue和ArrayBlockingQueue是FIFO队列，二者分别于LinkedList和ArrayList类似，但比同步List拥有更好的并发性能。PriorityBlockingQueue是一个按优先级排序的队列。当希望按照某种顺序而不是FIFO来处理元素时，这个队列非常有用。

BlockingQueue的put和take等方法会抛出受检查异常（Checked Exception）InterruptedException,关于线程中断前面已经讨论过了。

4.3 同步工具类
在容器类中，阻塞队列是一种独特的类，他们不仅能作为保存对象的容器，还能协调生产者和消费者等线程之间的控制流，因为take和put等方法将阻塞，知道队列达到期望的状态。
同步工具类可以是任何一个对象，只要它根据自身的状态来协调线程的控制流。阻塞队列可以作为同步工具类，其他类型的同步工具类还包括信号量（Semaphore）,栅栏（Barrier）以及闭锁（Latch）.

4.3.1 闭锁（CountDownLatch）
闭锁是一种同步工具类，可以延迟线程的进度直到到达终止状态。闭锁的作用相当于一扇门：在闭锁到达结束状态之前，这扇门一直是关闭的，并且没有任何线程能通过，当到达结束状态时，这扇门会打开并允许所有的线程通过。countDown方法最好在finally里执行。
示例可以参考：http://www.itzhai.com/the-introduction-and-use-of-a-countdownlatch.html

4.3.2  FutureTask
FutureTask也可以当做闭锁，FutureTask表示的计算是通过Callable来实现的，相当于一种可生成结果的Runnable，并且可以处于以下3中状态：等待运行（Waiting to run）,正在运行（Running）和运行完成（Completed），当FutureTask进入完成状态后，他会永远停止在这个状态上。
Future.get的行为取决于任务的状态，任务完成那么get会立即返回，否则阻塞直到任务完成。
示例可以参考：
http://lf6627926.iteye.com/blog/1538313
http://www.cnblogs.com/dolphin0520/p/3949310.html

4.3.3 信号量（Semaphore）
计数信号量用来控制同时访问某个特定资源的操作数量，或者同时执行某个指定操作的数量。Semaphore中管理着一组虚拟的许可（permit）,许可的初始数量可通过构造函数来指定。在执行操作时可以首先获得（acquire）许可（只要还有剩余的许可），并在使用以后释放许可。如果没有许可那么acquire将阻塞直到有许可（或直到被中断或超时）。Release将返回以个许可给信号量。二值信号量可以用作互斥体（mutex）,并具备不可重入的加锁语义。
示例可以参考：http://hi.baidu.com/var_youyou/item/0623433e5009e6697d034b8e

4.3.4 栅栏（Barrier）
闭锁可以等待启动一组相关的操作，闭锁是一次性对象，一旦进入终止状态就不能重置。栅栏（Barrier）类似闭锁，能阻塞一组线程直到某个事件发生，栅栏与闭锁的关键区别在于，所有线程必须同时到达栅栏位置才能继续执行。闭锁用于等待事件，栅栏用于等待其他线程。
CyclicBarrier初始时还可带一个Runnable的参数，此Runnable任务在CyclicBarrier的数目达到后，所有其它线程被唤醒前被执行。
示例可以参考：http://blog.csdn.net/huang_xw/article/details/7090152