垃圾回收概念

程序创建对象等引用类型实体时会在虚拟内存中分配给它们一块内存空间，如果该内存空间不再被任何引用变量引用时就成为需要被回收的垃圾。操作系统会记录一个进程运行时的所占用的内存、CPU和寄存器等资源，当进程结束后便由操作系统能够自动回收资源。但是对于一个运行较长时间的程序，如果使用完内存资源后没有及时释放就会造成内存泄漏甚至系统错误。

C++
deletewild pointer
C++C++
GolangC++CPU

1. 垃圾回收过程

MutatorAllocatorHeapCollectorGolang



2. 自动垃圾回收与手动垃圾回收

CmallocfreeC
mallocfree
CC++RustPythonJavaGolang

3. 垃圾回收目标

垃圾回收器主要包括三个目标：

  • 无内存泄漏：垃圾回收器最基本的目标就是减少防止程序员未及时释放导致的内存泄漏，垃圾回收器会识别并清理内存中的垃圾
  • 自动回收无用内存：垃圾回收器作为独立的子任务，不需要程序员显式调用即可自动清理内存垃圾
  • 内存整理：如果只是简单回收无用内存，那么堆上的内存空间会存在较多碎片而无法满足分配较大对象的需求，因此垃圾回收器需要重整内存空间，提高内存利用率


垃圾回收的常见方法

GC0Mark-SweepMark-CopyMark-Compact

1. 引用计数

Reference countingGCpythonphpobjective-CC++std::shared_ptr
pythonpython
ob_refcnt

引用计数法优点包括：

0GC

缺点包括：

ObjAObjBObjBObjA0

2. 追踪基础：可达性分析算法

Mark
GC RootGC RootReference Chain

对于“不可达”的对象，我们可以认为该对象为垃圾对象并回收对应的内存空间。



java
Strong ReferenceObject obj = new Object()Soft ReferenceReferenceQueueJVMGCOOMWeak ReferenceJVMPhantom ReferenceGC

同引用计数法相比，追踪式算法具有如下优点：

  • 解决了循环引用对象的回收问题
  • 占用空间更少

缺点包括：

GCStop The World, STW

3. 标记-清除算法

Mark-Sweep
  • 标记：记录需要回收的垃圾对象
  • 清除：在标记完成后回收垃圾对象的内存空间



优点包括：

  • 算法吞吐量较高，即运行用户代码时间 / （运行用户代码时间 + 运行垃圾收集时间）较高
  • 空间利用率高：同标记-复制相比不需要额外空间复制对象，也不需要像引用计数算法为每个对象设置引用计数器

缺点包括：

  • 清除后会产生大量的内存碎片空间，导致程序在运行时可能没法为较大的对象分配内存空间，导致提前进行下一次垃圾回收

4. 标记-复制算法

Mark-Copy



优点包括：

GC RootGC

缺点包括：

  • 同标记-清除法相比，在“可达”对象占比较高的情况下有复制对象的开销
  • 内存利用率较低，相当于可利用的内存仅有一半

5. 标记-整理算法

Mark-Compact



优点包括：

  • 避免了内存碎片化的问题
  • 在对象存活率较高的情况下，标记-整理算法由于不需要复制对象效率更高，因此更加适合老年代算法

缺点包括：

STW

6. 三色标记法

STWGC
  • 白色：未搜索的对象，在回收周期开始时所有对象都是白色，在回收周期结束时所有的白色都是垃圾对象
  • 灰色：正在搜索的对象，但是对象身上还有一个或多个引用没有扫描
  • 黑色：已搜索完的对象，所有的引用已经被扫描完
GCGC Root

具体的实现如下：

GC Root

优点：

  • 不需要暂停整个程序进行垃圾回收

缺点：

  • 如果程序垃圾对象的产生速度大于垃圾对象的回收速度时，可能导致程序中的垃圾对象越来越多而无法及时收集
  • 线程切换和上下文转换的消耗会使得垃圾回收的总体成本上升，从而降低系统吞吐量

