📄 lib0039.html
字号:
<html>
<META http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>malloc() Version 3: Segregated Lists</title>
<link rel="STYLESHEET" type="text/css" href="images/xpolecat.css">
<link rel="STYLESHEET" type="text/css" href="images/ie.content.books24x7.css">
</head>
<body >
<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>
<div class="chapter">
<a name="ch04"></a>
<div class="section">
<h2 class="first-section-title"><a name="509"></a><a name="ch04lev1sec8"></a><span class="fixed">malloc()</span> Version 3: Segregated Lists</h2><div class="section">
<h3 class="sect3-title">
<a name="510"></a><a name="ch04lev2sec11"></a>Theory</h3>
<p class="first-para">With the sequential fit approach, we spent a lot of effort in terms of splitting and merging blocks of memory. The segregated lists approach attempts to sidestep this problem by keeping several lists of fixed-sized memory blocks. In other words, the heap storage is segregated into groups of blocks based on their size. If you need a 32-byte block, query the appropriate list for free space instead of traversing the entire heap.</p>
<p class="para">In my segregated list implementation, I break memory into 6,136-byte rows, where each row consists of eight different blocks of memory. This is illustrated in <a class="internaljump" href="#ch04fig12">Figure 4.12</a>. The size of the first element in each row is 16 bytes, and the size of the last element in each row is 4,096 bytes.</p>
<div class="figure">
<a name="511"></a><a name="ch04fig12"></a><span class="figuremediaobject"><a href="images/fig293%5F01%5F0%2Ejpg" NAME="IMG_79" target="_parent"><img src="images/fig293_01.jpg" height="238" 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.12</span></span>
</div>
<a name="512"></a><a name="IDX-266"></a>
<p class="para">Because the list elements are fixed in size, and their positions are known, we do not need the <span class="fixed">PREVIOUS</span>, <span class="fixed">FREE</span>, and <span class="fixed">SIZE</span> header fields that were used in the sequential fit scheme. However, we do need the <span class="fixed">STATE</span> header field. This causes every plot of real estate in memory to be prefixed by a header that is a single byte in size.</p>
<p class="para">Each 6,136-byte row of memory contains eight memory blocks that increase in size (see <a class="internaljump" href="#ch04fig13">Figure 4.13</a>). Given that rows are stacked on top of each other in memory, as displayed in <a class="internaljump" href="#ch04fig12">Figure 4.12</a>, to get to the next element of a specific size, take the index of a given element and add 6,136 to it.</p>
<div class="figure">
<a name="513"></a><a name="ch04fig13"></a><span class="figuremediaobject"><a href="images/fig294%5F01%5F0%2Ejpg" NAME="IMG_80" target="_parent"><img src="images/fig294_01.jpg" height="191" width="290" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 4.13</span></span>
</div>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="514"></a><a name="ch04lev2sec12"></a>Implementation</h3>
<p class="first-para">The implementation of the segregated memory manager closely mirrors the implementation of the sequential fit manager:</p>
<a name="515"></a><a name="ch04table04"></a>
<table class="table" border="1">
<caption class="table-title">
<span class="table-title"><span class="table-titlelabel">Table 4.4</span></span>
</caption>
<thead>
<tr valign="top">
<th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">File</b>
</p>
</th><th class="th" scope="col" align="left">
<p class="table-para">
<b class="bold">Use</b>
</p>
</th>
</tr>
</thead>
<tbody>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">driver.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">contains <span class="fixed">main()</span>, is the scene of the crime</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">mallocV3.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">
<span class="fixed">newMalloc()</span>, <span class="fixed">newFree()</span> wrappers (3rd version)</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">perform.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">implements the <span class="fixed">PerformanceTest</span> class</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">memmgr.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">implements the <span class="fixed">SegregatedMemoryManager</span> class</p>
</td>
</tr>
</tbody>
</table>
<p class="para">The only files that I had to modify were the <span class="fixed">mallocV3.cpp</span> file and the <span class="fixed">memmgr.cpp</span> file.</p>
<a name="516"></a><a name="IDX-267"></a>
<div class="section">
<h4 class="sect4-title">memmgr.cpp</h4>
<p class="first-para">The majority of the real work is performed by the class defined in this file. The <span class="fixed">SegregatedMemoryManager</span> class takes care of allocating heap storage from Windows and managing it. The allocation function uses a helper function to search through the free lists. The release function does everything by itself.</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#ifdef DEBUG_SL_MEM_MGR</span>
<span style="background-color:d9d9d9">#define MSG0(arg); printf(arg);</span>
<span style="background-color:d9d9d9">#define MSG1(arg1,arg2); printf(arg1,arg2);</span>
<span style="background-color:d9d9d9">#else</span>
<span style="background-color:d9d9d9">#define MSG0(arg);</span>
<span style="background-color:d9d9d9">#define MSG1(arg1,arg2);</span>
<span style="background-color:d9d9d9">#endif</span>
<span style="background-color:d9d9d9">#define U1 unsigned char</span>
<span style="background-color:d9d9d9">#define U4 unsigned long</span>
<span style="background-color:d9d9d9">/*</span>
<span style="background-color:d9d9d9">list element format</span>
<span style="background-color:d9d9d9">|0| |1 .. n|</span>
<span style="background-color:d9d9d9">[STATE][payload]</span>
<span style="background-color:d9d9d9">U1 ?</span>
<span style="background-color:d9d9d9">byte allocated/freed is address of first byte of payload</span>
<span style="background-color:d9d9d9">header = 1 bytes</span>
<span style="background-color:d9d9d9">*/</span>
<span style="background-color:d9d9d9">#define STATE(i) (*((U1*)(&ram[i-1]))) /*FREE,OCCUPIED*/</span>
<span style="background-color:d9d9d9">#define FREE 0</span>
<span style="background-color:d9d9d9">#define OCCUPIED 1</span>
<span style="background-color:d9d9d9">char *stateStr[3]={"FREE","OCCUPIED"};</span>
<span style="background-color:d9d9d9">#define START16 1 /*index of first 16-byte payload*/</span>
<span style="background-color:d9d9d9">#define START32 18 /*index of first 16-byte payload*/</span>
<span style="background-color:d9d9d9">#define START64 51 /*index of first 16-byte payload*/</span>
<span style="background-color:d9d9d9">#define START128 116 /*index of first 16-byte payload*/</span>
<span style="background-color:d9d9d9">#define START256 245 /*index of first 16-byte payload*/</span>
<span style="background-color:d9d9d9">#define START512 502 /*index of first 16-byte payload*/</span>
<span style="background-color:d9d9d9">#define START1024 1015 /*index of first 16-byte payload*/</span>
<span style="background-color:d9d9d9">#define START4096 2040 /*index of first 16-byte payload*/</span>
<span style="background-color:d9d9d9">#define SZ_ROW 6136 /*size of a row of entries in table*/</span>
<span style="background-color:d9d9d9">class SegregatedMemoryManager</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">private:</span><a name="517"></a><a name="IDX-268"></a>
<span style="background-color:d9d9d9">HANDLE handle;</span>
<span style="background-color:d9d9d9">U1 *ram; /*memory storage*/</span>
<span style="background-color:d9d9d9">U4 size; /*# bytes*/</span>
<span style="background-color:d9d9d9">U4 nrows; /*# of 6136 byte rows*/</span>
<span style="background-color:d9d9d9">void initColumn(U4 index);</span>
<span style="background-color:d9d9d9">U4 searchColumn(U4 index);</span>
<span style="background-color:d9d9d9">void printColumn(U4 index);</span>
<span style="background-color:d9d9d9">public:</span>
<span style="background-color:d9d9d9">SegregatedMemoryManager(U4 nbytes);</span>
<span style="background-color:d9d9d9">~SegregatedMemoryManager();</span>
<span style="background-color:d9d9d9">void*allocate(U4 nbytes);</span>
<span style="background-color:d9d9d9">void release(void* addr);</span>
<span style="background-color:d9d9d9">void printState();</span>
<span style="background-color:d9d9d9">};</span>
<span style="background-color:d9d9d9">SegregatedMemoryManager::SegregatedMemoryManager(U4 nbytes)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">handle = GetProcessHeap();</span>
<span style="background-color:d9d9d9">if(handle==NULL)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">printf("SegregatedMemoryManager::");</span>
<span style="background-color:d9d9d9">printf("SegregatedMemoryManager():");</span>
<span style="background-color:d9d9d9">printf("invalid handle\n");</span>
<span style="background-color:d9d9d9">exit (1);</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">ram = (U1*)HeapAlloc(handle,HEAP_ZERO_MEMORY,nbytes);</span>
<span style="background-color:d9d9d9">//for portability, you could use:</span>
<span style="background-color:d9d9d9">//ram = (unsigned char*)malloc(nbytes);</span>
<span style="background-color:d9d9d9">size = nbytes;</span>
<span style="background-color:d9d9d9">if(size<SZ_ROW)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">printf("SegregatedMemoryManager::");</span>
<span style="background-color:d9d9d9">printf("SegregatedMemoryManager():");</span>
<span style="background-color:d9d9d9">printf("not enough memory fed to constructor\n");</span>
<span style="background-color:d9d9d9">exit (1);</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">nrows = size/SZ_ROW;</span>
<span style="background-color:d9d9d9">initColumn(START16);</span>
<span style="background-color:d9d9d9">initColumn(START32);</span>
<span style="background-color:d9d9d9">initColumn(START64);</span><a name="518"></a><a name="IDX-269"></a>
<span style="background-color:d9d9d9">initColumn(START128);</span>
<span style="background-color:d9d9d9">initColumn(START256);</span>
<span style="background-color:d9d9d9">initColumn(START512);</span>
<span style="background-color:d9d9d9">initColumn(START1024);</span>
<span style="background-color:d9d9d9">initColumn(START4096);</span>
<span style="background-color:d9d9d9">MSG0("SegregatedMemoryManager::");</span>
<span style="background-color:d9d9d9">MSG1("SegregatedMemoryManager(%lu)\n",nbytes);</span>
<span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}/*end constructor---------------------------------------*/</span>
<span style="background-color:d9d9d9">void SegregatedMemoryManager::initColumn(U4 index)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">U4 i;</span>
<span style="background-color:d9d9d9">for(i=0;i<nrows;i++)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">STATE(index)=FREE;</span>
<span style="background-color:d9d9d9">index = index + SZ_ROW;</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}/*end initColumn---------------------------------------*/</span>
<span style="background-color:d9d9d9">SegregatedMemoryManager::~SegregatedMemoryManager()</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">if(HeapFree(handle,HEAP_NO_SERIALIZE,ram)==0)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">printf("SegregatedMemoryManager::");</span>
<span style="background-color:d9d9d9">printf("~SegregatedMemoryManager():");</span>
<span style="background-color:d9d9d9">printf("could not free heap storage\n");</span>
<span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">//for portability, you could use:</span>
<span style="background-color:d9d9d9">//free(ram);</span>
<span style="background-color:d9d9d9">MSG0("SegregatedMemoryManager::");</span>
<span style="background-color:d9d9d9">MSG0("~SegregatedFitMemoryManager()");</span>
<span style="background-color:d9d9d9">MSG1("free ram[%lu]\n",size);</span>
<span style="background-color:d9d9d9">return;</span>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -