Image: Structure and Interpretation of Computer Programs p.764a

Description: (From the description p.761 (733) in the pdf file): Stop-and-copy garbage collection: memory is divided in two halves: working memory and free memory. When cons constructs pairs, it allocates these in working memory. When working memory is full, we perform garbage collection by locating all the useful pairs in working memory and copying these into consecutive locations in free memory. (The useful pairs are located by tracing all the car and cdr pointers, starting with the machine registers.) Since we do not copy the garbage, there will presumably be additional free memory that we can use to allocate new pairs. In addition, nothing in the working memory is needed, since all the useful pairs in it have been copied. Thus, if we interchange the roles of working memory and free memory, we can continue processing; new pairs will be allocated in the new working memory (which was the old free memory). When this is full, we can copy the useful pairs into the new free memory (which was the old working memory). The description assumes a Lisp architecture. The diagram illustrates the situation right before garbage collection.
Title: Structure and Interpretation of Computer Programs p.764a
Credit: This file has been extracted from another file: Structure and Interpretation of Computer Programs (Second Edition).pdf p.764 (736)
Author: Massachusetts Institute of Technology, Harold Abelson and Gerald Jay Sussman with Julie Sussman
Usage Terms: Creative Commons Attribution-Share Alike 4.0
License: CC BY-SA 4.0
License Link: https://creativecommons.org/licenses/by-sa/4.0
Attribution Required?: Yes