[concurrency-interest] StampedLock: A possible SequenceLock replacement

Boehm, Hans hans.boehm at hp.com
Sun Jun 24 13:57:10 EDT 2012

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.


> -----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

More information about the Concurrency-interest mailing list