CPU Scheduling Interview Questions with Gantt Chart Numericals
Last updated 2026-11-19
CPU scheduling is the most numerical part of an operating systems paper. You will be given arrival times and burst times, asked to draw a Gantt chart and report average waiting time or turnaround time. This page works through each classic algorithm on small data sets, with every subtraction shown, and also covers the conceptual questions that surround them.
All formulas use the same definitions: turnaround time = completion time - arrival time, waiting time = turnaround time - burst time, and response time = first CPU time - arrival time. Keep these three lines at the top of your rough sheet. For the broader subject, see operating systems interview questions, and for a preparation plan see how to crack an OS interview.
| Formulas | TAT = CT - AT; WT = TAT - BT; RT = first run - AT |
|---|---|
| Algorithms covered | FCFS, SJF, SRTF, round robin, priority, MLFQ |
| Numericals | 6 with full Gantt charts |
A checklist for any scheduling numerical
- Sort by arrival time first and note ties. Most mistakes come from missing a process that arrives while another is running.
- For preemptive algorithms, re-check the ready queue at every arrival, not only when a process finishes.
- Draw the Gantt chart with timestamps under each boundary, then fill a table of CT, TAT and WT. Verify that the sum of burst times equals the last completion time when there is no idle gap.
- In round robin, a process that arrives at the same instant a quantum expires is usually placed in the queue before the preempted one. State this assumption in the exam.
CPU Scheduling Interview Questions with Gantt Chart Numericals: questions with worked answers
1 What are the criteria used to compare CPU scheduling algorithms?
easyCPU utilisation (keep the CPU busy), throughput (processes completed per unit time), turnaround time (submission to completion), waiting time (time spent in the ready queue), and response time (submission to first response, important for interactive systems). A good scheduler maximises utilisation and throughput and minimises the other three, but these goals conflict, so no algorithm wins on all.
2 Differentiate between preemptive and non-preemptive scheduling.
easyIn non-preemptive scheduling a process keeps the CPU until it finishes or blocks for I/O (FCFS, non-preemptive SJF). In preemptive scheduling the OS can take the CPU away when a higher-priority process arrives or a quantum expires (SRTF, round robin, preemptive priority). Preemption gives better response times but needs context switches and careful protection of shared kernel data.
3 Numerical: Three processes arrive at time 0 with burst times P1 = 24, P2 = 3, P3 = 3. Find the average waiting time under FCFS, then under SJF.
easyFCFS runs in arrival order. Waiting times are P1 = 0, P2 = 24, P3 = 27, so the average is (0 + 24 + 27) / 3 = 17 ms. SJF runs P2, P3, P1: waits are P2 = 0, P3 = 3, P1 = 6, so the average is 9 / 3 = 3 ms. The same work finishes by 30 in both cases, but short jobs are no longer stuck behind the long one. That stuck-behind-a-long-job effect under FCFS is the convoy effect.
textFCFS: | P1 (0-24) | P2 (24-27) | P3 (27-30) | SJF: | P2 (0-3) | P3 (3-6) | P1 (6-30) |4 Numerical: Non-preemptive SJF with P1 (AT 0, BT 8), P2 (AT 1, BT 4), P3 (AT 2, BT 9), P4 (AT 3, BT 5). Find average waiting and turnaround time.
mediumAt time 0 only P1 is present, so it runs 0 to 8 without interruption. At t = 8 the ready processes are P2 (4), P3 (9), P4 (5); the shortest is P2 (8 to 12), then P4 (12 to 17), then P3 (17 to 26). Completion times: P1 8, P2 12, P4 17, P3 26. Turnaround: 8, 11, 14, 24. Waiting: P1 0, P2 11 - 4 = 7, P4 14 - 5 = 9, P3 24 - 9 = 15. Average waiting = (0 + 7 + 9 + 15) / 4 = 7.75 ms. Average turnaround = (8 + 11 + 14 + 24) / 4 = 14.25 ms.
text| P1 | P2 | P4 | P3 | 0 8 12 17 265 Numerical: Solve the same data (P1: 0, 8; P2: 1, 4; P3: 2, 9; P4: 3, 5) with SRTF, the preemptive form of SJF.
mediumAt t = 0 P1 runs. At t = 1 P2 arrives with burst 4, shorter than P1's remaining 7, so P2 preempts. At t = 2 P3 (9) arrives and at t = 3 P4 (5) arrives, but P2's remaining time (3, then 2) is smaller, so P2 continues and finishes at 5. Then P4 (5) runs 5 to 10, P1 (remaining 7) runs 10 to 17, and P3 runs 17 to 26. Turnaround: P1 17, P2 4, P3 24, P4 7. Waiting: P1 17 - 8 = 9, P2 0, P3 15, P4 2. Average waiting = 26 / 4 = 6.5 ms, better than the 7.75 ms of non-preemptive SJF.
text| P1 | P2 | P4 | P1 | P3 | 0 1 5 10 17 266 Numerical: Round robin with quantum 4. P1 (BT 5), P2 (BT 3), P3 (BT 8), all arriving at 0. Find average waiting time and the number of context switches.
mediumThe queue is P1, P2, P3. P1 runs 0 to 4 (1 left), P2 runs 4 to 7 and finishes, P3 runs 7 to 11 (4 left), P1 runs 11 to 12 and finishes, P3 runs 12 to 16 and finishes. Completion times: P1 12, P2 7, P3 16. Since arrival is 0, turnaround equals completion. Waiting = turnaround - burst: P1 12 - 5 = 7, P2 7 - 3 = 4, P3 16 - 8 = 8. Average waiting = 19 / 3 = 6.33 ms. There are 4 switches between the 5 slices.
text| P1 | P2 | P3 | P1 | P3 | 0 4 7 11 12 167 How does the time quantum affect round robin?
mediumWith a very large quantum round robin degenerates to FCFS. With a very small quantum the CPU spends a large fraction of time switching: if a switch costs 1 ms and the quantum is 4 ms, 20 percent of the time is overhead. A common rule of thumb is that about 80 percent of CPU bursts should be shorter than the quantum. Response time improves as the quantum shrinks, turnaround time usually gets worse.
8 Numerical: Preemptive priority scheduling (smaller number means higher priority). P1: AT 0, BT 4, priority 2. P2: AT 1, BT 3, priority 1. P3: AT 2, BT 2, priority 3. Find average waiting time.
mediumP1 starts at 0. At t = 1 P2 arrives with higher priority and preempts. P3 arrives at 2 but has the lowest priority, so P2 runs 1 to 4. At t = 4, P1 (priority 2, 3 units left) beats P3, so P1 runs 4 to 7 and P3 runs 7 to 9. Completion: P1 7, P2 4, P3 9. Turnaround: 7, 3, 7. Waiting: P1 7 - 4 = 3, P2 0, P3 7 - 2 = 5. Average waiting = 8 / 3 = 2.67 ms.
text| P1 | P2 | P1 | P3 | 0 1 4 7 99 What is starvation in priority scheduling and how does aging solve it?
mediumA low-priority process can wait indefinitely if higher-priority processes keep arriving. Aging gradually raises the priority of a process the longer it waits, for example by one level every 15 minutes, so that eventually it is selected. The same problem exists in SJF, where a long job may never run while short ones keep coming.
10 Numerical: SJF needs predicted burst lengths. Using exponential averaging with alpha = 0.5, initial prediction 10 ms, and actual bursts 6 ms then 4 ms, find the next two predictions.
mediumThe formula is tau(n+1) = alpha x t(n) + (1 - alpha) x tau(n). First: tau1 = 0.5 x 6 + 0.5 x 10 = 8 ms. Second: tau2 = 0.5 x 4 + 0.5 x 8 = 6 ms. A larger alpha gives more weight to the most recent burst; alpha = 0 ignores the measured bursts completely, and alpha = 1 uses only the last burst.
11 What is the convoy effect?
mediumWhen one CPU-bound process holds the CPU for a long burst under FCFS, many short or I/O-bound processes queue behind it, the I/O devices sit idle and overall utilisation drops. Using SJF, round robin or a multilevel queue breaks the convoy. The first numerical above shows it: the average wait falls from 17 to 3.
12 Explain multilevel queue and multilevel feedback queue scheduling.
mediumA multilevel queue splits the ready queue into separate queues such as system, interactive and batch, each with its own algorithm, and a fixed way of choosing between queues (strict priority or time slices between them). A process stays in its queue. In multilevel feedback queue scheduling a process can move between queues: a job that uses its full quantum is demoted, and one that blocks early or waits long is promoted. This approximates SJF without knowing burst lengths and favours interactive work.
13 What is highest response ratio next (HRRN)? Give a calculation.
mediumHRRN is a non-preemptive algorithm that picks the ready process with the largest response ratio = (waiting time + burst time) / burst time. It favours short jobs but a long job's ratio keeps growing while it waits, so it avoids starvation. Example at t = 10: A has waited 6 with burst 4, giving (6 + 4) / 4 = 2.5; B has waited 2 with burst 2, giving (2 + 2) / 2 = 2. A is chosen even though B is shorter.
14 What is priority inversion and how is it handled?
mediumPriority inversion happens when a high-priority task is blocked on a lock held by a low-priority task, and a medium-priority task preempts the low one, so the high-priority task waits on the medium one indirectly. The remedy is priority inheritance: the lock holder temporarily runs at the priority of the highest waiter. A famous real case was the 1997 Mars Pathfinder resets, fixed by enabling priority inheritance on the mutex.
15 How does the Linux scheduler decide which task runs next?
hardFor ordinary tasks Linux used the Completely Fair Scheduler (CFS) for many years. It tracks a virtual runtime for each task, keeps runnable tasks in a red-black tree ordered by that value and always picks the leftmost, the task that has received the least CPU relative to its weight. Nice values change the weight. Since Linux 6.6 the EEVDF algorithm replaced CFS, using eligibility and virtual deadlines to improve latency fairness. Real-time classes (SCHED_FIFO, SCHED_RR) run before ordinary tasks.
16 Which scheduling algorithm gives the minimum average waiting time, and what is its limitation?
hardShortest job first, in its preemptive form SRTF when arrivals differ, gives the minimum average waiting time for a given set of processes; this can be shown by an exchange argument, since swapping a longer job ahead of a shorter one only increases total waiting. Its limitation is that burst lengths are not known in advance, so they must be predicted from history, and long jobs can starve.
Frequently asked questions
How do I calculate average waiting time quickly?
Compute completion times from the Gantt chart, subtract arrival time to get turnaround, subtract burst time to get waiting, then average. A check: total waiting equals total turnaround minus total burst.
Which scheduling algorithm is used in real operating systems?
Modern general-purpose systems use priority-based multilevel feedback ideas with time slicing, for example Linux's EEVDF or earlier CFS and the Windows priority-based round robin. Textbook FCFS and SJF are mainly for teaching and for batch systems.
What if two processes arrive at the same time in an exam question?
Break the tie by process number (P1 before P2) unless the question says otherwise. For round robin, say whether a newly arrived process enters the queue before or after the preempted one, then be consistent.
Is response time the same as waiting time?
No. Waiting time is the total time in the ready queue. Response time is only the time until the first run. In FCFS they are equal for each process, but in round robin response time is usually much smaller than waiting time.
Related guides
- Operating Systems Interview Questions with Worked Answers
- Process and Thread Interview Questions with fork() Output Problems
- Process Synchronization Interview Questions: Semaphores, Mutex and Classic Problems
- Deadlock Interview Questions with Banker's Algorithm Worked Example
- Memory Management Interview Questions with Numericals
- Linux Interview Questions and Answers: Concepts, Permissions and Processes
More in CS Fundamentals Interview Questions
- Database Indexing Interview Questions
- DBMS Concurrency Control Interview Questions
- DBMS Interview Questions and Answers
- DBMS Keys Interview Questions
- Deadlock Interview Questions with Banker's Algorithm Worked Example
- Design Patterns Interview Questions with Code
- Distributed Systems Interview Questions
- DNS Interview Questions: Resolution, Record Types, Caching and Troubleshooting
- ER Model Interview Questions
- File System Interview Questions: Inodes, Allocation and Disk Scheduling
- Git Interview Questions and Answers with Commands
- HTTP and HTTPS Interview Questions: Methods, Status Codes, TLS and Caching