📄 lib0043.html
字号:
<html>
<META http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>malloc() Version 5: Mark-Sweep</title>
<link rel="STYLESHEET" type="text/css" href="images/xpolecat.css">
<link rel="STYLESHEET" type="text/css" href="images/ie.content.books24x7.css">
</head>
<body >
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<td><div STYLE="MARGIN-LEFT: 0.15in;">
<a href="toc.html"><img src="images/teamlib.gif" width="62" height="15" border="0" align="absmiddle" alt="Team LiB"></a></div></td>
<td valign="top" class="v2" align="right"><div STYLE="MARGIN-RIGHT: 0.15in"><a href="LiB0042.html"><img src="images/previous.gif" width="62" height="15" border="0" align="absmiddle" alt="Previous Section"></a>
<a href="LiB0044.html"><img src="images/next.gif" width="41" height="15" border="0" align="absmiddle" alt="Next Section"></a>
</div></td></tr>
</table>
<div class="chapter">
<a name="ch05"></a>
<div class="section">
<h2 class="first-section-title"><a name="570"></a><a name="ch05lev1sec3"></a><span class="fixed">malloc()</span> Version 5: Mark-Sweep</h2><div class="section">
<h3 class="sect3-title">
<a name="571"></a><a name="ch05lev2sec5"></a>Theory</h3>
<p class="first-para">The operation of automatic memory managers consists of two phases: locating memory garbage and reclaiming that garbage. The mark-sweep approach to garbage collection is named after how it implements these two phases. The mark-sweep technique belongs to the tracing school of garbage collection. This means that a mark-sweep collector takes an active role in ferreting out memory references instead of relying on the compiler to do all the work.</p>
<p class="para">The mark phase involves taking all the currently occupied memory blocks and marking them as "testing" because, for the moment, we do not know which memory blocks are genuinely occupied and which memory blocks are garbage. Next, the mark-sweep collector looks through the application's memory space searching for pointers to the heap. Any memory blocks that still have pointers referencing them are allowed to return to "occupied" status.</p>
<a name="572"></a><a name="IDX-305"></a>
<p class="para">The remaining "testing" blocks are assumed to be garbage and collected. The sweep phase involves moving through the heap and releasing these "testing" blocks. In other words, the memory manager sweeps all of the garbage back into the "free" bucket.</p>
<p class="para">The basic mark-sweep dance steps are displayed in <a class="internaljump" href="#ch05fig05">Figure 5.5</a>.</p>
<div class="figure">
<a name="573"></a><a name="ch05fig05"></a><span class="figuremediaobject"><a href="images/fig333%5F01%5F0%2Ejpg" NAME="IMG_85" target="_parent"><img src="images/fig333_01.jpg" height="241" width="350" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 5.5</span></span>
</div>
<p class="para">As mentioned in <a href="LiB0026.html#290" target="_parent" class="chapterjump">Chapter 3</a>, most applications have four types of sections: code sections, data sections, stack sections, and one or more heaps. Because code sections tend to be designated as execute-only memory areas, only the stack, heap, and data section of an application can be scanned for pointers (see <a class="internaljump" href="#ch05fig06">Figure 5.6</a>). In my implementation, I scan only the heap and the stack.</p>
<div class="figure">
<a name="574"></a><a name="ch05fig06"></a><span class="figuremediaobject"><a href="images/fig333%5F02%5F0%2Ejpg" NAME="IMG_86" target="_parent"><img src="images/fig333_02.jpg" height="397" width="199" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 5.6</span></span>
</div>
<a name="575"></a><a name="IDX-306"></a>
<div class="qandaset">
<table border="0" cellpadding="0">
<tr class="qandaentry">
<td class="td" valign="top" width="2%">
<p class="first-para">
<a name="LiB24"><b>1. </b></a>
</p>
</td><td class="td" valign="top" width="90%">
<p class="first-para">OK, so if the manager looks for pointers, what does a pointer look like?</p>
</td><td class="td" valign="top" width="8%">
<p class="first-para">
<a href="#LiB23"><img src="images/question.gif" height="24" width="24" alt="Some compilers add a special tag to pointers. The problem with this approach is that the tag consumes part of a pointer's storage space and prevents a pointer from being capable of referencing the full address space. I decided that in my implementation, I would use a conservative garbage collection approach and consider any 32-bit value to be a potential pointer. This basically means that I have to scan memory byte-by-byte to enumerate every possible 32-bit value (see Figure 5.7 ). " border="0"></a>
</p>
</td>
</tr>
</table>
<p class="bold">Answers</p>
<table border="0" cellpadding="0">
<tr class="qandaentry-answer">
<td class="td" valign="top" width="2%">
<p class="first-para">
<a class="internaljump" name="answer.nr-qandaentry.5F65F703-5059-4621-8D79-A56ECE78C6F1" href="#LiB24"><b>1.</b></a> </p>
</td><td class="td" valign="top" width="90%">
<p class="first-para">Some compilers add a special tag to pointers. The problem with this approach is that the tag consumes part of a pointer's storage space and prevents a pointer from being capable of referencing the full address space. I decided that in my implementation, I would use a <i class="emphasis">conservative garbage collection</i> approach and consider any 32-bit value to be a potential pointer. This basically means that I have to scan memory byte-by-byte to enumerate every possible 32-bit value (see <a class="internaljump" href="#ch05fig07">Figure 5.7</a>).<div class="figure">
<a name="576"></a><a name="ch05fig07"></a><span class="figuremediaobject"><a href="images/fig334%5F01%5F0%2Ejpg" NAME="IMG_87" target="_parent"><img src="images/fig334_01.jpg" height="189" width="277" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 5.7</span></span>
</div>
</p>
</td>
</tr>
</table>
</div>
<p class="para">In my implementation, each memory block header has a <span class="fixed">STATE</span> field. This field is 8 bits in size and may be in one of three states: Free, Occupied, Testing. The remaining fields are similar to those used by the sequential fit manual memory manager (see <a class="internaljump" href="#ch05fig08">Figure 5.8</a>).</p>
<div class="figure">
<a name="577"></a><a name="ch05fig08"></a><span class="figuremediaobject"><a href="images/fig335%5F01%5F0%2Ejpg" NAME="IMG_88" target="_parent"><img src="images/fig335_01.jpg" height="177" width="286" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 5.8</span></span>
</div>
<p class="para">There are a couple of policy decisions that a mark-sweep collector has to make. Specifically, a mark-sweep memory manager has to decide which parts of memory it is going to monitor and when it is going sweep them to reclaim garbage.</p>
<p class="para">I decided in my implementation that I would search for pointers in the heap and the stack. This would allow me to search through an application's local variables and dynamically allocated storage. As far as deciding when to garbage collect, I decided to use a counter variable called <span class="fixed">tick</span> that would invoke the garbage collection algorithm after reaching a certain value (stored in a variable called <span class="fixed">period</span>). <a name="578"></a><a name="IDX-307"></a>The programmer can configure the value of <span class="fixed">period</span> so that they may control how often garbage collection occurs.</p>
<p class="para">I also provide a <span class="fixed">forceCollection()</span> function that can be used to force the memory manager to perform a sweep of memory.</p>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note </td><td valign="top" class="admon-body">
<p class="first-para">This function does not suggest that garbage collection occur; it demands that garbage collection occur.</p>
</td>
</tr>
</table>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="579"></a><a name="ch05lev2sec6"></a>Implementation</h3>
<p class="first-para">I decided to implement a mark-sweep garbage collector by modifying the sequential fit implementation in <a href="LiB0032.html#418" target="_parent" class="chapterjump">Chapter 4</a>. My implementation of the reference counting memory manager required four files:</p>
<a name="580"></a><a name="ch05table02"></a>
<table class="table" border="1">
<caption class="table-title">
<span class="table-title"><span class="table-titlelabel">Table 5.2</span></span>
</caption>
<thead>
<tr valign="top">
<th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">File</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Use</b>
</p>
</th>
</tr>
</thead>
<tbody>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">driver.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">contains <span class="fixed">main()</span>, is the scene of the crime</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">mallocV5.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">
<span class="fixed">newMalloc(), newFree()</span> wrappers (5th version)</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">perform.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">implements the <span class="fixed">PerformanceTest</span> class</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">memmgr.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">implements the <span class="fixed">MarkSweepMemoryManager</span> class</p>
</td>
</tr>
</tbody>
</table>
<div class="section">
<h4 class="sect4-title">driver.cpp</h4>
<p class="first-para">This file contains the <span class="fixed">main()</span> entry point. You can build my implementation to execute a diagnostic test or a performance test. To build the diagnostic version, you will need to comment out the <span class="fixed">PerformanceTestDriver()</span> invocation and uncomment the <span class="fixed">debugTest()</span> invocation. You will also need to activate the <span class="fixed">DEBUG_XXX</span> macros in the <span class="fixed">mallocV4.cpp</span> file.</p>
<a name="581"></a><a name="IDX-308"></a>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include<mallocV5.cpp></span>
<span style="background-color:d9d9d9">#include<perform.cpp></span>
<span style="background-color:d9d9d9">void debugTest()</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">void *ptr;</span>
<span style="background-color:d9d9d9">void *ptr1;</span>
<span style="background-color:d9d9d9">void *ptr2;</span>
<span style="background-color:d9d9d9">unsigned long *lptr;</span>
<span style="background-color:d9d9d9">unsigned long allocs[6]={8,12,33,1,122,50};</span>
<span style="background-color:d9d9d9">printf("address of ptr = %p\n",&ptr);</span>
<span style="background-color:d9d9d9">printf("address of ptr1 = %p\n",&ptr1);</span>
<span style="background-color:d9d9d9">printf("address of ptr2 = %p\n",&ptr2);</span>
<span style="background-color:d9d9d9">printf("address of lptr = %p\n",&lptr);</span>
<span style="background-color:d9d9d9">printf("address of allocs = %p\n",allocs);</span>
<span style="background-color:d9d9d9">initMemMgr(270,4);</span>
<span style="background-color:d9d9d9">//8</span>
<span style="background-color:d9d9d9">ptr = newMalloc(allocs[0]); if(ptr==NULL){ printf</span>
<span style="background-color:d9d9d9">("ptr==NULL!\n"); }</span>
<span style="background-color:d9d9d9">//12</span>
<span style="background-color:d9d9d9">ptr = newMalloc(allocs[1]); if(ptr==NULL){ printf</span>
<span style="background-color:d9d9d9">("ptr==NULL!\n"); }</span>
<span style="background-color:d9d9d9">ptr2=ptr;</span>
<span style="background-color:d9d9d9">//33</span>
<span style="background-color:d9d9d9">ptr = newMalloc(allocs[2]); if(ptr==NULL){ printf</span>
<span style="background-color:d9d9d9">("ptr==NULL!\n"); }</span>
<span style="background-color:d9d9d9">lptr=(unsigned long*)ptr;</span>
<span style="background-color:d9d9d9">*lptr=(unsigned long)ptr;</span>
<span style="background-color:d9d9d9">lptr=NULL;</span>
<span style="background-color:d9d9d9">//1</span>
<span style="background-color:d9d9d9">//first garbage collection here</span>
<span style="background-color:d9d9d9">ptr = newMalloc(allocs[3]); if(ptr==NULL){ printf</span>
<span style="background-color:d9d9d9">("ptr==NULL!\n"); }</span>
<span style="background-color:d9d9d9">ptr2=ptr;</span>
<span style="background-color:d9d9d9">//122</span>
<span style="background-color:d9d9d9">ptr = newMalloc(allocs[4]); if(ptr==NULL){ printf</span>
<span style="background-color:d9d9d9">("ptr==NULL!\n"); }</span>
<span style="background-color:d9d9d9">ptr1=ptr;</span>
<span style="background-color:d9d9d9">//50, should fail</span>
<span style="background-color:d9d9d9">ptr = newMalloc(allocs[5]); if(ptr==NULL){ printf</span>
<span style="background-color:d9d9d9">("ptr==NULL!\n"); }</span><a name="582"></a><a name="IDX-309"></a>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -