lib0037.html

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

<h4 class="sect4-title">Tests</h4>
<p class="first-para">I performed two different tests against this memory manager. A debug test was performed 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 was performed by executing the code in the <span class="fixed">debugTest()</span> function defined in the <span class="fixed">driver.cpp</span> source file. I keep things fairly simple, but at the same time, I 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">mallocV1.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. After every allocation and release, I print out the contents of the bit map and the binary search tree. This provides a state snapshot of the memory manager. Also, the bits in each bit map byte read from left to right (which is to say that the lower order bits are on the left-hand side):</p>
<div class="informalexample">
<pre class="literallayout">
BitMap::BitMap(): nbytes=3, nbits=24
MemoryManager::MemoryManager():mallloc() mem[384]
MemoryManager::allocate(): request 8 bytes
MemoryManager::allocate(): run_bits=1
MemoryManager::allocate(): found run of 1 bits at 0<a name="474"></a><a name="IDX-243"></a>
insertNode(): inserting 5373964
MemoryManager::allocate(): address=5373964
----------------------------------------------
byte[0]=fe
01111111
byte[1]=ff
11111111
byte[2]=ff
11111111
----------------------------------------------
(5373964)
----------------------------------------------
MemoryManager::allocate(): request 12 bytes
MemoryManager::allocate(): run_bits=l
MemoryManager::allocate(): found run of 1 bits at 1
insertNode(): moving right
insertNode(): inserting 5373980
MemoryManager::allocate(): address=5373980
----------------------------------------------
byte[0]=fc
00111111
byte[l]=ff
11111111
byte[2]=ff
11111111
-----------------------------------------------
-(5373980)
(5373964)
----------------------------------------------
MemoryManager::allocate(): request 33 bytes
MemoryManager::allocate(): run_bits=3
MemoryManager::allocate(): found run of 3 bits at 2
insertNode(): moving right
insertNode(): moving right
insertNode(): inserting 5373996
MemoryManager::allocate(): address=5373996
----------------------------------------------
byte[0]=e0
00000111
byte[l]=ff
11111111
byte[2]=ff
11111111
----------------------------------------------
--(5373996)
-(5373980)
(5373964)
----------------------------------------------
MemoryManager::allocate(): request 1 bytes
MemoryManager::allocate(): run_bits=l
MemoryManager::allocate(): found run of 1 bits at 5<a name="475"></a><a name="IDX-244"></a>
insertNode(): moving right
insertNode(): moving right
insertNode(): moving right
insertNode(): inserting 5374044
MemoryManager::allocate(): address=5374044
----------------------------------------------
byte[0]=c0
00000011
byte[1]=ff
11111111
byte[2]=ff
11111111
-------------------------------------------------
---(5374044)
--(5373996)
-(5373980)
(5373964)
----------------------------------------------
MemoryManager::allocate(): request 122 bytes
MemoryManager::allocate(): run_bits=8
MemoryManager::allocate(): found run of 8 bits at 6
insertNode(): moving right
insertNode(): moving right
insertNode(): moving right
insertNode(): moving right
insertNode(): inserting 5374060
MemoryManager::allocate(): address=5374060
----------------------------------------------
byte[0]=0
00000000
byte[1]=c0
00000011
byte[2]=ff
11111111
-----------------------------------------------
----(5374060)
---(5374044)
--(5373996)
-(5373980)
(5373964)
----------------------------------------------
MemoryManager::allocate(): request 50 bytes
MemoryManager::allocate(): run_bits=4
MemoryManager::allocate(): found run of 4 bits at 14
insertNode(): moving right
insertNode(): moving right
insertNode(): moving right
insertNode(): moving right
insertNode(): moving right
insertNode(): inserting 5374188
MemoryManager::allocate(): address=5374188<a name="476"></a><a name="IDX-245"></a>
----------------------------------------------
byte[0]=0
00000000
byte[1]=0
00000000
byte[2]=fc
00111111
-----------------------------------------------
-----(5374188)
----(5374060)
---(5374044)
--(5373996)
-(5373980)
(5373964)
----------------------------------------------
MemoryManager::release(): address=5373964
deleteNode(): freeing 5373964
----------------------------------------------
byte[0]=1
10000000
byte[1]=0
00000000
byte[2]=fc
00111111
----------------------------------------------
----(5374188)
---(5374060)
--(5374044)
-(5373996)
(5373980)
----------------------------------------------
MemoryManager::release(): address=5373980
deleteNode(): freeing 5373980
----------------------------------------------
byte[0]=3
11000000
byte[1]=0
00000000
byte[2]=fc
00111111
----------------------------------------------
---(5374188)
--(5374060)
-(5374044)
(5373996)
----------------------------------------------
MemoryManager::release(): address=5373996
deleteNode(): freeing 5373996
----------------------------------------------
byte[0]=1f
11111000<a name="477"></a><a name="IDX-246"></a>
byte[1]=0
00000000
byte[2]=fc
00111111
----------------------------------------------
--(5374188)
-(5374060)
(5374044)
----------------------------------------------
MemoryManager::release(): address=5374044
deleteNode(): freeing 5374044
----------------------------------------------
byte[0]=3f
11111100
byte[1]=0
00000000
byte[2]=fc
00111111
----------------------------------------------
-(5374188)
(5374060)
----------------------------------------------
MemoryManager::release(): address=5374060
deleteNode(): freeing 5374060
----------------------------------------------
byte[0]=ff
11111111
byte[1]=3f
11111100
byte[2]=fc
00111111
----------------------------------------------
(5374188)
----------------------------------------------
MemoryManager::release(): address=5374188
deleteNode(): freeing 5374188
----------------------------------------------
byte[0]=ff
11111111
byte[1]=ff
11111111
byte[2]=ff
11111111
-----------------------------------------------
-----------------------------------------------
BitMap::~BitMap(): freeing map[3]
MemoryManager::~MemoryManager():free() mem[384]
</pre>
</div>
<p class="para">The performance test was nowhere near as extended with regard to the output that it produced. This was primarily because all the <a name="478"></a><a name="IDX-247"></a>debug <span class="fixed">printf()</span> statements had been precluded from the build. Here is the output generated by the performance test build:</p>
<div class="informalexample">
<pre class="literallayout">
BitMap::BitMap(): nbytes=8193, nbits=65544
MemoryManager::MemoryManager():mallloc() mem[1048704]
PerformanceTest::runTest(): time whistle blown
PerformanceTest::runTest(): race has ended
BitMap::~BitMap(): freeing map[8193]
MemoryManager::~MemoryManager():free() mem[1048704]
msecs=856
</pre>
</div>
<p class="last-para">The most important value is located on the last line of the output. The bitmapped memory manager took 856 milliseconds to allocate and free 1024 regions of memory. This will not mean much until we look at the other memory managers.</p>
<a></a>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="479"></a><a name="ch04lev2sec6"></a>Trade-Offs</h3>
<p class="first-para">Bit mapped memory managers have the benefit of providing a straightforward way to organize memory that, depending on the bit-to-memory ratio, can minimize internal fragmentation. Many early operating systems used bit maps to help manage memory because bit maps are fixed in size and thus can be placed outside of the chaos of the kernel's dynamic memory pools. For example, if each bit in a bit map represents 16 bytes of memory, a 512KB bit map will be needed to manage 64MB of memory. Although this doesn't include the storage needed for the associated BST, you can see that the overhead isn't that bad.</p>
<p class="para">On the other hand, finding a run of free bits in a bit map means that you may have to traverse the entire set of bits to find what you are looking for (assuming that you do find it). This mandatory searching makes allocation very expensive in terms of execution time.</p>
<p class="para">If I had to improve this code, I would replace the binary search tree with a tree data structure that is guarant