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.6 by dl, Fri Oct 12 17:35:29 2012 UTC vs.
Revision 1.15 by jsr166, Sun Oct 14 16:42:07 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 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 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 <     * 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 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 244 | 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 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 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
# 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 891 | 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
895 <     * methods use a similar spin strategy: If associated queue
896 <     * appears to be empty, then the thread spin-waits up to SPINS
897 <     * times before enqueing, and then, if the first thread to be
898 <     * enqueued, spins again up to SPINS times before blocking. If,
899 <     * upon wakening it fails to obtain lock, and is still (or
900 <     * becomes) the first waiting thread (which indicates that some
901 <     * other thread barged and obtained lock), it escalates spins (up
902 <     * to MAX_HEAD_SPINS) to reduce the likelihood of continually
903 <     * 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 949 | 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 1007 | 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