[concurrency-interest] Stricter read ordering

Tobias Lindaaker thobes at gmail.com
Thu Apr 17 03:37:24 EDT 2014


I'm sending this again, since it didn't end up anywhere the first time, I
apologise if anyone gets this email twice.

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20140417/618cda5a/attachment.html>


More information about the Concurrency-interest mailing list