CPU scheduling: timelines and performance measures
Learning goals and assumptions
Learn to build FCFS, non-preemptive SJF, SRTF and round-robin timelines, then compute completion, turnaround, waiting and response times. Prerequisite: ready/running/blocked states. Every example here uses one CPU execution slot, known positive CPU-burst lengths, zero context-switch overhead, no I/O and no blocking after arrival. These classroom assumptions are not claims about real workloads.
We use half-open intervals [a,b): the process executes for b−a units and finishes that interval at b. All times use the same arbitrary unit. An arrival at time b is available for the scheduling decision at b, not before b.
1. Record four times before calculating
For a process let A be arrival time, B its required CPU service, S the first time it actually runs, and C its completion time.
- Turnaround T = C−A: elapsed time from arrival to completion.
- Response R = S−A: delay until the first CPU service in this lesson's convention.
- Waiting W = T−B: total time ready but not running, under our no-I/O, zero-overhead assumptions.
Response is not completion time and not the sum of every later wait. In a model with blocking I/O, subtracting only CPU service from turnaround also includes blocked time, so it no longer gives ready-queue waiting alone. In broader systems, “response time” may refer to first externally observable output; always read the stated convention.
A quick consistency check is A≤S≤C and W≥0. The sum of all CPU execution intervals for each process must equal its burst B. Never average completion times and call the result average turnaround unless all arrivals are zero.
2. One workload, different policies
Use P1:(A=0,B=5), P2:(A=1,B=3), P3:(A=2,B=1). For any equal-choice tie, prefer earlier arrival, then lower process number. These are original teaching examples, not past-exam questions.
FCFS (first come, first served) is non-preemptive here. P1 starts at 0 and finishes at 5, although P2 and P3 arrive meanwhile. Then P2 runs and finally P3:
[0,5) P1; [5,8) P2; [8,9) P3.
| Process | S | C | T=C−A | W=T−B | R=S−A |
|---|---|---|---|---|---|
| P1 | 0 | 5 | 5 | 0 | 0 |
| P2 | 5 | 8 | 7 | 4 | 4 |
| P3 | 8 | 9 | 7 | 6 | 6 |
Average waiting is (0+4+6)/3=10/3. For this one-burst non-preemptive model, W=R for each process. That equality is not a universal rule.
3. Non-preemptive SJF is not SRTF
Shortest job first (SJF), as used here, chooses the shortest burst among processes ready when a new dispatch is needed. At 0 only P1 is ready, so it must start. Later arrivals do not interrupt it. At 5, P3's burst 1 is shorter than P2's burst 3:
[0,5) P1; [5,6) P3; [6,9) P2.
Completion times in P1,P2,P3 order are 5,9,6. Turnarounds are 5,8,4 and waiting times are 0,5,3. Average waiting is 8/3. The shortest job does not always run first: it must already have arrived, and a non-preemptive job already running is not interrupted.
Shortest remaining time first (SRTF) is preemptive. Reconsider when a process arrives or a running process finishes. At time 1, P1 has 4 remaining while newly arrived P2 needs 3, so P2 replaces P1. At time 2, P2 has 2 remaining while P3 needs 1, so P3 replaces P2:
[0,1) P1; [1,2) P2; [2,3) P3; [3,5) P2; [5,9) P1.
Completion times are 9,5,3; turnarounds are 9,4,1; waiting times are 4,1,0. Average waiting is 5/3. All first starts equal arrivals, so all response times are 0, even though P1 waits 4 units later. Compare remaining service, not original service, when making SRTF decisions. Equal remaining times do not automatically require a switch; follow the declared tie rule.
4. Round robin: track the queue explicitly
Round robin (RR) gives the head of the ready queue at most one quantum q. An unfinished process whose quantum expires joins the tail. A process that finishes earlier releases the CPU immediately; unused quantum time is not reserved for it. Arrivals append to the queue. Here q=2, and arrivals exactly at a quantum boundary join the queue before the just-expired process is requeued.
- 0–2: P1 runs, leaving 3 units. P2 arrived at 1; P3 arrives at 2. Queue becomes P2,P3,P1.
- 2–4: P2 runs, leaving 1. Queue becomes P3,P1,P2.
- 4–5: P3 finishes after 1 unit. Queue is P1,P2.
- 5–7: P1 runs, leaving 1. Queue becomes P2,P1.
- 7–8: P2 finishes. Then P1 finishes on 8–9.
Completion times are 9,8,5. Turnarounds are 9,7,3; waiting times are 4,4,2; response times are 0,1,2. Therefore average waiting=10/3 and average response=1. The equality of RR and FCFS average waiting here is a property of this workload, not a general result. A smaller quantum does not guarantee lower average turnaround and, in real systems, increases the importance of switching overhead.
5. Idle gaps and workload limits
If the only jobs are X:(A=2,B=2) and Y:(A=6,B=1), the CPU is idle on [0,2), runs X on [2,4), is idle on [4,6), then runs Y on [6,7). Each job has zero waiting time. Utilization over [0,7) is 3/7; over [2,7) it is 3/5. A utilization answer without its measurement window is incomplete.
SJF's familiar average-waiting optimality statement needs assumptions, such as all jobs available together, known service times and the relevant non-preemptive model. Do not extrapolate a small trace into a theorem for all arrival patterns, priorities or interactive workloads. This lesson also does not cover I/O scheduling, priority scheduling, multilevel feedback queues or starvation remedies.
A reliable exam method
- Write arrivals, bursts, policy, quantum, tie rule and overhead assumptions.
- At each event, update remaining work and the eligible set or queue.
- Mark every run interval and idle interval; verify total executed service.
- Extract S and C from the timeline before computing T,W,R.
- Average the requested metric, not whichever column is easiest.
Typical errors are letting an unarrived job run, preempting under non-preemptive SJF, comparing original bursts under SRTF, restarting a finished RR job, omitting idle time, and treating response as turnaround.
Original practice: six single-correct MCQs
Original questions, not previous-year questions. Choose exactly one option. All question assumptions continue to apply.
C01. P1:(arrival 0, burst 5), P2:(arrival 1, burst 3), P3:(arrival 2, burst 1) run under non-preemptive FCFS with zero overhead and no I/O. What is the average waiting time?
A. 10/3 B. 19/3 C. 7/3 D. 4
Answer: A
A: Starts are 0,5,8, so waits are 0,4,6 and the average is 10/3.
B: 19/3 is the average turnaround: (5+7+7)/3, not waiting.
C: This is not the sum of the correctly traced ready waits divided by three.
D: Four is P2's waiting time alone, not the average of all three.
C02. With the same arrivals and bursts, what is the non-preemptive SJF execution order?
A. P3, P2, P1 B. P1, P2, P3 C. P1, P3, P2 D. P2, P1, P3
Answer: C
A: P3 has not arrived at time 0, so it cannot run first.
B: After P1 finishes, P3 is the shorter ready job and precedes P2.
C: P1 is alone at time 0; at time 5 choose P3's burst 1 before P2's burst 3.
D: P2 has not arrived at time 0, while P1 is already available.
C03. For the same workload under SRTF, what is P1's total waiting time?
A. 0 B. 1 C. 5 D. 4
Answer: D
A: Zero is P1's response time, not its later accumulated waiting.
B: P1 executes one unit initially; this is not its waiting.
C: Five is P1's required CPU service.
D: P1 runs 0–1, waits 1–5, then runs 5–9: waiting is 4, also 9−0−5=4.
C04. For the same workload, RR uses quantum 2 and arrivals at a boundary join before the expired process is requeued. What are completion times in P1,P2,P3 order?
A. 5, 8, 9 B. 9, 8, 5 C. 9, 5, 3 D. 9, 9, 5
Answer: B
A: These are the FCFS completion times, not RR.
B: Trace P1 0–2, P2 2–4, P3 4–5, P1 5–7, P2 7–8, P1 8–9.
C: These are the SRTF completion times, not this RR queue trace.
D: P2 has only one unit remaining at 7 and finishes at 8; it does not consume a full unused quantum.
C05. A process arrives at 3, first runs at 5, requires 4 total CPU units and finishes at 12. There is no I/O or overhead. What are turnaround, waiting and response, respectively?
A. 12, 8, 5 B. 9, 2, 5 C. 9, 5, 2 D. 7, 3, 2
Answer: C
A: These values fail to subtract arrival time from completion and first-start times.
B: Waiting and response have been exchanged; later waits also count in waiting.
C: T=12−3=9; W=9−4=5; R=5−3=2.
D: Seven is completion minus first start, which excludes the initial delay and is not turnaround.
C06. Only X:(arrival 2, burst 2) and Y:(arrival 6, burst 1) exist, with zero overhead and immediate dispatch when ready. What fraction of [0,7) is the CPU busy?
A. 3/7 B. 3/5 C. 1 D. 4/7
Answer: A
A: Total CPU service is 2+1=3 over the specified seven-unit window.
B: 3/5 uses the different window [2,7), omitting the initial idle interval.
C: There is idle time on both [0,2) and [4,6).
D: 4/7 is the idle fraction, not the busy fraction.
Sources and scope
This original introductory lesson aligns with Section 8, Operating System, of the official GATE 2027 CS syllabus. It does not complete OS or the full syllabus. The syllabus verifies topic relevance; the primary textbook references verify foundational concepts. Examples, timelines and practice are original.
Sources checked 2026-10-14.
Sign in to keep your progress. Sign in