Memory Allocation
When allocating heap memory, there are multiple strategies we can deploy to use the allocated memory. This guide explores two popular approaches: first-fit and best-fit allocation.
Memory Overview
Below is a simple program that makes a series of heap memory allocations using malloc, and some calls to free:
void *a = malloc(128); // 128 == 0x 80 bytes
void *b = malloc(384); // 384 == 0x180 bytes
void *c = malloc(128);
void *d = malloc(128);
void *e = malloc(256); // 256 == 0x100 bytes
void *f = malloc(128);
/* Line 7 */
free(b);
free(c);
free(e);
With sequential allocation of memory and no overhead, at ‘Line 7` a total of 900 bytes are allocated:
| 128 bytes | ← f = 0x1400 |
| 256 bytes | ← e = 0x1300 |
| 128 bytes | ← d = 0x1280 |
| 128 bytes | ← c = 0x1200 |
| 384 bytes | ← b = 0x1080 |
| 128 bytes | ← a = 0x1000 |
Start of Heap (0x1000) |
After we run the remaining code, we introduce several holes into our heap memory:
| 128 bytes | ← f = 0x1400 |
| 256 bytes (FREE) | ← 0x1300 |
| 128 bytes | ← d = 0x1280 |
| 128 bytes (FREE) | ← 0x1200 |
| 384 bytes (FREE) | ← 0x1080 |
| 128 bytes | ← a = 0x1000 |
Start of Heap (0x1000) |
Since we have two free blocks next to each other, we can coalesce these two small free blocks (128 + 384 = 512 bytes) together:
| 128 bytes | ← f = 0x1400 |
| 256 bytes (FREE) | |
| 128 bytes | ← d = 0x1280 |
| 512 bytes (FREE) | |
| 128 bytes | ← a = 0x1000 |
Start of Heap (0x1000) |
Question: What strategies are best to find how to fill these holes when new allocations arrive?
Strategy #1: First-Fit
The First-fit Allocation Strategy traverses the system’s list of free blocks to find the first free block that is large enough that can be used to fulfill the request. For example, consider three new requests:
void *x = malloc(128);
void *y = malloc(500);
void *z = malloc(100);
Using first fit, the first allocation request, x for 64 bytes, finds that it can placed in the very first free heap block and uses a small part of the block:
| 128 bytes | ← f = 0x1400 |
| 256 bytes (FREE) | |
| 128 bytes | ← d = 0x1280 |
| 384 bytes (FREE) | |
| 128 bytes | ← x = 0x1080 |
| 128 bytes | ← a = 0x1000 |
Start of Heap (0x1000) |
Using first fit, the second allocation request, y for 500 bytes, cannot fit in either the first hole (448 bytes) nor the second hole (256 bytes). To facilitate this heap request, new heap memory must be allocated:
| 500 bytes | ← y = 0x1480 |
| 128 bytes | ← f = 0x1400 |
| 256 bytes (FREE) | |
| 128 bytes | ← d = 0x1280 |
| 384 bytes (FREE) | |
| 128 bytes | ← x = 0x1080 |
| 128 bytes | ← a = 0x1000 |
Start of Heap (0x1000) |
Finally, the final allocation request, z for 64 bytes, is able to fit immediately after x in our first hole of 448 bytes:
| 500 bytes | ← y = 0x1480 |
| 128 bytes | ← f = 0x1400 |
| 256 bytes (FREE) | |
| 128 bytes | ← d = 0x1280 |
| 284 bytes (FREE) | |
| 100 bytes | ← z = 0x1100 |
| 128 bytes | ← x = 0x1080 |
| 128 bytes | ← a = 0x1000 |
Start of Heap (0x1000) |
Strategy #2: Best-Fit
The Best-fit Allocation Strategy traverses all of your free blocks to find the free block that best fits the memory request. A best fit is defined to be the block that leaves as small of a resultant block as possible.
Using the same memory as we had before the first strategy:
| 128 bytes | ← f = 0x1400 |
| 256 bytes (FREE) | |
| 128 bytes | ← d = 0x1280 |
| 512 bytes (FREE) | |
| 128 bytes | ← a = 0x1000 |
Start of Heap (0x1000) |
Consider three new requests:
void *x = malloc(128);
void *y = malloc(500);
void *z = malloc(100);
Using best fit, the available free blocks are 512 bytes (at 0x1080) and 256 bytes (at 0x1300). Since the 256 byte block best fits a request for 128 bytes, x is allocated within the 256 byte block:
| 128 bytes | ← f = 0x1400 |
| 128 bytes (FREE) | |
| 128 bytes | ← x = 0x1300 |
| 128 bytes | ← d = 0x1280 |
| 512 bytes (FREE) | |
| 128 bytes | ← a = 0x1000 |
Start of Heap (0x1000) |
Next, the allocation request for y of 500 bytes can only be allocated in the 512-byte hole and is a nearly perfect fit:
| 128 bytes | ← f = 0x1400 |
| 128 bytes (FREE) | |
| 128 bytes | ← x = 0x1300 |
| 128 bytes | ← d = 0x1280 |
| 12 bytes (FREE) | |
| 500 bytes | ← y = 0x1080 |
| 128 bytes | ← a = 0x1000 |
Start of Heap (0x1000) |
Finally, the final allocation request – z of 100 bytes – fits nearly perfectly in the hole of 128 bytes:
| 128 bytes | ← f = 0x1400 |
| 28 bytes (FREE) | |
| 100 bytes | ← z = 0x1380 |
| 128 bytes | ← x = 0x1300 |
| 128 bytes | ← d = 0x1280 |
| 12 bytes (FREE) | |
| 500 bytes | ← y = 0x1080 |
| 128 bytes | ← a = 0x1000 |
Start of Heap (0x1000) |
First-Fit vs. Best-Fit Analysis
Both first-fit and best-fit strategies are good memory allocation strategies that allow the re-use of memory. Both strategies have different strengths and weaknesses.
Running Time:
- First-fit is faster, allowing the searching for memory to stop immediately after finding a free-block of large enough size.
- Best-fit is slow, requiring the search of every free block in memory.
Allocation Patterns:
- First-fit can use up valuable large blocks of free space for tiny requests, resulting in the need to grow the heap more often and using more memory than a best-fit algorithm. (You saw this in our example above where first-fit needed to allocate more heap memory for
y.) - Best-fit will result in many small holes that may never be useful resulting in increased memory fragmentation. (You saw this in our example above where best-fit created a hole of 12 and 28 bytes – smaller than any request our program ever made.)
We will explore strategies to make use of the advantages of both methods in the next lecture through the use of segregated free lists.