--- jsr166/src/jsr166e/StampedLock.java 2012/10/12 16:53:10 1.5 +++ jsr166/src/jsr166e/StampedLock.java 2012/10/13 22:10:38 1.10 @@ -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; @@ -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 @@ -237,7 +254,7 @@ public class StampedLock implements java /** Maximum number of retries before blocking on acquisition */ private static final int SPINS = (NCPU > 1) ? 1 << 6 : 1; - /** Maximum number of retries before re-blocking on write lock */ + /** 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 */ @@ -891,16 +908,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 +957,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 +1016,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); } } @@ -1103,8 +1114,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; @@ -1119,7 +1129,7 @@ public class StampedLock implements java } else { U.compareAndSwapObject(pred, RNEXT, p, q); - break; + p = pred.next; } } else {