分类目录归档：并发

JUC 可重入 读写锁 ReentrantReadWriteLock

发表于由
5

读写锁 ReadWriteLock

读写锁维护了一对相关的锁，一个用于只读操作，一个用于写入操作。只要没有writer，读取锁可以由多个reader线程同时保持。写入锁是独占的。

互斥锁一次只允许一个线程访问共享数据，哪怕进行的是只读操作；读写锁允许对共享数据进行更高级别的并发访问：对于写操作，一次只有一个线程（write线程）可以修改共享数据，对于读操作，允许任意数量的线程同时进行读取。

与互斥锁相比，使用读写锁能否提升性能则取决于读写操作期间读取数据相对于修改数据的频率，以及数据的争用——即在同一时间试图对该数据执行读取或写入操作的线程数。

读写锁适用于读多写少的情况。

可重入读写锁 ReentrantReadWriteLock

属性

ReentrantReadWriteLock 也是基于 AbstractQueuedSynchronizer 实现的，它具有下面这些属性（来自Java doc文档）：

  • 获取顺序：此类不会将读取者优先或写入者优先强加给锁访问的排序。
    • 非公平模式（默认）：连续竞争的非公平锁可能无限期地推迟一个或多个reader或writer线程，但吞吐量通常要高于公平锁。
    • 公平模式：线程利用一个近似到达顺序的策略来争夺进入。当释放当前保持的锁时，可以为等待时间最长的单个writer线程分配写入锁，如果有一组等待时间大于所有正在等待的writer线程的reader，将为该组分配读者锁。
    • 试图获得公平写入锁的非重入的线程将会阻塞，除非读取锁和写入锁都自由（这意味着没有等待线程）。
  • 重入：此锁允许reader和writer按照 ReentrantLock 的样式重新获取读取锁或写入锁。在写入线程保持的所有写入锁都已经释放后，才允许重入reader使用读取锁。
    writer可以获取读取锁，但reader不能获取写入锁。

  • 锁降级：重入还允许从写入锁降级为读取锁，实现方式是：先获取写入锁，然后获取读取锁，最后释放写入锁。但是，从读取锁升级到写入锁是不可能的。

  • 锁获取的中断：读取锁和写入锁都支持锁获取期间的中断。

  • Condition 支持：写入锁提供了一个 Condition 实现，对于写入锁来说，该实现的行为与 ReentrantLock.newCondition() 提供的 Condition 实现对 ReentrantLock 所做的行为相同。当然，此 Condition 只能用于写入锁。
    读取锁不支持 Condition，readLock().newCondition() 会抛出 UnsupportedOperationException。

  • 监测：此类支持一些确定是读取锁还是写入锁的方法。这些方法设计用于监视系统状态，而不是同步控制。

继续阅读 →

JUC ConcurrentLinkedQueue

发表于由
6

java.util.concurrent.ConcurrentLinkedQueue 是一个基于链接结点的、无界、线程安全的、FIFO队列。它的是实现采用了无等待（wait-free）、无锁（lock-free）算法，该算法基于 Maged M. Michael 和 Michael L. Scott 合著的 Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms 中描述的算法。

一、设计思路

  1. 使用 CAS 原子指令来处理对数据的并发访问，把同步最小化到单个硬件指令上；这是无锁算法的基础。
  2. 分别用 head、tail 两个原子指针来指向队头和队尾，可以同时进行入队和出队操作，但允许 head、tail 并不总是指向有效的头和尾；把入队、出队需要同步更新的范围最小化到单个原子变量上，这是无锁算法实现的关键。
  3. 在入队、出队操作上并不总是更新 head、tail，而是在多次操作后才进行更新，节省了CAS指令。具有批量更新的效果。
  4. 由于 head、tail 并不总是指向头和尾，这就是说，队列会出现不一致的情况，所以在 head、tail 上定义了一些不变式来维护算法的正确性。

二、不变式

不变式是在执行方法之前和之后，队列必须要保持的。可变式是在执行过程中，队列允许出现的不一致情况。

head 的约束

通过这个结点能够在 O(1) 时间到达第一个存活（非已删除）结点，如果有的话。

不变式
  • 所有存活结点可以 从 head 开始通过 succ() 访问。
  • head != null。
  • (tmp = head).next != tmp || tmp != head，这个不变式是说 head 在方法开始之前、之后，head 指向的结点应该是在队列上的。
