CPU Scheduling

What is response time?

Time from arrival until the process first gets the CPU

What is wait time?

Total time a process spends in the ready queue

What is turnaround time?

Time from arrival to completion

Response time formula?

First CPU start time − arrival time

Turnaround time formula?

Finish time − arrival time

Wait time formula?

Turnaround time − total CPU burst time

Which scheduling minimizes average turnaround time?

SJN / SRTF

Which scheduling is most fair?

Round Robin

Which scheduling risks starvation?

SJN

What must you draw first to solve scheduling problems?

A Gantt chart (timeline)

Common exam mistake in wait time?

Forgetting to subtract CPU burst from turnaround time

Given FIFO scheduling, when does a process wait?

When earlier-arriving processes are running

FIFO example: P1 arrives at 0 (5ms), P2 arrives at 2 (3ms). What is P2's response time?

P2 starts at 5 → response time = 5 − 2 = 3ms

FIFO example: P1 (5ms at 0), P2 (3ms at 2). What is P2's turnaround time?

Finishes at 8 → turnaround = 8 − 2 = 6ms

FIFO example: P1 (5ms at 0), P2 (3ms at 2). What is P2's wait time?

Turnaround 6 − burst 3 = 3ms

RR example: Quantum = 2ms. P1(4ms,0), P2(3ms,0). What is P2's response time?

P1 runs first (0–2), P2 starts at 2 → response = 2ms

RR example: Quantum = 2ms. P1(4ms,0), P2(3ms,0). What is P2's turnaround time?

Schedule: P1 0–2, P2 2–4, P1 4–6, P2 6–7 → turnaround = 7 − 0 = 7ms

RR example: Quantum = 2ms. P1(4ms,0), P2(3ms,0). What is P2's wait time?

Turnaround 7 − burst 3 = 4ms

SJN example: P1(6ms,0), P2(2ms,0), P3(4ms,0). What runs first?

P2 → P3 → P1

SJN definition?

Runs the process with the shortest CPU burst first

SJN example: P1(6ms,0), P2(2ms,0), P3(4ms,0). What is P1's wait time?

P1 waits for P2 and P3 → 2 + 4 = 6ms

SRTF definition?

Preemptive version of SJN based on remaining time

SRTF example: P1(8ms,0), P2(4ms,2). What happens at time 2?

P2 preempts P1 because it has shorter remaining time

SRTF example: P1(8ms,0), P2(4ms,2). What is P2's response time?

P2 starts immediately at time 2 → response = 0ms

SRTF example: P1(8ms,0), P2(4ms,2). What is P2's turnaround time?

P2 finishes at time 6 → turnaround = 6 − 2 = 4ms

Round Robin definition?

Preemptive scheduling with fixed time slices