⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 lib0037.html

📁 Memory Management—Algorithms and implementation in C/C++ Introduction Chapter 1 - Memory Manag
💻 HTML
📖 第 1 页 / 共 5 页
字号:
🔍
12345 
<html>
<META http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<title>malloc() Version 1: Bitmapped Allocation</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="LiB0036.html"><img src="images/previous.gif" width="62" height="15" border="0" align="absmiddle" alt="Previous Section"></a>
<a href="LiB0038.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="450"></a><a name="ch04lev1sec6"></a><span class="fixed">malloc()</span> Version 1: Bitmapped Allocation</h2><div class="section">
<h3 class="sect3-title">
<a name="451"></a><a name="ch04lev2sec4"></a>Theory</h3>
<p class="first-para">The bit map approach uses an array of bits to keep track of which regions of memory are free and which regions are occupied. Memory is broken up into small plots of real estate, and each bit in the bit map represents one of these plots. This is illustrated in <a class="internaljump" href="#ch04fig05">Figure 4.5</a>.</p>
<div class="figure">
<a name="452"></a><a name="ch04fig05"></a><span class="figuremediaobject"><a href="images/fig252%5F01%5F0%2Ejpg" NAME="IMG_72" target="_parent"><img src="images/fig252_01.jpg" height="215" 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.5</span></span>
</div>
<p class="para">The problem with this approach is that the bit map does not indicate how much memory has been allocated for a given region. If you execute a command like</p>
<div class="informalexample">
<pre class="literallayout">
               my_address = malloc(55);
               free(my_address);<a name="453"></a><a name="IDX-225"></a>
</pre>
</div>
<p class="para">the bit map will not know how much storage to free because a bit map has no place to record how much storage was allocated. All a bit map can do is tell you which regions of memory are free and which are taken. When you allocate the 55 bytes above, a certain number of bits in the bit map will be cleared. However, once this happens, the bit map cannot tell who owns the region and how much memory they control.</p>
<p class="para">This means that we need to augment the bit map with another data structure that will be able to record how much memory is reserved for each allocation. I decided to use a binary search tree (BST) to serve this purpose. These two data structures &mdash; the bit map and the binary search tree &mdash; complement each other nicely. The bit map is used during the allocation phase to locate a free memory region, and the BST is used during the release phase to determine how many bits in the bit map to reset.</p>
<div class="figure">
<a name="454"></a><a name="ch04fig06"></a><span class="figuremediaobject"><a href="images/fig253%5F01%5F0%2Ejpg" NAME="IMG_73" target="_parent"><img src="images/fig253_01.jpg" height="273" 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.6</span></span>
</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">In my implementation, I used a <i class="emphasis">set</i> bit (1) to indicate a free region of memory and a <i class="emphasis">clear</i> bit (0) to indicate an occupied region of memory. The choice is arbitrary, but it is important to remember this if you are going to understand my bookkeeping.</p>
</td>
</tr>
</table>
<p class="para">The best way to prepare you to look at the source is to provide psuedocode for the core memory management algorithms:</p>
<div class="informalexample">
<pre class="literallayout">
<u class="underline">allocation: ( void * newMalloc(unsigned long size) )</u>
</pre>
</div>
<ol class="orderedlist">
<li class="first-listitem">
<p class="first-para">Translate the number of bytes requested to an equivalent number of bits in the bit map.</p>
<a name="455"></a><a name="IDX-226"></a>
</li>
<li class="listitem">
<p class="first-para">Look for a run of free bits equal to the value calculated in step 1.</p>
</li>
<li class="listitem">
<p class="first-para">If such a run exists, go to step 4; otherwise return NULL.</p>
</li>
<li class="listitem">
<p class="first-para">Clear the bits in the bit map to indicate that the associated memory is occupied.</p>
</li>
<li class="listitem">
<p class="first-para">Create a BST entry for the allocated memory and insert it into the BST.</p>
</li>
<li class="listitem">
<p class="first-para">Return the address of the first byte of the allocated memory.</p>
</li>
</ol>
<p class="para">A <i class="emphasis">run</i> of bits in the bit map is just a sequence of consecutively set or clear bits. With regard to allocation, we are interested in runs of bits that are set (i.e., set to 1).</p>
<div class="informalexample">
<pre class="literallayout">
<u class="underline">release: ( void newFree(void *addr) )</u>
</pre>
</div>
<ol class="orderedlist">
<li class="first-listitem">
<p class="first-para">Take the address supplied and use it to index an entry in the BST.</p>
</li>
<li class="listitem">
<p class="first-para">If an entry exists, then go to step 3; otherwise stop.</p>
</li>
<li class="listitem">
<p class="first-para">Use the information in the BST entry to set bits in the bit map to the "free" state.</p>
</li>
</ol>
<p class="last-para">Each BST node represents a region of allocated memory. As such, the nodes contain three vital pieces of information. They store the allocated memory's address in the heap. They also store the allocated memory's starting index in the bit map and the number of bits that are utilized in the bit map. This allows the node to take a call from a function like <span class="fixed">newFree()</span> and map the function's linear address argument to a location in the bit map.</p>
<a></a>
</div>
<div class="section">
<h3 class="sect3-title">
<a name="456"></a><a name="ch04lev2sec5"></a>Implementation</h3>
<p class="first-para">The source code implementation of the bit map memory manager is broken up into several files:</p>
<a name="457"></a><a name="ch04table02"></a>
<table class="table" border="1">
<caption class="table-title">
<span class="table-title"><span class="table-titlelabel">Table 4.2</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">mallocv1.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">
<span class="fixed">newMalloc(), newFree()</span> wrappers</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">uses <span class="fixed">bitmap.cpp</span> and <span class="fixed">tree.cpp</span> to institute a policy</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">bitmap.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">implements the bit map</p>
</td>
</tr>
<tr valign="top">
<td class="td" align="left">
<p class="table-para">
<span class="fixed">tree.cpp</span>
</p>
</td><td class="td" align="left">
<p class="table-para">implements the BST</p>
</td>
</tr>
</tbody>
</table>
<p class="para">The <span class="fixed">tree.cpp</span> and <span class="fixed">bitmap.cpp</span> files provide the mechanism side of the memory manager. These files contain fairly neutral <a name="458"></a><a name="IDX-227"></a>implementations of a BST and a bit map. The <span class="fixed">MemoryManager</span> class in <span class="fixed">memmgr.cpp</span> is what brings these two mechanisms together to institute a working policy.</p>
<div class="section">
<h4 class="sect4-title">tree.cpp</h4>
<p class="first-para">The BST implementation is fairly generic:</p>
<div class="informalexample">
<pre class="literallayout">
<span style="background-color:d9d9d9">/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span>
<span style="background-color:d9d9d9">+ declarations</span>
<span style="background-color:d9d9d9">+</span>
<span style="background-color:d9d9d9">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/</span>

