《垃圾接纳的算法与实现》-算法-摘抄
本文是册本《垃圾接纳的算法与实现》的摘抄，不涉及算法源码及步骤讲解模块。预备
对象由头(header)和域(field)构成。
头：对象中保存对象本身信息的部分，主要含有以下信息：对象的巨细和种类。
域：对象利用者在对象中可访问的部分，数据范例有指针、非指针；指针是指向内存空间中某块区域的值；非指针指的是在编程中直接利用值本身。数值、字符以及真假值都是非指针。
通过GC，对象会被销毁或保留，起关键作用的就是指针。GC是根据对象的指针指向去征采其他对象的。GC对非指针不举行任何操纵。
一个GC算法的主要前提是能判别指针和非指针。
其次，要知道指针要指向对象的哪个部分。指针如果指向对象首地址以外的部分，GC就会变得非常复杂。幸亏，大多数语言中，指针都默认指向对象首地址。
mutator：改变GC对象间的引用关系，现实举行的操纵有：生成对象，更新指针。
堆：执行程序时用于动态存放对象的内存空间。
GC是管理堆中已分配对象的机制。在开始执行mutator前，GC要分配用于堆的内存空间。一旦开始执行mutator，程序就会按照mutator的要求在堆中存放对象。等到堆被对象占满后，GC就会启动，从而分配可用空间。如果不能分配足够的可用空间，一般情况下就要扩大堆。
把$heap_start定为指向堆首地址的指针，把$heap_end定为指向堆末尾下一个地址的指针。即，$heap_end等于$heap_start + HEAP_SIZE，HEAP_SIZE表示堆的巨细。
运动对象：将分配到内存空间中的对象中那些能通过mutator引用的对象；
非运动对象：把分配到堆中那些不能通过程序引用的对象，死掉的对象，即垃圾。
分配：allocation，指的是在内存空间中分配对象。当mutator需要新对象时，就会向分配器(allocator)申请一个巨细合适的空间。
分块：chunk，指为利用对象而事先准备出来的空间。内存里的各个区块都重复着分块->运动对象->垃圾（非运动对象）->分块->…如许的过程。
根：root，指向对象的指针的起点部分。根，可以通过mutator直接引用。几种根：调用栈(Call Stack)、寄存器以及全局变量空间。
GC在一般情况下无法严谨地判断寄存器和调用栈中的值是指针还是非指针。
评价尺度：
[*]吞吐量：throughput，在单位时间内的处理本领。即便是同一GC算法，其吞吐量也是受mutator的动作左右的。评价GC算法的吞吐量时，有须要把mutator的动作也考虑在内。
[*]最大暂停时间：因执行GC而暂停执行mutator的最长时间。高的吞吐量和短的最大暂停时间，两者不可兼得
[*]堆利用服从：左右堆利用服从的因素有两个：头的巨细、堆的用法。
在堆中堆放的信息越多，GC的服从也就越高，吞吐量也就随之得到改善。但毋庸置疑，头越小越好。因此为了执行GC，需要把在头中堆放的信息控制在最小限度。
可用的堆越大，GC运行越快；相反，越想有效地利用有限的堆，GC花费的时间就越长。
[*]访问局部性：具有引用关系的对象之间通常很大概存在一连访问的情况；因此，把具有引用关系的对象安排在堆中较近的位置，就能提高在缓存中读取到想利用的数据的概率，令mutator高速运行。PC上有4种存储器，分别是寄存器、缓存、内存、辅助存储器。
https://i-blog.csdnimg.cn/direct/ea352453c729486d8e54624803a9d15d.png
标志清除
Mark Sweep GC，两个阶段，标志阶段把全部运动对象都做上标志。清除阶段把那些没有标志的对象，即非运动对象举行接纳。
注意要制止重复举行标志处理。
标志所花费的时间是与运动对象的总数成正比的。
深度优先搜索比广度优先搜索更能压低内存利用量。因此在标志阶段经常用到深度优先搜索。
接纳对象就是把对象作为分块，连接到被称为空闲链表的单向链表。在之后举行分配时只要遍历这个空闲链表，就可以找到可用的分块。
在清除阶段，程序会遍历全部堆，举行垃圾接纳。所花费时间与堆巨细成正比。堆越大，清除阶段所花费的时间就会越长。
分配：搜索空闲链表并寻找巨细合适的分块。
分配战略：
[*]First-fit：在pickup_chunk()函数中，最初发现大于等于size的分块时就会立即返回该分块；
[*]Best-fit：遍历空闲链表，返回大于等于size的最小分块；
[*]Worst-fit：找出空闲链表中最大的分块，将其分割成mutator申请的巨细和分割后剩余的巨细，目的是将分割后剩余的分块最大化。很轻易生成大量小的分块，不推荐。
分配所需的时间短，可以选择利用First-fit更为明智。
归并：coalescing，在清除阶段举行，把全部的一连的小分块连在一起形成一个大分块。不一连的不能归并？
优点：
[*]实现简朴；
[*]兼容守旧式GC算法：不会移动对象，搭配守旧式GC算法（对象不能被移动）。
缺点：
[*]碎片化：
[*]分配速率
[*]与写时复制技能不兼容：
多个空闲链表
BiBOP法
BiBOP，Big Bag Of Pages，将巨细相近的对象整理成固定巨细的块举行管理的做法。试图解决GC标志-清除算法的碎片化问题：把堆分割成固定巨细的块，让每个块只能设置同样巨细的对象。
位图标志
对此我们有个方法，那就是只收集各个对象的标志位并表格化，不跟对象一起管理。在标志的时候，不在对象的头里置位，而是在这个表格中的特定场所置位。像如许聚集了用于标志的位的表格称为“位图表格”（bitmap table），利用这个表格举行标志的举动称为“位图标志”。
散列表和树形布局
耽误清除法
清除操纵所花费的时间与堆巨细成正比。即待处理的堆越大，GC标志-清除算法所花费的时间就越长，效果就会妨碍到mutator的处理。
Lazy Sweep，缩减因清除操纵而导致的mutator最大暂停时间的方法。
耽误清除的效果是不均衡的。程序在清除垃圾较多的部分时能立刻获得分块，所以能淘汰mutator的暂停时间。然而一旦程序开始清除运动对象周围，就怎么也无法获得分块，会增加mutator的暂停时间。
引用计数法
Reference Counting，计数器是无符号的整数，用于计数器的位数根据算法和实现而有所不同。引用计数法中的对象如图所示：https://i-blog.csdnimg.cn/direct/6492173a1067457aba10bc2daecc83f7.png
优点：
[*]可马上接纳垃圾：当被引用数的值为0时，对象立刻就会把自己作为空闲空间连接到空闲链表；
[*]最大暂停时间短：只有当通过mutator更新指针时程序才会执行垃圾接纳。即，每次通过执行mutator生成垃圾时这部分垃圾都会被接纳，因而大幅度地淘汰mutator的最大暂停时间；
[*]没有须要沿指针查找：在各个计算节点内GC时利用GC标志-清除算法，在考虑到节点间的引用关系时则接纳引用计数法。
缺点：
[*]计数器值的增减处理繁重：对有根指针而言，根可以通过mutator直接被引用，指针更新时，计数器的值都得随之更新；
[*]计数器需要占用很多位：用于引用计数的计数器最大必须能数完堆中全部对象的引用数，极端情况下，全部对象同时引用一个对象，大大降低内存空间利用服从；
[*]实现烦琐复杂：实现不当，会产生Bug；
[*]循环引用无法接纳：两个对象相互引用，所以各对象的计数器的值都是1。但是这些对象组并没有被其他任何对象引用。
耽误引用计数法
计数器值增减处理繁重的缘故原由之一是从根的引用变革频繁。
Deferred Reference Counting，让从根引用的指针的变革不反映在计数器上。
ZCT，Zero Count Table，会事先记录下计数器值在dec_ref_cnt()函数的作用下变为0的对象。
https://i-blog.csdnimg.cn/direct/3532fcdcf4d744d1acd769cb2ec4ec79.png
优点：耽误根引用的计数，将垃圾批量接纳，而不是有一个就接纳一个。
缺点：
[*]不能马上接纳垃圾；
[*]scan_zct()函数导致最大暂停时间延伸。执行scan_zct()函数所花费的时间与$zct巨细成正比。$zct越大，要搜索的对象就越多，妨碍mutator运作的时间也就越长。要想缩减因scan_zct()函数而导致的暂停时间，就要缩小$zct。但是如许一来调用scan_zct()函数的频率就得增加，降低吞吐量。
Sticky引用计数法
1位引用计数法
1bit Reference Counting，标签引用计数法，Sticky引用计数法的一个极端。
一个观察结论：险些没有对象是被共有的，全部对象都能被立刻接纳。
计数器只有1位，0表示被引用数为1，状态用UNIQUE表示，1表示被引用数≥2，状态用MULTIPLE表示。
https://i-blog.csdnimg.cn/direct/37260e061e67414cb265bf956ca8c27e.png
具体实现，由于指针通常默认为4字节对齐，所以没法利用低2位。
https://i-blog.csdnimg.cn/direct/27af2b61e04845599e978a3e988186b3.png
优点：
[*]能利用高速缓存：不需要在更新计数器（标签）时读取要引用的对象；
[*]节省内存消耗量。
缺点：
部分标志-清除算法
Partial Mark & Sweep，只对大概有循环引用的对象群利用GC标志-清除算法，对其他对象举行内存管理时利用引用计数法。执行一般的GC标志-清除算法的目的是查找运动对象，而执行部分标志-清除算法的目的则是查找非运动对象。
对象会被涂成4种不同的颜色来举行管理：
[*]BLACK：黑，绝对不是垃圾的对象，对象产生时的初始颜色；
[*]WHITE：白，绝对是垃圾的对象；
[*]GRAY：灰，搜索完毕的对象；
[*]HATCH：阴影，大概是循环垃圾的对象。
在对象头中分配2位空间，用00～11对应4个颜色。
部分标志-清除算法的特性就是要涂色的对象和要举行计数器减量的对象不是同一对象，据此就可以很顺利地接纳循环垃圾。
局限性：从队列搜索对象所付出的成本太大，被队列记录的对象是候选垃圾，需要查找3次对象，即分别执行1次mark_gray()、scan_gray()及collect_white()方法，增加最大暂停时间。
复制
Copying GC，把某个空间里的运动对象复制到其他空间，把原空间里的全部对象都接纳掉。将复制运动对象的原空间称为From空间，将粘贴运动对象的新空间称为To空间。From空间和To空间巨细必须一致。
如果分块的巨细不敷，即分块小于所申请的巨细时，比起启动GC，起首应分配足够大的分块。否则一旦分块巨细不敷，分配就会失败。
优点：
[*]吞吐量高：GC标志-清除算法消耗的吞吐量是搜索运动对象（标志阶段）所花费的时间和搜索整体堆（清除阶段）所花费的时间之和。而GC复制算法只搜索并复制运动对象；
[*]可实现高速分配：不利用空闲链表；比起GC标志-清除算法和引用计数法等利用空闲链表的分配，GC复制算法明显快得多；
[*]没有碎片化：复制的操纵可看做是压缩，会整理碎片；
[*]缓存兼容：有引用关系的对象会被安排在堆里离彼此较近的位置，mutator执行速率极快。
缺点：
[*]堆利用服从低下：把堆二等分，利用率只有一半；
[*]不兼容守旧式GC：必须移动对象重写指针，因此和守旧式GC算法不相容；
[*]递归调用函数：复制某个对象时要递归复制它的子对象，服从不如迭代好；每次递归调用时都会消耗栈，存在栈溢出的大概。
这里讲的是Fenichel和Yochelson的复制GC，为了方便，简称为FY复制GC。
Cheney复制GC
Cheney复制GC中没有用到COPIED标签，利用forwarding指针来判断对象是否复制完毕。
GC没复制的对象时，其指针指向From空间某处的对象。如果某个对象有着指向To空间某处的指针，则阐明这个对象已复制完毕。即，obj.field1指向To空间时，对象obj已复制完毕。
对比：
[*]FY复制是递归地复制，Cheney复制是迭代地复制；
[*]FY复制GC接纳的是深度优先搜索，Cheney复制GC则是广度优先搜索；
优点：
[*]迭代算法，可克制调用函数的额外负担和栈的消耗；
[*]拿堆用作队列，省去用于搜索的内存空间。
缺点：在搜索对象上利用广度优先搜索，不兼容缓存，即不能利用缓存。
近似深度优先搜索方法
4个重要的变量：
[*]$page：将堆分割成一个个页面的数组。$page指向第i个页面的开头；
[*]$local_scan：将每个页面中搜索用的指针作为元素的数组，$local_scan指向第i个页面中下一个应该搜索的位置；
[*]$major_scan：指向搜索尚未完成的页面开头的指针；
[*]$free：指向分块开头的指针。
在搜索一开始把有引用关系的对象安排在同一个页面中。不管在哪一个页面里，对象间都存在着引用关系。由于接纳的不是完整的广度优先搜索，而是在每个页面上分别举行广度优先搜索。
疑问：在每个页面上分别举行广度优先搜索，最后再整体利用深度优先搜索吗？
多空间复制算法
GC复制算法最大的缺点是只能利用半个堆。多空间复制算法，把堆N等分，对此中2块空间执行GC复制算法，对剩下的(N-2)块空间执行GC标志-清除算法，2种算法的组合。
优点：更有效利用堆空间。
缺点：即标志-清除算法的缺点，分配耗费时间、分块碎片化等。
标志压缩
Mark Compact GC，标志-清除+复制。
压缩阶段通过数次搜索堆来重新装填运动对象，跟GC复制不同，不消牺牲半个堆。
优点：有效利用堆，没有碎片化问题。
缺点：压缩花费计算成本，Lisp2算法的压缩阶段，必须对整个堆举行3次搜索。
Two-Finger算法
有一个很大的制约条件：必须将全部对象整理成巨细一致。和Lisp2算法不同，没有须要为forwarding指针准备空间，只需要在原空间对象的域中设定forwarding指针即可。
2个步骤：移动对象、更新指针。
优点：Lisp2算法要事先确保每个对象都留有1个字用于forwarding指针。而Two-Finger算法能把forwarding指针设置在移动前的对象的域里，所以不需要额外的内存空间以用于forwarding指针，内存利用服从更高。吞吐量更高。
缺点：全部对象的巨细必须一致；无法利用缓存。
利用BiBOP法，只要把同一巨细的对象安排在同一个分块里，就能对每个分块应用Two-Finger算法。
将具有引用关系的对象安排在堆中较近的位置，就能够通过缓存来提高访问速率。
表格算法
用表格来压缩的方法，执行2次压缩操纵。
2个步骤：移动对象（群）以及构筑间隙表格、更新指针。
间隙表格：Break Table，按照一个个运动对象群记录下压缩所需信息的表格。
优点：
[*]没须要为压缩准备出多余的空间：利用分块，保留更换指针所必需的信息；
[*]压缩前后保留对象顺序，可利用缓存。
缺点：
[*]维持间隙表格需付出很高的代价：每次移动运动对象群都要举行表格的移动和更新；
[*]在更新指针时也不能忽略搜索表格所带来的消耗。在更新指针前，如果先将表格排序，则表格的搜索就能高速化。不外排序表格也需要相应的消耗，并不能从根本上解决问题。
ImmixGC算法
3个步骤：选定备用的From块、搜索阶段、清除阶段。
根据对象巨细分成3类：
[*]小型对象：线以下巨细；
[*]中型对象：比线大，不到8K字节；
[*]大型对象：大于等于8K字节，Immix GC不予管理，Jikes的MMTk来处理。
优点：
缺点：
守旧与精确GC
守旧GC
Conservative GC，不能识别指针和非指针的GC。
不明确的根，Ambiguous Roots
精确GC
Exact GC，能精确识别指针和非指针的GC。创建精确的根的方法有很多，共通点就是需要语言处理程序的增援。
打标签
不把寄存器和栈等当作根
间接引用
MostlyCopyingGC
前提条件：
[*]根是不明确的根
[*]没有不明确的数据布局
[*]对象巨细随意
[*]CPU是32位
黑名单
守旧式GC的缺点之一：指针的错误识别，即本来应该被看作垃圾的对象却被保留下来。
分代垃圾接纳
Generational GC，对象引入年龄概念。
Minor GC，对新生代对象的GC。新生代GC后存活一定次数的新生代对象晋升(promotion)为老年代对象。Major GC，对老年代对象的GC。
Ungar分代垃圾接纳
堆布局图，用$new_start、$survivor1_start、$survivor2_start、$old_start4个变量指向3类空间的开头，
https://i-blog.csdnimg.cn/direct/b10c79dabbb34678a5a20a8e0cc5483e.png
https://i-blog.csdnimg.cn/direct/553fd0f537524579b32b1d06703d88e5.png
对象的头部中除包罗对象的种类和巨细外，还有以下这3条信息：
[*]age：对象年龄，对象从新生代GC中存活下来的次数，超过可设置的一定次数，晋升为老年代；
[*]forwarded：已经复制完毕的标志，用于防止重复复制类似对象；
[*]remembered：已经向记录集记录完毕的标志，用来防止向记录集中重复记录的标志，老年代利用，前两个是新生代利用。
优点：提高吞吐量。
缺点：
记录各代之间的引用的方法
Ungar的分代垃圾接纳利用记录集来记录各代间的引用，为了直接记录发出引用的对象，对应每个发出引用的对象各花费1个字节。如果各代之间的引用很多，还会出现记录集溢出。
卡片标志
卡片标志：Card Marking，起首把老年代空间按照相等的巨细分割开来，分割出来 的一个个空间就称为卡片，还要为每个卡片准备一个与其对应的标志位，并将这个位作为标志表格(Mark Table)举行管理。GC时会寻找位图表格。当找到设置标志位的卡片时，就会从卡片开头开始寻找指向新生代空间的引用。
当由于改写指针而产生从老年代对象到新生代对象的引用时，要事先对被改写的域所属的卡片设置标志位，可通过写入屏蔽来实现。纵然对象跨两张卡片，也不会有什么问题。
优点：
[*]能有效利用内存空间。每个128字节（1024位）的新生代空间都只需要一个位来用作标志，所以整个位表(Bit Table)只需要老年代空间的1/1024的空间。
[*]无论从老年代空间指向新生代空间的引用怎么增加，都不会发生像记录集那样溢出的情况。
缺点：如果在标志表格里设置很多位，在搜索卡片上大概花费大量时间。因此只有在局部存在从老年代空间指向新生代空间的引用时，卡片标志才能发挥作用。
页面标志
页面标志：Page Marking，是考虑到多数OS以页面为单位来管理内存空间。
一旦mutator对堆内的某一个页面举行写入操纵，OS就会设置跟这个页面对应的位，把这个位叫作页面重写标志位(Dirty Bit)。卡片标志中是搜索标志表格，页面标志则是搜索这个页面重写标志位。
为不能利用页面重写标志位的OS准备一种方法，即利用内存掩护功能：在mutator执行过程中掩护老年代空间不被写入，当mutator写入老年代空间时，通过非常处理来检测出这项操纵。在非常处理函数的内部，和卡片标志一样，事先设置与发生写入的页面对应的位。
页面标志只适用于能利用页面重写标志位或能利用内存掩护功能的环境。别的，由于检测出全部对页面举行的写入操纵，所以除了在生成从老年代空间指向新生代空间的引用时，在其他情况下也需要搜索页面。
多代垃圾接纳
分代GC有两个年代。Multi Generational GC，多代垃圾接纳，有3个年代以上的GC。比如4代GC示意图：https://i-blog.csdnimg.cn/direct/8d6f349281f147c7ad47cdb3daa1825d.png
除最老那一代外，每代都有一个记录集。X代的记录集只记录来自比X老的其他代的引用。分代数目越多，对象变成垃圾的时机也就越大，所以这个方法确实能淘汰活到最老代的对象。
当然，不能过分增加分代数目。分代数目越多，每代能利用的空间也就相应变小，各代之间的引用变多，各代中垃圾接纳花费的时间也就越来越长。
列车垃圾接纳
Train GC，为了在分代垃圾接纳中利用老年代GC而接纳的算法，可控制老年代GC中暂停时间的增长。
增量垃圾接纳
Incremental GC，一种通过渐渐推进垃圾接纳来控制mutator最大暂停时间的方法。
Steele算法
利用的写入屏蔽要比Dijkstra的写入屏蔽条件更严酷，淘汰GC中错误标志的对象。
汤浅算法
比较各个写入屏蔽
RC Immix算法
Reference Counting Immix，将引用计数法吞吐量低这一缺点改善到实用级别。
归并型引用计数法
在引用计数法中，每当对象间的引用关系发生变革，都要增减该对象的计数器，以包管其数值一直是精确的。这是通过写入屏蔽实现的。如果计数器频繁发生增减，则写入屏蔽的执行频率就会增加，处理就会变得繁重。
一个事实：如果对同一个对象分别举行一次增量和减量操纵，两者会相互抵消，终极计数器的值并没有变革。
Coalesced Reference Counting，考虑选定一个时间区间，在该期间内不举行计数器的增减。指针改动时的信息（对象和其全部子对象）会被注册到更改缓冲区(Modified Buffer)，这项操纵是通过写入屏蔽来执行的。等到更改缓冲区满了，就要运行GC。如果在对象间的引用关系发生变革时，计数器没有增减的话，就会导致有一段时间计数器值是错误的。
优点：增加吞吐量。它不是逐次举行计数器的增减处理，而是在某种程度上一并执行，所以能无视增量和减量相抵消的部分。尤其在一个对象频繁更新指针的情况下，归并型引用计数法能起到很大的作用。
缺点：增加mutator的暂停时间，在查找更改缓冲区的过程中需要让mutator暂停。减小更改缓冲区的巨细，能相应缩短暂停时间，不外吞吐量就会降低。需要加以衡量。
归并型引用计数法+Immix
优缺点
优点：通过RC Immix，吞吐量低得到大幅度的改善，缘故原由有2点：
[*]导入归并型引用计数法：没有通过写入屏蔽来执行计数器的增减操纵，所以纵然对象间的引用关系频繁发生变革，吞吐量也不会降落太多；
[*]撤除空闲链表：通过以线为单位来管理分块，在线内移动指针就可举行分配。还省去把分块重新连接到空闲链表的处理。
缺点：
[*]会增加暂停时间：可以通过调整更改缓冲区的巨细来缩短暂停时间；
[*]只要线内还有一个非垃圾对象，就无法将其接纳。在线的计数器是1，线内还有一个运动对象的情况下，会白白消耗大部分线。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]