Concurrent Collection of Cyclic Garbage in Reference Counting Systems

A method for processing changes to reference counts in a reference counting system, each reference count associated with a particular object and containing a number of references that reference the particular object, the method comprising the steps of:

• determining increments and decrements of reference counts for a current time period;
• processing the increments of reference counts for the current time period;
• storing the decrements of reference counts for the current time period;
• and
• processing decrements of reference counts for a previous time period.

A computer system comprising:

• a memory that stores computer-readable code;
• and
• a processor operatively coupled to the memory, the processor configured to implement the computer-readable code, the computer-readable code configured to:
• identify candidate objects having associated reference counts for garbage collection, wherein each candidate object is potentially garbage;
• and
• determine if the candidate objects are garbage, the step of determining performed without preventing mutators in the system from changing object references and the step of determining further comprising the steps of:
• determining, after a time period, if the candidate objects are still potentially garbage;
• and
• for those candidate objects that are still potentially garbage, determining if the reference count associated with the candidate object has changed.

An article of manufacture comprising:

• a computer-readable medium having computer-readable program code means embodied thereon, the computer-readable program code means comprising:
• a step to identify candidate objects having associated reference counts for garbage collection, wherein each candidate object is potentially garbage;
• and
• a step to determine if the candidate objects are garbage, the step of determining performed without preventing mutators in the system from changing object references and the step of determining further comprising the steps of:
• determining, after a time period, if the candidate objects are still potentially garbage;
• and
• for those candidate objects that are still potentially garbage, determining if the reference count associated with the candidate object has changed.