The short answer
The four main types of scheduling algorithms are:
- First-come, first-served (FCFS): tasks run in arrival order, each to completion.
- Shortest job first (SJF): the task with the shortest CPU burst runs next.
- Priority scheduling: the highest-priority task runs next.
- Round robin (RR): each task runs for a fixed time slice, then goes to the back of the queue.
FCFS and SJF are classically non-preemptive. Round robin is preemptive. Priority scheduling can be either. Each has a preemptive or refined variant, covered below.
Definitions only go so far, so this article runs the same set of tasks through all four algorithms and compares the results. For a more conceptual look at each policy, including how they map onto Linux and RTOS scheduling, see the four main types of processor scheduling policies.
A worked example: one task set, four algorithms
The task set
Four tasks all arrive at time 0, in the order P1, P2, P3, P4. Burst time is how long each needs the CPU. For priority scheduling, a lower number means higher priority.
| Task | Burst time | Priority |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 4 |
| P3 | 8 | 1 (highest) |
| P4 | 3 | 3 |
Total work is 19 time units, so every algorithm finishes at time 19. What changes is who waits and for how long.
We’ll measure two things:
- Waiting time: total time a task spends ready but not running. With all arrivals at 0, it’s the finish time minus the burst time.
- Response time: time from arrival until the task first gets the CPU.
FCFS
Tasks run in arrival order.
| P1 | P2 | P3 | P4 |
0 6 8 16 19
| Task | Start | Finish | Waiting |
|---|---|---|---|
| P1 | 0 | 6 | 0 |
| P2 | 6 | 8 | 6 |
| P3 | 8 | 16 | 8 |
| P4 | 16 | 19 | 16 |
Average waiting time: (0 + 6 + 8 + 16) / 4 = 7.5. For non-preemptive algorithms, response time equals waiting time here, so average response is also 7.5.
SJF
Shortest burst first: P2 (2), P4 (3), P1 (6), P3 (8).
| P2 | P4 | P1 | P3 |
0 2 5 11 19
| Task | Start | Finish | Waiting |
|---|---|---|---|
| P2 | 0 | 2 | 0 |
| P4 | 2 | 5 | 2 |
| P1 | 5 | 11 | 5 |
| P3 | 11 | 19 | 11 |
Average waiting time: (0 + 2 + 5 + 11) / 4 = 4.5.
Priority
Highest priority first: P3 (1), P1 (2), P4 (3), P2 (4). Since all tasks arrive together, preemptive and non-preemptive priority give the same result here.
| P3 | P1 | P4 | P2 |
0 8 14 17 19
| Task | Start | Finish | Waiting |
|---|---|---|---|
| P3 | 0 | 8 | 0 |
| P1 | 8 | 14 | 8 |
| P4 | 14 | 17 | 14 |
| P2 | 17 | 19 | 17 |
Average waiting time: (0 + 8 + 14 + 17) / 4 = 9.75.
Round robin (quantum = 2)
Each task gets up to 2 units, then goes to the back of the queue.
| P1 | P2 | P3 | P4 | P1 | P3 | P4 | P1 | P3 | P3 |
0 2 4 6 8 10 12 13 15 17 19
Step by step:
- 0–2: P1 runs (4 left). 2–4: P2 runs and finishes at 4.
- 4–6: P3 runs (6 left). 6–8: P4 runs (1 left).
- 8–10: P1 runs (2 left). 10–12: P3 runs (4 left).
- 12–13: P4 runs its last unit and finishes at 13.
- 13–15: P1 runs and finishes at 15.
- 15–19: only P3 remains. It runs two more slices and finishes at 19.
| Task | First runs at | Finish | Waiting |
|---|---|---|---|
| P1 | 0 | 15 | 9 |
| P2 | 2 | 4 | 2 |
| P3 | 4 | 19 | 11 |
| P4 | 6 | 13 | 10 |
Average waiting time: (9 + 2 + 11 + 10) / 4 = 8.0. Average response time: (0 + 2 + 4 + 6) / 4 = 3.0.
Comparing the results
| Algorithm | Avg. waiting time | Avg. response time | Task switches* |
|---|---|---|---|
| FCFS | 7.5 | 7.5 | 3 |
| SJF | 4.5 | 4.5 | 3 |
| Priority | 9.75 | 9.75 | 3 |
| Round robin (q = 2) | 8.0 | 3.0 | 8 |
*Switches from one task to a different task, not counting the first dispatch.
What the example shows
- FCFS suffers from the convoy effect. P4, a short task, waits 16 units because it happens to be behind two long tasks.
- SJF gives the lowest average waiting time. For tasks that all arrive together, running the shortest first is provably optimal for average waiting time. The catch is that it needs burst times in advance.
- Round robin trades waiting time for response time. Every task starts within 6 units, but tasks finish later on average because they’re interleaved. It also needed more than twice as many task switches, each of which costs real time on real hardware.
- Priority scheduling doesn’t care about averages. It had the worst average waiting time here, because the highest-priority task was also the longest. That’s not a flaw. Priority scheduling exists to serve the most urgent task first, and P3 waited 0. This is exactly the property real-time systems want.
Preemptive variants
Two of the four algorithms have common preemptive versions, which matter when tasks arrive at different times:
- Shortest remaining time first (SRTF): when a new task arrives with a shorter burst than what’s left of the running task, the scheduler switches to it. This improves average waiting time further but increases context switches and the risk of starving long tasks.
- Preemptive priority: when a higher-priority task becomes ready, it immediately takes the CPU from a lower-priority one. This is the core of almost every real-time operating system.
Choosing a round-robin quantum
The quantum controls how round robin behaves:
- A very large quantum turns round robin into FCFS. In the example, a quantum of 8 or more would give the same timeline as FCFS.
- A very small quantum gives excellent response time but spends a growing share of time on context switches.
General-purpose systems typically choose a quantum that is large compared with the context-switch cost but small enough to keep interactive tasks feeling responsive. In RTOSes that support time slicing, the slice is commonly one scheduler tick, and it only applies among tasks of equal priority.
Starvation and aging
Both SJF and priority scheduling can starve tasks. A long job or a low-priority task may wait indefinitely if shorter or higher-priority work keeps arriving. General-purpose systems use aging, gradually raising the priority of tasks the longer they wait, so everything eventually runs.
Real-time systems usually don’t age priorities, because that would undermine the guarantee that the most urgent work runs first. Instead, designers check in advance that the total load leaves enough time for every task to meet its deadline.
Beyond the four: real-time scheduling algorithms
The four classic algorithms come from general-purpose operating systems, where the goals are throughput, fairness, and good average response. Real-time systems need a different guarantee: every task meets its deadline, even in the worst case. For that, embedded engineers use:
- Rate monotonic (RM): fixed priorities, with shorter periods getting higher priorities.
- Deadline monotonic (DM): fixed priorities, with shorter deadlines getting higher priorities.
- Earliest deadline first (EDF): dynamic priorities. The task with the nearest absolute deadline runs.
- Cyclic executive / time-triggered: a fixed timetable built at design time.
These come with schedulability tests that tell you, before you ship, whether a set of tasks will meet its deadlines. We cover them, with a worked response-time analysis, in real-time scheduling and multitasking in embedded systems.
Which algorithms do embedded systems use?
Most embedded RTOSes use preemptive priority scheduling, with round robin among tasks of equal priority. So two of the four classic algorithms are in daily use on microcontrollers, combined. FCFS shows up in simple work queues, such as processing messages in arrival order inside one task. SJF is rarely used directly, because execution times aren’t known in advance.
Very simple firmware may not use a scheduler at all: a main loop calls each function in turn, which is effectively a cooperative round robin. For when that’s enough and when it isn’t, see RTOS vs super loop: when do you actually need an RTOS?.
Frequently asked questions
Which scheduling algorithm is best?
There’s no single best. SJF is best for average waiting time when burst lengths are known, round robin is best for fairness and response time, and preemptive priority is best when some tasks are more urgent than others, as in real-time systems.
Is round robin suitable for real-time embedded systems?
Not on its own for hard deadlines, because an urgent task may wait for every other task’s time slice. RTOSes use it only to share time among tasks that have the same priority.
What is the difference between waiting time and turnaround time?
Turnaround time is the total time from arrival to completion. Waiting time is the part of that spent ready but not running. For a task that never blocks, turnaround time equals waiting time plus burst time.