How do you calculate average waiting time for FCFS?

For FCFS: list processes in arrival order. Completion time of P1 = burst time. Completion of P2 = completion of P1 + burst of P2 (if P2 arrived before P1 finished). Waiting time = turnaround time - burst time. Turnaround time = completion time - arrival time. Average waiting time = sum of all waiting times / number of processes.

What is the difference between SJF and SRTF?

SJF (Shortest Job First) is non-preemptive — once a process starts executing, it runs to completion. SRTF (Shortest Remaining Time First) is the preemptive version — if a new process arrives with shorter remaining burst time than the current process, the current process is preempted. SRTF gives minimum average waiting time among all scheduling algorithms.

What is convoy effect in FCFS scheduling?

Convoy effect occurs in FCFS when a long CPU-bound process holds the CPU while many short I/O-bound processes wait in the ready queue. This leads to poor CPU and I/O device utilisation. All shorter processes must wait behind one long process — like cars stuck behind a slow truck on a single-lane road.

How does Round Robin scheduling handle time quantum selection?

If time quantum is too large, Round Robin degenerates to FCFS. If too small, context switch overhead dominates (excessive overhead). Optimal quantum: large enough to minimize context switch overhead but small enough for reasonable response time. Typical values: 10–100ms. Rule of thumb: 80% of CPU bursts should be shorter than the quantum.

CPU Scheduling for GATE CS

FCFS, SJF, SRTF, Round Robin, Priority scheduling — Gantt charts, waiting time, turnaround time with complete GATE-level numerical examples.

Last updated: April 2026 | GATE CS 2024–2026 syllabus

Key Takeaways for GATE

TAT = Completion Time − Arrival Time. WT = TAT − Burst Time.
FCFS: non-preemptive, simple, convoy effect. Worst average WT when short jobs follow long ones.
SJF: minimum average WT among non-preemptive algorithms. Starvation of long jobs possible.
SRTF (preemptive SJF): minimum average WT among ALL algorithms. Most complex to implement.
Round Robin: fair, best for time-sharing. No starvation. Performance depends on time quantum.
Priority: lower number = higher priority (GATE convention unless stated). Starvation solved by aging.
Multilevel Queue: separate queues for different process classes (foreground/background), each with own algorithm.

1. Scheduling Metrics

Turnaround Time (TAT) = Completion Time − Arrival Time
Waiting Time (WT) = TAT − Burst Time = time spent in ready queue
Response Time = Time of first CPU allocation − Arrival Time
CPU Utilisation = CPU busy time / Total elapsed time × 100%
Throughput = Number of processes completed / Unit time

Goal: maximise CPU utilisation & throughput; minimise TAT, WT, response time.

2. FCFS — First Come First Served

Non-preemptive. Processes served in arrival order. Simple but can cause convoy effect.

Example:

Process	Arrival	Burst	Completion	TAT	WT
P1	0	5	5	5	0
P2	1	3	8	7	4
P3	2	8	16	14	6

Gantt chart: | P1 (0–5) | P2 (5–8) | P3 (8–16) |
Avg TAT = (5+7+14)/3 = 8.67 Avg WT = (0+4+6)/3 = 3.33

Convoy effect: One CPU-bound process with large burst time makes all shorter processes wait. Like slow truck on single-lane road. Leads to low CPU and I/O utilisation.

3. SJF — Shortest Job First (Non-preemptive)

Among processes in ready queue at dispatch time, pick the one with shortest burst time. Non-preemptive — runs to completion once started.

Example: (same processes as above)

Process	Arrival	Burst	Completion	TAT	WT
P1	0	5	5	5	0
P2	1	3	8	7	4
P3	2	8	16	14	6

At t=0, only P1 available → runs. At t=5, both P2 (burst=3) and P3 (burst=8) available → P2 chosen.
Gantt: | P1(0–5) | P2(5–8) | P3(8–16) |
Same as FCFS here because P1 arrived first and no shorter job was ready at t=0.

Starvation: Long jobs may wait indefinitely if short jobs keep arriving. Solution: aging (gradually increase priority of waiting processes).

