lib0039.html

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

        <span style="background-color:d9d9d9">}</span>
        <span style="background-color:d9d9d9">index = index + SZ_ROW;</span>
    <span style="background-color:d9d9d9">}</span>
    <span style="background-color:d9d9d9">printf("\n");</span>
    <span style="background-color:d9d9d9">return;</span>

<span style="background-color:d9d9d9">}/*end printColumn------------------------------------------------------*/</span>
</pre>
</div>
<a></a>
</div>
<div class="section">
<h4 class="sect4-title">mallocV3.cpp</h4>
<p class="first-para">There were several minor alterations to this file, most notably the presence of a different set of debugging macros. To activate debugging code, uncomment the macros and compile a new build.</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include&lt;stdio.h&gt;</span>
<span style="background-color:d9d9d9">#include&lt;stdlib.h&gt;</span>
<span style="background-color:d9d9d9">#include&lt;windows.h&gt;</span>

<span style="background-color:d9d9d9">//#define DEBUG_SL_MEM_MGR</span>
<span style="background-color:d9d9d9">//#define DEBUG_MALLOCV3</span>

<span style="background-color:d9d9d9">#include&lt;memmgr.cpp&gt;</span><a name="524"></a><a name="IDX-275"></a>
<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">wrapper functions</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">SegregatedMemoryManager *mmptr;</span>

<span style="background-color:d9d9d9">void initMemMgr(unsigned long totalbytes)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">mmptr = new SegregatedMemoryManager(totalbytes);</span>
<span style="background-color:d9d9d9">}</span>

<span style="background-color:d9d9d9">void closeMemMgr()</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">delete(mmptr);</span>
<span style="background-color:d9d9d9">}</span>

<span style="background-color:d9d9d9">void *newMalloc(unsigned long size)</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">void *ptr = (*mmptr).allocate(size);</span>

<span style="background-color:d9d9d9">#ifdef DEBUG_MALLOCV3</span>
    <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_MALLOCV3</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>
</pre>
</div>
<a></a>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="525"></a><a name="ch04lev2sec13"></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 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 <a name="526"></a><a name="IDX-276"></a>debug test, you will want to make sure that the <span class="fixed">DEBUG_XXX</span> macros in <span class="fixed">mallocV3.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">
SegregatedMemoryManager::SegregatedMemoryManager(1048576)
SegregatedMemoryManager::allocate(8)
SegregatedMemoryManager::searchColumn(): free at index 1,
address=00B8000D
[16 bytes][00B8000D]
[32 bytes]
[64 bytes]
[128 bytes]
[256 bytes]
[512 bytes]
[1024 bytes]
[4096 bytes]
SegregatedMemoryManager::allocate(12)
SegregatedMemoryManager::searchColumn(): free at index 6137,
address=00B81805
[16 bytes][00B8000D] [00B81805]
[32 bytes]
[64 bytes]
[128 bytes]
[256 bytes]
[512 bytes]
[1024 bytes]
[4096 bytes]
SegregatedMemoryManager::allocate(33)
SegregatedMemoryManager::searchColumn(): free at index 51,
address=00B8003F
[16 bytes][00B8000D] [00B81805]
[32 bytes]
[64 bytes][00B8003F]
[128 bytes]
[256 bytes]
[512 bytes]
[1024 bytes]
[4096 bytes]
SegregatedMemoryManager::allocate(1)
SegregatedMemoryManager::searchColumn(): free at index 12273,
address=00B82FFD
[16 bytes][00B8000D] [00B81805] [00B82FFD]
[32 bytes]
[64 bytes][00B8003F] [128 bytes]
[256 bytes]
[512 bytes]
[1024 bytes]<a name="527"></a><a name="IDX-277"></a>
[4096 bytes]
SegregatedMemoryManager::allocate(122)
SegregatedMemoryManager::searchColumn(): free at index 116,
address=00B80080
[16 bytes][00B8000D] [00B81805] [00B82FFD]
[32 bytes]
[64 bytes][00B8003F]
[128 bytes][00B80080]
[256 bytes]
[512 bytes]
[1024 bytes]
[4096 bytes]
SegregatedMemoryManager::allocate(50)
SegregatedMemoryManager::searchColumn(): free at index 6187,
address=00B81837
[16 bytes][00B8000D] [00B81805] [00B82FFD]
[32 bytes]
[64 bytes][00B8003F] [00B81837]
[128 bytes][00B80080]
[256 bytes]
[512 bytes]
[1024 bytes]
[4096 bytes]

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

SegregatedMemoryManager::release(00B8000D)
SegregatedMemoryManager::address resolves to index 1
[16 bytes] [00B81805] [00B82FFD]
[32 bytes]
[64 bytes][00B8003F] [00B81837]
[128 bytes] [00B80080]
[256 bytes]
[512 bytes]
[1024 bytes]
[4096 bytes]
SegregatedMemoryManager::release(00B82FFD)
SegregatedMemoryManager::address resolves to index 12273
[16 bytes] [00B81805]
[32 bytes]
[64 bytes][00B8003F] [00B81837]
[128 bytes] [00B80080]
[256 bytes]
[512 bytes]
[1024 bytes]
[4096 bytes]
SegregatedMemoryManager::release(00B80080)
SegregatedMemoryManager::address resolves to index 116
[16 bytes] [00B81805]
[32 bytes]
[64 bytes][00B8003F]  [00B81837]<a name="528"></a><a name="IDX-278"></a>
[128 bytes]
[256 bytes]
[512 bytes]
[1024 bytes]
[4096 bytes]
SegregatedMemoryManager::release(00B8003F)
SegregatedMemoryManager::address resolves to index 51
[16 bytes][00B81805]
[32 bytes]
[64 bytes][00B81837]
[128 bytes]
[256 bytes]
[512 bytes]
[1024 bytes]
[4096 bytes]
SegregatedMemoryManager::release(00B81805)
SegregatedMemoryManager::address resolves to index 6137
[16 bytes]
[32 bytes]
[64 bytes][00B81837]
[128 bytes]
[256 bytes]
[512 bytes]
[1024 bytes]
[4096 bytes]
SegregatedMemoryManager::release(00B81837)
SegregatedMemoryManager::address resolves to index 6187
[16 bytes]
[32 bytes]
[64 bytes]
[128 bytes]
[256 bytes]
[512 bytes]
[1024 bytes]
[4096 bytes]
SegregatedMemoryManager::~SegregatedFitMemoryManager()free
ram[1048576]
</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">mallocV3.cpp</span>, and then enabling the <span class="fixed">PerformanceTestDriver()</span> function. The results of the performance run were:</p>
<div class="informalexample">
<pre class="literallayout">
PerformanceTest::runTest(): time whistle blown
PerformanceTest::runTest(): race has ended
msecs=5<a name="529"></a><a name="IDX-279"></a>
</pre>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="530"></a><a name="ch04lev2sec14"></a>Trade-Offs</h3>
<p class="first-para">Compared to the sequential fit technique, the segregated list implementation is blazing fast. However, this does not come without a cost. The segregated list approach demands a large initial down payment of memory. The fact that only certain block sizes are provided can also lead to severe internal fragmentation. For example, a 1,024-byte block could end up being used to service a 32-byte request.</p>
<p class="last-para">Another issue resulting from fixed block sizes is that there is a distinct ceiling placed on the size of the memory region that can be allocated. In my implementation, you cannot allocate a block larger than 4,096 bytes. If, for some reason, you need a 4,097-byte block of memory, you are plain out of luck. There are variations of my segregated list approach, such as the <i class="emphasis">buddy system,</i> that allow certain forms of splitting and merging to deal with this size-limit problem.</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="LiB0038.html"><img src="images/previous.gif" width="62" height="15" border="0" align="absmiddle" alt="Previous Section"></a>
<a href="LiB0040.html"><img src="images/next.gif" width="41" height="15" border="0" align="absmiddle" alt="Next Section"></a>
</div></td></tr>
</table>
</body>
</html>