1196 lines · 45.2 KB · Java
RawDownload
/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation.  Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ /* * This file is available under and governed by the GNU General Public * License version 2 only, as published by the Free Software Foundation. * However, the following notice accompanied the original version of this * file: * * 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/publicdomain/zero/1.0/ */ package java.util.concurrent;import java.util.concurrent.locks.*;import java.util.concurrent.atomic.*;import java.util.*; /** * A {@linkplain BlockingQueue blocking queue} in which each insert * operation must wait for a corresponding remove operation by another * thread, and vice versa.  A synchronous queue does not have any * internal capacity, not even a capacity of one.  You cannot * <tt>peek</tt> at a synchronous queue because an element is only * present when you try to remove it; you cannot insert an element * (using any method) unless another thread is trying to remove it; * you cannot iterate as there is nothing to iterate.  The * <em>head</em> of the queue is the element that the first queued * inserting thread is trying to add to the queue; if there is no such * queued thread then no element is available for removal and * <tt>poll()</tt> will return <tt>null</tt>.  For purposes of other * <tt>Collection</tt> methods (for example <tt>contains</tt>), a * <tt>SynchronousQueue</tt> acts as an empty collection.  This queue * does not permit <tt>null</tt> elements. * * <p>Synchronous queues are similar to rendezvous channels used in * CSP and Ada. They are well suited for handoff designs, in which an * object running in one thread must sync up with an object running * in another thread in order to hand it some information, event, or * task. * * <p> This class supports an optional fairness policy for ordering * waiting producer and consumer threads.  By default, this ordering * is not guaranteed. However, a queue constructed with fairness set * to <tt>true</tt> grants threads access in FIFO order. * * <p>This class and its iterator implement all of the * <em>optional</em> methods of the {@link Collection} and {@link * Iterator} interfaces. * * <p>This class is a member of the * <a href="{@docRoot}/../technotes/guides/collections/index.html"> * Java Collections Framework</a>. * * @since 1.5 * @author Doug Lea and Bill Scherer and Michael Scott * @param <E> the type of elements held in this collection */public class SynchronousQueue<E> extends AbstractQueue<E>    implements BlockingQueue<E>, java.io.Serializable {    private static final long serialVersionUID = -3223113410248163686L;     /*     * This class implements extensions of the dual stack and dual     * queue algorithms 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 (see also     * http://www.cs.rochester.edu/u/scott/synchronization/pseudocode/duals.html).     * The (Lifo) stack is used for non-fair mode, and the (Fifo)     * queue for fair mode. The performance of the two is generally     * similar. Fifo usually supports higher throughput under     * contention but Lifo maintains higher thread locality in common     * applications.     *     * A dual queue (and similarly stack) is one that at any given     * time either holds "data" -- items provided by put operations,     * or "requests" -- slots representing take operations, or is     * empty. A call to "fulfill" (i.e., a call requesting an item     * from a queue holding data or vice versa) dequeues a     * complementary node.  The most interesting feature of these     * queues is that any operation can figure out which mode the     * queue is in, and act accordingly without needing locks.     *     * Both the queue and stack extend abstract class Transferer     * defining the single method transfer that does a put or a     * take. These are unified into a single method because in dual     * data structures, the put and take operations are symmetrical,     * so nearly all code can be combined. The resulting transfer     * methods are on the long side, but are easier to follow than     * they would be if broken up into nearly-duplicated parts.     *     * The queue and stack data structures share many conceptual     * similarities but very few concrete details. For simplicity,     * they are kept distinct so that they can later evolve     * separately.     *     * The algorithms here differ from the versions in the above paper     * in extending them for use in synchronous queues, as well as     * dealing with cancellation. The main differences include:     *     *  1. The original algorithms used bit-marked pointers, but     *     the ones here use mode bits in nodes, leading to a number     *     of further adaptations.     *  2. SynchronousQueues must block threads waiting to become     *     fulfilled.     *  3. Support for cancellation via timeout and interrupts,     *     including cleaning out cancelled nodes/threads     *     from lists to avoid garbage retention and memory depletion.     *     * Blocking is mainly accomplished using LockSupport park/unpark,     * except that nodes that appear to be the next ones to become     * fulfilled first spin a bit (on multiprocessors only). On very     * busy synchronous queues, spinning can dramatically improve     * throughput. And on less busy ones, the amount of spinning is     * small enough not to be noticeable.     *     * Cleaning is done in different ways in queues vs stacks.  For     * queues, we can almost always remove a node immediately in O(1)     * time (modulo retries for consistency checks) when it is     * cancelled. But if it may be pinned as the current tail, it must     * wait until some subsequent cancellation. For stacks, we need a     * potentially O(n) traversal to be sure that we can remove the     * node, but this can run concurrently with other threads     * accessing the stack.     *     * While garbage collection takes care of most node reclamation     * issues that otherwise complicate nonblocking algorithms, care     * is taken to "forget" references to data, other nodes, and     * threads that might be held on to long-term by blocked     * threads. In cases where setting to null would otherwise     * conflict with main algorithms, this is done by changing a     * node's link to now point to the node itself. This doesn't arise     * much for Stack nodes (because blocked threads do not hang on to     * old head pointers), but references in Queue nodes must be     * aggressively forgotten to avoid reachability of everything any     * node has ever referred to since arrival.     */     /**     * Shared internal API for dual stacks and queues.     */    abstract static class Transferer {        /**         * Performs a put or take.         *         * @param e if non-null, the item to be handed to a consumer;         *          if null, requests that transfer return an item         *          offered by producer.         * @param timed if this operation should timeout         * @param nanos the timeout, in nanoseconds         * @return if non-null, the item provided or received; if null,         *         the operation failed due to timeout or interrupt --         *         the caller can distinguish which of these occurred         *         by checking Thread.interrupted.         */        abstract Object transfer(Object e, boolean timed, long nanos);    }     /** The number of CPUs, for spin control */    static final int NCPUS = Runtime.getRuntime().availableProcessors();     /**     * The number of times to spin before blocking in timed waits.     * The value is empirically derived -- it works well across a     * variety of processors and OSes. Empirically, the best value     * seems not to vary with number of CPUs (beyond 2) so is just     * a constant.     */    static final int maxTimedSpins = (NCPUS < 2) ? 0 : 32;     /**     * The number of times to spin before blocking in untimed waits.     * This is greater than timed value because untimed waits spin     * faster since they don't need to check times on each spin.     */    static final int maxUntimedSpins = maxTimedSpins * 16;     /**     * The number of nanoseconds for which it is faster to spin     * rather than to use timed park. A rough estimate suffices.     */    static final long spinForTimeoutThreshold = 1000L;     /** Dual stack */    static final class TransferStack extends Transferer {        /*         * This extends Scherer-Scott dual stack algorithm, differing,         * among other ways, by using "covering" nodes rather than         * bit-marked pointers: Fulfilling operations push on marker         * nodes (with FULFILLING bit set in mode) to reserve a spot         * to match a waiting node.         */         /* Modes for SNodes, ORed together in node fields */        /** Node represents an unfulfilled consumer */        static final int REQUEST    = 0;        /** Node represents an unfulfilled producer */        static final int DATA       = 1;        /** Node is fulfilling another unfulfilled DATA or REQUEST */        static final int FULFILLING = 2;         /** Return true if m has fulfilling bit set */        static boolean isFulfilling(int m) { return (m & FULFILLING) != 0; }         /** Node class for TransferStacks. */        static final class SNode {            volatile SNode next;        // next node in stack            volatile SNode match;       // the node matched to this            volatile Thread waiter;     // to control park/unpark            Object item;                // data; or null for REQUESTs            int mode;            // Note: item and mode fields don't need to be volatile            // since they are always written before, and read after,            // other volatile/atomic operations.             SNode(Object item) {                this.item = item;            }             boolean casNext(SNode cmp, SNode val) {                return cmp == next &&                    UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);            }             /**             * Tries to match node s to this node, if so, waking up thread.             * Fulfillers call tryMatch to identify their waiters.             * Waiters block until they have been matched.             *             * @param s the node to match             * @return true if successfully matched to s             */            boolean tryMatch(SNode s) {                if (match == null &&                    UNSAFE.compareAndSwapObject(this, matchOffset, null, s)) {                    Thread w = waiter;                    if (w != null) {    // waiters need at most one unpark                        waiter = null;                        LockSupport.unpark(w);                    }                    return true;                }                return match == s;            }             /**             * Tries to cancel a wait by matching node to itself.             */            void tryCancel() {                UNSAFE.compareAndSwapObject(this, matchOffset, null, this);            }             boolean isCancelled() {                return match == this;            }             // Unsafe mechanics            private static final sun.misc.Unsafe UNSAFE;            private static final long matchOffset;            private static final long nextOffset;             static {                try {                    UNSAFE = sun.misc.Unsafe.getUnsafe();                    Class k = SNode.class;                    matchOffset = UNSAFE.objectFieldOffset                        (k.getDeclaredField("match"));                    nextOffset = UNSAFE.objectFieldOffset                        (k.getDeclaredField("next"));                } catch (Exception e) {                    throw new Error(e);                }            }        }         /** The head (top) of the stack */        volatile SNode head;         boolean casHead(SNode h, SNode nh) {            return h == head &&                UNSAFE.compareAndSwapObject(this, headOffset, h, nh);        }         /**         * Creates or resets fields of a node. Called only from transfer         * where the node to push on stack is lazily created and         * reused when possible to help reduce intervals between reads         * and CASes of head and to avoid surges of garbage when CASes         * to push nodes fail due to contention.         */        static SNode snode(SNode s, Object e, SNode next, int mode) {            if (s == null) s = new SNode(e);            s.mode = mode;            s.next = next;            return s;        }         /**         * Puts or takes an item.         */        Object transfer(Object e, boolean timed, long nanos) {            /*             * Basic algorithm is to loop trying one of three actions:             *             * 1. If apparently empty or already containing nodes of same             *    mode, try to push node on stack and wait for a match,             *    returning it, or null if cancelled.             *             * 2. If apparently containing node of complementary mode,             *    try to push a fulfilling node on to stack, match             *    with corresponding waiting node, pop both from             *    stack, and return matched item. The matching or             *    unlinking might not actually be necessary because of             *    other threads performing action 3:             *             * 3. If top of stack already holds another fulfilling node,             *    help it out by doing its match and/or pop             *    operations, and then continue. The code for helping             *    is essentially the same as for fulfilling, except             *    that it doesn't return the item.             */             SNode s = null; // constructed/reused as needed            int mode = (e == null) ? REQUEST : DATA;             for (;;) {                SNode h = head;                if (h == null || h.mode == mode) {  // empty or same-mode                    if (timed && nanos <= 0) {      // can't wait                        if (h != null && h.isCancelled())                            casHead(h, h.next);     // pop cancelled node                        else                            return null;                    } else if (casHead(h, s = snode(s, e, h, mode))) {                        SNode m = awaitFulfill(s, timed, nanos);                        if (m == s) {               // wait was cancelled                            clean(s);                            return null;                        }                        if ((h = head) != null && h.next == s)                            casHead(h, s.next);     // help s's fulfiller                        return (mode == REQUEST) ? m.item : s.item;                    }                } else if (!isFulfilling(h.mode)) { // try to fulfill                    if (h.isCancelled())            // already cancelled                        casHead(h, h.next);         // pop and retry                    else if (casHead(h, s=snode(s, e, h, FULFILLING|mode))) {                        for (;;) { // loop until matched or waiters disappear                            SNode m = s.next;       // m is s's match                            if (m == null) {        // all waiters are gone                                casHead(s, null);   // pop fulfill node                                s = null;           // use new node next time                                break;              // restart main loop                            }                            SNode mn = m.next;                            if (m.tryMatch(s)) {                                casHead(s, mn);     // pop both s and m                                return (mode == REQUEST) ? m.item : s.item;                            } else                  // lost match                                s.casNext(m, mn);   // help unlink                        }                    }                } else {                            // help a fulfiller                    SNode m = h.next;               // m is h's match                    if (m == null)                  // waiter is gone                        casHead(h, null);           // pop fulfilling node                    else {                        SNode mn = m.next;                        if (m.tryMatch(h))          // help match                            casHead(h, mn);         // pop both h and m                        else                        // lost match                            h.casNext(m, mn);       // help unlink                    }                }            }        }         /**         * Spins/blocks until node s is matched by a fulfill operation.         *         * @param s the waiting node         * @param timed true if timed wait         * @param nanos timeout value         * @return matched node, or s if cancelled         */        SNode awaitFulfill(SNode s, boolean timed, long nanos) {            /*             * When a node/thread is about to block, it sets its waiter             * field and then rechecks state at least one more time             * before actually parking, thus covering race vs             * fulfiller noticing that waiter is non-null so should be             * woken.             *             * When invoked by nodes that appear at the point of call             * to be at the head of the stack, calls to park are             * preceded by spins to avoid blocking when producers and             * consumers are arriving very close in time.  This can             * happen enough to bother only on multiprocessors.             *             * The order of checks for returning out of main loop             * reflects fact that interrupts have precedence over             * normal returns, which have precedence over             * timeouts. (So, on timeout, one last check for match is             * done before giving up.) Except that calls from untimed             * SynchronousQueue.{poll/offer} don't check interrupts             * and don't wait at all, so are trapped in transfer             * method rather than calling awaitFulfill.             */            long lastTime = timed ? System.nanoTime() : 0;            Thread w = Thread.currentThread();            SNode h = head;            int spins = (shouldSpin(s) ?                         (timed ? maxTimedSpins : maxUntimedSpins) : 0);            for (;;) {                if (w.isInterrupted())                    s.tryCancel();                SNode m = s.match;                if (m != null)                    return m;                if (timed) {                    long now = System.nanoTime();                    nanos -= now - lastTime;                    lastTime = now;                    if (nanos <= 0) {                        s.tryCancel();                        continue;                    }                }                if (spins > 0)                    spins = shouldSpin(s) ? (spins-1) : 0;                else if (s.waiter == null)                    s.waiter = w; // establish waiter so can park next iter                else if (!timed)                    LockSupport.park(this);                else if (nanos > spinForTimeoutThreshold)                    LockSupport.parkNanos(this, nanos);            }        }         /**         * Returns true if node s is at head or there is an active         * fulfiller.         */        boolean shouldSpin(SNode s) {            SNode h = head;            return (h == s || h == null || isFulfilling(h.mode));        }         /**         * Unlinks s from the stack.         */        void clean(SNode s) {            s.item = null;   // forget item            s.waiter = null; // forget thread             /*             * At worst we may need to traverse entire stack to unlink             * s. If there are multiple concurrent calls to clean, we             * might not see s if another thread has already removed             * it. But we can stop when we see any node known to             * follow s. We use s.next unless it too is cancelled, in             * which case we try the node one past. We don't check any             * further because we don't want to doubly traverse just to             * find sentinel.             */             SNode past = s.next;            if (past != null && past.isCancelled())                past = past.next;             // Absorb cancelled nodes at head            SNode p;            while ((p = head) != null && p != past && p.isCancelled())                casHead(p, p.next);             // Unsplice embedded nodes

Lines 1–500 of 1196.

Keyboard shortcuts

General

Show keyboard shortcuts
?
Focus the current search
/

Issues and pull requests

Open filters
f

Issues, pull requests and Inbox

Select next item
j↓
Select previous item
k↑
Open selected item
Enter
Dismiss filters or clear selection
Esc

Repository code

Go to file
t