2.2 Garbage Collection

Figure 2: References between regular and shared objects.

POSH implements a separate algorithm for multi-process garbage collection of shared objects.

Python implements garbage collection through reference counting, maintaining a simple reference count for each object. Reference counts are updated using the Py_INCREF and Py_DECREF macros, which increment and decrement the count without any form of synchronization. Consequently, these macros will not work correctly for shared objects, which can be accessed concurrently by multiple processes. Furthermore, using a single reference count per object makes it impossible to avoid memory leaks when processes terminate abnormally, since no knowledge is maintained about the number of references any particular process holds to an object. A garbage collection algorithm for shared objects must be able to account for references from all live processes, and should be able to correct the reference counts of shared objects when processes terminate abnormally. POSH implements an alternative garbage collection algorithm for shared objects that meets these requirements. It builds on the observation that references to shared objects fall within one of two categories.

(A)

References stored in a process' address space. This may be viewed as a reference leading from a process to the shared object.

(B)

References stored in another shared object. This may be viewed as a reference leading from one shared object to another.

POSH ensures that every reference from a process to a shared object is wrapped in a special proxy object. A proxy object holds a single reference to a shared object, and allows transparent access to the shared object by forwarding all attribute accesses. A process may have any number of references to a given proxy object, but there is never more than one proxy object in a process for a given shared object. The problem of tracking references of type (A) is thus reduced to tracking all proxy objects in existence. POSH sets an upper limit to the number of processes that can be created, and associates a bitmap with each shared object. The bitmap uses a single bit per process to indicate whether or not that process has a proxy object for the shared object. From another viewpoint, the bitmap represents a binary reference count per process.

Maintaining such a bitmap consequently accounts for all references of type (A) as defined above. To account for references of type (B), leading from one shared object to another, a separate counter is maintained. Together, the bitmap and the counter constitute the state that must be maintained for each shared object. When all the bits in the bitmap are cleared (indicating that no process has a proxy object for it), and the counter is 0, the shared object can be deleted.

Figure 2 shows an example in which three processes are sharing a total of five objects. In the figure, none of the processes have a proxy object for E, meaning that all the bits in E's bitmap are cleared. However, there is a reference from D to E, which is reflected in E's counter and prevents the object from being deleted. Conversely, there are two proxy objects for C, which means that two of the bits in the bitmap are set. There are no references to C from other shared objects, however, so once the two proxy objects are deleted, C will be deleted as well.

The normal reference count, ob_refcnt, has no meaning for shared objects, and is initialized to 2³⁰. This value is chosen so that C code that views shared objects as regular PyObjects can use the Py_INCREF and Py_DECREF macros without harm, as long as the operations performed are neutral with regard to the reference count. The unsynchronized access to the object's reference count leads to the theoretical possibility of lost updates, which could be a problem if the reference count reached 0 or overflowed. However, the probability of a lost update incorrectly modifying the reference count in the same direction a total of 2³⁰ times is assumed to be so extremely low that the possibility can be disregarded.