page422.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 121 行
HTML
121 行
<HTML><HEAD><TITLE>Reference Counting 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="tex2html6038" HREF="page423.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6036" HREF="page415.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6030" HREF="page421.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6040" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0013200000000000000000">Reference Counting Garbage Collection</A></H1><P>The difficulty in garbage collection is notthe actual process of collecting the garbage--it is the problem of finding the garbage in the first place.An object is considered to be garbagewhen no references to that object exist.But how can we tell when no references to an object exist?<P>A simple expedient is to keep track in each objectof the total number of references to that object.That is, we add a special field to each object calleda <em>reference count</em><A NAME=29821> </A><A NAME=29822> </A><A NAME=29823> </A>.The idea is that the reference count field is not accessible tothe Python program.Instead, the reference count field is updated bythe Python virtual machine itself.<P>Consider the statement<PRE>p = int(57)</PRE>which creates a new instance of the <tt>int</tt> class.Only a single variable, <tt>p</tt>, refers to the object.Thus, its reference count should be one.<P><P><A NAME="29898"> </A><A NAME="figgarbage1"> </A> <IMG WIDTH=575 HEIGHT=107 ALIGN=BOTTOM ALT="figure29826" SRC="img1690.gif" ><BR><STRONG>Figure:</STRONG> Objects with reference counters.<BR><P><P>Now consider the following sequence of statements:<PRE>p = int(57)q = p</PRE>This sequence creates a single <tt>int</tt> instance.Both <tt>p</tt> and <tt>q</tt> refer to the same object.Therefore, its reference count should be two.<P>In general, every time one reference variable is assigned to another,it may be necessary to update several reference counts.Suppose <tt>p</tt> and <tt>q</tt> are both reference variables.The assignment<PRE>p = q</PRE>would be implemented by the Python virtual machine as follows:<PRE>if p is not q: if p is not None: p.refCount -= 1 p = q if p is not None: p.refCount += 1</PRE><P>For example suppose <tt>p</tt> and <tt>q</tt> are initialized as follows:<PRE>p = int(57)q = int(99)</PRE>As shown in Figure <A HREF="page422.html#figgarbage2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a),two <tt>int</tt> objects are created,each with a reference count of one.Now, suppose we assign <tt>q</tt> to <tt>p</tt>using the code sequence given above.Figure <A HREF="page422.html#figgarbage2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b) shows that after the assignment,both <tt>p</tt> and <tt>q</tt> refer to the same object--its reference count is two.And the reference count on <tt>int</tt> has gone to zerowhich indicates that it is garbage.<P><P><A NAME="30119"> </A><A NAME="figgarbage2"> </A> <IMG WIDTH=575 HEIGHT=161 ALIGN=BOTTOM ALT="figure29916" SRC="img1691.gif" ><BR><STRONG>Figure:</STRONG> Reference counts before and after the assignment <tt>p = q</tt>.<BR><P><P>The costs of using reference counts are twofold:First, every object requires the special reference count field.Typically, this means an extra word of storagemust be allocated in each object.Second, every time one reference is assigned to another,the reference counts must be adjusted as above.This increases significantly the time taken by assignment statements.<P>The advantage of using reference countsis that garbage is easily identified.When it becomes necessary to reclaim the storage from unused objects,the garbage collector needs only to examine the reference count fieldsof all the objects that have been created by the program.If the reference count is zero, the object is garbage.<P>It is not necessary to wait until there is insufficient memorybefore initiating the garbage collection process.We can reclaim memory used by an object immediatelywhen its reference goes to zero.Consider what happens if we implement the Python assignment<tt>p = q</tt>in the Python virtual machine as follows:<PRE>if p is not q: if p is not None: p.refCount -= 1 if p.refCount == 0: heap.release(p) p = q if p is not None: p.refCount += 1</PRE>Notice that the <tt>release</tt> method is invoked immediatelywhen the reference count of an object goes to zero,i.e., when it becomes garbage.In this way, garbage may be collected incrementally as it is created.<P><BR> <HR><UL> <LI> <A NAME="tex2html6041" HREF="page423.html#SECTION0013210000000000000000">When Objects Refer to Other Objects</A><LI> <A NAME="tex2html6042" HREF="page424.html#SECTION0013220000000000000000">Why Reference Counting Does Not Work</A></UL><HR><A NAME="tex2html6038" HREF="page423.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6036" HREF="page415.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6030" HREF="page421.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6040" 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 + =
减小字号Ctrl + -
显示快捷键?