4. SRTF — Shortest Remaining Time First (Preemptive SJF)

When a new process arrives, if its burst time < remaining time of current process, preempt current process. Gives minimum average waiting time.

Example:

Process	Arrival	Burst
P1	0	8
P2	1	4
P3	2	2
P4	3	1

Trace:
t=0: P1 starts (only one). Remaining P1=8.
t=1: P2 arrives (burst=4 < P1 remaining=7). Preempt P1. P2 runs. Remaining P1=7, P2=4.
t=2: P3 arrives (burst=2 < P2 remaining=3). Preempt P2. P3 runs.
t=3: P4 arrives (burst=1 < P3 remaining=1). Preempt P3. P4 runs.
t=4: P4 done. P3 remaining=1 runs (shortest). t=5: P3 done. P2 remaining=3. t=8: P2 done. P1 remaining=7. t=15: P1 done.

Gantt: |P1(0–1)|P2(1–2)|P3(2–3)|P4(3–4)|P3(4–5)|P2(5–8)|P1(8–15)|
WT: P1=8–1=7(time not running), P2=(1–1)+(5–2)=3, P3=(2–2)+(4–3)=1, P4=3–3=0
Wait properly: WT=TAT–Burst. TAT: P1=15–0=15, P2=8–1=7, P3=5–2=3, P4=4–3=1.
WT: P1=15–8=7, P2=7–4=3, P3=3–2=1, P4=1–1=0. Avg WT=(7+3+1+0)/4=2.75

5. Round Robin (RR)

Each process gets a fixed time quantum q. After quantum expires, process is preempted and goes to end of ready queue. Best for time-sharing systems.

Example (q = 2):

Process	Arrival	Burst
P1	0	5
P2	0	3
P3	0	4

Queue order (all arrive at 0): P1, P2, P3
Gantt: |P1(0–2)|P2(2–4)|P3(4–6)|P1(6–8)|P2(8–9)|P3(9–11)|P1(11–12)|
Completion: P1=12, P2=9, P3=11
TAT: P1=12, P2=9, P3=11. WT: P1=7, P2=6, P3=7. Avg WT=6.67

Effect of time quantum:
q → ∞: degenerates to FCFS.
q → 0: theoretical ideal (processor sharing), huge context switch overhead in practice.
Optimal: 80% of bursts finish within 1 quantum.

No starvation in Round Robin — every process gets CPU within at most (n−1)×q time units where n = number of processes.

6. Priority Scheduling

Each process has a priority. CPU allocated to highest priority process.
Convention: Lower number = higher priority (GATE default unless stated).
Can be preemptive or non-preemptive.

Starvation (indefinite blocking): Low-priority process may never execute if high-priority processes keep arriving.
Solution — Aging: Gradually increase priority of waiting processes. After waiting time T, priority increases by 1.

SJF is a special case of priority scheduling where priority = 1/burst_time.

7. Multilevel Queue & Multilevel Feedback Queue

Multilevel Queue: Ready queue partitioned into multiple queues (e.g., foreground/interactive and background/batch). Each queue has its own scheduling algorithm. Queue itself has priority (foreground over background).
Processes permanently assigned to one queue — no movement between queues.

Multilevel Feedback Queue (MLFQ):
Processes can move between queues based on behaviour.
New processes start in highest-priority queue (short quantum).
If process uses full quantum → moved down (lower priority, longer quantum).
If process waits too long → moved up (aging, prevents starvation).
Most flexible but most complex. Used by many real OS schedulers.

8. Algorithm Comparison

Algorithm	Preemptive?	Starvation?	Avg WT	Best For
FCFS	No	No	Worst	Batch systems
SJF	No	Yes (long jobs)	Minimum (non-preemptive)	Batch, known burst times
SRTF	Yes	Yes (long jobs)	Minimum (overall)	Theoretical optimum
Round Robin	Yes	No	Depends on quantum	Time-sharing, interactive
Priority (non-preemptive)	No	Yes	Depends	Real-time (with priority)
Priority (preemptive)	Yes	Yes	Depends	Real-time systems
MLFQ	Yes	No (with aging)	Good	General purpose OS

