lib0035.html

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

</div>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note&nbsp;</td><td valign="top" class="admon-body">
<p class="first-para">Another problem with both of the previous examples is that memory is released in the exact order in which it is allocated. It would be a bad move to assume that this type of behavior could be expected.</p>
</td>
</tr>
</table>
<p class="para">High-grade memory managers usually try to take advantage of regularities that exist in executing programs. If there are patterns, special steps can be instituted to exploit those patterns and benefit overall performance. Random data destroys regularity. This can lead to incorrect performance evaluations because a memory manager that does successfully take advantage of regularities will not be able to flex its muscles. On the same note, a memory manager that does a poor job of exploiting patterns will be able to hide its weakness behind the random allocation stream.</p>
<a name="438"></a><a name="IDX-217"></a>
<p class="para">This leads me to a dilemma. I cannot use a series of fixed-sized memory block requests, and I cannot use a random stream of allocation requests. I need to create a synthetic stream of allocation requests and release requests that are reasonably random but still exhibit a basic element of regularity. The caveat is that, although programs can demonstrate regular behavior, there are an infinite number of programs that a manual memory manager might confront. What type of allocation behavior is the most likely?</p>
<p class="para">This is where I threw my hands up and decided to use a stream of allocation requests that followed a specific discrete probability distribution. This allowed me to weight certain types of memory requests, although it also forced me to decide on a certain type of allocation behavior (i.e., one that might not be realistic).</p>
<p class="para">I decided to use the following discrete probability distribution to model allocation requests:</p>
<a name="439"></a><a name="ch04table01"></a>
<table class="table" border="1">
<caption class="table-title">
<span class="table-title"><span class="table-titlelabel">Table 4.1</span></span>
</caption>
<thead>
<tr valign="top">
<th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">(x) Size of Allocation in Bytes</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">(P(x)) Probability</b>
</p>
</th>
</tr>
</thead>
<tbody>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">16</p>
</td><td class="td" align="left">
<p class="table-para">.15 = p<sub>1</sub>
</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">32</p>
</td><td class="td" align="left">
<p class="table-para">.20 = p<sub>2</sub>
</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">64</p>
</td><td class="td" align="left">
<p class="table-para">.35 = p<sub>3</sub>
</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">128</p>
</td><td class="td" align="left">
<p class="table-para">.20 = p<sub>4</sub>
</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">256</p>
</td><td class="td" align="left">
<p class="table-para">.02 = p<sub>5</sub>
</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">512</p>
</td><td class="td" align="left">
<p class="table-para">.04 = p<sub>6</sub>
</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">1024</p>
</td><td class="td" align="left">
<p class="table-para">.02 = p<sub>7</sub>
</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">4096</p>
</td><td class="td" align="left">
<p class="table-para">.02 = p<sub>8</sub>
</p>
</td>
</tr>
</tbody>
</table>
<p class="para">Visually, this looks like what is displayed in <a class="internaljump" href="#ch04fig04">Figure 4.4</a>.</p>
<div class="figure">
<a name="440"></a><a name="ch04fig04"></a><span class="figuremediaobject"><a href="images/fig245%5F01%5F0%2Ejpg" NAME="IMG_71" target="_parent"><img src="images/fig245_01.jpg" height="209" width="350" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 4.4</span></span>
</div>
<p class="para">I will admit that this distribution is somewhat arbitrary. To actually generate random numbers that obey this distribution, I use an <a name="441"></a><a name="IDX-218"></a>algorithm that is based on what is known as the <i class="emphasis">inverse transform method</i>.</p>
<ol class="orderedlist">
<li class="first-listitem">
<p class="first-para">Generate a uniform random number, <span class="fixed">U</span>, between 0 and 1.</p>
</li>
<li class="listitem">
<p class="first-para">If <span class="fixed">U</span> &lt; p<sub>1</sub> = .15, set allocation to 16 bytes and go to step 10.</p>
</li>
<li class="listitem">
<p class="first-para">If <span class="fixed">U</span> &lt; p<sub>1</sub>+p<sub>2</sub> = .35, set allocation to 32 bytes and go to step 10.</p>
</li>
<li class="listitem">
<p class="first-para">If <span class="fixed">U</span> &lt; p<sub>1</sub>+p<sub>2</sub>+p<sub>3</sub> = .70, set allocation to 64 bytes and go to step 10.</p>
</li>
<li class="listitem">
<p class="first-para">If <span class="fixed">U</span> &lt; p<sub>1</sub>+p<sub>2</sub>+p<sub>3</sub>+p<sub>4</sub> = .90, set allocation to 128 bytes and go to step 10.</p>
</li>
<li class="listitem">
<p class="first-para">If <span class="fixed">U</span> &lt; p<sub>1</sub>+p<sub>2</sub>+p<sub>3</sub>+p<sub>4</sub>+p<sub>5</sub> = .92, set allocation to 256 bytes and go to step 10.</p>
</li>
<li class="listitem">
<p class="first-para">If <span class="fixed">U</span> &lt; p<sub>1</sub>+p<sub>2</sub>+p<sub>3</sub>+p<sub>4</sub>+p<sub>5</sub>+p<sub>6</sub> = .96, set allocation to 512 bytes and go to step 10.</p>
</li>
<li class="listitem">
<p class="first-para">If <span class="fixed">U</span> &lt; p<sub>1</sub>+p<sub>2</sub>+p<sub>3</sub>+p<sub>4</sub>+p<sub>5</sub>+p<sub>6</sub>+p<sub>7</sub> = .98, set allocation to 1024 bytes and go to step 10.</p>
</li>
<li class="listitem">
<p class="first-para">Set allocation to 4096 bytes and go to step 10.</p>
</li>
<li class="listitem">
<p class="first-para">Stop.</p>
</li>
</ol>
<p class="para">This algorithm is based on being able to generate a uniform random number between 0 and 1. In other words, I must be able to generate a random number that is equally likely to be anywhere between 0 and 1. To do this, I use the following function:</p>
<div class="informalexample">
<pre class="literallayout">
double getU()
{
    return(((double)rand())/((double)RAND_MAX));

}/*end getU*/
</pre>
</div>
<p class="para">This code invokes the <span class="fixed">rand()</span> function located in the C standard library. The <span class="fixed">rand()</span> function generates what is known as a <i class="emphasis">pseudorandom</i> integer in the range 0 to <span class="fixed">RAND_MAX</span>. A pseudorandom number is one that is generated by a mathematical formula. A well-known formula for creating random integer values is the Linear Congruential Generator (LCG), which makes use of a recursive relationship:</p>
<div class="informalexample">
<pre class="literallayout">
     x<sub>n+1</sub>  =   (ax<sub>n</sub>  +  b)mod m        for   n = 0, 1, 2, 3, ...
</pre>
</div>
<p class="para">For example, if we pick a=5, b=3, m=16, and x<sub>0</sub>=3, we will obtain the following stream of values:</p>
<div class="informalexample">
<pre class="literallayout">
     x<sub>0</sub> = 3, x<sub>1</sub> = 2, x<sub>2</sub> = 13, x<sub>3</sub> = 4, ...<a name="442"></a><a name="IDX-219"></a>
</pre>
</div>
<p class="para">The value x<sub>0</sub> is known as the <i class="emphasis">seed</i>. One thing you should know about LCGs is that they eventually begin to repeat themselves. In general, the constants that are chosen (i.e., a, b, and m) make the difference between a good and a bad LCG. According to Knuth, a good LCG is:</p>
<div class="informalexample">
<pre class="literallayout">
     ( 3141592653x<sub>n</sub> + 2718281829 )mod 2<sup>35</sup>     x<sub>0</sub>  = 0
</pre>
</div>
<p class="para">Because the formula allows us to determine what the next number is going to be, the numbers are not truly random. However, the formula guarantees that generated values will be evenly distributed between 0 and <span class="fixed">RAND_MAX</span>, just like a long series of values that are actually uniformly random. The fact that these formula-based numbers are not really random, in the conventional sense, is what led John Von Neumann to proclaim the following in 1951:</p>
<blockquote class="blockquote">
<p class="first-para">"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."</p>
</blockquote>
<table border="0" cellspacing="0" cellpadding="0" class="note">
<tr>
<td valign="top" class="admon-check"></td><td valign="top" class="admon-title">Note&nbsp;</td><td valign="top" class="admon-body">
<p class="first-para">The LCG technique for creating random numbers was discovered by Dick Lehmer in 1949. Lehmer was a prominent figure in the field of computational mathematics during the twentieth century. He was involved with the construction of ENIAC, the first digital computer in the United States, and was also the director of the National Bureau of Standards' Institute for Numerical Analysis.</p>
</td>
</tr>
</table>
<a></a>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="443"></a><a name="ch04lev2sec3"></a>Testing Methodology</h3>
<p class="first-para">Each memory manager that I implement will be subjected to two tests: a diagnostic test and a performance test.</p>
<p class="para">If you modify any of the source code that I provide, you may want to run the diagnostic test to make sure that everything still operates correctly. The goal of a diagnostic test is to examine the operation of a component, so it will necessarily execute much more slowly than a performance test. Once a memory manager has passed its diagnostic test, it can be barraged with a performance test.</p>
<p class="para">Performance testing will be executed by an instantiation of the <span class="fixed">PerformanceTest</span> class. The class is used as follows:</p>
<div class="informalexample">
<pre class="literallayout">
double p[8] = {.15, .20, .35, .20, .02, .04, .02, .02};
unsigned long x[8] = {16,32,64,128,256,512,1024,4096};