Memory Allocation with First-Fit and Best-Fit

In contiguous memory allocation systems, the operating system selects a free partition or hole for each incoming process according to a placement rule such as first-fit or best-fit.2 These strategies influence fragmentation and overall memory efficiency.2

We are given memory blocks, in order:

Processes arrive in order:

Under first-fit, the allocator scans memory from the beginning and places each process into the first sufficiently large free block. Under best-fit, it scans all available blocks and chooses the smallest one that can still hold the process, aiming to reduce immediate leftover space.2

Footnotes

1. First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩ ↩² ↩³

2. First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩ ↩²

3. Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩ ↩²

The resulting first-fit state is:

Final free blocks after first-fit:

Notice the important effect of external fragmentation: although total remaining free memory is $100 + 176 + 200 + 300 + 183 = 959$ KB, no single block is at least $426$ KB, so P4 still cannot be placed.2

$$\text{Largest free block after first-fit} = 300 \text{ KB} < 426 \text{ KB}$$

Thus, first-fit leaves enough total memory but not enough contiguous memory for the last process.2

Footnotes

1. Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩ ↩²

2. OPERATING SYSTEMS - Real Memory Management PDF - Explains placement algorithms and external fragmentation in contiguous allocation. ↩ ↩²

The resulting best-fit state is:

Final free blocks after best-fit:

All four processes are allocated successfully. This aligns with standard best-fit behavior: choosing the smallest adequate free block tends to preserve larger blocks for later large requests.2

Footnotes

1. First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩

2. Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩

A direct efficiency comparison can be made in two ways:

1. Number of processes allocated: best-fit allocates all $4$ processes, while first-fit allocates only $3$.2
2. Memory utilization for this sequence: total requested memory is

$$212 + 417 + 112 + 426 = 1167 \text{ KB}$$

Under first-fit, allocated memory is

$$212 + 417 + 112 = 741 \text{ KB}$$

Under best-fit, allocated memory is

$$1167 \text{ KB}$$

So best-fit uses more of the available memory to satisfy actual process demand in this particular case.2

This example is a classic case where best-fit is more efficient because it avoids consuming large blocks too early.2

Footnotes

1. First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩ ↩² ↩³

2. OPERATING SYSTEMS - Real Memory Management PDF - Explains placement algorithms and external fragmentation in contiguous allocation. ↩ ↩²

3. Memory Management in Operating System - Summarizes first-fit, best-fit, and fragmentation concepts in OS memory management. ↩

Final Conclusion

For the partitions $100$, $500$, $200$, $300$, and $600$ KB and the processes $212$, $417$, $112$, and $426$ KB, the placements are:

• First-fit:
  $212 \rightarrow 500$,
  $417 \rightarrow 600$,
  $112 \rightarrow 288$ leftover,
  $426 \rightarrow$ not allocated.2

• Best-fit:
  $212 \rightarrow 300$,
  $417 \rightarrow 500$,
  $112 \rightarrow 200$,
  $426 \rightarrow 600$.2

Therefore, best-fit makes the most efficient use of memory in this case because it allocates all four processes, whereas first-fit allocates only three.2

Footnotes

1. First-Fit Allocation in Operating Systems - Defines first-fit scanning behavior and discusses fragmentation effects. ↩

2. OPERATING SYSTEMS - Real Memory Management PDF - Explains placement algorithms and external fragmentation in contiguous allocation. ↩ ↩² ↩³

3. First Best and Worst Fit.pptx - Provides the exact worked example with these partition and process sizes. ↩ ↩²