<span style="background-color:d9d9d9">struct BiNode</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">unsigned long value;        //linear address</span>
    <span style="background-color:d9d9d9">unsigned long index;        //index into bitmap [0,nbits-1]</span>
    <span style="background-color:d9d9d9">unsigned long nreserved;    //number of bits reserved</span>

    <span style="background-color:d9d9d9">struct BiNode *left;</span>
    <span style="background-color:d9d9d9">struct BiNode *right;</span>
<span style="background-color:d9d9d9">};</span>

<span style="background-color:d9d9d9">class BinarySearchTree</span>
<span style="background-color:d9d9d9">{</span>
    <span style="background-color:d9d9d9">public:</span>
    <span style="background-color:d9d9d9">struct BiNode *root_ptr;</span>

    <span style="background-color:d9d9d9">void insertNode(struct BiNode **link, unsigned long val);</span>
    <span style="background-color:d9d9d9">void insertNode(struct BiNode **link, struct BiNode *ptr);</span>

    <span style="background-color:d9d9d9">struct BiNode* findNode(struct BiNode *link, unsigned</span>
                            <span style="background-color:d9d9d9">long val);</span>

    <span style="background-color:d9d9d9">struct BiNode* deleteSmallestNode(struct BiNode **link);</span>
    <span style="background-color:d9d9d9">void deleteNode(struct BiNode **link, unsigned long val);</span>
    <span style="background-color:d9d9d9">void deleteAll(struct BiNode **link);</span>

    <span style="background-color:d9d9d9">void printTree(struct BiNode *link, int level);</span>
    <span style="background-color:d9d9d9">unsigned long getHeight(struct BiNode *link);</span>
<span style="background-color:d9d9d9">};</span>

<span style="background-color:d9d9d9">/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++</span>
<span style="background-color:d9d9d9">+ definitions</span>
<span style="background-color:d9d9d9">+</span>
<span style="background-color:d9d9d9">++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/</span>

<span style="background-color:d9d9d9">/*</span>
     <span style="background-color:d9d9d9">given struct Binode **link</span><a name="459"></a><a name="IDX-228"></a>
     <span style="background-color:d9d9d9">link   = address of a variable which holds the address</span>
              <span style="background-color:d9d9d9">of the node</span>
     <span style="background-color:d9d9d9">*link = address of the node</span>
     <span style="background-color:d9d9d9">**link = node</span>
<span style="background-color:d9d9d9">*/</span>

<span style="background-color:d9d9d9">void BinarySearchTree::insertNode(struct BiNode **link,</span>
                                  <span style="background-color:d9d9d9">unsigned long val)</span>
<span style="background-color:d9d9d9">{</span>
   <span style="background-color:d9d9d9">if( *link==NULL )</span>
   <span style="background-color:d9d9d9">{</span>
       <span style="background-color:d9d9d9">(*link) = (struct BiNode*)malloc(sizeof(struct BiNode));</span>
       <span style="background-color:d9d9d9">(*(*link)).value = val;</span>
       <span style="background-color:d9d9d9">(*(*link)).left = NULL;</span>
       <span style="background-color:d9d9d9">(*(*link)).right = NULL;</span>
       <span style="background-color:d9d9d9">PRINT("insertNode(): inserting %d\n",val);</span>
   <span style="background-color:d9d9d9">}</span>
12345

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -