CPU Scheduling Algorithm Simulator
Compare CPU scheduling policies through dispatch traces and ready-queue decisions, including context-switch overhead and per-process timing metrics.{{ summaryTitle }}
{{ summaryLine }}
| Step | Kind | Process | Start | End | Ready queue | Decision | Copy |
|---|---|---|---|---|---|---|---|
| {{ row.step }} | {{ row.kind }} | {{ row.process }} | {{ row.start }} | {{ row.end }} | {{ row.ready_queue }} | {{ row.decision }} |
The chart renderer is unavailable. The same timing values remain in the ledger.
| Process | Arrival | Burst | First start | Completion | Turnaround | Waiting | Response | Priority | Copy |
|---|---|---|---|---|---|---|---|---|---|
| {{ row.id }} | {{ row.arrival }} | {{ row.burst }} | {{ row.first_start }} | {{ row.completion }} | {{ row.turnaround }} | {{ row.waiting }} | {{ row.response }} | {{ row.priority }} |
Notes
{{ section.title }}
{{ section.body }}
Introduction:
When several runnable processes share one CPU, only one can make progress at a time. A scheduler decides who runs next, how long that process keeps the CPU, and what happens when new work arrives. The same workload can therefore feel responsive under one policy and sluggish under another even though every process eventually receives the same amount of service.
The central trade-off is between simple ordering, short completion times, fast first responses, fairness, and dispatch overhead. First-Come, First-Served preserves arrival order but can leave short jobs behind a long one. Shortest Job First favors a short ready job, while Shortest Remaining Time First can interrupt current work when an even shorter job arrives. Priority scheduling follows an assigned rank. Round Robin instead gives each ready process a bounded turn and rotates unfinished work through a queue.
| Question | Timing measure | Common misreading |
|---|---|---|
| How long until the process first runs? | Response time | A fast first response does not guarantee an early finish. |
| How much time passes from arrival to completion? | Turnaround time | Turnaround includes both useful CPU service and time spent waiting. |
| How long is the process ready but not running? | Waiting time | Waiting is not the same as idle CPU time. |
| How much elapsed time performs process work? | CPU utilization | A high percentage alone says nothing about fairness or responsiveness. |
Policy comparisons only make sense when the workload assumptions stay fixed. Arrival times, CPU bursts, priority numbers, time quantum, and context-switch cost can all change the outcome. Tie handling matters too: two mathematically valid implementations may produce different schedules if they break equal arrivals or equal bursts differently.
A bounded teaching schedule is not a full operating system. Real schedulers also respond to I/O blocking, multiple cores, interrupts, changing priorities, affinity, and incomplete knowledge of future CPU bursts. The simplified model is best used to study dispatch rules and timing consequences, not to predict the performance of a particular machine.
How to Use This Tool:
Keep one workload fixed while changing the scheduling policy. That makes differences in the trace and timing ledger attributable to the policy rather than to different inputs.
- Choose a Scheduling policy. For Round Robin, also set a whole-number Time quantum from 1 to 20 ticks.
- Enter one to eight Processes, one per line, as
ID, arrival, burst, priority. IDs must be unique; arrival may be 0, burst must be at least 1, and a lower priority number runs first. - Open Advanced when context-switch overhead matters. A cost of 0 adds no time; a positive cost adds elapsed non-service ticks when the CPU changes directly from one process to another.
- Start the dispatch playback, then pause or step through the ready-queue decisions. The playback cadence changes only animation speed, not the computed schedule.
- Compare Average waiting time, utilization, makespan, the per-process timing ledger, and the dispatch trace. Reload the same rows under another policy before drawing a conclusion.
Interpreting Results:
Start with the per-process rows, not the average alone. A low mean waiting time can hide one process that waits much longer than the rest, while a short response time may belong to a process that finishes late. The dispatch trace explains where each delay came from by separating run, idle, and context-switch spans.
- Makespan is the elapsed time from tick 0 through the final completion, including idle and context-switch time.
- Utilization counts service ticks as a percentage of makespan. Added switch cost lowers it because overhead consumes elapsed time without completing a burst.
- Throughput is completed processes per tick for this finite workload. It is not a long-run capacity guarantee.
- Policy notes describe the observed workload only. Keep arrival, burst, priority, quantum, and switch cost unchanged when comparing policies.
Technical Details:
The schedule advances in whole ticks on one CPU. Ready processes have arrived and still have burst time remaining. Non-preemptive policies retain the selected process until completion; SRTF reconsiders the ready set after every service tick; Round Robin returns unfinished work to the back of its first-in, first-out queue after a quantum expires.
Rule Core:
| Policy | Selection rule | Preemption and ties |
|---|---|---|
| FCFS | Choose the earliest-arriving ready process. | Run to completion; equal arrivals follow source-row order. |
| SJF | Choose the ready process with the smallest original burst. | Run to completion; ties use arrival, then row order. |
| SRTF | At each tick, choose the smallest remaining burst. | A shorter arrival may preempt; ties use arrival, then row order. |
| Priority | Choose the ready process with the lowest numeric priority. | Run to completion; ties use arrival, then row order. |
| Round Robin | Take the head of the ready queue for at most one quantum. | Unfinished work returns behind arrivals observed during its turn. |
If no process is ready, the CPU jumps to the next arrival and records an idle span. Context-switch cost is inserted only for a direct change from one running process to another. An idle gap clears that direct-switch relationship.
Formula Core:
For process i, let A be arrival, B burst, S first start, and C completion, all in ticks.
Averages are arithmetic means across all process rows. The display rounds average timings and percentages, while the schedule retains the full computed values. For example, arrival 2, first start 5, burst 4, and completion 9 give response 3 ticks, turnaround 7 ticks, and waiting 3 ticks.
Model boundaries:
Process rows are limited to arrivals from 0 to 100 ticks, bursts from 1 to 100 ticks, priorities from 0 to 99, and a total simulated schedule no longer than 5,000 ticks. CPU bursts are known in advance. I/O blocking, multicore execution, priority aging, affinity, and operating-system-specific queues are deliberately omitted.
Worked Examples:
A short job arrives behind a long one
Suppose P1 arrives at tick 0 with a 7-tick burst and P2 arrives at tick 2 with a 1-tick burst. FCFS keeps P1 until tick 7, so P2 first runs at tick 7 and waits 5 ticks. SRTF preempts P1 at tick 2, completes P2 at tick 3, then resumes P1. The example shows why the same total service can produce very different response and waiting times.
References:
- Scheduling: Introduction, Operating Systems: Three Easy Pieces, 2008–2023 edition.
- CPU Scheduling lecture notes, UC San Diego CSE 120, Spring 2023.