Autocoder

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.

FormulasTAT = CT - AT; WT = TAT - BT; RT = first run - AT
Algorithms coveredFCFS, SJF, SRTF, round robin, priority, MLFQ
Numericals6 with full Gantt charts

A checklist for any scheduling numerical

CPU Scheduling Interview Questions with Gantt Chart Numericals: questions with worked answers

  1. 1

    What are the criteria used to compare CPU scheduling algorithms?

    easy

    CPU 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. 2

    Differentiate between preemptive and non-preemptive scheduling.

    easy

    In 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. 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.

    easy

    FCFS 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.

    text
    FCFS: | P1 (0-24) | P2 (24-27) | P3 (27-30) |
    SJF:  | P2 (0-3)  | P3 (3-6)   | P1 (6-30)  |
  4. 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.

    medium

    At 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   26
  5. 5

    Numerical: Solve the same data (P1: 0, 8; P2: 1, 4; P3: 2, 9; P4: 3, 5) with SRTF, the preemptive form of SJF.

    medium

    At 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        26
  6. 6

    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.

    medium

    The 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   16
  7. 7

    How does the time quantum affect round robin?

    medium

    With 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. 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.

    medium

    P1 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       9
  9. 9

    What is starvation in priority scheduling and how does aging solve it?

    medium

    A 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. 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.

    medium

    The 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. 11

    What is the convoy effect?

    medium

    When 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. 12

    Explain multilevel queue and multilevel feedback queue scheduling.

    medium

    A 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. 13

    What is highest response ratio next (HRRN)? Give a calculation.

    medium

    HRRN 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. 14

    What is priority inversion and how is it handled?

    medium

    Priority 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. 15

    How does the Linux scheduler decide which task runs next?

    hard

    For 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. 16

    Which scheduling algorithm gives the minimum average waiting time, and what is its limitation?

    hard

    Shortest 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

More in CS Fundamentals Interview Questions

See all in this section