Re: JavaMemoryModel: Employing copy-on-write & avoiding double-check idiom

From: Doug Lea (dl@cs.oswego.edu)
Date: Tue Oct 30 2001 - 20:39:02 EST


>
> I am trying to employ copy-on-write with a Map in a project to avoid
> synchronized access to it. As the program runs, the Map grows as new
> mappings are added, but they are added in less frequency as time goes on
> until eventually no more mappings get added. There is logic that needs to
> get a value for a particular key from the Map and add a new mapping if the
> key isn't present. I don't see how to accomplish that logic in a
> thread-safe manner without avoiding the double-checked locking idiom or some
> other concurrency error.

Probably best here is an optimistic style. Assuming a field
"themap" protected with lock aLock, you could do something like:

 Map m;
 for (;;) {
   synchronized(aLock) {
     m = themap;
   }
   if (m.containsKey(x))
     break;

   Map newmap = m.createNewMapIncluding(x, y);
   synchronized(aLock) {
     if (themap == m) {
       m = themap = newmap;
       break;
     }
   }
 }
 ... now use m ...

Under JSR133 rules, you can avoid the first lock if you declare themap
field as volatile. Until JSR133 is made part of the standard, you can
do this only if you running on JVMs somehow known to support it
already (including hotspot 1.4).

> Oh, and should the reference to the Map be made
> volatile? From my understanding, it should be.

> I don't understand why the
> reference to the internal array in
> EDU.oswego.cs.dl.util.concurrent.CopyOnWriteArrayList is not marked
> volatile.

This code works conservatively under pre-JSR133 semantics. So EVERY
access to the array goes through a lock (similar to above). A
post-JSR133 version can be made faster.

-- 
Doug Lea, Computer Science Department, SUNY Oswego, Oswego, NY 13126 USA
dl@cs.oswego.edu 315-312-2688 FAX:315-312-5424 http://gee.cs.oswego.edu/  
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



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