《Java并发编程的艺术》读书笔记——并发容器框架
并发容器框架
1.多线程中的容器
上图是Java中的集合框架结构，当我们在单线程中使用集合框架中，一切都是顺理成章的。但到了多线程环境，由于基础容器就没有做同步处理，可能会出现很多线程安全的问题。最常见的问题就是常用的HashMap在多线程环境下执行put方法时可能会形成环链而导致死循环，从而占尽CPU。
Java在util集合框架的基础上又添加了线程安全的集合框架，在util包下的concurrent子包中。
举个例子，上面说的HashMap在多线程环境中的问题就可以使用ConcurrentHashMap来解决，在ConcurrentHashMap中，使用一种叫多段锁的机制，HashTable虽然是线程安全的，但所有的数据都共用一把锁，所以在数据访问的时候所有线程将会竞争同一把锁，这样就把并发转化成了串行，大大降低了性能。而多段锁机制是把数据切分成多段，每段有一把锁，这样在访问不同段的时候就可以实现并发。ConcurrentHashMap的数据结构是维持一个叫做Segment的数组，每个Segment都是一个可重入锁，而Segment里面又有一个Node数组(跟HashMap中的Node一样，实现了Map.Entry接口），这个Node数组就是用来真正存数据的数据结构，而每个Segment就用来管理自己内部的Node数组的线程安全访问。
在使用ConcurrentHashMap时，get方法先通过hash定位到Segment，然后再has到Segment里面的Node，由于使用了分段锁，在hash到Segment时，共享变量全部都使用了volatile，因此在读的时候可以保证变量的可见性，而在写的时候要加锁(put操作)，而hash到Node时不需要加锁，因此get操作的效率是比较高的。这里的效率高的前提是hash Segment的效果要比较好，如果在has Segment时冲突就非常严重，那么多段锁将无效，其实ConcurrentHashMap就退化成了HashTable了。在ConcurrentHashMap中使用了再hash的方法来提高hash的效果。
2阻塞队列
阻塞队列是在util队列的基础上添加了阻塞的功能，也就是说在队列满的时候，再添加元素就会阻塞直到队列不满；当队列为空是获取元素阻塞直到队列不空为止，这和生产者-消费者模式很相似。
Java为阻塞队列提供了7个实现，分别是数组数据结构有界的阻塞队列ArrayBlockingQueue，链表数据结构的有界阻塞队列LinkedBlockingQueue,支持优先级排序的无界阻塞队列PriorityBlockingQueue，使用优先级队列实现的无界阻塞队列DelayQueue，不存储元素的阻塞队列SynchronousQueue，链表数据结构的无界阻塞队列LinkedTransferQueue，链表数据结构双向阻塞队列LinkedBlockingDeque。阻塞队列的实现跟生产者-消费者模式差不多，都使用了通知-等待机制。这里就不再赘述。
3.Fork/Join框架
Fork/Join是一个把大任务切分成小任务再把小任务的执行结果组合成最终结果的并发编程框架。
Fork/Join框架把大任务切分成若干个小任务，然后把小任务放到几个队列中，每个队列分配一个工作线程。但是可能有的队列的线程先把队列中的所有任务执行完，而其他队列还有任务等待执行，这时Fork/Join框架就使用了一种任务窃取机制来提高线程的利用率。任务队列使用了双端队列，被窃取任务的队列永远从双端队列的头部取任务，而窃取任务的线程永远从双端队列的尾部拿任务。
JDK为我们实现了基础的Fork/Join框架，首先是任务类ForkJoinTask类，有两个了类：用于没有返回结果任务的RecursiveAction和用于有返回结果任务的RecursiveTask，然后通过ForkJoinPool来执行任务。
Fork/Join框架的工作原理是：ForkJoinPool内部维持一个ForkJoinTask数组和一个ForkJoinThread数组，ForkJoinTask用来保存工作任务，而ForkJoinThread是用来执行任务的线程。执行任务时就调用fork方法，然后调用join方法等待执行返回结果，join方法和Thread和join方法一样，会阻塞当前线程直接join的线程完成才会继续执行。