reentrantreadwritelock.java

JAVA的一些源码 JAVA2 STANDARD EDITION DEVELOPMENT KIT 5.0

/*
 * @(#)ReentrantReadWriteLock.java	1.7 04/07/14
 *
 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

package java.util.concurrent.locks;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.*;

/**
 * An implementation of {@link ReadWriteLock} supporting similar
 * semantics to {@link ReentrantLock}.
 * <p>This class has the following properties:
 *
 * <ul>
 * <li><b>Acquisition order</b>
 *
 * <p> This class does not impose a reader or writer preference
 * ordering for lock access.  However, it does support an optional
 * <em>fairness</em> policy.  When constructed as fair, threads
 * contend for entry using an approximately arrival-order policy. When
 * the write lock is released either the longest-waiting single writer
 * will be assigned the write lock, or if there is a reader waiting
 * longer than any writer, the set of readers will be assigned the
 * read lock.  When constructed as non-fair, the order of entry to the
 * lock need not be in arrival order.  In either case, if readers are
 * active and a writer enters the lock then no subsequent readers will
 * be granted the read lock until after that writer has acquired and
 * released the write lock.
 * 
 * <li><b>Reentrancy</b>
 * <p>This lock allows both readers and writers to reacquire read or
 * write locks in the style of a {@link ReentrantLock}. Readers are not
 * allowed until all write locks held by the writing thread have been
 * released.  
 * <p>Additionally, a writer can acquire the read lock - but not vice-versa.
 * Among other applications, reentrancy can be useful when
 * write locks are held during calls or callbacks to methods that
 * perform reads under read locks. 
 * If a reader tries to acquire the write lock it will never succeed.
 * 
 * <li><b>Lock downgrading</b>
 * <p>Reentrancy also allows downgrading from the write lock to a read lock,
 * by acquiring the write lock, then the read lock and then releasing the
 * write lock. However, upgrading from a read lock to the write lock is
 * <b>not</b> possible.
 *
 * <li><b>Interruption of lock acquisition</b>
 * <p>The read lock and write lock both support interruption during lock
 * acquisition.
 *
 * <li><b>{@link Condition} support</b>
 * <p>The write lock provides a {@link Condition} implementation that
 * behaves in the same way, with respect to the write lock, as the 
 * {@link Condition} implementation provided by
 * {@link ReentrantLock#newCondition} does for {@link ReentrantLock}.
 * This {@link Condition} can, of course, only be used with the write lock.
 * <p>The read lock does not support a {@link Condition} and
 * <tt>readLock().newCondition()</tt> throws 
 * <tt>UnsupportedOperationException</tt>.
 *
 * <li><b>Instrumentation</b>
 * <P> This class supports methods to determine whether locks
 * are held or contended. These methods are designed for monitoring
 * system state, not for synchronization control.
 * </ul>
 *
 * <p> Serialization of this class behaves in the same way as built-in
 * locks: a deserialized lock is in the unlocked state, regardless of
 * its state when serialized.
 *
 * <p><b>Sample usages</b>. Here is a code sketch showing how to exploit
 * reentrancy to perform lock downgrading after updating a cache (exception
 * handling is elided for simplicity):
 * <pre>
 * class CachedData {
 *   Object data;
 *   volatile boolean cacheValid;
 *   ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
 *
 *   void processCachedData() {
 *     rwl.readLock().lock();
 *     if (!cacheValid) {
 *        // upgrade lock manually
 *        rwl.readLock().unlock();   // must unlock first to obtain writelock
 *        rwl.writeLock().lock();
 *        if (!cacheValid) { // recheck
 *          data = ...
 *          cacheValid = true;
 *        }
 *        // downgrade lock
 *        rwl.readLock().lock();  // reacquire read without giving up write lock
 *        rwl.writeLock().unlock(); // unlock write, still hold read
 *     }
 *
 *     use(data);
 *     rwl.readLock().unlock();
 *   }
 * }
 * </pre>
 *
 * ReentrantReadWriteLocks can be used to improve concurrency in some
 * uses of some kinds of Collections. This is typically worthwhile
 * only when the collections are expected to be large, accessed by
 * more reader threads than writer threads, and entail operations with
 * overhead that outweighs synchronization overhead. For example, here
 * is a class using a TreeMap that is expected to be large and 
 * concurrently accessed.
 *
 * <pre>
 * class RWDictionary {
 *    private final Map&lt;String, Data&gt;  m = new TreeMap&lt;String, Data&gt;();
 *    private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
 *    private final Lock r = rwl.readLock();
 *    private final Lock w = rwl.writeLock();
 *
 *    public Data get(String key) {
 *        r.lock(); try { return m.get(key); } finally { r.unlock(); }
 *    }
 *    public String[] allKeys() {
 *        r.lock(); try { return m.keySet().toArray(); } finally { r.unlock(); }
 *    }
 *    public Data put(String key, Data value) {
 *        w.lock(); try { return m.put(key, value); } finally { w.unlock(); }
 *    }
 *    public void clear() {
 *        w.lock(); try { m.clear(); } finally { w.unlock(); }
 *    }
 * }
 * </pre>
 * 
 *
 * <h3>Implementation Notes</h3>
 *
 * <p>A reentrant write lock intrinsically defines an owner and can
 * only be released by the thread that acquired it.  In contrast, in
 * this implementation, the read lock has no concept of ownership, and
 * there is no requirement that the thread releasing a read lock is
 * the same as the one that acquired it.  However, this property is
 * not guaranteed to hold in future implementations of this class.
 *
 * <p> This lock supports a maximum of 65536 recursive write locks
 * and 65536 read locks. Attempts to exceed these limits result in
 * {@link Error} throws from locking methods.
 *
 * @since 1.5
 * @author Doug Lea
 *
 */
