（转）火车算法

转至：http://www.cnblogs.com/wenfeng762/

火车算法详细说明了按代收集的垃圾收集器的成熟对象空间的组织。火车算法的目的是为了在成熟对象空间提供限定时间的渐进收集。

概述
    在传统编程语言中, 对于那些无用对象, 程序员需要在原本指向这个对象引用都消失之前之前, 回收它所占据的内存空间(这里的消失指的是引用不再指向这个对象)。这导致了两个常见的程序错误: 首先, 如果对一个已经被回收的对象再次进行操作将会导致内存异常; 其次, 如果一个对象在被回收前已经没有引用指向它时, 那么, 直到程序终止前, 它将一直占据内存空间. (这样的漏洞对于一个生命周期不长的程序来说可能影响不大), 但是对于一个运行周期较长的应用程序而言, 随着程序地运行, 这样的漏洞将会导致它消耗越来越多的内存空间. 显而易见, 最终将会导致程序因为内存都被分配完而被迫终止.
     “垃圾” (garbage)通常指的是那些在程序中不会再被用到(不可及)的对象——因此可以安全的释放他们占据的内存空间. 为了帮助程序员从"回收无用对象所占内存空间"的工作中解脱出来,能够让他们专注于程序功能的实现,  已经研究出了一些能够从内存空间中自动监测出无用对象并释放他们所占据的内存空间的算法.——这些算法就是垃圾收集机制.
     在一些诸如Java、C#的现代高级编程语言中, 已经广泛使用了自动化内存管理机制. 在这些机制的一些实现方法中, 可以看到, 它们在进行无用对象回收过程中, 最大不足之处是它们是非增量式的(垃圾回收)算法. 这些算法需要在垃圾回收过程中停掉主程序的运行. (这样一来,)当对内存的需求增大的过程中, 程序被停掉的时间也将变得越来越长.这就是为什么增量式的垃圾回收变得越来越重要. 一些实时应用常常需要在几毫秒时间内作出响应, 一些与用户交互的应用也仅仅允许极短时间的停顿.(这个时间通常是一秒的小部分). 那么垃圾回收将不可能使用在一些在线角色扮演的游戏中, 因为没有玩家能够接受每一次垃圾回收带来的延时.
另外, 将一次垃圾回收分成一个个微小的步骤还有其它好处. 很多时候, 对象可能会分布在一些不同的系统中, 如果采用非增量式的垃圾回收, 那么, 这将导致在进行垃圾回收的时候, 所有系统都将停止运行.  在这种情况下, 火车算法往往可以解决问题.
基本思想
接下来将会描述一些常见的垃圾回收算法背后的主要思想, 以及火车算法.
         垃圾回收基本上包含两个主要任务:
第一: 检测.
         无论如何, 垃圾收集器需要区分出”活”的对象和”垃圾”. 算法通常使用另一种方法而不是去搜寻所有无用对象: “活”的对象都会被标记并被保留下来. 来看对象空间外部指向一个对象的引用称为”根引用”. 所有被这样的引用指向的对象会被标记为”活”对象. 当然, 所有被这些”活”对象引用的对象同样被标记为”活”的. 当所有被引用的对象都已经被标记,那么算法结束. 此时可以保证的一点是所有的无用对象都没有标记并且无法被程序访问了.

第二:释放.
         有两个可行的方法来删除”垃圾”.
-          通过复制这些活着的对象到一个安全的地方来保留他们, 并将被无用对象占据的内存块释放.
-          释放所有没有被标记为活着的对象空间.

在上图中, 假设监测到了所有活着的对象. 首先是对象G, 根引用直接指向这两个对象, 当然要标记. 同样, 由于通过对象A能够(让程序操作), 所以对象B也被保留下来了. 值得一提的是, 图中对象C, D和E的引用构成了一个圈(自循环)的话, 那么这些对象也应该被看作是无用对象(垃圾).
         通过拷贝那些存在引用的对象来保留它们的做法, 一眼看下去, 似乎是相当耗费性能的. 但是这个技术也有它的优点: 每次垃圾回收后, 内存是连续的, 因此, 各个对象都是紧密排列的, 于是程序能够执行得更快.

         图2显示了一部分空闲的内存空间, 保留下了所有被引用的对象. 所谓”from space”指的是在垃圾回收以前, 当前程序正在使用的内存空间. 而”to space” 则是表示了垃圾回收后, 保留下来的内存空间.
         当垃圾回收正在进行的过程中, 被中断很长一段时间是不允许的, 其中(垃圾对象的)监测是一个很大的问题. 几乎很难找到这样一个能将这个过程分成一个个小步骤的算法­——一般来说这就是所谓的增量式垃圾回收——火车算法提供了这样一个解决方案.

