IAE Academy

GATE 2020 CS Q.11: solution and answer

GATE 2020 · CSQ.11 · 1 mark · MCQ

Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process's memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statements is TRUE?

  1. (A)

    The hole created by first fit is always larger than the hole created by next fit.

  2. (B)

    The hole created by worst fit is always larger than the hole created by first fit.

  3. (C)

    The hole created by best fit is never larger than the hole created by first fit.

  4. (D)

    The hole created by next fit is never larger than the hole created by best fit.

See the question in the paper
GATE 2020 CS question 11Tap to open full size

Answer and solution

ANSWER

Option (C) is true: the hole created by best fit is never larger than the hole created by first fit.

Official answer: CSource: Official answer key, GATE 2020 CS (IIT Delhi)

  1. The hole left after allocation is (size of the chosen hole) (request size). The request size is the same for every strategy, so a strategy that picks a smaller hole leaves a smaller leftover hole. Only holes large enough for the request are candidates. By the question, no candidate fits exactly, so every candidate leaves a smaller hole.

  2. Best fit picks the smallest adequate hole. First fit, next fit and worst fit each pick some adequate hole, so each picked hole is at least as large as the best-fit hole. Hence best fit leaves the smallest leftover of all four strategies.

  3. (C) First fit picks an adequate hole, which is at least as large as the best-fit hole. So the hole created by best fit is never larger than the one created by first fit. TRUE.

  4. (D) Next fit picks an adequate hole at least as large as the best-fit hole, so its leftover is never smaller than best fit's. It can be strictly larger: for example, if the next adequate hole after the pointer is bigger than the smallest adequate hole, next fit leaves a larger hole. So 'never larger than best fit' is FALSE.

  5. (A) Take a case where the first adequate hole is also the first adequate hole found from the pointer. Then first fit and next fit pick the same hole and create equal holes, so 'always larger' fails. FALSE.

  6. (B) Take a case where the first adequate hole is also the largest hole. Then first fit and worst fit pick the same hole and create equal holes, so 'always larger' fails. FALSE.

  7. Only (C) is true.

KEY IDEA

Leftover hole = chosen hole size minus request size, so best fit, which picks the smallest adequate hole, always leaves the smallest leftover. Every other strategy leaves a hole at least as large as best fit's.

WATCH OUT FOR

Reading 'always larger' as true for worst fit or first fit. Two strategies can pick the very same hole, and then the leftovers are equal, so a strict 'always larger' claim fails. Another slip is assuming next fit can do no worse than best fit. It can leave a bigger hole.

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

More Memory management questions