Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: markspace <-@.>
Newsgroups: comp.lang.java.programmer
Subject: Re: Volatile happens before question
Date: Thu, 19 Jan 2012 09:40:27 -0800
Organization: A noiseless patient Spider
Lines: 82
Message-ID: <jf9kid$vac$1@dont-email.me>
References: <09848313-2372-4c23-8f52-fa84c612c100@u32g2000yqe.googlegroups.com> <jf4dip$203$1@dont-email.me> <jf5184$r9f$1@dont-email.me> <jf52tt$9b9$1@dont-email.me> <jf5g64$uga$1@dont-email.me> <k0j9x3nt2or.70vxbwtikmz$.dlg@40tude.net> <jf5mm0$ndt$1@dont-email.me> <1pi7kea3zdo0b.1ixhuq3p9ybbu$.dlg@40tude.net> <fkmiu8-6vc.ln1@news.simpsonst.f2s.com> <60dddbf9-3686-4824-a918-64a59faba177@a8g2000vba.googlegroups.com> <s96bklu5m72u.h0brrnp2d8fq$.dlg@40tude.net> <f8b028b6-9f5b-4838-bae3-9a1d1b0716d3@l1g2000vbc.googlegroups.com> <jf7239$k2b$1@dont-email.me> <726da9ce-57f4-4136-b50b-56a032aca196@f1g2000yqi.googlegroups.com> <jf78bd$s4v$1@dont-email.me> <652cb878-fb2f-4361-8f70-61bc493cebf6@r16g2000yqi.googlegroups.com> <jf7crq$p30$1@dont-email.me> <6280ea10-c656-40fa-ba3d-50f24d471978@j15g2000yqb.googlegroups.com> <jf7n1d$ojv$1@dont-email.me> <6b44805b-ff63-41ba-8060-cbd92164f9d6@o9g2000yqa.googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 19 Jan 2012 17:40:30 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="XjIWM99mD7Ijfdu600oVPA"; logging-data="32076"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19kIMfW9KTlsJVNo/Lxn7Qdtra7tpdaOp4="
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:8.0) Gecko/20111105 Thunderbird/8.0
In-Reply-To: <6b44805b-ff63-41ba-8060-cbd92164f9d6@o9g2000yqa.googlegroups.com>
Cancel-Lock: sha1:ktg8FYQP2KiP494G1ihX0pJ0wy8=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:11497

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

> Yes that is correct, it is also possible that it goes:
>
> Thread 1                        Thread 2
> Writer                          Reader
>
> W1: map.put() // write
>                                   R1: writeCounter.get() // happens
> before
>                                   R2: map.get()          // read
>                                   R3: writerCounter.get() // happens
> before
> W2: writeCounter.increment()


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.