util/concurrent/Semaphore.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;
import java.util.concurrent.locks.*;

/**
 * A counting semaphore.  Conceptually, a semaphore maintains a set of
 * permits.  Each {@link #acquire} blocks if necessary until a permit is
 * available, and then takes it.  Each {@link #release} adds a permit,
 * potentially releasing a blocking acquirer.
 * However, no actual permit objects are used; the <tt>Semaphore</tt> just
 * keeps a count of the number available and acts accordingly.
 *
 * <p>Semaphores are used to restrict the number of threads than can
 * access some (physical or logical) resource. For example, here is
 * a class that uses a semaphore to control access to a pool of items:
 * <pre>
 * class Pool {
 *   private static final MAX_AVAILABLE = 100;
 *   private final Semaphore available = new Semaphore(MAX_AVAILABLE);
 *
 *   public Object getItem() throws InterruptedException {
 *     available.acquire();
 *     return getNextAvailableItem();
 *   }
 *
 *   public void putItem(Object x) {
 *     if (markAsUnused(x))
 *       available.release();
 *   }
 *
 *   // Not a particularly efficient data structure; just for demo
 *
 *   protected Object[] items = ... whatever kinds of items being managed
 *   protected boolean[] used = new boolean[MAX_AVAILABLE];
 *
 *   protected synchronized Object getNextAvailableItem() {
 *     for (int i = 0; i < MAX_AVAILABLE; ++i) {
 *       if (!used[i]) {
 *          used[i] = true;
 *          return items[i];
 *       }
 *     }
 *     return null; // not reached
 *   }
 *
 *   protected synchronized boolean markAsUnused(Object item) {
 *     for (int i = 0; i < MAX_AVAILABLE; ++i) {
 *       if (item == items[i]) {
 *          if (used[i]) {
 *            used[i] = false;
 *            return true;
 *          }
 *          else
 *            return false;
 *       }
 *     }
 *     return false;
 *   }
 *
 * }
 * </pre>
 * <p>Before obtaining an item each thread must acquire a permit from the
 * semaphore, guaranteeing that an item is available for use. When the
 * thread has finished with the item it is returned back to the pool and
 * a permit is returned to the semaphore, allowing another thread to
 * acquire that item.
 * Note that no synchronization lock is held when {@link #acquire} is
 * called as that would prevent an item from being returned to the pool.
 * The semaphore encapsulates the synchronization needed to restrict access to
 * the pool, separately from any synchronization needed to maintain the
 * consistency of the pool itself.
 *
 * <p>A semaphore initialized to one, and which is used such that it only
 * has at most one permit available, can serve as a mutual exclusion lock.
 * This is more
 * commonly known as a <em>binary semaphore</em>, because it only has two
 * states: one permit available, or zero permits available.
 * When used in this way, the binary semaphore has the property (unlike many
 * {@link Lock} implementations, that the &quot;lock&quot; can be released by
 * a thread other than the owner (as semaphores have no notion of ownership).
 * This can be useful in some specialised contexts, such as deadlock recovery.
 *
 * <p>This class makes no guarantees about the order in which threads
 * acquire permits. In particular, barging is permitted, that is, a thread
 * invoking {@link #acquire} can be allocated a permit ahead of a thread
 * that has been waiting. If you need more deterministic guarantees, consider
 * using {@link FairSemaphore}.
 *
 *
 * @since 1.5
 * @spec JSR-166
 * @revised $Date: 2003/06/24 14:34:49 $
 * @editor $Author: dl $
 * @author Doug Lea
 *
 */
public class Semaphore implements java.io.Serializable {
    // todo SerialID
    // uses default serialization, which happens be fine here.

    // Fields are package-private to allow the FairSemaphore variant
    // to access.

    final ReentrantLock lock;
    final Condition available;
    long count;

    /** 
     * Package-private constructor used by FairSemaphore
     * @param permits the initial number of permits available
     * @param lock the lock to use
     */
    Semaphore(long permits, ReentrantLock lock) {
        this.count = permits;
        this.lock = lock;
        available = lock.newCondition();
    }

    /**
     * Construct a <tt>Semaphore</tt> with the given number of
     * permits.
     * @param permits the initial number of permits available
     */
    public Semaphore(long permits) {
        this(permits, new ReentrantLock());
    }

    /**
     * Acquires a permit from this semaphore, blocking until one is
     * available, or the thread is {@link Thread#interrupt interrupted}.
     *
     * <p>Acquires a permit, if one is available and returns immediately,
     * reducing the number of available permits by one.
     * <p>If no permit is 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 the {@link #release} method for this
     * semaphore and the current thread happens to be chosen as the
     * thread to receive the permit; 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.
     *
     * @throws InterruptedException if the current thread is interrupted
     *
     * @see Thread#interrupt
     */
    public void acquire() throws InterruptedException {
        lock.lockInterruptibly();
        try {
            while (count <= 0) 
                available.await();
            --count;
        }
        catch (InterruptedException ie) {
            available.signal();
            throw ie;
        }
        finally {
            lock.unlock();
        }
    }

    /**
     * Acquires a permit from this semaphore, blocking until one is
     * available.
     *
     * <p>Acquires a permit, if one is available and returns immediately,
     * reducing the number of available permits by one.
     * <p>If no permit is available then the current thread becomes
     * disabled for thread scheduling purposes and lies dormant until
     * some other thread invokes the {@link #release} method for this
     * semaphore and the current thread happens to be chosen as the
     * thread to receive the permit.
     *
     * <p>If the current thread
     * is {@link Thread#interrupt interrupted} while waiting
     * for a permit then it will continue to wait, but the time at which
     * the thread is assigned a permit may change compared to the time it
     * would have received the permit had no interruption occurred. When the
     * thread does return from this method its interrupt status will be set.
     *
     */
    public void acquireUninterruptibly() {
        lock.lock();
        try {
            while (count <= 0) 
                available.awaitUninterruptibly();
            --count;
        }
        finally {
            lock.unlock();
        }
    }

    /**
     * Acquires a permit from this semaphore, only if one is available at the 
     * time of invocation.
     * <p>Acquires a permit, if one is available and returns immediately,
     * with the value <tt>true</tt>,
     * reducing the number of available permits by one.
     *
     * <p>If no permit is available then this method will return
     * immediately with the value <tt>false</tt>.
     *
     * @return <tt>true</tt> if a permit was acquired and <tt>false</tt>
     * otherwise.
     */
    public boolean tryAcquire() {
        lock.lock();
        try {
            if (count > 0) {
                --count;
                return true;
            }
            return false;
        }
        finally {
            lock.unlock();
        }
    }

    /**
     * Acquires a permit from this semaphore, if one becomes available 
     * within the given waiting time and the
     * current thread has not been {@link Thread#interrupt interrupted}.
     * <p>Acquires a permit, if one is available and returns immediately,
     * with the value <tt>true</tt>,
     * reducing the number of available permits by one.
     * <p>If no permit is 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 the {@link #release} method for this
     * semaphore and the current thread happens to be chosen as the
     * thread to receive the permit; or
     * <li>Some other thread {@link Thread#interrupt interrupts} the current
     * thread; or
     * <li>The specified waiting time elapses.
     * </ul>
     * <p>If a permit is 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
     * a permit,
     * </ul>
     * then {@link InterruptedException} is thrown and the current thread's
     * interrupted status is cleared.
     * <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.
     *
     * @param timeout the maximum time to wait for a permit
     * @param granularity the time unit of the <tt>timeout</tt> argument.
     * @return <tt>true</tt> if a permit was acquired and <tt>false</tt>
     * if the waiting time elapsed before a permit was acquired.
     *
     * @throws InterruptedException if the current thread is interrupted
     *
     * @see Thread#interrupt
     *
     */
    public boolean tryAcquire(long timeout, TimeUnit granularity)
        throws InterruptedException {
        lock.lockInterruptibly();
        long nanos = granularity.toNanos(timeout);
        try {
            for (;;) {
                if (count > 0) {
                    --count;
                    return true;
                }
                if (nanos <= 0)
                    return false;
                nanos = available.awaitNanos(nanos);
            }
        }
        catch (InterruptedException ie) {
            available.signal();
            throw ie;
        }
        finally {
            lock.unlock();
        }
    }

    /**
     * Releases a permit, returning it to the semaphore.
     * <p>Releases a permit, increasing the number of available permits
     * by one.
     * If any threads are blocking trying to acquire a permit, then one
     * is selected and given the permit that was just released.
     * That thread is re-enabled for thread scheduling purposes.
     * <p>There is no requirement that a thread that releases a permit must
     * have acquired that permit by calling {@link #acquire}.
     * Correct usage of a semaphore is established by programming convention
     * in the application.
     */
    public void release() {
        lock.lock();
        try {
            ++count;
            available.signal();
        }
        finally {
            lock.unlock();
        }
    }
        

    /**
     * Return the current number of permits available in this semaphore.
     * <p>This method is typically used for debugging and testing purposes.
     * @return the number of permits available in this semaphore.
     */
    public long availablePermits() {
        lock.lock();
        try {
            return count;
        }
        finally {
            lock.unlock();
        }
    }
}


Revision:	1.5
Committed:	Tue Jul 8 00:46:35 2003 UTC (20 years, 11 months ago) by dl
Branch:	MAIN
Changes since 1.4:	+2 -1 lines
Log Message:	Locks in subpackage; fairness params added
#	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	import java.util.concurrent.locks.*;
9
10	/**
11	* A counting semaphore. Conceptually, a semaphore maintains a set of
12	* permits. Each {@link #acquire} blocks if necessary until a permit is
13	* available, and then takes it. Each {@link #release} adds a permit,
14	* potentially releasing a blocking acquirer.
15	* However, no actual permit objects are used; the <tt>Semaphore</tt> just
16	* keeps a count of the number available and acts accordingly.
17	*
18	* <p>Semaphores are used to restrict the number of threads than can
19	* access some (physical or logical) resource. For example, here is
20	* a class that uses a semaphore to control access to a pool of items:
21	* <pre>
22	* class Pool {
23	* private static final MAX_AVAILABLE = 100;
24	* private final Semaphore available = new Semaphore(MAX_AVAILABLE);
25	*
26	* public Object getItem() throws InterruptedException {
27	* available.acquire();
28	* return getNextAvailableItem();
29	* }
30	*
31	* public void putItem(Object x) {
32	* if (markAsUnused(x))
33	* available.release();
34	* }
35	*
36	* // Not a particularly efficient data structure; just for demo
37	*
38	* protected Object[] items = ... whatever kinds of items being managed
39	* protected boolean[] used = new boolean[MAX_AVAILABLE];
40	*
41	* protected synchronized Object getNextAvailableItem() {
42	* for (int i = 0; i < MAX_AVAILABLE; ++i) {
43	* if (!used[i]) {
44	* used[i] = true;
45	* return items[i];
46	* }
47	* }
48	* return null; // not reached
49	* }
50	*
51	* protected synchronized boolean markAsUnused(Object item) {
52	* for (int i = 0; i < MAX_AVAILABLE; ++i) {
53	* if (item == items[i]) {
54	* if (used[i]) {
55	* used[i] = false;
56	* return true;
57	* }
58	* else
59	* return false;
60	* }
61	* }
62	* return false;
63	* }
64	*
65	* }
66	* </pre>
67	* <p>Before obtaining an item each thread must acquire a permit from the
68	* semaphore, guaranteeing that an item is available for use. When the
69	* thread has finished with the item it is returned back to the pool and
70	* a permit is returned to the semaphore, allowing another thread to
71	* acquire that item.
72	* Note that no synchronization lock is held when {@link #acquire} is
73	* called as that would prevent an item from being returned to the pool.
74	* The semaphore encapsulates the synchronization needed to restrict access to
75	* the pool, separately from any synchronization needed to maintain the
76	* consistency of the pool itself.
77	*
78	* <p>A semaphore initialized to one, and which is used such that it only
79	* has at most one permit available, can serve as a mutual exclusion lock.
80	* This is more
81	* commonly known as a <em>binary semaphore</em>, because it only has two
82	* states: one permit available, or zero permits available.
83	* When used in this way, the binary semaphore has the property (unlike many
84	* {@link Lock} implementations, that the "lock" can be released by
85	* a thread other than the owner (as semaphores have no notion of ownership).
86	* This can be useful in some specialised contexts, such as deadlock recovery.
87	*
88	* <p>This class makes no guarantees about the order in which threads
89	* acquire permits. In particular, barging is permitted, that is, a thread
90	* invoking {@link #acquire} can be allocated a permit ahead of a thread
91	* that has been waiting. If you need more deterministic guarantees, consider
92	* using {@link FairSemaphore}.
93	*
94	*
95	* @since 1.5
96	* @spec JSR-166
97	* @revised $Date: 2003/06/24 14:34:49 $
98	* @editor $Author: dl $
99	* @author Doug Lea
100	*
101	*/
102	public class Semaphore implements java.io.Serializable {
103	// todo SerialID
104	// uses default serialization, which happens be fine here.
105
106	// Fields are package-private to allow the FairSemaphore variant
107	// to access.
108
109	final ReentrantLock lock;
110	final Condition available;
111	long count;
112
113	/**
114	* Package-private constructor used by FairSemaphore
115	* @param permits the initial number of permits available
116	* @param lock the lock to use
117	*/
118	Semaphore(long permits, ReentrantLock lock) {
119	this.count = permits;
120	this.lock = lock;
121	available = lock.newCondition();
122	}
123
124	/**
125	* Construct a <tt>Semaphore</tt> with the given number of
126	* permits.
127	* @param permits the initial number of permits available
128	*/
129	public Semaphore(long permits) {
130	this(permits, new ReentrantLock());
131	}
132
133	/**
134	* Acquires a permit from this semaphore, blocking until one is
135	* available, or the thread is {@link Thread#interrupt interrupted}.
136	*
137	* <p>Acquires a permit, if one is available and returns immediately,
138	* reducing the number of available permits by one.
139	* <p>If no permit is available then the current thread becomes
140	* disabled for thread scheduling purposes and lies dormant until
141	* one of two things happens:
142	* <ul>
143	* <li>Some other thread invokes the {@link #release} method for this
144	* semaphore and the current thread happens to be chosen as the
145	* thread to receive the permit; or
146	* <li>Some other thread {@link Thread#interrupt interrupts} the current
147	* thread.
148	* </ul>
149	*
150	* <p>If the current thread:
151	* <ul>
152	* <li>has its interrupted status set on entry to this method; or
153	* <li>is {@link Thread#interrupt interrupted} while waiting
154	* for a permit,
155	* </ul>
156	* then {@link InterruptedException} is thrown and the current thread's
157	* interrupted status is cleared.
158	*
159	* @throws InterruptedException if the current thread is interrupted
160	*
161	* @see Thread#interrupt
162	*/
163	public void acquire() throws InterruptedException {
164	lock.lockInterruptibly();
165	try {
166	while (count <= 0)
167	available.await();
168	--count;
169	}
170	catch (InterruptedException ie) {
171	available.signal();
172	throw ie;
173	}
174	finally {
175	lock.unlock();
176	}
177	}
178
179	/**
180	* Acquires a permit from this semaphore, blocking until one is
181	* available.
182	*
183	* <p>Acquires a permit, if one is available and returns immediately,
184	* reducing the number of available permits by one.
185	* <p>If no permit is available then the current thread becomes
186	* disabled for thread scheduling purposes and lies dormant until
187	* some other thread invokes the {@link #release} method for this
188	* semaphore and the current thread happens to be chosen as the
189	* thread to receive the permit.
190	*
191	* <p>If the current thread
192	* is {@link Thread#interrupt interrupted} while waiting
193	* for a permit then it will continue to wait, but the time at which
194	* the thread is assigned a permit may change compared to the time it
195	* would have received the permit had no interruption occurred. When the
196	* thread does return from this method its interrupt status will be set.
197	*
198	*/
199	public void acquireUninterruptibly() {
200	lock.lock();
201	try {
202	while (count <= 0)
203	available.awaitUninterruptibly();
204	--count;
205	}
206	finally {
207	lock.unlock();
208	}
209	}
210
211	/**
212	* Acquires a permit from this semaphore, only if one is available at the
213	* time of invocation.
214	* <p>Acquires a permit, if one is available and returns immediately,
215	* with the value <tt>true</tt>,
216	* reducing the number of available permits by one.
217	*
218	* <p>If no permit is available then this method will return
219	* immediately with the value <tt>false</tt>.
220	*
221	* @return <tt>true</tt> if a permit was acquired and <tt>false</tt>
222	* otherwise.
223	*/
224	public boolean tryAcquire() {
225	lock.lock();
226	try {
227	if (count > 0) {
228	--count;
229	return true;
230	}
231	return false;
232	}
233	finally {
234	lock.unlock();
235	}
236	}
237
238	/**
239	* Acquires a permit from this semaphore, if one becomes available
240	* within the given waiting time and the
241	* current thread has not been {@link Thread#interrupt interrupted}.
242	* <p>Acquires a permit, if one is available and returns immediately,
243	* with the value <tt>true</tt>,
244	* reducing the number of available permits by one.
245	* <p>If no permit is available then
246	* the current thread becomes disabled for thread scheduling
247	* purposes and lies dormant until one of three things happens:
248	* <ul>
249	* <li>Some other thread invokes the {@link #release} method for this
250	* semaphore and the current thread happens to be chosen as the
251	* thread to receive the permit; or
252	* <li>Some other thread {@link Thread#interrupt interrupts} the current
253	* thread; or
254	* <li>The specified waiting time elapses.
255	* </ul>
256	* <p>If a permit is acquired then the value <tt>true</tt> is returned.
257	* <p>If the current thread:
258	* <ul>
259	* <li>has its interrupted status set on entry to this method; or
260	* <li>is {@link Thread#interrupt interrupted} while waiting to acquire
261	* a permit,
262	* </ul>
263	* then {@link InterruptedException} is thrown and the current thread's
264	* interrupted status is cleared.
265	* <p>If the specified waiting time elapses then the value <tt>false</tt>
266	* is returned.
267	* The given waiting time is a best-effort lower bound. If the time is
268	* less than or equal to zero, the method will not wait at all.
269	*
270	* @param timeout the maximum time to wait for a permit
271	* @param granularity the time unit of the <tt>timeout</tt> argument.
272	* @return <tt>true</tt> if a permit was acquired and <tt>false</tt>
273	* if the waiting time elapsed before a permit was acquired.
274	*
275	* @throws InterruptedException if the current thread is interrupted
276	*
277	* @see Thread#interrupt
278	*
279	*/
280	public boolean tryAcquire(long timeout, TimeUnit granularity)
281	throws InterruptedException {
282	lock.lockInterruptibly();
283	long nanos = granularity.toNanos(timeout);
284	try {
285	for (;;) {
286	if (count > 0) {
287	--count;
288	return true;
289	}
290	if (nanos <= 0)
291	return false;
292	nanos = available.awaitNanos(nanos);
293	}
294	}
295	catch (InterruptedException ie) {
296	available.signal();
297	throw ie;
298	}
299	finally {
300	lock.unlock();
301	}
302	}
303
304	/**
305	* Releases a permit, returning it to the semaphore.
306	* <p>Releases a permit, increasing the number of available permits
307	* by one.
308	* If any threads are blocking trying to acquire a permit, then one
309	* is selected and given the permit that was just released.
310	* That thread is re-enabled for thread scheduling purposes.
311	* <p>There is no requirement that a thread that releases a permit must
312	* have acquired that permit by calling {@link #acquire}.
313	* Correct usage of a semaphore is established by programming convention
314	* in the application.
315	*/
316	public void release() {
317	lock.lock();
318	try {
319	++count;
320	available.signal();
321	}
322	finally {
323	lock.unlock();
324	}
325	}
326
327
328	/**
329	* Return the current number of permits available in this semaphore.
330	* <p>This method is typically used for debugging and testing purposes.
331	* @return the number of permits available in this semaphore.
332	*/
333	public long availablePermits() {
334	lock.lock();
335	try {
336	return count;
337	}
338	finally {
339	lock.unlock();
340	}
341	}
342	}
343
344
345