列车算法

[资料来源](http://www.ssw.uni-linz.ac.at/General/Staff/TW/Wuerthinger05Train.pdf)http://www.ssw.uni-linz.ac.at/General/Staff/TW/Wuerthinger05Train.pdf 程序可以在两次垃圾收集运行之间执行任何操作，例如更改指针。为了便于讨论，我们假设一个对象只适合于一个单块。考虑以下Java伪代码: c l a s sP o i n t e r{P o i n t e r p ;}P o i n t e r objectA =newP o i n t e r ( ) ;P o i n t e r objectB =newP o i n t e r ( ) ;P o i n t e r R1 = objectB ;/ / Object AR1 . p = objectA ;/ / Object B/ / Ensure t h a t t h e r e are no other/ / root r e f e r e n c e s to A or BobjectA =n u l l;objectB =n u l l;w h i l e(t r u e){/ / Garbage c o l l e c t i o n runP o i n t e r tmp = R1 . p ;R1 . p = R1 ;R1 = tmp ;tmp =n u l l;newP o i n t e r ( ) ;/ / This o b j e c t i s never c o l l e c t e d !} 如果垃圾收集运行总是在标记的位置上，那么就不会有任何垃圾被收集，程序在每次循环中都会使用越来越多的内存。 图18显示了配置之后的对象空间。对象B由根指针引用，对象a由B引用。 在执行一次垃圾收集之后，对象空间的压缩如图18所示。到目前为止，没有任何意外，如果程序没有改变任何东西，垃圾收集器的下一次运行将把对象B移到最后一列火车上。所有其他死亡的对象将被正确地收集。 但是现在程序更改了指针，因此对象A现在由根指针引用，对象B由A引用。图20显示了结果配置 当垃圾回收器处理下一辆车时，它没有将B移到最后一辆火车上，而是注意到B是从同一辆火车中引用的，并将其移到1号火车尾部的一辆新车上。现在程序再次更改指针，结果对象空间的第一个train与图18中的完全相同，唯一的区别是objectspace还包含所有新分配的对象。因此，垃圾收集器永远不会删除任何未使用的对象。 只要记住，B是由列车外部的一个引用指向的，并且确保即使没有外部引用，也要将它从1号列车中复制出来。当然，只有在当前遍历中没有从第一个列车中复制对象时才需要这样做。这样，记住的列车中的第一个成员就被保存下来。在处理一辆汽车时，算法必须查看是否有这样一个特殊的参考，并对待它，就好像它仍然存在一样 在文本表示我们只需要添加,如果记忆集设置当前的汽车是空的,存在一个特殊的引用指向该列车,这个引用添加到记忆集设置。如果特别参考点到最低编号的汽车必须移除后通过 该算法的Java伪代码模型需要ObjectSpace类中的一个新成员变量，该成员变量是特殊引用，如果不存在这样的引用，则为null。当特殊的参考点指向当前车厢，并且没有来自当前列车外部的对该车厢的其他引用时，这个引用必须添加到引用列表中。 每当第一节车厢的任何对象都没有被复制出列车时，记住的列车集合中的一个成员就必须保存为特殊引用。列车的记忆集通常不会被明确地保存，因为它只是所有列车记忆集的并集，没有任何列车内部的引用。因此，收集器必须迭代整个汽车，但这可能会造成相当大的性能损失。幸运的是，有一个解决方案:当第一列火车没有复制对象时，设置一个旗帜。如果设置了该标志，写屏障算法将把旧引用写入特殊值，并在影响第一列火车的下一个指针赋值完成时再次清除该标志。 首先，我们需要找到一个非常快速的方法来获得一个物体的汽车和火车。显然，这是经常需要的，如Java伪代码所示。 解决方案是选择汽车大小的形式2的n次方，也对齐汽车的2的n次方边界。那么对应于某一对象的汽车的指数可以计算如下: i n ta d d r e s s = o b j e c t . getAddress ( ) ;i n tcarIndex = a d d r e s s>>n ; 一个简单的右移就可以了，而且性能非常好。现在我们需要一个数组，它在每个可能的car索引前都有一个条目。这个数组的大小是可用内存的数量除以2的n次方。对于每辆车，我们保存它的列车车号和车号。 c l a s sCar{i n ttrainNumber ;i n tcarNumber ;} Car [ ] indexTable =newCar [MEMORYAVAILABLE>>n ] ; 下一个表显示了与图22所示的对象空间相对应的indextable的可能配置。假设块大小是0xfff(4096)。 index train car memory 0 3 2 0x0000 - 0x0FFF 1 0x1000 - 0x1FFF 2 1 1 0x2000 - 0x2FFF 3 2 1 0x3000 - 0x3FFF 4 0x4000 - 0x4FFF 5 3 3 0x5000 - 0x5FFF 6 0x6000 - 0x6FFF 7 1 2 0x7000 - 0x7FFF 8 3 1 0x8000 - 0x8FFF 注意，一个简单的右移12给出了任何内存地址的表索引。 只有第一辆火车和火车的第一节车厢才能被移动。因此，一个包含所有车辆的所有列车的简单链表，以及包含所有车辆的每个列车的链表，将确保快速找到下一辆车或下一辆火车 当一辆车被释放时，它就会从火车链表中移除，并添加到一个自由列表中。通过这种方式，它甚至只需要固定的时间就可以释放整个火车，因为被标记的汽车可以完全添加到自由列表中。 算法的一个可能的性能问题是所谓的流行对象。当一个对象被许多其他对象引用时，它就被称为流行对象。包含流行对象的汽车有一个非常大的记忆集，复制这样的对象需要很多指针来更新。这里的问题是指向一个对象的引用的数量只受整个引用数量的限制。因此，收集一个非常流行的对象可能意味着垃圾收集器的大量工作，这将导致正常的程序停止一段不可接受的长时间。 这个问题的一个可能的解决方案是使用间接寻址。所有对对象的引用都指向保存该对象真实地址的位置。通过这种方式，只需更新指针就可以非常快速地移动对象。图23显示了这种策略的作用.但是这种解决方案有一个缺点。正如前面所讨论的，在大多数程序中，指针访问比指针赋值频繁得多。在每次对指针的读访问时，这种间接性都需要额外的性能开销 那么，还有其他的机会来处理流行对象吗?只是不要复制他们!当一节车厢里有流行对象时，不要把它收起来放到车厢尽头。不幸的是，如果这样做，会出现许多问题，因为现在可能再次出现无限循环和未收集垃圾。但是所有这些问题都是可以解决的，但是还需要付出很多努力。 让我们讨论第一个问题:如果在一辆车里有一个对象和一个流行对象在一起，它永远不会被收集起来。更糟糕的是，仅被该对象引用的所有对象也不会被释放。图24显示了这种有问题的情况。B、C、D、E和F将是垃圾，但在收集流行对象A之前永远不会被收集。但由于A的流行，这很可能要花很长时间，甚至可能要到程序结束。 如果两个受欢迎的对象形成如图25所示的循环，就会出现另一个问题。如果一列新的列车在需要逻辑移动一个热门对象时启动，又会出现一个无尽循环的情况。整个结构将是垃圾，但永远不会被收集。 所以，首先，必须在移动汽车之前找到一种方法，将所有不受欢迎的物体从汽车中解救出来。这并不像乍一看那么容易，因为如果一辆车里有流行对象，需要处理的记忆集可能非常大。汽车中的每个对象都需要一个单独的记忆集。当一个对象的引用数大于某个特定的数目时，它就被称为popular，并且丢弃这个对象的已记住的集合。使用了大量内存，但第一个问题已经解决 释放所有正常对象后，该车应该附加到哪列火车上?对于流行对象没有记忆集合，要知道这一点，必须为每个对象保存一个附加条目:包含指向该对象的引用的数量最大的列车。这个值可以很容易地更新，而不是向已记住的集合添加条目。 但事实证明，这个问题更加棘手，因为如果一辆汽车里不止一个流行对象，该怎么办?汽车必须能够被拆开。在释放完所有非流行对象后，实体车被分成更小的部分，每个部分包含一个流行对象。 现在必须特别注意找出一个对象属于哪一辆车。上一节中提到的非常有效和简单的策略对于分体式汽车不再适用。事实上，需要一个二叉搜索树来找出一个给定的内存地址属于哪一辆车。图26显示了一辆被分成4个部分的汽车，图27显示了相应的二叉搜索树。在正常的程序中，流行物品是相当罕见的，所以汽车中流行物品的数量应该少一些。如果搜索树是平衡的，树的高度永远不会大于以2为底的(每辆车的最大物品数量)的对数，log2（每辆车的最大物品数量）。 下一章对Richard L. Hudson、Ron Morrison、J. Elliot B.Moss和David S. Munro在1997年提出的DMOS (distributed Mature Object Space)垃圾收集算法进行了概述。它将训练算法的思想扩展到分布式系统中。术语“节点”用于系统的一个成员，并假定所有节点都可以通过消息进行通信。此外，为了简单起见，如果消息没有到达目的地或节点没有作出反应，则会出现的问题将不予讨论。 在分布式系统中使用垃圾收集算法时，我们必须考虑的第一件事是，如何知道来自其他节点的外部引用?必须使用消息来保持每个节点的知识是最新的。 每个对象都有一个所谓的主节点。对象的物理表示驻留在主节点，这个节点还负责删除对象。其他节点只能保存对对象的引用。需要一个消息协议来让主节点知道哪些外部引用指向它自己的对象 发送事件:当A将指向对象的指针发送给另一个节点B时，它必须通知该对象的主节点。 接收事件:当B接收到指针时，主节点也希望得到通知。 Delete事件:当B从它的消息缓冲区中删除指针后，它发送另一个事件。 添加指针事件:对于每一个新创建的引用，对象的节点不是它的主节点，一个事件被创建 删除指针事件:类似地，对于发送的每个丢失指针事件 显示了一个可能的场景，采取的步骤依次是: 1节点1向主节点发送一条关于指针传输的消息。 2节点1发送指向节点2的指针。 3节点2接收指针，并向主节点发送成功接收的消息 4节点2告诉主节点，存在了另一个指向objecta的指针。 5节点2从它的接收缓冲区中删除指针，并就这个事实向主节点发送另一条消息 每当指针在节点2上被复制或覆盖时，将再次通知主节点。当然，有几种可能的优化可以最小化消息的数量。这些将在[2]中详细讨论。 在分布式系统中，使用列车算法需要跨越多个节点的列车。当然，我们可以复制周围的对象，这样可以确保某个train的所有对象都在同一个节点上。但这是相当令人失望的损失，而且常常是不必要的。因此，必须设计一个允许火车车厢在节点上分布的系统 每列火车都有一个所谓的主节点。这个节点创建了这个火车，并负责管理这个火车，并添加需要创建该火车的车厢的新节点。使用某列火车的所有节点都使用令牌环方案连接。当节点想要加入环时，它向主节点发送一条消息，然后在主节点之后被添加到环中。环中的每个节点都知道它的后继节点。下面的Java伪代码可以完成这项工作。 c l a s sNode{Node s u c c e s s o r ;v o i dwantToJoin ( Node n ){n . s u c c e s s o r =t h i s. s u c c e s s o r ;t h i s. s u c c e s s o r = n ;}} 一个不再包含任何列车车厢的节点可以离开环。请注意，主节点必须永远不离开，直到列车被销毁，因为它负责欢迎新节点 一个节点如何离开环的想法如下:在环上传递一个令牌，当它到达想要离开的节点的前任节点时，前任节点相应地设置它的继任者。要特别注意一行中不止一个节点想要离开环的可能性。然后他们将能够同时离开。示例实现如下面的Java伪代码所示，图30给出了可视化。 c l a s sNode{Node s u c c e s s o r ;v o i dprocessLeaveMessage ( Node leaver , Node newSuccessor ){i f(t h i s. s u c c e s s o r == l e a v e r ){/ / We are predecessort h i s. s u c c e s s o r = newSuccessor ;}e l s e{i f( newSuccessor ==t h i s&& weWantToLeave ( ) ){s u c c e s s o r . processLeaveMessage ( leaver , s u c c e s s o r ) ;}e l s e{s u c c e s s o r . processLeaveMessage ( leaver , newSuccessor ) ;}}}} 在没有全局同步的情况下，必须解决的主要问题之一是，如何确定列车何时可以报废?再次使用令牌环系统。在设计这种算法时，必须记住一个重要的事实:当没有外部引用到火车时，无论发生什么，都不会有任何外部引用到它。这很简单，因为没有人知道火车的任何物体，就好像整列火车不存在一样。 第一种方法是，当这个节点上没有对train的外部引用时，只让令牌继续运行到下一个节点。在令牌循环一圈后，火车被丢弃。但这是完全错误的，因为即使在某个时间点A的某个节点上没有对车厢的外部引用，由于在其他节点上对该列车的引用，也可以创建对A节点上对象的新的外部引用。 因此，只有当令牌按照建议传递给一个循环，并传递额外的一轮，以确保同时没有新的外部引用添加到任何节点时，我们才能丢弃该train。这导致以下算法: c l a s sTrain{b o o l e a nchanged ;i n tnumberOfExternalReferences ;v o i dremoveExternalReference (){numberOfExternalReferences−−;}v o i dnewExternalReference (){numberOfExternalReferences ++;changed =t r u e;}}c l a s sNode{Node s u c c e s s o r ;v o i dp r o c e s s D i s c a r d T r a i n ( Node sender , Train t r a i n ){i f( ! t r a i n . changed ){i f( sender ==t h i s){/ / The t r a i n can be s a f e l y discardedt r a i n . d i s c a r d ( ) ;}e l s e{s u c c e s s o r . p r o c e s s D i s c a r d T r a i n ( sender , t r a i n ) ;}}e l s e{w h i l e( t r a i n . numberOfExternalReferences>0){wait ( ) ;}t r a i n . changed =f a l s e;s u c c e s s o r . p r o c e s s D i s c a r d T r a i n (t h i s, t r a i n ) ;}}} 任何知道没有外部引用到它的部分的节点都可以启动这个过程。该表显示了节点1开始向节点2发送消息时令牌的进展情况 current node N2 N3 N1 N2 N3 N1 sender N1 N2 N3 N1 N2 N3 old changed T T T F F F new changed F F F F F F 现在发送方更改的值为false，它等于当前节点，因此可以删除该列车。例如，如果在此期间向节点3添加了一个新引用，那么该列车将不会被释放。当令牌到达节点时，源设置为N3，令牌必须等待，直到外部引用被删除 因为被处理的列车并不总是像普通列车算法中那样总是第一个列车，而且可能一次处理多个列车，所以有可能在试图查看是否可以丢弃它的同时插入新对象。这只能发生如果一个对象有一个多余的相对较低的编号的火车。图31显示了有问题的情况。 可以收集A对象的列车，但是如果同时对B的车厢进行处理，情况如图32所示。因为有一个对B的外部引用，所以不能再删除火车! 要阻止其他节点在某列火车上增加汽车是不容易的。一种可能的解决方案是跟踪在更改位设置为false后添加到列车的所有对象。如果火车真的被收集起来，这些对象必须通过形成新的火车来拯救。 当系统需要快速反应时，就必须使用增量策略。Train算法给出了一种可用于分布式系统的增量垃圾收集策略。 copying collector 当对象年轻时有效 列车算法 对old object 进行回收 标记-整理算法 重新定位对象 暂停时间<10ms 对象写屏障