参考 What Volatile Means in Java，Memory Models，Consistency model。另外，stack overflow 的讨论或许有用。

Java 中的 volatile 可以保证可见性、有序性。可见性：线程 A 写入 volatile 变量，线程 B 读取该 volatile 变量可以读到最新值，并且在线程 A 写入 volatile 变量之前对 A 可见的变量值，在线程 B 读取该 volatile 变量之后对 B 也可见。有序性：禁止（编译器/CPU）对 volatile 变量相关的指令进行重排优化。虽然 Java 并发编程实战中提到 volatile 不能保证原子性，但是对 long/double 类型的 volatile 变量的简单赋值操作是原子的，我所说的简单赋值是指不依赖变量当前值的赋值操作。

问题

在《深入理解 Java 虚拟机》第 12 章中有提到 volatile 相关的汇编代码，简单的示例如下。书中提到 lock addl 相当于一个内存屏障，阻止跨内存屏障的指令重排，同时还会将当前处理器的缓存写入内存，以及使其他处理器的缓存失效，从而禁止指令重排。

1
2
3
4
5
6
7

private static boolean a;
private volatile static boolean b;

public static void foo() {
    a = true;
    b = true;
}

1
2
3
4
5

0x000002271ed4378c: movabs $0x711dec880,%r10 ; {oop(a 'java/lang/Class'{0x0000000711dec880} = 'Test')}
0x000002271ed43796: movb $0x1,0x70(%r10)
0x000002271ed4379b: movb $0x1,0x71(%r10)
0x000002271ed437a0: lock addl $0x0,-0x40(%rsp) ;*putstatic b {reexecute=0 rethrow=0 return_oop=0}
; - Test::foo@5 (line 8)

最初，我有个疑问，就是赋值语句之后的内存屏障无法禁止屏障之前的指令重排，例如此处的两个赋值语句 a=true 和 b=true 是否可能重排。询问 Jeremy（JSR-133 的作者之一）之后，他告诉我：

It is possible for processors to do that in general, but x86 doesn’t, so you don’t need a barrier there. Search for “total store order” if you’re curious.

然后，我查找和 TSO 相关的内容时，又一次找到 Russ Cox 的博客，以下内容部分来自该博客。

概念

顺序一致性（Sequential Consistency）：单个处理器按照程序顺序执行（不重排指令），多个处理器按照某种顺序交错执行，这样的多处理器就是顺序一致的。

大多数指令集架构不提供顺序一致的内存模型，因为更强的一致性通常意味着更少的优化（更低的性能）。x86 使用 Total Store Order（TSO）内存模型：所有处理器都连接到单个共享内存，但是每个处理器有一个本地的写入队列，写入操作排队写入共享内存，读取操作会优先读取本地写入队列中的值（如果有的话）。ARM/POWER 的内存模型更加宽松：每个处理器从自己的内存完整副本中读取和写入，读取可以延迟到写入之后，并且每个写入都独立地传播到其他处理器，在写入传播时允许重新排序。

测试

Litmus Test（石蕊测试）：初始时 x=0,y=0（共享变量），rn 表示私有存储（例如，寄存器或者局部变量），不考虑编译器重排指令。

以下程序是否可以看到 r1=1,r2=0？顺序一致性和 x86 中不可以，ARM/POWER 中可以。

1
2
3
4
5
6

// Thread1
x = 1
y = 1
// Thread2
r1 = y
r2 = x

以下程序是否可以看到 r1=0,r2=0？顺序一致性中不可以，x86 和 ARM/POWER 中可以。

1
2
3
4
5
6

// Thread1
x = 1
r1 = y
// Thread2
y = 1
r2 = x

其他

区分 consistency 和 coherency：consistency 表示多个处理器对所有内存位置的操作的总顺序达成一致，coherency 表示多个处理器对相同内存位置的操作的总顺序达成一致。

JMM 为程序中所有操作定义了一个偏序关系，称为 Happens-Before。操作 A Happens-Before 操作 B 的含义是：如果操作 A 先于操作 B 发生，那么执行操作 B 的线程能够看到操作 A 的结果。如果两个操作没有 Happens-Before 关系，那么 JVM/CPU 可以对它们任意地重新排序。

