GATE 2026 CS2 Q.55: solution and answer

GATE 2026 · CS2Q.55 · 2 marks · NAT

Consider contiguous allocation of physical memory to processes using variable partitioning scheme. Suppose there are 8 holes in the memory of sizes 20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB, and 12 KB. Assume that no two holes are adjacent. Two processes P1 of size 16 KB and P2 of size 9 KB arrive in that order, and they are allocated memory using the best-fit technique. After allocating space to P1 and P2, the number of holes of size less than 8 KB is ____________. (answer in integer)

Note: 1K=2^10

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The number of holes smaller than 8 KB is 3.

Official answer: 3Source: Official answer key, GATE 2026 CS2 (IIT Guwahati)

Best fit allocates each process to the smallest hole that is large enough for it.
P1 needs $16 KB$ . The holes of at least $16 KB$ are $20, 25, 18$ . The smallest is $18 KB$ , so P1 goes there and leaves a hole of $18 - 16 = 2 KB$ .
The holes are now $20, 4, 25, 2, 7, 9, 15, 12$ (in $KB$ ).
P2 needs $9 KB$ . The holes of at least $9 KB$ are $20, 25, 9, 15, 12$ . The smallest is exactly $9 KB$ , so P2 fills it completely and no leftover hole remains.
The holes are now $20, 4, 25, 2, 7, 15, 12$ (7 holes).
The holes smaller than $8 KB$ are $4, 2, 7$ . The count is $3$ .

KEY IDEA

Best fit takes the smallest hole that is big enough. An exact fit leaves no hole behind, while a larger hole leaves a remainder that becomes a new hole.

WATCH OUT FOR

Using first fit or worst fit would put P1 in the 20 KB or 25 KB hole. Another slip is leaving a zero-size hole after the exact fit of P2 and counting it. A third is forgetting that the 2 KB remainder from P1 is a new hole smaller than 8 KB.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 10 Memory management questions, with notes

GATE 2026 CS2 Q.55: solution and answer

Answer and solution

More Memory management questions