High yield ●●●

⏱️ CPU Scheduling

Why it matters: Almost every paper has a Gantt-chart numerical: average waiting or turnaround time for SRTF, round robin or priority.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 5 done.

Formulas

Turnaround time
TAT = CT − AT
Waiting time
WT = TAT − BT
Response time
RT = (first time on CPU) − AT
CPU utilisation
useful time / total time, where total includes context-switch time
Round robin first wait
at most (n − 1) × q for n processes that all arrived
Rate-monotonic bound
U = Σ Cᵢ/Tᵢ ≤ n (2^(1/n) − 1) (sufficient test); EDF: U ≤ 1
Exponential averaging
τ(n+1) = α·t(n) + (1 − α)·τ(n)

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Average waiting / turnaround time for SRTF, RR or priority
Draw the Gantt chart carefully, mark preemption points and arrival ties, then compute WT = TAT − BT.
★★★
Which algorithm gives minimum average waiting time or can starve
SJF is optimal for waiting time; SJF, SRTF and priority can starve; RR and FCFS cannot.
★★★
Effect of the time quantum
Large q turns RR into FCFS; small q raises context-switch overhead; compute CPU efficiency.
★★★
Processes with I/O bursts
Alternate CPU and I/O bursts: the CPU is idle only if every process is in I/O.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

13 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

13 questions · 0 correct of 0 attempted · marks 0 / 20

Year:
GATE 2025 CS2 · Q26MCQ1 mark
Processes P1, P2, P3, P4 arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times. Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?
GATE 2025 CS1 · Q38MCQ2 marks
A computer has two processors, M1 and M2. Four processes P1, P2, P3, P4 with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows: M1 uses priority of execution for the processes as P1 > P3 > P2 > P4, i.e., P1 and P4 have highest and lowest priorities, respectively. M2 uses priority of execution for the processes as P2 > P3 > P4 > P1, i.e., P2 and P1 have highest and lowest priorities, respectively. A process Pi is scheduled to a processor Mk, if the processor is free and no other process Pj is waiting with higher priority. At any given point of time, a process can be allocated to any one of the free processors without violating the execution priority rules. Ignore the context switch time. What will be the average waiting time of the processes in milliseconds?
GATE 2024 CS2 · Q37MCQ2 marks
Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time. A (0, 10), B (2, 6), C (4, 3), and D (6, 7). Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?
GATE 2023 · Q27MSQ1 mark
Which one or more of the following CPU scheduling algorithms can potentially cause starvation?

One or more options may be correct. Select all that apply, then submit.

GATE 2022 · Q42MCQ2 marks
Consider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time t = 0. There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?
GATE 2021 Set 1 · Q25NAT1 mark
Three processes arrive at time zero with CPU bursts of 16, 20 and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is ______ milliseconds.
GATE 2020 · Q50NAT2 marks
Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order P1, P2, P3, P4. Processes P1, P2, P3, P4 with burst times (in ms) 8, 7, 2, 4. If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is ______.
GATE 2019 Set 2 · Q41NAT2 marks
Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below: P1 (arrival 0, burst 3), P2 (arrival 1, burst 1), P3 (arrival 3, burst 3), P4 (arrival 4, burst Z). These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is ______.
GATE 2017 Set 1 · Q24NAT1 mark
Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below: P1 (arrival 0, burst 7), P2 (3, 3), P3 (5, 5), P4 (6, 2). If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is ______ milliseconds.
GATE 2016 Set 1 · Q20MCQ1 mark
Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?
GATE 2014 Set 1 · Q32NAT2 marks
Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds. A (arrival 0, execution 6), B (3, 2), C (5, 4), D (7, 6), E (10, 3). Using the shortest remaining time first scheduling algorithm, the average process turnaround time (in msec) is ______.
GATE 2013 Code A · Q10MCQ1 mark
A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?
GATE 2012 Code A · Q31MCQ2 marks
Consider the 3 processes, P1, P2 and P3 shown in the table: P1 (arrival 0, 5 time units), P2 (arrival 1, 7 units), P3 (arrival 3, 4 units). The completion order of the 3 processes under the policies FCFS and RR2 (round robin scheduling with CPU quantum of 2 time units) are

Common traps

Idle time: if no process has arrived, the Gantt chart has a gap. Do not skip it.
In SRTF compare the new arrival with the remaining time of the running process, not its original burst.
Priority numbers: check whether lower number = higher priority before choosing.
In round robin, the order of the queue when an arrival coincides with a quantum expiry changes the answer: follow the stated convention.