This class also supports methods that conditionally provide * conversions across the three modes. For example, method {@link * #tryConvertToWriteLock} attempts to "upgrade" a mode, returning - * valid write stamp if (1) already in writing mode (2) in reading + * a valid write stamp if (1) already in writing mode (2) in reading * mode and there are no other readers or (3) in optimistic mode and * the lock is available. The forms of these methods are designed to * help reduce some of the code bloat that otherwise occurs in @@ -76,8 +76,11 @@ import java.util.concurrent.TimeUnit; * into initial unlocked state, so they are not useful for remote * locking. * - *
The scheduling policy of StampedLock does not consistently prefer - * readers over writers or vice versa. + *
The scheduling policy of StampedLock does not consistently + * prefer readers over writers or vice versa. A zero return from any + * "try" method for acquiring or converting locks does not carry any + * information about the state of the lock; a subsequent invocation + * may succeed. * *
Sample Usage. The following illustrates some usage idioms * in a class that maintains simple two-dimensional points. The sample @@ -119,7 +122,7 @@ import java.util.concurrent.TimeUnit; * } * * double distanceFromOriginV2() { // combines code paths - * for (long stamp = sl.optimisticRead(); ; stamp = sl.readLock()) { + * for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) { * double currentX, currentY; * try { * currentX = x; @@ -177,7 +180,7 @@ public class StampedLock implements java * read-locked. The read count is ignored when validating * "optimistic" seqlock-reader-style stamps. Because we must use * a small finite number of bits (currently 7) for readers, a - * supplementary reader overflow word is used when then number of + * supplementary reader overflow word is used when the number of * readers exceeds the count field. We do this by treating the max * reader count value (RBITS) as a spinlock protecting overflow * updates. @@ -213,6 +216,20 @@ public class StampedLock implements java * in-progress spins/signals, and others do not account for * cancellations. * + * Controlled, randomized spinning is used in the two await + * methods to reduce (increasingly expensive) context switching + * while also avoiding sustained memory thrashing among many + * threads. Both await methods use a similar spin strategy: If + * the associated queue appears to be empty, then the thread + * spin-waits up to SPINS times (where each iteration decreases + * spin count with 50% probablility) before enqueing, and then, if + * it is the first thread to be enqueued, spins again up to SPINS + * times before blocking. If, upon wakening it fails to obtain + * lock, and is still (or becomes) the first waiting thread (which + * indicates that some other thread barged and obtained lock), it + * escalates spins (up to MAX_HEAD_SPINS) to reduce the likelihood + * of continually losing to barging threads. + * * As noted in Boehm's paper (above), sequence validation (mainly * method validate()) requires stricter ordering rules than apply * to normal volatile reads (of "state"). In the absence of (but @@ -244,7 +261,7 @@ public class StampedLock implements java private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1 /** The number of bits to use for reader count before overflowing */ - private static final int LG_READERS = 7; + private static final int LG_READERS = 7; // Values for lock state and stamp operations private static final long RUNIT = 1L; @@ -293,7 +310,7 @@ public class StampedLock implements java private transient int readerOverflow; /** - * Creates a new lock initially in unlocked state. + * Creates a new lock, initially in unlocked state. */ public StampedLock() { state = ORIGIN; @@ -317,7 +334,7 @@ public class StampedLock implements java * Exclusively acquires the lock if it is immediately available. * * @return a stamp that can be used to unlock or convert mode, - * or zero if the lock is not available. + * or zero if the lock is not available */ public long tryWriteLock() { long s, next; @@ -522,7 +539,7 @@ public class StampedLock implements java } /** - * If the lock state matches the given stamp, releases + * If the lock state matches the given stamp, releases the * non-exclusive lock. * * @param stamp a stamp returned by a read-lock operation @@ -589,10 +606,11 @@ public class StampedLock implements java /** * If the lock state matches the given stamp then performs one of * the following actions. If the stamp represents holding a write - * lock, returns it. Or, if a read lock, if the write lock is - * available, releases the read and returns a write stamp. Or, if - * an optimistic read, returns a write stamp only if immediately - * available. This method returns zero in all other cases. + * lock, returns it. Or, if a read lock, if the write lock is + * available, releases the read lock and returns a write stamp. + * Or, if an optimistic read, returns a write stamp only if + * immediately available. This method returns zero in all other + * cases. * * @param stamp a stamp * @return a valid write stamp, or zero on failure @@ -649,7 +667,7 @@ public class StampedLock implements java else if (m == WBIT) { if (a != m) break; - next = state = s + (WBIT + RUNIT); + state = next = s + (WBIT + RUNIT); readerPrefSignal(); return next; } @@ -683,7 +701,7 @@ public class StampedLock implements java else if (m == WBIT) { if (a != m) break; - next = state = (s += WBIT) == 0L ? ORIGIN : s; + state = next = (s += WBIT) == 0L ? ORIGIN : s; readerPrefSignal(); return next; } @@ -891,16 +909,7 @@ public class StampedLock implements java /** * RNG for local spins. The first call from await{Read,Write} * produces a thread-local value. Unless zero, subsequent calls - * use an xorShift to further reduce memory traffic. Both await - * methods use a similar spin strategy: If associated queue - * appears to be empty, then the thread spin-waits up to SPINS - * times before enqueing, and then, if the first thread to be - * enqueued, spins again up to SPINS times before blocking. If, - * upon wakening it fails to obtain lock, and is still (or - * becomes) the first waiting thread (which indicates that some - * other thread barged and obtained lock), it escalates spins (up - * to MAX_HEAD_SPINS) to reduce the likelihood of continually - * losing to barging threads. + * use an xorShift to further reduce memory traffic. */ private static int nextRandom(int r) { if (r == 0) @@ -949,8 +958,9 @@ public class StampedLock implements java p.next = node; for (int headSpins = SPINS;;) { WNode np; int ps; - if ((np = node.prev) != p && np != null) - (p = np).next = node; // stale + if ((np = node.prev) != p && np != null && + (p = np).next != node) + p.next = node; // stale if (p == whead) { for (int k = headSpins;;) { if (((s = state) & ABITS) == 0L) { @@ -1007,16 +1017,18 @@ public class StampedLock implements java WNode predNext = pred.next; node.status = CANCELLED; if (predNext != null) { - Thread w = null; + Thread w; WNode succ = node.next; - while (succ != null && succ.status == CANCELLED) - succ = succ.next; - if (succ != null) - w = succ.thread; - else if (node == wtail) - U.compareAndSwapObject(this, WTAIL, node, pred); + if (succ == null || succ.status == CANCELLED) { + succ = null; + for (WNode t = wtail; t != null && t != node; t = t.prev) + if (t.status <= 0) + succ = t; + if (succ == null && node == wtail) + U.compareAndSwapObject(this, WTAIL, node, pred); + } U.compareAndSwapObject(pred, WNEXT, predNext, succ); - if (w != null) + if (succ != null && (w = succ.thread) != null) U.unpark(w); } }