public class ReentrantReadWriteLock implements ReadWriteLock, java.io.Serializable  {
    private static final long serialVersionUID = -6992448646407690164L;
    /** Inner class providing readlock */
    private final ReentrantReadWriteLock.ReadLock readerLock;
    /** Inner class providing writelock */
    private final ReentrantReadWriteLock.WriteLock writerLock;
    /** Performs all synchronization mechanics */
    private final Sync sync;

    /**
     * Creates a new <tt>ReentrantReadWriteLock</tt> with
     * default ordering properties.
     */
    public ReentrantReadWriteLock() {
        sync = new NonfairSync();
        readerLock = new ReadLock(this);
        writerLock = new WriteLock(this);
    }

    /**
     * Creates a new <tt>ReentrantReadWriteLock</tt> with
     * the given fairness policy.
     *
     * @param fair true if this lock should use a fair ordering policy
     */
    public ReentrantReadWriteLock(boolean fair) {
        sync = (fair)? new FairSync() : new NonfairSync();
        readerLock = new ReadLock(this);
        writerLock = new WriteLock(this);
    }

    public ReentrantReadWriteLock.WriteLock writeLock() { return writerLock; }
    public ReentrantReadWriteLock.ReadLock  readLock()  { return readerLock; }

    /* 
     * Read vs write count extraction constants and functions.
     * Lock state is logically divided into two shorts: The lower
     * one representing the exclusive (writer) lock hold count,
     * and the upper the shared (reader) hold count.
     */
    
    static final int SHARED_SHIFT   = 16;
    static final int SHARED_UNIT    = (1 << SHARED_SHIFT);
    static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;
    
