Neural Sync Active

CPU Scheduling — FCFS, SJF, SRTF

Registry Synced

CPU Scheduling — FCFS, SJF, SRTF

1249 words

6 min read

Reading compass

Now · 🎯 Learning Objectives

CPU Scheduling — FCFS, SJF, SRTF

🎯 Learning Objectives

Calculate turnaround time, waiting time, and response time for any scheduling algorithm
Trace FCFS, SJF (preemptive and non-preemptive) with Gantt charts
Identify the convoy effect and its impact on average waiting time
Explain why SJF is optimal in terms of average waiting time

1. Scheduling Fundamentals

1.1 Intuition

CPU scheduling decides which process gets the CPU next. The OS scheduler (short-term scheduler) runs whenever the CPU becomes idle — typically every few milliseconds. Good scheduling makes the system feel responsive (low response time) while maximizing throughput.

1.2 Scheduling Criteria

Criterion	Formula	Goal
CPU Utilization	`busy_time / total_time`	Maximize (keep CPU busy)
Throughput	`processes_completed / time`	Maximize
Turnaround Time (TAT)	`completion_time - arrival_time`	Minimize
Waiting Time (WT)	`turnaround_time - burst_time`	Minimize
Response Time	`first_response_time - arrival_time`	Minimize (for interactivity)

(Diagram)

1.3 Scheduling Decision Points

Process switches from Running → Waiting (I/O request)
Process switches from Running → Ready (interrupt/timer)
Process switches from Waiting → Ready (I/O complete)
Process terminates

2. First-Come, First-Served (FCFS)

2.1 Intuition

The simplest algorithm: the first process to arrive gets the CPU first (like a queue at a ticket counter). Non-preemptive — once a process gets the CPU, it keeps it until it terminates or does I/O.

2.2 Worked Example 1

Processes:

Process	Arrival Time	Burst Time
P1	0	24
P2	0	3
P3	0	3

Gantt Chart:


pseudo
|   P1 (24)  |  P2 (3)  |  P3 (3)  |
0            24         27         30

Calculations:

Process	BT	Start	End	TAT (End-AT)	WT (TAT-BT)
P1	24	0	24	24	0
P2	3	24	27	27	24
P3	3	27	30	30	27

Average TAT = (24 + 27 + 30) / 3 = 27 Average WT = (0 + 24 + 27) / 3 = 17

2.3 Worked Example 2: Convoy Effect

Processes:

Process	Arrival Time	Burst Time
P1	0	10
P2	0	1
P3	0	1

Gantt Chart:


pseudo
|   P1 (10)  |  P2 (1)  |  P3 (1)  |
0            10         11         12

Average WT = (0 + 10 + 11) / 3 = 7 The convoy effect occurs when short processes wait behind a long one. If P2 and P3 (short) arrived right after P1 started, they still wait 10 units.

2.4 Worked Example 3: Non-zero Arrival Times

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

Gantt Chart:


pseudo
|   P1 (7)   |  P2 (4)  | P3(1) |  P4 (4)  |
0             7          11     12         16

Tracing Table:

Step	Time	Ready Queue	Running	Event
1	0	P1	P1	P1 starts
2	2	P1's turn, P2 arrives	P1 continues	P2 ready
3	4	P2, P3 arrives	P1 continues	P3 ready
4	5	P2, P3, P4 arrives	P1 continues	P4 ready
5	7	P2, P3, P4	P2 starts	P1 done
6	11	P3, P4	P3 starts	P2 done
7	12	P4	P4 starts	P3 done
8	16	--	--	P4 done

Average TAT = (7 + 9 + 8 + 11) / 4 = 8.75 Average WT = (0 + 5 + 7 + 7) / 4 = 4.75

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

3.1 Intuition

The process with the smallest total burst time runs next. SJF is provably optimal in terms of average waiting time — but requires knowing burst times in advance (usually estimated using exponential averaging).

3.2 Worked Example

Using the same processes as Example 3 above:

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

Gantt Chart:


pseudo
|   P1 (7)   |  P3 (1)  |  P2 (4)  |  P4 (4)  |
0             7          8          12         16

Tracing Table:

Step	Time	Ready Queue	Running	Event
1	0	P1	P1	P1 starts
2	2	P2 (BT=4)	P1 continues	P2 arrives
3	4	P2(BT=4), P3(BT=1)	P1 continues	P3 arrives
4	5	P2(BT=4), P3(BT=1), P4(BT=4)	P1 continues	P4 arrives
5	7	P2(4), P3(1), P4(4)	P3 starts	P1 done; SJF picks P3
6	8	P2(4), P4(4)	P2 starts	P3 done; SJF picks P2 (or P4)
7	12	P4(4)	P4 starts	P2 done
8	16	--	--	P4 done

Calculations:

Process	AT	BT	Start	End	TAT	WT
P1	0	7	0	7	7	0
P3	4	1	7	8	4	3
P2	2	4	8	12	10	6
P4	5	4	12	16	11	7

Average TAT = (7 + 10 + 4 + 11) / 4 = 8.0 Average WT = (0 + 6 + 3 + 7) / 4 = 4.0 Compare with FCFS: WT was 4.75, now 4.0 — SJF is better!

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

4.1 Intuition

