[ZZ]随机垃圾收集

http://linux.chinaunix.net/bbs/archiver/tid-893113.html
随机垃圾收集

内存管理作为资源管理的一种形式一直以来就是软件开发中的难题，大部分编程错误都出现在和内存操作有关的代码中，几十年来内核程序员一直在寻求更好的内存管理机制。事实证明，有效的资源管理技术是绝大多数软件开发从业人员所难以掌握的。因此，早在20世纪60年代垃圾收集就已经随着LISP的发明而被提出并广泛关注，以试图提供一种自动化的内存管理机制。虽然历经了长期发展，在解释型语言中成功的广泛应用，并且不断以程序库的方式向C/C++这种系统级开发语言中渗透，但是作为一种自动化资源管理机制还远未达到广泛适用，尤其是系统及软件的要求。因此在前人的研究基础上，以节点复制为基本框架，结合系统开发中的内存管理的实际，采用随机收集算法，提出一种适用度广泛的新型垃圾收集算法，并可应用于编译器和操作系统的内存管理、闪存文件系统等方面开发之中。
David在Lcc开发中大量使用的一种基于对象生存周期的内存管理方式Arena。Arena是先分配一个内存块，然后再从该内存块中分配内存数据，在整块内的节点都死亡后一次释放整个内存块，从而大大简化了代码，消除了存储漏洞，并避免了内存泄露和重复释放的问题。而其缺点就是可能需要更多的内存空间，并且可能出现悬挂引用，更重要的是这种生存周期确定并一致特例在现实中很少存在。节点复制是一种高效，接口、模型最为简洁的收集方法，唯一的诟病就是庞大的内存需求。结合节点复制的优点，改进这个内存管理模型，仍然是先分配一个内存块，然后再从该内存块中分配内存数据。然而由于对象生存周期的不确定性，在一段时间后不是释放整个内存块，而是扫描整个块看其中还有没有存活的数据，将存活数据复制到一个新块中去再释放该块。
由于是将内存分块分配和收集，而不是分成两个半区，只是一个块一个块的收集，减小了收集的范围，缩短了因收集而产生的中断。如果程序总共用N个块的话用于垃圾收集的内存为1/N，而不是1/2，所以又降低了节点复制方法的内存占用率。因为节点复制算法是搬迁式的，所以同时还消除了内存碎片，从而又降低了分配对象的代价。
为进一步提高性能，就要考虑收集的顺序。大多数商用系统会采用类似“中断”的方式进行收集，然而和外设不同的是，内存没有计算能力，所有关于内存的计算都是靠CPU来完成的，在这里，“中断”方式仍然是线性的if-else形式。因此，采用“中断”收集方式并不比“轮询”收集方式要好。
简单的自加1或自减1的偏序操作的代价是非常低的，那么是顺序收集还是逆序收集呢？一般不会考虑逆序收集，因为很多操作系统都会尽可能的从低地址连续分配内存，逆序收集无疑会扫描很多空白区域，所以顺序收集是个不错的方法。然而访问内存总不像访问寄存器那样直接，况且不同的机器的内存的容量和数量又是不尽相同的，不同的内存的硬件访问方式也是不同的，再加上与cache的关系，用随机访问来掩盖差异是在合适不过的了。
采用随机的收集顺序，一个random()并不会带来多高的代价但却会有很好的效果。收集正在使用的块是一件很麻烦的事情，会造成很大的性能损失，如果总共有N块内存的话，当前使用率为n/N（通常n不会很大），收集率为1/N，收集到当前使用块的概率为n/N^2，机会还是很小的。而每块被收集到的概率是相等的，又不会出现某些块总被收集到某些块却总也收集不到的现象。
充分利用内存会得到很好的性能，就不一定会固守尽可能从低地址连续分配内存的主观教条，从而整个内存空间的使用状况是离散的，这样就会更加适合于使用随机收集的方式。
闪存和内存存在一定程度上的相似性，而现在闪存文件系统也需要某种有效的垃圾收集机制的支持，因此我将此收集算法改造出一个适用于闪存文件系统的变体。因为现在广泛使用的Nand_Flash需要按块读写，所以该收集算法还可用于基于Nand_Flash的闪存文件系统。Nand_Flash有擦写次数寿命的限制，需要写均衡技术的支持，对此我们只要把新块分配到尚未使用的新块中，即可达到写均衡的效果。由于Nand_Flash会随机的产生坏块，使用该收集算法可以不把物理坏块映射到任何逻辑块上，使得文件系统在逻辑层上是连续可用的。
为进一步提高收集效率还可以采取分代的策略，并把那些生存周期确定不变的数据（如C语言中的全局变量）放在一个块中并且不对该块进行扫描，让该块随着程序的结束而被释放，对于那些大型数据，进行标记远比复制的代价要小得多。
为了避免直接使用ANSI／ISO C的malloc()和free()函数而造成的内存碎片和操作时间不确定等问题，著名实时内核MicroC/OS-II把连续大块内存分区，每个分区又分成一些大小相同的块来进行管理。如果将该收集算法加以改进并应用在操作系统的内存管理和虚拟内存管理模块中，按区、块收集内存，简化了内存管理和虚拟内存管理的模型，同时也解决了内存碎片的问题，给整个系统和应用程序提供更有效的存储管理机制，从而带来更好的性能。在操作系统层面上提供垃圾收集机制不仅性能更好，又使得垃圾收集机制在整个系统上是统一的，而不必分别在不同的编译器和应用程序上实现垃圾收集机制，以避免一个系统中存在多个垃圾收集机制而造成的资源浪费和潜在的冲突。