Close Window

Show Source |    | About   «  17.15. Memory Cues and Resumption Strategies   ::   Contents   ::   17.17. Over-Constrained Code  »

17.16. Memory Management

17.16.1. Memory Management Memory Management

  • Problem: Records (of various lengths) need to be stored.

  • Model: A big array of space to store them, managed by a memory manager.

    • Like a coat-check stand, give them your coat, get back a ticket. Later, return the ticket for your coat.

    • We call the ticket a handle. Memory Manager ADT

// Memory Manager abstract class
interface MemManager {
  // Store a record and return a handle to it
  public MemHandle insert(byte[] info);

  // Release the space associated with a record
  public void release(MemHandle h);

  // Get back a copy of a stored record
  public byte[] getRecord(MemHandle h);
} Implementation Issues

  • The client doesn’t know what is in the handle.

  • The memory manager doesn’t know what is in the message.

  • Multiple clients can share a memory manager.

  • The memory manager might interact with a buffer pool:
    • The client decides what gets stored

    • The memory manager decides where things get stored

    • The buffer pool decides when blocks are in main memory Dynamic Storage Allocation

  • Use a memory manager when:
    • Access patterns are uncertain

    • Messages are of varying length

  • Over time, memory contains interspersed free blocks and reserved blocks.

    • When adding a new message, find a free block large enough

    • When deleting, merge free blocks Fragmentation

  • Internal fragmentation: when more space is allocated than the message size.

    • Might be done to make memory management easier

    • Example: Sectors and clusters on disk

  • External fragmentation: Free blocks too small to be useful. Managing the Free Blocks

  • A key issue is how to merge free blocks
    1. Use a linked list of free blocks (external to the memory pool) Selecting a Free Block

  • Somehow, need to pick one of the free blocks in which to store the message

    • It must be at least as large as the message (plus whatever info the memory manager needs, such as size and tags)

    • Extra space can be returned as a free block

    • Want to minimize fragmentation, and avoid failing to service requests Sequential Fit Methods

First Fit: Start from beginning, pick first free block that is big enough
Store list in memory-pool order
Circular first fit: Move forward from current position
Best Fit: Pick the smallest block big enough
Store by block size, or search list
Protect large blocks for big requests
Worst Fit: Pick the biggest block
Store by block size, or search list
Avoid external fragmentation Example . Buddy Method

The memory pool is a power of 2 in size.
Memory allocations are always the smallest power of 2 equal to or bigger than the request.
Free (and allocated) blocks are therefore always a power of 2
Keep a list for each block size
Easy to merge freed blocks Buddy Method Example . Failure Policies

What do we do if there is no free block that can hold the message?
Must resort to a failure policy.
Reject the request
Grow the memory
Compact the memory
Garbage collection

   «  17.15. Memory Cues and Resumption Strategies   ::   Contents   ::   17.17. Over-Constrained Code  »

Close Window