01: /*
02: File: FIFOSemaphore.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 First-in/First-out implementation of a Semaphore.
18: * Waiting requests will be satisified in
19: * the order that the processing of those requests got to a certain point.
20: * If this sounds vague it is meant to be. FIFO implies a
21: * logical timestamping at some point in the processing of the
22: * request. To simplify things we don't actually timestamp but
23: * simply store things in a FIFO queue. Thus the order in which
24: * requests enter the queue will be the order in which they come
25: * out. This order need not have any relationship to the order in
26: * which requests were made, nor the order in which requests
27: * actually return to the caller. These depend on Java thread
28: * scheduling which is not guaranteed to be predictable (although
29: * JVMs tend not to go out of their way to be unfair).
30: * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
31: **/
32:
33: public class FIFOSemaphore extends QueuedSemaphore {
34:
35: /**
36: * Create a Semaphore with the given initial number of permits.
37: * Using a seed of one makes the semaphore act as a mutual exclusion lock.
38: * Negative seeds are also allowed, in which case no acquires will proceed
39: * until the number of releases has pushed the number of permits past 0.
40: **/
41:
42: public FIFOSemaphore(long initialPermits) {
43: super (new FIFOWaitQueue(), initialPermits);
44: }
45:
46: /**
47: * Simple linked list queue used in FIFOSemaphore.
48: * Methods are not synchronized; they depend on synch of callers
49: **/
50:
51: protected static class FIFOWaitQueue extends WaitQueue {
52: protected WaitNode head_ = null;
53: protected WaitNode tail_ = null;
54:
55: protected void insert(WaitNode w) {
56: if (tail_ == null)
57: head_ = tail_ = w;
58: else {
59: tail_.next = w;
60: tail_ = w;
61: }
62: }
63:
64: protected WaitNode extract() {
65: if (head_ == null)
66: return null;
67: else {
68: WaitNode w = head_;
69: head_ = w.next;
70: if (head_ == null)
71: tail_ = null;
72: w.next = null;
73: return w;
74: }
75: }
76: }
77:
78: }
|