Learn
A1.3.3 | APPROACHES TO SCHEDULING
01 | ONE CORE, SEVERAL READY TASKS
A long video export is using the processor. You click a button in another application. Must your application wait until the entire export finishes, or can the OS give it a turn sooner? The answer depends partly on scheduling.
Scheduling selects runnable work for execution on processor cores. The scheduler applies a policy to decide which task gets an opportunity to run next. Many real systems schedule threads; our examples use one runnable task per process.
The objective is not simply “make the CPU busy”. A useful policy may also need good responsiveness, efficient completion, fair opportunities and low management overhead. Improving one measure can make another worse.
This lesson compares first-come first-served, round robin, priority scheduling and multilevel queue scheduling. Start with what each rule does, then use evidence to compare its consequences.
02 | READY, RUNNING AND BLOCKED MEAN DIFFERENT THINGS
A ready task could execute if it were given a core. A running task is currently executing. A blocked task is waiting for an event, such as completion of a storage read, before it can proceed.
The ready queue contains runnable work waiting for selection. The word queue does not mean every policy must choose strictly from the front in arrival order; a priority policy can select according to importance instead.
A task waiting for input does not become useful CPU work just because it is important. While it is blocked, another ready task can execute. When the event completes, it can become ready again.
Our worked examples contain only CPU work and no blocking. That simplification makes the scheduling rule visible; real programs often alternate between CPU bursts and I/O waits.
03 | PREEMPTION AND CONTEXT SWITCHES
Preemption means taking a task off the CPU before it has finished its current CPU burst, so another ready task can run. The preempted task can later resume; it is not being deleted or restarted from the beginning.
A non-preemptive policy lets a selected task continue until it finishes or blocks. A preemptive policy can interrupt its turn, for example when a time limit expires or higher-priority work becomes ready.
A context switch saves one task’s execution state and restores another’s. State includes information needed to resume, such as register values and the execution position. Switching consumes time that is not useful progress on the applications’ work.
Policy and preemption are separate choices. Priority scheduling can be preemptive or non-preemptive. State which version you mean instead of assuming that its name settles every implementation detail.
04 | DEFINE THE WORKLOAD BEFORE COMPARING
We will run three tasks on one CPU core. All arrive at time 0, with initial ready order A, B, C. Each has one CPU burst, and there is no I/O, idle time or simulated switching delay. Time is measured in arbitrary units.
Task A is a long batch job. B and C are short interactive jobs. A burst is the amount of CPU execution a task needs in this model, not time spent waiting. Smaller priority numbers mean higher priority here; other systems may use a different convention.
| Task | Arrival | CPU burst | Priority | Queue class |
|---|---|---|---|---|
| A | 0 | 8 | 3: lowest | Batch |
| B | 0 | 3 | 1: highest | Interactive |
| C | 0 | 1 | 2: middle | Interactive |
These choices describe one example, not a universal ranking of policies. Use the same workload when comparing approaches, and state the assumptions so the reader can interpret your evidence.
05 | FIRST-COME FIRST-SERVED: KEEP ARRIVAL ORDER
First-come first-served (FCFS), also called first-in first-out, selects the task that has waited earliest in ready-queue order. In the non-preemptive form used here, A completes before B runs, and B completes before C runs.
A executes from 0 to 8, B from 8 to 11, and C from 11 to 12. The numbers mark interval boundaries: A occupies [0,8), then B starts at 8. Each bar shows a period of execution, not a separate processor.
The rule is simple and has relatively little preemption overhead. It can suit a straightforward batch queue when arrival order matters and quick interaction is not the main goal.
Its weakness is the convoy effect: short tasks can wait behind a long CPU burst. Here C needs only one unit but does not start until time 11. Arrival-order fairness does not imply a short response delay for every task.
06 | ROUND ROBIN: SHARE TURNS USING A QUANTUM
Round robin (RR) gives each ready task a turn of up to a fixed time quantum. A task that still needs CPU time goes to the back of the ready queue when its quantum expires. A task that finishes sooner leaves immediately.
With quantum 2, A runs for two units, then B for two. C needs only one unit, so it finishes after running from 4 to 5. The scheduler does not waste an extra unit completing C’s nominal turn.
The remaining tasks continue taking turns. A resumes its saved work each time; it does not repeat the first part of its computation.
RR gives runnable tasks repeated opportunities and often improves initial response in an interactive workload. In this example C starts at 4 instead of 11. However, a task may finish later than it would under another policy, and frequent switches add overhead.
The adjacent A turns at the end are two quantum dispatches, but there is no change to a different task between them. Do not count that boundary as an additional task-to-task switch in this model.
07 | CHOOSING A QUANTUM IS A TRADEOFF
A short quantum lets waiting tasks receive a turn sooner, but can cause more frequent context switches. A long quantum reduces that switching frequency, but allows one task to occupy a core for longer before another gets a turn.
If the quantum is at least as long as every burst in this all-ready example, each task finishes in its first turn. RR then produces the same A, B, C order as FCFS. That does not mean RR always behaves identically to FCFS.
Imagine each switch costs 0.1 units. After 2 units of useful work followed by a switch, the switch occupies 0.1 ÷ 2.1 of that interval, about 4.8%. After only 0.5 units of work, the same cost occupies about 16.7%. These are illustrative ratios, not a prediction for a particular OS.
There is no universally perfect quantum. Its usefulness depends on workload, hardware and responsiveness requirements. Our simulator ignores switching delay so you can see the scheduling choices clearly.
08 | PRIORITY SCHEDULING: IMPORTANCE CHANGES THE ORDER
Priority scheduling selects the highest-priority ready task. Our non-preemptive example uses 1 as highest, so B runs first, C second and A last. Equal priorities would be broken by initial order.
The resulting order is B from 0 to 3, C from 3 to 4, and A from 4 to 12. B receives immediate service despite being behind A in the initial ready order.
This approach can favour important work instead of treating every task identically. In a preemptive version, newly ready higher-priority work could interrupt lower-priority work. No tasks arrive after time 0 in our simulator, so it does not demonstrate that interruption.
A key risk is starvation: low-priority tasks may wait indefinitely if higher-priority work keeps arriving. That cannot occur forever in our finite three-task example, but it matters in an ongoing system.
Aging can reduce this risk by increasing a waiting task’s effective priority over time. Importance also does not guarantee a deadline: meeting real-time deadlines requires suitable policies, workload assumptions and resources.
09 | MULTILEVEL QUEUES: CLASSIFY, THEN SCHEDULE
Multilevel queue scheduling separates ready tasks into queues according to a class, such as interactive or batch work. Each queue can have its own policy. The scheduler also needs a rule for sharing CPU time between queues.
In our example, B and C belong to the interactive queue and use RR with quantum 2. A belongs to the batch queue and uses FCFS. We give the interactive queue strict priority over the batch queue. The batch task runs only when no interactive task is ready.
B runs 0 to 2, C runs 2 to 3, B finishes 3 to 4, and A runs 4 to 12. Notice that C can receive a turn before B finishes because the interactive queue itself uses RR.
HIGHER QUEUE | INTERACTIVE
B and C · Round robin within this queue
LOWER QUEUE | BATCH
A · FCFS within this queue
Strict priority can starve the lower queue if the higher queue remains busy indefinitely. Another design can reserve time shares for queues rather than using strict priority, so state the chosen rule.
Do not confuse this with multilevel feedback queue scheduling. A feedback design can move tasks between queues based on behaviour. Our multilevel queue example has fixed class membership; it does not promote or demote tasks automatically.
10 | MEASURE WHAT YOU MEAN BY BETTER
A policy can help a task start promptly but still delay its final completion. Use clearly defined measures rather than calling one approach “faster” without saying what improved.
In the simulator, response time means arrival to first CPU execution. It is a useful scheduling measure, not the full time until a user sees a meaningful response. Turnaround time means arrival to completion. Waiting time is time spent ready but not running.
Because our tasks arrive at 0 and never block, response = first start; turnaround = completion; waiting = turnaround − CPU burst. With I/O or other states, do not assume that simple waiting formula applies unchanged.
| Measure | Meaning | Typical aim |
|---|---|---|
| Response time | First start − arrival, in this model | Reduce initial delay |
| Turnaround time | Completion − arrival | Finish jobs sooner |
| Waiting time | Total time in the ready state without executing | Reduce ready-queue delay |
| Throughput | Jobs completed per unit time | Complete more work in a period |
| CPU utilisation | Proportion of time the CPU is busy | Avoid unnecessary idle time |
| Fairness | Opportunities or shares under a stated policy | Avoid unjustified exclusion |
All four simulated policies finish 12 useful units by time 12 because switching delay, I/O and idle time are excluded. Their ordering changes individual delays even though the total useful CPU work is identical. Real overhead can change total completion time.
11 | COMPARE THE SAME WORKLOAD INTERACTIVELY
Select a policy and step through its dispatches. Each revealed bar shows one CPU turn; the table gives final measures for the complete schedule. Change the quantum to see how RR and the interactive queue respond.
The comparison table recalculates all four approaches for the same workload. Priority is non-preemptive; multilevel queues use strict interactive-over-batch priority, RR within interactive, and FCFS within batch. The quantum has no effect on FCFS or our priority version.
| Task | First start | Completion | Response | Turnaround | Waiting |
|---|
| Approach | Mean response | Mean turnaround | Mean waiting | Task-to-task switches |
|---|
Switch count excludes the initial dispatch and adjacent turns of the same task. It is a simplified comparison, not a count of every kernel operation on a real computer.
12 | INTERPRET THE RESULTS AT QUANTUM 2
For FCFS, C first runs at 11 and completes at 12. Under RR with quantum 2, C first runs at 4 and completes at 5. RR improves C’s initial response and completion for this workload because it does not wait for A’s full burst.
A shows the other side: FCFS completes A at 8, while RR completes it at 12. Sharing turns helps the short tasks here but delays the long task’s completion. “RR is always faster” would ignore that difference.
Priority starts B immediately. Multilevel queues also start B immediately, but let C take a turn after two units rather than after B’s complete three-unit burst. The difference comes from the policy within the interactive queue.
At quantum 2, mean response is about 6.33 for FCFS, 2.00 for RR, 2.33 for priority and 2.00 for our multilevel queues. These results describe this specific set of tasks. They are not fixed characteristics of the algorithm names.
13 | CHOOSE FOR A CONTEXT, NOT A SLOGAN
A basic overnight batch queue may value simplicity and predictable arrival order, making FCFS defensible. If many short jobs sit behind long bursts, its waiting delays become a weakness.
A time-sharing interactive environment benefits from repeated turns, making RR useful. Compare the quantum and switching overhead rather than assuming equal turns solve every requirement.
A system with explicit urgency classes may use priority scheduling. Explain the need to serve important work promptly, then address lower-priority starvation and whether preemption is required.
An environment mixing interactive and batch workloads may use multilevel queues with different policies. The additional flexibility brings configuration choices: class assignment, within-queue rules and inter-queue sharing all affect the result.
Real operating systems can combine ideas. A queue may use priorities and RR within a priority level. The four approaches are useful concepts, not a claim that every OS uses exactly one isolated textbook rule.
14 | PRACTISE COMPARING WITH A REASON
Choose a comparison prompt, predict the answer and reveal the explanation. Focus on naming the criterion and supporting the comparison with a mechanism or a specific result.
15 | FOUR APPROACHES SIDE BY SIDE
| Approach | Selection rule | Strength | Limitation |
|---|---|---|---|
| FCFS | Arrival order; non-preemptive here | Simple; few preemptions | Short work can wait behind a long burst |
| Round robin | Rotate runnable tasks using a quantum | Regular turns; useful initial responsiveness | Quantum tradeoff; switching overhead; completion delays can rise |
| Priority | Select highest-priority ready work | Favours explicit importance | Starvation risk; priority assignment matters |
| Multilevel queues | Separate classes, with rules within and between queues | Different treatment for different workload classes | More policy choices; strict higher-queue priority can starve lower queues |
Fairness needs a definition. FCFS respects arrival order, RR offers repeated turns, and priority deliberately favours some work. A fair policy for one purpose may be inappropriate for another.
16 | WRITE AN ACTUAL COMPARISON
The command word compare requires relevant similarities and/or differences. Pair the approaches on the same criterion: selection rule, responsiveness, overhead, starvation or suitability for a stated context.
For example: “FCFS can delay short interactive tasks behind a long CPU burst, whereas RR preempts after a quantum and gives other ready tasks a turn. In this example C starts at 4 under RR instead of 11 under FCFS, although RR introduces more task-to-task switches.”
Both approaches allocate CPU execution among ready work. The difference is how they choose and limit turns. Linking the mechanism to an effect is stronger than writing two disconnected lists of features.
Avoid saying non-preemptive means a blocked task holds the CPU, priority guarantees deadlines, or multilevel queues automatically move tasks between classes. Keep the assumptions and the evidence visible.
Further reading: Scheduling: introduction and worked models · Scheduling policies and queue structures