列车算法-526互联

[资料来源](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 对象写屏障