在计算机科学中，垃圾回收（Garbage Collection，GC）是自动内存管理的一种形式，通常由垃圾收集器收集并适时回收或重用不再被对象占用的内存。垃圾回收作为内存管理的一部分，包含3个重要的功能：分配和管理新对象、识别正在使用的对象、清除不再使用的对象。
5种经典算法
标记-清扫
分为两个主要阶段，第1阶段是扫描并标记当前活着的对象，第2阶段是清扫没有被标记的垃圾对象。因此，标记-清扫算法是一种间接的垃圾回收算法，它不直接查找垃圾对象，而是通过活着的对象推断出垃圾对象。
主要缺点在于可能产生内存碎片或空洞，这会导致新对象分配失败。
标记-压缩
标记-压缩（Mark-Compact）算法通过将分散的、活着的对象移动到更紧密的空间来解决内存碎片问题。标记-压缩算法分为标记与压缩两个阶段，在压缩阶段，需要扫描活着的对象并将其压缩到空闲的区域，这可以保证压缩后的空间更紧凑，从而解决内存碎片问题。同时，压缩后的空间能以更快的速度查找到空闲的内存区域（在已经使用内存的后方）。
缺点在于内存对象在内存的位置是随机的，这常常会破坏缓存的局部性，并且时常需要一些额外的空间来标记当前对象已经移动到了其他地方。
半空间复制
半空间复制（Semispace Copy）是一种用空间换时间的算法。经典的半空间复制算法只能使用一半的内存空间，保留另一半的内存空间用于快速压缩内存。
半空间复制的压缩性消除了内存碎片问题，同时，其压缩时间比标记-压缩算法更短。半空间复制不分阶段，在扫描根对象时就可以直接压缩，每个扫描到的对象都会从fromspace的空间复制到tospace的空间。因此，一旦扫描完成，就得到了一个压缩后的副本。
引用计数
每个对象都包含一个引用计数，每当其他对象引用了此对象时，引用计数就会增加。反之，取消引用后，引用计数就会减少。一旦引用计数为0，就表明该对象为垃圾对象，需要被回收。
引用计数算法简单高效，在垃圾回收阶段不需要额外占用大量内存，即便垃圾回收系统的一部分出现异常，也能有一部分对象被正常回收。
但这种朴素的算法也有一些致命的缺点：一些没有破坏性的操作，如只读操作、循环迭代操作也需要更新引用计数，栈上的内存操作或寄存器操作更新引用计数是难以接受的。同时，引用计数必须原子更新，并发操作同一个对象会导致引用计数难以处理自引用的对象。
分代GC
将对象按照存活时间进行划分。这种算法的重要前提是：死去的对象一般都是新创建不久的，因此，没有必要反复地扫描旧对象，这大概率会加快垃圾回收的速度，提高处理能力和吞吐量，减少程序暂停的时间。
但是分代GC也不是没有成本的，这种算法没有办法及时回收老一代的对象，并且需要额外开销引用和区分新老对象，特别是在有多代对象的时候。
Go语言中的垃圾回收
Go语言采用了并发三色标记算法进行垃圾回收。三色标记是最简单的垃圾回收算法，其实现也很简单。
- 引用计数由于其固有的缺陷在并发时很少使用，不适合Go这样的高并发语言。
- 压缩算法的主要优势是减少碎片并且快速分配。Go语言使用了现代内存分配算法TCmalloc，虽然没有压缩算法那样极致，但它已经很好地解决了内存碎片的问题。并且，由于需要加锁，压缩算法并不适合在并发程序中使用。
- 分代GC的主要假设是大部分变成垃圾的对象都是新创建的，但是由于编译器的优化，Go语言通过内存逃逸的机制将会继续使用的对象转移到了堆中，大部分生命周期很短的对象会在栈中分配，这和其他使用分代GC的编程语言有显著的不同，减弱了使用分代GC的优势。同时，分代GC需要额外的写屏障来保护并发垃圾回收时对象的隔代性，会减慢GC的速度。
Go垃圾回收演进
- Go 1.0的单协程垃圾回收，在垃圾回收开始阶段需要停止所有的用户协程，并且在垃圾回收阶段只有一个协程执行垃圾回收。
- 在Go 1.1之后，垃圾回收由多个协程并行执行，大大加快了垃圾回收的速度，但是这个阶段仍然不允许用户协程执行
- Go 1.5对垃圾回收进行了重大更新，该版本允许用户协程与后台的垃圾回收同时执行，大大降低了用户协程暂停的时间（从300ms左右降低到40ms左右）
- Go 1.6大幅度减少了在STW（Stop TheWorld）期间的任务，使得用户协程暂停的时间从40ms左右降到5ms左右。
- Go 1.8使用了混合写屏障技术消除了栈重新扫描的时间，将用户协程暂停的时间降低到0.5ms左右。
垃圾回收全流程
当内存到达了垃圾回收的阈值后，将触发新一轮的垃圾回收。之后会先后经历标记准备阶段、并行标记阶段、标记终止阶段及垃圾清扫阶段。在并行标记阶段引入了辅助标记技术，在垃圾清扫阶段还引入了辅助清扫、系统驻留内存清除技术。
标记准备阶段
任务是清扫上一阶段GC遗留的需要清扫的对象，因为使用了懒清扫算法，所以当执行下一次GC时，可能还有垃圾对象没有被清扫。 标记准备阶段会为每个逻辑处理器P启动一个标记协程，但并不是所有的标记协程都有执行的机会，因为在标记阶段，标记协程与正常执行用户代码的协程需要并行，以减少GC给用户程序带来的影响。
计算标记协程的数量
在标记准备阶段，会计算当前后台需要开启多少标记协程。目前，Go语言规定后台标记协程消耗的CPU应该接近25%。
切换到后台标记协程
在标记准备阶段执行了STW，此时暂停了所有协程。当关闭STW准备再次启动所有协程时，每个逻辑处理器P都会进入一轮新的调度循环，在调度循环开始时，调度器会判断程序是否处于GC阶段，如果是，则尝试判断当前P是否需要执行后台标记任务。
并发标记阶段
在并发标记阶段，后台标记协程可以与执行用户代码的协程并行。Go语言的目标是后台标记协程占用CPU的时间为25%，以最大限度地避免因执行GC而中断或减慢用户协程的执行。后台标记任务有3种不同的模式。
- DedicatedMode代表处理器专门负责标记对象，不会被调度器抢占。
在DedicatedMode下，会一直执行后台标记任务，这意味着当前逻辑处理器P本地队列中的协程将一直得不到执行，这是不能接受的。所以Go语言的做法是先执行可以被抢占的后台标记任务，如果标记协程已经被其他协程抢占，那么当前的逻辑处理器P并不会执行其他协程，而是将其他协程转移到全局队列中，并取消gcDrainUntilPreempt标志，进入不能被抢占的模式。
- FractionalMode代表协助后台标记，在标记阶段到达目标时间后，会自动退出。
- IdleMode代表当处理器没有查找到可以执行的协程时，执行垃圾收集的标记任务，直到被抢占。
根对象扫描
扫描的第一阶段是扫描根对象。在最开始的标记准备阶段会统计这次GC一共要扫描多少对象。 根对象是最基本的对象，从根对象出发，可以找到所有的引用对象（即活着的对象）。在Go语言中，根对象包括全局变量（在.bss和.data段内存中）、span中finalizer的任务数量，以及所有的协程栈。finalizer是Go语言中对象绑定的析构器，当对象的内存释放后，需要调用析构器函数，从而完整释放资源。
全局变量扫描
扫描全局变量需要编译时与运行时的共同努力。只有在运行时才能确定全局变量被分配到虚拟内存的哪一个区域，另外，如果全局变量有指针，那么在运行时其指针指向的内存可能变化。而在编译时，可以确定全局变量中哪些位置包含指针。
finalizer
析构器不会被栈上或全局变量引用，需要单独处理。
在标记期间，后台标记协程会遍历mspan中的specials链表，扫描finalizer所位于的元素（对象），并扫描当前元素（对象）
栈扫描
栈扫描需要编译时与运行时的共同努力，运行时能够计算出当前协程栈的所有栈帧信息，而编译时能够得知栈上有哪些指针，以及对象中的哪一部分包含了指针。运行时首先计算出栈帧布局，每个栈帧都代表一个函数，运行时可以得知当前栈帧的函数参数、函数本地变量、寄存器SP、BP等一系列信息。每个栈帧函数的参数和局部变量，都需要进行扫描，确认该对象是否仍然在使用，如果在使用则需要扫描位图判断对象中是否包含指针。
栈对象
栈对象是在栈上能够被寻址的对象。编译器会在编译时将所有的栈对象都记录下来，同时，编译器将追踪栈中所有可能指向栈对象的指针。在垃圾回收期间，所有的栈对象都会存储到一棵二叉搜索树中。
扫描灰色对象
在进行根对象扫描时，会将标记的对象放入本地队列中，如果本地队列放不下，则放入全局队列中。这种设计最大限度地避免了使用锁，在本地缓存的队列可以被逻辑处理器P无锁访问。
在进行扫描时，使用相同的原理，先消费本地队列中找到的标记对象，如果本地队列为空，则加锁获取全局队列中存储的对象。在标记期间、会循环往复地从本地标记队列获取灰色对象，灰色对象扫描到的白色对象（即还没有被标记）仍然会被放入标记队列中，并把灰色节点标记为黑色，如果扫描到已经被标记的对象则忽略，一直到队列中的任务为空为止。
标记终止阶段
完成并发标记阶段所有灰色对象的扫描和标记后进入标记终止阶段，标记终止阶段主要完成一些指标，例如统计用时、统计强制开始GC的次数、更新下一次触发GC需要达到的堆目标、关闭写屏障等，并唤醒后台清扫的协程，开始下一阶段的清扫工作。标记终止阶段会再次进入STW。
计算下一次触发GC时需要达到的堆目标，这叫作垃圾回收的调步算法。调步算法是Go 1.5提出的算法，由于从Go 1.5开始使用并发的三色标记，在GC开始到结束的过程中，用户协程可能被分配了大量的内存，所以在GC的过程中，程序占用的内存（后简称占用内存）的大小实际上超过了设定的触发GC的目标。为了解决这样的问题，需要对程序进行估计，从而在达到内存占用量目标（后简称目标内存）之前就启动GC，并保证在GC结束之后，占用内存的大小刚好在目标内存附近。
辅助标记
在并发标记阶段，扫描内存的同时用户协程也不断被分配内存，当用户协程的内存分配速度快到后台标记协程来不及扫描时，GC标记阶段将永远不会结束，从而无法完成完整的GC周期，造成内存泄漏。
辅助标记必须在垃圾回收的标记阶段进行，由于用户协程被分配了超过限度的内存而不得不将其暂停并切换到辅助标记工作。所以一个简单的策略是让X=M，其中，X为后台标记协程需要多扫描的内存，M为新分配的内存。即在并发标记期间，一旦新分配了内存M，就必须完成M的扫描工作。
屏障技术
在并发标记写入和删除对象时，可能破坏三色不变性，因此必须有一种机制能够维护三色不变性，这就是屏障技术。屏障技术的原则是在写入或者删除对象时将可能活着的对象标记为灰色。
垃圾清扫
垃圾标记工作完成意味着已经追踪到内存中所有活着的对象（虽然可能有一些浮动垃圾），之后进入垃圾清扫阶段，将垃圾对象的内存回收重用或返还给操作系统。
程序中只有一个垃圾清扫协程，并在清扫阶段与用户协程同时运行。当清扫协程被唤醒后，会开始垃圾清扫。垃圾清扫采取了懒清扫的策略，即执行少量清扫工作后，通过Gosched函数让渡自己的执行权利，不需要一直执行。因此当触发下一阶段的垃圾回收后，可能有没有被清理的内存，需要先将它们清理完。
懒清扫
以span为单位进行的，先从mheap中的sweepSpans队列中取出需要清扫的span。整个span将会被mheap回收，并更新整个基数树，表明当前span的整个空间都可以被程序再次使用。如果当前span的整个空间并不完全为空，那么span会被重新放入sweepSpans正在使用的span列表中。
这种回收方式并没有直接将内存释放到操作系统中，而是再次组织内存以便能在下次内存分配时利用已经被回收的内存。
辅助清扫
辅助清扫即工作协程必须在适当的时机执行辅助清扫工作，以避免下一次GC发生时还有大量的未清扫span。判断是否需要清扫的最好时机是在工作协程分配内存时。
目前Go语言会在两个时机判断是否需要辅助扫描。一个是在需要向mcentrel申请内存时，一个在是大对象分配时。
系统驻留内存清除
基数树的叶子节点管理了一个chunk块大小的内存。基本思路是在基数树中找到连续的没有被操作系统回收的内存，一次只清除一个物理页。
