[concurrency-interest] StampedLock: A possible SequenceLock replacement

Doug Lea dl at cs.oswego.edu
Sat Jun 23 09:17:53 EDT 2012


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


More information about the Concurrency-interest mailing list