Dual data structures

Synchronized blocks in Java allow multithreaded programs to coordinate access to shared data structures. Their performance can suffer, however, if the operating system preempts a thread that is holding the lock on a synchronized object. Nonblocking data structures avoid this problem with clever algorithms (based on atomic variables) in which no thread ever waits for another.

This talk will present the notion of dual data structures, which also support condition synchronization. When expected conditions are met, a dual data structure works like any other nonblocking structure. It also avoids contention when threads must wait (e.g., for data to be added to a currently empty queue), and guarantees immediate wakeup when the wait is over. When dual queues were used (in the Java SE 6 release) to replace the original semaphore-based code in java.util.concurrent.ThreadPoolExecutor, performance improved by about a factor of 10.