# CPU Scheduling — FCFS, SJF, SRTF, Round Robin and Priority with Gantt Charts

Source: https://skills101.in/learn/operating-systems/cpu-scheduling — Skills101 free tutorial (Operating Systems). Updated 2026-11-09.

When several processes are **ready**, the **CPU scheduler** decides who runs next. Exams and interviews give you a table of processes and ask for **average waiting time** — here's how to solve every version.

## 1. The terms

| Term | Formula |
|---|---|
| **Arrival time (AT)** | when the process becomes ready |
| **Burst time (BT)** | CPU time it needs |
| **Completion time (CT)** | when it finishes |
| **Turnaround time (TAT)** | **CT − AT** (total time in the system) |
| **Waiting time (WT)** | **TAT − BT** (time spent waiting) |
| **Response time** | first time on CPU − AT |

**Preemptive** schedulers can take the CPU away from a running process; **non-preemptive** ones let it finish.

We'll use the same four processes for every algorithm:

| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 8 |
| P4 | 3 | 6 |

## 2. FCFS (First Come, First Served) — non-preemptive

Run in order of arrival.

![FCFS Gantt chart: P1 0–5, P2 5–8, P3 8–16, P4 16–22. Average waiting time 5.75, average turnaround 11.25](https://skills101.in/learn-img/operating-systems/gantt-fcfs.svg)

| Process | CT | TAT = CT − AT | WT = TAT − BT |
|---|---|---|---|
| P1 | 5 | 5 | 0 |
| P2 | 8 | 7 | 4 |
| P3 | 16 | 14 | 6 |
| P4 | 22 | 19 | 13 |

**Average WT = (0 + 4 + 6 + 13) / 4 = 5.75**, average TAT = 11.25.

Simple, but a long job at the front makes everyone wait — the **convoy effect**.

## 3. SJF (Shortest Job First) — non-preemptive

When the CPU is free, pick the **shortest** burst among the arrived processes.

![SJF Gantt chart: P1 0–5, then P2 5–8, P4 8–14, P3 14–22. Average waiting time 5.25](https://skills101.in/learn-img/operating-systems/gantt-sjf.svg)

At t = 0 only P1 has arrived, so it runs to 5. Then the shortest of P2 (3), P3 (8), P4 (6) is P2, then P4, then P3.

WT: P1 0, P2 4, P4 5, P3 12 → **average 5.25**, average TAT 10.75.

SJF gives the **minimum average waiting time** of all non-preemptive algorithms — but it needs burst times in advance (usually estimated), and long jobs can **starve**.

## 4. SRTF (Shortest Remaining Time First) — preemptive SJF

At every arrival, run the process with the **least remaining** time.

- t = 0: P1 starts (remaining 5).
- t = 1: P2 arrives with 3 < P1's remaining 4 → **P2 preempts** P1. P2 runs 1–4.
- t = 4: P1 (4 left), P3 (8), P4 (6) → P1 runs 4–8.
- Then P4 8–14, P3 14–22.

Gantt: **P1 0–1 · P2 1–4 · P1 4–8 · P4 8–14 · P3 14–22**

WT: P1 3, P2 0, P3 12, P4 5 → **average 5.0** (the best of all here), average TAT 10.5.

## 5. Round Robin (RR) — preemptive, quantum = 2

Each process gets at most **2 units**, then goes to the back of the queue. New arrivals join the queue **before** the process that was just preempted.

![Round Robin with quantum 2: P1, P2, P3, P1, P4, P2, P3, P1, P4, P3, P4, P3, finishing at 22. Average waiting time 9.75](https://skills101.in/learn-img/operating-systems/gantt-rr.svg)

WT: P1 9, P2 7, P3 12, P4 11 → **average 9.75**, average TAT 15.25.

Waiting time is higher, but **response time** is excellent — everyone gets the CPU quickly. That's why time-sharing systems use RR.

**Quantum size:** too large → becomes FCFS; too small → too many context switches.

## 6. Priority scheduling

Each process has a priority; the highest runs first (preemptive or not). Problem: **starvation** of low-priority processes. Fix: **aging** — slowly increase the priority of processes that wait long.

## 7. Comparison

| Algorithm | Preemptive? | Avg WT here | Strength | Weakness |
|---|---|---|---|---|
| FCFS | no | 5.75 | simple | convoy effect |
| SJF | no | 5.25 | low waiting | starvation; needs burst time |
| SRTF | yes | **5.0** | lowest waiting | starvation; many switches |
| Round Robin (q=2) | yes | 9.75 | fair, responsive | more waiting & switches |
| Priority | either | — | important jobs first | starvation (use aging) |

Real systems use **multilevel feedback queues**: interactive jobs get high priority and short quanta; CPU-heavy jobs drift to lower queues.

## Common mistakes

- Using CT − BT for waiting time (it's TAT − BT, i.e. CT − AT − BT).
- In RR, putting the preempted process ahead of new arrivals.
- Forgetting that SJF can only choose among processes that have **arrived**.

## Quick recap

- TAT = CT − AT; WT = TAT − BT.
- FCFS simple; SJF/SRTF minimise waiting but can starve; RR fair and responsive.
- Draw the Gantt chart first, then fill the table.


Practice quiz and free certificate: https://skills101.in/learn/operating-systems/cpu-scheduling