A computer system has 1000 KB of contiguous main memory, initially empty. Jobs…
2018
A computer system has 1000 KB of contiguous main memory, initially empty. Jobs are allocated in arrival order and are not relocated or compacted. The sequence is:
Job 1 arrives and requires 200 KB.
Job 2 arrives and requires 350 KB.
Job 3 arrives and requires 300 KB.
Job 1 finishes.
Job 4 arrives and requires 120 KB.
Job 5 arrives and requires 150 KB.
Job 6 arrives and requires 70 KB.
Between first-fit and best-fit, which policy can allocate all arriving jobs in this sequence?
Answer: A. First-fit — ConceptIn contiguous allocation, first-fit selects the first hole in address order that is large enough, whereas best-fit selects the smallest hole that is…
- A.
First-fit
- B.
Best-fit
- C.
Both, first-fit and best-fit
- D.
Cannot be determined
Attempted by 414 students.
Show answer & explanation
Correct answer: A
Concept
In contiguous allocation, first-fit selects the first hole in address order that is large enough, whereas best-fit selects the smallest hole that is large enough.
External fragmentation is compared by tracing the ordered hole sizes after each allocation; total free memory alone is not sufficient when no single hole is large enough.
Application
After Jobs 1, 2, and 3 are placed, 150 KB remains at the high-address end. When Job 1 finishes, the holes in address order are 200 KB and 150 KB.
For Job 4 (120 KB), first-fit uses the 200 KB hole and leaves 80 KB, while best-fit uses the 150 KB hole and leaves 30 KB.
For Job 5 (150 KB), first-fit uses the 150 KB hole, so its remaining hole is 80 KB. Best-fit uses the 200 KB hole, so its holes are 50 KB and 30 KB.
For Job 6 (70 KB), first-fit has an 80 KB hole and can allocate it. Best-fit has 80 KB free in total, but its largest hole is only 50 KB, so it cannot allocate a contiguous 70 KB block.
Stage | First-fit holes | Best-fit holes |
|---|---|---|
After Job 1 finishes | 200 KB, 150 KB | 200 KB, 150 KB |
After Job 4 | 80 KB, 150 KB | 200 KB, 30 KB |
After Job 5 | 80 KB | 50 KB, 30 KB |
Cross-check
Immediately before Job 6, both policies have 80 KB free in total. Only first-fit has that free memory in one contiguous 80 KB hole; best-fit has split it into 50 KB and 30 KB holes.
Therefore, first-fit performs better for this sequence because it allocates every arriving job.
A video solution is available for this question — log in and enroll to watch it.