SRTF is the preemptive version of SJF. When a new process arrives with a remaining burst time smaller than the currently running process, the scheduler preempts the current process.

4.2 Worked Example

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

Gantt Chart:


pseudo
| P1(1) | P2(1) | P3(1) | P4(1) | P2(3)  |   P1(7)   |
0       1       2       3       4        7          14

Tracing Table:

Step	Time	Event	Ready Queue (remaining)	Running
1	0	P1 arrives	--	P1(8) starts
2	1	P2 arrives (BT=4 < P1's 7)	P1(7)	P2(4) preempts
3	2	P3 arrives (BT=2 < P2's 3)	P1(7), P2(3)	P3(2) preempts
4	3	P4 arrives (BT=1 < P3's 1)	P1(7), P2(3), P3(1)	P4(1) preempts
5	4	P4 done	P1(7), P2(3), P3(1)	P3(1) resumes
6	5	P3 done	P1(7), P2(3)	P2(3) resumes
7	7	P2 done	P1(7) (remaining 7)	P1(7) resumes
8	14	P1 done	--	--

Calculations:

Process	AT	BT	End	TAT	WT
P1	0	8	14	14	6
P2	1	4	7	6	2
P3	2	2	5	3	1
P4	3	1	4	1	0

Average TAT = (14 + 6 + 3 + 1) / 4 = 6.0 Average WT = (6 + 2 + 1 + 0) / 4 = 2.25 SRTF gives the best average waiting time of any algorithm, but can cause starvation (long processes may never run).

5. Common Pitfalls

Pitfall 1: Confusing preemptive and non-preemptive

Mistake: Applying SJF selection only at new arrivals (should also check remaining time for SRTF). Fix: In SRTF, after every new arrival, compare the new process's burst time with the remaining time of the running process.

Pitfall 2: Forgetting to update remaining time

Mistake: In SRTF tracing, treating remaining time as original burst time. Fix: Maintain a column showing remaining burst time after each time unit.

Pitfall 3: Ignoring arrival times

Mistake: Sorting all processes by burst time regardless of when they arrive. Fix: Only processes that have arrived by the current time can be scheduled.

6. 📐 Key Formulas / Concepts

Concept	Formula	Notes
Turnaround Time	`TAT = C - A`	Completion time - Arrival time
Waiting Time	`WT = TAT - BT`	Turnaround time - Burst time
Response Time	`RT = start - A`	First CPU time - Arrival time
Convoy Effect	Short process waits behind long process	Problem with FCFS
SJF Optimality	SJF minimizes average WT	Only if all processes arrive simultaneously

7. 📝 Practice Questions

Q1: Three processes P1 (BT=6), P2 (BT=8), P3 (BT=7) arrive at time 0. Compute average TAT and WT for FCFS in order P1, P2, P3.

Gantt: P1(0-6), P2(6-14), P3(14-21)

Process	TAT	WT
P1	6	0
P2	14	6
P3	21	14

Avg TAT = (6+14+21)/3 = 13.67 Avg WT = (0+6+14)/3 = 6.67 Q2: Same processes as Q1, compute for SJF.

Order: P1(6), P3(7), P2(8)

Process	TAT	WT
P1	6	0
P3	13	6
P2	21	13

Avg TAT = (6+13+21)/3 = 13.33 Avg WT = (0+6+13)/3 = 6.33 Q3: What is the convoy effect? Provide a concrete example.

Answer: The convoy effect describes the situation where a long CPU-bound process holds the CPU while many short processes wait. Example: P1(BT=10), P2(BT=1), P3(BT=1) with FCFS — average WT = (0+10+11)/3 = 7. If they ran in order P2, P3, P1, average WT = (0+1+2)/3 = 1. Q4: Why is SJF called "provably optimal"?

Answer: SJF minimizes average waiting time for a given set of processes assuming they all arrive at the same time. The proof shows that any swap of a short process with a longer one in the schedule increases the average waiting time. Q5: Processes P1(AT=0, BT=5), P2(AT=1, BT=3), P3(AT=2, BT=3), P4(AT=3, BT=1). Compute SRTF average WT.

Gantt: P1(0-1), P2(1-3), P3(3-4), P4(4 passes...). Let me trace properly:

Time	Running	Ready Queue (rem)
0	P1(5)	--
1	P2(3) [P1 has 4, P2 has 3 < 4]	P1(4)
2	P3(3) [P2 has 2, P3 has 3 > 2? No!]	Wait, P2 ran from 1-2, remaining=2. P3(3) > P2(2), so P2 continues
2	P2(2)	P1(4), P3(3)
3	P4(1) [P2 has 1, P4(1)=P2's 1, tie - let P4 run]	P1(4), P2(1), P3(3)
4	P2(1)	P1(4), P3(3)
5	P3(3)	P1(4)
8	P1(4)	--
12	--	--

WT: P1=7, P2=1, P3=3, P4=0 → Avg WT = 11/4 = 2.75

8. 🔗 Cross-References

Week 4 - MLFQ: Multilevel Feedback Queue builds on SJF concepts
Week 5 - Synchronization: Priority inversion problem
BSCS4021 (Advanced Algorithms): Scheduling theory Join Discord Previousxv6 Booting & System CallsNextCPU Scheduling: RR, Priority, MLFQ