util/concurrent/ReentrantReadWriteLock.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain. Use, modify, and
 * redistribute this code in any way without acknowledgement.
 */

package java.util.concurrent;

/**
 * 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. Instead, threads contend using an
 * approximately arrival-order policy. The actual order depends on the
 * order in which an internal {@link FairReentrantLock} is granted, but
 * essentially when the write lock is released either the single writer
 * at the notional head of the queue will be assigned the write lock, or
 * the set of readers at the head of the queue will be assigned the read lock.
 * <p>If readers are active and a writer arrives 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.
 * And both view the
 * interruptible lock methods as explicit interruption points and give
 * preference to responding to the interrupt over normal or reentrant 
 * acquisition of the lock, or over reporting the elapse of the waiting
 * time, as applicable.

 *
 * <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>Ownership</b>
 * <p>While not exposing a means to query the owner, the write lock does
 * internally define an owner and so the write lock can only be released by
 * the thread that acquired it.
 * <p>In contrast, the read lock has no concept of ownership.
 * Consequently, while not a particularly 
 * good practice, it is possible to acquire a read lock in one thread, and 
 * release it in another. This can occasionally be useful.
 *
 *
 * </ul>
 *
 * <p><b>Sample usage</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>
 *
 * @see ReentrantLock
 * @see Condition
 * @see ReadWriteLock
 * @see Locks
 *
 * @since 1.5
 * @spec JSR-166
 * @revised $Date: 2003/06/26 10:47:35 $
 * @editor $Author: dl $
 * @author Doug Lea
 *
 */
public class ReentrantReadWriteLock implements ReadWriteLock, java.io.Serializable  {

    /*
      Note that all fields are transient and defined in a way that
      deserialized locks are in initial unlocked state.
    */

    /** Inner class providing readlock */
    private final Lock readerLock = new ReaderLock();
    /** Inner class providing writelock */
    private final Lock writerLock = new WriterLock();

    public Lock writeLock() { return writerLock; }

    public Lock readLock() { return readerLock; }

    /** 
     * Main lock.  Writers acquire on entry, and hold until release.
     * Reentrant acquires on write lock are allowed.  Readers acquire
     * and release only during entry, but are blocked from doing so if
     * there is an active writer. RRWLock is a simple ReentrantLock
     * subclass defined below that surrounds WriteLock condition waits
     * with bookeeping to save and restore writer state.
     **/
    private final RRWLock entryLock = new RRWLock();

    /** 
     * Number of threads that have entered read lock.  This is never
     * reset to zero. Incremented only during acquisition of read lock
     * while the "entryLock" is held, but read elsewhere, so is declared
     * volatile.
     **/
    private transient volatile int readers;

    /** 
     * Number of threads that have exited read lock.  This is never
     * reset to zero.  Accessed only in code protected by rLock. When
     * exreaders != readers, the rwlock is being used for
     * reading. Else if the entry lock is held, it is being used for
     * writing (or in transition). Else it is free.  Note: To
     * distinguish these states, we assume that fewer than 2^32 reader
     * threads can simultaneously execute.
     **/
    private transient int exreaders;

    /**
     * Flag set while writing. Needed by ReaderLock.tryLock to
     * distinguish contention from unavailability. Accessed
     * in ways that do not require being volatile.
     */
    private transient boolean writing;

    /**
     * Lock used by exiting readers and entering writers
     */

    private final ReentrantLock writeCheckLock = new ReentrantLock();

    /**
     * Condition waited on by blocked entering writers.
     */
    private final Condition writeEnabled = writeCheckLock.newCondition();

    /**
     * Reader exit protocol, called from unlock. if this is the last
     * reader, notify a possibly waiting writer.  Because waits occur
     * only when entry lock is held, at most one writer can be waiting
     * for this notification.  Because increments to "readers" aren't
     * protected by "this" lock, the notification may be spurious
     * (when an incoming reader in in the process of updating the
     * field), but at the point tested in acquiring write lock, both
     * locks will be held, thus avoiding false alarms. And we will
     * never miss an opportunity to send a notification when it is
     * actually needed.
    */
    private void readerExit() {
        writeCheckLock.lock();
        try {
            if (++exreaders == readers) 
                writeEnabled.signal(); 
        }
        finally {
            writeCheckLock.unlock();
        }
    }