读写屏障技术

1. 三色标记法的并发性问题

假设三色标记法执行前，包含如下对象：



则三色标记法的具体执行过程如下：



DADD



2. 并发问题原因及解决思路

假设三色标记法和用户程序并发执行，那么下列两个条件同时满足就可能出现错误回收非垃圾对象的问题：

  • 条件1：某一黑色对象引用白色对象
  • 条件2：对于某个白色对象，所有和它存在可达关系的灰色对象丢失了访问它的可达路径

简单证明一下：如果条件1不满足，那么任何不该被回收的白色对象都能和至少一个灰色对象存在“可达”路径，因此不会有白色对象被遗漏；如果条件2不满足，那么对于某一个白色对象，即使它被黑色对象引用，但至少存在一个和它存在可达关系的灰色对象，因此这个白色对象也不会被回收。

一句话总结即是：在三色标记法执行的某个特定时机，只要存在未经访问的能够到达白色对象的可达路径，就可以令黑色对象引用白色对象，反正该白色对象在后面标记中会被识别为“可达”对象从而不会被错误回收。
STW, stop the world

3. 读写屏障技术

屏障技术：给代码操作内存的顺序添加一些限制，即在内存屏障前执行的动作必须先于在你内存屏障后执行的动作。

使用屏障技术可以使得用户程序和三色标记过程并发执行，我们只需要达成下列任意一种三色不变性：

  • 强三色不变性：黑色对象永远不会指向白色对象
  • 弱三色不变性：黑色对象指向的白色对象至少包含一条由灰色对象经过白色对象的可达路径
GChookhookRead barrier
STWSTW



4. Dijkstra插入写屏障

Dijkstra

一个对象可以存储在内存中的“栈”或者“堆”，由于“栈”空间容量小且要求相应速度较高，因此“插入写屏障”不适合用于“栈”空间。在“插入写屏障”保护下的三色标记法执行例子如下：







GC Root SetSTWSTWSTW
DijkstraMutator



DijkstraSTW

5. Yuasa删除写屏障

Yuasa*slot = ptrslotptr*slotAB



GC Root SetADDBCD
YuasaMutatorCollector
MutatorABCBMutatorBCC



YuasaDijkstraCollectorMutatorBCECE

6. 混合写屏障

6.1 引入混合写屏障的原因

go v1.8hybrid write barrierGC RootGC RootGoroutineDijkstraMarkgolang
Goroutinere-scan10~100 ms

回顾一下之前提到的两种写屏障的劣势：

DijkstraSTWYuasaSTWGC RootMutator

6.2 混合写屏障的实现

注意：混合写屏障也是仅在堆空间启动的，防止降低栈空间的运行效率

混合写屏障逻辑如下：

GCSTWGC

6.3 具体场景的实现

GC



场景一：某个对象从堆对象的下游变成栈对象的下游，这种情况下标记该对象为灰色，该对象就不会被错误地回收



场景二：某个对象从一个栈对象的下游变成另一个对象的下游，由于对象全都在栈空间对象的可达对象中，因此混合写屏障不会对这些对象着色。



G



G



8. 分代收集算法

most object die youngheap

8.1 分代收集算法的三个假设

  • 弱分代假说：大多数对象的生命周期都很短
  • 强分代假说：多轮垃圾回收都没清理掉的对象往往不容易死亡
  • 跨代引用假说：跨代引用和同代引用相比仅占一小部分

8.2 新生代分区和老年代分区

GC
YoungOld98%YoungEdenSurvivor0Survivor18:1:1Young10%SurvivorOldOld



YoungOldMinor GCMajor GC

8.3 对象的分配策略

YonugEdenOldYoung10%SurvivorSurvivorMinor GC

8.4 分代算法的大体流程

YoungOld
EdenOldEdenMinor GCEdenSurvivor0EdenEdenMinor GCEdenSurvivor0Survivor1EdenSurvivor0Minor GCMinor GCOldMinor GCSurvivorOldOldMajor GC