可变式
  • head.item 可能是、也可能不是 空的。
  • 允许 tail 落后于 head，那是因为 tail 不能从 head 到达。

tail 的约束

从它可以在 O(1) 时间访问到队列的最后一个结点（唯一的满足 node.next == null 的结点）。这个也就是说 tail 指向的并不总是最后一个存活结点。

不变式
  • 最后的结点总是可以从 tail 开始通过 succ() 访问。
  • tail != null。
可变式
  • tail.item 可能是、也可能不是空。
  • 允许 tail 落后于 head，那是因为 tail 不能从 head 到达。
  • tail.next 可能是、也可能不是 自指向到 tail。
    继续阅读 →

JUC LinkedBlockingQueue

发表于由
回复

java.util.concurrent.LinkedBlockingQueue 是一个基于单向链表的、范围任意的（其实是有界的）、FIFO 阻塞队列。访问与移除操作是在队头进行，添加操作是在队尾进行，并分别使用不同的锁进行保护，只有在可能涉及多个节点的操作才同时对两个锁进行加锁。

队列是否为空、是否已满仍然是通过元素数量的计数器（count）进行判断的，由于可以同时在队头、队尾并发地进行访问、添加操作，所以这个计数器必须是线程安全的，这里使用了一个原子类 AtomicInteger，这就决定了它的容量范围是： 1 – Integer.MAX_VALUE。

由于同时使用了两把锁，在需要同时使用两把锁时，加锁顺序与释放顺序是非常重要的：必须以固定的顺序进行加锁，再以与加锁顺序的相反的顺序释放锁。

头结点和尾结点一开始总是指向一个哨兵的结点，它不持有实际数据，当队列中有数据时，头结点仍然指向这个哨兵，尾结点指向有效数据的最后一个结点。这样做的好处在于，与计数器 count 结合后，对队头、队尾的访问可以独立进行，而不需要判断头结点与尾结点的关系。
继续阅读 →

JUC ArrayBlockingQueue

发表于由
回复

java.util.concurrent.ArrayBlockingQueue 是一个线程安全的、基于数组、有界的、阻塞的、FIFO 队列。试图向已满队列中放入元素会导致操作受阻塞；试图从空队列中提取元素将导致类似阻塞。

此类基于 java.util.concurrent.locks.ReentrantLock 来实现线程安全，所以提供了 ReentrantLock 所能支持的公平性选择。

属性

队列的操作主要有读、写，所以用了两个 int 类型的属性作为下一个读写位置的的指针。存放元素的数组是 final 修饰的，所以数组的大小是固定的。对于并发控制，是所有的访问都必须加锁，并用两个条件对象用于协调读写操作。

// 队列存放元素的容器
final Object[] items;

// 下一次读取或移除的位置
int takeIndex;

// 存放下一个放入元素的位置
int putIndex;

// 队列里有效元素的数量
int count;


// 所有访问的保护锁
final ReentrantLock lock;

// 等待获取的条件
private final Condition notEmpty;

// 等待放入的条件
private final Condition notFull;

环绕处理

如果指针一直往前增加或一直往后减小，那么总会超出数组的有效索引范围。所以需要进行一些环绕处理。

// 指针前移
final int inc(int i) {
    return (++i == items.length) ? 0 : i;
}

// 指针后移
final int dec(int i) {
    return ((i == 0) ? items.length : i) - 1;
}

注意，上面的处理都是对指针值的直接处理，而不关心是读指针还是写指针，因为是否有可读元素、可写空间的判断是通过对 count 计数来判断的。

这也是 count 的作用，它极大地简化了指针有效性的判断。在下面的 insert 和 extract 方法中根本就不需要对读写指针之间的位置关系进行判断，非常精妙。

通过环绕处理可以把这个数组看成是圆形的缓存。
继续阅读 →

JUC 源码分析 四 wait notify notifyAll 与 条件对象

发表于由
2

内置锁 与 wait notify 机制

每个Java对象都有一个内置锁，通过 synchronized 关键字使用。线程之间可以通过 Object 类的 wait, notify, notifyAll 进行协调。

wait, notify, notifyAll 方法说明：

  • wait：在其他线程调用此对象的 notify() 方法或 notifyAll() 方法前，导致当前线程等待。当前线程必须拥有此对象监视器。该线程发布对此监视器的所有权并等待，直到其他线程通过调用 notify 方法，或 notifyAll 方法通知在此对象的监视器上等待的线程醒来。然后该线程将等到重新获得对监视器的所有权后才能继续执行。
  • notify：唤醒在此对象监视器上等待的单个线程，直到当前线程放弃此对象上的锁定，才能继续执行被唤醒的线程。如果所有线程都在此对象上等待，则会选择唤醒其中一个线程，选择是任意性的，被唤醒的线程将以常规方式与在该对象上主动同步的其他所有线程进行竞争。
  • notifyAll：唤醒在此对象监视器上等待的所有线程，直到当前线程放弃此对象上的锁定，才能继续执行被唤醒的线程。被唤醒的线程将以常规方式与在该对象上主动同步的其他所有线程进行竞争。

以一个有界缓存为例，展示了内置锁和 wait、notify、notifyAll 的一般用法：

public class BoundedBuffer<T> {
       private final Object[] buffer;
       private final int length;

       public BoundedBuffer(int length ) {
             if (length < 0) {
                   throw new IllegalArgumentException("length < 0");
            }
             this.length = length ;
             buffer = new Object[length ];
      }

       // synchronized 用于方法上，表示一个同步方法，线程进入方法前自动获得内置锁
       public synchronized void put(T obj) throws InterruptedException {
             // 线程被唤醒时，条件不一定满足（虚假唤醒），所以需要在循环里进行测试、等待
             while (isFull()) {
                   // 在当前的对象实例上等待，由其他线程调用 notifyAll 或 notify 方法唤醒
                  wait();
            }

            doPut(obj);

             // 唤醒在此对象监视器上等待（通过wait方法进入等待）的所有线程。
             // 直到当前线程放弃此对象上的锁定，才能继续执行被唤醒的线程。
            notifyAll();

      }

       public synchronized T take() throws InterruptedException {
            T object = null;
             while (isEmpty()) {
                  wait();
            }
            object = doTake();
            notifyAll();
             return object;
      }

       private void doPut(T obj) { // not implemented
      }

       private T doTake() { // not implemented
             return null ;
      }

       private boolean isEmpty() { // not implemented
             return false ;
      }

       private boolean isFull() { // not implemented
             return false ;
      }
}

继续阅读 →

Java 内存模型 JMM

发表于由
回复

JMM，Java Memory Model，Java 内存模型。

什么是内存模型，要他何用？

假定一个线程为变量var赋值：var = 3;，内存模型要回答的问题是：在什么条件下，读取变量var的线程可以看到3这个值？

如果缺少了同步，线程可能无法看到其他线程操作的结果。导致这种情况的原因可以有：编译器生成指令的次序可以不同于源代码的“显然”版本，编译器还会把变量存储在寄存器而不是内存中；处理器可以乱序或并行执行指令；缓存会改变写入提交到主存得到变量的次序；存储在处理器本地缓存中的变量对其他处理器不可见 等等。

数据依赖性

如果两个操作访问同一个变量，且这两个操作中有一个为写操作，此时这两个操作之间就存在数据依赖性。数据依赖分下列三种类型：

名称　　　代码示例　　　　　说明
写后读　　a = 1;b = a;　　　写一个变量之后，再读这个位置。
写后写　　a = 1;a = 2;　　　写一个变量之后，再写这个变量。
读后写　　a = b;b = 1;　　　读一个变量之后，再写这个变量。

上面三种情况，只要重排序两个操作的执行顺序，程序的执行结果将会被改变。

编译器和处理器在重排序时，会遵守数据依赖性，编译器和处理器不会改变存在数据依赖关系的两个操作的执行顺序。

as-if-serial语义

as-if-serial语义的意思指：不管怎么重排序，（单线程）程序的执行结果不能被改变。编译器、runtime 和处理器都必须遵守as-if-serial语义。

数据竞争

当程序未正确同步时，就会存在数据竞争。java内存模型规范对数据竞争的定义为：在一个线程中写一个变量，在另一个线程读同一个变量，而且写和读没有通过同步来排序。

顺序一致性模型

操作执行的顺序是唯一的，就是它们出现在程序中的顺序，这与执行它们的处理器无关；变量每一次读操作，都能得到执行序列上这个变量最新的写入值，无论这是哪个处理器写入的。这个是一个理想的模型，JMM是不支持的。

Java 语言规范规定了 JVM 要维护内部线程类似顺序语意（within-thread as-if-serial semantics）：只要程序的最终结果等同于它在严格的顺序环境中执行的结果，那么上述所有的行为都是允许的。

