NOTE

本篇笔记基于《Java并发编程实战》第15章 - 原子变量与非阻塞同步机制

1. 锁的劣势#

在并发编程中，锁是一种常见的同步机制，但是从前面几章的内容中我们不难发现，用锁来进行同步时会存在一些问题：

1. 性能开销较大： 锁会引入线程的上下文切换和调度开销，线程竞争激烈时，锁会导致大量的阻塞和线程切换，从而显著降低性能。
2. 潜在的死锁问题： 锁的使用不当容易导致死锁。例如，多个线程循环等待对方持有的锁，程序会陷入不可恢复的状态。
3. 可伸缩性差： 锁在高并发场景下会导致竞争问题，线程数越多，锁的竞争越激烈，导致系统性能下降。并且在多核 CPU 中，锁的使用会限制程序的并行性。
4. 阻塞线程会导致资源浪费： 锁的阻塞机制会让线程进入等待状态，占用系统资源（如线程栈、内核资源）。阻塞线程需要等待重新调度，这增加了系统的资源消耗和延迟。
5. 锁释放的顺序难以控制： 在复杂程序中，如果多个线程需要按照一定顺序访问资源，锁可能导致线程调度的不可预测性，增加了设计复杂性。

因此，现在并发领域的大多数研究都侧重于非阻塞算法，以换取更好的可伸缩性和活跃性。

2. Compare-And-Swap#

CAS 是一种基于硬件指令的原子操作，主要用于在多线程环境下更新共享变量。CAS 是由 CPU 提供的指令级支持（如 cmpxchg 指令），因此它在硬件层面保证了操作的原子性。

CAS 包含以下三个操作数：

1. 内存位置 (V)： 需要操作的变量的内存地址。
2. 期望值 (E)： 线程希望变量当前的值。
3. 新值 (N)： 线程准备写入的值。

执行过程： 比较内存中的值 V 是否等于期望值 E

• 如果相等：说明没有其他线程修改变量，将新值 N 写入内存。
• 如果不相等：说明有其他线程修改了变量，不执行更新，返回当前值或失败标志。

在下面这段代码中，就借助CAS实现了一个非阻塞的计数器。首先，通过 value.get() 获取当前计数值，赋值给 v。然后调用 compareAndSwap(v, v + 1) 试图将当前值更新为 v + 1。如果当前值等于 v，说明没有其他线程修改值，则更新成功，compareAndSwap 返回旧值 v，跳出循环。如果当前值不等于 v，说明其他线程在此期间修改了值，compareAndSwap 返回的值与 v 不相等，继续循环到更新成功。最后返回新值 v + 1。

public class CasCounter {
    private SimulatedCAS value;

    public int getValue() {
        return value.get();
    }

    public int increment() {
        int v;
        do {
            v = value.get();
        } while (v != value.compareAndSwap(v, v + 1));
        return v + 1;
    }
}

潜在的问题#

1. ABA 问题： CAS 判断的是值是否变化，而非对象的整体状态。当一个变量从值 A 变为 B，再回到 A 时，CAS 无法检测到变化。
2. 自旋： 如果 CAS 操作失败，线程会不断重试，称为自旋操作。这可能导致 CPU 占用率升高，特别是在高并发环境下。

3. 原子变量类#

Java 中的原子变量类是线程安全的类，用于高效地执行原子性操作，避免了使用锁来实现线程同步。其特点如下所示：

1. 无锁线程安全： 使用硬件支持的 CAS 操作实现，避免了锁的开销。
2. 高效： 在高并发场景中性能优于传统的锁机制。
3. 简单易用： 提供多种常见的原子操作（如增减、更新、替换）。

常用的原子变量类有以下几种：

• AtomicInteger：用于操作 int 类型的变量。
• AtomicLong：用于操作 long 类型的变量。
• AtomicReference<T>：用于原子更新引用类型的变量。
• AtomicBoolean：用于操作 boolean 类型变量。

4. 非阻塞算法#

非阻塞的栈是一种线程安全的数据结构，通过无锁算法实现多线程间的并发访问。非阻塞栈使用CAS操作替代传统锁机制，避免线程阻塞，从而提升高并发场景下的性能。

核心数据结构#

• 栈使用一个链表实现，每个节点包含两个字段：
  1. value： 存储栈的值。
  2. next： 指向下一个节点的指针。
• 栈顶指针（top）使用 AtomicReference 包装，确保原子性操作。

Push 操作#

1. 创建一个新节点。
2. 设置新节点的 next 指向当前栈顶。
3. 使用 CAS 将栈顶更新为新节点。

Pop 操作#

1. 获取当前栈顶。
2. 使用 CAS 将栈顶更新为当前栈顶的 next。
3. 返回当前栈顶的值。

实现代码：

public class NonBlockingStack<T> {
    private AtomicReference<Node<T>> top = new AtomicReference<>();

    private static class Node<T> {
        T value;
        Node<T> next;

        Node(T value) {
            this.value = value;
        }
    }

    public void push(T value) {
        Node<T> newNode = new Node<>(value);
        Node<T> currentTop;

        do {
            currentTop = top.get();  
            newNode.next = currentTop;  
        } while (!top.compareAndSet(currentTop, newNode));
    }

    public T pop() {
        Node<T> currentTop;

        do {
            currentTop = top.get();
            if (currentTop == null) {  
                return null;
            }
        } while (!top.compareAndSet(currentTop, currentTop.next));

        return currentTop.value;
    }
}