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

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

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

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

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

  • Example: Buddy Method

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

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

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

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

1.1.1.9. Example¶

1.1.1.10. .¶

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

1.1.1.12. Buddy Method Example¶

1.1.1.13. .¶

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