参考 Coroutines for Go，Coroutine Wiki。

什么是协程（coroutine）？通常使用的函数（function）也被称为子例程（subroutine），一系列调用会形成一个调用栈（call stack），调用者（caller）和被调用者（callee）是父子关系。而协程不同，协程之间是对等关系，每个协程都有一个调用栈。协程有非对称和对称两种实现，非对称协程使用 resume 和 yield 关键字，调用者使用 resume 恢复某个协程，被调用者使用 yield 暂停当前协程，然后控制会转移到调用者。对称协程只使用 yield 关键字，但是需要指定将控制转移给哪个协程。经典的例子，比较两个二叉树是否包含相同的序列（中序遍历），代码。

协程的控制转移是主动的（非抢占式），不需要操作系统支持，也不需要使用锁和信号量等同步原语。线程的控制转移是被动的（抢占式），由操作系统调度，上下文切换更加昂贵，需要使用同步原语保护共享变量。协程只提供并发性，而线程可以利用多核 CPU 实现并行。切换的速度，协程最多 10 纳秒，线程几微秒，Goroutines 和 Virtual Threads（Java 21） 几百纳秒。

网络上各种术语的解释很混乱，根据多线程模型，我倾向于使用用户线程和内核线程的对应关系，来描述不同的实现。简单描述一下我的理解：平常使用的是一对一模型，Goroutines 和 Virtual Threads 使用的是多对多模型。协程不能简单的看作多对一模型，协程是非抢占式的用户线程，描述的是多个用户线程之间的协作关系，实际上可以在各个模型上实现协程。

关于 Goroutines 的实现，可以看 Dmitry Vyukov 的演讲 Go scheduler: Implementing language with lightweight concurrency。其他资源：Scalable Go Scheduler Design Doc，The Go scheduler，HACKING。

简单的设计，使用一对一模型 + 线程池，缺点是线程的内存占用较大，Goroutine 阻塞会导致线程阻塞，没有“无限数量”的栈。所以，使用多对多模型，Goroutine 占用内存更小，可以被 Go runtime 完全控制。如果 Goroutine 因为锁/通道/网络 IO/计时器而阻塞，Goroutine 将会进入阻塞队列，运行此 Goroutine 的内核线程不会阻塞，Go runtime 可以从 Run Queue 中调度 Runnable 的 Goroutine 到该内核线程上（复用，Multiplex）。

但是，当 Goroutine 进行系统调用，控制将从 Goroutine 转移到系统调用处理程序，Go runtime 是无法感知该处理流程的，直到系统调用返回，所以此时运行 Goroutine 的内核线程是无法被复用的。有可能所有内核线程都阻塞在系统调用上，而该系统调用所需的资源被某个 Runnable 的 Goroutine 持有，从而发生死锁。所以在系统调用发生时总是会创建/唤醒一个内核线程，执行 Run Queue 中的 Goroutine。当内核线程从系统调用返回，Go runtime 将内核线程上的 Goroutine 放入 Run Queue，使该内核线程空闲从而保证指定的并行度（由 GOMAXPROCS 指定）。

关于 GOMAXPROCS，runtime 文档的描述如下：The GOMAXPROCS variable limits the number of operating system threads that can execute user-level Go code simultaneously. There is no limit to the number of threads that can be blocked in system calls on behalf of Go code; those do not count against the GOMAXPROCS limit.

该实现的瓶颈在全局的互斥锁（MUTEX），内核线程创建 Goroutine 以及获取 Goroutine 都需要操作共享的 Run Queue。解决方案很容易想到，就是为每个内核线程创建本地变量，从而避免频繁访问全局的共享变量。该方案会增加获取下一个 Goroutine 的复杂性，Go 调度器实现的获取顺序是， Local Run Queue、Global Run Queue、Network Poller、Work Stealing。

由于发生系统调用时会创建/唤醒内核线程，也就是说内核线程的数量会多于 CPU 的核心数量。新的调度器为每个内核线程分配本地资源，但是实际上执行 Go 代码的内核线程的数量是固定的（由 GOMAXPROCS 指定），所以空闲线程不应该持有资源，会造成资源浪费以及降低 Work Stealing 的效率。所以，设计上引入一个新的实体，也就是处理器（Processor），从而调度模型从 GM 变为 GMP。Go runtime 不会为每个内核线程分配资源，而是为 Processor 分配资源，Processor 的数量就是 CPU 的核心数量。在新的模型中，当 Goroutine 发生系统调用时，Goroutine 会创建/唤醒新的内核线程，然后将 Processor 对象交给新的内核线程。

目前，调度器已经足够好，不过可以更好。公平性（Fairness）和性能的权衡：设计者想要以最小的性能开销获得最小的公平性。FIFO 队列可以一定程度上保证公平性，但是如果当前 Goroutine 陷入无限循环，队列中的 Goroutine 将会饥饿，所以设计者使用 10 ms 的时间片轮转调度（时分共享，抢占式）。另一方面，FIFO 队列缺少局部性（影响性能），最后进入队列的 Goroutine 会在最后运行。常见的场景，当前 Goroutine 创建另一个 Goroutine，然后自身被阻塞等待另一个 Goroutine 执行。缺少局部性的 FIFO 会产生很大延迟，所以设计者在 Local Run Queue 的尾部添加一个单元素的 LIFO 缓冲区，每次获取 Goroutine 都会首先从缓冲区中获取（Direct Switch）。

该设计引入额外两个问题，一个是其他内核线程从当前内核线程 Work Stealing 时，将 LIFO 中的 Goroutine 窃取，影响 Direct Switch 的执行。解决方案是只有 Goroutine 被放入 LIFO 超过 3 μs 才能被窃取。另一个问题是，不断创建 Goroutine 会导致 LIFO 缓冲区总是有元素，从而 FIFO 队列中的 Goroutine 会饥饿，解决方案是当前 Goroutine 和 LIFO 中的 Goroutine 共享同一个 10 ms 的时间片。

如果 Local Run Queue 一直不为空，Global Run Queue 会饥饿。所以，假设当前是第 schedTick 次获取，设计者设置当 schedTick % 61 == 0 时，优先从 Global Run Queue 获取 Goroutine。为什么使用 61，因为 61 不大不小，太大会饥饿，太小会因为 Global Run Queue 的 MUTEX 限制性能，并且参考哈希表的设计，使用质数而不是 2 的幂会更随机/公平。

最后，Network Poller 可能会饥饿，解决方案是使用后台线程从中定期获取 Goroutine。之所以不像处理 Global Run Queue 饥饿一样在当前线程中获取，是因为从 Network Poller 获取 Goroutine 涉及到 epoll_wait() 系统调用（很慢）。

贴一下去年发现的 Bug，嘿嘿。

导致 Bug 的示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> map = new HashMap<>(2);

        map.merge(1, 1, Integer::sum);
        map.merge(2, 1, Integer::sum);

        map.forEach((k, v) -> {
            map.merge(k, -1, Integer::sum);
            System.out.println(k);
        });
    }
}

Java Bug DataBase 链接，里面比较详细的讨论了发生的问题，由于当时急着发出去，我的评论有点乱，而且是中文翻译为英文的，有点拉。

今天重新回顾一下 Bug，顺便简单解释一下。上述代码的输出为 2，期望输出是 2 和 1（顺序不重要）。问题在于，在两次 merge 之后，map 包含的元素数量 2 已经超过扩容阈值 1，下一次扩容发生在迭代中，导致不正确的输出。具体来说，在 resize 方法中，有 oldTab[j] = null; 操作，即转移元素到新数组时，会将旧数组的所有元素置为 null，从而旧数组的迭代器扫描不到剩余的元素。总的来说，即使在遍历的过程中，没有发生结构性的修改，在特定情况下使用 merge 方法修改 HashMap 依然会导致问题。特定情况是指，在遍历之前 HashMap 的包含的元素数量超过扩容阈值，然后在遍历的过程中使用 merge 方法。

ORACLE 的内部人员首先说明，由于调用 Map 上的方法可能产生破坏迭代的副作用，所以不建议在迭代的过程中调用 Map 上的方法，特别是具有副作用的方法，建议重写代码避免这种情况。然后提到 merge 方法确实有问题，即元素数量超过阈值也没有立即扩容，它和 put 方法的实现不同。评论中还列出其他具有类似副作用的方法，以及其他产生副作用的情况，详细看链接。