Lock-free atom garbage collection for multithreaded Prolog
The runtime system of dynamic languages such as Prolog or Lisp and their derivatives contain a symbol table, in Prolog often called the atom table. A simple dynamically resizing hash-table used to be an adequate way to implement this table. As Prolog becomes fashionable for 24 × 7 server processes we need to deal with atom garbage collection and concurrent access to the atom table. Classical lock-based implementations to ensure consistency of the atom table scale poorly and a stop-the-world approach to implement atom garbage collection quickly becomes a bottle-neck, making Prolog unsuitable for soft real-time applications. In this article we describe a novel implementation for the atom table using lock-free techniques where the atom-table remains accessible even during atom garbage collection. Relying only on CAS (Compare And Swap) and not on external libraries, the implementation is straightforward and portable.
|Stakeholder||SecuritEase, New Zealand|
|Journal||Theory and Practice of Logic Programming|
|Conference||International Conference on Logic Programming|
Wielemaker, J, & Harris, K. (Keri). (2016). Lock-free atom garbage collection for multithreaded Prolog. Theory and Practice of Logic Programming, 16(5-6). doi:10.1017/S1471068416000272