Cheney's algorithm

Cheney's algorithm

Cheney's algorithm, first described in a 1970 ACM paper by C.J. Cheney, is a method of garbage collection in computer software systems. In this scheme, the 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.

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.

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

The algorithm needs no stack and only two pointers outside of the from-space and to-space: a pointer to the beginning of free space in the to-space, and a pointer to the next word in to-space that needs to be examined. For this reason, it's sometimes called a "two-finger" collector --- it only needs "two fingers" pointing into the to-space to keep track of its state. The data between the two fingers represents work remaining for it to do.

The forwarding pointer (sometimes called a "broken heart") is used only during the garbage collection process: When a reference to an object already in to-space (thus having a forwarding pointer in from-space) is found, the reference can be updated quickly simply by updating its pointer to match the forwarding pointer.

Because the strategy is to exhaust all live references, and then all references in referenced objects, this is known as a breadth-first list copying garbage collection scheme.

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 Tri-color 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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Mark-compact algorithm — In computer science, a mark compact algorithm is a type of garbage collection algorithm used to reclaim unreachable memory. Mark compact algorithms can be regarded as a combination of the mark sweep algorithm and Cheney s copying algorithm. First …   Wikipedia

  • Chicken (Scheme implementation) — Chicken Scheme Original author(s) Felix Winkelmann Developer(s) The Chicken Team Initial release …   Wikipedia

  • Breadth-first search — Infobox Algorithm class=Search Algorithm Order in which the nodes are expanded data=Graph time=O(|V|+|E|) = O(b^d) space=O(|V|+|E|) = O(b^d) optimal=yes (for unweighted graphs) complete=yesIn graph theory, breadth first search (BFS) is a graph… …   Wikipedia

  • Garbage collection (computer science) — This article is about garbage collection in memory management. For garbage collection in an SSD, see garbage collection (SSD). For other uses, see garbage collection. In computer science, garbage collection (GC) is a form of automatic memory… …   Wikipedia

  • M.T.A. — For other uses, see MTA (disambiguation). M.T.A. , often called The MTA Song , is a 1949 song by Jacqueline Steiner and Bess Lomax Hawes. Known informally as Charlie on the MTA , the song s lyrics tell of a man named Charlie trapped on Boston s… …   Wikipedia

  • Murray Waas — Murray S. Waas (born 20 December 1961)[1] is an American freelance investigative journalist known most recently for his coverage of the White House planning for the 2003 invasion of Iraq and ensuing controversies and American political scandals… …   Wikipedia

  • Nominal terms (computer science) — Nominal terms are a metalanguage for embedding object languages with binding constructs into. Intuitively, they may be seen as an extension of first order terms with support for name binding. Consequently, the native notion of equality between… …   Wikipedia

  • Approximation theory — In mathematics, approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby. Note that what is meant by best and simpler will depend on …   Wikipedia

  • diff — This article is about the file comparison utility. For other uses, see DIFF (disambiguation). Diffs redirects here. For the American punk rock group, see The Diffs. In computing, diff is a file comparison utility that outputs the differences… …   Wikipedia

  • Cutting-plane method — In mathematical optimization, the cutting plane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are popularly used to… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”