util/concurrent/Exchanger.java

/*
 * Written by Doug Lea, Bill Scherer, and Michael Scott with
 * assistance from members of JCP JSR-166 Expert Group and released to
 * the public domain, as explained at
 * http://creativecommons.org/licenses/publicdomain
 */

package java.util.concurrent;
import java.util.concurrent.*; // for javadoc (till 6280605 is fixed)
import java.util.concurrent.locks.*;
import java.util.concurrent.atomic.*;
import java.util.Random;

/**
 * A synchronization point at which threads can pair and swap elements
 * within pairs.  Each thread presents some object on entry to the
 * {@link #exchange exchange} method, matches with a partner thread,
 * and receives its partner's object on return.
 *
 * <p><b>Sample Usage:</b>
 * Here are the highlights of a class that uses an <tt>Exchanger</tt> to
 * swap buffers between threads so that the thread filling the
 * buffer gets a freshly
 * emptied one when it needs it, handing off the filled one to
 * the thread emptying the buffer.
 * <pre>
 * class FillAndEmpty {
 *   Exchanger&lt;DataBuffer&gt; exchanger = new Exchanger();
 *   DataBuffer initialEmptyBuffer = ... a made-up type
 *   DataBuffer initialFullBuffer = ...
 *
 *   class FillingLoop implements Runnable {
 *     public void run() {
 *       DataBuffer currentBuffer = initialEmptyBuffer;
 *       try {
 *         while (currentBuffer != null) {
 *           addToBuffer(currentBuffer);
 *           if (currentBuffer.full())
 *             currentBuffer = exchanger.exchange(currentBuffer);
 *         }
 *       } catch (InterruptedException ex) { ... handle ... }
 *     }
 *   }
 *
 *   class EmptyingLoop implements Runnable {
 *     public void run() {
 *       DataBuffer currentBuffer = initialFullBuffer;
 *       try {
 *         while (currentBuffer != null) {
 *           takeFromBuffer(currentBuffer);
 *           if (currentBuffer.empty())
 *             currentBuffer = exchanger.exchange(currentBuffer);
 *         }
 *       } catch (InterruptedException ex) { ... handle ...}
 *     }
 *   }
 *
 *   void start() {
 *     new Thread(new FillingLoop()).start();
 *     new Thread(new EmptyingLoop()).start();
 *   }
 * }
 * </pre>
 *
 * <p>Memory consistency effects: For each pair of threads that
 * successfully exchange objects via an {@code Exchanger}, actions
 * prior to the {@code exchange()} in each thread
 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
 * those subsequent to a return from the corresponding {@code exchange()}
 * in the other thread.
 *
 * @since 1.5
 * @author Doug Lea and Bill Scherer and Michael Scott
 * @param <V> The type of objects that may be exchanged
 */
public class Exchanger<V> {
    /*
     * The underlying idea is to use a stack to hold nodes containing
     * pairs of items to be exchanged. Except that:
     *
     *  *  Only one element of the pair is known on creation by a
     *     first-arriving thread; the other is a "hole" waiting to be
     *     filled in. This is a degenerate form of the dual stacks
     *     described in "Nonblocking Concurrent Objects with Condition
     *     Synchronization",  by W. N. Scherer III and M. L. Scott.
     *     18th Annual Conf. on  Distributed Computing, Oct. 2004.
     *     It is "degenerate" in that both the items and the holes
     *     are shared in the same nodes.
     *
     *  *  There isn't really a stack here! There can't be -- if two
     *     nodes were both in the stack, they should cancel themselves
     *     out by combining. So that's what we do. The 0th element of
     *     the "arena" array serves only as the top of stack.  The
     *     remainder of the array is a form of the elimination backoff
     *     collision array described in "A Scalable Lock-free Stack
     *     Algorithm", by D. Hendler, N. Shavit, and L. Yerushalmi.
     *     16th ACM Symposium on Parallelism in Algorithms and
     *     Architectures, June 2004. Here, threads spin (using short
     *     timed waits with exponential backoff) looking for each
     *     other.  If they fail to find others waiting, they try the
     *     top spot again.  As shown in that paper, this always
     *     converges.
     *
     * The backoff elimination mechanics never come into play in
     * common usages where only two threads ever meet to exchange
     * items, but they prevent contention bottlenecks when an
     * exchanger is used by a large number of threads.
     */

    /**
     * Size of collision space. Using a size of half the number of
     * CPUs provides enough space for threads to find each other but
     * not so much that it would always require one or more to time
     * out to become unstuck. Note that the arena array holds SIZE+1
     * elements, to include the top-of-stack slot.
     */
    private static final int SIZE =
        (Runtime.getRuntime().availableProcessors() + 1) / 2;

    /**
     * Base unit in nanoseconds for backoffs. Must be a power of two.
     * Should be small because backoffs exponentially increase from
     * base.
     */
    private static final long BACKOFF_BASE = 128L;

    /**
     * Sentinel item representing cancellation.  This value is placed
     * in holes on cancellation, and used as a return value from Node
     * methods to indicate failure to set or get hole.
     */
    static final Object FAIL = new Object();

    /**
     * The collision arena. arena[0] is used as the top of the stack.
     * The remainder is used as the collision elimination space.
     * Each slot holds an AtomicReference<Node>, but this cannot be
     * expressed for arrays, so elements are casted on each use.
     */
    private final AtomicReference[] arena;

    /** Generator for random backoffs and delays. */
    private final Random random = new Random();

    /**
     * Creates a new Exchanger.
     */
    public Exchanger() {
        arena = new AtomicReference[SIZE + 1];
        for (int i = 0; i < arena.length; ++i)
            arena[i] = new AtomicReference();
    }

    /**
     * Main exchange function, handling the different policy variants.
     * Uses Object, not "V" as argument and return value to simplify
     * handling of internal sentinel values. Callers from public
     * methods cast accordingly.
     * @param item the item to exchange.
     * @param timed true if the wait is timed.
     * @param nanos if timed, the maximum wait time.
     * @return the other thread's item.
     */
    private Object doExchange(Object item, boolean timed, long nanos)
        throws InterruptedException, TimeoutException {
        Node me = new Node(item);
        long lastTime = (timed)? System.nanoTime() : 0;
        int idx = 0;     // start out at slot representing top
        int backoff = 0; // increases on failure to occupy a slot

        for (;;) {
            AtomicReference<Node> slot = (AtomicReference<Node>)arena[idx];

            // If this slot is already occupied, there is a waiting item...
            Node you = slot.get();
            if (you != null) {
                Object v = you.fillHole(item);
                slot.compareAndSet(you, null);
                if (v != FAIL)       // ... unless it was cancelled
                    return v;
            }

            // Try to occupy this slot
            if (slot.compareAndSet(null, me)) {
                // If this is top slot, use regular wait, else backoff-wait
                Object v = ((idx == 0)?
                            me.waitForHole(timed, nanos) :
                            me.waitForHole(true, randomDelay(backoff)));
                slot.compareAndSet(me, null);
                if (v != FAIL)
                    return v;
                if (Thread.interrupted())
                    throw new InterruptedException();
                if (timed) {
                    long now = System.nanoTime();
                    nanos -= now - lastTime;
                    lastTime = now;
                    if (nanos <= 0)
                        throw new TimeoutException();
                }

                me = new Node(item);      // Throw away nodes on failure
                if (backoff < SIZE - 1)   // Increase or stay saturated
                    ++backoff;
                idx = 0;                  // Restart at top
            }

            else // Retry with a random non-top slot <= backoff
                idx = 1 + random.nextInt(backoff + 1);

        }
    }

    /**
     * Returns a random delay less than (base times (2 raised to backoff))
     */
    private long randomDelay(int backoff) {
        return ((BACKOFF_BASE << backoff) - 1) & random.nextInt();
    }

    /**
     * Nodes hold partially exchanged data. This class
     * opportunistically subclasses AtomicReference to represent the
     * hole. So get() returns hole, and compareAndSet CAS'es value
     * into hole.  Note that this class cannot be parameterized as V
     * because the sentinel value FAIL is only of type Object.
     */
    static final class Node extends AtomicReference<Object> {
        private static final long serialVersionUID = -3221313401284163686L;

        /** The element offered by the Thread creating this node. */
        final Object item;
        /** The Thread creating this node. */
        final Thread waiter;

        /**
         * Creates node with given item and empty hole.
         * @param item the item.
         */
        Node(Object item) {
            this.item = item;
            waiter = Thread.currentThread();
        }

        /**
         * Tries to fill in hole. On success, wakes up the waiter.
         * @param val the value to place in hole.
         * @return on success, the item; on failure, FAIL.
         */
        Object fillHole(Object val) {
            if (compareAndSet(null, val)) {
                LockSupport.unpark(waiter);
                return item;
            }
            return FAIL;
        }

