Re: Volatile happens before question

On 1/19/2012 8:18 AM, raphfrk@gmail.com wrote:


That one I specifically don't see. If you get a reader and a writer
accessing the map at the same time, then the reader will detect a change
and retry the operation. There's two get's on the reader side, it might
be useful to distinguish between them.

public V get(Object key) {
   int save = 0;
   V value = null;
   do {
     while (((save = writeCounter.get()) & 1) == 1); // RA
     value = map.get(key);
   } while (save != writeCounter.get()); // RB
   return value;
}

I'll do the same on the writer side just for clarity.

public V put(K key, V value) {
   lock.lock();
   try {
     writeCounter.getAndIncrement(); // WA
     map.put(key, value);
     writeCounter.getAndIncrement(); // WB
   } finally {
     lock.unlock();
   }
   return value;
}

So here's how I parse a "failed" read.

Thread 1 Thread 2
Writer Reader

                                 writerCounter.get() // RA
writeCounter.increment() // WA
map.put()
                                 // 1: No happens-before here

                                 map.get()
                                 writerCounter.get() // RB
                                 writerCounter.get() // RA

                                 // 2: this repeats until...

writeCounter.increment() // WB
                          -----> writerCounter.get() // RA
                                 map.get()
                                 writerCounter.get() // RB

The ----> arrow indicates the happens-before (which is the same way the
JLS shows happens-before).

(I'm ignoring the happens-before for the writeCounter itself. That
there is such a relationship should be obvious.)

Now with the WB -> RA pair there's been happens before relationship
established and the second map.get() in the reader thread is ok.

The first map.get() is fubar but according to Patricia we should at
least expect to get back from the get call with only bad data, no other
problems. Likewise, the write should not be expected to create "out of
this air" values. If so, then the second read should be clean.