主流的垃圾回收机制都有哪些？

　　前面有不少回答了，其中有部分靠谱的内容，感觉要补充也挺麻烦的，俺就放个俺推荐的书单吧：

　　但是这个“标记清除”跟一般的标记清除还是有点差别的，全名是“局部标记清除”，它基于引用计数

　　这个算法最早好像是出现在fortran，虽然流程都是“确定根集合-标记-清除”，但是和普通MS算法不同的是，第一步确定根集合是基于引用计数来做的，它不是以“栈、全局变量”之类的东西作为根集合起点，而是随便给个堆上对象的集合都可以根据引用计数算出这个集合的“根”，也就是说根本不需要跟踪或扫描栈和全局区域

　　具体做法也很简单：对于任何对象集合，我们先弄个表存它们的引用计数的副本，然后把内部引用都拆掉，所谓内部引用是指这个集合中的某个对象引用了另一个本集合内部的对象，拆的过程中减少引用计数，当然是在副本表里面减少

　　全部拆除后，引用计数依然不为0的，就是根集合，然后开始标记过程，标记其实不需要任何染色，只要逐步恢复引用并增加副本表的引用计数即可

　　随便抽出6个对象作为一个集合，这个集合有外部进来的连接（到a和b），也有到外部的连接（c引用了外面某个对象），但这个都无所谓，重要的是其内部连接，右边是引用计数表，然后我们拆掉所有内部连接：

　　从a和b出发可达的都被回复了，引用计数还是0的就是这个集合内部循环引用的垃圾（e和f）

　　如果你把所有对象看做一个集合，那么这个算法每次都可以回收所有垃圾，当然，性能是另码事

　　你也可以将对象划分为一个个小的集合，分别来回收，但这时候的效果就取决于你是否能尽量将循环引用的垃圾划分到每个集合中，集合划分粒度越粗，回收效果越好，但是速度越慢，反之亦然

　　python的做法是分代，每一代作为一个集合，其他语言的GC中的分代需要额外记录各代之间的引用，但是python基于引用计数，反而不需要了

　　补充：这个算法作为引用计数的补充，最大好处就是不需要runtime环境支持栈和全局空间的扫描，譬如说，你在C++中用智能指针配合自己写的对象申请和释放器，理论上讲是可以解决循环引用问题而不需要关心栈和全局区的“根集合”，这样就算智能指针和普通手工申请释放两种机制混合用也没问题，唯一麻烦的地方是，你需要对每个shared_ptr维护的对象实现遍历引用和标记。另一个好处是，虽然你的代码有很多类都会用引用计数来维护，但并不是每个类都是容器类，而非容器类的对象显然不可能出现循环引用，单纯的引用计数就足够了，因此上面算法仅针对容器即可

　　更进一步地，如果上面这些用一个编译器分析处理，还可以分析出那些类是会进入引用计数管理，给这些类自动生成标记清除的相关方法代码，以及进一步分析哪些类可能形成循环引用，哪些不可能形成，最终这个算法只需要处理必要的类型的对象即可

　　有一部分 GC 一定要遍历需要 GC 的对象的图，从而获得一个精确的哪个对象活着哪个对象死了的信息。我们称这种 GC 为 tracing GC，不需要遍历的称为 non-tracing GC （比如 reference counting，它只能获得一个近似的信息，所以无法处理图里的环）。

　　有的 GC 需要程序员/编译器提供合作，以精确的知道哪个 pointer 是对象（指需要 GC 的对象）。有的 GC 不需要，光靠猜（猜也是很难的！猜不出来就只能当做是 pointer 了），也能做到 GC。前者称之为 precise GC，后者称之为 conservative GC（比如 Boehm GC）。我们下面主要讨论 precise GC。

　　有的 GC 分配了内存之后，这块内存可能会被移动到另外一个地方去，防止内存碎片化，提高缓存局部性（cache locality，这个怎么翻译呢..），这种 GC 被称为 moving GC，而不这么做的 GC 就称为 non-moving GC。moving GC 自然都是 tracing GC，因为它们必须要知道怎么遍历需要 GC 的对象的图，不然没法移动（毕竟移动某个对象的时候，也要修改存有这个对象的地方的值，指向新的位置）。

