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