Concurrent Programming in Java
© 1996-1999 Doug Lea  



2.4 Structuring and Refactoring Classes


For a more extensive discussion of double-check, see the page on "Double-Checked Locking is Broken" .

Readings and Resources

A general account of refactoring classes is: Optimistic update algorithms that can be proven to succeed eventually include the class of wait-free algorithms in which no thread ever blocks on a condition that can be satisfied only by the action of some other thread. In wait-free algorithms, every thread succeeds after a finite number of attempts, regardless of what other threads do or do not do. Most algorithms employ the notion of helping: when a thread cannot continue, it takes some action to help another thread complete its task. The theory of wait-free algorithms is described in: Practical wait-free update algorithms are known for only a small number of common data structures, for example queues and lists. However, these algorithms are increasingly used in underlying run-time support in operating system kernels and JVM implementations. The online supplement contains an adaptation of a wait-free queue class described in the following paper, as well as links to descriptions of wait-free algorithms implemented in other languages.

A thorough discussion of non-blocking data-structure techniques may be found in the PhD thesis of Michael Greenwald. "Non-Blocking Synchronization and System Design", Stanford University, 1999.

Doug Lea
Last modified: Fri Oct 13 17:51:57 EDT 2000