    /**
     * Writer enter protocol, called after acquiring entry lock.
     * Wait until all readers have exited.
     * @throws InterruptedException if interrupted while waiting
    */
    private void writerEnter() throws InterruptedException {
        writeCheckLock.lock();
        try {
            while (exreaders != readers) 
                writeEnabled.await();
        }
        finally {
            writeCheckLock.unlock();
        }

    }

    /**
     * Trylock version of Writer enter protocol
     * @return true if successful
     */
    private boolean tryWriterEnter() {
        writeCheckLock.lock();
        boolean ok = (exreaders == readers);
        writeCheckLock.unlock();
        return ok;
    }

    /**
     * Timed version of writer enter protocol, called after acquiring
     * entry lock.  Wait until all readers have exited.
     * @param nanos the wait time
     * @return true if successful
     * @throws InterruptedException if interrupted while waiting
     */
    private boolean tryWriterEnter(long nanos) throws InterruptedException {
        writeCheckLock.lock();
        try {
            while (exreaders != readers) {
                if (nanos <= 0) 
                    return false;
                nanos = writeEnabled.awaitNanos(nanos);
            }
            return true;
        }
        finally {
            writeCheckLock.unlock();
        }
    }


    /**
     * The Reader lock
     */
    private class ReaderLock implements Lock {

        public void lock() {
            entryLock.lock();
            ++readers; 
            entryLock.unlock();
        }

        public void lockInterruptibly() throws InterruptedException {
            entryLock.lockInterruptibly();
            ++readers; 
            entryLock.unlock();
        }

        public  boolean tryLock() {
            // if we fail entry lock just due to contention, try again.
            while (!entryLock.tryLock()) {
                if (writing)
                    return false;
                else
                    Thread.yield();
            }

            ++readers; 
            entryLock.unlock();
            return true;
        }

        public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
            if (!entryLock.tryLock(time, unit)) 
                return false;

            ++readers; 
            entryLock.unlock();
            return true;
        }

        public  void unlock() {
            readerExit();
        }

        public Condition newCondition() {
            throw new UnsupportedOperationException();
        }
    }

    /**
     * The writer lock
     */
    private class WriterLock implements Lock  {
        public void lock() {
            entryLock.lock();
            writing = true;
            if (entryLock.getHoldCount() > 1)  // skip if held reentrantly
                return;

            boolean wasInterrupted = false;
            for (;;) {
                try {
                    writerEnter();
                    break;
                }
                catch (InterruptedException ie) {
                    wasInterrupted = true;
                }
            }
            if (wasInterrupted) {
                Thread.currentThread().interrupt();
            }
        }

        public void lockInterruptibly() throws InterruptedException {
            entryLock.lockInterruptibly();
            writing = true;
            if (entryLock.getHoldCount() > 1) // skip if held reentrantly
                return;
            
            try {
                writerEnter();
            }
            catch (InterruptedException ie) {
                writing = false;
                entryLock.unlock();
                throw ie;
            }
        }

        public boolean tryLock( ) {
            if (!entryLock.tryLock())
                return false;
            writing = true;
            if (entryLock.getHoldCount() > 1) 
                return true;

            if (!tryWriterEnter()) {
                entryLock.unlock();
                writing = false;
                return false;
            }
            return true;
        }

        public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
            long startTime = JSR166Support.currentTimeNanos();
            long nanos = unit.toNanos(time);
            if (!entryLock.tryLock(nanos, TimeUnit.NANOSECONDS)) 
                return false;
            writing = true;
            if (entryLock.getHoldCount() > 1) 
                return true;
            
            nanos -= JSR166Support.currentTimeNanos() - startTime;
            try {
                if (!tryWriterEnter(nanos)) {
                    entryLock.unlock();
                    writing = false;
                    return false;
                }
            }
            catch (InterruptedException ie) {
                writing = false;
                entryLock.unlock();
                
                throw ie;
            }
            return true;
        }
        
        public void unlock() {
            // must perform owner check before clearing "writing"
            if (!entryLock.isHeldByCurrentThread())
                throw new IllegalMonitorStateException();
            writing = false;
            entryLock.unlock();
        }

        public Condition newCondition() { 
            return entryLock.newCondition();
        }
        
    }

    /**
     * Subclass of ReentrantLock to adjust fields on entry and exit to
     * condition waits.
     */
    class RRWLock extends FairReentrantLock {
        
        void beforeWait() {
            writing = false;
        }

        void afterWait() {
            writing = true;
            // same as lock, except never bypass writerEnter.
            boolean wasInterrupted = false;
            for (;;) {
                try {
                    writerEnter();
                    break;
                }
                catch (InterruptedException ie) {
                    wasInterrupted = true;
                }
            }
            if (wasInterrupted) {
                Thread.currentThread().interrupt();
            }
        }
    }

}

