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.