lib0045.html

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

struct MemHandle
{
    unsigned long value;
    void *ptr;
};
</pre>
</div>
<p class="para">This would allow you to change the address of a memory block (i.e., <span class="fixed">void *ptr</span>) without having to change the value stored by pointers in the application (i.e., <span class="fixed">unsigned long value</span>). When an address change does occur, all you need to update is a single <span class="fixed">MemHandle</span> structure instead of potentially dozens of application variables. This type of relationship is displayed in <a class="internaljump" href="#ch05fig13">Figure 5.13</a>.</p>
<div class="figure">
<a name="624"></a><a name="ch05fig13"></a><span class="figuremediaobject"><a href="images/fig364%5F01%5F0%2Ejpg" NAME="IMG_93" target="_parent"><img src="images/fig364_01.jpg" height="163" width="329" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 5.13</span></span>
</div>
<p class="para">For example, consider the following code:</p>
<div class="informalexample">
<pre class="literallayout">
void *ptr1;
ptr1  = newMalloc(20);  //assume returns handle value=55
printf("%lu\n",ptr);    //prints out 55
forceCollection();      //memory blocks may shift
printf("%lu\n",ptr);    //still prints out 55
</pre>
</div>
<p class="para">When I initially call <span class="fixed">newmalloc()</span>, the value stored in <span class="fixed">ptr1</span> is a handle value instead of an actual address. When I call <span class="fixed">forceCollection()</span> to initiate garbage collection, memory blocks in the heap may end up being rearranged. However, the handle value will not change, even if its associated address does.</p>
<p class="para">Some garbage collectors use handles in conjunction with a stack allocation scheme. Memory is allocated in a fashion similar to a stack. There is a pointer (<span class="fixed">SP</span>) that keeps track of the top of the stack. Allocation requests cause the stack pointer to increment. This is a very fast scheme in practice (even faster than the segregated list approach).</p>
<a name="625"></a><a name="IDX-337"></a>
<p class="para">When the stack hits its limit, the garbage collector kicks in and reclaims garbage. To minimize fragmentation, the occupied blocks are all shifted down to the bottom of the heap. Because handles are being used instead of actual pointers, all the collector has to do when it makes this shift is update all the handles. The application variables can remain untouched.</p>
<p class="para">This process is illustrated in <a class="internaljump" href="#ch05fig14">Figure 5.14</a>.</p>
<div class="figure">
<a name="626"></a><a name="ch05fig14"></a><span class="figuremediaobject"><a href="images/fig365%5F01%5F0%2Ejpg" NAME="IMG_94" target="_parent"><img src="images/fig365_01.jpg" height="230" width="329" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 5.14</span></span>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="627"></a><a name="ch05lev2sec12"></a>Real-Time Behavior</h3>
<p class="first-para">With my mark-sweep collector, there was a noticeable decrease in execution time when the frequency of garbage collection was decreased. This might lead you to think that the best way to speed up a garbage collector is to delay collection until the last possible moment. As it turns out, this approach isn't a good idea because it can force a garbage collector to perform reclamation when the application urgently needs allocation the most. A memory-starved application can be forced to wait for storage space, which it desperately needs, while the garbage collector chugs away.</p>
<p class="para">At the other end of the spectrum, there is the idea that you could speed a garbage collector up by allowing it to do a small amount of work during each allocation. This tactic is known as <i class="emphasis">incremental garbage collection,</i> and you got a taste of it when you observed the reference counting collector.</p>
<a name="628"></a><a name="IDX-338"></a>
<p class="para">Incremental garbage collection works very nicely in practice because the constant heap maintenance that an incremental manager performs provides enough breathing room for requests to be satisfied in real time.</p>
<p class="para">I like to think of garbage collection as the inspection of a Marine Corps barracks at Parris Island. If you wait until the last minute to clean things up, break out some jelly because you are toast. The drill instructor is going to come storming in and read you the riot act for all of the details that you couldn't possibly have attended to in the 30 minutes you had to get your bunk in order. On the other hand, if you constantly keep your area neat and clean, it will be much easier to deal with the drill instructor when he arrives.</p>
<p class="last-para">Garbage collection is the same way. Demanding allocations tend to occur when the memory manager can least afford to service them. It is Murphy's Law, plain and simple. By keeping the heap relatively organized at all times, those expensive allocation requests will not hurt as much. It will also allow the memory manager to guarantee service pauses within a certain time range.</p>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="629"></a><a name="ch05lev2sec13"></a>Life Span Characteristics</h3>
<p class="first-para">Most applications have a set of objects that exist for the life span of an application and another set of temporal objects that blink in and out of existence. It makes sense, then, to have different storage areas and algorithms to deal with memory blocks that have different life spans. This tactic is known as <i class="emphasis">generational garbage collection</i>.</p>
<p class="para">A generational memory manager breaks the heap into regions based on life span, known as <i class="emphasis">generations</i> (see <a class="internaljump" href="#ch05fig15">Figure 5.15</a>). The memory manager begins by allocating memory from the youngest generation.</p>
<div class="figure">
<a name="630"></a><a name="ch05fig15"></a><span class="figuremediaobject"><a href="images/fig367%5F01%5F0%2Ejpg" NAME="IMG_95" target="_parent"><img src="images/fig367_01.jpg" height="336" 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.15</span></span>
</div>
<p class="para">When the youngest generation is exhausted, the memory manager will initiate garbage collection. Those memory blocks that survive collection over the course of several iterations will be moved to the next older generation. As this process continues, the memory blocks that survive will be filtered up to the older generations. Each time a generation's storage space is exhausted, the memory manager will garbage collect that generation and all the younger generations.</p>
<p class="para">Most of the garbage collection and allocation activity ends up occurring in the younger storage areas of the heap. This leaves the older memory blocks in relative tranquility. It's like a college physics department: The young guys do all the work, and the old guys hang out and polish their awards.</p>
<a name="631"></a><a name="IDX-339"></a>
<p class="last-para">This means that because activity in the older generations is limited, slower algorithms that waste less memory can be used to track memory blocks in the older generations. On the other hand, speed should be the determining factor when choosing an algorithm to allocate and track memory in the younger generations.</p>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="632"></a><a name="ch05lev2sec14"></a>Multithreaded Support</h3>
<p class="first-para">All the implementations presented in this book have been single-threaded; this was a conscious decision on my part in order to keep things simple so that you could focus on the main ideas. The handicap of using a single-threaded garbage collection scheme is that reclamation is done on the critical path of execution.</p>
<p class="para">I think that most garbage collection implementations assume a multithreaded environment where there will be plenty of CPU cycles off the critical path. This allows the garbage collector to supposedly do its thing as a background thread while the rest of the program chugs merrily along. If you are interested in building a commercial-quality garbage collector, I would recommend that you consider a multithreaded approach.</p>
<p class="para">There are two sides to every coin; such is the case with using threads. The first sacrifice you will typically make is portability. Every vendor seems to supply their own specially tweaked version, and you can expect to dedicate a significant portion of your development time porting your code to work on different operating systems.</p>
<a name="633"></a><a name="IDX-340"></a>
<p class="para">Another pitfall of using threads is that it does not necessarily guarantee high performance. For example, let us assume you have a thread-enabled operating system that can perform thread switches at the kernel level so that each process table entry has fields to support one or more threads. Let us also assume that there are 100 processes running, and each process has five active threads (see <a class="internaljump" href="#ch05fig16">Figure 5.16</a>).</p>
<div class="figure">
<a name="634"></a><a name="ch05fig16"></a><span class="figuremediaobject"><a href="images/fig368%5F01%5F0%2Ejpg" NAME="IMG_96" target="_parent"><img src="images/fig368_01.jpg" height="198" 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.16</span></span>
</div>
<p class="para">This places us in a situation where there are 500 distinct executing threads. Now imagine an operating system, which is not thread-enabled, that just has 100 running processes. On the thread-enabled operating system, a thread will have to potentially wait in line behind 499 other threads before it gets its chance to execute. On the thread-disabled machine, a process only has to share the processor with 99 other tasks, and each execution path will get a larger share of the processor's attention.</p>
<p class="para">Is the thread-enabled system necessarily faster, or does it just give a programmer the ability to load down the operating system so that each thread actually gets less processor time?</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&nbsp;</td><td valign="top" class="admon-body">
<p class="first-para">I will admit that this is a somewhat stilted scenario. A fair comparison would be to compare an operating system scheduling 500 threads against an operating system scheduling 500 single-threaded tasks. In this scenario, the thread-enabled operating system would offer better performance.</p>
</td>
</tr>
</table>
<p class="para">My point is not that multithreading hurts performance. In fact, using threads can usually boost performance due to the lower relative overhead of the associated context switch. My point is that multithreading does not <i class="emphasis">guarantee</i> high performance (ha ha &mdash; always read the fine print). In a production environment, actual <a name="635"></a><a name="IDX-341"></a>performance often has more to do with the hardware that an application is deployed on and the current load of tasks that the kernel is servicing than the architecture of a particular application. Performance has many independent variables, and an application's thread model is just one of those variables.</p>
<a name="636"></a><a name="IDX-342"></a>
<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="LiB0044.html"><img src="images/previous.gif" width="62" height="15" border="0" align="absmiddle" alt="Previous Section"></a>
<a href="LiB0046.html"><img src="images/next.gif" width="41" height="15" border="0" align="absmiddle" alt="Next Section"></a>
</div></td></tr>
</table>
</body>
</html>