　　有的 GC 一次处理整个对象图，有的 GC 则做了优化，一部分时间只处理较新的对象。这个优化是建立在一个现象上的：新的对象比较容易指向老的对象，而老的对象较少指向新的对象；新的对象比较容易死掉，而活了比较久的对象则很有可能会活更久。很多编程的方式都会造成这种现象，比如 immutable data structures 等等。那么针对性的，GC 就可以区分对象的年纪，把内存分配的区域分为（较大的）老区和（较小的，为了缓存局部性）新区，然后根据老区满了与否，每次 GC 判断到底是只需要 GC 新区还是全都需要 GC。如果只需要 GC 新区，那么遍历对象图的时候只要遇到了老区的对象，就直接当做这个对象是活着的，后面的图就不用看了，直接剪掉。遇到了新区的对象，就根据对象存活了几次 GC 来看要不要将其移动到老区里。当然这个现象并不是绝对的，还是会出现老对象指向新对象的情况，怎么办呢？这就要在每次修改对象的时候（这种做法被称为 GC write barrier，就是每次修改对象之前都要有个检查），检查被修改的对象是不是老对象，修改成的值是不是新对象，如果确实是这样，那么就用一种方法（比如 remembered set，card marking 等等）来记住这个例外的情况。这么做的 GC 称之为 generational GC。

　　，详见 sgc.c （代码里还是有不少噪声的.. 因为 stack 并不完全是一个 root set，需要避开一些位置）

　　是较为简单的一种 moving GC，就是分配 2 块一样大的内存，第一块用完了就开始 GC，将活着的对象移动到第二块上去，死了的就不管了，周而复始。我有一个玩具 Scheme JIT 里用到了它：

　　最近在整理Golang垃圾回收机制的背后原理，发现知乎在垃圾回收机制下的问答还没有人回答地比较完善，故抛砖引玉。

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

　　如果由于异常或者其他原因导致delete语句没有正常执行，且该函数被频繁调用，那么很容易占用所有系统内存从而导致程序崩溃，如果泄漏的是系统资源的话甚至还会导致系统崩溃。另一方面如果我们在不该释放内存的时候释放内存，那么仍然在使用这块内存的指针就会变成野指针wild pointer，使用该指针对内存进行读写是未定义的行为。

　　由于C++支持比较强大的指针计算功能，因此在C++中引入自动垃圾回收是一件比较困难的事情：

　　由于Golang没有C++这种对指针偏移的操作，因此可以在语言层面包含自动的垃圾回收功能，系统可以在CPU相对空闲的时候进行垃圾回收。

　　用户程序Mutator通过内存分配器Allocator在堆Heap上申请内存，垃圾回收器Collector会定时清理堆上的内存。内存分配器如何申请内存我们已经在前面Golang内存管理介绍过了，本篇主要介绍的是垃圾回收器如何清理内存。

　　C语言这种较为传统的语言通过malloc和free手动向操作系统申请和释放内存，这种自由管理内存的方式给予程序员极大的自由度，但是也相应地提高了对程序员的要求。C语言的内存分配和回收方式主要包括三种：

　　C、C++和Rust等较早的语言采用的是手动垃圾回收，需要程序员通过向操作系统申请和释放内存来手动管理内存，程序员极容易忘记释放自己申请的内存，对于一个长期运行的程序往往是一个致命的缺点。Python、Java和Golang等较新的语言采取的都是自动垃圾回收方式，程序员只需要负责申请内存，垃圾回收器会周期性释放结束生命周期的变量所占用的内存空间。

　　无内存泄漏：垃圾回收器最基本的目标就是减少防止程序员未及时释放导致的内存泄漏，垃圾回收器会识别并清理内存中的垃圾

　　自动回收无用内存：垃圾回收器作为独立的子任务，不需要程序员显式调用即可自动清理内存垃圾

　　内存整理：如果只是简单回收无用内存，那么堆上的内存空间会存在较多碎片而无法满足分配较大对象的需求，因此垃圾回收器需要重整内存空间，提高内存利用率

　　引用计数Reference counting会为每个对象维护一个计数器，当该对象被其他对象引用时加一，引用失效时减一，当引用次数归零后即可回收对象。使用这类GC方法的语言包括python、php、objective-C和C++标准库中的std::shared_ptr等。

　　其中ob_refcnt为引用计数器，当一个对象有新的引用时计数器增一，当引用它的对象被删除时计数器减一。

　　时间和空间成本较高：一方面是因为每个对象需要额外的空间存储引用计数器变量，另一方面是在栈上的赋值时修改引用次数时间成本较高（原本只需要修改寄存器中的值，现在计数器需要不断更新因此不是只读的，需要额外的原子操作来保证线程安全）

　　引用计数是一种摊销算法，会将内存的回收分摊到整个程序的运行过程，但是当销毁一个很大的树形结构时无法保证响应时间

　　尽管前面提到的三种追踪式垃圾回收算法实现起来各不相同，但是第一步都是通过可达性分析算法标记Mark对象是否“可达”。一般可到达的对象主要包括两类：

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

　　可达性算法中判断对象是否“可达”依赖于“引用”的定义，java中的引用从强到弱可分为四类，不同的引用类型可以满足多样化的场景：

　　：用于描述有用但非必需的对象，只有在内存不足的时候才会回收该对象，适合实现内存敏感的高速缓存（网页缓存和图片缓存等）；软引用可以和引用队列

　　进行垃圾回收时会直接回收被弱引用关联的对象，同软引用相比有更短的生命周期

　　：一个对象与虚引用关联时在任何时候都可以被垃圾回收器回收，因此并不会影响该对象的生命周期，主要用于跟踪对象被

　　回收的活动；虚引用必须和引用队列联合使用，当回收一个对象时如果发现它还有虚引用，就会在回收对象的内存之前将这个虚引用加入到与之关联的引用队列中，这样程序可以通过判断引用队列是否加入虚引用来判断被引用的对象是否将进行垃圾回收

　　标记-清除Mark-Sweep算法是最基础的追踪式算法，分为“标记”和“清除”两个步骤：

　　标记-复制Mark-Copy算法将内存分成大小相同的两块，当某一块的内存使用完了之后就将使用中的对象挨个复制到另一块内存中，最后将当前内存恢复未使用的状态。

　　标记-整理Mark-Compact算法综合了标记-清除法和标记-复制法的优势，既不会产生内存碎片化的问题，也不会有一半内存空间浪费的问题。该方法首先标记出所有“可达”的对象，然后将存活的对象移动到内存空间的一端，最后清理掉端边界以外的内存。

　　前面提到的“标记”类算法都有一个共同的瑕疵，即在进行垃圾回收的时候会暂停整个程序（STW问题）。三色标记法是对“标记”阶段的改进，在不暂停程序的情况下即可完成对象的可达性分析。GC线程将所有对象分为三类：

　　三色标记法属于增量式GC算法，回收器首先将所有的对象着色成白色，然后从GC Root出发，逐步把所有“可达”的对象变成灰色再到黑色，最终所有的白色对象即是“不可达”对象。

　　上述三色标记执行过后堆内存中白色对象（只有D）会被当做垃圾对象清理掉，如果用户在标记执行过程中建立了从A对象到D对象的引用，那么会导致后续对D的访问出错。这种没有指向合法地址的指针一般被称为“野指针”，会造成严重的程序错误。

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

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

　　一种最简单解决三色标记并发问题的方法是停止所有的赋值器线程，保证标记过程不受干扰，即垃圾回收器中常提到的STW, stop the world方法。另外一种思路就是使用赋值器屏障技术使得赋值器在进行指针写操作时同步垃圾回收器，保证不破坏弱三色不变性（见下文）。

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

　　GC中使用的内存读写屏障技术指的是编译器会在编译期间生成一段代码，该代码在运行期间用户读取、创建或更新对象指针时会拦截内存读写操作，相当于一个hook调用，根据hook时机不同可分为不同的屏障技术。由于读屏障Read barrier技术需要在读操作中插入代码片段从而影响用户程序性能，所以一般使用写屏障技术来保证三色标记的稳健性。

　　Dijkstra插入写屏障避免了前面提到的条件1，即防止黑色对象指向白色对象。

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

