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 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);
}
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.
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
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.
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
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
.
What do we do if there is no free block that can hold the message?