001: /*
002: * $RCSfile: RWLock.java,v $
003: *
004: * Copyright (c) 2005 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Use is subject to license terms.
007: *
008: * $Revision: 1.1 $
009: * $Date: 2005/02/11 04:57:01 $
010: * $State: Exp $
011: */
012: package com.sun.media.jai.util;
013:
014: import java.util.LinkedList;
015: import java.util.ListIterator;
016:
017: /**
018: * A class that provides a classic reader/writer lock functionality.
019: * This implementation is based on the JavaWorld article by Tark Modi
020: * titled "Lock on to an alternate synchronized mechanism" with some
021: * minor modifications.
022: *
023: * <p>This lock provides the following functionality : <ul>
024: *
025: * <li> Allows multiple threads read access while only a single
026: * thread can have a write access.</li>
027: *
028: * <li> Allows a thread owning a read lock to "upgrade" to a write
029: * lock.</li>
030: *
031: * <li> Allows a thread owning a write lock to "downgrade" to a read
032: * lock.</li>
033: *
034: * <li> Allows the option to either block or specify a waitTime on
035: * certain requests.
036: *
037: * </ul>
038: */
039: public final class RWLock {
040:
041: // Should a read lock be allowed to upgrade to a write lock if the
042: // thread requesting the write lock already owns the read lock.
043: private boolean allowUpgrades;
044:
045: // Lock Types
046: private static int READ = 1;
047: private static int WRITE = 2;
048:
049: private static int NOT_FOUND = -1;
050:
051: // A list of threads that are waiting to acquire a lock, waiting to
052: // upgrade their lock or have been granted locks.
053: private WaitingList waitingList = new WaitingList();
054:
055: private class WaitingList extends LinkedList {
056:
057: // Return index of the first writer in the list.
058: int indexOfFirstWriter() {
059:
060: ListIterator iter = listIterator(0);
061: int index = 0;
062:
063: while (iter.hasNext()) {
064: if (((ReaderWriter) iter.next()).lockType == WRITE)
065: return index;
066: index++;
067: }
068:
069: return NOT_FOUND;
070: }
071:
072: // Return the index of the last thread granted a lock
073: int indexOfLastGranted() {
074:
075: ListIterator iter = listIterator(size());
076: int index = size() - 1;
077:
078: while (iter.hasPrevious()) {
079: if (((ReaderWriter) iter.previous()).granted == true)
080: return index;
081: index--;
082: }
083:
084: return NOT_FOUND;
085: }
086:
087: // Return index of the element for this thread
088: int findMe() {
089: return indexOf(new ReaderWriter());
090: }
091: }
092:
093: // Element stored in the waiting list.
094: private class ReaderWriter {
095:
096: Thread key; // set equal to the Thread ID
097: int lockType; // READ or WRITE
098: int lockCount; // # of times lock was taken
099: boolean granted; // Has this thread been granted the lock
100:
101: ReaderWriter() {
102: this (0);
103: }
104:
105: ReaderWriter(int type) {
106:
107: key = Thread.currentThread();
108: lockType = type;
109: lockCount = 0;
110: granted = false;
111: }
112:
113: /**
114: * Two elements are equal if their keys are equal. Note that
115: * this does not make any instanceof checks since it assumes
116: * that this implementation uses the this list a certain way.
117: */
118: public boolean equals(Object o) {
119: return key == ((ReaderWriter) o).key;
120: }
121: }
122:
123: /**
124: * Constructor.
125: *
126: * @param should upgrades of read locks to write locks be
127: * allowed ?
128: */
129: public RWLock(boolean allowUpgrades) {
130:
131: this .allowUpgrades = allowUpgrades;
132: }
133:
134: /**
135: * Constructor. Equivalent to <code>RWLock(true)</code>
136: * which creates an upgradable reader-writer lock.
137: */
138: public RWLock() {
139: this (true);
140: }
141:
142: /**
143: * Tries to obtain a read lock within the specified time.
144: *
145: * @param waitTime the time to wait in milliseconds while trying
146: * to obtain the read lock. A negative value indicates a
147: * blocking wait.
148: *
149: * @return true if the read lock was obtained without timing out.
150: */
151: public synchronized boolean forReading(int waitTime) {
152:
153: ReaderWriter element = null;
154:
155: // Is there a node for this thread already in the list?
156: // If not, create a new one.
157: int index = waitingList.findMe();
158:
159: if (index != NOT_FOUND) {
160: element = (ReaderWriter) waitingList.get(index);
161:
162: } else {
163: element = new ReaderWriter(READ);
164: waitingList.add(element);
165: }
166:
167: // If a lock has already been granted once just increment the
168: // count and return. It does not matter whether the lock granted
169: // initially was a READ or WRITE lock.
170: if (element.lockCount > 0) {
171: element.lockCount++;
172: return true;
173: }
174:
175: long startTime = System.currentTimeMillis();
176: long endTime = waitTime + startTime;
177:
178: do {
179: int nextWriter = waitingList.indexOfFirstWriter();
180:
181: index = waitingList.findMe();
182:
183: // If there is no writer in front of me I get a
184: // read lock. Otherwise, I wait...
185: if ((nextWriter == NOT_FOUND) || (nextWriter > index)) {
186: element.lockCount++;
187: element.granted = true;
188: return true;
189: }
190:
191: // Non-blocking version, just return. Do not need notifyAll
192: // here since we added and removed the new element within the
193: // same synchronized block and so no other thread ever saw
194: // it.
195: if (waitTime == 0) {
196: waitingList.remove(element);
197: return false;
198: }
199:
200: // Now wait for the lock.
201: try {
202: // Negative wait time indicates a blocking wait.
203: if (waitTime < 0) {
204: wait();
205:
206: } else {
207: long delta = endTime - System.currentTimeMillis();
208:
209: if (delta > 0)
210: wait(delta);
211: }
212: } catch (InterruptedException e) {
213: // Should never be here.
214: // These messages are for debugging purposes only
215: System.err
216: .println(element.key.getName()
217: + " : interrupted while waiting for a READ lock!");
218: }
219:
220: } while ((waitTime < 0)
221: || (endTime > System.currentTimeMillis()));
222:
223: // Could not get the lock and timed out.
224: waitingList.remove(element);
225:
226: // Important to notify all threads of our removal.
227: notifyAll();
228:
229: // Failed to get lock.
230: return false;
231: }
232:
233: /**
234: * Tries to obtain a read lock. Equivalent to <code>forReading(-1)
235: * </code> which will go into a blocking wait attempting to get a
236: * read lock.
237: *
238: * @return true, always.
239: */
240: public synchronized boolean forReading() {
241: return forReading(-1);
242: }
243:
244: /**
245: * Tries to obtain a write lock withing the specified time. If the
246: * current thread owns a read lock, then it is upgraded to a write
247: * lock if upgrades are allowed, else, throws an UpgradeNotAllowed
248: * exception. If the lock is not owned by the current thread then
249: * it waits for a write lock for the specified time.
250: *
251: * @param waitTime the time to wait in milliseconds while trying
252: * to obtain the write lock. A negative value indicates a
253: * blocking wait.
254: *
255: * @return true if the write lock was obtained without timing out.
256: *
257: * @throws UpgradeNotAllowed if current thread owns a read lock
258: * and upgrades are not allowed.
259: */
260: public synchronized boolean forWriting(int waitTime)
261: throws UpgradeNotAllowed {
262:
263: ReaderWriter element = null;
264:
265: // Is there a node for this thread already in the list?
266: // If not, create a new one.
267: int index = waitingList.findMe();
268:
269: if (index != NOT_FOUND) {
270: element = (ReaderWriter) waitingList.get(index);
271:
272: } else {
273: element = new ReaderWriter(WRITE);
274: waitingList.add(element);
275: }
276:
277: // If the thread has a READ lock, we need to upgrade
278: if ((element.granted == true) && (element.lockType == READ)) {
279:
280: try {
281: if (!upgrade(waitTime))
282: return false;
283: } catch (LockNotHeld e) {
284: return false;
285: }
286: }
287:
288: // If a lock has already been granted once just increment the
289: // count and return. At this point the thread either had a WRITE
290: // lock or was upgraded to have one.
291: if (element.lockCount > 0) {
292: element.lockCount++;
293: return true;
294: }
295:
296: long startTime = System.currentTimeMillis();
297: long endTime = waitTime + startTime;
298:
299: do {
300: // If there are any readers in front of me
301: // I have to wait...
302: index = waitingList.findMe();
303:
304: // If I am the first one in the list I get the lock.
305: if (index == 0) {
306: element.lockCount++;
307: element.granted = true;
308: return true;
309: }
310:
311: // Non-blocking version, just return. Do not need notifyAll
312: // here since we added and removed the new element within the
313: // same synchronized block and so no other thread ever saw
314: // it.
315: if (waitTime == 0) {
316: waitingList.remove(element);
317: return false;
318: }
319:
320: // Now wait for the lock.
321: try {
322: // Negative wait time indicates a blocking wait.
323: if (waitTime < 0) {
324: wait();
325:
326: } else {
327: long delta = endTime - System.currentTimeMillis();
328:
329: if (delta > 0)
330: wait(delta);
331: }
332: } catch (InterruptedException e) {
333: // Should never be here.
334: // These messages are for debugging purposes only
335: System.err
336: .println(element.key.getName()
337: + " : interrupted while waiting for a WRITE lock!");
338: }
339:
340: } while ((waitTime < 0)
341: || (endTime > System.currentTimeMillis()));
342:
343: // Could not get the lock and timed out.
344: waitingList.remove(element);
345:
346: // Notify all threads of our removal.
347: notifyAll();
348:
349: // Failed to get the lock.
350: return false;
351: }
352:
353: /**
354: * Tries to obtain a write lock. Equivalent to <code>forWriting(-1)
355: * </code> which will go into a blocking wait attempting to get a
356: * write lock.
357: *
358: * @return true, always.
359: *
360: * @throws UpgradeNotAllowed if current thread owns a read lock
361: * and upgrades are not allowed.
362: */
363: public synchronized boolean forWriting() throws UpgradeNotAllowed {
364: return forWriting(-1);
365: }
366:
367: /**
368: * Try to upgrade a write lock within the specified amount of time.
369: * If the current thread does not own the lock or if upgrades
370: * are not allowed an exception is thrown. If the current thread
371: * already owns a write lock, nothing happens. Otherwise, threads
372: * already owning a read lock are given a higher priority in
373: * receiving the write lock than those that own no lock.
374: *
375: * @param waitTime the time to wait in milliseconds while trying
376: * to upgrade to a write lock. A negative value indicates a
377: * blocking wait.
378: *
379: * @return true if the upgrade was performed without timing out.
380: *
381: * @throws LockNotHeld if the current thread does not own the lock
382: * @throws UpgradeNotAllowed if the lock is not currently
383: * held by the owner.
384: */
385: public synchronized boolean upgrade(int waitTime)
386: throws UpgradeNotAllowed, LockNotHeld {
387:
388: if (!allowUpgrades)
389: throw new UpgradeNotAllowed();
390:
391: // We should already be in the list. If not, it is an error.
392: int index = waitingList.findMe();
393:
394: if (index == NOT_FOUND)
395: throw new LockNotHeld();
396:
397: // Get the actual element. If the lock type is already WRITE,
398: // just return.
399: ReaderWriter element = (ReaderWriter) waitingList.get(index);
400:
401: if (element.lockType == WRITE)
402: return true;
403:
404: // What is the index of the last granted lock?
405: int lastGranted = waitingList.indexOfLastGranted();
406:
407: // lastGranted can not be NOT_FOUND, after all we are
408: // granted a READ lock!
409: if (lastGranted == NOT_FOUND)
410: throw new LockNotHeld();
411:
412: // If we are not the last granted lock, then we will position
413: // ourselves as such.
414: if (index != lastGranted) {
415: waitingList.remove(index);
416: ListIterator iter = waitingList.listIterator(lastGranted);
417: iter.add(element);
418: }
419:
420: // We want new readers to think this is a write lock
421: // This is important so that they block i.e. do not get granted.
422: // Since we are now waiting for a write lock it is
423: // important that we were after all granted read locks.
424: element.lockType = WRITE;
425:
426: long startTime = System.currentTimeMillis();
427: long endTime = waitTime + startTime;
428:
429: do {
430: index = waitingList.findMe();
431:
432: if (index == 0) {
433: return true;
434: }
435:
436: // Non-blocking version. Do not need notifyAll here since
437: // we changed the lock type back and forth within the same
438: // synchronized block and so no other thread ever saw it.
439: if (waitTime == 0) {
440:
441: // Back to READ type
442: element.lockType = READ;
443:
444: // No need to readjust position since it does not matter
445: // for already granted locks.
446: return false;
447: }
448:
449: // Now wait for the lock.
450: try {
451: // Negative wait time indicates a blocking wait.
452: if (waitTime < 0) {
453: wait();
454: } else {
455: long delta = endTime - System.currentTimeMillis();
456:
457: if (delta > 0)
458: wait(delta);
459: }
460: } catch (InterruptedException e) {
461: // Should never be here.
462: // These messages are for debugging purposes only
463: System.err
464: .println(element.key.getName()
465: + " : interrupted while waiting to UPGRADE lock!");
466: }
467:
468: } while ((waitTime < 0)
469: || (endTime > System.currentTimeMillis()));
470:
471: // We failed to upgrade. Go back to original lock type
472: element.lockType = READ;
473:
474: // Important to notify all threads that we are back
475: // to being a READ lock.
476: notifyAll();
477:
478: // Failed to upgrade.
479: return false;
480: }
481:
482: /**
483: * Tries to upgrade to a write lock. Equivalent to
484: * <code>upgrade(-1)</code> which will go into a blocking wait
485: * attempting to get a upgrade to a write lock.
486: *
487: * @return true, always.
488: *
489: * @throws LockNotHeld if some other thread owns the lock
490: * @throws UpgradeNotAllowed if the lock is not currently
491: * held by the owner.
492: */
493: public synchronized boolean upgrade() throws UpgradeNotAllowed,
494: LockNotHeld {
495: return upgrade(-1);
496: }
497:
498: /**
499: * Tries to downgrade a write lock to a read lock. If the current
500: * thread does not hold the lock an exception is thrown. If the
501: * current thread already owns a read lock, nothing happens. If it
502: * owns a write lock, then it is downgraded to a read lock. All
503: * threads waiting for a read lock can now get it only if there are
504: * no other threads waiting for a write lock ahead of them.
505: *
506: * @return true if the downgrade was performed successfully.
507: *
508: * @throws LockNotHeld if the current thread does not own the lock.
509: */
510: public synchronized boolean downgrade() throws LockNotHeld {
511:
512: // We should already be in the list. If not, it is an error.
513: int index = waitingList.findMe();
514:
515: if (index == NOT_FOUND)
516: throw new LockNotHeld();
517:
518: // Get the element for this thread
519: ReaderWriter e = (ReaderWriter) waitingList.get(index);
520:
521: // Downgrade the WRITE lock and notify all threads of the change.
522: if (e.lockType == WRITE) {
523: e.lockType = READ;
524: notifyAll();
525: }
526:
527: return true;
528: }
529:
530: /**
531: * Tries to relinquish the ownership of a lock. If the
532: * current thread does not hold the lock an exception is
533: * thrown. Note that every call to <code>forReading</code>
534: * and <code>forWriting</code> must have a corresponding
535: * <code>release()</code> call. However, <code>upgrade()</code>
536: * and <code>downgrade()</code> do not have corresponding
537: * <code>release()</code> calls.
538: *
539: * @throws LockNotHeld if the current thread does not own the lock.
540: */
541: public synchronized void release() throws LockNotHeld {
542:
543: // We should already be in the list. If not, it is an error.
544: int index = waitingList.findMe();
545:
546: if (index == NOT_FOUND)
547: throw new LockNotHeld();
548:
549: // Get the element for this thread
550: ReaderWriter e = (ReaderWriter) waitingList.get(index);
551:
552: // If the lock count goes down to zero,
553: // remove the lock and notify all threads of the change.
554: if ((--e.lockCount) == 0) {
555: waitingList.remove(index);
556: notifyAll();
557: }
558: }
559:
560: /**
561: * The exception thrown when trying to upgrade a lock when
562: * the lock does not allow upgrades.
563: */
564: public class UpgradeNotAllowed extends RuntimeException {
565: }
566:
567: /**
568: * The exception thrown when trying to upgrade a lock when
569: * the lock is not held by the current thread.
570: */
571: public class LockNotHeld extends RuntimeException {
572: }
573: }
|