Portable, unobtrusive garbage collection for multiprocessor systems

We describe and prove the correctness of a new concurrent mark-and-sweep garbage collection algorithm. This algo-rithm derives from the classical on-the- y algorithm from Dijkstra et al. [9]. A distinguishing feature of our algo-rithm is that it supports multiprocessor environments where the registers of running processes are not readily accessible, without imposing any overhead on the elementary opera-tions of loading a register or reading or initializing a eld. Furthermore our collector never blocks running mutator pro-cesses except possibly on requests for free memory; in par-ticular, updating a eld or creating or marking or sweeping a heap object does not involve system-dependent synchro-nization primitives such as locks. We also provide support for process creation and deletion, and for managing an ex-tensible heap of variable-sized objects.