[concurrency-interest] Stricter read ordering

Tobias Lindaaker thobes at gmail.com
Wed Apr 23 11:00:58 EDT 2014


If you use the single "version" field in the way you outlined, to serve two purposes, both a special "someone is writing" mark and as a version, then one field would suffice.
The two fields were just a different way of achieving the same guarantees without having a special marker value.

We have contemplated a volatile write to an object that's local to the thread, in order to get the volatile write barrier semantics without writing to a contended location. Would that give sufficient barrier semantics? As Oleksandr Otenko pointed out earlier, there might even be a problem with reordering of writes.

-tobias

On 23 Apr 2014, at 16:40 , Roman Elizarov <elizarov at devexperts.com> wrote:

> What was the reason, then, to use two control variables (written and next)? I don't see how it makes the algorithm "more correct", versus the one that uses just one "version" variable (write it before and after write and read before and after read). Without CAS or additional barriers (that are available in Java 8 only) both approaches are equally incorrect in theory, but both will should equally correct on x86 due to TSO, unless HotSpot does some crazy reordering. 
> 
> As a side note, I can prove that under JMM the read path of this algorithm must have at least one write (volatile write). You cannot make read path read-only under JMM (if you don't have explicit access to barriers). This prove yields a CAS-less construction of this algorithm, but I have not rigorously looked at it, since it is less intuitive and does not look to be not be giving a performance improvement over the CAS version. 
> 
> -----Original Message-----
> From: Tobias Lindaaker [mailto:thobes at gmail.com] 
> Sent: Wednesday, April 23, 2014 6:29 PM
> To: Roman Elizarov
> Cc: concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] Stricter read ordering
> 
> That is one of the approaches we have in our benchmark suite for this, and we also concluded that the CAS in read() would have a too substantial impact on the scalability of the algorithm.
> 
> -tobias
> 
> On 23 Apr 2014, at 16:16 , Roman Elizarov <elizarov at devexperts.com> wrote:
> 
>> The original problem itself is solvable, albeit with a different algorithm. It's funny, that we've discussed the same problem today internally and then I see this thread on concurrency-interest list. 
>> 
>> Let me state the problem first. There is a multi-word state that we have to read and write in non-volatile way (if reads and writes of our state can be made volatile, then solution is trivial and is not of a much interest). We need to implement single-writer multi-reader atomic snapshot of this multi-word state with the primitives described in and under the constraints of the Java Memory Model (think Java 5+). The read does not have to be lock-free. It just needs to detect that snapshot being read is not consistent. In original question author was Ok for reader to spin in case of the read/write conflict, but we actually have a different problem where it is Ok for reader to abandon the read attempt altogether. The key is to detect this conflict or to return an atomic snapshot of the protected state if there is no read/write conflict.
>> 
>> So, here is a solution. It can be proven to work on current version of JMM (starting Java 5 and later) in the JMM's model, by analyzing possible executions and their corresponding SO, SW, and HB relations. It requires just one extra int of state (instead of two), but this int needs to be CAS-ed both on read and on write to ensure proper happens-before edges and to guarantee the consistent read of non-volatile state. The proof of this algorithm's correctness is left as an exercise for the reader. It will not scale, though, if there are many concurrent readers, because of the CAS in read path. 
>> 
>> class VersionedData {
>>   // bit that we'll use to indicate that the state is being written to
>>   private static final int WRITE = 1 << 31;
>>   // we need to CAS version (in practise we'll do it via Unsafe to avoid extra object)
>>   private final AtomicInteger version = new AtomicInteger();
>> 
>>   // this is the data I protect, in reality there is much more protected state
>>   private int x, y;
>> 
>>   public synchronized void update(int x, int y) {
>>       // I guarantee single writers to this method,
>>       // illustrated with 'synchronized' in this simplification
>>       // first use CAS to mark version as being written to
>>       int v0 = version.get(); // can be non-volatile read, but then the following CAS can fail and needs to retry
>>       version.compareAndSet(v0, v0 | WRITE); // always succeeds in single-writer case, ensures proper HB edges for JMM
>>       // then write protected data (non-volatile writes)
>>       this.x = x;
>>       this.y = y;
>>       // then increment version and reset write bit
>>       version.set((v0 + 1) & ~WRITE);
>>   }
>> 
>>   public DataCarrier read() {
>>       // I allow multiple readers, so this method is not synchronized
>>       int x, y;
>>       int v0;
>>       do {
>>           // first read version
>>           v0 = version.get();
>>           if ((v0 & WRITE) != 0)
>>               continue; // immediately abort, because write in progress was detected
>>           // then read protected data
>>           x = this.x;
>>           y = this.y;
>>           // use CAS to check that version is still the same and to ensure proper HB edges for JMM at the same time
>>       } while (!version.compareAndSet(v0, v0));
>>       return new DataCarrier(x, y);
>>   }
>> }
>> 
>> -----Original Message-----
>> From: concurrency-interest-bounces at cs.oswego.edu 
>> [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf Of 
>> Aleksey Shipilev
>> Sent: Wednesday, April 23, 2014 5:36 PM
>> To: Tobias Lindaaker; concurrency-interest at cs.oswego.edu
>> Subject: Re: [concurrency-interest] Stricter read ordering
>> 
>> On 04/23/2014 05:05 PM, Tobias Lindaaker wrote:
>>> Yes, I had a look at StampedLock and Unsafe.loadFence(), and it seems 
>>> to do exactly what I want, and if I was fortunate enough to be able 
>>> to move to Java 8 I would use it. Unfortunately we are still stuck on 
>>> Java 7. We even have customers who are still strongly requesting Java
>>> 6 compatibility.
>> 
>> These constraints make the problem unresolvable.
>> 
>> You might want to look for pre-JDK8 prototype for StampedLock [1]:
>> 
>>    * As noted in Boehm's paper (above), sequence validation (mainly
>>    * method validate()) requires stricter ordering rules than apply
>>    * to normal volatile reads (of "state").  In the absence of (but
>>    * continual hope for) explicit JVM support of intrinsics with
>>    * double-sided reordering prohibition, or corresponding fence
>>    * intrinsics, we for now uncomfortably rely on the fact that the
>>    * Unsafe.getXVolatile intrinsic must have this property
>>    * (syntactic volatile reads do not) for internal purposes anyway,
>>    * even though it is not documented.
>> 
>>   public boolean validate(long stamp) {
>>       return (stamp & SBITS) == (U.getLongVolatile(this, STATE) & SBITS);
>>   }
>> 
>> But if Unsafe.loadFence() is risky since it is not specified (yet) JMM-wise, and so interactions with other volatile ops and fences is just undocumented... then using Unsafe.getXVolatile is double-risky because the behavioral effect of read ordering is *REALLY* implementation-specific, and you if are using it for read ordering, you are five miles past the gateway to Hell already.
>> 
>> Thanks,
>> -Aleksey.
>> 
>> [1]
>> http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/jsr166e/Stampe
>> dLock.java?revision=1.1 
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> 




More information about the Concurrency-interest mailing list