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

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

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

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

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

17.16.1.6. 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)

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

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

17.16.1.9. Example¶

17.16.1.10. .¶

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

17.16.1.12. Buddy Method Example¶

17.16.1.13. .¶

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