util/concurrent/FairSemaphore.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;

/**
 * A semaphore guaranteeing that threads invoking any of the {@link
 * #acquire() acquire} methods are allocated permits in the order in
 * which their invocation of those methods was processed
 * (first-in-first-out; FIFO). Note that FIFO ordering necessarily
 * applies to specific internal points of execution within these
 * methods.  So, it is possible for one thread to invoke
 * <tt>acquire</tt> before another, but reach the ordering point after
 * the other, and similarly upon return from the method.
 *
 * <p>Because permits are allocated in-order, this class also provides
 * convenience methods to {@link #acquire(long) acquire} and {@link
 * #release(long) release} multiple permits at a time. 
 *
 * @since 1.5
 * @spec JSR-166
 * @revised $Date: 2003/05/27 15:50:14 $
 * @editor $Author: dl $
 *
 */
public class FairSemaphore extends Semaphore {

    /*
     * This differs from Semaphore only in that it uses a
     * FairReentrantLock.  Because the FairReentrantLock guarantees
     * FIFO queuing, we don't need to do anything fancy to prevent
     * overtaking etc.  for the multiple-permit methods. The only
     * minor downside is that multi-permit acquires will sometimes
     * repeatedly wake up finding that they must re-wait. A custom
     * solution could minimize this, at the expense of being slower
     * and more complex for the typical case.
     */

    /**
     * Construct a <tt>FiFoSemaphore</tt> with the given number of
     * permits.
     * @param permits the initial number of permits available
     */
    public FairSemaphore(long permits) { 
        super(permits, new FairReentrantLock()); 
    }

    /**
     * Acquires the given number of permits from this semaphore, 
     * blocking until all are available, 
     * or the thread is {@link Thread#interrupt interrupted}.
     *
     * <p>Acquires the given number of permits, if they are available,
     * and returns immediately,
     * reducing the number of available permits by the given amount.
     *
     * <p>If insufficient permits are available then the current thread becomes
     * disabled for thread scheduling purposes and lies dormant until
     * one of two things happens:
     * <ul>
     * <li>Some other thread invokes one of the {@link #release() release} 
     * methods for this semaphore, the current thread is next to be assigned
     * permits and the number of available permits satisfies this request; or
     * <li>Some other thread {@link Thread#interrupt interrupts} the current
     * thread.
     * </ul>
     *
     * <p>If the current thread:
     * <ul>
     * <li>has its interrupted status set on entry to this method; or
     * <li>is {@link Thread#interrupt interrupted} while waiting
     * for a permit,
     * </ul>
     * then {@link InterruptedException} is thrown and the current thread's
     * interrupted status is cleared. 
     * Any available permits are assigned to the next waiting thread as if
     * they had been made available by a call to {@link #release()}.
     *
     * @param permits the number of permits to acquire
     *
     * @throws InterruptedException if the current thread is interrupted
     * @throws IllegalArgumentException if permits less than zero.
     *
     * @see Thread#interrupt
     */
    public void acquire(long permits) throws InterruptedException {
        if (permits < 0) throw new IllegalArgumentException();

        lock.lockInterruptibly();
        try {
            while (count - permits < 0) 
                available.await();
            count -= permits;
        }
        catch (InterruptedException ie) {
            available.signal();
            throw ie;
        }
        finally {
            lock.unlock();
        }
        
    }

    /**
     * Acquires the given number of permits from this semaphore, 
     * blocking until all are available.
     *
     * <p>Acquires the given number of permits, if they are available,
     * and returns immediately,
     * reducing the number of available permits by the given amount.
     *
     * <p>If insufficient permits are available then the current thread becomes
     * disabled for thread scheduling purposes and lies dormant until
     * some other thread invokes one of the {@link #release() release} 
     * methods for this semaphore, the current thread is next to be assigned
     * permits and the number of available permits satisfies this request.
     *
     * <p>If the current thread
     * is {@link Thread#interrupt interrupted} while waiting
     * for permits then it will continue to wait and its position in the
     * queue is not affected. When the
     * thread does return from this method its interrupt status will be set.
     *
     * @param permits the number of permits to acquire
     * @throws IllegalArgumentException if permits less than zero.
     *
     */
    public void acquireUninterruptibly(long permits) {
        if (permits < 0) throw new IllegalArgumentException();

        lock.lock();
        try {
            while (count - permits < 0) 
                available.awaitUninterruptibly();
            count -= permits;
        }
        finally {
            lock.unlock();
        }
    }

