📄 lib0038.html
字号:
<html>
<META http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>malloc() Version 2: Sequential Fit</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="LiB0037.html"><img src="images/previous.gif" width="62" height="15" border="0" align="absmiddle" alt="Previous Section"></a>
<a href="LiB0039.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="481"></a><a name="ch04lev1sec7"></a><span class="fixed">malloc()</span> Version 2: Sequential Fit</h2><p class="first-para">Back in the early 1990s, I was experimenting with DOS in an effort to see how <span class="fixed">malloc()</span> and <span class="fixed">free()</span> were implemented by Borland's Turbo C libraries.</p>
<p class="para">Here is the program that I used:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#include<stdio.h></span>
<span style="background-color:d9d9d9">#include<stdlib.h></span>
<span style="background-color:d9d9d9">void main()</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">void *ptr[5];</span>
<span style="background-color:d9d9d9">int i;</span>
<span style="background-color:d9d9d9">for(i=0;i<5;i++)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">ptr[i]=malloc(32);</span>
<span style="background-color:d9d9d9">printf("%p\n",ptr [i]);</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">for(i=0;i<5;i++)</span>
<span style="background-color:d9d9d9">{</span>
<span style="background-color:d9d9d9">free(ptr[i]);</span>
<span style="background-color:d9d9d9">}</span>
<span style="background-color:d9d9d9">return;</span>
<span style="background-color:d9d9d9">}</span>
</pre>
</div>
<p class="para">I compiled this using the following command line: <span class="fixed">C:\dos> tcc-mh dmalloc.c</span>.</p>
<p class="para">I specified a "huge" memory model (via the <span class="fixed">-mh</span> option) so that addresses would be specified in the <span class="fixed">segment:offset</span> real mode format.</p>
<p class="para">This program produced the following output while running on DOS:</p>
<div class="informalexample">
<pre class="literallayout">
193B:0004 ( physical address 193B4 )
193E:0004 ( physical address 193E4 )
1941:0004 ( physical address 19414 )
1944:0004 ( physical address 19444 )
1947:0004 ( physical address 19474 )
</pre>
</div>
<p class="para">As you can see, the libraries give each allocation its own 48-bit block. It is more than likely that the extra 16 bytes is used by the <a name="482"></a><a name="IDX-249"></a>Turbo C <span class="fixed">malloc()</span> and <span class="fixed">free()</span> libraries to link the regions of memory together into a linked list. This is a key feature of the sequential fit approach to memory management.</p>
<div class="section">
<h3 class="sect3-title">
<a name="483"></a><a name="ch04lev2sec7"></a>Theory</h3>
<p class="first-para">The sequential fit technique organizes memory into a linear linked list of free and reserved regions (see <a class="internaljump" href="#ch04fig07">Figure 4.7</a>). When an allocation request occurs, the memory manager moves sequentially through the list until it finds a free block of memory that can service/fit the request (hence the name "sequential fit").</p>
<div class="figure">
<a name="484"></a><a name="ch04fig07"></a><span class="figuremediaobject"><a href="images/fig277%5F01%5F0%2Ejpg" NAME="IMG_74" target="_parent"><img src="images/fig277_01.jpg" height="102" width="286" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 4.7</span></span>
</div>
<p class="para">Typically, an external data structure is not needed because portions of the allocated memory are reserved so that the memory being managed can index itself. Logically, the blocks of memory are arranged as in <a class="internaljump" href="#ch04fig07">Figure 4.7</a>. However, the actual organization of each block, be it free or reserved, in my implementation is specified by <a class="internaljump" href="#ch04fig08">Figure 4.8</a>.</p>
<div class="figure">
<a name="485"></a><a name="ch04fig08"></a><span class="figuremediaobject"><a href="images/fig277%5F02%5F0%2Ejpg" NAME="IMG_75" target="_parent"><img src="images/fig277_02.jpg" height="177" 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.8</span></span>
</div>
<a name="486"></a><a name="IDX-250"></a>
<p class="para">The scheme for allocation is pretty simple; the memory manager simply traverses the linked list of memory blocks until it reaches a free block that is big enough to satisfy the request. If the free block is much larger than the memory request, it will split the free block into two pieces. One part of the split block will be used to service the request, and the other part will remain free to service other requests for memory (see <a class="internaljump" href="#ch04fig09">Figure 4.9</a>).</p>
<div class="figure">
<a name="487"></a><a name="ch04fig09"></a><span class="figuremediaobject"><a href="images/fig278%5F01%5F0%2Ejpg" NAME="IMG_76" target="_parent"><img src="images/fig278_01.jpg" height="37" 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.9</span></span>
</div>
<p class="para">The algorithm for releasing blocks of memory requires adjacent blocks of free memory to be merged. This is where the real work occurs. For a block situated between two other blocks, there are basically four different scenarios that are possible (see <a class="internaljump" href="#ch04fig10">Figure 4.10</a>).</p>
<div class="figure">
<a name="488"></a><a name="ch04fig10"></a><span class="figuremediaobject"><a href="images/fig278%5F02%5F0%2Ejpg" NAME="IMG_77" target="_parent"><img src="images/fig278_02.jpg" height="197" 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.10</span></span>
</div>
<p class="para">The trick is to be able to reassign the <span class="fixed">NEXT</span> and <span class="fixed">PREVIOUS</span> pointers, shown in <a class="internaljump" href="#ch04fig07">Figure 4.7</a>, correctly. If both blocks on either side of a freed block are occupied, no pointer manipulation needs to be performed. However, if one or both of the adjacent blocks is free, blocks of memory will need to be merged.</p>
<p class="para">The best way to understand this is visually. <a class="internaljump" href="#ch04fig11">Figure 4.11</a> shows an example of the pointer manipulation that needs to be performed in order to merge two adjacent blocks.</p>
<div class="figure">
<a name="489"></a><a name="ch04fig11"></a><span class="figuremediaobject"><a href="images/fig279%5F01%5F0%2Ejpg" NAME="IMG_78" target="_parent"><img src="images/fig279_01.jpg" height="191" width="297" alt="Click To expand" border="0"></a></span>
<br style="line-height: 1">
<span class="figure-title"><span class="figure-titlelabel">Figure 4.11</span></span>
</div>
<a name="490"></a><a name="IDX-251"></a>
<p class="last-para">For a rigorous explanation of how memory block merging works, read the source code of the <span class="fixed">SequentialFitMemoryManager</span> class.</p>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="491"></a><a name="ch04lev2sec8"></a>Implementation</h3>
<p class="first-para">Because storage space in the heap is used to help organize heap memory, the sequential fit memory manager implementation is not as prolific as the bit map-based manager. My implementation requires only four files:</p>
<a name="492"></a><a name="ch04table03"></a>
<table class="table" border="1">
<caption class="table-title">
<span class="table-title"><span class="table-titlelabel">Table 4.3</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">mallocV2.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">
<span class="fixed">newMalloc(), newFree()</span> wrappers (2nd 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">SequentialFitMemoryManager</span> class</p>
</td>
</tr>
</tbody>
</table>
<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">SequentialFitMemoryManager</span> class takes care of allocating heap storage from Windows and managing it. Both the allocation and release functions have secondary private helper routines. The allocation function uses a helper function to split free blocks. The release function calls a helper function to perform the actual merging of free memory blocks.</p>
<a name="493"></a><a name="IDX-252"></a>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">#ifdef DEBUG_SF_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 3||4 7|| 8 ||9 12||13 .. n|</span>
<span style="background-color:d9d9d9">[PREV][NEXT][STATE][SIZE][payload]</span>
<span style="background-color:d9d9d9">U4 U4 U1 U4 ?</span>
<span style="background-color:d9d9d9">byte allocated/freed is address of first byte of payload</span>
<span style="background-color:d9d9d9">header = 13 bytes</span>
<span style="background-color:d9d9d9">byte[0] is occupied by header data, so is always used, thus</span>
<span style="background-color:d9d9d9">first link has prev=0 ( 0 indicates not used )</span>
<span style="background-color:d9d9d9">last link has next=0</span>
<span style="background-color:d9d9d9">*/</span>
<span style="background-color:d9d9d9">#define PREV(i) (*((U4*)(&ram[i-13])))</span>
<span style="background-color:d9d9d9">#define NEXT(i) (*((U4*)(&ram[i-9])))</span>
<span style="background-color:d9d9d9">#define STATE(i) (*((U1*)(&ram[i-5]))) /*FREE,OCCUPIED*/</span>
<span style="background-color:d9d9d9">#define SIZE(i) (*((U4*)(&ram[i-4])))</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 START 13 /*address of first payload*/</span>
<span style="background-color:d9d9d9">#define SZ_HEADER 13</span>
<span style="background-color:d9d9d9">class SequentialFitMemoryManager</span>
<span style="background-color:d9d9d9">{</span>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -