Packer: An innovative space-time-efficient parallel garbage collection algorithm based on virtual spaces
Packer: An innovative space-time-efficient parallel garbage collection algorithm based on virtual spaces
复制标题
DOI：
10.1109/ipdps.2009.5160989
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
Shaoshan Liu;Ligang Wang;Xiao-Feng Li;J. Gaudiot
中科院分区：
文献类型：
--
作者：
Shaoshan Liu;Ligang Wang;Xiao-Feng Li;J. Gaudiot
垃圾收集器（GC）设计的根本挑战是以最小的时间开销最大化回收的空间。为了有效的内存管理，在许多GC设计中，堆被分为大对象空间（LOS）和非大对象空间（non-LOS）。当其中一个空间已满时，即使另一个空间可能仍有大量空闲空间，也会触发垃圾收集，从而导致空间利用效率低下。此外，现有GC设计中的空间划分意味着不同的GC算法用于不同的空间。这不仅延长了垃圾收集的暂停时间，而且使收集在多个空间上效率不高。为了解决这些问题，我们提出了包装，一个空间和时间效率的并行垃圾收集算法的基础上的新概念的虚拟空间。Packer不是将堆物理地划分为多个空间，而是在一个物理共享空间中管理多个虚拟空间。通过多个虚拟空间，Packer提供了高效内存管理的优势。同时，由于只有一个物理共享空间，Packer避免了空间利用效率低下的问题。为了减少Packer的垃圾收集暂停时间，我们还提出了一种新的并行化方法，适用于多个虚拟空间。我们把压缩GC并行化问题简化为树遍历并行化问题，并将其应用于普通和大型对象压缩。
The fundamental challenge of garbage collector (GC) design is to maximize the recycled space with minimal time overhead. For efficient memory management, in many GC designs the heap is divided into large object space (LOS) and non-large object space (non-LOS). When one of the spaces is full, garbage collection is triggered even though the other space may still have a lot of free room, thus leading to inefficient space utilization. Also, space partitioning in existing GC designs implies different GC algorithms for different spaces. This not only prolongs the pause time of garbage collection, but also makes collection not efficient on multiple spaces. To address these problems, we propose Packer, a space-and-time-efficient parallel garbage collection algorithm based on the novel concept of virtual spaces. Instead of physically dividing the heap into multiple spaces, Packer manages multiple virtual spaces in one physically shared space. With multiple virtual spaces, Packer offers the advantage of efficient memory management. At the same time, with one physically shared space, Packer avoids the problem of inefficient space utilization. To reduce the garbage collection pause time of Packer, we also propose a novel parallelization method that is applicable to multiple virtual spaces. We reduce the compacting GC parallelization problem into a tree traversal parallelization problem, and apply it to both normal and large object compaction.