本文共 2395 字，大约阅读时间需要 7 分钟。
在基于锁的算法中可能会由于线程在持有锁或者内存页缺失导致I/O阻塞，从而引发活跃性问题。而在非阻塞算法中，一个线程的失败不会导致其他线程也失败或挂起。通常我们会使用CAS来协调各个线程之间的操作，无竞争的CAS总能执行成功，并且如果有多个线程竞争同一个CAS，那么总会有一个线程在竞争中胜出并执行下去。
创建非阻塞算法的关键在于，要找出如何将原子修改的范围缩小到单个变量上，同时还要维护数据的一致性。在更新某个值时如果具有不确定性，或者更新失败时需要进行重新尝试执行。
现代处理器都提供了特殊的指令，可以自动更新共享变量，而且能够检测到其它线程的干扰（如果发生干扰则回退并重试）。非阻塞算法利用硬件指令代替JVM的锁定代码路径，从而在更细粒度层次上进行同步，失败的线程也可以立即重试，而不会被挂起后重新调度，同时降低了争用。
CAS只能保证对单个变量访问的原子性，但在链表中需要单独维护头指针和尾指针，当插入一个新元素时，这两个指针需要采用原子操作来更新。并且如果第一个CAS成功而第二个CAS失败的话，那么会使链表处于不一致的状态，即使这两个CAS都成功了，在这两个CAS执行之间，依旧可能有另一个线程访问该链表。
为此，当线程B到达时，如果发现线程A在执行更新，那么线程B就知道有一个操作已经部分完成，并且不能立即开始执行自己的更新操作，此时线程B可以等待直到线程A完成操作，从而使两个线程不会相互干扰。但是如果线程A在更新过程失败了，那么其他线程都将无法再访问链表。所以当线程B到达时如果发现A正在修改数据结构，那么在数据结构中应该有足够多的信息（这就需要把对数据结构的操作过程精细的划分成多个阶段或状态，考虑每个阶段或状态多线程访问会出现的情况），使得线程B能够帮助线程A完成更新操作，当线程B完成了更新操作后，就可以执行自己的操作，当A恢复后再试图完成其操作时，会发现B已经替它完成了。
在ConcurrentLinkedQueue中使用了该算法，其插入操作源码如下：
public boolean offer(E e) { checkNotNull(e); final Node newNode = new Node (e); for (Node t = tail, p = t;;) { Node q = p.next; if (q == null) { // p is last node if (p.casNext(null, newNode)) { // Successful CAS is the linearization point // for e to become an element of this queue, // and for newNode to become "live". if (p != t) // hop two nodes at a time casTail(t, newNode); // Failure is OK. return true; } // Lost CAS race to another thread; re-read next } else if (p == q) // We have fallen off list. If tail is unchanged, it // will also be off-list, in which case we need to // jump to head, from which all live nodes are always // reachable. Else the new tail is a better bet. p = (t != (t = tail)) ? t : head; else // Check for tail updates after two hops. p = (p != t && t != (t = tail)) ? t : q; }} 首先，它先将传入进来的元素包装为一个Node实例newNode，然后获得尾指针指向的节点p以及其next指针指向的节点q，此时会检查链表是否处于中间状态，判断的条件是q是否为null，如果q为null的话，那么链表处于稳定状态，线程就会执行自己的插入操作——先将最后一个元素的next指针CAS更新为新插入节点，然后将最后一个元素CAS更新为新节点。如果这两个步骤之间有另一个线程到达的话，那么它会发现链表处于不稳定状态，即最后一个元素的next指针q不为null，此时当前线程不会等待其他线程执行完成而是帮助它完成操作，并将尾节点向前推进一个节点，直到它发现链表处于稳定状态之后，才开始执行自己的插入操作。
转载地址：http://tvtmi.baihongyu.com/