双端队列与工作密取

Java 6 增加了两种容器类型，Deque（发音为 “deck”）和 BlockingDeque，它们分别对 Queue 和 BlockingQueue 进行了扩展。

• Deque 是一个双端队列，实现了在队列头和队列尾的高效插入和移除。

• 具体实现包括 ArrayDeque 和 LinkedBlockingDeque。

双端队列适用于工作密取（Work Stealing）：在生产者-消费者设计中，所有消费者有一个共享的工作队列，而在工作密取设计中，每个消费者都有各自的双端队列。如果一个消费者完成了自己双端队列中的全部工作，那么它可以从其他消费者双端队列末尾秘密地获取工作。

工作密取模式比传统的生产者-消费者模式具有更高的可伸缩性，这是因为工作者线程不会在单个共享的任务队列上发生竞争。

• 在大多数时候，它们都只是访问自己的双端队列，从而极大地减少了竞争。

• 当工作者线程需要访问另一个队列时，它会从队列的尾部而不是从头部获取工作，因此进一步降低了队列上的竞争程度。

工作密取非常适用于既是消费者也是生产者的问题——当执行某个工作时可能导致出现更多的工作。例如，在网页爬虫程序中处理一个页面时，通常会发现有更多的页面需要处理。类似的还有许多搜索图的算法，例如在垃圾回收阶段对堆进行标记，都可以通过工作密取机制来实现高效并行。

• 当一个工作线程找到新的任务单元时，它会将其放到自己队列的末尾（或者在工作共享设计模式中，放入其他工作者线程的队列中）。

• 当双端队列为空时，它会在另一个线程的队列队尾查找新的任务，从而确保每个线程都保持忙碌状态。