Questions: Contiguous Memory Allocation and Fragmentation

Question 1

A system uses variable-partition memory allocation. Currently, free memory consists of three holes: 60 KB, 50 KB, and 40 KB — 150 KB total. A new process requiring 120 KB arrives. What happens?

• A. The process is allocated across the 60 KB and 50 KB holes using non-contiguous allocation
• B. The process cannot be allocated because no single contiguous hole is large enough — this is external fragmentation
• C. The OS performs compaction automatically and then allocates the process
• D. The process is allocated to the 60 KB hole with 60 KB of internal fragmentation

Answer: (B)

This is the classic external fragmentation scenario: enough total free memory (150 KB > 120 KB needed) exists, but no single contiguous region is large enough. Under contiguous allocation, a process must reside in one unbroken block — so the 120 KB process cannot be placed. Automatic compaction (option C) is not assumed — it is expensive and must be explicitly invoked. Option D confuses the problem type: internal fragmentation occurs within an allocated block, not when a process is refused due to hole-size mismatch.

Question 2

Why is First-Fit often preferred over Best-Fit in practice, despite Best-Fit selecting the smallest hole that fits a process?

• A. First-Fit is faster to implement and requires less memory for bookkeeping
• B. Best-Fit creates many tiny residual holes that are too small to be useful, producing more total unusable fragmentation
• C. First-Fit always leaves larger free holes available for future large processes
• D. Best-Fit is incompatible with variable-partition allocation schemes

Answer: (B)

Best-Fit sounds optimal — taking the smallest sufficient hole minimizes waste per allocation. But in practice, it creates many tiny leftover fragments (the unused remainder after a best-fit allocation) that are too small for any practical future request. These tiny holes accumulate and are effectively unusable. First-Fit, despite selecting holes less 'efficiently,' often leaves larger residual spaces that can accommodate future requests. In practice, First-Fit is faster (doesn't require scanning all holes) and produces comparable or better actual utilization. The locally optimal choice produces globally worse outcomes — a counterintuitive but important result.

Question 3

Fixed-partition memory allocation suffers from internal fragmentation but is immune to external fragmentation.

• T. True
• F. False

Answer: True

This is correct. In fixed-partition allocation, memory is divided into predetermined regions at boot time, and each process gets exactly one partition. Internal fragmentation occurs when a process is smaller than its partition — the unused space inside is wasted. But because partition boundaries are fixed and each partition is either fully allocated or fully free, there are no 'holes' between allocations — which is what external fragmentation requires. External fragmentation is specifically a variable-partition problem, where allocated and freed regions of different sizes create a patchwork of unusable gaps.

Question 4

Best-Fit allocation consistently produces less total memory fragmentation than First-Fit in practice.

• T. True
• F. False

Answer: False

Despite the intuitive appeal, empirical studies and simulations consistently show that Best-Fit does not reliably outperform First-Fit in practice. Best-Fit's selection of the smallest sufficient hole leaves many tiny residual fragments that are practically unusable, eventually filling memory with slivers no process can use. First-Fit tends to leave larger residual regions. Neither strategy eliminates external fragmentation, and neither consistently dominates the other across all workloads. The intuitively 'best' local strategy is not empirically the best global strategy.

Question 5

Explain why compaction addresses external fragmentation but is not a complete solution, and what structural change paging makes to eliminate external fragmentation entirely.

Model answer: Compaction physically relocates all processes to consolidate free space into one contiguous region. It works but has three limitations: (1) it is expensive — every byte of occupied memory may need to be copied; (2) all processes must pause during compaction; (3) it requires addresses to be rebound at runtime, which not all systems support. Most importantly, it is reactive — fragmentation recurs after more allocations. Paging eliminates external fragmentation structurally by removing the contiguity requirement: a process's logical address space is divided into fixed-size pages that map to any available physical frames regardless of location. Because any page can go anywhere, no space is ever 'too small' due to non-contiguity.

This is the 'why paging exists' insight. Paging isn't just a different allocation strategy — it's a structural escape from the contiguity constraint that makes fragmentation inevitable. Understanding the fragmentation problems of contiguous allocation is precisely what makes the motivation for paging clear rather than arbitrary.