A.      将内存空间分成若干块
火车算法的主要思想是将内存空间(这里的内存空间仅仅指JVM实例占据OS的内存空间)分割成若干个小块, 并且单独地在每一个内存块上进行标记和拷贝操作. 主要的麻烦仅仅是停掉程序对当前内存块的操作, 并且中断的时间会根据内存块的大小, 较原来停掉所有程序内存, 将会大大减小.
标记和拷贝的操作只在一个内存块上进行的话, 根引用将不再只是从内存块外指向里面内存对象的引用. 因此我们必须跟踪对象的所有引用, 当然要排除排除那些来自同一个内存块中的对象.所有这些引用的集合称为内存块的”记忆集合”(remembered set). 简单地假设一个内存块恰好可以存储三个对象. 图3展示了对象在若干个内存块中的一种可能的分布. 这种分布是针对图1的场景而言.

当垃圾回收器在第一个内存块中执行垃圾回收时, 利用”记忆集合”, 找出了只有对象G被来自内存块外部的引用所引用. 因此这个对象G将会保留下来, 并被拷贝到最后一个内存块中. 现在, 第一个内存块已经整个可以被清空了——对象F可以毫无疑问地被删掉了. 第一遍垃圾回收的结果可以如图4所示.

在接下去的一次回收中, 相同的步骤将会在下一个内存块中被执行. 对象A将会被保留下来, 并且由于对象B能够通过对象A被程序访问——他同样被保留下来了. 此时, 由于最后一个内存块还有空闲的空间, 所以没有必要再分配新的内存块了. 要注意的是, “记忆集合”是如何更新来反映回收的的内存块中对象的分布的.

一个内存块的”记忆集合”是空的, 因此整个内存块就可以被自由并且安全地标记了.

这似乎是一种持续向前的增量式的垃圾回收算法了.但也存在一些问题.
B.      写隔离(Write Barrier)(这里的隔离是只能有一个线程来访问)
首先, 我们将如何高效地实现”记忆集合”. 如果没有硬件或至少是编译器的支持, 这是不可能的做到. 有些垃圾回收算法在操作过程中需要一种叫做”读隔离”地策略, 火车算法需要使用”写隔离”策略. 在使用”读隔离”策略的时候, 每次有指针(pointer)来访问指定代码的时候, “读隔离”策略都要被执行, 而”写隔离”策略只在指针执行赋值操作的时候才被执行. 通常情况下, 程序读访问的频率远比写访问高.
无论什么时候进行指针赋值操作, 算法都要进行两步操作:
1. 清除旧的的引用(这里的旧的引用指的是那些已经没有用处的引用): 如果旧的引用被注册在一个”记忆集合”中, 那么应该将它从中删除.
2. 添加新的引用: 如何有新的引用指向对象空间的某个一个内存块中的对象, 那么需要将这个引用添加到恰当的”记忆集合”中.
下面这个Java伪代码显示了所有4种可能的场景——进行了指针赋值. 假设a, b, c三个对象被分配在了不同的内存块中了.
class Pointer{                                                                
     Pointer p; 
}                                                                                                                                                                           
Pointer a = new   Pointer( ); 
Pointer b = new   Pointer( );                                               
Pointer c = new   Pointer( ); 
// Case    1: Nothing has to be done no pointer to objects in the object space is affected. 
a.p =null; 
// Case    2: Add b.p to the remembered set of the block of a 
b.p = a; 
// Case    3: Remove b.p from the remembered set of the block of a and add it to the
//remembered set of the block c 
b.p = c; 
// Case    4: Remove b.p from the remembered set of the block of c                                                               
b.p = null; 
       有一个可能比较优化的办法就是如果内存块都被标上数字, 那么算法每次总是先对标记最小的内存块早进行处理. 那么仅仅从那些标记较高的内存块的指向标记较低的内存块的引用要被记录到”记忆集合”中.
在拷贝对象的时候, “记忆集合”也被用来更新引用. 然而, 这将会非常耗费性能.

C.      很大的对象
    将内存空间分为一些小的内存块的时候, 还另外一个必须解决的问题. 由于内存块的大小是固定的, 所以将无法存储一个比他大小大的对象. 解决这个问题的方法是有一个额外的较大的内存空间——而只是把这个真实对象(就是那个放不下的)的引用放入内存块中.

D.      循环问题
已经讨论过的算法可以说是在解决问题上是相当有用且具有一定的扩展性. 但是循环依旧是一个需要解决的问题.
       到目前为止, 所有例子中没有出现在两个或两个以上内存块中存在循环的现象. 看这个例子:

注意, 这个例子中, “记忆集合”已经被优化过, 使得只存在从高标记(之前说过内存块被标上数字)向低标记内存块的引用. 一旦运行算法, 我们必须承认, 有一种回收后的结果可能仅仅只是将内存块(当然包括”记忆集合”)的位置进行一个细微的变化. 如图10所示.

但是当我们进行下一次垃圾回收的时候, 可能回收结果又再一次变回了图9所示的内存空间. 这将会是一个死循环——除非程序释放了对象A, F或是G的内存空间, 或是分配了新的对象. 否则, 对象C, E和D将会永远不被清理, 就这样一直浪费内存——这当然是我们所不能接受的.
显然对于存在于一个两个或两个以上内存块构成的引用循环中的垃圾对象而言, 它将永远不会清除. 事实上, 在一个真实的程序中, 很有可能出现这样的内存结构. 例如, 对一个双向链表的引用消失了.(这个情况下, 只存在了链表内部无休止的引用了).
直觉告诉我们, 解决这个问题的方法是将所有的引用循环都放入同一个内存块中去.


        因为, 如果对象在内存块中是像图11那样分布的话, 那么对象C D和E就能够被正确地清除垃圾了. 但是链接结构大小的上限就是可用内存的大小, 所以我们不能将内存空间分成更小的内存块了. 假设内存块能够随着需要不断增大, 那么循环的问题将会很容易得到解决.
       如果对象A是要被保留下来的, 而在另外一个内存块中有这个对象的引用, 那么对象A将会被移到这个引用所在的内存块中去. 那些只有被根引用指向的对象会被移动到一个新的内存块中.  如果有个对象被好几个内存块中的引用指向的话, 那么这个对象可以被移动到这个内存块中的任意一个.
这个策略保证了经过几次迭代之后, 死的链表结构都被放在了同一个内存块中了. 来看看这个算法对于图9的情况是怎样工作的.

        因为D和E这两个对象仅仅被C引用, 所以他们将不会被拷贝到最后一个内存块中去, 但是却被移动到了第二个内存块中去了. 要注意的是, 这将不会生效, 因为一个内存块最多只能容得下三个对象——对于这个情形将在后面讲到.
        图13中显示了下一步完成后的内存空间.


       对象F和G都由根引用指向, 所以他们被保留下来, 剩下的对象就被清理了. 这个情况和图11非常相似. 在这瞬间地调用之后, C, E和对象D被正确的清理了.
       现在, 至少在程序不会持续地改变两个对象根引用的情况下, 经过有限次的迭代, 一个由排外的垃圾对象组成的循环将会被回收. 这里排外的垃圾对象指的是上文中提到的彼此构成引用, 却没有其它根引用的对象. 但是现在, 可以看到算法正在随意地改变内存块的大小. 仅仅改变内存块大小的做法不是一个很好的解决办法——因为在每次循环中, 内存块都是在运行的, 所以这样的回收策略不是渐进式的.
模拟火车站
针对上述提到的问题, 火车算法一个解决方法是随意改变内存块的大小——这也是火车算法名字的来源.
A.      模拟火车
为了更好的理解这个算法, 对象空间可以被看作是一个大火车站. 内存块依然有大小的限制, 在这个算法中, 他们扮演了车厢的角色. 车厢被组织起来形成一列”火车”——一列”火车”可以有任意多的车厢. 每个车厢都有一个记忆集合, 同样每列”火车”也会有一个记忆集合——这个记忆集合只包含火车内部的引用.
B.      例子
图14基于图1的对象结构, 只是这里对象空间被组织成一个火车站了. 其中包含了若干个被按序标记的火车, 火车由随意多个同样被按序标记的车厢组成. 在这个例子中, 有两列火车. 每个车厢最多可以存储三个对象, 每列火车可以包含任意多个车厢.

火车的记忆集合是它所有车厢记忆集合的总和, 不包括那些来自其它火车的引用. 在图14中, 对象E是1.1车厢在引用集合中, 但是他不在1号火车的引用集合中. 因为垃圾回收算法总是从标记最小的车厢开始, 在更新引用集合的时候, 只有那些来自标记高的车厢的引用才被看作是. 因此, 对象E属于车厢1.1的记忆集合, 而对象C不在车厢1.2的记忆集合中.
当垃圾回收器收集第一个车厢, 对象A需要保留下来, 由于是根引用指向它, 所以它会被拷贝到一个完全新的火车中去. 由于对象B只有被A引用, 所以它会被拷贝到和A同一列火车中去. 这一点很重要, 因为通过这种方式, 自循环的垃圾对象结构最终被转移到同一列单独的火车中去了. 由于对象C被来自同一列火车的对象引用, 所以它被拷贝到了火车的最后去了. 现在第一个车厢空了, 可以被释放了. 通过第一遍回收, 火车站中的状况可以如图15所示.

记忆集合将会相应地进行更新. 第一列火车已经没有从外面(这里的外面指的是第一列火车以外)指向的引用的,所以在下一次回收中, 整个火车空间将会被案例的释放. 如图16所示.

任何时候, 在第一列火车中自循环的垃圾对象结构不会被拷贝到另外火车中去. 当所有不在这个自循环结构中的对象被拷贝到其它火车中后, 这列火车将会被释放. 这很容易理解. 可是是否能保证每一个自循环的结构最终都会留在第一列火车中呢? 如果一个自循环结构分布在一些不同的火车中, 那么, 在一系列迭代之后, 原来第二列火车会成为这个自循环结构的第一列火车, 并且结构体中的所有对象, 都会被分配到其它火车中去.(这里的其它火车指的是刚才自循环结构所占据的一些火车, 但是除去第一列火车.). 因此包含这个自循环结构对象火车数量会减少一个. 当火车数目达到1时, 剩下的这个火车中包含了自循环结构的所有对象, 于是, 这个垃圾对象结构可以被正确的回收了.
图17反映一个由4个对象组成的自循环结构.

在算法第一次执行后, 火车1被释放了, 对象A被转移到了火车2中. 下一次, 对象A和B被一起转移到了火车3中,下一次是和C一起到火车4中去了——最后, 自循环结构中所有的对象都被转移到了同一个火车中, 那么等到下一次算法执行时, 这个自循环结构将会被释放了.  看上去算法执行得不错.
c.      书面方式描述算法
1.       选择标号最小的火车.
2.       如果火车的记忆集合是空的, 释放整列火车并终止, 否则进行第三步操作.
3.       选择火车中标号最小的车厢.
4.       对于车厢记忆集合的每个元素:
a.       如果它是一个被根引用引用的对象, 那么, 将拷贝到一列新的火车中去; 如果是一个被其它火车的对象指向的对象, 那么, 将它拷贝到这个指向它的火车中去.
b.       假设有一些对象已经被保留下来了, 那么通过这些对象可以触及到的对象将会被拷贝到同一列火车中去.
在这个步骤中, 有必要对受影响的引用集合进行相应地更新. 如果一个对象被来自多个火车的对象引用, 那么它可以被拷贝到任意一个火车去.
5.       释放车厢并且终止.
d      用Java实现火车算法
首先假设以下类型和方法是存在的:
import java.util.List;

/**引用*/
abstract class Reference{
    /**Return the source of the reference*/
    abstract Object getSourceObject();
    /**Return the referenced object*/
    abstract Object getReferencedObject();
}

