2. Memory Management

2.1. 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.

2.2. 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);
}

2.3. 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

2.4. 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

2.5. 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.

2.6. Managing the Free Blocks

• A key issue is how to merge free blocks

  • Use a linked list of free blocks (external to the memory pool)

2.7. 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

2.8. 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

2.9. Example

2.10. 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

2.11. Buddy Method Example

2.12. 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