IAE Academy

GATE 2023 CS Q.27: solution and answer

GATE 2023 · CSQ.27 · 1 mark · MSQ

Which one or more of the following CPU scheduling algorithms can potentially cause starvation?

  1. (A)

    First-in First-Out

  2. (B)

    Round Robin

  3. (C)

    Priority Scheduling

  4. (D)

    Shortest Job First

See the question in the paper
GATE 2023 CS question 27Tap to open full size

Answer and solution

ANSWER

Priority Scheduling (C) and Shortest Job First (D) can cause starvation.

Official answer: A, C, D or C, DSource: Official answer key, GATE 2023 CS (IIT Kanpur)

  1. Starvation means a ready process can wait indefinitely because other processes are always chosen ahead of it.

  2. FIFO (FCFS): the ready queue is served strictly in arrival order. Every process reaches the front after a finite number of earlier arrivals, so no starvation.

  3. Round Robin: each ready process gets a time quantum in cyclic order. With ready processes a process waits at most before its next turn, so no starvation.

  4. Priority scheduling: the highest-priority ready process always runs. A steady stream of higher-priority arrivals can keep a low-priority process waiting forever, so starvation is possible (the usual cure is aging).

  5. Shortest Job First (including its preemptive form SRTF): the shortest burst is always chosen. If short jobs keep arriving, a long job may never be picked, so starvation is possible.

  6. Hence the algorithms that can cause starvation are Priority Scheduling and Shortest Job First, options C and D.

KEY IDEA

Starvation needs a scheduler that can keep choosing other processes ahead of a waiting one forever. Priority and SJF/SRTF do this. FIFO and Round Robin bound every process's waiting time.

WATCH OUT FOR

Thinking only priority scheduling starves, and forgetting that SJF/SRTF starves long jobs when short jobs keep arriving. Another slip is picking FIFO because a long job at the front delays others. That delay is finite, so it is not starvation.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 8 CPU scheduling questions, with notes

More CPU scheduling questions