📄 http:^^www.cs.wisc.edu^~cs537-1^memory.html
字号:
Date: Tue, 05 Nov 1996 00:27:42 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Thu, 31 Oct 1996 21:38:55 GMTContent-length: 20000<html><head><title>CS 537 - Memory Management</title></head><body bgcolor="#ffffff"><h1>CS 537<br>Lecture Notes<br>Memory Management</h1><hr><h2>Contents</h2><ul><li><!WA0><a href="#core"> Allocating Main Memory </a><ul><li><!WA1><a href="#core_algorithms"> Algorithms for Memory Management </a><li><!WA2><a href="#core_compaction"> Compaction and Garbage Collection </a><li><!WA3><a href="#core_swapping"> Swapping </a></ul></ul><hr><a name="core"> <h2> Allocating Main Memory </h2> </a>We first consider how to manage main (``core'') memory (also called<em>random-access memory</em> (RAM)).In general, a memory manager provides two operations:<pre><font color="0f0fff"> Address allocate(int size); void deallocate(Address block);</font></pre>The procedure <samp><font color="0f0fff">allocate</font></samp> receives a request for a contiguous blockof <samp><font color="0f0fff">size</font></samp> bytes of memory and returns a pointer to such a block.The procedure <samp><font color="0f0fff">deallocate</font></samp> releases the indicated block, returningit to the <em>free pool</em> for reuse.Sometimes a third procedure is also provided,<pre><font color="0f0fff"> Address reallocate(Address block, int new_size);</font></pre>which takes an allocated block and changes its size, either returning partof it to the free pool or extending it to a larger block.It may not always be possible to grow the block without copying it toa new location, so <samp><font color="0f0fff">reallocate</font></samp> returns the new address of the block.<p>Memory allocators are used in a variety of situations.In Unix, each process has a <em>data segment</em>.There is a system call to make the data segment bigger, but no system callto make it smaller.Also, the system call is quite expensive.Therefore, there are library procedures (called <samp><font color="0f0fff">malloc</font></samp>, <samp><font color="0f0fff">free</font></samp>,and <samp><font color="0f0fff">realloc</font></samp>) to manage this space.Only when <samp><font color="0f0fff">malloc</font></samp> or <samp><font color="0f0fff">realloc</font></samp> runs out of space is it necessaryto make the system call.The C++ operators <samp><font color="0f0fff">new</font></samp> and <samp><font color="0f0fff">delete</font></samp> are just dressed-up versionsof <samp><font color="0f0fff">malloc</font></samp> and <samp><font color="0f0fff">free</font></samp>.The Java operator <samp><font color="0f0fff">new</font></samp> also uses <samp><font color="0f0fff">malloc</font></samp>, and theJava runtime sustem calls <samp><font color="0f0fff">free</font></samp> when an object is no found to beinaccessible during <em>garbage collection</em> (described below).<p>The operating system also uses a memory allocator to manage spaceused for OS data structures and given to ``user'' processes for their own use.As we saw<!WA4><a href="http://www.cs.wisc.edu/~cs537-1/processes.html#using_why">before</a>, there are several reasons why we might want multipleprocesses, such as serving multiple interactive users or controlling multipledevices.There is also a ``selfish'' reason why the OS wants to have multiple processesin memory at the same time:to keep the CPU busy.Suppose there are <em>n</em> processes in memory (this is called the<em>level of multiprogramming</em>) and each process is blocked(waiting for I/O) a fraction <em>p</em> of the time.In the best case, when they ``take turns'' being blocked, the CPU will be100% busy provided <em>n(1-p) ≥ 1</em>. For example, ifeach process is ready 20% of the time, <em>p = 0.8</em> and the CPU couldbe kept completely busy with five processes.Of course, real processes aren't so cooperative. In the worst case, theycould all decide to block at the same time, in which case, the CPU<em>utilization</em> (fraction of the time the CPU is busy) would be only<em>1 - p</em> (20% in our example).If each processes decides randomly and independently whento block, the chance that all <em>n</em> processes are blocked at thesame time is only <em>p<sup>n</sup></em>, so CPU utilization is<em>1 - p<sup>n</sup></em>. Continuing our example in which <em>n = 5</em> and <em>p = 0.8</em>, theexpected utilization would be 1 - .8<sup>5</sup> = 1 - .32768 = 0.67232.In other words, the CPU would be busy about 67% of the time on the average.See Figure 3-2 on page 77 of the text.<a name="core_algorithms"> <h3> Algorithms for Memory Management </h3> </a>Clients of the memory mangager keep track of allocated blocks (for now,we will not worry about what happens when a client ``forgets'' about a block).The memory manager needs to keep track of the ``holes'' between them.The most common data structure is a doubly linked list of holes, sorted by address.This data structure is called the <em>free list</em>.This free list doesn't actually consume any space (other than thehead and tail pointers), since the links between holes can be stored inthe holes themselves (provided each hole is at least as large as twopointers).To satisfy an <samp><font color="0f0fff">allocate(n)</font></samp> request, the memory manager finds a holeof size at least <em>n</em> and removes it from the list.If the hole is bigger than <em>n</em> bytes, it can split off the tailof the hole, making a smaller hole, which it returns to the list.To satisfy a <samp><font color="0f0fff">deallocate</font></samp> request, the memory manager turns thereturned block into a ``hole'' data structure and inserts it intothe appropriate place in the free list. If the new hole is immediatelypreceded or followed by a hole, the holes can be <em>coalesced</em>into a bigger hole.<p>How does the memory manager know how big the returned block is?The usual trick is to put a small <em>header</em> in the allocated block,containing the size of the block and perhaps some other information.The <samp><font color="0f0fff">allocate</font></samp> routine returns a pointer to the body of the block, notthe header, so the client doesn't need to know about it.The <samp><font color="0f0fff">deallocate</font></samp> routine subtracts the header size from its argumentto get the address of the header.The client thinks the block is a little smaller than it really is.So long as the client ``colors inside the lines'' there is no problem, butif the client has bugs and scribbles on the header, the memory managercan get completely confused.This is a frequent problem with malloc in Unix programs written in C orC++.The Java system uses a variety of runtime checks to prevent this kind of bug.<p>How does the memory manager choose a hole to respond to an <samp><font color="0f0fff">allocate</font></samp>request?At first, it might seem that it should choose the smallest hole that isbig enough to satisfy the request.This strategy is called <em>best fit</em>.It has two problems. First, it requires an expensive search of theentire free list to find the best hole (although fancier data structurescan be used to speed up the search).More importantly, it leads to the creation of lots of little holesthat are not big enough to satisfy any requests.This situation is called <em>fragmentation</em>, and is a problem forall memory-management strategies, although it is particularly bad forbest-fit.One way to aviod making little holes is to give the client a bigger blockthan it asked for.For example, we might round all requests up to the next larger multipleof 64 bytes.That doesn't make the fragmentation go away, it just hides it.Unusable space in the form of holes is called <em>external fragmentation</em>,while unused space inside allocated blocks is called <em>internalfragmentation</em>.<p>Another strategy is <em>first fit</em>, which simply scans thefree list until a large enough hole is found.Despite the name, first-fit is generally better than best-fit becauseit leads to less fragmentation.There is still one problem: Small holes tend to accumulate near thebeginning of the free list, making the memory allocator search fartherand farther each time.This problem is solved with <em>next fit</em>, which starts each searchwhere the last one left off, wrapping around to the beginng when theend of the list is reached.<p>Yet another strategy is to maintain separate lists, each containingholes of a different size.Tanenbaum's ``multiprogramming with fixed partitions'' (Section 3.1.3on page 78) can be viewed as an extreme case of this approach, in whichthe number of ``holes'' is very small.This approach works well at the application level, when only a fewdifferent types of objects are created (although there might belots of instances of each type).It can also be used in a more general setting by rounding all requestsup to one of a few pre-determined choices.For example, the memory mangager may round all requests up to the nextpower of two bytes (with a minimum of, say, 64) and then keep listsof holes of size 64, 128, 256, ..., etc. Assuming the largest requestpossible is 1 megabyte, this requires only 14 lists.This is the approach taken by most implementations of malloc.This approach eliminates external fragmentation entirely, but internalfragmenation may be as bad as 50% in the worst case (which occurs whenall requests are one byte more than a power of two).<p>Another problem with this approach is how to coalesce neighboring holes.One possibility is not to try. The system is initialized by splitting memory up into a fixed set of holes (either all thesame size or a variety of sizes). Each request is matched to an``appropriate'' hole. If the request is smaller than the hole size, theentire hole is allocated to it anyhow. When the allocate block is released,it is simply returned to the appropriate free list.Most implementations of malloc use a variant of this approach (someimplementations split holes, but most never coalesce them).<p>An interesting trick for coalescing holes with multiple free lists is the<em>buddy system</em>.Assume all blocks and holes have sizes which are powers of two(so requests are always rounded up to the next power of two) and eachblock or hole starts at an address that is an exact multiple of its size.Then each block has a ``buddy'' of the same size adjacent to it, such that⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -