初级分代GC

　　GC的分类

　　通常情况下GC分为两种，fgsj1122分别是：扫描GC(Tracing GC)和引用计数GC(Reference counting GC)。其中扫描GC是比较常用的GC实现方法，其原理是：把正在使用的对象找出来，然后把未被使用的对象释放。而引用计数GC则是对每个对象都添加一个计数器，引用增加一个计数器就加一，引用减少一个计数器就减一，当计数器减至零时，把对象回收释放。引用计数GC跟C++中的shared_ptr类似，自然也会存在循环引用问题。

　　扫描GC(Tracing GC)是广泛使用的GC方法，最简单的实现方式是mark-sweep，即扫描所有存活的对象并mark，然后遍历整个GC对象列表，把所有标记过的对象清除标记，把未标记过的对象释放。如果GC使用的是mark-sweep方法，程序运行一段时间后触发了GC，每次GC的时候会把当前程序中的所有对象都扫描一次，然后释放未使用的对象。这对于分配GC对象少的程序来说没有什么问题，当程序中存在大量分配GC对象时，每次启动GC扫描所有对象的代价是很高的，又因为GC的过程通常是stop-the-world，所以高代价的GC会导致整个程序卡顿一段时间。对于这个问题，解决方法有增量 GC(Incremental GC)和分代GC(Generational GC)。

　　增量GC(Incremental GC)会把整个GC过程分成很多步(phase)，每步的执行可以存在一定间隔运行程序本身，这就尽量把stop-the-world的时间变短，使得程序不会因为GC而导致延迟太大。Lua默认采用的是这种实现方法，Lua 5.2中也引入了分代GC作为备选GC方法。

　　分代GC(Generational GC)把对象分成几代(Generation)，通常把GC分为两种：Minor GC和Major GC。刚刚分配出来的对象属于最年轻的一代，在一次GC过后把年轻代中存活的对象上升到年老的一代中。把只扫描年轻一代的对象以减少扫描对象数量的GC过程称为Minor GC，只有在特定情况下才会启动完整的Major GC。分代GC是基于在大多数程序中新创建的对象同时也是最快变成无效的对象的经验设计的，对年轻代对象GC时，可以释放大多数无效对象，存活下来的对象一般存活时间也会更长，因此把它们上升到下一代中以减少最这些对象的扫描。

　　对于GC内存的管理，有移动和非移动之分。移动的就是把一次GC过后存活的对象compact到一起，使GC管理的内存保持连续，这里增加了一个移动对象的开销，不过它也同样带来不少好处：分配释放对象快和更快的序列遍历(在CPU cache中及在同一个Virtual memory page中)。正因为它会把对象compact到一起，对象的地址就会发生变化，这也就导致一个明显的缺点，不能使用指针引用GC对象。

　　其它高级GC方法，比如.NET的background GC，几乎不需要stop-the-world就可以在GC线程中完成GC，这种高科技的GC对于我这种初级人士基本属于不可想象。

　　初级分代GC设计

　　了解了基本的GC方法之后，我为luna第二版实现了一个初级的分代GC，把对象分成三代：GCGen0,GCGen1,GCGen2:

　　GCGen0是最年轻的一代，默认所有对象都是分配在这代中。

　　GCGen1是年老的一代，在一次GC过后GCGen0代存活的对象会移动到这一代中。

　　GCGen2是最老的一代，一般情况下用于存放编译时分配的会长期存在的对象，比如函数及字符串常量。

　　由于我在很多地方直接引用了GC对象的指针，为了简单起见，我没有在GC之后移动对象，而是对每个对象单独分配释放内存。每个对象都有Generation标记和GC标记以及一个用于指向跟自己属于同代的GC对象的指针。

　　Minor GC对GCGen0代对象mark-sweep，并把存活的对象移动到GCGen1代中。既然需要mark，自然需要对所有GCGen0代存活的对象标记，这通过对root对象的遍历完成，root是指所有对象的引用入口，比如程序的栈和全局表。对于Minor GC的root对象遍历最简单的方法是跟Major GC的root遍历完全一致，不过这样的遍历对于本来就是为了减少遍历对象的Minor GC来说似乎不合，所以通常只对某一小块root遍历，比如只对栈上的对象遍历，然后再把存活的对象保留不存活的对象释放。

　　Minor GC的root遍历存在一个问题：假设只把栈上的对象作为root遍历，会存在一些从GCGen0代分配出来的对象没有被栈上的对象引用，而被全局表中的某个对象引用，或者其它某个非GCGen0对象引用了，这样对GCGen0代sweep的时候可能会把这个存活的对象当做无效对象而释放掉，这种操作自然也就会导致整个程序crash。于是为了控制root遍历的范围，又要解决这个问题，对非GCGen0对象引用GCGen0对象的时候，需要把这个非 GCGen0的对象也加入到root遍历列表中去。这时引入了barrier，对于非GCGen0对象引用GCGen0对象时，把这个非GCGen0的对象放到barrier列表中。

　　Major GC是一个完整的GC，它遍历所有的root并mark，并把所有的无效的对象都sweep释放。

　　GC启动的时机

　　GC什么时候启动是一个需要仔细考虑的问题，由于我实现的GC并没有自己管理内存(Lua也没有自己管理内存，所有内存分配都通过 realloc)，所以我把GCGen0代和GCGen1代的对象数量作为启动时机的衡量指标，当GCGen0和GCGen1的对象数量大于它们的阈值时，分别启动Minor GC和Major GC。我觉得对象的数量比起内存占用大小(各种复杂的GC对象导致内存占用很难精确的统计，Lua的内存统计也不够精确)更能反映GC时间的长短，如果两者结合也许会更好。

　　通过判断GC对象个数超过阈值时启动GC，同时需要在GC之后自动调整阈值大小。比如某些程序很快的达到GCGen0的阈值并在Minor GC之后有超过一半的对象还是存活的，这时需要把阈值调大，以减少GC启动的次数，这个阈值也不能无限扩大，这不仅会导致一段时间内内存占用一直上升，也会导致一旦触发GC所需扫描的对象数量太多，GC耗时太长，程序运行的延时增加。