--- jsr166/src/jsr166e/StampedLock.java 2012/10/12 16:27:05 1.3 +++ jsr166/src/jsr166e/StampedLock.java 2012/10/14 16:42:07 1.15 @@ -11,8 +11,8 @@ import java.util.concurrent.TimeUnit; /** * A capability-based lock with three modes for controlling read/write - * access. The state of a StampedLock consists of a version and - * mode. Lock acquisition methods return a stamp that represents and + * access. The state of a StampedLock consists of a version and mode. + * Lock acquisition methods return a stamp that represents and * controls access with respect to a lock state; "try" versions of * these methods may instead return the special value zero to * represent failure to acquire access. Lock release and conversion @@ -26,7 +26,7 @@ import java.util.concurrent.TimeUnit; * in method {@link #unlockWrite} to release the lock. Untimed and * timed versions of {@code tryWriteLock} are also provided. When * the lock is held in write mode, no read locks may be obtained, - * and all observer validations will fail. + * and all optimistic read validations will fail. * *
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 @@ -87,7 +90,7 @@ import java.util.concurrent.TimeUnit; * *
{@code * class Point { - * private volatile double x, y; + * private double x, y; * private final StampedLock sl = new StampedLock(); * * void move(double deltaX, double deltaY) { // an exclusively locked method @@ -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 - * supplementatry 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 @@ -235,16 +252,16 @@ public class StampedLock implements java private static final int NCPU = Runtime.getRuntime().availableProcessors(); /** Maximum number of retries before blocking on acquisition */ - private static final int SPINS = NCPU > 1 ? 1 << 6 : 1; + private static final int SPINS = (NCPU > 1) ? 1 << 6 : 1; - /** Maximum number of retries before re-blocking on write lock */ - private static final int MAX_HEAD_SPINS = NCPU > 1 ? 1 << 12 : 1; + /** Maximum number of retries before re-blocking */ + private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 1; /** The period for yielding when waiting for overflow spinlock */ 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; @@ -303,7 +320,7 @@ public class StampedLock implements java * Exclusively acquires the lock, blocking if necessary * until available. * - * @return a stamp that can be used to unlock or convert mode. + * @return a stamp that can be used to unlock or convert mode */ public long writeLock() { long s, next; @@ -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; @@ -329,16 +346,16 @@ public class StampedLock implements java /** * Exclusively acquires the lock if it is available within the - * given time and the current thread has not been interrupted + * given time and the current thread has not been interrupted. * * @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 * @throws InterruptedException if the current thread is interrupted - * before acquiring the lock. + * before acquiring the lock */ public long tryWriteLock(long time, TimeUnit unit) throws InterruptedException { - long nanos = unit.toNanos(time); + long nanos = unit.toNanos(time); if (!Thread.interrupted()) { long s, next, deadline; if (((s = state) & ABITS) == 0L && @@ -358,9 +375,9 @@ public class StampedLock implements java * Exclusively acquires the lock, blocking if necessary * until available or the current thread is interrupted. * - * @return a stamp that can be used to unlock or convert mode. + * @return a stamp that can be used to unlock or convert mode * @throws InterruptedException if the current thread is interrupted - * before acquiring the lock. + * before acquiring the lock */ public long writeLockInterruptibly() throws InterruptedException { if (!Thread.interrupted()) { @@ -378,7 +395,7 @@ public class StampedLock implements java * Non-exclusively acquires the lock, blocking if necessary * until available. * - * @return a stamp that can be used to unlock or convert mode. + * @return a stamp that can be used to unlock or convert mode */ public long readLock() { for (;;) { @@ -401,7 +418,7 @@ public class StampedLock implements java * Non-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 tryReadLock() { for (;;) { @@ -419,12 +436,12 @@ public class StampedLock implements java /** * Non-exclusively acquires the lock if it is available within the - * given time and the current thread has not been interrupted + * given time and the current thread has not been interrupted. * * @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 * @throws InterruptedException if the current thread is interrupted - * before acquiring the lock. + * before acquiring the lock */ public long tryReadLock(long time, TimeUnit unit) throws InterruptedException { @@ -457,9 +474,9 @@ public class StampedLock implements java * Non-exclusively acquires the lock, blocking if necessary * until available or the current thread is interrupted. * - * @return a stamp that can be used to unlock or convert mode. + * @return a stamp that can be used to unlock or convert mode * @throws InterruptedException if the current thread is interrupted - * before acquiring the lock. + * before acquiring the lock */ public long readLockInterruptibly() throws InterruptedException { if (!Thread.interrupted()) { @@ -512,7 +529,7 @@ public class StampedLock implements java * * @param stamp a stamp returned by a write-lock operation * @throws IllegalMonitorStateException if the stamp does - * not match the current state of this lock. + * not match the current state of this lock */ public void unlockWrite(long stamp) { if (state != stamp || (stamp & WBIT) == 0L) @@ -522,12 +539,12 @@ 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 * @throws IllegalMonitorStateException if the stamp does - * not match the current state of this lock. + * not match the current state of this lock */ public void unlockRead(long stamp) { long s, m; @@ -557,7 +574,7 @@ public class StampedLock implements java * * @param stamp a stamp returned by a lock operation * @throws IllegalMonitorStateException if the stamp does - * not match the current state of this lock. + * not match the current state of this lock */ public void unlock(long stamp) { long a = stamp & ABITS, m, s; @@ -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 @@ -707,7 +725,7 @@ public class StampedLock implements java * stamp value. This method may be useful for recovery after * errors. * - * @return true if the lock was held, else false. + * @return true if the lock was held, else false */ public boolean tryUnlockWrite() { long s; @@ -724,7 +742,7 @@ public class StampedLock implements java * requiring a stamp value. This method may be useful for recovery * after errors. * - * @return true if the read lock was held, else false. + * @return true if the read lock was held, else false */ public boolean tryUnlockRead() { long s, m; @@ -773,6 +791,7 @@ public class StampedLock implements java * Tries to increment readerOverflow by first setting state * access bits value to RBITS, indicating hold of spinlock, * then updating, then releasing. + * * @param stamp, assumed that (stamp & ABITS) >= RFULL * @return new stamp on success, else zero */ @@ -792,6 +811,7 @@ public class StampedLock implements java /** * Tries to decrement readerOverflow. + * * @param stamp, assumed that (stamp & ABITS) >= RFULL * @return new stamp on success, else zero */ @@ -889,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) @@ -911,14 +922,14 @@ public class StampedLock implements java /** * Possibly spins trying to obtain write lock, then enqueues and - * blocks while not head of write queue or cannot aquire lock, + * blocks while not head of write queue or cannot acquire lock, * possibly spinning when at head; cancelling on timeout or * interrupt. * * @param interruptible true if should check interrupts and if so * return INTERRUPTED * @param deadline if nonzero, the System.nanoTime value to timeout - * at (and return zero). + * at (and return zero) */ private long awaitWrite(boolean interruptible, long deadline) { WNode node = null; @@ -947,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) { @@ -1005,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); } } @@ -1022,7 +1036,7 @@ public class StampedLock implements java return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L; } - /* + /** * Waits for read lock or timeout or interrupt. The form of * awaitRead differs from awaitWrite mainly because it must * restart (with a new wait node) if the thread was unqueued and @@ -1101,8 +1115,7 @@ public class StampedLock implements java /** * If node non-null, forces cancel status and unsplices from queue * if possible, by traversing entire queue looking for cancelled - * nodes, cleaning out all at head, but stopping upon first - * encounter otherwise. + * nodes. */ private long cancelReader(RNode node, boolean interrupted) { Thread w; @@ -1117,7 +1130,7 @@ public class StampedLock implements java } else { U.compareAndSwapObject(pred, RNEXT, p, q); - break; + p = pred.next; } } else {