[concurrency-interest] Stricter read ordering

Oleksandr Otenko oleksandr.otenko at oracle.com
Wed Apr 23 09:16:12 EDT 2014

Your code does lead to inconsistencies.

A permitted reordering is:

this.x=x; can go ahead of this.next=next;, which will lead to the 
reading thread observe written==next, yet x being updated, and not y.


On 16/04/2014 12:25, Tobias Lindaaker wrote:
> [First some background, feel free to jump straight to the code below]
> I believe I have a sufficient understanding of read and write 
> barriers, and the barrier implications of volatile in java. With this 
> knowledge I was eyeing a piece of code I wrote some time ago, that has 
> been working fine all along, and thinking to myself that in theory 
> there is a possibility of inconsistent reads in that code, I've just 
> never seen it actually happening.
> I've tried to read up on how I could change my code to make it 
> guaranteed to be safe, but not found a good solution, in fact some 
> sources seem to imply that my current implementation would be 
> correct[1], but most confirm that my understanding of barriers is 
> correct and that there is a potential inconsistency in my code.
> I thus thought I'd ask in the hopes that someone has greater insight 
> than me and can provide me with a tweak to make my code correct, or 
> assure me in some way that the current code would work.
> I'll present a simplified version of the code I have, and then 
> describe the problem.
>     class VersionedData {
>       // this is the overhead I use to manage consistency
>       private final volatile long written;
>       private final volatile long next;
>       // 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 'synchornized' in this simplification
>         long next = this.next + 1;
>         this.next = next;
>         this.x = x;
>         this.y = y;
>         this.written = next;
>       }
>       public DataCarrier read() {
>         // I allow multiple readers, so this method is not synchronized
>         int x, y;
>         long version;
>         do {
>           version = this.written;
>           x = this.x;
>           y = this.y;
>         } while ( version != this.next );
>         return new DataCarrier( x, y );
>       }
>     }
> The strategy above works quite well in practice, since reads are much 
> more common than writes, so the occasional retry on read is fine an 
> does not cost a lot.
> According to my understanding of read barriers read instructions that 
> are after the barrier in program order are guaranteed not to be moved 
> to before the barrier, so the reading of the data cannot be moved to 
> before the reading of this.written.
> However, as far as I understand, there are no guarantees that read 
> instructions that are before a barrier in program order are not moved 
> to after the barrier, meaning that the reading of the data could be 
> moved to after the reading of this.next, introducing an opportunity 
> for a writer to introduce inconsistent data without the reader 
> detecting this.
> Is there any way I could introduce a fence that guarantees that the 
> data reads will not be moved to after the read of this.next?
> Thank you,
> Tobias
> [1] Doug Lea's Fences API claims that the orderReads() method "Ensures 
> that a read of the given reference prior to the invocation of this 
> method occurs before a subsequent use of the given reference with the 
> effect of reading or writing a field": 
> http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/Fences.html
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20140423/cc388ee4/attachment-0001.html>

More information about the Concurrency-interest mailing list