ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166e/StampedLock.java

Comparing jsr166/src/jsr166e/StampedLock.java (file contents):
Revision 1.3 by jsr166, Fri Oct 12 16:27:05 2012 UTC vs.
Revision 1.17 by jsr166, Mon Oct 15 04:32:41 2012 UTC

#	Line 11 | Line 11 | import java.util.concurrent.TimeUnit;
11
12		/**
13		* A capability-based lock with three modes for controlling read/write
14	<	* access.  The state of a StampedLock consists of a version and
15	<	* mode. Lock acquisition methods return a stamp that represents and
14	>	* access.  The state of a StampedLock consists of a version and mode.
15	>	* Lock acquisition methods return a stamp that represents and
16		* controls access with respect to a lock state; "try" versions of
17		* these methods may instead return the special value zero to
18		* represent failure to acquire access. Lock release and conversion
#	Line 26 | Line 26 | import java.util.concurrent.TimeUnit;
26		*   in method {@link #unlockWrite} to release the lock. Untimed and
27		*   timed versions of {@code tryWriteLock} are also provided. When
28		*   the lock is held in write mode, no read locks may be obtained,
29	<	*   and all observer validations will fail.  </li>
29	>	*   and all optimistic read validations will fail.  </li>
30		*
31		*  <li><b>Reading.</b> Method {@link #readLock} possibly blocks
32		*   waiting for non-exclusive access, returning a stamp that can be
#	Line 55 | Line 55 | import java.util.concurrent.TimeUnit;
55		* <p>This class also supports methods that conditionally provide
56		* conversions across the three modes. For example, method {@link
57		* #tryConvertToWriteLock} attempts to "upgrade" a mode, returning
58	<	* valid write stamp if (1) already in writing mode (2) in reading
58	>	* a valid write stamp if (1) already in writing mode (2) in reading
59		* mode and there are no other readers or (3) in optimistic mode and
60		* the lock is available. The forms of these methods are designed to
61		* help reduce some of the code bloat that otherwise occurs in
#	Line 76 | Line 76 | import java.util.concurrent.TimeUnit;
76		* into initial unlocked state, so they are not useful for remote
77		* locking.
78		*
79	<	* <p>The scheduling policy of StampedLock does not consistently prefer
80	<	* readers over writers or vice versa.
79	>	* <p>The scheduling policy of StampedLock does not consistently
80	>	* prefer readers over writers or vice versa.  A zero return from any
81	>	* "try" method for acquiring or converting locks does not carry any
82	>	* information about the state of the lock; a subsequent invocation
83	>	* may succeed.
84		*
85		* <p><b>Sample Usage.</b> The following illustrates some usage idioms
86		* in a class that maintains simple two-dimensional points. The sample
#	Line 87 | Line 90 | import java.util.concurrent.TimeUnit;
90		*
91		*  <pre>{@code
92		* class Point {
93	<	*   private volatile double x, y;
93	>	*   private double x, y;
94		*   private final StampedLock sl = new StampedLock();
95		*
96		*   void move(double deltaX, double deltaY) { // an exclusively locked method
#	Line 119 | Line 122 | import java.util.concurrent.TimeUnit;
122		*   }
123		*
124		*   double distanceFromOriginV2() { // combines code paths
125	<	*     for (long stamp = sl.optimisticRead(); ; stamp = sl.readLock()) {
125	>	*     for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) {
126		*       double currentX, currentY;
127		*       try {
128		*         currentX = x;
#	Line 177 | Line 180 | public class StampedLock implements java
180		* read-locked.  The read count is ignored when validating
181		* "optimistic" seqlock-reader-style stamps.  Because we must use
182		* a small finite number of bits (currently 7) for readers, a
183	<	* supplementatry reader overflow word is used when then number of
183	>	* supplementary reader overflow word is used when the number of
184		* readers exceeds the count field. We do this by treating the max
185		* reader count value (RBITS) as a spinlock protecting overflow
186		* updates.
#	Line 213 | Line 216 | public class StampedLock implements java
216		* in-progress spins/signals, and others do not account for
217		* cancellations.
218		*
219	+	* Controlled, randomized spinning is used in the two await
220	+	* methods to reduce (increasingly expensive) context switching
221	+	* while also avoiding sustained memory thrashing among many
222	+	* threads.  Both await methods use a similar spin strategy: If
223	+	* the associated queue appears to be empty, then the thread
224	+	* spin-waits up to SPINS times (where each iteration decreases
225	+	* spin count with 50% probablility) before enqueing, and then, if
226	+	* it is the first thread to be enqueued, spins again up to SPINS
227	+	* times before blocking. If, upon wakening it fails to obtain
228	+	* lock, and is still (or becomes) the first waiting thread (which
229	+	* indicates that some other thread barged and obtained lock), it
230	+	* escalates spins (up to MAX_HEAD_SPINS) to reduce the likelihood
231	+	* of continually losing to barging threads.
232	+	*
233		* As noted in Boehm's paper (above), sequence validation (mainly
234		* method validate()) requires stricter ordering rules than apply
235		* to normal volatile reads (of "state").  In the absence of (but
#	Line 235 | Line 252 | public class StampedLock implements java
252		private static final int NCPU = Runtime.getRuntime().availableProcessors();
253
254		/** Maximum number of retries before blocking on acquisition */
255	<	private static final int SPINS = NCPU > 1 ? 1 << 6 : 1;
255	>	private static final int SPINS = (NCPU > 1) ? 1 << 6 : 1;
256
257	<	/** Maximum number of retries before re-blocking on write lock */
258	<	private static final int MAX_HEAD_SPINS = NCPU > 1 ? 1 << 12 : 1;
257	>	/** Maximum number of retries before re-blocking */
258	>	private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 1;
259
260		/** The period for yielding when waiting for overflow spinlock */
261		private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1
262
263		/** The number of bits to use for reader count before overflowing */
264	<	private static final int  LG_READERS = 7;
264	>	private static final int LG_READERS = 7;
265
266		// Values for lock state and stamp operations
267		private static final long RUNIT = 1L;
#	Line 293 | Line 310 | public class StampedLock implements java
310		private transient int readerOverflow;
311
312		/**
313	<	* Creates a new lock initially in unlocked state.
313	>	* Creates a new lock, initially in unlocked state.
314		*/
315		public StampedLock() {
316		state = ORIGIN;
#	Line 303 | Line 320 | public class StampedLock implements java
320		* Exclusively acquires the lock, blocking if necessary
321		* until available.
322		*
323	<	* @return a stamp that can be used to unlock or convert mode.
323	>	* @return a stamp that can be used to unlock or convert mode
324		*/
325		public long writeLock() {
326		long s, next;
#	Line 317 | Line 334 | public class StampedLock implements java
334		* Exclusively acquires the lock if it is immediately available.
335		*
336		* @return a stamp that can be used to unlock or convert mode,
337	<	* or zero if the lock is not available.
337	>	* or zero if the lock is not available
338		*/
339		public long tryWriteLock() {
340		long s, next;
#	Line 329 | Line 346 | public class StampedLock implements java
346
347		/**
348		* Exclusively acquires the lock if it is available within the
349	<	* given time and the current thread has not been interrupted
349	>	* given time and the current thread has not been interrupted.
350		*
351		* @return a stamp that can be used to unlock or convert mode,
352	<	* or zero if the lock is not available.
352	>	* or zero if the lock is not available
353		* @throws InterruptedException if the current thread is interrupted
354	<	* before acquiring the lock.
354	>	* before acquiring the lock
355		*/
356		public long tryWriteLock(long time, TimeUnit unit)
357		throws InterruptedException {
358	<	long nanos =  unit.toNanos(time);
358	>	long nanos = unit.toNanos(time);
359		if (!Thread.interrupted()) {
360		long s, next, deadline;
361		if (((s = state) & ABITS) == 0L &&
#	Line 358 | Line 375 | public class StampedLock implements java
375		* Exclusively acquires the lock, blocking if necessary
376		* until available or the current thread is interrupted.
377		*
378	<	* @return a stamp that can be used to unlock or convert mode.
378	>	* @return a stamp that can be used to unlock or convert mode
379		* @throws InterruptedException if the current thread is interrupted
380	<	* before acquiring the lock.
380	>	* before acquiring the lock
381		*/
382		public long writeLockInterruptibly() throws InterruptedException {
383		if (!Thread.interrupted()) {
#	Line 378 | Line 395 | public class StampedLock implements java
395		* Non-exclusively acquires the lock, blocking if necessary
396		* until available.
397		*
398	<	* @return a stamp that can be used to unlock or convert mode.
398	>	* @return a stamp that can be used to unlock or convert mode
399		*/
400		public long readLock() {
401		for (;;) {
#	Line 401 | Line 418 | public class StampedLock implements java
418		* Non-exclusively acquires the lock if it is immediately available.
419		*
420		* @return a stamp that can be used to unlock or convert mode,
421	<	* or zero if the lock is not available.
421	>	* or zero if the lock is not available
422		*/
423		public long tryReadLock() {
424		for (;;) {
#	Line 419 | Line 436 | public class StampedLock implements java
436
437		/**
438		* Non-exclusively acquires the lock if it is available within the
439	<	* given time and the current thread has not been interrupted
439	>	* given time and the current thread has not been interrupted.
440		*
441		* @return a stamp that can be used to unlock or convert mode,
442	<	* or zero if the lock is not available.
442	>	* or zero if the lock is not available
443		* @throws InterruptedException if the current thread is interrupted
444	<	* before acquiring the lock.
444	>	* before acquiring the lock
445		*/
446		public long tryReadLock(long time, TimeUnit unit)
447		throws InterruptedException {
#	Line 457 | Line 474 | public class StampedLock implements java
474		* Non-exclusively acquires the lock, blocking if necessary
475		* until available or the current thread is interrupted.
476		*
477	<	* @return a stamp that can be used to unlock or convert mode.
477	>	* @return a stamp that can be used to unlock or convert mode
478		* @throws InterruptedException if the current thread is interrupted
479	<	* before acquiring the lock.
479	>	* before acquiring the lock
480		*/
481		public long readLockInterruptibly() throws InterruptedException {
482		if (!Thread.interrupted()) {
#	Line 512 | Line 529 | public class StampedLock implements java
529		*
530		* @param stamp a stamp returned by a write-lock operation
531		* @throws IllegalMonitorStateException if the stamp does
532	<	* not match the current state of this lock.
532	>	* not match the current state of this lock
533		*/
534		public void unlockWrite(long stamp) {
535		if (state != stamp || (stamp & WBIT) == 0L)
#	Line 522 | Line 539 | public class StampedLock implements java
539		}
540
541		/**
542	<	* If the lock state matches the given stamp, releases
542	>	* If the lock state matches the given stamp, releases the
543		* non-exclusive lock.
544		*
545		* @param stamp a stamp returned by a read-lock operation
546		* @throws IllegalMonitorStateException if the stamp does
547	<	* not match the current state of this lock.
547	>	* not match the current state of this lock
548		*/
549		public void unlockRead(long stamp) {
550		long s, m;
#	Line 557 | Line 574 | public class StampedLock implements java
574		*
575		* @param stamp a stamp returned by a lock operation
576		* @throws IllegalMonitorStateException if the stamp does
577	<	* not match the current state of this lock.
577	>	* not match the current state of this lock
578		*/
579		public void unlock(long stamp) {
580		long a = stamp & ABITS, m, s;
#	Line 589 | Line 606 | public class StampedLock implements java
606		/**
607		* If the lock state matches the given stamp then performs one of
608		* the following actions. If the stamp represents holding a write
609	<	* lock, returns it. Or, if a read lock, if the write lock is
610	<	* available, releases the read and returns a write stamp. Or, if
611	<	* an optimistic read, returns a write stamp only if immediately
612	<	* available. This method returns zero in all other cases.
609	>	* lock, returns it.  Or, if a read lock, if the write lock is
610	>	* available, releases the read lock and returns a write stamp.
611	>	* Or, if an optimistic read, returns a write stamp only if
612	>	* immediately available. This method returns zero in all other
613	>	* cases.
614		*
615		* @param stamp a stamp
616		* @return a valid write stamp, or zero on failure
#	Line 683 | Line 701 | public class StampedLock implements java
701		else if (m == WBIT) {
702		if (a != m)
703		break;
704	<	next = state = (s += WBIT) == 0L ? ORIGIN : s;
704	>	state = next = (s += WBIT) == 0L ? ORIGIN : s;
705		readerPrefSignal();
706		return next;
707		}
#	Line 707 | Line 725 | public class StampedLock implements java
725		* stamp value. This method may be useful for recovery after
726		* errors.
727		*
728	<	* @return true if the lock was held, else false.
728	>	* @return true if the lock was held, else false
729		*/
730		public boolean tryUnlockWrite() {
731		long s;
#	Line 724 | Line 742 | public class StampedLock implements java
742		* requiring a stamp value. This method may be useful for recovery
743		* after errors.
744		*
745	<	* @return true if the read lock was held, else false.
745	>	* @return true if the read lock was held, else false
746		*/
747		public boolean tryUnlockRead() {
748		long s, m;
#	Line 773 | Line 791 | public class StampedLock implements java
791		* Tries to increment readerOverflow by first setting state
792		* access bits value to RBITS, indicating hold of spinlock,
793		* then updating, then releasing.
794	+	*
795		* @param stamp, assumed that (stamp & ABITS) >= RFULL
796		* @return new stamp on success, else zero
797		*/
#	Line 792 | Line 811 | public class StampedLock implements java
811
812		/**
813		* Tries to decrement readerOverflow.
814	+	*
815		* @param stamp, assumed that (stamp & ABITS) >= RFULL
816		* @return new stamp on success, else zero
817		*/
#	Line 889 | Line 909 | public class StampedLock implements java
909		/**
910		* RNG for local spins. The first call from await{Read,Write}
911		* produces a thread-local value. Unless zero, subsequent calls
912	<	* use an xorShift to further reduce memory traffic.  Both await
893	<	* methods use a similar spin strategy: If associated queue
894	<	* appears to be empty, then the thread spin-waits up to SPINS
895	<	* times before enqueing, and then, if the first thread to be
896	<	* enqueued, spins again up to SPINS times before blocking. If,
897	<	* upon wakening it fails to obtain lock, and is still (or
898	<	* becomes) the first waiting thread (which indicates that some
899	<	* other thread barged and obtained lock), it escalates spins (up
900	<	* to MAX_HEAD_SPINS) to reduce the likelihood of continually
901	<	* losing to barging threads.
912	>	* use an xorShift to further reduce memory traffic.
913		*/
914		private static int nextRandom(int r) {
915		if (r == 0)
#	Line 911 | Line 922 | public class StampedLock implements java
922
923		/**
924		* Possibly spins trying to obtain write lock, then enqueues and
925	<	* blocks while not head of write queue or cannot aquire lock,
925	>	* blocks while not head of write queue or cannot acquire lock,
926		* possibly spinning when at head; cancelling on timeout or
927		* interrupt.
928		*
929		* @param interruptible true if should check interrupts and if so
930		* return INTERRUPTED
931		* @param deadline if nonzero, the System.nanoTime value to timeout
932	<	* at (and return zero).
932	>	* at (and return zero)
933		*/
934		private long awaitWrite(boolean interruptible, long deadline) {
935		WNode node = null;
#	Line 947 | Line 958 | public class StampedLock implements java
958		p.next = node;
959		for (int headSpins = SPINS;;) {
960		WNode np; int ps;
961	<	if ((np = node.prev) != p && np != null)
962	<	(p = np).next = node; // stale
961	>	if ((np = node.prev) != p && np != null &&
962	>	(p = np).next != node)
963	>	p.next = node; // stale
964		if (p == whead) {
965		for (int k = headSpins;;) {
966		if (((s = state) & ABITS) == 0L) {
#	Line 1005 | Line 1017 | public class StampedLock implements java
1017		WNode predNext = pred.next;
1018		node.status = CANCELLED;
1019		if (predNext != null) {
1020	<	Thread w = null;
1020	>	Thread w;
1021		WNode succ = node.next;
1022	<	while (succ != null && succ.status == CANCELLED)
1023	<	succ = succ.next;
1024	<	if (succ != null)
1025	<	w = succ.thread;
1026	<	else if (node == wtail)
1027	<	U.compareAndSwapObject(this, WTAIL, node, pred);
1022	>	if (succ == null || succ.status == CANCELLED) {
1023	>	succ = null;
1024	>	for (WNode t = wtail; t != null && t != node; t = t.prev)
1025	>	if (t.status <= 0)
1026	>	succ = t;
1027	>	if (succ == null && node == wtail)
1028	>	U.compareAndSwapObject(this, WTAIL, node, pred);
1029	>	}
1030		U.compareAndSwapObject(pred, WNEXT, predNext, succ);
1031	<	if (w != null)
1031	>	if (succ != null && (w = succ.thread) != null)
1032		U.unpark(w);
1033		}
1034		}
#	Line 1022 | Line 1036 | public class StampedLock implements java
1036		return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1037		}
1038
1039	<	/*
1039	>	/**
1040		* Waits for read lock or timeout or interrupt. The form of
1041		* awaitRead differs from awaitWrite mainly because it must
1042		* restart (with a new wait node) if the thread was unqueued and
#	Line 1101 | Line 1115 | public class StampedLock implements java
1115		/**
1116		* If node non-null, forces cancel status and unsplices from queue
1117		* if possible, by traversing entire queue looking for cancelled
1118	<	* nodes, cleaning out all at head, but stopping upon first
1105	<	* encounter otherwise.
1118	>	* nodes.
1119		*/
1120		private long cancelReader(RNode node, boolean interrupted) {
1121		Thread w;
#	Line 1117 | Line 1130 | public class StampedLock implements java
1130		}
1131		else {
1132		U.compareAndSwapObject(pred, RNEXT, p, q);
1133	<	break;
1133	>	p = pred.next;
1134		}
1135		}
1136		else {

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines