Chapter 7. Java Concurrent

7.1 Usage

读者回忆一下在计算机系统课程中学习的关于 thread 和 process 的知识，最好能够在心中对比一下在 C/C++ 中使用线程和进程。

我们本节的目的是在 Java 中使用线程。两种方法：

  • 使用 Runnable Interface：
    1. 重写 public void run() 方法；
    2. 将这个类的实例作为 Thread 类型的构造参数。构造完成后启动 Thread#start() 即可；
  • 继承于 Thread Class；
    1. 重写 public void run() 方法；
    2. 直接启动：Thread#start()；

注意，我们需要特别处理 InterruptedException：

  • Java 多线程程序中，我们应该总是考虑这种 exception。这意味着外部有人正在希望以一种优雅的方式结束当前线程（就是对当前线程对象 Thread#interrupt()），并且可能正在通过 Thread#join() 等待；

  • 不应该在捕获这个异常的时候直接抛出另外一种异常（混淆原因），或者直接忽略（外部线程可能正在等待结束！）；

  • 根据方法自身的含义，一般有两种解决方案：

    1. 继续向上传播这个异常（当你的方法本身就是一个耗时操作 / 网络操作或者其他情况）；
    2. 捕获这个异常、设置当前线程被 interrupted 的 flag（方便 log 溯源）：Thread.currentThread.interrupt()，并且准备结束；

    然后处理当前类中需要回收 / 处理的资源。无论是哪一种方法，都需要遵循当前方法的语义：“调用它出现 InterruptException 这种情况是否合理？”

7.2 Synchronized Methods

Java 线程中的设定和 C/C++ 是类似的，它也会共享线程间的资源，不过 Java 没有指针，只是通过引用共享的。因此会遇到和 C/C++ 一样的问题。

就以共享静态变量为例，多线程同时操作共享静态变量会导致未定义的行为（race condition）。

在 C/C++ 中，一般会通过设立临界区（信号量 semaphore）或互斥锁（mutex）来锁定共享变量，确保同一时间只有一个/指定数量的线程可以访问。

在 Java 中，提供了一种修饰方法的关键字 synchronized，其作用是：

  1. 被该关键字修饰的方法，其所在的类型的任意一个对象，只能被一个线程调用被这个关键字修饰的方法。

    也就是说，相当于在这个方法的类上设一个互斥锁（被称为 intrinsic lock 固有锁，或者 monitor lock），把这个类中所有被 synchroized 修饰的方法锁住；

  2. 当一个线程退出了一个对象的 synchronized 方法，则会与这个对象其他的 synchronized 方法建立一个 happens-before relationship，以确保对象被使用的状态能被所有线程知道；

如果 synchronized 修饰在静态方法上，那么锁住的就是与 intrinsic lock 关联的 class 实例，而不是它的实例的实例。也就是对这个类中静态域的访问会被控制，需要与实例方法的 synchronized 区分开。

Java 甚至支持到 statement 细粒度的 synchronized：

1
2
3
4
5
6
7
8
9
10
public void addName(String name) {
    // 这里保护实例属性的并发访问（this）
    // 如果需要保护静态成员，则需要将关键字定义在静态方法上
    // 或者括号内使用 Class 元类型的实例
    synchronized(this) {
        lastName = name;
        nameCount++; 
    } 
    nameList.add(name); 
}

7.3 Reentrant Synchronization

Java 中提供了一类可重入锁，可以让获得锁的同一个线程多次访问临界资源：

1
2
3
4
5
6
7
8
9
10
11
12
// 注意，如果需要保护类的静态成员，则应该将锁也定义为静态成员
Lock lock = new ReentrantLock();

lock.lock();
try {
    //更新对象状态
    //捕获异常，并在必须时恢复不变性条件
} catch (Exception e) {
   e.printStackTrace();
} finally {
   lock.unlock();
}

7.4 Atomic Access & Keyword volatile

Java 中原生的单步原子访问操作包含：

  • 针对引用变量的读写、大多数基本类型的读 或 写（除了 long / double）；

  • 被 volatile 关键字修饰的所有变量的读 或 写（包括 long 和 double）；

    volatile 的本质是，程序在访问一个被它修饰的变量后，会直接进入 main memory 读取，而不会使用寄存器 / 线程本地缓存；相当于告诉 JVM 这个变量可能会在当前线程的控制流以外的地方被更改。

    它会确保当一个线程修改了一个变量时，其他线程能够立即看到这个修改。

    底层是通过禁止指令重排序和 memory barrier（如 x86-64 的 fence 族指令） 等机制来实现的。

Java 的原子访问操作可以：

  • 保证多线程操作一个数据时值不会错误的改变（写操作字节码指令会一次性执行完），降低 memory inconsistency 的风险；
  • 保证各个线程总是能读到关于这个值最新情况（读操作字节码指令会读到最新的情况并且一次性执行完）；

那么，为什么 Java 既然有内置 Atomic Classes、锁、synchronous 关键字等等同步机制，为什么还需要 volatile 关键字？

问出这个问题就说明你将 “多线程原子操作”（也称 “同步”）和这里的 “单步原子访问操作” 的概念混淆了。

  • 单步原子操作是指，Java 中的一条基本字节码指令（例如读一次内存、写一次内存）会不会被 CPU（其他线程）从中间打断、打乱；
  • 多线程原子操作通常讨论的是一条/一系列 Java 代码的执行（例如从获取内存中的共享变量值到自增写回的这个流程）会不会被 CPU（其他线程）从中间打断；

我们发现，满足单步原子访问操作是满足多线程原子操作的必要不充分条件。因此底层在实现多线程同步机制时，一定已经实现了单步原子访问的操作（及时刷到内存中）。

单步的原子操作是由语言本身以及硬件指令的特征决定。在 Java 中，为了保证灵活性还向上提供了 volatile 关键字，相当于告诉 JVM 和 CPU，被它修饰的变量一是不能放在寄存器中/缓存下来，二是它需要满足单步原子操作（不能乱序执行）。

而多线程原子操作则需要开发者按照程序语义，利用同步机制手动指定代码片段的临界区，即同一时刻的访问控制。

总结一下，你只需要记住这些：

  • volatile 保证 Java 多线程对某个变量的读、写是及时的（不使用寄存器、不使用线程缓存、禁止指令乱序），一定能被下一条指令 / 其他线程感知到；
  • 其他的同步操作，保证 Java 代码片段执行期间的临界特性（不会有另一个线程同时执行相同代码）；
  • 为共享变量加锁（或者其他同步机制）之后，就不再需要 volatile 关键字了（后者是前者的必要不充分条件）；

因此，只有在没有多线程同步的需求（volatile 不保证同一线程对变量的一系列操作是原子的），但是又要保证对某一个变量的读和写是准确、及时的时候，可以使用 volatile 关键字，例如状态标志、简单的布尔变量等，这样不需要加锁，规避了死锁以及性能问题。

注意：C/C++ 中的 volatile 关键字的含义与 Java 有些差异。

它只是告诉 Compiler 不要优化被修饰的变量，并且把它放在内存中，每次读写都直接对内存操作。常用在嵌入式 / 绕过编译器进行内存映射等场景中。

这里没有单步原子操作的说法，因为 C/C++ 编译结束后直接就是机器码。

7.5 Dead Lock, Starvation, Live Lock

无论是死锁还是活锁，都是指多个线程之间因互相请求访问资源而导致程序无法继续执行的情况。

它们的不同点是：

对于死锁，它发生的情况是多个线程或进程在互相等待对方释放资源时，自己又不会主动释放自己占有的资源，导致程序永远无法继续的情况。

例如，假设一个程序的两个线程 A 和 B，A 先获得了一个资源 X 并给它上锁，B 获得了另一个资源 Y 也给它上了锁。但是接下来 B 需要资源 X 才能继续、A 又需要 Y 才能继续。所以二者相互等待对方释放资源锁，造成了死锁；

对于活锁，线程并不会阻塞在原地，而是反复地在释放资源和获取资源间横跳，这主要是因为程序有处理资源访问冲突的机制，但是两个存在活锁的线程相互处理访问冲突的时候又造成了访问冲突，也无法继续下去。

例如一个程序的线程 A 和 B，假设 A 先获得了一个资源 X 并给它上锁，B 获得了另一个资源 Y 也给它上了锁。A 想要获取资源 Y 的时候发现 B 占用了，于是 A 主动释放了资源 X 给 B，自己去获取资源 Y；但是此时 B 也主动释放了 Y 资源，去获取 X 资源，双方只是调换了资源持有的顺序，仍然无法继续执行。

线程饥饿是指，因为共享资源调度策略的问题，造成某些线程一直无法获得执行的机会而近乎停止执行，而另一些线程则一直占用共享资源不释放。

7.6 Condition Variable in Java: Guarded Blocks

在 Java 中，和 C/C++ 的 condition variable 对应的、在 blocks 前通过某些方式检查（例如轮询）一些条件再决定执行的，线程动作同步的术语被称为 guarded block。

Java 中被 synchrounous 修饰的方法可用 Object#wait() 和 Object#notify*() / notifyAll() 来实现与 condition variable 相似的效果。

  • Object#wait()：此时会设置等待的信息、放锁并且挂起当前线程（不是 spin lock）；
  • Object#notify / notifyAll()：另一个线程可以通过访问当前对象的这两个方法来唤醒等待在 intrinsic lock 上的线程，把锁交给它们；

我们可以利用 guarded blocks 模仿 condition variable 的做法实现生产者消费者模式。

7.7 Immutable Objects

在很多实际情况下，不可变数据类型的好处：

  • 复制构造时，不是引用传递，因此是深拷贝。这样使用起来和基本类型一样方便，但是又不用担心改错源数据（非引用链接）；

  • 确保数据在多线程情况下无需同步，线程安全！

我们在 Java Bean & Record 一节已经讨论过。不可变类的定义：一个类满足如下三个条件：

  • 类型中的每个数据域都是 私有的、常量的（private，final）；
  • 每个数据域都只能通过 getter 方法获取，不能有任何 setter 方法，并且没有“返回值是指向可变数据域的引用”的 getter 方法；
  • 必须存在公有构造函数，并且构造函数内初始化各个数据域（常量只能这么做）；
  • Object 基类继承函数 equals 返回 true 当且仅当类中的每个数据域都相等；
  • Object 基类继承函数 hashCode 在类中的每个数据域都相等时，一定返回一样的值；
  • Object 基类继承函数 toString 最好包含 类名 和 每个数据域的名称和值；

因此如果有一个类数据域都私有、没有修改器方法，但有一个方法：返回内部一个可变数据域的引用（例如数组），则这个类也是可变类；

7.8 High Level Concurrency Objects

Java 中包装了一些高级并发对象：

7.8.1 Lock Objects

Lock Objects：对常见的并发场景提供了简单的保护；

例如 ReentrantLock（可重入锁），

可以使用 tryLock() 获取锁、unlock() 释放锁。

和 Intrinsic Lock 机制很相似（包括持有规则、通过关联的 Condition 对象 notify/wait）相比更好的一点是 “允许 try”，也就是获取锁不成功的话还可以回到获取锁前的执行状态。

7.8.2 Executors

创建一个新的线程可以通过继承 Thread 类或者实现 Runnable 接口来实现，这两种方式创建的线程在运行结束后会被虚拟机销毁，进行垃圾回收，如果线程数量过多，频繁的创建和销毁线程会浪费资源，降低效率。而线程池的引入就很好解决了上述问题，线程池可以更好的创建、维护、管理线程的生命周期，做到复用，提高资源的使用效率，也避免了开发人员滥用 new 关键字创建线程的不规范行为。

在实际生产中，一般企业内部会规定编码规范。例如 Aliyun 指出，线程资源必须通过线程池提供，不允许在应用中显式的创建线程。如果不使用线程池，有可能造成系统创建大量同类线程而导致消耗完内存或者“过度切换”的问题。

Executors：为启动、管理线程提供了更高级的 API，可以使用线程池机制为大规模并发应用提供支持；

将线程创建、管理的工作从应用业务逻辑中剥离。Java 中的 Executor 就是来包装这个的接口。

其中，有一些框架 / 库可以实现 Executor 接口。例如：

  • Thread Pools：线程池，最常见的对于 Executor 的 implementation；
  • Fork/Join：一个利用多处理器资源的 Executor 实现框架。

Executor 接口只有一个：

1
void execute(java.lang.Runnable runnable);

不需要自行创建 Thread，而是将 Runnable 类放到 Executor 中，让它帮你启动和管理。

类似地，还有 ExecutorService 接口，提供了比 Executor 更灵活的线程提交方式：

1
public interface ExecutorService extends java.util.concurrent.Executor, java.lang.AutoCloseable;

类似 Executor，不过它不仅仅允许你提交 Runnable 对象，还允许使用 Callable，并使用 Future<T> 来异步获取返回值，可以通过返回的 Future 对象了解、管理 Runnable/Callable 的执行状态：

1
2
3
4
5
6
Future<?> submit(Runnable runnable);
Future<T> submit(Runnable runnable, T t);
Future<T> submit(Callable<T> callable);

// 同时启动多个 callable 对象
List<Future<T>> invokeAll(Collection<? extends Callable<T>> collection) throws InterruptedException;
1
2
// 等待终止
boolean awaitTermination(long l, TimeUnit timeUnit) throws InterruptedException;

在 ExecutorService 基础上继续包装 ScheduledExecutorService，允许对线程启动提供调度 delay 的时间：

1
2
ScheduledFuture<V> schedule(Callable<V> callable, long l, TimeUnit timeUnit);
ScheduledFuture<?> schedule(Runnable runnable, long l, TimeUnit timeUnit);

A. Implementation: ThreadPoolExecutor

Thread Pool 线程池，是 Executor 的一种实现，用的最多的是 ThreadPoolExecutor 类型。

  • ThreadPoolExecutor 类型继承：

  • ThreadPoolExecutor 状态维护：运行状态 (runState) 和线程数量 (workerCount) 放在同一个 Atomic Integer 中，高 3 位保存 runState，低 29 位保存 workerCount，二者同时取出避免数据不一致或者频繁占用锁资源。

    1
    private final AtomicInteger ctl = new AtomicInteger(ctlOf(RUNNING, 0));

  • runState：共有 5 种：

    | 运行状态 | 状态描述 |
    | ————— | —————————————————————————————— |
    | RUNNING | 运行状态。能接收新提交的任务，也能处理阻塞队列中的任务 |
    | SHUTDOWN | 准备关闭状态。不接受新提交的任务，但能处理阻塞队列中的任务 |
    | STOP | 停止状态。所有正在执行的任务会被终止，不接受新提交任务、队列中存在的任务 |
    | TIDYING | 空闲状态。所有任务都已经结束，并且当前有效线程数（workerCount）为 0 |
    | TERMINATED | 终止状态。在空闲状态下才能终止，标识不再使用 |

  • execute Control Flow：

    1. 首先检测线程池运行状态，如果不是 RUNNING，则直接拒绝；
    2. 如果 workerCount < corePoolSize，则创建并启动一个线程来执行新提交的任务；
    3. 如果 workerCount >= corePoolSize，且线程池内的阻塞队列未满，则将任务添加到该阻塞队列中；
    4. 如果 workerCount >= corePoolSize && workerCount < maximumPoolSize，且线程池内的阻塞队列已满，则创建并启动一个线程来执行新提交的任务；
    5. 如果 workerCount >= maximumPoolSize，并且线程池内的阻塞队列已满，则根据拒绝策略来处理该任务，默认的处理方式是直接抛异常。

  • 拒绝策略（饱和策略）：

    • AbortPolicy：默认策略，抛出异常 RejectedExecutionException，拒绝执行；
    • CallerRunsPolicy：调用执行自己的线程运行任务，也就是直接在调用 execute 方法的线程中运行 (run) 被拒绝的任务，如果执行程序已关闭，则会丢弃该任务。因此这种策略会降低对于新任务提交速度，影响程序的整体性能。如果您的应用程序可以承受此延迟并且要求任何一个任务请求都要被执行的话，你可以选择这个策略；
    • DiscardPolicy：不处理新任务，直接丢弃掉；
    • DiscardOldestPolicy：此策略将丢弃最早的未处理的任务请求。

使用 ThreadPoolExecutor 一般配合 fixed thread pool 的策略。好处是可以让应用 degraded gracefully。

不过 Executor 本身也提供了一些快速创建的工厂方法，帮助在一些场景下简化代码逻辑：

  • 使用 newFixedThreadPool 创建固定的线程数的线程池（同时最多只有指定的线程数正在执行）；

  • 使用 newSingleThreadExecutor 单个线程实例的 executor，一次执行一个线程；

  • 使用 newCachedThreadPool 创建可动态调整线程数的线程池，可以应对多个短期 tasks；

    创建一个可缓存的线程池，调用 execute 将重用以前构造的线程（如果线程可用）。如果没有可用的线程，则创建一个新线程并添加到池中。终止并从缓存中移除那些已有 60 秒钟未被使用的线程；

  • newScheduledThreadPool 创建一个支持定时及周期性的任务执行的线程池，多数情况下可用来替代 Timer 类；

[!WARNING]

但是在实际生产实践中，我们不建议使用 Executors 来创建线程池。建议使用 ThreadPoolExecutor 构造函数的方式，因为后者的处理方式让开发者更加明确线程池的运行规则，规避资源耗尽的风险。

再强调一次。项目中创建多线程时，使用上面的方法线程池创建方式，无论是单一、可变、定长都有一定问题，原因是：

  • FixedThreadPool 和 SingleThreadExecutor 底层使用有界阻塞队列 LinkedBlockingQueue；
  • CachedThreadPool：底层使用的是同步队列 SynchronousQueue；
  • ScheduledThreadPool 和 SingleThreadScheduledExecutor：使用的无界的延迟阻塞队列DelayedWorkQueue；

这些队列的最大长度为都是 Integer.MAX_VALUE，可能会堆积大量请求导致 OOM（为什么网络请求场景下，队列越长越有可能 OOM，请参见 “计算机系统工程 - 拥塞控制”）。

所以实际生产环境中开发者会根据需求手动定制 ThreadPoolExecutor 的 7 个参数，来自定义线程池。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 线程池的核心线程数
private static int corePoolSize = 30;
// 能容纳的最大线程数
private static int maximumPoolSize = 200;
// 空闲线程存活时间
private static long keepAliveTime = 0L;
// 空闲线程存活时间 单位
private static TimeUnit unit = TimeUnit.MILLISECONDS;
// 创建线程的工厂类,自定义线程名称
private static String threadName = "thread-local-pool-%d";
private static ThreadFactory namedThreadFactory = new ThreadFactoryBuilder().setNameFormat(threadName).build();
// 存放提交但未执行任务的队列
private static BlockingQueue<Runnable> threadFactory = new LinkedBlockingQueue<>(1024);
// 等待队列满后的拒绝策略
private static RejectedExecutionHandler handler = new ThreadPoolExecutor.AbortPolicy();
// 定义线程池
private static ExecutorService pool = new ThreadPoolExecutor(corePoolSize, maximumPoolSize, keepAliveTime, unit, threadFactory, namedThreadFactory, handler);

B. Implementation: ForkJoinTask

而 Fork/Join 框架是针对 ExecutorService 接口的实现。它可以充分利用多处理器的优势，为那些可以拆成小块递归的任务设计，例如：

1
2
3
4
5
if (my portion of the work is small enough) 
    do the work directly 
else 
    split my work into two pieces 
    invoke the two pieces and wait for the results

在 ForkJoinTask 子类（RecursiveTask 有返回值、RecursiveAction 无返回值）中定义这些任务。

7.8.3 Other Utilities

Concurrent Collections

Concurrent Collections：更容易地管理大规模数据，减少 synchronization 次数；

Atomic Variables

Atomic Variables：针对变量粒度的同步机制，可以在一定程度上避免 data inconsistency；

All classes have get and set methods that work like reads and writes on volatile variables

Virtual Threads

Java 中是一类轻量级线程解决方案。让线程创建、调度、管理的开销最小化。

Virtual Threads 是 Java Thread 的实例，这与任何 OS thread 是相互独立的。

当 virtual threads 内部调用了阻塞的 I/O 操作后，会立即被 JVM 挂起；

virtual threads 有一个有限的 call stack，并且只能执行一个 HTTP client 请求 / JDBC 查询。这对一些异步的耗时任务比较合适，但是不适合 CPU intensive tasks；

1
2
3
Thread virtualThread = Thread.ofVirtual().start(() -> {
    // Code to be executed by the virtual thread
});

所以 Virtual Threads 不是说会比普通线程更快，而是说比普通线程更具可扩展性（provide scale），这在高并发、每次请求处理耗时的服务器网络应用中能提升吞吐量。

ThreadLocalRandom：为多线程提供高效的伪随机数生成方案；

Chapter 8. Java Garbage Collection

本章，我们将先从 “为什么需要垃圾回收”、“垃圾回收的思路是什么”（8.1）出发，先介绍现存的主流语言（Python/JavaScript 等）甚至操作系统（Android）究竟采用了哪些垃圾回收方式（8.2 ~ 8.7），然后再来看看 Java 语言自己是怎么做垃圾回收的（8.8 ~ 8.9）。

8.1 Problem Definition

8.1.1 Why & How

通常情况下，无论是什么语言，在运行时想要分配空间，要么放在栈上、要么放在堆上。

栈上分配的变量全权由编译器管理（如果你写过编译器，请回想一下令人讨厌的 global frame size），这也是绝大多数语言的（解释型语言则是解释器）共性；

但是部分语言的有一部分空间是分配在堆上的。例如 tiger 语言中，我们初始化数组/结构体，它调用的 runtime function 底层由 C++ 实现，最终就是分配在堆上的。

如果这类使用堆空间的语言，在运行时不及时释放堆空间，可能会导致堆溢出的问题。由于像 tiger 这样的语言不涉及底层的结构（包括 Python、Java 等等），没有指针的概念，自然也没办法自己释放，或者这种语言的定位就是不需要开发者来释放（所谓 “内存安全”），那么还需要借助运行时机制来管理堆空间。

垃圾回收的基本原理就是，当一个被分配的地址没办法被当前的任何指针/变量访问到（not reachable），那么就需要运行时工具帮助释放这片空间，使得它能够被重新分配和使用。

更准确一点，其实应该进行 liveness analysis（就像前面设计编译器时做的），但是运行时显然不方便做这种静态分析（运行时难以看出）。因此人们通常使用可达性（reachability）来代替 liveness 进行分析，只不过 reachability 可能没有 liveness 那么及时 / 精确（还可能出现一些问题，后面讨论）。

也就是说，如果存活，一定可达（这是由各个语言的编译器保证的）。

于是，垃圾回收的过程就是，从当前已知存活的变量开始（例如当前栈帧上、寄存器中正在使用的变量），递归地去搜索可达的内存区域，再把分配过、但不可达的内存释放即可。

我们通常使用有向图去描述 “两个存活变量间的可达关系”：结点表示程序当前栈上/寄存器中正在使用的变量 和 堆上分配的记录，边表示地址指针；

所以，几乎所有自动 GC 都遵循一个理念：按照某个策略预定的时间（定时策略），释放不再继续使用的（标记策略）引用类型变量所占用的空间；

为什么加上了 “定时”：运行时是动态的，总不能只回收一次，或者一直回收；

8.1.2 GC Metrics

另外还有一点需要注意的是，GC 通常会伴随一段时间的 STW（stop-the-world，时停），此时段间，无论这个语言是单线程还是多线程的，都需要全部暂停等待 GC 的处理。

这样的 STW 在大多数 GC 算法中都是必要的，不过有长有短（取决于具体算法）。这主要是因为 GC 在运行时总有一些数据需要确保 synchronization，防止并发的回收造成数据不安全的问题。我将 STW 的时长称为 GC 算法的时延（GC latency）；

还有一点需要明确的是，我们引入 GC 是为了防止内存泄漏。而 “内存泄漏” 这个概念本身并不是说没有回收完所有的不再使用的空间就是泄漏了，而是没有及时的回收不再使用的堆空间，引发的一系列问题，包括堆溢出。

所以重点在于 “及时” 而不是 “全部”。也就是说，一个 GC 算法可以不需要在一次回收过程清理掉全部的垃圾，而是只需要确保及时就行。

于是我们还可以定义 GC throughput，即一次 GC 操作中，单位时间内回收记录的数量，这个指标能间接反映这个 GC 算法的效率，以及它究竟是否 “及时”。

8.2 Mark & Swap

一种 GC 策略是 “标记清除”（Mark-And-Swap，标记策略）+ 溢出清理（定时策略）：

  • Mark：从可达有向图的根结点（已知存活的变量）开始遍历，将遇到的所有结点全部标记一遍；

  • Swap：将整个堆扫描一遍，把没有标记的结点放到 free list 中（相当于释放），并且清空所有标记（为下一轮 GC 准备）；

  • 程序在 GC 开始时 freeze，在 GC 结束时 resume，从 free list 中分配堆空间；
  • 程序只有在 free list 为空时才进行 GC；

目前正在使用这个策略的语言有 JavaScript；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Mark phase:
    for each root v
        DFS(v)

Sweep phase:
    p <- first address in heap
    while p < last address in heap
        if record p is marked
            unmark p
        else let f1 be the first field in p
            p.f1 <- freelist
            freelist <- p
        p <- p + (size of record p)

function DFS(x)
    if x is a pointer and points to record y
        if record y is not marked
            mark y
        for each field fi of record y
            DFS(y.fi)

这样做的优缺点：

  • 优点：算法简单便于实现，很多情况下确实是有效的（满了就回收全部的垃圾）；

  • 缺点：性能不佳（扫描全堆，throughput 不大），而且需要经常打断程序执行流先做垃圾回收，程序效率不佳（总体 STW 很长）。

分析一下：

$T=c_1R+c_2H$（$R$ 为可达变量数、$H$ 为堆大小），每次增长 free list entry 数量 $H-R$，因此总体均摊时间：$\overline{T}=\dfrac{c_1R+c_2H}{H-R}$；

于是我们知道：当 $H$ 和 $R$ 很接近的时候，GC 的性能会很差。因此我们的改进是，在 $\dfrac{R}{H}\gt0.5$ 的时候建议 OS 增大当前进程的堆的大小；

第二个改进，是考虑到如果只使用 DFS 函数调用递归很可能导致栈溢出（因为堆本身是很大的），考虑引入 显式的栈来实现 DFS；

更有技巧一点的话，还有 pointer reversal 这类优化的方法。但是本文的主题不是讨论这些算法，因此略过，感兴趣的读者可以自行搜索。

第三个改进，对于 free list，我们可以模仿 Memory Allocation 的 aggregation list，管理多个 free list 并按照列表的大小来分类；

8.3 Reference Count

还有一类常见的 GC 策略是 “引用计数”（标记策略）+ 分配时清理（定时策略）；

目前使用这种 GC 策略的语言有 Python、Swift 等等；

这里我们对每一个在堆上的 record 维护一个额外的字段（ref_cnt）表明当前有多少变量指向它。

然后在赋值、作用域变化等等情况时更新变量对应的值就行。

举个例子，例如 record x 的某个 field x.fi 原本是 z（是堆上的 record）赋值为 y（另一个堆上的 record）此时：

  • 读写 y 的 reference count 使其增加；
  • 读写 z 的 reference count 使其减少；
  • 检查 z 的 reference count 如果是 0，则将 z 加入 freelist；
  • 而 z 中的字段（例如 z.fi）如果是堆上的指针，则推迟到 z 所在的地址被从 free list 分配出去时再减小 reference count；

于是相较于同步的 Mark-and-Swap，引用计数的好处是：

  • 避免了批量、递归的检查回收操作，将部分的更新引用计数操作推迟到分配时（批处理提升了 GC throughput）；
  • 不需要频繁进行全堆扫描，提升了程序执行效率（压缩了 STW 的时长）；

只不过引用计数还引入了一些问题：

  • 循环引用：相互引用的变量无法让 ref_cnt 减为 0（信息不充分会导致回收不充分）；

    解决方法 1：引入语义层面的语法特性，例如弱引用（Weak References），当内存压力比较大的时候，将这种弱引用视为没有引用。

    但是这相当于把难题丢给了开发者，容易导致程序运行时错误的出现（例如使用一个被释放了的弱引用变量）；

    解决方法 2：进行简单的 cycle detection，对某些容易成环的地方进行特殊检查，及时除环；

    解决方法 3：与 mark & swap 结合（occasional），补上全局信息，但 mark 操作很昂贵；

  • 内存访问性能问题：例如 x.fi <- p 这个语句在加上引用计数的 GC 后，会变成 3 次内存访问，性能可能更差些：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    z <- x.fi
    c <- z.count
    c <- c – 1
    z.count <- c
    if c = 0 call putOnFreelist
    x.fi <- p
    c <- p.count
    c <- c + 1
    p.count <- c

正因为这两个问题，我们常常在一些 GC 学术原型中才能见到它，实际使用这种方法会出现一些难以避免的性能问题。但是不可否认的是，这种方法（思路）真的很简单和显然，所以它也被常常应用到其他的领域和方面。例如 file table 维护文件打开状态时使用、虚拟页和物理页的映射时物理页维护引用计数、C++ 的智能指针 shared_ptr 等等。

8.4 Copy Collection

这类 GC 策略比较新，有些现代的应用（例如 Android 10+）就在使用这种 GC 策略。内容如下：

  • 将 heap 拆成两个部分：from-space & to-space；

    from-space 专门存放分配的内容，to-space 专门管理回收的内容；

  • 两个 space 都有一个 limit 指针表示该区域结尾；

  • next 表示该区域接下来要插入的位置，分配内存就是向 next 后面追加可达的 entry；

  • 如果 next 到 limit 的位置，证明当前的 semi-space 满了，我们从 root 根结点（目前肯定存活的）开始，将所有可达结点 copy 到另一个 semi-space 中（next 也移过去了），相当于丢弃了不可达结点、变相进行了一次 GC；

这样做有几点好处：

  • 不需要特地进行 mark + sweep 了，操作更简单，降低了时间复杂度，一次 copy 足矣（进一步降低 STW 长度）；
  • 每次 copy 都相当于整理出了连续的空闲堆空间，方便分配、减小了 external fragments，最大化 memory utilization；

相比于 mark-and-sweep 也有坏处：

  • 如果大部分变量存活时间很长（$R\sim H$），会导致内存拷贝过多，overhead 很大；
  • 一半的空间利用率低下；

实现 Copy Collection 的算法是 Cheney’s algorithm：

解释一下算法：

把当前准备切走的一边称为 from-space，另一边称为 to-space；

每个被分配的 entry（$p$）的第一个字段（$f_1$）保存指向当前分配对象自己的指针（只有在移动更新时指向新的对应的 entry），其他字段（$f_i$）存放正常被分配的数据；

Forward(p) 函数的含义是将 p 指针对应的结点数据完全移动到 to-space（如果已经完成移动则什么也不做）；

主函数的算法就是从根结点开始（先 forward 根结点）BFS 遍历结点、更新 scan，遍历到的直接调用 Forward 转移。同时需要更新拿在手上的指针，保证上层应用无感；

这种算法有些优缺点：

  • 优点：不引入额外数据结构（没有额外的栈、不需要 reversal pointers）；
  • 缺点：影响原来程序的 locality！无法充分利用局部性（不相干的 record 可能被复制到一起），这会降低每次 GC 后的程序执行效率；

因此我们作出优化：Semi-depth-first Algorithm，这也是 Copy Collection 最常见的实现方法：

这个算法的思路是 DFS，所以主函数省略了（就是对每个 root 结点调用 Forward 然后结束）。这个 Forward 函数我们在 Cheney’s Algorithm 中见过类似的结构，就是如果当前 entry（由 p 指向）完全移到 to-space（第一字段已经在 to-space 了），那么就直接返回，否则调用 chase 迁移；

主要看 Chase(p) 的做法。q 和 next 有点像算法里的左右指针，q 表示当前正在迁移的 entry 的开头，next 则表示正在迁移的 entry 的结尾；

而 r 和 p 又像一对前后指针，p 表示当前正在 copy 的节点，r 则是一轮 semi-DFS 从根到叶遍历的指针；

中间 for 循环的作用是把要 copy 的 p 指向的 entry 的每个字段都复制到 to-space 中。同时 Chase 还需要考虑 p entry 中指向 from-space（分配在堆上但没迁移的 entry）的指针。

为什么 Chase 需要考虑 p 中的指向 from-space 的指针？因为这里是 DFS，不能直接结束对 p 的迁移，否则就变成 BFS 了（Cheney’s Algorithm）；应该像这样一直沿树边递归到底；

一轮 semi-DFS 后，如果 p 有多个 field 都指向堆，那么默认是先 copy 当前 p entry 中的最后一个 from-space 分配的地址，方便 repeat 循环递归（DFS）地移动 from-space 中分配的 entries；

为啥是 copy 最后一个？因为递归过程一次只能保存一个，这也是算法称为 “semi-DFS” 的原因（没有完全遵循 DFS 的遍历方法）。更清楚一点，我们可以看下面的比较图（注意到 4、6 是最后才访问的）：

例如 1 -> 2 -> 5 后，一轮 semi-DFS 结束，虽然看到了 4 对应的 record，但也只是更新了 2 的 record 的指针，并没有 copy 4 的 record 到 to-space；随后递归回溯到 1 再继续；

Optimizations?

注意到，copy collection 对于堆空间的浪费还是很严重的，因为每次只使用一半的堆空间（另一边必须是无效的）。于是一个很简单的优化是，底层使用 mmap 来处理对堆空间的分配。我们可以让另一半（不在使用的 to-space）在 copy 前是 unmap 的状态（未分配物理页），这样能更充分地利用机器资源。

但这么做也有点问题，在 GC collector 进行 copy collection 的途中可能出现物理内存猛增的情况；

但这确实能缓解在除了 GC 阶段以外的其他时间里内存不够用的情况。

注意到 Copy Collection 的均摊开销主要在 $\dfrac{c_3R}{\dfrac{H}{2}-R}$ 左右（$c_3\sim10$，$R$ 为存活记录的大小）；那么我们如何降低上述内存使用，并且继续提升整体 GC 性能呢？

8.5 General Collection (Generations)

8.5.1 Design

一般情况下，GC 的 throughput 和 latency 是相互制约的，例如我想要确保 throughput 很大，一般需要扫描更多的信息来进行批处理，但扫描更多的信息会导致 latency 的延长。

但是这种 GC 的策略相较于前面几种方法，可以同时提升 throughput、降低 latency。主要是人们有以下的特性的观察（不是准确和普适的定律，而是经验假设）：

  • 堆上新创建的对象通常更容易先死去；
  • 堆上存活的时间越长的对象通常更不容易死去；

堆上存活时间长的越长，短的越可能更短。也许可以用马太效应解释；

基于这个特性，人们提出了 general collection 的 GC 策略（分代）：

  • 将 heap 分为若干区域 $G_0,\space G_1,\space G_2,\ldots$，编号从小到大存放的是创建对象的由新到旧（新生代 ~ 持久代）。被分配的对象首先被放入 $G_0$；

  • $G_0,G_1,\ldots$ 这些代（generations）一般使用 Marking 的思路（给数据标记）；

  • GC collector 重点回收 $G_0$ 区域的对象。同时需要关注 $G_1,G_2,\ldots$ 中指向 $G_0$ 区域的指针（如果存在，$G_0$ 的这个区域就不能释放）；

    其实 $G_1,G_2,\ldots$ 中有指向 $G_0$ 区域的指针 这件事本身就很罕见。主要是因为根据经验假设，$G_0$ 只有很少一部分新生对象会进入 $G_1$ 以及更旧的代（10%-20%），而 $G_1$ 中的指针更普遍的是指向自己代或者更旧的代（因为先定义再使用嘛），更少有指向新一代的指针。

    相反的情况，如果 $G_0$ 中的数据有些指向 $G_1,G_2,\ldots$ 区域的指针，那么它们可以立即被释放；

  • 每次 $G_0$ 未能清空 N 次（N 一般是 2~3 左右，应该看不同应用场景）的部分会转移到 $G_1$，并且更旧的代同理，依次进行；也正因如此，$G_0,G_1,\ldots$ 各代间的大小差距最好是指数级的；

这样做带来的好处是，每次回收只需要扫描原先 20% 左右的区域，但是能回收率能达到 80%，不仅减小了 latency（扫描的区域少了），而且增大了 throughput（单位时间回收的量增多了），极大提升 GC 效率。

这种策略的均摊时间开销：$\dfrac{c_3R}{H-R}$（和 Copy Collection 相比，$\dfrac{H}{2}$ 变为 $H$）；并且通常情况下，由于 $G_0$ 本身不大，因此很多情况都有 $H\gt10R$，也就是说一般情况的均摊复杂度 $\dfrac{1}{9}c_3$（相对于前面的策略效率提升了 10 倍，如果只考虑 $G_0$ 的话）！

可是，如果涉及更旧代的回收，时间开销还是很大的（例如如果只有两代，并且做一次 $G_0,G_1$ 回收，就相当于扫描了整个堆）。不过好在需要回收旧代的频率并不是很高。

8.5.2 Patch: Ways of Remembering

现在回过头看一下，如果使用 general collection，有个问题是我们 “同时需要关注 $G_1,G_2,\ldots$ 中指向 $G_0$ 区域的指针”。

虽然就像前面说的，这种情况很罕见，但还是需要考虑的，例如堆上分配的结构体在它被分配的很久以后突然更新了一个字段，这种情况就可能出现上述罕见的现象。于是我们需要单独保存一些旧代中有指针指向新代的信息（不然 GC collector 很难判断 $G_0$ 中会不会出现上述罕见情况，而且全表扫描太慢了）。

为了解决这个问题，人们首先想出了借助一个 Remembered List 的方法：每次更新被分配 entry 的某个字段时，向这个 list 中加入一条更新的记录。这种方法有个问题，就是实际上可用的堆的空间一般很大，平均需要记录的更新数据可能会达到数个 MB，这对于一个内存中的列表而言开销已经比较大了。

于是人们想使用 Remembered Set 来存放，因为它的去重性质，我们可以在分配的 object $b$ 中使用 1 个 bit 来记录它是否已在 remembered set 中；

以上两种方法的粒度都是对象（很细），免不了占用比较大的内存资源。

于是人们提出了粗粒度的信息存放方案（Card Marking，比较主流的实现方案）：

  • 将内存分为 $2^k$ bytes 大小的内存区域，称为 logical cards（逻辑卡片）；
  • 一个对象可以占据一个卡片的一部分，或者从卡片中间区域开始占据到后面的卡片；
  • 当 $b$ 地址在分配后被更新时，包含这个地址的卡片会被标记；
  • 可以用更小的 list（byte index 向右移动了 $k$ 位）来保存 mark 的情况；

具体实现就是在每次更新 object 时打桩（在 obj.f = a 的后面加上代码，判断如果确实是 G1 指向 G0 的情况，则从 card 对应的 list 中取出并更新）；

坏处：不清楚在这片区域的 cross generation pointer 具体在哪里，还需要在这片区域内继续查找（空间换时间）；

另一种方法是用 Page 的粒度来管理这个信息（Page Marking）：

  • 就像 card marking，不过 $2^k$ 是页表大小；
  • 更新一个分配的 object 相当于 makes the page dirty；
  • 用户态程序可以在每次 GC 后标记 write-protected；

这样相当于把 card marking 的打桩操作变成了用户态的 fault handler。但实际上开销也不小（毕竟需要进出内核以及用户态 handler）；

8.6 Incremental Collection

这里还有个更加复杂的回收策略，和实际应用结合得比较紧密。

这个策略着重关注于优化 STW 时长（latency）这个指标，希望 GC 让应用停止的时间尽可能短（尤其是在涉及 UI 前台类型/端侧的语言中，不希望用户感受到卡顿）；

比如对于数十 GB 的内存而言，同步的 Mark & Swap 的 STW 可能在百毫秒级别，这对后台程序 / 服务器应用而言不那么关心，但是如果是端侧设备 / 浏览器 / 游戏设备 / 精确的嵌入式设备呢？这个问题就很突出了。

这个时候，两种思路：

  • 让 GC 回收程序和应用并发执行（从根本上极大缩短甚至基本消灭 STW）；
  • 让 GC 回收程序按应用执行的情况增量地回收（通过减少需要扫描的数据量，也能极大缩短 STW）；

这时我们需要引入一些概念：

  • Collector：专门收集不再使用的分配的空间并释放；

  • Mutator：改变 reachable data 的关联图；

    将应用中改变 reachable 关系的逻辑抽象出来，它就是之前阻碍 GC collector 并发，也是 STW 出现的主要原因；

  • Incremental Collection：只有 Mutator 需要 Collector 回收时才进行回收（调用式关系）；

  • Concurrent Collection：在 Mutator 执行期间 Collector 并发执行（后台服务关系）；

现在介绍一种 Incremental Collection 的实现模型：Tricolor Marking（三色标记模型）；

任意一个被分配的记录只会处于 3 种颜色中：

  • White: not visited by GC；
  • Grey: visited by GC, but its children are not；
  • Black: visited by GC, so as its children；

算法如下：

1
2
3
4
5
6
7
8
9
procedure tricolor-marking:
set root object gray // visit

while they are any gray objects:
    select a gray record p
    for each field fi of p:
        if fi.p is white:
            color fi.p gray		// visit first time (可以用栈压入来实现)
    color record p black		// visit second time (可以用栈弹出来实现)

这里是 BFS 性质的遍历所以使用栈数据结构。可以类比，Copy Collection 中的 Cheney’s Algorithm，可以使用队列数据结构来实现；

这里注意几个算法不变量（Invariants），它们是构建 Incremental Collection 的根本原理：

  • 不存在黑结点直接指向白结点的情况。如果有就说明黑色结点对应的对象并没有处理完全，出现了数据不一致的问题；
  • 灰结点一定在 collector 的数据结构（fringe）中，意味着正在处理；

现在，我们希望在 tricolor marking 的基础上引入 incremental collection，就意味着，被分配的 object 在 GC 结束后继续留有标记，交给 mutator 执行。

过一段时间后，再次进入 GC 执行算法时，可能就会出现上述算法不变量的违反。

例如，已经染黑的结点（GC 完全扫描的结点）在上一轮 GC 结束后，被 mutator 追加了白色结点（上一轮 GC 结束后才分配的），这个时候就违反了第一个 invariant。

于是！所谓的 incremental collection 做增量回收，就是通过在 runtime 分配堆空间时，采取措施保证 invariants 的成立（在 mutator 运行时，而非 collector 运行时），对变化的部分进行 GC 检查。

基本的思路还是，针对基本的读写操作进行打桩（barriers）：

  • Method 1 (Dijkstra, Lamport)：向黑结点 object 写入指针 field （插入白结点）时染灰（纳入 GC 管理中）；

  • Method 2 (Steele)：向黑结点 object 写入指针 field （插入白结点）时将父黑结点染灰（dirty，让之前的结点重新放入 GC fringe、表示需要重新扫描）；

    (Boehm, Demers, Shenker) 改进是把 black 结点的页改成 write-protected，page fault handler 更改权限为 writable，并且标记为灰色（但这么做也有性能问题）；

  • Method 3 (Baker)：在读灰结点 object 的白子结点时提前将该白结点染灰（纳入 GC 管理），这样 mutator 永远无法获得一个不受 GC 管理的指针了！因此就不会出现 invariant 的违反问题；

    (Appel, Ellis, Li) 改进还是利用 page fault，但这个时候直接从灰结点开始进行一次 GC，染成黑色-灰色的结点；

于是，我们基于 Copy Collection 的 Cheney’s Algorithm 实现一个 Incremental Collection 算法 (read)：Baker’s Algorithm；

基本前提：应用（mutator）和 GC（collector）处于同一线程中；

定时策略：仅 allocate memory 时交互进行；

仍然把 heap 分为 from-space 和 to-space 两个部分；

GC 过程仍然从堆内存满了后开始，但不是一次性做完，而是每次 allocation 时增量地做一点；步骤如下：

  1. 当堆（from-space）满后，交换二者角色，现在 from-space 变成空的一边；并且立即 forward root 结点到 from-space；

  2. 第一步结束后，不继续复制，而是先退出 GC 例程，回到应用（有点像协程 coroutine）；当应用在 GC 例程暂停期间 allocate 堆时，会再次唤醒 GC，此时：

    • 会直接分配在空的 from-space 的末端（减小 limit 的指针位置）；

    • 对应的扫描并从 to-space 中复制已分配记录（注意，如果分配了 N bytes 空间，那么从 to-space 扫描的大小不小于 N bytes，为了 copy 的过程不慢于应用分配的速度）。注意 forwarding pointers；

  3. 第一步结束后，如果应用在 GC 例程暂停期间 load references，创建了指向 to-space entry（这个 entry 是没有被复制到 from-space 过的）的 root 结点，那么根据 tricolor marking 理论，此时 to-space 中未被复制到 from-space 的 entries 全是白结点（没有被 GC 遍历过），这相当于直接将黑结点指向白结点（违反 invariant 1）。我们立即做一次 forward（但不关心它内部的 forwarding pointers）：

    如果指向的 to-space entry 是已被复制的，那么立即 forward：

  4. 当 scan 碰上 next 时，allocation 结束，本轮 GC 再次暂停，控制权又回到应用；

    只要保证 $R\lt\dfrac{1}{4}H$，在上述过程中就不会出现 GC 扫描时 from-space 用完的情况；

总结一下 incremental collection 的优缺点：

  • 优点：时延低，把复制的操作均摊到每次 allocation 时，减小了单次的 STW 时长，对 real-time app（例如浏览器/端侧设备渲染、游戏应用等等）友好；
  • 缺点：总体开销很大，每次 read 都多两条指令（compare & jump）；性能开销高出 20%（而且还没有考虑 locality）；

8.7 Concurrent Collection

之前我们讨论的是同步 GC，有没有异步 GC 呢？有的。就像前面说的，无论如何都需要 STW 来同步信息，只不过 STW 的长短罢了。在并行 GC 中，STW 的大部分工作都在 synchronization 中；

这里全部展开的话篇幅过长，我们按下不表，在后面讨论 Java 的并行 GC 的算法时再作介绍。

8.8 Parallel Scanvenge (Java)

一个内存密集型设计比较成功的语言。因此 Java 的 GC 设计的比较成熟。

2010 年左右的时间，Java 8 默认使用的是 Parallel Scavenge (PS) 这种 GC 策略。

定时策略：某个 semi-space 满了后；

它其实也是一种 Generation GC 的策略（stop-copy-compact，也有 STW 存在）。不过 Parallel Scavenge 对于新代和旧代的 GC 算法是不同的。总体结构如下：

注意到，Young Generation（新代）中存在 3 个 semi space: Eden、From、To，使用 Minor GC 算法如下：

  1. Application allocate 空间时向 Eden 区域直接插入；
  2. Eden-space 满了后，从 root 遍历复制 reachable records 到 to-space；
  3. 当 Eden-space 再次满了/ to-space 满了后，同时从 root 遍历复制 reachable records 到 from-space；
    • 其中在 to-space 中存活 K 轮的 records，会被 promote 到 old generation(s) 中；
  4. 在一轮复制结束后，如果 from-space 快满了，则交换 to-space 和 from-space 的身份；

Minor GC 如何并行与 Application 执行（parallel execution）？

  • Reference Tracking；
  • Copy Race（Queue & CAS）；
  • Work Stealing；

对于旧代（Old Generation）使用 Full/Major GC 算法：

一般要执行 Full GC，那么这时可能剩余内存已经不多了。

  • Marking: Mark all live objects;

  • Summary: Calculate new address for live objects;

    先算出地址，而不是上来就 copy，方便后面的 compaction；

  • Compact: Move objects and update references;

    需要考虑一个问题，如果 destination 也是 source 呢？

PS 这种策略也有些缺陷，例如空间是连续的（难以 split/adjust/reorganize），并且比例固定（在 VM 启动后固定）：

而且 Minor GC（4 GB ~）一般在 100ms 左右，Major GC （16 GB ~）一般多于 1s。

为了改进这个问题，我们可以：

  • 将 heap 的结构从 space 改成 regions（分块，smaller, segregated regions）：

  • Also including young and old spaces: Adding a middleground between old and young，这被称为 Mixed GC；

  • Collection set: including all regions to be collected；

当然，Parallel Scanvenge 有很强的特点，就是它是吞吐量垃圾收集器（Throughput Collector），它的设计目标是最大化应用程序的吞吐量。也就是说它适用于对吞吐量要求较高的应用程序，例如适合批处理任务或后台处理任务。

8.9 G1GC (Java)

Garbage First GC（G1GC）主要也是采用了 Generation GC 的思想，不过具体细节有些改动。

它将 Heap 分成 3 个部分，有点类似之前的 Parallel Scanvenge + Mixed GC 改进 + Collection Set 改进：

  • Eden: This is where newly created objects are allocated.
  • Survivor: There are typically two Survivor regions (S0 and S1), and they are used to hold objects that have survived one or more garbage collection cycles.
  • Old Generation: This region is used to hold long-lived objects that have survived multiple garbage collection cycles.

这里这篇文章描述的比较好，可以看看：How G1GC Work in Java；

算法则主要分为 3 个阶段：

  • 标记阶段，即从 Roots References 开始，标记活跃对象；
    • 此阶段一开始寻找 root 时需要 STW，不过因为数量很少，因此时间较短；
    • 然后需要遍历 reachable graph，此时是 concurrent mark，因此不需要 STW；
  • 转移阶段，即把活跃对象复制到新的内存地址上；
  • 重定位阶段，因为转移导致对象的地址发生了变化，在重定位阶段，所有指向对象旧地址的指针都要调整到对象新的地址上。

这里我们重点关注 G1GC 针对 Young GC 和 Mixed GC 的算法上，其主要流程如下：

此外，除了 Mixed GC 调整年轻代和年老代的回收阈值、heap 的分区收集结构，以及更强的并发能力以外，G1GC 还提供了预测性暂停时间 的特性，可以通过设置目标暂停时间（Pause Time Goal）来控制垃圾收集的暂停时间。

最后，G1GC 是为多核处理器和大内存系统设计的，旨在替代 CMS（Concurrent Mark-Sweep，注意到历史原因）的并发垃圾收集器（也是 Concurrent GC 的一种）。

8.10 ZGC (Java)

这是 Java 中的一个更新的 GC 机制。它在 Java 11 中实验性使用，在 Java 15 及以后可以正式作为生产环境的一种选择了。

ZGC 致力于提供尽可能短的 STW 时间。它的目标是：

  • STW 时间不超过 10 ms；
  • STW 时间不会随着堆的大小，或者活跃对象的大小而增加；
  • 支持 8 MB~4 TB 级别的堆（未来支持 16 TB）。

这主要是想匹配服务器应用程序的使用场景。因为在服务器应用程序中，大堆很常见（通常程序运行时间更长、运行的守护进程更多），而且需要快速的应用程序响应时间。

ZGC 有两种算法，一种是 Generational 的（分代），这个和前面 G1GC 以及 Parallel Scanvenge 比较相似，能够利用到分代的好处（吞吐量上升和更低的时延）；也有一种是 non-generational 的，主要是考虑到禁用分代后可以对某些使用场景进行运行时性能优化。这里我们为了简便，就讨论 non-generational 的实现。下面我们将不分代的 ZGC 单独称为 “ZGC”；

与 G1GC 的 Mixed GC 和 Young GC 类似，ZGC 也是采用标记然后复制的算法，不过 ZGC 对这部分的算法做了重大改进：ZGC 在标记、转移和重定位阶段几乎都是并发的。ZGC 垃圾回收周期如下图所示：

注意到 “初始标记” 就是我们在 G1GC 中讨论的，标记 root references，需要 STW、不能并发，不过时间很短。

Tricky Things

ZGC通过着色指针和读屏障技术，解决了转移过程中准确访问对象的问题，实现了并发转移。大致原理描述如下：并发转移中“并发”意味着GC线程在转移对象的过程中，应用线程也在不停地访问对象。假设对象发生转移，但对象地址未及时更新，那么应用线程可能访问到旧地址，从而造成错误。而在ZGC中，应用线程访问对象将触发“读屏障”，如果发现对象被移动了，那么“读屏障”会把读出来的指针更新到对象的新地址上，这样应用线程始终访问的都是对象的新地址。那么，JVM是如何判断对象被移动过呢？就是利用对象引用的地址，即着色指针。下面介绍着色指针和读屏障技术细节。

References Coloring

着色指针是一种将信息存储在指针中的技术。

ZGC 仅支持 64 位系统，它把 64 位虚拟地址空间划分为多个子空间，如下图所示：

其中，[0~4TB) 对应 Java 堆，[4TB ~ 8TB) 称为 M0 地址空间，[8TB ~ 12TB) 称为 M1 地址空间，[12TB ~ 16TB) 预留未使用，[16TB ~ 20TB) 称为 Remapped 空间。

当应用程序创建对象时，首先在堆空间申请一个虚拟地址，但该虚拟地址并不会映射到真正的物理地址。ZGC 同时会为该对象在 M0、M1 和 Remapped 地址空间分别申请一个虚拟地址，且这三个虚拟地址对应同一个物理地址，但这三个空间在同一时间有且只有一个空间有效。ZGC 之所以设置三个虚拟地址空间，是因为它使用“空间换时间”思想，去降低 GC 停顿时间。“空间换时间”中的空间是虚拟空间，而不是真正的物理空间。后续章节将详细介绍这三个空间的切换过程。

与上述地址空间划分相对应，ZGC 实际仅使用 64 位地址空间的第 0~41 位，而第 42~45 位存储元数据，第 47~63 位固定为 0。

ZGC 将对象存活信息存储在 42~45 位中，这与传统的垃圾回收（例如 Reference Count）并将对象存活信息放在对象头中的策略是不相同的。

Load Barriers

读屏障是 JVM 向应用代码插入一小段代码的技术。当应用线程从堆中读取对象引用时，就会执行这段代码。需要注意的是，仅“从堆中读取对象引用”才会触发这段代码。

读屏障示例：

1
2
3
4
5
Object o = obj.FieldA;    // 从堆中读取引用，需要加入屏障
<Load barrier>
Object p = o;            // 无需加入屏障，因为不是从堆中读取引用
o.dosomething();        // 无需加入屏障，因为不是从堆中读取引用
int i =  obj.FieldB;    //无需加入屏障，因为不是对象引用

ZGC 中读屏障的代码作用：在对象标记和转移过程中，用于确定对象的引用地址是否满足条件，并作出相应动作。

8.11 Summary

总的来说，虽然垃圾收集器的技术在不断进步，但直到现在还没有最好的收集器出现，因为不存在“万能”的收集器，只有适合某些使用场景的垃圾回收器。

Chapter 9. JDNI & SPI

Java Oracle Doc 一目了然：

Java Naming and Directory Interface (JNDI) 是一个应用程序编程接口 (API)，为使用 Java 编程语言编写的应用程序提供命名和目录功能。它的定义独立于任何特定的目录服务实现。因此，各种目录，无论新的、正在出现的和已经部署的，都可以用一种通用的方式访问。

而 JNDI 体系结构包括一个 API 和一个服务提供商接口 (SPI)。Java 应用程序使用 JNDI API 访问各种命名和目录服务。SPI 使各种命名和目录服务能以透明方式插入，从而允许使用 JNDI API 的 Java 应用程序访问它们的服务。

补充：什么是 SPI？

SPI 即 Service Provider Interface ，字面意思就是：“服务提供者的接口”，我的理解是：专门提供给服务提供者或者扩展框架功能的开发者去使用的一个接口。

SPI 将服务接口和具体的服务实现分离开来，将服务调用方和服务实现者解耦，能够提升程序的扩展性、可维护性。修改或者替换服务实现并不需要修改调用方。

SPI 和 API 有什么区别吗？下面一个图就能弄清楚：

  • 当实现方提供了接口和实现，我们可以通过调用实现方的接口从而拥有实现方给我们提供的能力，这就是 API。这种情况下，接口和实现都是放在实现方的包中。调用方通过接口调用实现方的功能，而不需要关心具体的实现细节。
  • 当接口存在于调用方这边时，这就是 SPI 。由接口调用方确定接口规则，然后由不同的厂商根据这个规则对这个接口进行实现，从而提供服务。

补充：SPI 出现的原因是？

面向对象设计鼓励模块间基于接口而非具体实现编程，以降低模块间的耦合，遵循依赖倒置原则，并支持开闭原则（对扩展开放，对修改封闭）。然而，直接依赖具体实现会导致在替换实现时需要修改代码，违背了开闭原则。为了解决这个问题，SPI 应运而生，它提供了一种服务发现机制，允许在程序外部动态指定具体实现。这与控制反转（IoC）的思想相似，将组件装配的控制权移交给了程序之外（IoC 比较著名的例子就是 Spring Framework）。