01: /*
02: File: PrioritySemaphore.java
03:
04: Originally written by Doug Lea and released into the public domain.
05: This may be used for any purposes whatsoever without acknowledgment.
06: Thanks for the assistance and support of Sun Microsystems Labs,
07: and everyone contributing, testing, and using this code.
08:
09: History:
10: Date Who What
11: 11Jun1998 dl Create public version
12: */
13:
14: package EDU.oswego.cs.dl.util.concurrent;
15:
16: /**
17: * A Semaphore that grants requests to threads with higher
18: * Thread priority rather than lower priority when there is
19: * contention. Ordering of requests with the same priority
20: * is approximately FIFO.
21: * Priorities are based on Thread.getPriority.
22: * Changing the priority of an already-waiting thread does NOT
23: * change its ordering. This class also does not specially deal with priority
24: * inversion -- when a new high-priority thread enters
25: * while a low-priority thread is currently running, their
26: * priorities are <em>not</em> artificially manipulated.
27: * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
28:
29: **/
30:
31: public class PrioritySemaphore extends QueuedSemaphore {
32:
33: /**
34: * Create a Semaphore with the given initial number of permits.
35: * Using a seed of one makes the semaphore act as a mutual exclusion lock.
36: * Negative seeds are also allowed, in which case no acquires will proceed
37: * until the number of releases has pushed the number of permits past 0.
38: **/
39:
40: public PrioritySemaphore(long initialPermits) {
41: super (new PriorityWaitQueue(), initialPermits);
42: }
43:
44: protected static class PriorityWaitQueue extends WaitQueue {
45:
46: /** An array of wait queues, one per priority **/
47: protected final FIFOSemaphore.FIFOWaitQueue[] cells_ = new FIFOSemaphore.FIFOWaitQueue[Thread.MAX_PRIORITY
48: - Thread.MIN_PRIORITY + 1];
49:
50: /**
51: * The index of the highest priority cell that may need to be signalled,
52: * or -1 if none. Used to minimize array traversal.
53: **/
54:
55: protected int maxIndex_ = -1;
56:
57: protected PriorityWaitQueue() {
58: for (int i = 0; i < cells_.length; ++i)
59: cells_[i] = new FIFOSemaphore.FIFOWaitQueue();
60: }
61:
62: protected void insert(WaitNode w) {
63: int idx = Thread.currentThread().getPriority()
64: - Thread.MIN_PRIORITY;
65: cells_[idx].insert(w);
66: if (idx > maxIndex_)
67: maxIndex_ = idx;
68: }
69:
70: protected WaitNode extract() {
71: for (;;) {
72: int idx = maxIndex_;
73: if (idx < 0)
74: return null;
75: WaitNode w = cells_[idx].extract();
76: if (w != null)
77: return w;
78: else
79: --maxIndex_;
80: }
81: }
82: }
83:
84: }
|