Operating System - Memory Allocation Strategies
When multiple memory blocks (holes) are available, the OS must choose the most suitable block to allocate for a new process. These strategies aim to minimize wasted space and improve efficiency.
First-Fit Allocation
-
Allocates the first block that is large enough to satisfy the request.
-
Scans memory from the beginning and stops as soon as a suitable block is found.
Example:
Suppose we have free memory blocks of sizes:
[100 KB, 500 KB, 200 KB, 300 KB, 600 KB]
A process requests 212 KB.
Allocation (First-Fit):
-
100 KB → too small
-
500 KB → suitable → allocate 212 KB here
Result:
-
500 KB block becomes 288 KB free (500 - 212)
-
Remaining blocks are unchanged.
Pros:
-
Fast and simple to implement.
Cons:
-
May lead to many small unusable holes near the beginning (fragmentation).
Best-Fit Allocation
-
Searches all memory blocks and allocates the smallest block that is large enough.
-
Tries to minimize leftover space (external fragmentation).
Example:
Same memory blocks:
[100 KB, 500 KB, 200 KB, 300 KB, 600 KB]
Request: 212 KB
Allocation (Best-Fit):
-
500 KB → too big
-
200 KB → too small
-
300 KB → best match (just 88 KB unused) → allocate here
Result:
-
300 KB block becomes 88 KB free
-
Rest unchanged
Pros:
-
Leaves the smallest possible leftover fragment.
Cons:
-
Slower due to scanning all blocks.
-
May still lead to fragmentation.
Worst-Fit Allocation
-
Allocates memory from the largest available block.
-
Idea is to leave larger leftover memory chunks.
Example:
Same memory blocks:
[100 KB, 500 KB, 200 KB, 300 KB, 600 KB]
Request: 212 KB
Allocation (Worst-Fit):
-
Largest block is 600 KB → allocate 212 KB here
Result:
-
600 KB becomes 388 KB free
-
Rest unchanged
Pros:
-
May reduce number of very small unusable fragments.
Cons:
-
Like best-fit, slower due to scanning all blocks.
-
May waste large memory blocks inefficiently.
Each of these strategies has different trade-offs in terms of speed, fragmentation, and memory utilization. The choice depends on the operating system’s goals and workload pattern.