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:
Fowler, Martin. Refactoring, Addison-Wesley, 1999.
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
Herlihy, Maurice. "Wait-free synchronization", ACM Transactions on
Programming Languages and Systems, vol. 13, no. 1, 1991.
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.
Last modified: Fri Oct 13 17:51:57 EDT 2000