    /**
     * Acquires the given number of permits from this semaphore, only if 
     * all are available at the  time of invocation.
     * <p>Acquires the given number of permits, if they are available, and 
     * returns immediately, with the value <tt>true</tt>,
     * reducing the number of available permits by the given amount.
     *
     * <p>If insufficient permits are available then this method will return
     * immediately with the value <tt>false</tt> and the number of available
     * permits is unchanged.
     *
     * @param permits the number of permits to acquire
     *
     * @return <tt>true</tt> if the permits were acquired and <tt>false</tt>
     * otherwise.
     * @throws IllegalArgumentException if permits less than zero.
     */
    public boolean tryAcquire(long permits) {
        if (permits < 0) throw new IllegalArgumentException();

        lock.lock();
        try {
            if (count - permits >= 0) {
                count -= permits;
                return true;
            }
            return false;
        }
        finally {
            lock.unlock();
        }
    }

    /**
     * Acquires the given number of permits from this semaphore, if all 
     * become available within the given waiting time and the
     * current thread has not been {@link Thread#interrupt interrupted}.
     * <p>Acquires the given number of permits, if they are available and 
     * returns immediately, with the value <tt>true</tt>,
     * reducing the number of available permits by the given amount.
     * <p>If insufficient permits are available then
     * the current thread becomes disabled for thread scheduling
     * purposes and lies dormant until one of three things happens:
     * <ul>
     * <li>Some other thread invokes one of the {@link #release() release} 
     * methods for this semaphore, the current thread is next to be assigned
     * permits and the number of available permits satisfies this request; or
     * <li>Some other thread {@link Thread#interrupt interrupts} the current
     * thread; or
     * <li>The specified waiting time elapses.
     * </ul>
     * <p>If the permits are acquired then the value <tt>true</tt> is returned.
     * <p>If the current thread:
     * <ul>
     * <li>has its interrupted status set on entry to this method; or
     * <li>is {@link Thread#interrupt interrupted} while waiting to acquire
     * the permits,
     * </ul>
     * then {@link InterruptedException} is thrown and the current thread's
     * interrupted status is cleared.
     * Any available permits are assigned to the next waiting thread as if
     * they had been made available by a call to {@link #release()}.
     *
     * <p>If the specified waiting time elapses then the value <tt>false</tt>
     * is returned.
     * The given waiting time is a best-effort lower bound. If the time is
     * less than or equal to zero, the method will not wait at all.
     * Any available permits are assigned to the next waiting thread as if
     * they had been made available by a call to {@link #release()}.
     *
     * @param permits the number of permits to acquire
     * @param timeout the maximum time to wait for the permits
     * @param granularity the time unit of the <tt>timeout</tt> argument.
     * @return <tt>true</tt> if all permits were acquired and <tt>false</tt>
     * if the waiting time elapsed before all permits were acquired.
     *
     * @throws InterruptedException if the current thread is interrupted
     * @throws IllegalArgumentException if permits less than zero.
     *
     * @see Thread#interrupt
     *
     */
    public boolean tryAcquire(long permits, long timeout, TimeUnit granularity)
        throws InterruptedException {
        if (permits < 0) throw new IllegalArgumentException();
        lock.lockInterruptibly();
        long nanos = granularity.toNanos(timeout);
        try {
            for (;;) {
                if (count - permits >= 0) {
                    count -= permits;
                    return true;
                }
                if (nanos <= 0)
                    return false;
                nanos = available.awaitNanos(nanos);
            }
        }
        catch (InterruptedException ie) {
            available.signal();
            throw ie;
        }
        finally {
            lock.unlock();
        }

    }


