Cheney's algorithm: Difference between revisions

Revision as of 23:16, 18 March 2022

Revision as of 03:24, 26 April 2022

Line 1:

{{Use dmy dates|date=September 2021}}

{{more footnotes|date=April 2014}}

'''Cheney's algorithm''', first described in a 1970 [[Association for Computing Machinery|ACM]] paper by C.J. Cheney, is a [[stop and copy]] method of [[tracing garbage collection]] in computer software systems. In this scheme, the [[Memory management#Dynamic memory allocation|heap]] is divided into two equal halves, only one of which is in use at any one time. Garbage collection is performed by copying live objects from one semispace (the from-space) to the other (the to-space), which then becomes the new heap. The entire old heap is then discarded in one piece. It is an improvement on the previous stop and copy technique.{{citation needed|date=April 2016}}

Cheney's algorithm reclaims items as follows:

* '''Object references on the stack.''' Object references on the stack are checked. One of the two following actions is taken for each object reference that points to an object in from-space:

** If the object has not yet been moved to the to-space, this is done by creating an identical copy in the to-space, and then replacing the from-space version with a forwarding pointer to the to-space copy. Then update the object reference to refer to the new version in to-space.

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

* '''Objects in the to-space.''' The 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 objects.

Line 44:

swap(fromspace, tospace)

allocPtr = tospace

scanPtr = tospace

-- scan every root you've got

Line 56:

r = copy(r)

EndForEach

scanPtr = scanPtr + o.size() -- points to the next object in the to-space, if any

EndWhile

</pre>

Line 69:

EndIf

return forwarding-address(o)

</pre>

Line 78 ⟶ 77:

== Equivalence to tri-color abstraction ==

Cheney's algorithm is an example of a [[Tracingtracing garbage collection#Tri-color marking|tri-color marking]] garbage collector. 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.

Line 86 ⟶ 85:

== References ==

* {{cite journal

| last = Cheney | first = C.J.

| title = A Nonrecursive List Compacting Algorithm

| journal = Communications of the ACM

| volume = 13 | issue = 11 | date = November 1970 | pages = 677–678

| doi = 10.1145/362790.362798

| s2cid = 36538112

}}

* {{cite journal

| last1 = Fenichel | first1 = R.R.

|last2=Yochelson |first2 = Jerome C.

| title = A LISP garbage-collector for virtual-memory computer systems

| journal = Communications of the ACM

| volume = 12 | issue = 11 |year=1969 | pages = 611–612

| doi = 10.1145/363269.363280

| last2 = Yochelson

| s2cid = 36616954

| first2 = Jerome C.

}}

| s2cid = 36616954

}}

* {{cite journal

| last =Byers Byers| first = Rick

| title = Garbage Collection Algorithms

| journal = Garbage Collection Algorithms

| volume = 12 | issue = 11 |year=2007 | pages = 3–4

| url = http://courses.cs.washington.edu/courses/csep521/07wi/prj/rick.pdf

}}

{{Memory management}}

[[Category:Automatic memory management]]