JMM 规定了 JVM 的一种最小保证：什么时候写入一个变量会对其他线程可见。
继续阅读 →

JUC 源码分析 三 AbstractQueuedSynchronizer 共享模式 与 CountDownLatch

发表于由
回复

共享模式

共享模式允许一组线程获取同一个许可。为实现共享模式子类需要实现两个方法：

  • tryAcquireShared：返回int类型的值，小于0表示获取失败，等于0表示获取成功但不允许后续更多的获取，大于0表示获取成功且允许更多的后续获取。
  • tryReleaseShared：返回true表示释放许可成功，可以唤醒等待线程；false表示失败，不唤醒等待线程。

共享获取 acquireShared

public final void acquireShared(int arg) {
    if (tryAcquireShared(arg) < 0)
        doAcquireShared(arg);
}

private void doAcquireShared(int arg) {
       // 添加到等待队列，不管是共享模式还是独占模式，都共享同一个等待队列。
    final Node node = addWaiter(Node.SHARED);
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head) {
                int r = tryAcquireShared(arg); // 尝试获取，返回值表示是否允许获取
                if (r >= 0) {
                   // 获取成功
                   // 把自己设为头结点并传递可以获取的信号
                   // node 把自己设为头结点后，它的后继发现它的前驱是头结点了，就会尝试获取。
                    setHeadAndPropagate(node, r);
                    p.next = null; // help GC
                    if (interrupted)
                        selfInterrupt();
                    failed = false;
                    return;
                }
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

private void setHeadAndPropagate(Node node, int propagate) {
    Node h = head; // Record old head for check below
    setHead(node);
    /*
     * 尝试通知队列里的下一个结点，如果：
     *       调用者指示或者之前操作记录显示需要传递
     *       (注意：这里对waitStatus使用单一检查，因为PROPAGATE可能被转换到SIGNAL)
     *   并且
     *       下一个结点以共享模式等待或者我们根本就不知道，因为它是空的。
     *
     * 在这些检查有点保守，可能导致不必要的唤醒，但只是在多重竞争acquires/releases时，
     * 因此，大多数都是现在或不久就需要通知的。
     */
    if (propagate > 0 || h == null || h.waitStatus < 0) {
        Node s = node.next;
        if (s == null || s.isShared())
            doReleaseShared();
    }
}

private void setHead(Node node) {
    head = node;
    node.thread = null; // for GC
    node.prev = null;
}

继续阅读 →

内存关卡/栅栏 （ Memory Barriers / Fences ） – 译

发表于由
回复

翻译自：Martin Thompson – Memory Barriers/Fences

在这篇文章里，我将讨论并发编程里最基础的技术–以内存关卡或栅栏著称，那让进程内的内存状态对其他进程可见。

CPU 使用了很多技术去尝试和适应这样的事实：CPU 执行单元的性能已远远超出主内存性能。在我的“Writing Combining”文章，我只是谈及其中一种技术。CPU 使用的用来隐藏内存延迟的最普通技术是管线化指令，然后付出巨大努力和资源去尝试重排序这些管线来最小化缓存不命中的有关拖延。

当一个程序执行的时候，它不在乎，如果重排序后的指令提供了一样的最终结果。例如，在一个循环内，如果循环内没有操作使用循环计算器，循环计数器什么时候更新是不在乎的。编译器和 CPU 自由地重排序指令来最大化地利用 CPU，直到下一次迭代即将开始时才更新它（循环计数器）。也可能，在一个循环的执行过程中，这个变量可能存储在一个寄存器里，永远不会推到缓存或主内存，因此，它对其它 CPU 永远不可见。

CPU 核包含多个执行单元。例如，一个现代的Intel CPU 包含6个执行单元，可以做一组数学，条件逻辑和内存操作的组合。每个执行单元可以做这些任务的组合。这些执行单元并行地操作，允许指令并行地执行。如果从其它 CPU 来观察，这引入了程序顺序的另一层不确定性。

最终，当缓存不命中发生时，现代 CPU 可以根据内存加载的结果做一个假设，然后基于这个假设继续执行直至实际数据的加载完成。

提供“程序顺序”保留了 CPU 和编译器自由地做它们认为可以提升性能的事情。

cpu-memory-cache-system

加载（load）和存储（store）到缓存和主内存是被缓冲和重排序的，使用加载（load），存储（store），和写组合（writing-combining）缓存。这些缓存是关联的队列，允许快速查找。这种查找是必须的，当一个稍后的加载需要读取一个之前存储的、还没有到达缓存的值时。上图描绘了现代多核 CPU 的简化视图。它显示了执行单元如何使用本地寄存器和缓存来管理内存，与缓存子系统来回传送。

在多线程环境下，需要采用一些技术来让程序结果及时可见。我不会在这篇文章里涉及缓存一致性。仅仅假设一旦内存被推到缓存，然后有一个协议消息将发生，以确保所有共享数据的缓存是一致的。这种使内存对处理器核可见的技术被称为内存关卡或栅栏。

内存关卡提供了两种属性。首先，它们保留了外部可见的程序顺序，通过确保所有的、关卡两侧的指令表现出正确的程序顺序，如果从其他CPU观察。第二，它们使内存可见，通过确保数据传播到缓存子系统。

内存关卡是一个复杂的主题。它们在不同的 CPU 架构上的实现是非常不同的。Intel CPU 有一个关联的强内存模型。本篇将以 x86 CPU 为基础讲解。

继续阅读 →

JUC 源码分析 二 ReentrantLock

发表于由
回复

上一篇文章已完整展示了等待队列的管理（添加结点、移除取消结点）、独占模式下的acquire操作、acquire中断取消、前驱如何通知后继。这些知识已足够用来实现一个可重入锁。

本篇通过java.util.concurrent.locks.ReentrantLock类的源码来分析如何实现可重入锁。

可重入锁

可重入锁就是说当线程拥有这把锁的时候，它再次请求锁是成功的；当线程释放锁时，如果持有锁的线程对锁的请求次数大于释放次数，则该线程仍然拥有锁，直到请求次数与释放次数相等时才真正释放锁。

所以可重入锁需要一个重入计数变量，初始值设为0，当成功请求锁时加1，释放锁时减1，当释放锁之后计数为0则真正释放锁。重入锁还必须持有对锁持有者的引用，用以判断是否可以重入。

锁的公平性

如果锁能够严格按照线程请求锁的先后顺序分配锁，则认为锁具有公平性；如果某一线程能在其他等待线程之前获取到锁，则认为锁不具有公平性。

ReentrantLock

ReentrantLock是JUC包里可重入的独占锁实现，它具有三个内部类：Sync、NonfairSync、FairSync，通过构造函数的参数来指定锁是否是公平的，下面是一些核心代码：

public class ReentrantLock implements Lock, java.io.Serializable {
     private final Sync sync;

     public ReentrantLock(boolean fair) {
         sync = fair ? new FairSync() : new NonfairSync();
     }

     public void lock() {
         sync.lock();
     }

     public void unlock() {
         sync.release(1);     // 这个1表示退出锁1次。
     }

     // 带超时限制的获取
  public boolean tryLock(long timeout, TimeUnit unit)
          throws InterruptedException {
      return sync.tryAcquireNanos(1, unit.toNanos(timeout));
  }

     // 其他代码省略
}

可以看到，ReentrantLock都是把具体实现委托给内部类而不是直接继承自AbstractQueuedSynchronizer，这样的好处是用户不会看到不需要的方法，也避免了用户错误地使用AbstractQueuedSynchronizer的公开方法而导致错误。

ReentrantLock的重入计数是使用AbstractQueuedSynchronizer的state属性的，state大于0表示锁被占用、等于0表示空闲，小于0则是重入次数太多导致溢出了。
继续阅读 →

JUC 源码分析 一 AbstractQueuedSynchronizer

发表于由
2

队列结点

Node类型的waitStatus、prev、next 字段都用volatile 修饰，这样直接的读写操作就具有内存可视性。表示Node状态的waitStatus字段是个int类型，这样通过数值比较就可以判断Node的状态，而不需要很多的分支语句。

它的构造函数也是比较有意思的，有三个，分别用于构建同步队列的初始头结点或共享标识、构造同步队列的有效结点、构造条件队列的结点。也就是说，同步队列和条件队列的结点是相同的类型，所以可以从条件队列转移到同步队列去获取许可。

static final class Node {
       // 表明节点是否以共享模式等待的标记
    static final Node SHARED = new Node();

    // 表明节点是否以独占模式等待的标记
    static final Node EXCLUSIVE = null;

    // 表明线程已被取消
    static final int CANCELLED =  1;

    // 表明后续节点的线程需要unparking
    static final int SIGNAL    = -1;

    // 表明线程正在等待一个条件
    static final int CONDITION = -2;

    // 表明下一次acquireShared应该无条件传播
    static final int PROPAGATE = -3;

    /*
     * 状态字段，只能取下面的值：
     * SIGNAL(-1)：    这个结点的后继是（或很快是）阻塞的（通过park），所以当前结点
     *              必须unpark它的后继，当它释放或取消时。为了避免竞争，acquire方法必须
     *              首先表明它们需要一个信号，然后再次尝试原子性acquire，如果失败了就阻塞。
     *               
     * CANCELLED(1)：  这个结点由于超时或中断已被取消。结点从不离开这种状态。尤其是，
     *                 这种状态的线程从不再次阻塞。
     *
     * CONDITION(-2)： 这个结点当前在一个条件队列上。它将不会用于sync队列的结点，
     *               直到被转移，在那时，结点的状态将被设为0.
     *              这个值在这里的使用与其他字段的使用没有关系，仅仅是简化结构。
     *               
     * PROPAGATE(-3)： releaseShared应该传递给其他结点。这是在doReleaseShared里设置
     *                 （仅仅是头结点）以确保传递继续，即使其他操作有干涉。
     *
     * 0：             非以上任何值。
     *
     * 值是组织为数字的用以简化使用。非负值表示结点不需要信号。这样，大部分代码不需要
     * 检查特定的值，只需要(检查)符号。
     *
     * 对于普通同步结点，字段初始化为0；对于条件结点初始化为CONDITION(-2)。
     * 通过CAS操作修改(或者，当允许时，用无条件volatile写。)
     */
    volatile int waitStatus;

    /*
     * 连接到当前结点/线程依赖的用来检查等待状态的前驱结点。
     * 在进入队列时赋值，只在出队列时置为空（为了GC考虑）。
     * 根据前驱结点的取消，我们使查找一个非取消结点的while循环短路，这个总是会退出，
     * 因为头结点从不会是取消了的：一个结点成为头只能是一次成功的acquire操作结果。
     *
     * 一个取消了的线程从不会在获取操作成功，线程只能取消自己，不能是其他结点。
     */
    volatile Node prev;

    /*
     * 连接到当前结点/线程释放时解除阻塞的后续结点。
     * 在入队列时赋值，在绕过已取消前驱节点时调整，出队列时置为空（for GC）。
     * 入队操作不会给前驱结点的next字段赋值，直到附件后（把新节点赋值给队列的tail属性？），
     * 所以看到next字段为空不一定表示它就是队列的尾结点。然而，如果next字段看起来是空，
     * 我们可以从tail向前遍历进行双重检查。
     * 被取消了的结点的next字段被设置为指向它自己而不是空，这让isOnSyncQueue变得容易。
     */
    volatile Node next;

    /*
     * 列队在这个结点的线程，在构造时初始化，用完后置空。
     */
    volatile Thread thread;

    /*
     * 连接到下一个在条件上等待的结点或是特殊的值SHARED。
     * 因为条件队列只在独占模式下持有时访问，我们只需要一个简单的链表队列来持有在条件上等待的结点。
     * 他们然后被转移到队列去re-acquire。
     * 因为条件只能是独占的，我们通过用一个特殊的值来表明共享模式 来节省一个字段。
     */
    Node nextWaiter;

    Node() {    // Used to establish initial head or SHARED marker
    }

    Node(Thread thread, Node mode) {     // Used by addWaiter
        this.nextWaiter = mode;
        this.thread = thread;
    }

    Node(Thread thread, int waitStatus) { // Used by Condition
        this.waitStatus = waitStatus;
        this.thread = thread;
    }
}

添加结点到等待队列

对于添加结点到队列的操作最重要的是要保证：即使添加的CAS操作失败了，也不能影响队列结点现有的连接关系。

对于新结点，它在CAS之前指向它的预期前驱，CAS成功之后再更新预期前驱的后继指针。

在步骤1成功之后、步骤2完成之前，其他线程通过结点的 “next” 连接可能看到“尾结点”（即代码里的 pred）的 “next” 为空，但其实队列里已经加入新的结点，这也是为什么通过 “next” 连接遍历队列时碰到后继为空的，必须从原子地更新的 “tail” 结点向后遍历。
继续阅读 →