    /**
     * Releases the given number of permits, returning them to the semaphore.
     * <p>Releases the given number of permits, increasing the number of 
     * available permits by that amount.
     * If any threads are blocking trying to acquire permits, then the
     * one that has been waiting the longest
     * is selected and given the permits that were just released.
     * If the number of available permits satisfies that thread's request
     * then that thread is re-enabled for thread scheduling purposes; otherwise
     * the thread continues to wait. If there are still permits available
     * after the first thread's request has been satisfied, then those permits
     * are assigned to the next waiting thread. If it is satisfied then it is
     * re-enabled for thread scheduling purposes. This continues until there
     * are insufficient permits to satisfy the next waiting thread, or there
     * are no more waiting threads.
     *
     * <p>There is no requirement that a thread that releases a permit must
     * have acquired that permit by calling {@link Semaphore#acquire acquire}.
     * Correct usage of a semaphore is established by programming convention
     * in the application.
     *
     * @param permits the number of permits to release
     * @throws IllegalArgumentException if permits less than zero.
     */
    public void release(long permits) {
        if (permits < 0) throw new IllegalArgumentException();
        lock.lock();
        try {
            count += permits;
            for (int i = 0; i < permits; ++i)
                available.signal();
        }
        finally {
            lock.unlock();
        }
    }
}
Revision:	1.2
Committed:	Sat Jun 7 16:07:09 2003 UTC (21 years ago) by dl
Branch:	MAIN
CVS Tags:	JSR166_PRELIMINARY_TEST_RELEASE_1
Changes since 1.1:	+13 -30 lines
Log Message:	Simpified Javadoc account of fairness
#	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	* A semaphore guaranteeing that threads invoking any of the {@link
11	* #acquire() acquire} methods are allocated permits in the order in
12	* which their invocation of those methods was processed
13	* (first-in-first-out; FIFO). Note that FIFO ordering necessarily
14	* applies to specific internal points of execution within these
15	* methods. So, it is possible for one thread to invoke
16	* <tt>acquire</tt> before another, but reach the ordering point after
17	* the other, and similarly upon return from the method.
18	*
19	* <p>Because permits are allocated in-order, this class also provides
20	* convenience methods to {@link #acquire(long) acquire} and {@link
21	* #release(long) release} multiple permits at a time.
22	*
23	* @since 1.5
24	* @spec JSR-166
25	* @revised $Date: 2003/05/27 15:50:14 $
26	* @editor $Author: dl $
27	*
28	*/
29	public class FairSemaphore extends Semaphore {
30
31	/*
32	* This differs from Semaphore only in that it uses a
33	* FairReentrantLock. Because the FairReentrantLock guarantees
34	* FIFO queuing, we don't need to do anything fancy to prevent
35	* overtaking etc. for the multiple-permit methods. The only
36	* minor downside is that multi-permit acquires will sometimes
37	* repeatedly wake up finding that they must re-wait. A custom
38	* solution could minimize this, at the expense of being slower
39	* and more complex for the typical case.
40	*/
41
42	/**
43	* Construct a <tt>FiFoSemaphore</tt> with the given number of
44	* permits.
45	* @param permits the initial number of permits available
46	*/
47	public FairSemaphore(long permits) {
48	super(permits, new FairReentrantLock());
49	}
50
51	/**
52	* Acquires the given number of permits from this semaphore,
53	* blocking until all are available,
54	* or the thread is {@link Thread#interrupt interrupted}.
55	*
56	* <p>Acquires the given number of permits, if they are available,
57	* and returns immediately,
58	* reducing the number of available permits by the given amount.
59	*
60	* <p>If insufficient permits are available then the current thread becomes
61	* disabled for thread scheduling purposes and lies dormant until
62	* one of two things happens:
63	* <ul>
64	* <li>Some other thread invokes one of the {@link #release() release}
65	* methods for this semaphore, the current thread is next to be assigned
66	* permits and the number of available permits satisfies this request; or
67	* <li>Some other thread {@link Thread#interrupt interrupts} the current
68	* thread.
69	* </ul>
70	*
71	* <p>If the current thread:
72	* <ul>
73	* <li>has its interrupted status set on entry to this method; or
74	* <li>is {@link Thread#interrupt interrupted} while waiting
75	* for a permit,
76	* </ul>
77	* then {@link InterruptedException} is thrown and the current thread's
78	* interrupted status is cleared.
79	* Any available permits are assigned to the next waiting thread as if
80	* they had been made available by a call to {@link #release()}.
81	*
82	* @param permits the number of permits to acquire
83	*
84	* @throws InterruptedException if the current thread is interrupted
85	* @throws IllegalArgumentException if permits less than zero.
86	*
87	* @see Thread#interrupt
88	*/
89	public void acquire(long permits) throws InterruptedException {
90	if (permits < 0) throw new IllegalArgumentException();
91
92	lock.lockInterruptibly();
93	try {
94	while (count - permits < 0)
95	available.await();
96	count -= permits;
97	}
98	catch (InterruptedException ie) {
99	available.signal();
100	throw ie;
101	}
102	finally {
103	lock.unlock();
104	}
105
106	}
107
108	/**
109	* Acquires the given number of permits from this semaphore,
110	* blocking until all are available.
111	*
112	* <p>Acquires the given number of permits, if they are available,
113	* and returns immediately,
114	* reducing the number of available permits by the given amount.
115	*
116	* <p>If insufficient permits are available then the current thread becomes
117	* disabled for thread scheduling purposes and lies dormant until
118	* some other thread invokes one of the {@link #release() release}
119	* methods for this semaphore, the current thread is next to be assigned
120	* permits and the number of available permits satisfies this request.
121	*
122	* <p>If the current thread
123	* is {@link Thread#interrupt interrupted} while waiting
124	* for permits then it will continue to wait and its position in the
125	* queue is not affected. When the
126	* thread does return from this method its interrupt status will be set.
127	*
128	* @param permits the number of permits to acquire
129	* @throws IllegalArgumentException if permits less than zero.
130	*
131	*/
132	public void acquireUninterruptibly(long permits) {
133	if (permits < 0) throw new IllegalArgumentException();
134
135	lock.lock();
136	try {
137	while (count - permits < 0)
138	available.awaitUninterruptibly();
139	count -= permits;
140	}
141	finally {
142	lock.unlock();
143	}
144	}
145
146	/**
147	* Acquires the given number of permits from this semaphore, only if
148	* all are available at the time of invocation.
149	* <p>Acquires the given number of permits, if they are available, and
150	* returns immediately, with the value <tt>true</tt>,
151	* reducing the number of available permits by the given amount.
152	*
153	* <p>If insufficient permits are available then this method will return
154	* immediately with the value <tt>false</tt> and the number of available
155	* permits is unchanged.
156	*
157	* @param permits the number of permits to acquire
158	*
159	* @return <tt>true</tt> if the permits were acquired and <tt>false</tt>
160	* otherwise.
161	* @throws IllegalArgumentException if permits less than zero.
162	*/
163	public boolean tryAcquire(long permits) {
164	if (permits < 0) throw new IllegalArgumentException();
165
166	lock.lock();
167	try {
168	if (count - permits >= 0) {
169	count -= permits;
170	return true;
171	}
172	return false;
173	}
174	finally {
175	lock.unlock();
176	}
177	}
178
179	/**
180	* Acquires the given number of permits from this semaphore, if all
181	* become available within the given waiting time and the
182	* current thread has not been {@link Thread#interrupt interrupted}.
183	* <p>Acquires the given number of permits, if they are available and
184	* returns immediately, with the value <tt>true</tt>,
185	* reducing the number of available permits by the given amount.
186	* <p>If insufficient permits are available then
187	* the current thread becomes disabled for thread scheduling
188	* purposes and lies dormant until one of three things happens:
189	* <ul>
190	* <li>Some other thread invokes one of the {@link #release() release}
191	* methods for this semaphore, the current thread is next to be assigned
192	* permits and the number of available permits satisfies this request; or
193	* <li>Some other thread {@link Thread#interrupt interrupts} the current
194	* thread; or
195	* <li>The specified waiting time elapses.
196	* </ul>
197	* <p>If the permits are acquired then the value <tt>true</tt> is returned.
198	* <p>If the current thread:
199	* <ul>
200	* <li>has its interrupted status set on entry to this method; or
201	* <li>is {@link Thread#interrupt interrupted} while waiting to acquire
202	* the permits,
203	* </ul>
204	* then {@link InterruptedException} is thrown and the current thread's
205	* interrupted status is cleared.
206	* Any available permits are assigned to the next waiting thread as if
207	* they had been made available by a call to {@link #release()}.
208	*
209	* <p>If the specified waiting time elapses then the value <tt>false</tt>
210	* is returned.
211	* The given waiting time is a best-effort lower bound. If the time is
212	* less than or equal to zero, the method will not wait at all.
213	* Any available permits are assigned to the next waiting thread as if
214	* they had been made available by a call to {@link #release()}.
215	*
216	* @param permits the number of permits to acquire
217	* @param timeout the maximum time to wait for the permits
218	* @param granularity the time unit of the <tt>timeout</tt> argument.
219	* @return <tt>true</tt> if all permits were acquired and <tt>false</tt>
220	* if the waiting time elapsed before all permits were acquired.
221	*
222	* @throws InterruptedException if the current thread is interrupted
223	* @throws IllegalArgumentException if permits less than zero.
224	*
225	* @see Thread#interrupt
226	*
227	*/
228	public boolean tryAcquire(long permits, long timeout, TimeUnit granularity)
229	throws InterruptedException {
230	if (permits < 0) throw new IllegalArgumentException();
231	lock.lockInterruptibly();
232	long nanos = granularity.toNanos(timeout);
233	try {
234	for (;;) {
235	if (count - permits >= 0) {
236	count -= permits;
237	return true;
238	}
239	if (nanos <= 0)
240	return false;
241	nanos = available.awaitNanos(nanos);
242	}
243	}
244	catch (InterruptedException ie) {
245	available.signal();
246	throw ie;
247	}
248	finally {
249	lock.unlock();
250	}
251
252	}
253
254
255
256	/**
257	* Releases the given number of permits, returning them to the semaphore.
258	* <p>Releases the given number of permits, increasing the number of
259	* available permits by that amount.
260	* If any threads are blocking trying to acquire permits, then the
261	* one that has been waiting the longest
262	* is selected and given the permits that were just released.
263	* If the number of available permits satisfies that thread's request
264	* then that thread is re-enabled for thread scheduling purposes; otherwise
265	* the thread continues to wait. If there are still permits available
266	* after the first thread's request has been satisfied, then those permits
267	* are assigned to the next waiting thread. If it is satisfied then it is
268	* re-enabled for thread scheduling purposes. This continues until there
269	* are insufficient permits to satisfy the next waiting thread, or there
270	* are no more waiting threads.
271	*
272	* <p>There is no requirement that a thread that releases a permit must
273	* have acquired that permit by calling {@link Semaphore#acquire acquire}.
274	* Correct usage of a semaphore is established by programming convention
275	* in the application.
276	*
277	* @param permits the number of permits to release
278	* @throws IllegalArgumentException if permits less than zero.
279	*/
280	public void release(long permits) {
281	if (permits < 0) throw new IllegalArgumentException();
282	lock.lock();
283	try {
284	count += permits;
285	for (int i = 0; i < permits; ++i)
286	available.signal();
287	}
288	finally {
289	lock.unlock();
290	}
291	}
292	}