Scheduling

Vocabulary

English	Meaning
FCFS	First-come, first-served scheduling: choosing ready tasks in arrival order.
SJF	Shortest-job-first scheduling: choosing the ready task with the shortest predicted CPU burst.
round robin/raʊnd ˈrɒbɪn/	Scheduling ready tasks in turns with a limited time quantum.
Gantt chart/ɡænt tʃɑːt/	A timeline showing when scheduled tasks use the processor.
turnaround time	Elapsed time from a job's arrival to its completion.
waiting time	Time a job spends in the ready queue waiting for processor service.

Three policies, one job set

The course set: bursts P1 = 7, P2 = 4, P3 = 1, P4 = 4, all arriving at 0. FCFS runs them in order; SJF runs the shortest next; round robin (quantum 2) slices everyone in turn — the Gantt chart shows who ran when.

{exercise:uni-cs0702-policies}

Practice

For the course set (7, 4, 1, 4 at time 0), the policy with the LOWEST average turnaround is —

Difficulty 1/5 · 100 coins + a small bonus on first completion today

Turnaround time = finish − arrival; waiting time = turnaround − burst. FCFS finishes $7, 11, 12, 16$ — average turnaround $11.5$. SJF (P3, P2, P4, P1) finishes $1, 5, 9, 16$ — average $7.75$.
RR ($q = 2$) runs P1 P1 | P2 P2 | P3 | P4 P4 | P1 P1 | P2 P2 | P4 P4 | P1 P1 | P1 — finishes P3 $= 5$, P2 $= 11$, P4 $= 13$, P1 $= 16$: average $11.25$. Same jobs, three answers.

{exercise:uni-cs0702-numbers}

Practice

Under FCFS the set finishes at —

Difficulty 1/5 · 100 coins + a small bonus on first completion today

The convoy effect: under FCFS a 7-burst job arrives first and P3 waits $11$ units for $1$ unit of work — FCFS's signature failure with interactive users.
Quantum choice: $q$ large degenerates to FCFS; $q$ tiny spends the CPU switching — a $1$ µs switch in a $2$ ms quantum wastes $0.05\%$, in a $20$ µs quantum $5\%$. Switches are work, not progress.