Re: JavaMemoryModel: How bad are incorrectly synchronized programs?

From: Doug Lea (dl@cs.oswego.edu)
Date: Thu Jul 31 2003 - 08:31:50 EDT


> Assuming we had the technology, would we want to rule out incorrectly
> synchronized programs?
>
> That is, suppose the compiler determines that
> there is a data race in your program.

As you know as well as anywone, these two statements should not be
considered as equivalent. There are useful algorithms and idioms in
which all races are provably benign, assuming a given memory model, so
are "correctly synchronized". Here's a prototypical example:

class X {
  volatile boolean available = false;
  Object data = null;

  void f() { // executed by "reader" threads
    if (available)
      use(data); // (*)
  }

  void g() { // executed by a "writer" thread
    for (;;) {
      if (occasionallyTrue) {
        data = new Object();
        available = true;
      }
   }
}

... supposing that the correctness of the program (which cannot
normally be automatically deduced) relies only on the fact that on
line (*), the data field seen is not "too old". In particular, it is
never the case that available is seen as true but data is seen as
null. (This initial case is basically the same as in double-check.)
Of course, in real programs, you need a lot of care to make sure
everything works out. For example, you can generally replace "Object"
here with a class with all-final fields, but not with most other kinds
of classes.

Most lock-free synchronization algorithms rely on this sort of
guarantee, which falls out of Bill and Jeremy's model (which prohibits
non-volatile reads to be reordered with volatile reads), and I think
also Sarita's.

-Doug
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:49 EDT