Loading...
A scheduler chooses which ready process uses the CPU. Make the arrival times and preemption policy explicit before calculating waiting and turnaround times.
What you'll be able to do
A process may be running, ready to run or blocked waiting for an event. A scheduler selects from ready processes; a blocked task is not eligible just because it arrived first. Our numerical examples use one CPU, one CPU burst per process, no I/O and no context-switch overhead. Actual operating systems must deal with more complex behaviour.
Arrival time is when a process becomes ready. Burst time is its required CPU work in this model. Completion minus arrival gives turnaround time. With one CPU-only burst, waiting time equals turnaround minus burst time. This is time spent ready without running, not the process’s entire lifetime. Include all idle intervals when drawing a timeline.
FCFS selects processes in ready-queue arrival order. In its basic non-preemptive form, a running process continues until it finishes or blocks. It is straightforward and does not need advance knowledge of burst lengths, but a long job can delay several short jobs behind it. This is the convoy effect.
For A arriving at 0 with burst 5, B at 1 with burst 2 and C at 2 with burst 1, A runs 0–5, B 5–7 and C 7–8. Waiting times are 0, 4 and 5 respectively, giving a mean of 3 time units. All values depend on the specified arrival pattern, not just the burst lengths.
Non-preemptive shortest-job-first chooses the shortest predicted burst among jobs ready when the CPU becomes free. A newly arriving shorter job does not interrupt the current burst. For the same workload, A starts at 0 because it is the only available job. At 5, C is chosen before B, producing A 0–5, C 5–6, B 6–8.
The waiting times are A=0, B=5 and C=3, averaging 8/3 time units. SJF can improve average waiting under suitable assumptions but needs known or estimated burst lengths. A long job can starve if enough short jobs keep arriving. Explain the user’s objective: predictable fairness, response time and throughput need not favour the same policy.
| Process | Arrival | Burst | FCFS completion | SJF completion |
|---|---|---|---|---|
| A | 0 | 5 | 5 | 5 |
| B | 1 | 2 | 7 | 8 |
| C | 2 | 1 | 8 | 6 |
Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.
Common mistakes to avoid
Key takeaways
Test yourself
Answer a few questions, then review anything you missed.
Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.