        /**
         * Waits for and gets the hole filled in by another thread.
         * Fails if timed out or interrupted before hole filled.
         * @param timed true if the wait is timed.
         * @param nanos if timed, the maximum wait time.
         * @return on success, the hole; on failure, FAIL.
         */
        Object waitForHole(boolean timed, long nanos) {
            long lastTime = (timed)? System.nanoTime() : 0;
            Object h;
            while ((h = get()) == null) {
                // If interrupted or timed out, try to cancel by
                // CASing FAIL as hole value.
                if (Thread.currentThread().isInterrupted() ||
                    (timed && nanos <= 0))
                    compareAndSet(null, FAIL);
                else if (!timed)
                    LockSupport.park();
                else {
                    LockSupport.parkNanos(nanos);
                    long now = System.nanoTime();
                    nanos -= now - lastTime;
                    lastTime = now;
                }
            }
            return h;
        }
    }

    /**
     * Waits for another thread to arrive at this exchange point (unless
     * it is {@link Thread#interrupt interrupted}),
     * and then transfers the given object to it, receiving its object
     * in return.
     *
     * <p>If another thread is already waiting at the exchange point then
     * it is resumed for thread scheduling purposes and receives the object
     * passed in by the current thread. The current thread returns immediately,
     * receiving the object passed to the exchange by that other thread.
     *
     * <p>If no other thread is already waiting at the exchange then the
     * current thread is disabled for thread scheduling purposes and lies
     * dormant until one of two things happens:
     * <ul>
     * <li>Some other thread enters the exchange; 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 the exchange,
     * </ul>
     * then {@link InterruptedException} is thrown and the current thread's
     * interrupted status is cleared.
     *
     * @param x the object to exchange
     * @return the object provided by the other thread.
     * @throws InterruptedException if current thread was interrupted
     * while waiting
     */
    public V exchange(V x) throws InterruptedException {
        try {
            return (V)doExchange(x, false, 0);
        } catch (TimeoutException cannotHappen) {
            throw new Error(cannotHappen);
        }
    }

    /**
     * Waits for another thread to arrive at this exchange point (unless
     * it is {@link Thread#interrupt interrupted}, or the specified waiting
     * time elapses),
     * and then transfers the given object to it, receiving its object
     * in return.
     *
     * <p>If another thread is already waiting at the exchange point then
     * it is resumed for thread scheduling purposes and receives the object
     * passed in by the current thread. The current thread returns immediately,
     * receiving the object passed to the exchange by that other thread.
     *
     * <p>If no other thread is already waiting at the exchange then the
     * current thread is disabled for thread scheduling purposes and lies
     * dormant until one of three things happens:
     * <ul>
     * <li>Some other thread enters the exchange; or
     * <li>Some other thread {@link Thread#interrupt interrupts} the current
     * thread; or
     * <li>The specified waiting time elapses.
     * </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 the exchange,
     * </ul>
     * then {@link InterruptedException} is thrown and the current thread's
     * interrupted status is cleared.
     *
     * <p>If the specified waiting time elapses then {@link TimeoutException}
     * is thrown.
     * If the time is
     * less than or equal to zero, the method will not wait at all.
     *
     * @param x the object to exchange
     * @param timeout the maximum time to wait
     * @param unit the time unit of the <tt>timeout</tt> argument.
     * @return the object provided by the other thread.
     * @throws InterruptedException if current thread was interrupted
     * while waiting
     * @throws TimeoutException if the specified waiting time elapses before
     * another thread enters the exchange.
     */
    public V exchange(V x, long timeout, TimeUnit unit)
        throws InterruptedException, TimeoutException {
        return (V)doExchange(x, true, unit.toNanos(timeout));
    }
}
Revision:	1.28
Committed:	Wed Sep 14 23:48:52 2005 UTC (18 years, 8 months ago) by dl
Branch:	MAIN
Changes since 1.27:	+4 -4 lines
Log Message:	Clarify class summary
#	Content
1	/*
2	* Written by Doug Lea, Bill Scherer, and Michael Scott with
3	* assistance from members of JCP JSR-166 Expert Group and released to
4	* the public domain, as explained at
5	* http://creativecommons.org/licenses/publicdomain
6	*/
7
8	package java.util.concurrent;
9	import java.util.concurrent.*; // for javadoc (till 6280605 is fixed)
10	import java.util.concurrent.locks.*;
11	import java.util.concurrent.atomic.*;
12	import java.util.Random;
13
14	/**
15	* A synchronization point at which threads can pair and swap elements
16	* within pairs. Each thread presents some object on entry to the
17	* {@link #exchange exchange} method, matches with a partner thread,
18	* and receives its partner's object on return.
19	*
20	* <p><b>Sample Usage:</b>
21	* Here are the highlights of a class that uses an <tt>Exchanger</tt> to
22	* swap buffers between threads so that the thread filling the
23	* buffer gets a freshly
24	* emptied one when it needs it, handing off the filled one to
25	* the thread emptying the buffer.
26	* <pre>
27	* class FillAndEmpty {
28	* Exchanger<DataBuffer> exchanger = new Exchanger();
29	* DataBuffer initialEmptyBuffer = ... a made-up type
30	* DataBuffer initialFullBuffer = ...
31	*
32	* class FillingLoop implements Runnable {
33	* public void run() {
34	* DataBuffer currentBuffer = initialEmptyBuffer;
35	* try {
36	* while (currentBuffer != null) {
37	* addToBuffer(currentBuffer);
38	* if (currentBuffer.full())
39	* currentBuffer = exchanger.exchange(currentBuffer);
40	* }
41	* } catch (InterruptedException ex) { ... handle ... }
42	* }
43	* }
44	*
45	* class EmptyingLoop implements Runnable {
46	* public void run() {
47	* DataBuffer currentBuffer = initialFullBuffer;
48	* try {
49	* while (currentBuffer != null) {
50	* takeFromBuffer(currentBuffer);
51	* if (currentBuffer.empty())
52	* currentBuffer = exchanger.exchange(currentBuffer);
53	* }
54	* } catch (InterruptedException ex) { ... handle ...}
55	* }
56	* }
57	*
58	* void start() {
59	* new Thread(new FillingLoop()).start();
60	* new Thread(new EmptyingLoop()).start();
61	* }
62	* }
63	* </pre>
64	*
65	* <p>Memory consistency effects: For each pair of threads that
66	* successfully exchange objects via an {@code Exchanger}, actions
67	* prior to the {@code exchange()} in each thread
68	* <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
69	* those subsequent to a return from the corresponding {@code exchange()}
70	* in the other thread.
71	*
72	* @since 1.5
73	* @author Doug Lea and Bill Scherer and Michael Scott
74	* @param <V> The type of objects that may be exchanged
75	*/
76	public class Exchanger<V> {
77	/*
78	* The underlying idea is to use a stack to hold nodes containing
79	* pairs of items to be exchanged. Except that:
80	*
81	* * Only one element of the pair is known on creation by a
82	* first-arriving thread; the other is a "hole" waiting to be
83	* filled in. This is a degenerate form of the dual stacks
84	* described in "Nonblocking Concurrent Objects with Condition
85	* Synchronization", by W. N. Scherer III and M. L. Scott.
86	* 18th Annual Conf. on Distributed Computing, Oct. 2004.
87	* It is "degenerate" in that both the items and the holes
88	* are shared in the same nodes.
89	*
90	* * There isn't really a stack here! There can't be -- if two
91	* nodes were both in the stack, they should cancel themselves
92	* out by combining. So that's what we do. The 0th element of
93	* the "arena" array serves only as the top of stack. The
94	* remainder of the array is a form of the elimination backoff
95	* collision array described in "A Scalable Lock-free Stack
96	* Algorithm", by D. Hendler, N. Shavit, and L. Yerushalmi.
97	* 16th ACM Symposium on Parallelism in Algorithms and
98	* Architectures, June 2004. Here, threads spin (using short
99	* timed waits with exponential backoff) looking for each
100	* other. If they fail to find others waiting, they try the
101	* top spot again. As shown in that paper, this always
102	* converges.
103	*
104	* The backoff elimination mechanics never come into play in
105	* common usages where only two threads ever meet to exchange
106	* items, but they prevent contention bottlenecks when an
107	* exchanger is used by a large number of threads.
108	*/
109
110	/**
111	* Size of collision space. Using a size of half the number of
112	* CPUs provides enough space for threads to find each other but
113	* not so much that it would always require one or more to time
114	* out to become unstuck. Note that the arena array holds SIZE+1
115	* elements, to include the top-of-stack slot.
116	*/
117	private static final int SIZE =
118	(Runtime.getRuntime().availableProcessors() + 1) / 2;
119
120	/**
121	* Base unit in nanoseconds for backoffs. Must be a power of two.
122	* Should be small because backoffs exponentially increase from
123	* base.
124	*/
125	private static final long BACKOFF_BASE = 128L;
126
127	/**
128	* Sentinel item representing cancellation. This value is placed
129	* in holes on cancellation, and used as a return value from Node
130	* methods to indicate failure to set or get hole.
131	*/
132	static final Object FAIL = new Object();
133
134	/**
135	* The collision arena. arena[0] is used as the top of the stack.
136	* The remainder is used as the collision elimination space.
137	* Each slot holds an AtomicReference<Node>, but this cannot be
138	* expressed for arrays, so elements are casted on each use.
139	*/
140	private final AtomicReference[] arena;
141
142	/** Generator for random backoffs and delays. */
143	private final Random random = new Random();
144
145	/**
146	* Creates a new Exchanger.
147	*/
148	public Exchanger() {
149	arena = new AtomicReference[SIZE + 1];
150	for (int i = 0; i < arena.length; ++i)
151	arena[i] = new AtomicReference();
152	}
153
154	/**
155	* Main exchange function, handling the different policy variants.
156	* Uses Object, not "V" as argument and return value to simplify
157	* handling of internal sentinel values. Callers from public
158	* methods cast accordingly.
159	* @param item the item to exchange.
160	* @param timed true if the wait is timed.
161	* @param nanos if timed, the maximum wait time.
162	* @return the other thread's item.
163	*/
164	private Object doExchange(Object item, boolean timed, long nanos)
165	throws InterruptedException, TimeoutException {
166	Node me = new Node(item);
167	long lastTime = (timed)? System.nanoTime() : 0;
168	int idx = 0; // start out at slot representing top
169	int backoff = 0; // increases on failure to occupy a slot
170
171	for (;;) {
172	AtomicReference<Node> slot = (AtomicReference<Node>)arena[idx];
173
174	// If this slot is already occupied, there is a waiting item...
175	Node you = slot.get();
176	if (you != null) {
177	Object v = you.fillHole(item);
178	slot.compareAndSet(you, null);
179	if (v != FAIL) // ... unless it was cancelled
180	return v;
181	}
182
183	// Try to occupy this slot
184	if (slot.compareAndSet(null, me)) {
185	// If this is top slot, use regular wait, else backoff-wait
186	Object v = ((idx == 0)?
187	me.waitForHole(timed, nanos) :
188	me.waitForHole(true, randomDelay(backoff)));
189	slot.compareAndSet(me, null);
190	if (v != FAIL)
191	return v;
192	if (Thread.interrupted())
193	throw new InterruptedException();
194	if (timed) {
195	long now = System.nanoTime();
196	nanos -= now - lastTime;
197	lastTime = now;
198	if (nanos <= 0)
199	throw new TimeoutException();
200	}
201
202	me = new Node(item); // Throw away nodes on failure
203	if (backoff < SIZE - 1) // Increase or stay saturated
204	++backoff;
205	idx = 0; // Restart at top
206	}
207
208	else // Retry with a random non-top slot <= backoff
209	idx = 1 + random.nextInt(backoff + 1);
210
211	}
212	}
213
214	/**
215	* Returns a random delay less than (base times (2 raised to backoff))
216	*/
217	private long randomDelay(int backoff) {
218	return ((BACKOFF_BASE << backoff) - 1) & random.nextInt();
219	}
220
221	/**
222	* Nodes hold partially exchanged data. This class
223	* opportunistically subclasses AtomicReference to represent the
224	* hole. So get() returns hole, and compareAndSet CAS'es value
225	* into hole. Note that this class cannot be parameterized as V
226	* because the sentinel value FAIL is only of type Object.
227	*/
228	static final class Node extends AtomicReference<Object> {
229	private static final long serialVersionUID = -3221313401284163686L;
230
231	/** The element offered by the Thread creating this node. */
232	final Object item;
233	/** The Thread creating this node. */
234	final Thread waiter;
235
236	/**
237	* Creates node with given item and empty hole.
238	* @param item the item.
239	*/
240	Node(Object item) {
241	this.item = item;
242	waiter = Thread.currentThread();
243	}
244
245	/**
246	* Tries to fill in hole. On success, wakes up the waiter.
247	* @param val the value to place in hole.
248	* @return on success, the item; on failure, FAIL.
249	*/
250	Object fillHole(Object val) {
251	if (compareAndSet(null, val)) {
252	LockSupport.unpark(waiter);
253	return item;
254	}
255	return FAIL;
256	}
257
258	/**
259	* Waits for and gets the hole filled in by another thread.
260	* Fails if timed out or interrupted before hole filled.
261	* @param timed true if the wait is timed.
262	* @param nanos if timed, the maximum wait time.
263	* @return on success, the hole; on failure, FAIL.
264	*/
265	Object waitForHole(boolean timed, long nanos) {
266	long lastTime = (timed)? System.nanoTime() : 0;
267	Object h;
268	while ((h = get()) == null) {
269	// If interrupted or timed out, try to cancel by
270	// CASing FAIL as hole value.
271	if (Thread.currentThread().isInterrupted() \|\|
272	(timed && nanos <= 0))
273	compareAndSet(null, FAIL);
274	else if (!timed)
275	LockSupport.park();
276	else {
277	LockSupport.parkNanos(nanos);
278	long now = System.nanoTime();
279	nanos -= now - lastTime;
280	lastTime = now;
281	}
282	}
283	return h;
284	}
285	}
286
287	/**
288	* Waits for another thread to arrive at this exchange point (unless
289	* it is {@link Thread#interrupt interrupted}),
290	* and then transfers the given object to it, receiving its object
291	* in return.
292	*
293	* <p>If another thread is already waiting at the exchange point then
294	* it is resumed for thread scheduling purposes and receives the object
295	* passed in by the current thread. The current thread returns immediately,
296	* receiving the object passed to the exchange by that other thread.
297	*
298	* <p>If no other thread is already waiting at the exchange then the
299	* current thread is disabled for thread scheduling purposes and lies
300	* dormant until one of two things happens:
301	* <ul>
302	* <li>Some other thread enters the exchange; or
303	* <li>Some other thread {@link Thread#interrupt interrupts} the current
304	* thread.
305	* </ul>
306	* <p>If the current thread:
307	* <ul>
308	* <li>has its interrupted status set on entry to this method; or
309	* <li>is {@link Thread#interrupt interrupted} while waiting
310	* for the exchange,
311	* </ul>
312	* then {@link InterruptedException} is thrown and the current thread's
313	* interrupted status is cleared.
314	*
315	* @param x the object to exchange
316	* @return the object provided by the other thread.
317	* @throws InterruptedException if current thread was interrupted
318	* while waiting
319	*/
320	public V exchange(V x) throws InterruptedException {
321	try {
322	return (V)doExchange(x, false, 0);
323	} catch (TimeoutException cannotHappen) {
324	throw new Error(cannotHappen);
325	}
326	}
327
328	/**
329	* Waits for another thread to arrive at this exchange point (unless
330	* it is {@link Thread#interrupt interrupted}, or the specified waiting
331	* time elapses),
332	* and then transfers the given object to it, receiving its object
333	* in return.
334	*
335	* <p>If another thread is already waiting at the exchange point then
336	* it is resumed for thread scheduling purposes and receives the object
337	* passed in by the current thread. The current thread returns immediately,
338	* receiving the object passed to the exchange by that other thread.
339	*
340	* <p>If no other thread is already waiting at the exchange then the
341	* current thread is disabled for thread scheduling purposes and lies
342	* dormant until one of three things happens:
343	* <ul>
344	* <li>Some other thread enters the exchange; or
345	* <li>Some other thread {@link Thread#interrupt interrupts} the current
346	* thread; or
347	* <li>The specified waiting time elapses.
348	* </ul>
349	* <p>If the current thread:
350	* <ul>
351	* <li>has its interrupted status set on entry to this method; or
352	* <li>is {@link Thread#interrupt interrupted} while waiting
353	* for the exchange,
354	* </ul>
355	* then {@link InterruptedException} is thrown and the current thread's
356	* interrupted status is cleared.
357	*
358	* <p>If the specified waiting time elapses then {@link TimeoutException}
359	* is thrown.
360	* If the time is
361	* less than or equal to zero, the method will not wait at all.
362	*
363	* @param x the object to exchange
364	* @param timeout the maximum time to wait
365	* @param unit the time unit of the <tt>timeout</tt> argument.
366	* @return the object provided by the other thread.
367	* @throws InterruptedException if current thread was interrupted
368	* while waiting
369	* @throws TimeoutException if the specified waiting time elapses before
370	* another thread enters the exchange.
371	*/
372	public V exchange(V x, long timeout, TimeUnit unit)
373	throws InterruptedException, TimeoutException {
374	return (V)doExchange(x, true, unit.toNanos(timeout));
375	}
376	}