📄 page428.html
字号:
<HTML><HEAD><TITLE>The Copy Algorithm</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html6102" HREF="page429.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6100" HREF="page427.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6096" HREF="page427.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6104" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0013410000000000000000">The Copy Algorithm</A></H2><P>The stop-and-copy algorithm divides the heap into two regions--an active region and an inactive region.For convenience, we can view each region as a separate heapand we shall refer to them as <tt>activeHeap</tt> and <tt>inactiveHeap</tt>.When the stop-and-copy algorithm is invoked,it copies all live objects from the <tt>activeHeap</tt>to the <tt>inactiveHeap</tt>.It does so by invoking the <tt>copy</tt> method given belowstarting at reach root:<PRE>for r in roots: r = copy(r, inactiveHeap)swap(activeHeap, inactiveHeap)</PRE><P>The <tt>copy</tt> method is complicated by the fact thatit needs to update all object references contained in the objectsas it copies those objects.In order to facilitate this,we record in every object a reference to its copy.That is, we add a special field to each object called <tt>forward</tt>which is a reference to the copy of this object.<P>The recursive <tt>copy</tt> method given below copies a given objectand all the objects indirectly accessible from the given objectto the destination heap.When the <tt>forward</tt> field of an object is <tt>None</tt>,it indicates that the given object has not yet been copied.In this case, the method creates a new instance of the object classin the destination heap.Then, the fields of the object are copied one-by-one.If the field is a value type, the value of that field is copied.However, if the field refers to another object,the <tt>copy</tt> method calls itself recursively to copy that object.<PRE>def copy(p, destination): if p is None: return None if p.forward is None: q = destination.newInstance(type(p)) p.forward = q for f in successors(p): q.f = copy(p.f, destination) q.forward = None return p.forward</PRE><P>If the <tt>copy</tt> method is invoked for an object whose<tt>forward</tt> field is non-<tt>None</tt>,that object has already been copiedand the <tt>forward</tt> field refers to the copy of that objectin the destination heap.In that case, the <tt>copy</tt> method simply returns a referenceto the previously copied object.<P>Figure <A HREF="page428.html#figgarbage6"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> traces the execution of the stop-and-copygarbage collection algorithm.When the algorithm is invoked and before any objects have been copied,the <tt>forward</tt> field of every object in the active region is <tt>None</tt>as shown in Figure <A HREF="page428.html#figgarbage6"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a).In Figure <A HREF="page428.html#figgarbage6"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b),a copy of object <I>A</I>, called <I>A</I>', has been created in the inactive region,and the <tt>forward</tt> field of <I>A</I> refers to <I>A</I>'.<P><P><A NAME="31402"> </A><A NAME="figgarbage6"> </A> <IMG WIDTH=575 HEIGHT=829 ALIGN=BOTTOM ALT="figure30996" SRC="img1696.gif" ><BR><STRONG>Figure:</STRONG> Stop-and-copy garbage collection.<BR><P><P>Since <I>A</I> refers to <I>B</I>,the next object copied is object <I>B</I>.As shown in Figure <A HREF="page428.html#figgarbage6"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c),fragmentation is eliminated by allocating storage for <I>B</I>'immediately next to <I>A</I>'.Next, object <I>C</I> is copied.Notice that <I>C</I> refers to <I>A</I>,but <I>A</I> has already been copied.Object <I>C</I>' obtains its reference to <I>A</I>'from the <tt>forward</tt> field of <I>A</I> as shown in Figure <A HREF="page428.html#figgarbage6"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (d).<P>After all the live objects have been copied from the active regionto the inactive region,the regions exchange their roles.As shown in Figure <A HREF="page428.html#figgarbage6"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (e),all the garbage has been collected and the heap is no longer fragmented.<P><HR><A NAME="tex2html6102" HREF="page429.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6100" HREF="page427.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6096" HREF="page427.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6104" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -