lib0038.html

Memory Management—Algorithms and implementation in C/C++ Introduction Chapter 1 - Memory Manag

    <span style="background-color:d9d9d9">(*mmptr).printState();</span>
<span style="background-color:d9d9d9">#endif</span>

    <span style="background-color:d9d9d9">return(ptr);</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">void newFree(void *ptr)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">(*mmptr).release(ptr);</span>

<span style="background-color:d9d9d9">#ifdef DEBUG_MALLOCV2</span>
    <span style="background-color:d9d9d9">(*mmptr).printState();</span>
<span style="background-color:d9d9d9">#endif</span>

    <span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span><a name="502"></a><a name="IDX-261"></a>
</pre>
</div>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">driver.cpp</h4>
<p class="first-para">As in the last example, this file contains the <span class="fixed">main()</span> function definition that invokes the testing code. The <span class="fixed">debugTest()</span> was completely rewritten for this implementation. The <span class="fixed">PerformanceTestDriver()</span> function, defined in <span class="fixed">perform.cpp</span> that makes use of the <span class="fixed">PerformanceTest</span> class, has been left untouched.</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;mallocV2.cpp&gt;</span>
<span style="background-color:d9d9d9">#include&lt;perform.cpp&gt;</span>

<span style="background-color:d9d9d9">void debugTest()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">void *ptr [6];</span>
    <span style="background-color:d9d9d9">unsigned long allocs[6]={8,12,33,1,122,50};</span>
    <span style="background-color:d9d9d9">int i;</span>

    <span style="background-color:d9d9d9">initMemMgr(270);</span>

    <span style="background-color:d9d9d9">for(i=0;i&lt;6;i++)</span>
    <span style="background-color:d9d9d9">{</span>
        <span style="background-color:d9d9d9">ptr[i] = newMalloc(allocs[i]);</span>
        <span style="background-color:d9d9d9">if(ptr[i]==NULL){ printf("ptr[%lu]==NULL!\n",i); }</span>
    <span style="background-color:d9d9d9">}</span>

    <span style="background-color:d9d9d9">printf("\n\nFREE MEMORY--------------------------------\n\n");</span>

    <span style="background-color:d9d9d9">newFree(ptr[0]);    //8</span>
    <span style="background-color:d9d9d9">newFree(ptr[3]);    //1</span>
    <span style="background-color:d9d9d9">newFree(ptr[4]);    //122</span>
    <span style="background-color:d9d9d9">newFree(ptr[2]);    //33</span>
    <span style="background-color:d9d9d9">newFree(ptr[1]);    //12</span>
    <span style="background-color:d9d9d9">newFree(ptr[5]);    //50</span>

    <span style="background-color:d9d9d9">closeMemMgr();</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end debugTest-------------------------------------------*/</span>

<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">//for the debug test, should activate debug macros in</span>
      <span style="background-color:d9d9d9">mallocVx.cpp</span>
    <span style="background-color:d9d9d9">//debugTest();</span>
    <span style="background-color:d9d9d9">//for the performance test, should comment out debug macros</span>
    <span style="background-color:d9d9d9">PerformanceTestDriver();</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">} /*end main----------------------------------------------*/</span><a name="503"></a><a name="IDX-262"></a>
</pre>
</div>
<a></a>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="504"></a><a name="ch04lev2sec9"></a>Tests</h3>
<p class="first-para">If you look at the <span class="fixed">main()</span> function defined in <span class="fixed">driver.cpp</span>, you will see that I performed both a debug test and a performance test. I performed a debug test to make sure that the manager was doing what it was supposed to do. If you modify my source code, I would suggest running the debug test again to validate your changes. Once I was sure that the memory manager was operational, I turned off debugging features and ran a performance test.</p>
<p class="para">The debug test is fairly simple, but at the same time, I would take a good, hard look at what is going on. If you decide to run a debug test, you will want to make sure that the <span class="fixed">DEBUG_XXX</span> macros in <span class="fixed">mallocV2.cpp</span> are turned on. You will also want to comment out the <span class="fixed">PerformanceTestDriver()</span> function call in <span class="fixed">main()</span>.</p>
<p class="para">The following output was generated by the debug build of the memory manager:</p>
<div class="informalexample">
<pre class="literallayout">
SequentialFitMemoryManager::SequentialFitMemoryManager(270)
SequentialFitMemoryManager::allocate(8)
SequentialFitMemoryManager::split(): split=YES
0) [P=0][addr=13][St=OCCUPIED][Sz=8][N=34]
1) [P=13][addr=34][St=FREE][Sz=236][N=0]
SequentialFitMemoryManager::allocate(12)
SequentialFitMemoryManager::split(): split=YES
0) [P=0][addr=13][St=OCCUPIED][Sz=8][N=34]
1) [P=13][addr=34][St=OCCUPIED][Sz=12][N=59]
2) [P=34][addr=59][St=FREE][Sz=211][N=0]
SequentialFitMemoryManager::allocate(33)
SequentialFitMemoryManager::split(): split=YES
0) [P=0][addr=13][St=OCCUPIED][Sz=8][N=34]
1) [P=13][addr=34][St=OCCUPIED][Sz=12][N=59]
2) [P=34][addr=59][St=OCCUPIED][Sz=33][N=105]
3) [P=59][addr=105][St=FREE][Sz=165][N=0]
SequentialFitMemoryManager::allocate(1)
SequentialFitMemoryManager::split(): split=YES
0) [P=0][addr=13][St=OCCUPIED][Sz=8][N=34]
1) [P=13][addr=34][St=OCCUPIED][Sz=12][N=59]
2) [P=34][addr=59][St=OCCUPIED][Sz=33][N=105]
3) [P=59][addr=105][St=OCCUPIED][Sz=1][N=119]
4) [P=105][addr=119][St=FREE][Sz=151][N=0]
SequentialFitMemoryManager::allocate(122)
SequentialFitMemoryManager::split(): split=YES
0) [P=0][addr=13][St=OCCUPIED][Sz=8][N=34]
1) [P=13][addr=34][St=OCCUPIED][Sz=12][N=59]
2) [P=34][addr=59][St=OCCUPIED][Sz=33][N=105]
3) [P=59][addr=105][St=OCCUPIED][Sz=1][N=119]
4) [P=105][addr=119][St=OCCUPIED][Sz=122][N=254]
5) [P=119][addr=254][St=FREE][Sz=16][N=0]
SequentialFitMemoryManager::allocate(50)<a name="505"></a><a name="IDX-263"></a>
0) [P=0][addr=13][St=OCCUPIED][Sz=8][N=34]
1) [P=13][addr=34][St=OCCUPIED][Sz=12][N=59]
2) [P=34][addr=59][St=OCCUPIED][Sz=33][N=105]
3) [P=59][addr=105][St=OCCUPIED][Sz=1][N=119]
4) [P=105][addr=119][St=OCCUPIED][Sz=122][N=254]
5) [P=119][addr=254][St=FREE][Sz=16][N=0]
ptr[5]==NULL!


FREE MEMORY---------------------------------------------------------------

SequentialFitMemoryManager::release(5439513)
SequentialFitMemoryManager::address resolves to index 13
0) [P=0][addr=13][St=FREE][Sz=8][N=34]
1) [P=13][addr=34][St=OCCUPIED][Sz=12][N=59]
2) [P=34][addr=59][St=OCCUPIED][Sz=33][N=105]
3) [P=59][addr=105][St=OCCUPIED][Sz=1][N=119]
4) [P=105][addr=119][St=OCCUPIED][Sz=122][N=254]
5) [P=119][addr=254][St=FREE][Sz=16][N=0]
SequentialFitMemoryManager::release(5439605)
SequentialFitMemoryManager::address resolves to index 105
0) [P=0][addr=13][St=FREE][Sz=8][N=34]
1) [P=13][addr=34][St=OCCUPIED][Sz=12][N=59]
2) [P=34][addr=59][St=OCCUPIED][Sz=33][N=105]
3) [P=59][addr=105][St=FREE][Sz=1][N=119]
4) [P=105][addr=119][St=OCCUPIED][Sz=122][N=254]
5) [P=119][addr=254][St=FREE][Sz=16][N=0]
SequentialFitMemoryManager::release(5439619)
SequentialFitMemoryManager::address resolves to index 119
SequentialFitMemoryManager::merge():merging with both sides
0) [P=0][addr=13][St=FREE][Sz=8][N=34]
1) [P=13][addr=34][St=OCCUPIED][Sz=12][N=59]
2) [P=34][addr=59][St=OCCUPIED][Sz=33][N=105]
3) [P=59][addr=105][St=FREE][Sz=165][N=0]
SequentialFitMemoryManager::release(5439559)
SequentialFitMemoryManager::address resolves to index 59
SequentialFitMemoryManager::merge():merging to NEXT
0) [P=0][addr=13][St=FREE][Sz=8][N=34]
1) [P=13][addr=34][St=OCCUPIED][Sz=12][N=59]
2) [P=34][addr=59][St=FREE][Sz=211][N=0]
SequentialFitMemoryManager::release(5439534)
SequentialFitMemoryManager::address resolves to index 34
SequentialFitMemoryManager::merge():merging with both sides
0) [P=0][addr=13][St=FREE][Sz=257][N=0]
SequentialFitMemoryManager::release(): cannot release NULL
pointer
0) [P=0][addr=13][St=FREE][Sz=257][N=0]
SequentialFitMemoryManager::~SequentialFitMemoryManager()free
ram[270]<a name="506"></a><a name="IDX-264"></a>
</pre>
</div>
<p class="para">Although it may seem a tad tedious, it will help you tremendously to read the <span class="fixed">debugTest()</span> function and then step through the previous output. It will give you an insight into what the code is doing and how the particulars are implemented.</p>
<p class="para">The performance test was conducted by commenting out <span class="fixed">debugTest()</span> and the debug macros in <span class="fixed">mallocV2.cpp</span>, and then enabling the <span class="fixed">PerformanceTestDriver()</span> function. The results of the performance run were interesting:</p>
<div class="informalexample">
<pre class="literallayout">
PerformanceTest::runTest(): time whistle blown
PerformanceTest::runTest(): race has ended
msecs=35
</pre>
</div>
<p class="last-para">As you can see, the performance increase is dramatic.</p>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="507"></a><a name="ch04lev2sec10"></a>Trade-Offs</h3>
<p class="first-para">The sequential fit approach solves many of the problems that plagued the bitmapped approach by using an indexing scheme that decreased redundant effort. Instead of manually sifting through each bit in a bit map, we were able to use a series of pointers to find what we needed much more quickly.</p>
<p class="para">While the sequential fit technique did exhibit far better performance than the bit map technique, we were only using a 270-byte heap. For much larger heaps, such as a 15MB heap, the amount of time needed to traverse a sequential linked list from beginning to end can hurt performance. Thus, the sequential fit method is not exactly a scalable solution.</p>
<p class="para">In terms of choosing a memory block to allocate, I use what is known as the <i class="emphasis">first-fit policy,</i> which is to say that my implementation uses the first satisfactory block of memory that it finds. There are other policies, like next-fit, best-fit, and worst-fit.</p>
<p class="para">The first-fit policy tends to cause the blocks of memory at the start of the linked list to splinter into a number of smaller blocks. Given that the sequential fit algorithm traverses the list starting from the beginning during an allocation, this can hurt execution time.</p>
<p class="para">The <i class="emphasis">next-fit</i> policy is like the first-fit policy, but the memory manager keeps track of the position of the last allocation. When the next allocation request is processed, the manager will start traversing the linked list from the point of the last allocation. This is done in an attempt to avoid re-traversing the beginning of the list.</p>
<p class="para">The <i class="emphasis">best-fit</i> policy traverses the linked list of memory blocks and uses the smallest possible block that will satisfy an allocation request. The best-fit approach does not waste memory and <a name="508"></a><a name="IDX-265"></a>minimizes internal fragmentation. In doing so, however, the policy tends to generate significant external fragmentation. The search for a "best" block can also be expensive in terms of execution time because several possible blocks may have to be located and compared.</p>
<p class="last-para">The <i class="emphasis">worst-fit</i> policy is instituted by having the memory manager allocate the largest possible memory block for a given request. This policy aims at minimizing external fragmentation. It also does a good job of eliminating large memory blocks so that the memory manager will fail when a request for a large block is submitted.</p>
<a></a>
</div>
<a></a>
</div>
</div>
</div>
</div>
<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="LiB0037.html"><img src="images/previous.gif" width="62" height="15" border="0" align="absmiddle" alt="Previous Section"></a>
<a href="LiB0039.html"><img src="images/next.gif" width="41" height="15" border="0" align="absmiddle" alt="Next Section"></a>
</div></td></tr>
</table>
</body>
</html>