multithreading - 这种异步垃圾收集器可能存在的缺陷

Question

我一直在研究一些关于垃圾收集的知识，主要应用于服务器端/实时应用程序，并且我已经开始草拟一种算法，使用它可以拥有一个异步垃圾收集系统。由于我现在开始讨论这个主题，所以我对 gc 算法不是很了解，所以我想知道这样的实现可能存在的陷阱。算法很粗糙，有很多未定义的部分。

我是这样想的:

• 每个线程都有自己的堆空间来管理，并存储它拥有的指针列表，这些指针正在被其他线程使用有了它，垃圾收集工作完全异步于正在运行的线程，并且:
• 阶段 1 开始跟踪线程的根并标记线程可访问的所有对象。如果我们进入另一个线程的空间，我们将停止跟踪这个指针，并在所有者线程上将这个指针标记为“正在使用”
• 在我们标记了所有区域之后，我们选择一个区域(可能具有最多死引用的区域)，并开始将其事件对象引用复制到另一个空间。 (它可能是整个线程堆空间，但我认为这个操作可能会占用太多内存)
• 复制从使用 CAS 设置一个标志开始，该标志表明正在复制对象。设置该标志时要对此特定对象执行的任何可变操作都将自旋锁定，直到 gc 线程设置新地址为止。复制完成后，将在旧地址上设置一个新地址，并且要对该对象执行的任何可变引用都将路由到新对象
• 在使用 CAS 更新对这些指针的所有引用后，旧空间最终被释放(不会使用错误地址更新新指针，因为每个修改器将首先检查引用是否已更改位置)

就是这样!

无论如何，我对一个可能的实现感到非常兴奋，它不会停止世界，并且只使用仅适用于被复制对象的快速自旋锁。但我想知道这是否有可能实现，或者是否有可能在某处有一个悬空指针，或者内存泄漏，或者它是无效的，等等。任何有助于此的信息将不胜感激!

我不太确定例如它将处理来自不同线程的循环引用。我认为这会很自然地处理，因为我们更新了当前 gc'ed 线程具有的所有危险指针。可能还有某种我没有考虑到的并发访问。

谢谢!

---- 编辑:感谢欧内斯特的贡献，我正在考虑不使用复制算法，而是使用简单的标记和扫描。那是因为我们每次访问对象的变量时都需要检查指针是否已更新。这在我看来是一个相当大的开销。不是吗？

Answer 1

你的想法很好，但我相信有很多微妙的问题需要大量的工作来解决，一旦解决，你将无法获得有竞争力的吞吐量性能。

each thread has its own heap space to manage, and stores a list of pointers it owns that are in use by other threads With that, garbage collection works totally asynchronous to the running threads, and:

如果有一个共享对象，哪个线程拥有它？如果一个并发集合有不同线程添加的对象，会不会有很多堆间指针？您如何处理堆之间的循环？

phase 1 start following the threads' roots and marking all objects reacheable by them. If we get into another thread's space, we stop following this pointer, and mark this pointer as "in use" on the owner thread

如果这与 mutator 运行同时完成，您如何防止在 GC 执行此标记时 mutator 改变拓扑以引入或消除堆间引用的竞争条件？

after we have marked all regions, we select a region (maybe with most dead references as possible), and start copying its live object references to another space. (it might be the whole thread heap space, but I think it could be too memory-intensive this operation)

如果这是针对多核，复制将使全局内存带宽饱和并破坏可伸缩性。

copying starts with setting with CAS a flag which states that the object is being copied. Any mutable action to be performed on this particular object while that flag is set will spin lock until a new address is set by the gc thread. When copying finishes, a new address is set on the old one, and any mutable reference to be performed on the object will be routed to the new object

无锁是棘手的。您正在对内存模型做出假设。您可能需要内存屏障。看起来您只是在模拟一个锁，在这种情况下，您谈论的是在每次将引用写入堆时获取和释放锁，这会非常昂贵。

自旋锁也不利于并发，因为您不仅会占用一个线程，还会燃烧一个无法再完成您正在等待的工作的核心!查看last core slowdown GHC 中的错误。无等待解决方案将使用 CAS 来获取 mutator 线程来帮助 GC 工作，而不是阻塞等待另一个线程来完成它。

after updating all references made to those pointers using CAS, the old space is finally freed (no new pointers will be updated with the wrong address, since every mutator will first check to see if the reference has changed locations)

好的。