读《Java并发编程实战》笔记。
如果在某种算法中，一个线程的失败或挂起不会导致其他线程也失败或挂起，那么这种算法就被称为非阻塞算法。
如果在算法的每个步骤中都存在某个线程能够执行下去，那么这种算法也被称为无锁（Lock-Free）算法。
非阻塞链表：
我们需要使用一些技巧：
第一个技巧，即使在一个包含多个步骤的更新操作中，也要确保数据结构总是处于一致的状态。第二个技巧，如果当 B 到达时发现 A 正在修改数据结构，那么在数据结构中应该有足够多的信息，使得 B 能完成 A 的更新操作。实现这两个技巧时的关键点在于：当队列处于稳定状态时，尾节点的 next 域将为空，如果队列处于中间状态，那么 tail.next 将非空。因此，如何线程都能够通过检查 tail.next 来获取队列当前的状态。而且，当队列处于中间状态时，可以通过将尾节点向前移动一个节点，从而结束其他线程正在执行的插入元素操作，并使得队列恢复为稳定状态。
import java.util.concurrent.atomic.AtomicReference; /** * Michael-Scott(Michael and Scott,1996)非阻塞算法中的插入算法 * <p> * * @author hyl * @version v1.0: LinkedQueue.java, v 0.1 2020/10/22 18:20 $ */ public class LinkedQueue <E>{ private static class Node <E>{ final E item; final AtomicReference<Node<E>> next; public Node(E item, Node<E> next){ this.item = item; this.next = new AtomicReference<>(next); } } // 哑节点 private final Node<E> dummy = new Node<>(null,null); private final AtomicReference<Node<E>> head = new AtomicReference<>(dummy); private final AtomicReference<Node<E>> tail = new AtomicReference<>(dummy); public boolean put(E item){ Node<E> newNode = new Node<>(item,null); while (true){ Node<E> curTail = tail.get(); Node<E> tailNext = curTail.next.get(); if (curTail == tail.get()){ if (tailNext != null){ // 队列处于中间状态，推进尾节点 tail.compareAndSet(curTail,tailNext); }else { // 处于稳定状态，尝试插入新节点 if (curTail.next.compareAndSet(null,newNode)){ // 插入操作成功，尝试推进尾节点 tail.compareAndSet(curTail,newNode); return true; } } } } } }在 ConcurrentLinkedQueue 中使用的正是该算法。
/** * A node from which the first live (non-deleted) node (if any) * can be reached in O(1) time. * Invariants: * - all live nodes are reachable from head via succ() * - head != null * - (tmp = head).next != tmp || tmp != head * Non-invariants: * - head.item may or may not be null. * - it is permitted for tail to lag behind head, that is, for tail * to not be reachable from head! */ private transient volatile Node<E> head; /** * A node from which the last node on list (that is, the unique * node with node.next == null) can be reached in O(1) time. * Invariants: * - the last node is always reachable from tail via succ() * - tail != null * Non-invariants: * - tail.item may or may not be null. * - it is permitted for tail to lag behind head, that is, for tail * to not be reachable from head! * - tail.next may or may not be self-pointing to tail. */ private transient volatile Node<E> tail; /** * Inserts the specified element at the tail of this queue. * As the queue is unbounded, this method will never return {@code false}. * * @return {@code true} (as specified by {@link Queue#offer}) * @throws NullPointerException if the specified element is null */ public boolean offer(E e) { checkNotNull(e); final Node<E> newNode = new Node<E>(e); for (Node<E> t = tail, p = t;;) { Node<E> 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; } }