Process scheduling MCQs from the KnowledgeGate question bank
CPU scheduling is one of the most reliably tested corners of Operating Systems, and the same handful of ideas keep returning: which algorithms are preemptive, why shortest-job-first minimises average waiting time, how the round robin quantum behaves at its extremes, and what makes a policy suitable for a time-shared system. Below are 12 solved MCQs pulled from KnowledgeGate's published question bank, every one a GATE previous-year question with the year noted. Attempt each before you read the answer. The explanation after each is deliberately short, just enough to lock the reasoning in. Every question links to its exact solved page in the operating systems CPU scheduling module, so you can go deeper wherever an answer feels shaky.
Scheduling basics: preemptive versus non-preemptive
Q1. Which of the following scheduling algorithms is non-preemptive? *(GATE 2002, see the solved page)*
(a) Round Robin
(b) First-In First-Out
(c) Multilevel Queue Scheduling
(d) Multilevel Queue Scheduling with Feedback
Answer: (b) First-In First-Out.
Once an FCFS process gets the CPU it runs to completion, so nothing preempts it. Round robin preempts on every time-slice expiry, and multilevel queue schemes preempt across priority levels, which is exactly what makes them the wrong picks here.
Q2. Which one of the following CPU scheduling algorithms cannot be preemptive? *(GATE 2026, see the solved page)*
(a) Shortest Remaining Time First (SRTF)
(b) First Come First Serve (FCFS)
(c) Round Robin
(d) Priority Scheduling
Answer: (b) First Come First Serve.
FCFS is non-preemptive by definition: the process that arrives first holds the CPU until it finishes. Each of the other three has a preemptive form, SRTF preempts on a shorter arrival, round robin on the quantum, priority on a higher-priority arrival. Notice the same idea from Q1 asked again decades later, which tells you how dependable this fact is.
Q3. Match the CPU scheduling algorithms in Group I to their applications in Group II. Group I: (P) Gang Scheduling, (Q) Rate Monotonic Scheduling, (R) Fair Share Scheduling. Group II: (1) Guaranteed Scheduling, (2) Real-time Scheduling, (3) Thread Scheduling. *(GATE 2007, see the solved page)*
(a) P-3, Q-2, R-1
(b) P-1, Q-2, R-3
(c) P-2, Q-3, R-1
(d) P-1, Q-3, R-2
Answer: (a) P-3, Q-2, R-1.
Gang scheduling co-schedules related threads together, so it pairs with thread scheduling. Rate monotonic is a fixed-priority scheme for periodic tasks, which is squarely real-time scheduling. Fair share hands each user a guaranteed slice of CPU, matching guaranteed scheduling.
Shortest Job First and Shortest Remaining Time First
Q4. Consider a set of n tasks with known runtimes to be run on a uniprocessor machine. Which scheduling algorithm results in the maximum throughput? *(GATE 2001, see the solved page)*
(a) Round Robin
(b) Shortest Job First
(c) Highest Response Ratio Next
(d) First Come First Served
Answer: (b) Shortest Job First.
Finishing the shortest jobs first clears the most tasks in the least time, which maximises throughput and minimises average waiting and turnaround time. Round robin optimises response and fairness, FCFS suffers the convoy effect, and HRRN is a middle path that ages waiting jobs.
Q5. Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time. Which scheduling algorithm minimises the average waiting time in the ready queue? *(GATE 2016, see the solved page)*
(a) Shortest remaining time first
(b) Round-robin with quantum less than the shortest burst
(c) Uniform random
(d) Highest priority first, priority proportional to burst length
Answer: (a) Shortest remaining time first.
When all jobs arrive together, SRTF reduces to SJF, which is provably optimal for average waiting time. The exchange argument is the proof: if a longer job runs before a shorter one, swapping them cuts total waiting time, so the optimal order is always shortest first.
Q6. Three CPU-intensive processes require 10, 20 and 30 time units and arrive at times 0, 2 and 6 respectively. How many context switches are needed under shortest remaining time first? Do not count the switches at time zero and at the end. *(GATE 2006, see the solved page)*
(a) 1
(b) 2
(c) 3
(d) 4
Answer: (b) 2.
P1 starts at t=0 with 10 units. When P2 arrives at t=2, P1 has 8 left versus P2's 20, so P1 keeps running; likewise at t=6, P1's 4 beats P3's 30. P1 finishes at t=10 (switch to P2), P2 finishes at t=30 (switch to P3). That is exactly two switches, because the shortest remaining job never changes until a process completes.
Round robin and time-sharing
Q7. Which scheduling policy is most suitable for a time-shared operating system? *(GATE 1995, see the solved page)*
(a) Shortest Job First
(b) Round Robin
(c) First Come First Serve
(d) Elevator
Answer: (b) Round Robin.
Time-sharing needs every interactive process to feel responsive, and round robin's fixed quantum guarantees each one a turn on a bounded cycle. FCFS lets a long job freeze everyone, SJF can starve long jobs, and elevator is a disk-scheduling policy, not a CPU one.
Q8. If the time-slice used in round-robin scheduling is more than the maximum time required to execute any process, then the policy will *(GATE 2008, see the solved page)*
(a) degenerate to shortest job first
(b) degenerate to priority scheduling
(c) degenerate to first come first serve
(d) none of the above
Answer: (c) degenerate to first come first serve.
Round robin only preempts when the quantum expires. If the quantum is larger than every process's burst, no process is ever preempted, so each one runs to completion in arrival order, which is precisely FCFS.
Q9. With n processes sharing the CPU in round-robin and each context switch taking s seconds, what quantum size q minimises switching overhead while guaranteeing every process the CPU at least every t seconds? *(GATE 1998, see the solved page)*
(a) q ≤ (t − ns)/(n − 1)
(b) q ≥ (t − ns)/(n − 1)
(c) q ≤ (t − ns)/(n + 1)
(d) q ≥ (t − ns)/(n + 1)
Answer: (a) q ≤ (t − ns)/(n − 1).
Before a process gets the CPU again, the other n−1 processes each run for q, and there are n context switches costing s each. The worst gap is (n−1)q + ns, and the guarantee demands this stays within t. Solving gives q ≤ (t − ns)/(n − 1); making q as large as this bound allows also minimises the switching overhead.
Q10. Five jobs P, Q, R, S, T with burst times 4, 1, 8, 1, 2 arrive at t=0 in that order. Under round robin with time slice 1, what is the completion (departure) time of job P? *(GATE 1997, see the solved page)*
(a) 4
(b) 10
(c) 11
(d) 12
Answer: (c) 11.
With a quantum of 1, the ready queue cycles P, Q, R, S, T and P needs four slices. P runs at t=0-1, then waits a full round and runs again at 5-6, 8-9, and finally 10-11, completing at t=11. The trap is forgetting that P re-enters the back of the queue after every slice, so its four units are spread across the schedule.
Q11. For processes P1 (arrival 0, burst 5), P2 (arrival 1, burst 7) and P3 (arrival 3, burst 4), what is the completion order under FCFS and under round robin with quantum 2? *(GATE 2012, see the solved page)*
(a) FCFS: P1, P2, P3; RR: P1, P2, P3
(b) FCFS: P1, P3, P2; RR: P1, P3, P2
(c) FCFS: P1, P2, P3; RR: P1, P3, P2
(d) FCFS: P1, P3, P2; RR: P1, P2, P3
Answer: (c) FCFS: P1, P2, P3; RR: P1, P3, P2.
FCFS runs jobs to completion in arrival order, so P1 then P2 then P3. Round robin with quantum 2 interleaves the bursts; simulating the slices, P1 finishes at 11, P3 at 13 and P2 at 16, so the shorter P3 slips ahead of the longer P2. This is the point of the question: preemption can reorder completions relative to arrival.
Q12. A uniprocessor system has two processes, each alternating 10 ms CPU bursts with 90 ms I/O bursts, both created at nearly the same time, with I/O able to proceed in parallel. Which scheduling strategy gives the least CPU utilisation over a long run? *(GATE 2003, see the solved page)*
(a) First come first served
(b) Shortest remaining time first
(c) Static priority with different priorities
(d) Round robin with a time quantum of 5 ms
Answer: (d) Round robin with a 5 ms quantum.
Each 10 ms CPU burst now gets chopped into two 5 ms slices, forcing an extra context switch mid-burst that the other policies avoid. Those extra switches are pure overhead that does no useful work, so the effective CPU utilisation drops. The lesson is that a quantum smaller than the natural burst buys you nothing but switching cost.
Where these 12 fit in your preparation
The set mirrors how CPU scheduling is examined: preemptive-versus-non-preemptive definitions (Q1-Q3), the SJF and SRTF optimality results and their numericals (Q4-Q6), and the round robin family from quantum behaviour to completion-order traps (Q7-Q12). If you scored below 10, the gap is usually the round robin timeline, so hand-simulate one full schedule until the queue mechanics feel automatic.
For the theory behind every answer, work through the CPU scheduling learn module and its PYQ sets, and see where scheduling sits in the wider syllabus in our Operating Systems for GATE breakdown. GATE aspirants get the full OS sequence inside GATE Guidance by Sanchit Sir, and NET aspirants can start from the NET CS category page. Solve, review the ones you missed, and come back a week later, because the second pass is where the marks get locked in.