On bounding time and space for multiprocessor garbage collection
On bounding time and space for multiprocessor garbage collection
复制标题
DOI：
10.1145/301618.301648
复制
发表时间：
1999-05
期刊：
影响因子：
--
通讯作者：
G. Blelloch;P. Cheng
中科院分区：
文献类型：
--
作者：
G. Blelloch;P. Cheng
本文提出了首个在时间和空间上具有可证明界限的多处理器垃圾回收算法。该算法是一种实时共享内存复制回收器。我们证明该算法最多需要2(R(l + 2/k) + N + 5PD)个内存位置，其中P是处理器的数量，R是计算过程中可达到的最大空间（从根集可访问的位置数量），N是可达到对象的最大数量，D是任何数据对象的最大深度，k是一个参数，指定每次分配一个位置时复制多少个位置。此外，我们表明客户端线程的暂停时间不会超过与k个非阻塞机器指令成比例的时间。即使对于任意长度的数组，这些界限也能得到保证。回收器只需要写屏障（读操作不受回收器影响），对产生垃圾的线程做很少的假设，并允许它们大部分时间异步运行。
This paper presents the first multiprocessor garbage collection algorithm with provable bounds on time and space. The algorithm is a real-time shared-memory copying collector. We prove that the algorithm requires at most 2(R(l + 2/k) + N + 5PD) memory locations, where P is the number of processors, R is the maximum reachable space during a computation (number of locations accessible from the root set), N is the maximum number of reachable objects, D is the maximum depth of any data object, and k is a parameter specifying how many locations are copied each time a location is allocated. Furthermore we show that client threads are never stopped for more than time proportional to k non-blocking machine instructions. The bounds are guaranteed even with arbitrary length arrays. The collector only requires write-barriers (reads are unaffected by the collector), makes few assumptions about the threads that are generating the garbage, and allows them to run mostly asynchronously.