ConcurrentLinkedQueue full use of the atomic package implementation has created a non-thread-safe lock concurrent queue too. Contrast to the lock mechanism to achieve the individual that the use of non-locking mechanism is difficult to give full consideration to the coordination between threads. Simply means that multiple threads access the internal data structure, if one thread is executed halfway for some reason fails, the other thread is able to detect and help complete the remaining operations. This requires the operation of the data structure is divided into many fine state or stage, to consider the status of each stage or multi-threaded visit will happen. The difficulty in this analysis, concurrent implementation of Queue has a good description. First, take a look at some of its source code:

public class ConcurrentLinkedQueue<E> extends AbstractQueue<E>
        implements Queue<E>, java.io.Serializable {
    private static final long serialVersionUID = 196745693267521676L;

    private static class Node<E> {
        private volatile E item;
        private volatile Node<E> next;

        private static final
            AtomicReferenceFieldUpdater<Node, Node>
            nextUpdater =
            AtomicReferenceFieldUpdater.newUpdater
            (Node.class, Node.class, "next");
        private static final
            AtomicReferenceFieldUpdater<Node, Object>
            itemUpdater =
            AtomicReferenceFieldUpdater.newUpdater
            (Node.class, Object.class, "item");

        Node(E x) { item = x; }

        Node(E x, Node<E> n) { item = x; next = n; }

        E getItem() {
            return item;
        }

        boolean casItem(E cmp, E val) {
            return itemUpdater.compareAndSet(this, cmp, val);
        }

        void setItem(E val) {
            itemUpdater.set(this, val);
        }

        Node<E> getNext() {
            return next;
        }

        boolean casNext(Node<E> cmp, Node<E> val) {
            return nextUpdater.compareAndSet(this, cmp, val);
        }

        void setNext(Node<E> val) {
            nextUpdater.set(this, val);
        }

    }

    private static final
        AtomicReferenceFieldUpdater<ConcurrentLinkedQueue, Node>
        tailUpdater =
        AtomicReferenceFieldUpdater.newUpdater
        (ConcurrentLinkedQueue.class, Node.class, "tail");
    private static final
        AtomicReferenceFieldUpdater<ConcurrentLinkedQueue, Node>
        headUpdater =
        AtomicReferenceFieldUpdater.newUpdater
        (ConcurrentLinkedQueue.class,  Node.class, "head");

    private boolean casTail(Node<E> cmp, Node<E> val) {
        return tailUpdater.compareAndSet(this, cmp, val);
    }

    private boolean casHead(Node<E> cmp, Node<E> val) {
        return headUpdater.compareAndSet(this, cmp, val);
    }

    private transient volatile Node<E> head = new Node<E>(null, null);

    private transient volatile Node<E> tail = head;
    ...
}

Take a look at its internal data structure Node implementation. Due to the use of atomic field updater AtomicReferenceFieldUpdater <T,V> (where T, said the type of the class to hold the field, V said the type of the field), so the corresponding fields need to be updated to use volatile to the statement. Its newUpdater (Class <U> tclass, Class <W> vclass, String fieldName) method instantiates a specific field update, parameter, respectively: the need to update the field to hold classes, field classes, to update the the field's name. Node's internal variable item, next field, respectively, corresponding to its own updater, and includes the method of its atomic operations compareAndSet (T obj, V expect, V update), where T is the field is set to hold the object , the latter two are expected and the new value.

For ConcurrentLinkedQueue itself there are two volatile thread shared variable: head, tail corresponding to the queue head pointer and tail pointer. To guarantee that this queue thread-safe is to ensure that these two Node references to access (update, view) of Atomic and visibility, due to volatile to guarantee the visibility of their own, so is the nature of its atomic changes to be guaranteed. The following method is to look at how their corresponding completion.

    public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
        Node<E> n = new Node<E>(e, null);
        for (;;) {
            Node<E> t = tail;
            Node<E> s = t.getNext();
            if (t == tail) { //------------------------------a
                if (s == null) { //---------------------------b
                    if (t.casNext(s, n)) { //-------------------c
                        casTail(t, n); //------------------------d
                        return true;
                    }
                } else {
                    casTail(t, s); //----------------------------e
                }
            }
        }
    }

