Scheduling basics: the times we measure; first-come first-served

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Which scheduler picks the next process for the CPU? from Lesson 1.1.2
2. Pre-emption moves a process from Running to? from Lesson 1.1.1
3. How many mode switches does one system call cause? from Lesson 0.1.3

1 · The Hook

Three customers queue at a single ticket counter: one needs 24 minutes, two need 3 minutes each. If the slow one goes first, everyone waits ages; if the quick ones go first, the average wait drops from 17 minutes to 3. CPU scheduling is choosing that order. GATE asks a scheduling question almost every year, and they all use the same few measurements and one drawing: the Gantt chart.

3 · Core Concept

Predict First — the answer

P1 waits 0, P2 waits 24, P3 waits 27. Average (0 + 24 + 27)/3 = 17 ms.

In plain words

Each process arrives at some time and needs the CPU for some amount of time (its burst). The scheduler decides the order. We draw the order as a timeline (a Gantt chart), then read off when each process finished, and from that how long it waited.

1. The times we measure (for each process)

Also: throughput = processes finished per unit time; CPU utilisation = % of time the CPU is busy.

2. Pre-emptive vs non-pre-emptive

• Non-pre-emptive: once a process has the CPU it keeps it until it finishes (or blocks).
• Pre-emptive: the OS may take the CPU away (when a better process arrives, or a time slice ends).

3. First-Come First-Served (FCFS)

Run processes in order of arrival; non-pre-emptive. Simple, fair in order, but suffers the convoy effect: short jobs stuck behind a long one wait a long time. If the CPU is free and nobody has arrived, it is idle until the next arrival.

4. The running example (used all through Phase 2)

(Priority is used in Lesson 2.1.3; a smaller number means higher priority.)

FCFS: P1 0–8, P2 8–12, P3 12–21, P4 21–26, P5 26–28.

Average TAT = 85/5 = 17; average WT = 57/5 = 11.4.

4 · Visual

FCFS on the running example

| P1        | P2   | P3           | P4      | P5 |
0           8      12             21        26   28

waiting:  P1 0   P2 8-1=7   P3 12-2=10   P4 21-3=18   P5 26-4=22

5 · Worked Examples

Example 1 Easy

Same three jobs (24, 3, 3 at time 0) in the order P2, P3, P1. Average waiting time?

Solution

Waits 0, 3, 6 → 3 ms. Order matters enormously.

Example 2 Medium

P1 arrives at 0 with burst 4, P2 arrives at 6 with burst 3 (FCFS). When does P2 finish? Is the CPU ever idle?

Solution

P1 runs 0–4; the CPU is idle 4–6; P2 runs 6–9 → CT = 9.

Example 3 GATE

In the running example under FCFS, what is the average turnaround time?

Solution

(8 + 11 + 19 + 23 + 24)/5 = 17.

6 · GATE Traps

• TAT = CT − AT, not CT alone (unless everyone arrives at 0).
• WT = TAT − BT; for non-pre-emptive schedules it equals start time − AT.
• Leave a gap (idle time) in the Gantt chart if no process has arrived yet.
• Response time and waiting time are equal for non-pre-emptive algorithms, but not for pre-emptive ones.

7 · Memory Hook

"Draw the Gantt chart, then TAT = CT − AT, WT = TAT − BT."

8 · Connect the Dots

FCFS ignores burst lengths, so short jobs suffer. The next lesson runs the shortest job first, which gives the smallest average waiting time of all.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — FCFS

Jobs with bursts 24, 3, 3 arrive at time 0 in the order P1, P2, P3 (FCFS). Average waiting time?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — FCFS

Running example under FCFS: average waiting time?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Idle time

FCFS: P1 (AT 0, BT 3), P2 (AT 5, BT 4), P3 (AT 6, BT 2). Average turnaround time?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Definitions

Turnaround time is:

1. (A) completion time − arrival time
2. (B) completion time − burst time
3. (C) burst time + arrival time
4. (D) start time − arrival time

Q5 · MCQ · 1 mark(s) — Convoy

The convoy effect is a weakness of:

1. (A) Round robin
2. (B) FCFS
3. (C) SRTF
4. (D) Priority with aging

10 · Rule Card

• AT, BT given; CT from the Gantt chart; TAT = CT − AT; WT = TAT − BT; RT = first start − AT.
• Non-pre-emptive: keep the CPU till done; pre-emptive: can be interrupted.
• FCFS: arrival order, non-pre-emptive, convoy effect; idle gaps when nothing has arrived.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

arrival timeburst timecompletion timeturnaround timewaiting timeresponse timethroughputCPU utilisationGantt chartpre-emptive vs non-pre-emptive schedulingfirst-come first-servedconvoy effectidle time