Concurrent Programming in Java
© 1996-1999 Doug Lea

2.4 Structuring and Refactoring Classes

Follow-ups

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:

Fowler, Martin. Refactoring, Addison-Wesley, 1999.

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:

Herlihy, Maurice. "Wait-free synchronization", ACM Transactions on Programming Languages and Systems, vol. 13, no. 1, 1991.

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.

Michael, Maged and Michael Scott. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms Proceedings, 15th ACM Symposium on Principles of Distributed Computing, ACM, 1996.

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