offer () method are very familiar with, that is, into the team operation. Involve a change in the operation of the end of the pointer, so this method depends on whether the guarantee to achieve atomicity. CAS operation with the cycle is to ensure atomic operations, there is no exception. Within the cycle of this method to obtain a tail pointer and its next point of the object, the next due to tail, and Node are volatile, so the difference is to ensure access to the latest value.
Code a: t == tail is the top-level co-ordination, if the other thread changed the tail of the reference, then the tail is not up to date to obtain a pointer to re-cycle to get the latest value.
Code b: s == null judgments. Stationary state tail pointing to the next must be null, but under the multi-threading is another state that is intermediate state: tail of the point has not changed, but the next point to the new node has been that the tail reference to changes after the completion of the state, which When s! = null. Here is a typical application of coordination, direct access to the code e to coordinate state participation in the middle of the thread to complete the final update, and then re-cycle to acquire new tail start their new round into the team attempts. Also noteworthy was the a, b, between the other threads may change the tail of the point, making a coordinated operation failed. This step can be seen from the lock-free implementation complexity.
Code c: t.casNext (s, n) is the first step into the team because the team needs into two steps: Update Node's next, changing the tail of the point. Code c may occur before the reference point to change the tail or into the middle of updating state, neither of these facts would make the t point to elements of the next property is the atom changed, no longer point to null. Then the code c operation failed, re-enter the loop.
Code d: This is the final step to complete the update, that is updated tail of the direction, coordination of the most interesting here, there has been embodied. From the code to see casTail (t, n) regardless of whether the success will be updated and then return true mark of success. First, it indicates that, if successful completion of two steps in this thread updated, return true is a matter of course; if casTail (t, n) unsuccessful? To make it clear that the completion of the code c represents an update into the intermediate state, code d is unsuccessful it is pointing tail changed by other threads. Means that for the other threads in terms of: they get an update in the middle state, s! = Null, enter the code e to assist the implementation of the final step of this thread, and the success of the first in this thread. Although the code in this thread so d failed, but it is due to be completed before the assistance of another thread, so return true also for granted.

Into the team through the analysis of this operation, you can clearly see that no lock to achieve a state of each of the steps and coordination between multi-threaded and work. To understand the whole process of entering a team, a team operating poll () implementation also becomes simple. Is basically similar, and nothing more than the same time, relates to the head and tail of the state, changing the head to the tail, while the coordination of care, in this small repeat. Here's what locks under its no-see visits, not just inside view even contain the coordination between threads, which is no lock to achieve a feature. Whether it contains (), size () or isEmpty (), as long as the head obtained after the first date of the Node can be very easy to achieve, after all, Node of the getNext () and getItem () returns the latest values are the corresponding. So, take a look at these methods within the first () How to obtain the latest first Node:

    Node<E> first() {
        for (;;) {
            Node<E> h = head;
            Node<E> t = tail;
            Node<E> first = h.getNext();
            if (h == head) { //---------------------------------------a
                if (h == t) { //-----------------------------------------b
                    if (first == null) //----------------------------------c
                        return null;
                    else
                        casTail(t, first); //--------------------------------d
                } else {
                    if (first.getItem() != null) //------------------------e
                        return first;
                    else // remove deleted node and continue
                        casHead(h, first); //------------------------------f
                }
            }
        }
    }

This method is trying to get the latest first non-head node of the times and in different stages of the same in the coordination of the head and tail of the update task, people feel there is no pure world of free locks work, He He.
Code a: or a top-level co-ordination, head pointing to no change in circumstances to continue the following operations. Then Hou head could only be static, because the poll () out the team against the operation of steps: the first update head pointing into the intermediate state, and then update the former head of the next of the item is null.
Code b: The reason why the case h == t independent of other circumstances (in a team poll () method, the same), mainly due to first! = Null may correspond to an update in the middle of a state, arising from intermediate The necessary condition is that the code b set up. If h == t indicated that access to begin and end the current thread pointer to point to the same node, of course, the implementation of the code b is possible that other threads will be conducted after the head or tail update.
Code c: first == null indicate update the tail did not go into the middle of the state but rather in a quiescent state, and because the tail is the head of the point to point, it returns null is the only option. However, this beautiful all are built on the code between the b and code c no other thread updates tail. If there are other threads into the team carried out the operation and at least into the intermediate state, then, h == t and the first == null are sorry the establishment, which creates the illusion of obtaining the value, in fact h.getNext () is no longer longer be null. Personally think that the code c changed if ((first = h.getNext ()) == null) will enhance the hit rate.
Code d: as long as the first! = Null (whether I modify the code or source code) This thread is to try to coordinate other thread first complete tail update, waiting for another to obtain the latest cycle of head and tail.
Code e: here first certainly is not null, tail or not does not affect the first update of the item of the acquisition, but the head of the update would be affected. If the head is being updated by another thread and enter the intermediate state, both the poll () within the else if (casHead (h, first)) success, but did not implement first.setItem (null) before. At this point the code e is satisfied, return is also the current first, but then head all the success of the first update of the item is null. So here to return to the first of the item is not necessarily the item! = Null node in the use of this method to obtain the item when the node again, the conduct must be judged, this point contains (...) methods such as in are reflected.
Code f: If the first of the item == null, then update the head pointing. An intuitive point of view it seems redundant, since a team's operation is the first head of the point to update the item is null and then update the. Another way to remove (...) But then just update the value of the item without changing the head direction, so for such a multi-threaded calls, the code f becomes very necessary in.

Such an analysis by the two methods can be extended to shared variables on the ConcurrentLinkedQueue implementation of other operations, so that the lock-free implementation of the deepest impression is to consider the coordination between threads. Unlike the locking mechanism, although at the expense of achieving a certain performance, but at least thread-safe operation of these non-shared variables do not have too much to consider other thread operations. At this point be considered to understand the complexity of implementation without the lock, which is perhaps the gains will lose it, Hehe.