FCFS & Round Robin Scheduling: Gantt Charts & Time Quantum
“Explore the Convoy Effect, Time Quantum trade-offs, and live Gantt charts.”
1.FCFS & The Convoy Effect
§ 3.1.First-Come, First-Served (FCFS) is the simplest non-preemptive algorithm: whoever arrives first in the ready queue is given the CPU until completion.
The Convoy Effect: If a long CPU-bound process arrives first, all subsequent short I/O-bound processes are forced to wait behind it. This drastically drags down average waiting time and leaves I/O devices sitting idle.
2.Round Robin (RR) with Time Quantum
§ 3.2.Round Robin (RR) is designed specifically for time-sharing systems. The CPU is allocated to each ready process for a small slice of time called the Time Quantum (q).
If the process's burst exceeds q, it is preempted and inserted at the tail of the Ready Queue.
If q is extremely large (q → ∞), RR degenerates into simple FCFS. If q is extremely small (q → 0), context-switch overhead dominates.
3. Solved Numerical: Round Robin Gantt Chart & Waiting Time
| P1 (AT, BT)AT = 0 ms, BT = 5 ms | P2 (AT, BT)AT = 1 ms, BT = 3 ms | P3 (AT, BT)AT = 2 ms, BT = 1 ms | Time Quantum (q)q = 2 ms |
At t=0, only P1 has arrived → P1 runs for full quantum q=2 (remaining BT = 3). During this interval, P2 arrives at t=1, and P3 arrives at exactly t=2. Crucial Invariant: When P1 quantum expires at t=2, newly arrived P3 enters the queue BEFORE preempted P1. Queue becomes: [P2, P3, P1].
t=2 to 4: P2 runs for 2 ms (remaining BT = 1). Re-queued at tail. Ready Queue becomes: [P3, P1, P2]. t=4 to 5: P3 needs only 1 ms ≤ q. It runs for 1 ms and terminates at t=5. Calls exit(), no re-queueing! Ready Queue becomes: [P1, P2].
t=5 to 7: P1 runs for 2 ms (remaining BT = 1). Queue: [P2, P1]. t=7 to 8: P2 runs for its final 1 ms and terminates at t=8. Queue: [P1]. t=8 to 9: P1 runs for its final 1 ms and terminates at t=9.
Using standard OS formulas: TAT = CT - AT and WT = TAT - BT. P1: CT = 9, TAT = 9 - 0 = 9 ms, WT = 9 - 5 = 4 ms. P2: CT = 8, TAT = 8 - 1 = 7 ms, WT = 7 - 3 = 4 ms. P3: CT = 5, TAT = 5 - 2 = 3 ms, WT = 3 - 1 = 0 ms.
4. Interactive CPU Scheduling & Gantt Chart Simulator
Interact with real processes. Switch between FCFS and Round Robin, adjust the time quantum, and observe how the Gantt chart and waiting times automatically recompute.
Real-time CPU Scheduler & Gantt Chart Simulator
| Process | Arrival (AT) | Burst (BT) | Completion (CT) | Turnaround (TAT) | Waiting (WT) |
|---|---|---|---|---|---|
| P1 | 0 ms | 5 ms | 11 ms | 11 ms | 6 ms |
| P2 | 1 ms | 3 ms | 10 ms | 9 ms | 6 ms |
| P3 | 2 ms | 1 ms | 5 ms | 3 ms | 2 ms |
| P4 | 3 ms | 2 ms | 9 ms | 6 ms | 4 ms |
Interactive simulation supporting all classic scheduling algorithms: FCFS, SJF (Non-preemptive), SRTF (Preemptive SJF), Priority (Preemptive & Non-preemptive), Round Robin, LJF, LRTF, and HRRN.
5. GATE Lens & Verified PYQ
Syllabus focus, recurring numerical patterns, common traps, and clearly labelled exam practice. Questions remain source-pending until an official paper and answer key are attached.
Round Robin with arrival time tie-breaks is one of the most common 2-mark numerical question patterns in GATE CS.
- •A process finishing exactly at its quantum boundary: it finishes execution and does NOT re-enter the queue.
- •Simultaneous arrival: if a new process arrives at time t exactly when an executing process is preempted, by standard convention the newly arrived process enters the Ready Queue FIRST, followed by the preempted process.
- •Forgetting the tie-breaking arrival order in the Ready queue.
Exam Practice / Source Verification Required
1 problemConsider three processes P1, P2, and P3 arriving at time 0, 1, and 2 with burst times 5, 3, and 1 respectively. Using Round Robin scheduling with time quantum q = 2, what is the average waiting time (in ms)?
6. 1-Minute Panic Revision
“FCFS = Non-preemptive, Convoy Effect. RR = Preemptive with Quantum q. Low q → high overhead; High q → FCFS.”
- •If new process arrives at time t when P is preempted: New arrival queued before preempted process.
- •If burst <= quantum, process finishes early and next process dispatches immediately.
- •Do not allow quantum to expire if process has less than q time remaining.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Official slides covering FCFS convoy effect, RR time slice quantum selection, and context switch costs.
Full chapter analyzing response time tradeoffs between FIFO and Round Robin with Gantt charts.
If the textbook derivation did not click immediately, consult these targeted video lessons:
Demonstrates exactly how to maintain the ready queue without ordering bugs during preemption boundaries.
Walks through FCFS step-by-step with CT, TAT, WT and explains why CPU-bound jobs stall I/O devices.
Curated lectures on Gantt Charts, Preemption, FCFS Convoy Effect, Round Robin Quantum & SJF/SRTF:
Step-by-step Gantt chart calculations with zero arithmetic ambiguity.
The most reliable demonstration of ready-queue tracking during simultaneous arrivals.
Structured textbook-level coverage with cleanly paced whiteboard walkthroughs.
Intense numerical speed practice and identifying examiner traps in Gantt charts.