Building Blocks - Java Concurrency in Practice - page 106

5.3.3. Deques and Work Stealing
Java 6 also adds another two collection types, Deque (pronounced “deck”) and Blockin-
gDeque , that extend Queue and BlockingQueue . A Deque is a doubleended queue that
allows efficient insertion and removal from both the head and the tail. Implementations in-
clude ArrayDeque and LinkedBlockingDeque .
Just as blocking queues lend themselves to the producer-consumer pattern, deques lend them-
selves to a related pattern called work stealing . A producerconsumer design has one shared
work queue for all consumers; in a work stealing design, every consumer has its own deque.
If a consumer exhausts the work in its own deque, it can steal work from the tail of someone
else's deque. Work stealing can be more scalable than a traditional producer-consumer design
because workers don't contend for a shared work queue; most of the time they access only
their own deque, reducing contention. When a worker has to access another's queue, it does
so from the tail rather than the head, further reducing contention.
Work stealing is well suited to problems in which consumers are also producers—when per-
forming a unit of work is likely to result in the identification of more work. For example,
processing a page in a web crawler usually results in the identification of new pages to
be crawled. Similarly, many graph-exploring algorithms, such as marking the heap during
garbage collection, can be efficiently parallelized using work stealing. When a worker iden-
tifies a new unit of work, it places it at the end of its own deque (or alternatively, in a work
sharing design, on that of another worker); when its deque is empty, it looks for work at the
end of someone else's deque, ensuring that each worker stays busy.