增量和并发式垃圾回收



STWCPU
GCCPU
CollectorSTW

1. 增量式垃圾回收



STW
  • 优势：将垃圾回收时间分摊开，避免了程序的长时间暂停，防止影响程序的实时性
  • 劣势：一方面引入了内存写屏障技术，需要额外的计算开销；另一方面由于写屏障技术的保守性导致有一些垃圾对象没有被回收，会增加一轮垃圾回收的总时长

2. 并发式垃圾回收



collectormutator

Golang GC如何扫描对象[见Reference14]

Golang扫描对象可以分为三部分：

  • 编译阶段：对静态类型做好标记准备
  • 运行阶段：赋值器分配内存时，根据编译阶段的type为对象内存对应的指针设置bitmap
  • 扫描阶段：根据指针的bitmap进行扫描

1. 编译阶段

1.1 Golang结构体对齐规则

Golang结构体对齐规则包括两部分：

  • 长度对齐
  • 地址对齐

1.2 长度对齐

长度对齐指的是结构体的长度至少是内部最长的基础字段的整数倍。比如下面这个结构体内存占用为16个字节，因为TestStruct整体要和内部最长的基础字段ptr（8字节的uintptr类型）对齐。

1.3 地址对齐

字段的地址偏移是自身长度的整数倍，仍然以TestStruct为例，令第二个元素为1个字节大小：

int1和int2之间填充了一些没使用到的内存空间，进而实现了地址对齐。

1.4 指针位标记

golang的所有类型都对应一个_type结构：

比如说我们定义一个struct如下：

pint2
第一个类型uintptr在指针的bitmap是不会标记成指针类型的，用这个存储指针是无法保护对象的（扫描的时候uintptr指向的对象不会被扫描）。

2. 运行期内存分配

heapBitsSetType

3. 运行扫描阶段

  • 扫描阶段从markroot开始，以栈对象、全局变量和寄存器对象作为gc root，创建一个有向引用图并将根对象添加到队列中
  • 新起一个异步goroutine执行gcDrain函数，从队列里消费并扫描对象

Golang GC

1. Golang GC发展历史

Golang
gc pause
go v1.1STWgo v1.3STWgc pausemsgo v1.5STWgc pause10msgo v1.8GCgc pause0.5msgo v1.14

2. 回顾Golang内存管理内容

GoX64512M16G512Gspansbitmaparena
arena8KBbitmaparenabitmaparena48Bbitmap512GB/(4*8)=16GB
spansmspanmspanspans8Barenapage8KBspans512GB/(1024)=512MB

3. Golang GC实现【见Reference5】

go v1.5STWSTWGolang
GCGC Rootgolanggoroutine

3.1 Golang GC四个阶段

前面提到Golang的GC属于并发式垃圾回收（意味着不需要长时间的STW，GC大部分执行过程是和用户代码并行的），它可以分为四个阶段：

Sweep TerminationMark_GCmarkMutator AssisteMutator AssisteMark Termination_GCmarkterminationSweep_GCoff
在GC过程中会有两种后台任务（G），包括标记任务和清扫任务。可以同时执行的标记任务约是P数量的四分之一，即go所说的25%CPU用于GC的依据。清扫任务会在程序启动后运行，进入清扫阶段时唤醒。

3.2 辅助GC

由于Golang使用了并发式的垃圾回收，将原本需要STW较长时间的GC过程分散到多次小规模的GC。当用户分配内存的速度超过GC回收速度时，Golang会通过辅助GC暂停用户程序进行垃圾回收，防止内存因分配对象速度过快消耗殆尽的问题。

3.3 GC触发时机

触发垃圾回收首先要满足三个前提条件：

memstats.enablegcpanicking == 0gcphase == _GCoff_Gcoff

对应的触发时机包括：

gcTriggerHeapgcTriggerTimegcTriggerCycle

4. GC调优常见方法

int8int+stringstrings.Joinbytes.Buffer

Reference