Revision:	1.7
Committed:	Tue Jul 8 00:46:35 2003 UTC (20 years, 10 months ago) by dl
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.6:	+2 -2 lines
State:	*FILE REMOVED*
Log Message:	Locks in subpackage; fairness params added
#	Content
1	/*
2	* Written by Doug Lea with assistance from members of JCP JSR-166
3	* Expert Group and released to the public domain. Use, modify, and
4	* redistribute this code in any way without acknowledgement.
5	*/
6
7	package java.util.concurrent;
8
9	/**
10	* An implementation of {@link ReadWriteLock} supporting similar
11	* semantics to {@link ReentrantLock}.
12	* <p>This class has the following properties:
13	* <ul>
14	* <li><b>Acquisition order</b>
15	* <p> This class does not impose a reader or writer preference
16	* ordering for lock access. Instead, threads contend using an
17	* approximately arrival-order policy. The actual order depends on the
18	* order in which an internal {@link FairReentrantLock} is granted, but
19	* essentially when the write lock is released either the single writer
20	* at the notional head of the queue will be assigned the write lock, or
21	* the set of readers at the head of the queue will be assigned the read lock.
22	* <p>If readers are active and a writer arrives then no subsequent readers
23	* will be granted the read lock until after that writer has acquired and
24	* released the write lock.
25	*
26	* <li><b>Reentrancy</b>
27	* <p>This lock allows both readers and writers to reacquire read or
28	* write locks in the style of a {@link ReentrantLock}. Readers are not
29	* allowed until all write locks held by the writing thread have been
30	* released.
31	* <p>Additionally, a writer can acquire the read lock - but not vice-versa.
32	* Among other applications, reentrancy can be useful when
33	* write locks are held during calls or callbacks to methods that
34	* perform reads under read locks.
35	* If a reader tries to acquire the write lock it will never succeed.
36	*
37	* <li><b>Lock downgrading</b>
38	* <p>Reentrancy also allows downgrading from the write lock to a read lock,
39	* by acquiring the write lock, then the read lock and then releasing the
40	* write lock. However, upgrading from a read lock to the write lock, is
41	* <b>not</b> possible.
42	*
43	* <li><b>Interruption of lock acquisition</b>
44	* <p>The read lock and write lock both support interruption during lock
45	* acquisition.
46	* And both view the
47	* interruptible lock methods as explicit interruption points and give
48	* preference to responding to the interrupt over normal or reentrant
49	* acquisition of the lock, or over reporting the elapse of the waiting
50	* time, as applicable.
51
52	*
53	* <li><b>{@link Condition} support</b>
54	* <p>The write lock provides a {@link Condition} implementation that
55	* behaves in the same way, with respect to the write lock, as the
56	* {@link Condition} implementation provided by
57	* {@link ReentrantLock#newCondition} does for {@link ReentrantLock}.
58	* This {@link Condition} can, of course, only be used with the write lock.
59	* <p>The read lock does not support a {@link Condition} and
60	* <tt>readLock().newCondition()</tt> throws
61	* <tt>UnsupportedOperationException</tt>.
62	*
63	* <li><b>Ownership</b>
64	* <p>While not exposing a means to query the owner, the write lock does
65	* internally define an owner and so the write lock can only be released by
66	* the thread that acquired it.
67	* <p>In contrast, the read lock has no concept of ownership.
68	* Consequently, while not a particularly
69	* good practice, it is possible to acquire a read lock in one thread, and
70	* release it in another. This can occasionally be useful.
71	*
72	*
73	* </ul>
74	*
75	* <p><b>Sample usage</b>. Here is a code sketch showing how to exploit
76	* reentrancy to perform lock downgrading after updating a cache (exception
77	* handling is elided for simplicity):
78	* <pre>
79	* class CachedData {
80	* Object data;
81	* volatile boolean cacheValid;
82	* ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
83	*
84	* void processCachedData() {
85	* rwl.readLock().lock();
86	* if (!cacheValid) {
87	* // upgrade lock manually
88	* rwl.readLock().unlock(); // must unlock first to obtain writelock
89	* rwl.writeLock().lock();
90	* if (!cacheValid) { // recheck
91	* data = ...
92	* cacheValid = true;
93	* }
94	* // downgrade lock
95	* rwl.readLock().lock(); // reacquire read without giving up write lock
96	* rwl.writeLock().unlock(); // unlock write, still hold read
97	* }
98	*
99	* use(data);
100	* rwl.readLock().unlock();
101	* }
102	* }
103	* </pre>
104	*
105	* @see ReentrantLock
106	* @see Condition
107	* @see ReadWriteLock
108	* @see Locks
109	*
110	* @since 1.5
111	* @spec JSR-166
112	* @revised $Date: 2003/06/26 10:47:35 $
113	* @editor $Author: dl $
114	* @author Doug Lea
115	*
116	*/
117	public class ReentrantReadWriteLock implements ReadWriteLock, java.io.Serializable {
118
119	/*
120	Note that all fields are transient and defined in a way that
121	deserialized locks are in initial unlocked state.
122	*/
123
124	/** Inner class providing readlock */
125	private final Lock readerLock = new ReaderLock();
126	/** Inner class providing writelock */
127	private final Lock writerLock = new WriterLock();
128
129	public Lock writeLock() { return writerLock; }
130
131	public Lock readLock() { return readerLock; }
132
133	/**
134	* Main lock. Writers acquire on entry, and hold until release.
135	* Reentrant acquires on write lock are allowed. Readers acquire
136	* and release only during entry, but are blocked from doing so if
137	* there is an active writer. RRWLock is a simple ReentrantLock
138	* subclass defined below that surrounds WriteLock condition waits
139	* with bookeeping to save and restore writer state.
140	**/
141	private final RRWLock entryLock = new RRWLock();
142
143	/**
144	* Number of threads that have entered read lock. This is never
145	* reset to zero. Incremented only during acquisition of read lock
146	* while the "entryLock" is held, but read elsewhere, so is declared
147	* volatile.
148	**/
149	private transient volatile int readers;
150
151	/**
152	* Number of threads that have exited read lock. This is never
153	* reset to zero. Accessed only in code protected by rLock. When
154	* exreaders != readers, the rwlock is being used for
155	* reading. Else if the entry lock is held, it is being used for
156	* writing (or in transition). Else it is free. Note: To
157	* distinguish these states, we assume that fewer than 2^32 reader
158	* threads can simultaneously execute.
159	**/
160	private transient int exreaders;
161
162	/**
163	* Flag set while writing. Needed by ReaderLock.tryLock to
164	* distinguish contention from unavailability. Accessed
165	* in ways that do not require being volatile.
166	*/
167	private transient boolean writing;
168
169	/**
170	* Lock used by exiting readers and entering writers
171	*/
172
173	private final ReentrantLock writeCheckLock = new ReentrantLock();
174
175	/**
176	* Condition waited on by blocked entering writers.
177	*/
178	private final Condition writeEnabled = writeCheckLock.newCondition();
179
180	/**
181	* Reader exit protocol, called from unlock. if this is the last
182	* reader, notify a possibly waiting writer. Because waits occur
183	* only when entry lock is held, at most one writer can be waiting
184	* for this notification. Because increments to "readers" aren't
185	* protected by "this" lock, the notification may be spurious
186	* (when an incoming reader in in the process of updating the
187	* field), but at the point tested in acquiring write lock, both
188	* locks will be held, thus avoiding false alarms. And we will
189	* never miss an opportunity to send a notification when it is
190	* actually needed.
191	*/
192	private void readerExit() {
193	writeCheckLock.lock();
194	try {
195	if (++exreaders == readers)
196	writeEnabled.signal();
197	}
198	finally {
199	writeCheckLock.unlock();
200	}
201	}
202
203	/**
204	* Writer enter protocol, called after acquiring entry lock.
205	* Wait until all readers have exited.
206	* @throws InterruptedException if interrupted while waiting
207	*/
208	private void writerEnter() throws InterruptedException {
209	writeCheckLock.lock();
210	try {
211	while (exreaders != readers)
212	writeEnabled.await();
213	}
214	finally {
215	writeCheckLock.unlock();
216	}
217
218	}
219
220	/**
221	* Trylock version of Writer enter protocol
222	* @return true if successful
223	*/
224	private boolean tryWriterEnter() {
225	writeCheckLock.lock();
226	boolean ok = (exreaders == readers);
227	writeCheckLock.unlock();
228	return ok;
229	}
230
231	/**
232	* Timed version of writer enter protocol, called after acquiring
233	* entry lock. Wait until all readers have exited.
234	* @param nanos the wait time
235	* @return true if successful
236	* @throws InterruptedException if interrupted while waiting
237	*/
238	private boolean tryWriterEnter(long nanos) throws InterruptedException {
239	writeCheckLock.lock();
240	try {
241	while (exreaders != readers) {
242	if (nanos <= 0)
243	return false;
244	nanos = writeEnabled.awaitNanos(nanos);
245	}
246	return true;
247	}
248	finally {
249	writeCheckLock.unlock();
250	}
251	}
252
253
254	/**
255	* The Reader lock
256	*/
257	private class ReaderLock implements Lock {
258
259	public void lock() {
260	entryLock.lock();
261	++readers;
262	entryLock.unlock();
263	}
264
265	public void lockInterruptibly() throws InterruptedException {
266	entryLock.lockInterruptibly();
267	++readers;
268	entryLock.unlock();
269	}
270
271	public boolean tryLock() {
272	// if we fail entry lock just due to contention, try again.
273	while (!entryLock.tryLock()) {
274	if (writing)
275	return false;
276	else
277	Thread.yield();
278	}
279
280	++readers;
281	entryLock.unlock();
282	return true;
283	}
284
285	public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
286	if (!entryLock.tryLock(time, unit))
287	return false;
288
289	++readers;
290	entryLock.unlock();
291	return true;
292	}
293
294	public void unlock() {
295	readerExit();
296	}
297
298	public Condition newCondition() {
299	throw new UnsupportedOperationException();
300	}
301	}
302
303	/**
304	* The writer lock
305	*/
306	private class WriterLock implements Lock {
307	public void lock() {
308	entryLock.lock();
309	writing = true;
310	if (entryLock.getHoldCount() > 1) // skip if held reentrantly
311	return;
312
313	boolean wasInterrupted = false;
314	for (;;) {
315	try {
316	writerEnter();
317	break;
318	}
319	catch (InterruptedException ie) {
320	wasInterrupted = true;
321	}
322	}
323	if (wasInterrupted) {
324	Thread.currentThread().interrupt();
325	}
326	}
327
328	public void lockInterruptibly() throws InterruptedException {
329	entryLock.lockInterruptibly();
330	writing = true;
331	if (entryLock.getHoldCount() > 1) // skip if held reentrantly
332	return;
333
334	try {
335	writerEnter();
336	}
337	catch (InterruptedException ie) {
338	writing = false;
339	entryLock.unlock();
340	throw ie;
341	}
342	}
343
344	public boolean tryLock( ) {
345	if (!entryLock.tryLock())
346	return false;
347	writing = true;
348	if (entryLock.getHoldCount() > 1)
349	return true;
350
351	if (!tryWriterEnter()) {
352	entryLock.unlock();
353	writing = false;
354	return false;
355	}
356	return true;
357	}
358
359	public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
360	long startTime = JSR166Support.currentTimeNanos();
361	long nanos = unit.toNanos(time);
362	if (!entryLock.tryLock(nanos, TimeUnit.NANOSECONDS))
363	return false;
364	writing = true;
365	if (entryLock.getHoldCount() > 1)
366	return true;
367
368	nanos -= JSR166Support.currentTimeNanos() - startTime;
369	try {
370	if (!tryWriterEnter(nanos)) {
371	entryLock.unlock();
372	writing = false;
373	return false;
374	}
375	}
376	catch (InterruptedException ie) {
377	writing = false;
378	entryLock.unlock();
379
380	throw ie;
381	}
382	return true;
383	}
384
385	public void unlock() {
386	// must perform owner check before clearing "writing"
387	if (!entryLock.isHeldByCurrentThread())
388	throw new IllegalMonitorStateException();
389	writing = false;
390	entryLock.unlock();
391	}
392
393	public Condition newCondition() {
394	return entryLock.newCondition();
395	}
396
397	}
398
399	/**
400	* Subclass of ReentrantLock to adjust fields on entry and exit to
401	* condition waits.
402	*/
403	class RRWLock extends FairReentrantLock {
404
405	void beforeWait() {
406	writing = false;
407	}
408
409	void afterWait() {
410	writing = true;
411	// same as lock, except never bypass writerEnter.
412	boolean wasInterrupted = false;
413	for (;;) {
414	try {
415	writerEnter();
416	break;
417	}
418	catch (InterruptedException ie) {
419	wasInterrupted = true;
420	}
421	}
422	if (wasInterrupted) {
423	Thread.currentThread().interrupt();
424	}
425	}
426	}
427
428	}
429