Before you start
- Know what a process is: a running program. A process is ready when it could use the CPU and is waiting for its turn, and running when it has it.
- Read a timeline from left to right. No programming needed.
Theory
A computer with one CPU can run only one process at a time. When several processes are ready, the scheduler decides whose turn it is. In this lesson time moves in units and switching processes costs nothing.
Each process has three values:
- Arrival: the instant it enters the ready queue.
- Burst: how many CPU units it needs to finish.
- Priority: a number from 1 to 9. 1 is the most urgent.
Algorithms come in two families. Non-preemptive ones let the process holding the CPU finish its burst. Preemptive ones can take the CPU away halfway.
| Algorithm | Rule | Type |
|---|---|---|
| FCFS | First in the queue goes first. | Non-preemptive |
| SJF | Shortest burst among ready processes. | Non-preemptive |
| SRTF | Least remaining time; a newcomer with less takes the CPU away. | Preemptive |
| Priority | Lowest priority number. | Non-preemptive |
| Round Robin | Queue order, but each turn lasts at most one quantum; then back to the end of the queue. | Preemptive |
Three metrics per process let us compare algorithms:
- Turnaround = finish − arrival: how long from arriving to finishing.
- Waiting = turnaround − burst: how long it sat in the queue without the CPU.
- Response = first turn − arrival: how long until it first got the CPU.
Example: P1 arrives at 0 with burst 3 and P2 arrives at 1 with burst 1. With FCFS, P1 runs from 0 to 3 and P2 from 3 to 4. P2 waited 2 units: it arrived at 1 and started at 3.
Predict
The board below starts with the Convoy effect scenario and the FCFS algorithm:
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 10 |
| P2 | 1 | 2 |
| P3 | 2 | 1 |
| P4 | 3 | 3 |
In what order will the four processes finish? Before running, tap the tokens in the order you expect in the Your prediction panel. Think about the FCFS rule, not about what would seem fair.
Run
Workload
Times in units. Priority: 1 is the most urgent.
| Process | Arrival | Burst | Priority | Remove process |
|---|---|---|---|---|
| P1 | ||||
| P2 | ||||
| P3 | ||||
| P4 |
Algorithm
First come, first served: serves processes in arrival order and never interrupts.
Your prediction
In what order will they finish? Tap the tokens in that order.
- Position 1
- Position 2
- Position 3
- Position 4
The board before the first turn
FCFS: serves processes in arrival order and never interrupts.
Ready queue
CPU
Free
Finished
- Empty
What happened this turn
Press Run or step turn by turn. Here you will see why the scheduler picks each process.
Metrics
| Process | Arrival | Burst | Finishes | Turnaround | Waiting | Response |
|---|---|---|---|---|---|---|
| P1 | 0 | 10 | – | – | – | – |
| P2 | 1 | 2 | – | – | – | – |
| P3 | 2 | 1 | – | – | – | – |
| P4 | 3 | 3 | – | – | – | – |
| Average | – | – | – |
Turnaround = finish − arrival. Waiting = turnaround − burst. Response = first turn − arrival.
Average waiting time by algorithm
For the current workload. Round Robin uses the chosen quantum.
As it plays, watch two moments:
- At instants 1 and 2, P2 and P3 arrive, much shorter than P1. Does anything happen to P1?
- At instant 10, P1 finishes. How long had P2 been waiting for a job of just 2 units?
Explain
This stage opens when you run the simulation to the end.
Go to the simulationWith FCFS the actual order is P1, P2, P3, P4. If you predicted that the short ones would finish first, you were thinking about bursts, but FCFS never looks at them: it serves processes in arrival order. P1 arrived alone at t = 0, took the CPU and keeps it until it finishes, even though P2 and P3 arrive later with much shorter jobs. Not even SJF would avoid this: it does not preempt either, so it also lets P1 finish.
Convoy effect. A long process at the front of the queue makes every short process behind it wait, like a slow truck on a one-lane road. With this workload FCFS gives an average waiting time of 7.25 units. Switch the board to SRTF and it drops to 2.
SJF is optimal for average waiting time among non-preemptive algorithms when all processes are available at once. The idea of the proof: if a long job goes before a short one, swapping them never increases the total wait.
SRTF is the preemptive version of SJF: it minimizes average waiting time, but it needs to know each process’s remaining time and can leave long processes waiting forever.
Starvation and aging. With priority or SJF, a process can be postponed indefinitely if someone “better” always arrives. The classic fix is aging: raising a process’s priority the longer it waits.
Response is not waiting. In non-preemptive algorithms they match. With preemption, a process can get the CPU early and still wait a lot in total: with Round Robin on the convoy scenario, P1 has response 0 but waits 6.
The Round Robin quantum. If the quantum is at least as long as the longest burst, Round Robin behaves like FCFS. If it is tiny, the system spends more time switching than working (switching is free in this simulator, not in reality). A rule of thumb: about 80% of bursts should fit in one quantum.
In real systems. For years Linux used CFS, which shares the CPU by accumulated run time, and since version 6.6 it uses EEVDF. Neither is one of the five classic algorithms, but both balance the same tensions: waiting, response and fairness.
Experiment
This stage opens when you run the simulation to the end.
Go to the simulationUse the board to solve these challenges. Each one reveals a possible solution when expanded.
1. Make Round Robin behave exactly like FCFS.
Load the Similar bursts scenario and set the quantum to 5 or 6. When every burst fits in one quantum, no turn is ever cut and Round Robin is FCFS.
2. Find a workload where SJF and SRTF produce different schedules.
The Convoy effect works: P2 arrives while P1 runs and only SRTF interrupts it (P1 runs from 0 to 1, P2 from 1 to 3…).
3. Find a workload where Round Robin has a higher average waiting time than FCFS.
Similar bursts with quantum 2: Round Robin waits 9.5 and FCFS 5.75. When bursts are alike, interleaving them makes all of them finish late.
4. With priority scheduling, make the priority-9 process wait as long as possible.
Give it an early arrival and add processes with priority 1 or 2 that arrive before the CPU frees up. Priority scheduling always picks the others first: starvation in miniature.
5. Get an average waiting time of 0 with any algorithm.
Space the arrivals so each process arrives after the previous one finishes, for example P1 arrives at 0 with burst 2, P2 at 2 with burst 3 and P3 at 5 with burst 1. Nobody waits in the queue.
Check
This stage opens when you run the simulation to the end.
Go to the simulationGo deeper
- Estimating the next burst. A real system does not know bursts in advance. It estimates them with an exponential average: τₙ₊₁ = α·tₙ + (1 − α)·τₙ, where tₙ is the last measured burst and α is usually 0.5.
- Multilevel feedback queues. Several queues with different priorities; a process that uses its whole quantum moves down a level. This approximates SJF without knowing bursts.
- Context-switch cost. Saving and restoring a process’s state takes time, which is why a tiny quantum reduces useful work.
Further reading:
- Silberschatz, Galvin and Gagne, Operating System Concepts, 10th ed., ch. 5.
- Arpaci-Dusseau and Arpaci-Dusseau, Operating Systems: Three Easy Pieces, ch. 7 and 8. Free online.
- Tanenbaum and Bos, Modern Operating Systems, 4th ed., section 2.4.
- Linux kernel documentation: EEVDF Scheduler.