Cheney's algorithm: Difference between revisions

Revision as of 02:21, 14 September 2008

Revision as of 04:34, 6 November 2008

Line 6:

** If the object has already been moved to the to-space, simply update the reference from the forwarding pointer in from-space.

* '''Objects referenced by objects on the stackto-space.''' Once this has been done, theThe garbage collector examines all object references ''in the objects that have been migrated to the to-space'', and performs one of the above two actions on the referenced objectobjects.

Once all to-space references have been examined and updated, garbage collection is complete.

Line 17:

== Semispace ==

Cheney based his work on the ''semispace'' garbage collector, which was published a year earlier by R.R. Fenichel and J.C. Yochelson.

== Equivalence to [[Garbage_collection_(computer_science)#Basic_algorithm|Tri-colour abstraction]] ==

The first member of the gray set is the stack itself. Objects referenced on the stack are copied into the to-space, which contains members of the black and gray sets.

The algorithm moves any white objects (equivalent to objects in the from-space without forwarding pointers) to the gray set by copying them to the to-space. Objects that are between the scanning pointer and the free-space pointer on the to-space area are members of the gray set still to be scanned. Objects below the scanning pointer belong to the black set. Objects are moved to the black set by simply moving the scanning pointer over them.

When the scanning pointer reaches the free-space pointer, the gray set is empty, and the algorithm ends.

==References==