ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jsr166e/StampedLock.java
(Generate patch)

Comparing jsr166/src/jsr166e/StampedLock.java (file contents):
Revision 1.7 by dl, Fri Oct 12 23:11:14 2012 UTC vs.
Revision 1.18 by jsr166, Mon Oct 15 05:26:53 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 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 78 | Line 78 | import java.util.concurrent.TimeUnit;
78   *
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 carry 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   *
# Line 180 | 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 <     * supplementary 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 216 | 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 247 | Line 261 | public class StampedLock implements java
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 296 | 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 320 | 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 525 | 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
# Line 592 | 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 652 | Line 667 | public class StampedLock implements java
667              else if (m == WBIT) {
668                  if (a != m)
669                      break;
670 <                next = state = s + (WBIT + RUNIT);
670 >                state = next = s + (WBIT + RUNIT);
671                  readerPrefSignal();
672                  return next;
673              }
# Line 686 | 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 894 | 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
898 <     * methods use a similar spin strategy: If associated queue
899 <     * appears to be empty, then the thread spin-waits up to SPINS
900 <     * times before enqueing, and then, if the first thread to be
901 <     * enqueued, spins again up to SPINS times before blocking. If,
902 <     * upon wakening it fails to obtain lock, and is still (or
903 <     * becomes) the first waiting thread (which indicates that some
904 <     * other thread barged and obtained lock), it escalates spins (up
905 <     * to MAX_HEAD_SPINS) to reduce the likelihood of continually
906 <     * 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 952 | 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 1010 | 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          }

Diff Legend

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