Automatic garbage collection (GC) prevents certain kinds of bugs and reduces programming overhead. GC techniques for sequential programs are based on reachability analysis. However, testing reachability from a root set is inadequate for determining whether an actor is garbage: Observe that an unreachable actor may send a message to a reachable actor. Instead, it is sufficient to check termination (sometimes also called quiescence): an actor is terminated if it is not currently processing a message and cannot receive a message in the future. Moreover, many actor frameworks provide all actors with access to file I/O or external storage; without inspecting an actor's internal code, it is necessary to check that the actor has terminated to ensure that it may be garbage collected in these frameworks. Previous algorithms to detect actor garbage require coordination mechanisms such as causal message delivery or nonlocal monitoring of actors for mutation. Such coordination mechanisms adversely affect concurrency and are therefore expensive in distributed systems. We present a low-overhead reference listing technique (called DRL) for termination detection in actor systems. DRL is based on asynchronous local snapshots and message-passing between actors. This enables a decentralized implementation and transient network partition tolerance. The paper provides a formal description of DRL, shows that all actors identified as garbage have indeed terminated (safety), and that all terminated actors--under certain reasonable assumptions--will eventually be identified (liveness).
翻译:自动垃圾收集(GC) 防止某些类型的错误,并减少编程管理费用。 连续程序GC技术基于可达性分析。 但是,根件的测试可达性不足以确定一个行为者是否是垃圾: 观察一个无法接触的行为者可能向一个可以接触的行为者发送信息。 相反, 足以检查终止( 有时也称为“ 私密” ): 一个行为者如果目前不处理一个信息, 未来无法接收信息, 就会终止。 此外, 许多行为者框架为所有行为者提供了访问文件 I/ O 或外部存储的渠道。 在不检查一个行为者的内部代码的情况下, 有必要检查一个行为者是否已经终止了, 以确保它可能是在这些框架中收集的垃圾 。 先前的检测行为者垃圾的算法需要协调机制, 如因因果关系而发送信息或对行为者进行非本地监测以进行突变异。 这种协调机制对调频度有不利影响,因此在分布式系统中费用很高。 我们在演员系统中提供低端参考列表技术(称为 DRL ) 用于检测终止操作系统。 DRL 是基于不稳的本地快照和信件传递者之间的内部代码, 最终显示一个分散化的服务器。