[concurrency-interest] StampedLock: A possible SequenceLock replacement

Roman Elizarov elizarov at devexperts.com
Mon Jun 25 04:47:00 EDT 2012


I, for one, would welcome a standard "intentional race" annotation. We've recently ran a bunch of our code through an [in-house] dynamic data-race detector (DRD) and on several occasions found benign data races. Interestingly enough, all were read/write races and there is a pattern to all of them. One example: we're tracking the most recent thread which acquired a [custom] lock. This "lastOwner" field is written only while the lock is held, but it is read outside of the lock when a thread fails to acquire the lock for a while. So, there's a write/read race on "lastOwner" field which our DRD had found. However, we know that there was at least one synchronization point (synchronizes-with edge) between the tread that held the lock and the thread that was trying to acquire it. We don't care about a race with threads that wrote this variable after that. We need to know any thread which owned the lock while we were trying to acquire it.

Basically, our code works as long as we have semantics of ~ "regular register" (not necessary an atomic one) that guarantees that a read that races with a number of write(s) would return either the previous value of the register or one of the values that are being written. The only guaranteed we need is that during a racy read it does not get a value "out of thin air". JMM does give us such guarantee.

Sincerely,
Roman Elizarov

-----Original Message-----
From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf Of Boehm, Hans
Sent: Sunday, June 24, 2012 9:57 PM
To: Doug Lea; Concurrency-interest at cs.oswego.edu
Subject: Re: [concurrency-interest] StampedLock: A possible SequenceLock replacement

It seems to me that problems 1 and 2 are essentially orthogonal, and are addressed by separable parts of the solution, right?  Problem 2 essentially requires something like a LoadLoad fence in the implementation of a validate()-like primitive, which, as Doug points out, makes it unimplementable in pure Java, and hard to explain in terms of the Java memory model.  But does it have much to do with the interface change, except that the interface change highlights the weird usage model?

I'm nervous about introducing any construct that relies on intentional, unannotated data races.  Is there already an annotation that says "not volatile, but intentionally accessed through data races"?  If not, is there a reason not to introduce one (aside from the fact that we don't really know what racy accesses mean)?  If we had one, a construct like this might at least not get in the way of data race detectors.

Hans

> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency- 
> interest-bounces at cs.oswego.edu] On Behalf Of Doug Lea
> Sent: Saturday, June 23, 2012 6:18 AM
> To: Concurrency-interest at cs.oswego.edu
> Subject: [concurrency-interest] StampedLock: A possible SequenceLock 
> replacement
> 
> 
> Early experience with jsr166e.SequenceLock suggests that it might be 
> less useful than anticipated. In addition to concerns that correctly 
> writing code using any seqlock-style construct can be challenging, 
> there are two technical issues limiting its range of applicability:
> 
> 1. Under high write rates, sequenced reads continually retry unless 
> readers fall back to getting the lock. But doing so causes other 
> readers to fail needlessly -- the lock is not actually protecting updates.
> This tends to devolve into a very slow emulation of an ordinary lock, 
> and may do so under even relatively low write rates when there are many readers.
> These could be avoided if some form of read-lock were available for 
> use on retry.
> 
> 2. As Hans Boehm and others pointed out (including in a paper at last 
> week's MSPC workshop -- http://safari.ece.cmu.edu/MSPC2012/papers/p12-
> boehm.pdf),
> SequenceLocks either require that all fields read be volatile/final 
> (which is the currently stated usage restriction), or that the 
> internal implementation of sequence validation use some ordering 
> mechanism not expressible using current JMM rules. This second option 
> is possible (although not strictly explainable :-), but only under a 
> slightly different  API to encapsulate seq validation as a method. 
> This could in turn be supported via non-public internal hotspot 
> intrinsics (although some internal specs might need to be strengthened to guarantee to do what they now do).
> 
> Attacking these issues presents an opportunity to also address another 
> continuing RFE -- providing a cheaper, but more restricted, form of 
> read- write lock than our ReentrantReadWriteLock. (This includes one 
> in the upcoming paper by Jun Shirako et al
> https://wiki.rice.edu/confluence/display/HABANERO/Publications)
> Creating one that also allows optimistic reads would further improve 
> support for STM-like constructions.
> 
> One down side of schemes that can support seqlock-like optimistic 
> validated observations, plus read-locks, plus write-locks is that the 
> classes don't fit nicely into our Lock APIs. Most if not all use 
> stamps/cookies/tickets returned from initial lock/start methods and 
> used as arguments in unlock/finish methods. This means that such a 
> lock would not be a drop-in replacement for other Locks. Which is 
> arguably an advantage, since the main usages it supports typically 
> entail very different code than most Lock-based code. In addition to 
> having different methods/signatures, such locks can't support reentrancy or Conditions. Here is one possible form:
> 
> class StampedLock {
>    long lockForWriting(); // return stamp needed for unlock call
>    long lockForReading();
>    long beginObserving(); // block until not write-locked
> 
>    void unlock(long stamp);
>    boolean validate(long stamp); // return false if interfered
> 
>    long tryLockForWriting(); // returns 0 if not available
>    long tryLockForReading();
>    long tryBeginObserving();
> 
>    boolean isLockedForWriting();
>    boolean isLockedForReading();
> 
>    long tryUpgradeFromReadingToWriting(long stamp); // succeed if only 
> 1 reader
>    long downgradeFromWritingToReading(long stamp);  // always succeed 
> }
> 
> And here is a sample usage -- a variant of the example in the 
> SequenceLock javadoc. It illustrates a read-only method with only one 
> optimistic try, falling back to read lock.
> (The try/finally's here are overkill in this particular example 
> because there are no possible exceptions.)
> 
> class Point {
>     private int x, y;
>     private final StampedLock lock = new StampedLock();
> 
>      public int magnitude() { // a read-only method
>          long stamp = lock.beginObserving();
>          try {
>              int currentX = x;
>              int currentY = y;
>          } finally {
>              if (!lock.validate(stamp)) {
>                  stamp = lock.lockForReading();
>                  try {
>                      currentX = x;
>                      currentY = y;
>                  } finally {
>                      lock.unlock(stamp);
>                  }
>              }
>              return currentX * currentX + currentY * currentY;
>          }
>      }
> 
>      public void move(int deltaX, int deltaY) { // a write-locked method
>         long stamp = lock.lockForWriting();
>         try {
>             x += deltaX;
>             y += deltaY;
>         } finally {
>             lock.unlock(stamp);
>         }
>     }
> }
> 
> A secondary issue here is whether StampedLock should even appear in 
> java.util.concurrent as opposed to being made available as an "extra".
> Correctness of optimistic modes relies on strict adherence to: read 
> then validate then use.
> This is not easy to get right especially when using arrays or 
> pointer-based data structures, so you cannot just slap on the 
> mechanics to most existing code. So this would not be the kind of 
> class non-experts would ever use. On the other hand, we'd like to 
> supply a common API for people who use such techniques to produce more user-friendly layered libraries and components.
> This audience might include ourselves for other future j.u.c classes.
> 
> Comments about this possible SequenceLock replacement would be 
> welcome.
> 
> (I'll be out Sunday through Wednesday so might not reply immediately.)
> 
> -Doug
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
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