📄 page425.html
字号:
<HTML><HEAD><TITLE>Mark-and-Sweep Garbage Collection</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="tex2html6071" HREF="page426.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6069" HREF="page415.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6063" HREF="page424.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6073" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0013300000000000000000">Mark-and-Sweep Garbage Collection</A></H1><P><A NAME="secgarbagemarksweep"> </A><P>This section presentsthe <em>mark-and-sweep</em><A NAME=30690> </A><A NAME=30691> </A>garbage collection algorithm.The mark-and-sweep algorithm was the first garbage collection algorithmto be developed that is able to reclaim cyclic data structures.<A NAME="tex2html768" HREF="footnode.html#30692"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A>Variations of the mark-and-sweep algorithm continue to be among the mostcommonly used garbage collection techniques.<P>When using mark-and-sweep,unreferenced objects are not reclaimed immediately.Instead, garbage is allowed to accumulate until all available memoryhas been exhausted.When that happens,the execution of the program is suspended temporarilywhile the mark-and-sweep algorithm collects all the garbage.Once all unreferenced objects have been reclaimed,the normal execution of the program can resume.<P>The mark-and-sweep algorithm is called a <em>tracing</em> garbage collectorbecause is <em>traces out</em> the entire collection of objectsthat are directly or indirectly accessible by the program.The objects that a program can access directlyare those objects which are referenced by local variableson the processor stack as well as by any global variablesthat refer to objects.In the context of garbage collection,these variables are called the <em>roots</em><A NAME=30696> </A>.An object is indirectly accessibleif it is referenced by a field in some other(directly or indirectly) accessible object.An accessible object is said to be <em>live</em><A NAME=30698> </A>.Conversely, an object which is not <em>live</em> is garbage.<P>The mark-and-sweep algorithm consists of two phases:In the first phase, it finds and marks all accessible objects.The first phase is called the <em>mark</em> phase.In the second phase, the garbage collection algorithm scansthrough the heap and reclaims all the unmarked objects.The second phase is called the <em>sweep</em> phase.The algorithm can be expressed as follows:<PRE>def markAndSweep(): for r in roots: mark(r) sweep()</PRE><P>In order to distinguish the live objects from garbage,we record the state of an object in each object.That is, we add a special <tt>bool</tt> field to each objectcalled, say, <tt>marked</tt>.By default, all objects are unmarked when they are created.Thus, the <tt>marked</tt> field is initially <tt>False</tt>.<P>An object <tt>p</tt> and all the objects indirectly accessiblefrom <tt>p</tt> can be marked by using the following recursive<tt>mark</tt> method:<PRE>def mark(p): if not p.marked: p.marked = True for q in successors(p): mark(q)</PRE>Notice that this recursive <tt>mark</tt> algorithmdoes nothing when it encounters an object that has already been marked.Consequently, the algorithm is guaranteed to terminate.And it terminates only when all accessible objects have been marked.<P>In its second phase, the mark-and-sweep algorithmscans through all the objects in the heap,in order to locate all the unmarked objects.The storage allocated to the unmarked objects is reclaimed during the scan.At the same time, the <tt>marked</tt> field on every live object is set backto <tt>False</tt> in preparation for the next invocation of themark-and-sweep garbage collection algorithm:<PRE>def sweep(): for p in heap: if p.marked: p.marked = False else: heap.release(p)</PRE><P>Figure <A HREF="page425.html#figgarbage5"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the operation of the mark-and-sweepgarbage collection algorithm.Figure <A HREF="page425.html#figgarbage5"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a) shows the conditions before garbage collection begins.In this example, there is a single root variable.Figure <A HREF="page425.html#figgarbage5"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b) shows the effect of the <em>mark</em> phaseof the algorithm.At this point, all live objects have been marked.Finally, Figure <A HREF="page425.html#figgarbage5"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c) shows the objects left after the <em>sweep</em>phase has been completed.Only live objects remain in memory and the <tt>marked</tt> fields haveall been set to <tt>False</tt> again.<P><P><A NAME="30956"> </A><A NAME="figgarbage5"> </A> <IMG WIDTH=575 HEIGHT=534 ALIGN=BOTTOM ALT="figure30720" SRC="img1695.gif" ><BR><STRONG>Figure:</STRONG> Mark-and-sweep garbage collection.<BR><P><P>Because the mark-and-sweep garbage collection algorithmtraces out the set of objects accessible from the roots,it is able to correctly identify and collect garbageeven in the presence of reference cycles.This is the main advantage of mark-and-sweep over the referencecounting technique presented in the preceding section.A secondary benefit of the mark-and-sweep approach is thatthe normal manipulations of reference variables incurs no overhead.<P>The main disadvantage of the mark-and-sweep approach is the factthat that normal program execution is suspended while thegarbage collection algorithm runs.In particular, this can be a problem in a program that interactswith a human user or that must satisfy real-time execution constraints.For example, an interactive application that uses mark-and-sweepgarbage collection becomes unresponsive periodically.<P><BR> <HR><UL> <LI> <A NAME="tex2html6074" HREF="page426.html#SECTION0013310000000000000000">The Fragmentation Problem</A></UL><HR><A NAME="tex2html6071" HREF="page426.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6069" HREF="page415.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6063" HREF="page424.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6073" 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 + -