9. GATE Examples

GATE 2019 — Round Robin (q=3):

Process	Arrival	Burst
P1	0	6
P2	0	4
P3	0	2

Gantt: |P1(0–3)|P2(3–6)|P3(6–8)|P1(8–11)|P2(11–12)|
Completion: P1=11, P2=12, P3=8.
WT: P1=11–6=5, P2=12–4=8, P3=8–2=6. Avg WT = (5+8+6)/3 = 6.33

GATE 2021 — SRTF:

Process	Arrival	Burst
P1	0	7
P2	2	4
P3	4	1
P4	5	4

t=0: P1 starts. t=2: P2 (rem=4) < P1 rem=5 → preempt. t=4: P3(1) < P2 rem=2 → preempt. t=5: P3 done. P2 rem=2 < P4=4 → P2. t=7: P2 done. P4 vs P1(rem=5): P4=4 wins. t=11: P4 done. P1(rem=5). t=16: P1 done.
Gantt: |P1(0–2)|P2(2–4)|P3(4–5)|P2(5–7)|P4(7–11)|P1(11–16)|
TAT: P1=16, P2=5, P3=1, P4=6. WT: P1=9, P2=1, P3=0, P4=2. Avg WT=3

GATE 2023 — Which algorithm has minimum average waiting time?
For any given set of processes, SRTF (preemptive SJF) always produces minimum average waiting time.
Answer: SRTF

10. Common Mistakes

Forgetting idle CPU time in Gantt chart: If no process is ready at some time t, the CPU is idle. This must be shown in the Gantt chart. Completion time calculation is affected — next process starts when it arrives, not immediately after previous.
SJF tie-breaking: When two processes have the same burst time, GATE usually says use FCFS order (lower process number or earlier arrival). Always check the problem statement.
Round Robin queue order: When a process uses its full quantum and a new process arrives at the same time step, the arriving process typically joins the queue first (implementation-defined — GATE usually specifies).
Waiting time vs response time: Waiting time = total time in ready queue. Response time = time until first CPU allocation. For non-preemptive algorithms, they may be equal. For RR, response time < waiting time for long processes.
SRTF with equal remaining time: If two processes have the same remaining burst time when a preemption decision is made, GATE uses FCFS order among tied processes.

11. FAQ

How do you calculate average waiting time for FCFS?: Step 1: List processes in arrival order. Step 2: Compute completion time for each (P1 finishes at burst time if arrival=0; each subsequent process finishes when previous finishes + its own burst, assuming no idle gap). Step 3: TAT = Completion − Arrival. Step 4: WT = TAT − Burst. Step 5: Average WT = sum / n. For idle gaps (when CPU waits for next arrival), adjust completion times accordingly.
What is the difference between SJF and SRTF?: SJF is non-preemptive: once dispatched, the process runs to completion, even if a shorter job arrives. The scheduling decision is made only when the CPU becomes free. SRTF is preemptive SJF: whenever a new process arrives, if its burst time is less than the remaining burst time of the current process, the current process is preempted. SRTF gives the globally minimum average waiting time but causes more context switches and potential starvation of long jobs.
What is convoy effect in FCFS scheduling?: Convoy effect is when a large CPU-bound process (long burst) reaches the front of the ready queue, causing all shorter processes behind it to wait for a long time. This is analogous to a convoy of cars stuck behind a slow truck. The result is high average waiting time, and both CPU and I/O devices are poorly utilised (I/O-bound processes queue up, I/O devices sit idle while the long CPU job runs).
How does Round Robin scheduling handle time quantum selection?: If quantum is too large (larger than most burst times), RR behaves like FCFS — processes run to completion before being preempted. If quantum is too small, the overhead of context switches dominates useful work. The optimal quantum should be larger than most interactive CPU bursts (so short jobs finish in one quantum) but small enough to give acceptable response time. The rule of thumb: ~80% of CPU bursts should be shorter than one time quantum.

CPU Scheduling for GATE CS – FCFS, SJF, Round Robin, Priority | EngineeringHulk