[concurrency-interest] Stricter read ordering

Hans Boehm boehm at acm.org
Wed Apr 23 13:26:28 EDT 2014


The original code is essentially a reimplementation of Linux seqlocks.  The
memory ordering issues are discussed in my MSPC 2012 paper, which you can
find at http://www.hpl.hp.com/techreports/2012/HPL-2012-68.html .

(The C++ writer code in that paper, which should be uninteresting, and is
beside the point, has a bug.  Don't copy!)

Hans


On Wed, Apr 23, 2014 at 8:00 AM, Kaiser, Peter
<Peter.Kaiser at compuware.com>wrote:

>  Ok, I see. Do the reader threads apply any modifications to the state,
> so that they each need an individual copy of the state?
>
> As the state has to be copied anyway to keep the program correctly
> synchronized there would have to be some very good arguments to use
> advanced synchronization mechanisms for a problem like this.
>
> If the state could be provided as an immutable snapshot to the readers
> moving all the logic to the update method would seem to be a good solution
> to me. Also that way reads wouldn’t be able to cause any memory problems by
> creating too much instances of the state object. If it’s not possible to
> store the state in an immutable object, then would simply cloning it in the
> read method be a possibility for you? Of course you would have one more
> instance of the state object, but would that be a problem?
>
>
>
> Best Regards, Peter
>
>
>
> *From:* concurrency-interest-bounces at cs.oswego.edu [mailto:
> concurrency-interest-bounces at cs.oswego.edu] *On Behalf Of *Tobias
> Lindaaker
> *Sent:* Mittwoch, 23. April 2014 16:22
> *To:* concurrency-interest at cs.oswego.edu
> *Subject:* Re: [concurrency-interest] Stricter read ordering
>
>
>
> If the actual code was as simple as the simplified example that would be a
> good idea.
>
> But the actual state is in a ByteBuffer, making this approach impossible
> (or at least extremely inconvenient and impractical).
>
>
>
> synchronizing the read method would have too much of a performance impact
> since it would make readers block one another.
>
>
>
> -tobias
>
>
>
> On 23 Apr 2014, at 16:11 , Kaiser, Peter <Peter.Kaiser at compuware.com>
> wrote:
>
>
>
>   Hi!
>
>
>
> Why not trying something like the following:
>
>
>
> class VersionedData {
>
>   private volatile DataCarrier dataCarrier;
>
>
>
>  public void update( int x, int y ) {
>
>     dataCarrier = new DataCarrier(x, y);
>
>   }
>
>
>
>   public DataCarrier read() {
>
>     return new dataCarrier;
>
>   }
>
> }
>
>
>
> Also making the read-method synchronized would be an easier solution. Or
> would this affect performance too much?
>
>
>
> Best Regards, Peter
>
>
>
>
>
> *From:* concurrency-interest-bounces at cs.oswego.edu [
> mailto:concurrency-interest-bounces at cs.oswego.edu<concurrency-interest-bounces at cs.oswego.edu>
> ] *On Behalf Of *Tobias Lindaaker
> *Sent:* Donnerstag, 17. April 2014 09:37
> *To:* concurrency-interest at cs.oswego.edu
> *Subject:* [concurrency-interest] Stricter read ordering
>
>
>
> 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
>
>
>
> The contents of this e-mail are intended for the named addressee only. It
> contains information that may be confidential. Unless you are the named
> addressee or an authorized designee, you may not copy or use it, or
> disclose it to anyone else. If you received it in error please notify us
> immediately and then destroy it. Compuware Austria GmbH (registration
> number FN 91482h) is a company registered in Vienna whose registered office
> is at 1120 Wien, Austria, Am Euro Platz 2 / Gebäude G.
>
>
>  The contents of this e-mail are intended for the named addressee only. It
> contains information that may be confidential. Unless you are the named
> addressee or an authorized designee, you may not copy or use it, or
> disclose it to anyone else. If you received it in error please notify us
> immediately and then destroy it. Compuware Austria GmbH (registration
> number FN 91482h) is a company registered in Vienna whose registered office
> is at 1120 Wien, Austria, Am Euro Platz 2 / Gebäude G.
>
> _______________________________________________
> 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/85419fa7/attachment-0001.html>


More information about the Concurrency-interest mailing list