　　第三步：遍历灰色对象列表，将可达的对象从白色标记为灰色；将遍历完的灰色对象标记为黑色

　　第四步：在三色标记过程中用户程序令栈区对象A指向对象H，令堆区对象E指向对象I，由于对象E在堆区从而触发插入写屏障并将黑色对象E指向的白色对象I标记为灰色，栈区对象A不触发

　　第六步：由于栈区对象没有启动插入写屏障，因此栈上可能存在白色对象被引用的情况（上图中对应对象H），因此在回收白色对象前在

　　尽管Dijkstra插入写屏障可以实现垃圾回收和用户程序的并发执行，但是它存在两个缺点。一方面它是一种比较保守的垃圾回收方法，把有可能存活的对象都标记成灰色了以满足“强三色不变性”。以下图为例，用户程序Mutator将对象A原本指向B对象的指针改成指向C对象，尽管在修改后B对象已经是一个垃圾对象，但是它在本轮垃圾回收过程中不会被回收。

　　另外一个缺点在于栈上的对象也是根对象，Dijkstra插入写屏障要么在用户程序执行内存写操作时为栈上对象插入写屏障，要么在一轮三色标记完成后使用STW重新对栈上的对象进行三色标记。前者会降低栈空间的响应速度，后者会暂停用户程序。

　　Yuasa删除写屏障避免了前面提到的条件2，防止丢失灰色对象到白色对象的可达路径。当用户程序执行*slot = ptr时（即令slot指向了ptr），我们会将当前下游对象*slot标记为灰色。一句话解释就是当删除对象A指向对象B的指针时，那么将被删除的对象标记为灰色。

　　下图简单绘制了Yuasa删除写屏障是如何保证用户程序Mutator和垃圾回收器Collector的并发执行的：

　　Yuasa删除写屏障和Dijkstra插入写屏障相比优点在于不需要在一轮三色标记后对栈空间上的对象进行重新扫描，缺点在于Collector会悲观地认为所有被删除的对象都可能被黑色对象引用，比如上图中第三步Mutator删除了对象B指向对象C的指针，如果此时还有一个单独的对象E指向C，那么本该被删除的对象E却可以在本轮垃圾回收中存活。

　　在go v1.8引入混合写屏障hybrid write barrier之前，由于GC Root对象包括了栈对象，如果运行时在所有GC Root对象上开启插入写屏障意味着需要在数量庞大的Goroutine的栈上都开启Dijkstra写屏障从而严重影响用户程序的性能。之前的做法是Mark阶段（golang垃圾回收使用的是标记-清除法）结束后暂停整个程序，对栈上对象重新进行三色标记法。

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

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

　　场景三：某个对象从一个堆对象的下游变成另一个堆对象的下游，比如下图中对象G从F的下游移动到Y的下游，为了避免对象G被错误回收，我们需要将其标记为灰色

　　场景四：某个对象从栈对象的下游变成堆对象的下游，对于栈空间对象不触发写屏障，但是对于被删除的堆空间对象G需要标记成灰色以保护它和它的下游对象不被错误删除

　　前面提到追踪式垃圾回收算法一个显著的问题是会频繁扫描生命周期较长的对象，而内存分配存在一个most object die young（绝大部分对象的生命周期都很短）的事实，因此有必要将对象按照生命周期的长度划分到堆heap上的两个甚至多个区域。对于新生代区域的扫描频率应该高于老年代区域。

　　分代收集算法会将对象按照生命周期的长短划分到不同的分区。对于生命周期短的新生代区域，每次回收仅需要考虑如何保留少量的存活对象，因此可以采用标记-复制算法完成GC；对于生命周期长的老年代区域，可以通过减少垃圾回收的频率来提升效率，同时由于对象存活率高没有额外的空间用于复制，因此一般使用标记-清除算法或者标记-整理算法。

　　由于堆分为Young和Old两个分区，因此垃圾回收也根据回收的分区不同划分为新生代回收Minor GC和老年代回收Major GC。

　　前面提到传统的垃圾回收算法都有STW的弊端，即需要在执行垃圾回收过程中需要抢占CPU，这会暂停所有的用户程序。这有两个弊端：

　　任务都比较繁重，长时间暂停用户程序会影响程序的响应速度，这对于实时性要求较高的程序是致命的缺点

　　，因此后续提到的增量式垃圾回收和并发式垃圾回收都是基于三色标记法和读写屏障技术的。为了保证三色不变性，我们需要在垃圾回收前打开写屏障，在本轮垃圾回收过程中用户所有对内存的写操作都需要被写屏障拦截。

　　并发式垃圾回收允许垃圾回收器collector和用户程序mutator同时执行，但仍然有一些阶段需要暂停用户程序。并发式的垃圾回收机制在一定程序上利用了多核计算机的优势并减少了对用户程序的干扰，不过依然无法摆脱读写屏障的额外计算开销和增加一轮垃圾回收总时长的问题。

　　也欢迎关注我的知乎账号@石溪，将持续发布机器学习数学基础及Python数据分析编程应用等方面的精彩内容。

　　这里我聊聊python中的垃圾收集机制。想系统的了解这个问题我们需要涉及引用机制、动态类型和共享引用这些基本概念。

　　先谈谈python中的对象引用机制和动态类型。的确，python使用变量的时候都没有声明变量的类型，这一点和C语言不同。但是，变量还可以工作，因为在python中类型是在运行的过程中自动决定的，而不是通过代码声明的，这意味着没有必要事先声明变量。

　　在python中，我们要明确一个概念：变量名和对象是划分开的，变量名永远没有任何关联的类型信息，类型是和对象关联的，而不存在于变量名中。一个变量名当第一次被赋值的时候被创建，而当新的赋值表达式出现时，他会马上被当前新引用的对象所代替。这就是python所谓的动态类型机制。具体看一个例子：

　　1、创建了一个字符串对象’abcde’，然后创建了一个变量a，将变量a和字符串对象’abcde’相连接，

　　2、之后又创建了一个列表对象[1,2,3,4,5]，然后又将他和a相连接。

　　这种从变量到对象的连接，我们称之为引用，以内存中的指针形式实现。因此直白的说，在内部，变量事实上是到对象内存空间的一个指针，而且指向的对象可以随着程序赋值语句而不断变化。

　　总结一下：变量名没有类型，只有对象才有类型，变量只是引用了不同类型的对象而已。每一个对象都包含了两个头部信息，一个是类型标志符，标识这个对象的类型，以及一个引用的计数器，用来表示这个对象被多少个变量名所引用，如果此时没有变量引用他，那么就可以回收这个对象。

　　还是上面那个例子，每当一个变量名被赋予了一个新的对象，那么之前的那个对象占用的空间就会被回收，前提是如果他没有被其他变量名或者对象引用。这种自动回收对象空间的机制叫做垃圾收集机制。

　　即当a被赋值给列表对象[1,2,3,4,5]时，字符串对象的内存空间就被自动回收（如果他没有被别的变量引用）

　　具体的内部机制是这样的：python在每个对象中保存了一个计数器，计数器记录了当前指向该对象的引用的数目。一旦这个计数器被设置为0，这个对象的内存空间就会自动回收。当a被赋值给列表对象后，原来的字符串对象‘abcde’的引用计数器就会变为0，导致他的空间被回收。这就使得我们不必像C++那样需要专门编写释放内存空间的代码了

　　此时字符串对象’abcde’的引用计数是2，我们进一步往下看如果我们此时对变量a重新赋值呢？

　　结果是显而易见的，变量a变成了列表对象的引用，而变量b依然是字符串对象’abcde’的引用，并且字符串对象的引用计数为由2变为1.

　　如果此时再对b进行重新赋值，字符串对象’abcde’的引用计数就会变为0，然后这个对象就被垃圾回收了。

　　总结一下，给一个变量赋一个新的值，并不是替换原始的对象，而是让这个变量去引用完全不同的另一个对象，而原来的对象的引用计数会随之减1。

　　关于Python编程和数据分析更全面的内容，欢迎关注我在CSDN上的专栏《python数据分析编程基础》。

　　当然还有《机器学习中的数学-全集》系列专栏，欢迎大家阅读，配合食用，效果更佳~

作者：admin

分类垃圾-环境保护从分类垃圾做起! 站点 QQ交谈