    /** Returns the number of shared holds represented in count  */
    static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }
    /** Returns the number of exclusive holds represented in count  */
    static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }

    /** 
     * Synchronization implementation for ReentrantReadWriteLock.
     * Subclassed into fair and nonfair versions.
     */
    abstract static class Sync extends AbstractQueuedSynchronizer {
        /** Current (exclusive) owner thread */
        transient Thread owner;

        /**
         * Perform write lock. Allows fast path in non-fair version.
         */
        abstract void wlock();

        /** 
         * Perform non-fair tryLock for write.  tryAcquire is
         * implemented in subclasses, but both versions need nonfair
         * try for trylock method
         */
        final boolean nonfairTryAcquire(int acquires) {
            // mask out readlocks if called from condition methods
            acquires = exclusiveCount(acquires);
            Thread current = Thread.currentThread();
            int c = getState();
            int w = exclusiveCount(c);
            if (w + acquires >= SHARED_UNIT)
                throw new Error("Maximum lock count exceeded");
            if (c != 0 && (w == 0 || current != owner))
                return false;
            if (!compareAndSetState(c, c + acquires)) 
                return false;
            owner = current;
            return true;
        }

        /** 
         * Perform nonfair tryLock for read. 
         */
        final int nonfairTryAcquireShared(int acquires) {
            for (;;) {
                int c = getState();
                int nextc = c + (acquires << SHARED_SHIFT);
                if (nextc < c)
                    throw new Error("Maximum lock count exceeded");
                if (exclusiveCount(c) != 0 && 
                    owner != Thread.currentThread())
                    return -1;
                if (compareAndSetState(c, nextc)) 
                    return 1;
                // Recheck count if lost CAS
            }
        }

        protected final boolean tryRelease(int releases) {
            Thread current = Thread.currentThread();
            int c = getState();
            if (owner != current)
                throw new IllegalMonitorStateException();
            int nextc = c - releases;
            boolean free = false;
            if (exclusiveCount(c) == releases) {
                free = true;
                owner = null;
            }
            setState(nextc);
            return free;
        }

        protected final boolean tryReleaseShared(int releases) {
            for (;;) {
                int c = getState();
                int nextc = c - (releases << SHARED_SHIFT);
                if (nextc < 0)
                    throw new IllegalMonitorStateException();
                if (compareAndSetState(c, nextc)) 
                    return nextc == 0;
            }
        }
    
        protected final boolean isHeldExclusively() {
            return exclusiveCount(getState()) != 0 && 
                owner == Thread.currentThread();
        }

        // Methods relayed to outer class
        
        final ConditionObject newCondition() { 
            return new ConditionObject(); 
        }

        final Thread getOwner() {
            int c = exclusiveCount(getState());
            Thread o = owner;
            return (c == 0)? null : o;
        }
        
        final int getReadLockCount() {
            return sharedCount(getState());
        }
        
        final boolean isWriteLocked() {
            return exclusiveCount(getState()) != 0;
        }

        final int getWriteHoldCount() {
            int c = exclusiveCount(getState());
            Thread o = owner;
            return (o == Thread.currentThread())? c : 0;
        }

        /**
         * Reconstitute this lock instance from a stream
         * @param s the stream
         */
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            s.defaultReadObject();
            setState(0); // reset to unlocked state
        }

        final int getCount() { return getState(); }
    }

    /** 
     * Nonfair version of Sync
     */
    final static class NonfairSync extends Sync {
        protected final boolean tryAcquire(int acquires) { 
            return nonfairTryAcquire(acquires);
        }

        protected final int tryAcquireShared(int acquires) {
            return nonfairTryAcquireShared(acquires);
        }

        // Use fastpath for main write lock method
        final void wlock() {
            if (compareAndSetState(0, 1))
                owner = Thread.currentThread();
            else
                acquire(1);
        }
    }

    /** 
     * Fair version of Sync
     */
    final static class FairSync extends Sync {
        protected final boolean tryAcquire(int acquires) { 
            // mask out readlocks if called from condition methods
            acquires = exclusiveCount(acquires);
            Thread current = Thread.currentThread();
            Thread first;
            int c = getState();
            int w = exclusiveCount(c);
            if (w + acquires >= SHARED_UNIT)
                throw new Error("Maximum lock count exceeded");
            if ((w == 0 || current != owner) &&
                (c != 0 || 
                 ((first = getFirstQueuedThread()) != null && 
                  first != current)))
                return false;
            if (!compareAndSetState(c, c + acquires)) 
                return false;
            owner = current;
            return true;
        }

        protected final int tryAcquireShared(int acquires) {
            Thread current = Thread.currentThread();
            for (;;) {
                int c = getState();
                if (exclusiveCount(c) != 0) {
                    if (owner != current)