/**对象*/
abstract class Object{
    /**Return all references that are contained in the object*/
    abstract List<Reference> getReferences();
    /**Return the car that corresponds to this object 
     * or null if this object is not part of the object space.*/
    abstract Car getCar();
    /**Return true if this object is referenced from outside its train.*/
    abstract boolean isreferencedFromTheOutside();
}

/**火车*/
abstract class Train{
    /**
     * return the size of the remembered set of that train
     */
    abstract int getRememberedSetSize();
    /**
     * Adds an object to the last cat of the train.
     * If the last car is full, a new car is automatically appended.
     * The car pointer of the train has to be update.
     * Also the reference sets of the old and new car and 
     * reference set sizes of their corresponding trains.
     * @param o
     */
    abstract void addObject(Object o);
    /**Free the entire train.*/
    abstract void free();
}

/**车厢*/
abstract class Car{
    /**Return the train that corresponds to this car.*/
    abstract Train getTrain();
    /**Returns true if this car will be processed before Car c.*/
    abstract boolean hasLowerNumber(Car c);
    /**Returns a list of references that 
     *represent the remembered set of this car*/
    abstract List<Reference> getRememberedSet();
    /**Frees this car.*/
    abstract void free();
}
/**对象空间*/
abstract class ObjectSpace{
    /**Returns car number 1.1 
     * or null if there is no car in the object space*/
    abstract Car getLowestNumberedCar();
    /**Return a newly created train that is appended 
     * at the end of the list of trains*/
    abstract Train createTrain();
}
以下是垃圾回收的伪代码:
class Colletion{
    public void doCollectionRun(ObjectSpace objectSpace){
        Car car = objectSpace.getLowestNumberedCar();
        if(null == car) //如果对象空间中已经没有车厢了, 表明全部都已经被回收了.
            return;
        
        Train train = car.getTrain();
        if( 0 == train.getRememberedSetSize() ){ 
            //如果这列火车记忆集合的大小为0, 那么就可以将整列火车进行释放了.
            train.free();
            return;
        }
        //对记忆集合中的引用进行遍历
        List<Reference> rememberedSet = car.getRememberedSet();
        for(Reference r : rememberedSet){
            
            Object o = r.getReferencedObject(); // 获得这个引用指向的对象
            Object source = r.getSourceObject();
            
            if( o.getCar() != car ){
                
                //如果这个对象已经被垃圾回收器处理了
                if(o.getCar() != source.getCar() ){
                    
                    //更新记忆集合
                    if(null == source.getCar() /*根引用*/
                            || o.getCar().hasLowerNumber(source.getCar() ) ){
                        o.getCar().getRememberedSet().add(r);
                    }else{
                        source.getCar().getRememberedSet().add(r);
                    }
                }
                continue;
            }
            
            if(null == source.getCar() ){
                //如果是根引用
                objectSpace.createTrain().addObject(o);
            }else if(source.getCar().getTrain() == car.getTrain() ){//来自同一列火车
                if(!o.isreferencedFromTheOutside() ){   //这个对象的引用来自己同一列火车
                    //当且仅当没有从外面来的引用, 那么将对象拷贝到火车的最后一个车厢
                    source.getCar().getTrain().addObject(o);
                }
            }else{
                //由于引用来自其它火车, 那么就移到其它火车中去.即移到引用它的引用所在的对象
                source.getCar().getTrain().addObject(o);
            }
            
            //由于对象o已经被保留下来了, 
            //那么凡是通过这个对象能够被程序操作的对象都要被保留下来
            Queue<Object> queue;
            queue.add(o);
            while(!queue.isEmpty() ){
                
                Object cur = queue.get();
                List<Reference> references = cur.getReferences();
                
                for(Reference r : references){
                    if(r.getSourceObject().getCar() == car &&
                            !r.getSourceObject().isreferencedFromTheOutside() ){
                        
                        //如果是来自同一列火车的, 那么就加到o对象所在的火车中去
                        o.getCar().getTrain().addObject(r.getReferencedObject() );
                    }
                }
            }
        }
        
        car.free();
    }
}



上面的代码展示了一个简单的垃圾回收算法运作过程, 但是依然存在漏洞, 并且在这些假设的方法中, 也需要在细节上作一番解释.

正确的火车算法
垃圾回收算法的一个重要特性是所有的垃圾对象都被回收并且不会出现无限循环. 上面示意的算法已经能够对自己循环结构进行正确的处理了, 但是有诡异的问题.
A.      错误
假设每个车厢只能够存储一个对象.看下面这个程序:
class Pointer{
            Pointer p;
        }
        
        Pointer objectA = new Pointer();
        Pointer objectB = new Pointer();
        
        Pointer R1  = objectB;
        R1.p        = objectA;
        
        objectA = null;
        objectB = null;
        
        while(true){
            //此处进行垃圾回收
            Pointer tmp = R1.p;
            R1.p = R1;
            R1 = tmp;
            tmp = null;
            new Pointer();
        }
即使垃圾回收器在标记的地方正确地运行, 也不会有任何垃圾对象被回收, 于是随着程序中while循环体的执行,程序将会消耗越来越多的内存.
图18显示了一个调整后的内存空间.

对象B被根指针引用, 对象A被B引用.
在进行一次垃圾回收后, 得到的对象空间就像图19所示. 毫无疑问, 如果程序没有作任何修改的话, 那么执行下次垃圾回收之后, 将会把对象B移到最后一列火车去, 而所有其它对象将会被正确地清除掉.

但是现在程序改变了, 对象A现在被根指针引用了, 对象B被对象A引用了.图20给出了调整后的对象空间示意图.

     当垃圾收集器执行下一次回收时, 他发现对象B被来自己同一列火车的对象引用着, 于是他在这列火车最后增加一个新的车厢, 并将对象B移到那是——而不是将对象B移到最后一列火车中去. 现在程序再次改变了指针, 调整后的内存空间如图21和开始的时候(图18)完全一样,  唯一的不同之处是所有新分配的对象空间都还在内存空间中(没有被回收). 因此, 垃圾收集器没有清除任何不被使用的对象.


显然, 这是算法中一个严重的问题. 当然, 程序不可能被设计成这样. 但是仍然有可能会出现这样的情况.幸运的是, 对于论点诡异的场景, 已经有了解决方案了.   Just remember that B was pointed to by a reference from outside the train and ensure that it is copied out of train number one even if there are no external references. This is of course only needed if there were no objects copied out of the first train in the current pass. Then the first member of the remembered set of the train is saved. When processing a car the algorithm has to look if there is such a special reference and treat it as if it would still exist.
B. 更正算法

现在来看看如何更正前面描述的火车算法, 来使他在面对这里提到的这个似乎很难发现的场景中也能够正确运行. 在原本的算法中, 我们只要添加上这样一个规则:
1.       如果当前车厢的记忆集合是空的, 这种情况下, 如果有一个指向车厢内的引用, 那么就要将这个引用加入到记忆集合中去了.
2.       如果有一个指向火车最后一节车厢的引用, 那么在这次垃圾回收工作后, 这个引用将会被移除.
abstract class ObjectSpace{ 
    /**Returns car number 1.1  
     * or null if there is no car in the object space*/ 
    abstract Car getLowestNumberedCar(); 
    /**Return a newly created train that is appended  
     * at the end of the list of trains*/ 
    abstract Train createTrain(); 
}

上面描述的对象空间伪代码中, 要加入一个新的成员变量, 这是一个特殊的引用, 并且当内存空间中不存在这样的引用的时候, 这个变量赋值为null.
在出现如下场景:
当这个特殊的引用指向当前车厢, 并且没有来自当前火车外面的引用指向这个车厢, 那么特殊的引用将会被加入到引用列表中去.
无论何时, 在没有对象从火车的第一个车厢中拷贝出去时, 这个火车记忆集合中的一个成员将会赋予给上面提到的这个特殊引用.  一列火车的记忆集合通常不会进行将其它更明确的信息进行保存, 因为他仅仅是将这个火车中所有车厢的记忆集合进行一个整合, 并且不包括任何内部的引用. 因此(垃圾)收集器不得不遍历所有车厢, 但是这样会导致很严重的性能下降. 幸运的是已经有解决方案了: 在没有对象从第一列火车从拷贝出去的时候, 设置一个标记,如果这个标记已经被设置了, 写障碍(write barrier)机制就会赋给原来的引用一个特殊的值, 然后在下次指针对第一列火车执行这个操作的时候清空这个标记(即将他置为没有标记状态).