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