CPU scheduling simulator

Each row of the table is a process with an arrival time, a burst time (how many time units of CPU it needs) and a priority. Change any number and the schedule is recalculated. The Gantt chart shows which process holds the CPU in each time unit, and the table fills in each process's completion, turnaround, waiting and response time, with averages underneath. The panel on the right runs every algorithm on the same processes, so you can compare them directly.

Press Step from 0 to move through time one unit at a time and see the ready queue and the reason for each decision. Things to try:

• Load Convoy effect and compare FCFS with SJF: the same three jobs, average waiting time 17 against 3.
• With round robin, change the quantum from 1 to 5 and watch the number of context switches and the average response time.
• Load A long job keeps waiting and choose SRTF or preemptive priority: P1 is pushed back every time a short or important job arrives.

The simulation follows the usual textbook conventions, which the page states so you can match them to your course: a process that arrives at the same moment another is preempted joins the queue first; ties go to the earlier arrival and then the lower process number; a lower priority number means a higher priority; and context switches take no time. It reproduces the worked examples in Silberschatz, Galvin and Gagne's Operating System Concepts exactly.

CPU scheduling is how an operating system decides which of the processes that are ready to run gets a CPU, and for how long. A machine usually has far more runnable threads than CPU cores, so the kernel's scheduler makes this choice many times a second: whenever a process finishes, blocks waiting for input or output, becomes ready, or uses up its time slice.

Processes alternate between CPU bursts, when they compute, and waits for I/O. A process waiting for a disk or the network is not in the ready queue; the scheduler only chooses among processes that could run right now. The algorithms on this page treat each process as one CPU burst, as textbooks do, which is enough to see how the choices differ.

Scheduling algorithms are judged on several measures that pull against each other: keeping the CPU busy, finishing as many jobs as possible per unit of time (throughput), finishing each job soon after it arrives (turnaround), starting interactive work quickly (response time), and not leaving any process waiting forever (fairness).

For each process, using the Gantt chart:

• Completion time (CT): when the process finishes its burst.
• Turnaround time (TAT) = completion time − arrival time. The total time from arrival to finish.
• Waiting time (WT) = turnaround time − burst time. The time spent ready but not running.
• Response time (RT) = time of first run − arrival time. How long before the process got the CPU at all.

Average each one over all processes to compare algorithms. For non-preemptive algorithms the response time equals the waiting time, because a process that starts runs to the end. For preemptive ones it can be much lower, which is the point of round robin.

FCFS runs processes in the order they arrive, each to completion. It is the simplest algorithm, a plain queue, and is fair in the sense that no process is overtaken. Its weakness is the convoy effect: one long process at the front makes every short process behind it wait. In the convoy workload, three processes of 24, 3 and 3 units arrive together; FCFS gives an average waiting time of 17 units, and running the two short ones first gives 3.

FCFS is non-preemptive, so it is a poor fit for interactive systems, where a long computation would freeze everything else. It survives inside other schedulers, for example as the policy within one priority level.

SJF picks the ready process with the shortest burst and runs it to completion. When all processes are available at the start, it gives the lowest possible average waiting time: moving a short job ahead of a long one reduces the short job's wait by more than it increases the long one's.

SRTF, also called preemptive SJF, applies the same rule whenever a process arrives: if the newcomer needs less time than the running process has left, it takes over. It does at least as well as SJF on average waiting time, with more context switches.

Both have two problems. The scheduler cannot know how long a burst will be; real systems estimate it from past bursts, typically with an exponential average, τ_n+1 = α·t_n + (1 − α)·τ_n, where t_n is the last burst and τ_n the previous estimate. And a long process can starve if short ones keep arriving.

Round robin is FCFS with a timer. Each process runs for at most one time quantum (also called a time slice); if it has not finished, it goes to the back of the ready queue and the next process runs. Every ready process gets a turn within (n − 1) × quantum time units, so response time is good and no process starves.

The quantum decides how round robin behaves. A very large quantum turns it into FCFS. A very small one gives each process a sliver of CPU in turn but spends more and more time switching between them: each context switch saves and restores registers, and the next process starts with cold caches. A common rule of thumb is to make the quantum longer than most CPU bursts, so most processes finish or block within one. Real systems use slices of a few milliseconds, while a context switch costs on the order of microseconds.

Round robin usually has a worse average turnaround time than SJF, because every process is held back by everyone else's turns, but a much better average response time. The table in the simulator shows both.

Priority scheduling runs the ready process with the highest priority. In this simulator and most textbooks, a lower number means a higher priority (Linux nice values work the same way; some systems use the opposite). The non-preemptive version waits for the running process to finish; the preemptive version switches as soon as a higher-priority process arrives. SJF is a special case where the priority is the burst length.

The risk is starvation: low-priority processes can wait indefinitely while higher-priority work keeps arriving. The standard fix is aging, slowly raising the priority of processes that have waited a long time. A related problem, priority inversion, happens when a high-priority process waits for a lock held by a low-priority one that cannot run because medium-priority processes keep the CPU. The Mars Pathfinder lander hit this in 1997, and its VxWorks system was fixed by turning on priority inheritance.

The simulator's default workload has five processes. Round robin uses a quantum of 2.

Real workloads mix interactive programs, which run briefly and wait for input, with batch jobs that compute for a long time. A multilevel queue keeps a separate queue per class, each with its own algorithm, such as round robin for interactive processes and FCFS for batch jobs, and a fixed priority between the queues.

A multilevel feedback queue (MLFQ) lets processes move between queues based on how they behave. A process that uses its whole time slice is moved down to a lower-priority queue with a longer slice; one that gives up the CPU early, typically to wait for I/O, stays high. Short and interactive jobs therefore get quick service without the scheduler knowing burst lengths in advance, and periodically moving every process back to the top prevents starvation. Fernando Corbató's CTSS used this idea in 1962, and it shaped the schedulers of many later systems.

Linux has several scheduling classes. Real-time threads use SCHED_FIFO (priority-based, run until they block) or SCHED_RR (the same with a time slice), and always run before normal threads. Normal threads were scheduled by the O(1) scheduler in the early 2.6 kernels, then by the Completely Fair Scheduler (CFS), written by Ingo Molnar and merged in 2.6.23 in 2007. CFS tracks each thread's virtual runtime, the CPU time it has used scaled by its nice value, keeps runnable threads in a red-black tree ordered by it, and always runs the one with the least. In kernel 6.6, in 2023, CFS was replaced by EEVDF (earliest eligible virtual deadline first), based on a 1995 paper by Ion Stoica and Hussein Abdel-Wahab, which keeps the fairness and improves latency for threads that need the CPU soon.

Windows uses preemptive priority scheduling with 32 priority levels, round robin within each level, and temporary priority boosts for threads that were waiting on input or I/O, which keeps interactive programs responsive.

On multi-core machines each core has its own run queue, and the scheduler also balances load between cores while trying to keep a thread on the core whose caches already hold its data.

Exam questions usually give a table of processes and ask for the Gantt chart and the average waiting and turnaround times under one or more algorithms. To get them right:

1. Draw the time line and mark every arrival.
2. At every arrival, completion and, for round robin, end of quantum, decide what runs next using the algorithm's rule. Write down the ready queue at each of these moments.
3. Check the convention for ties, especially in round robin when an arrival and a preemption happen at the same time. This simulator puts the new arrival first, as most textbooks do.
4. Fill in completion times from the chart, then compute TAT = CT − AT and WT = TAT − BT for each process, and average them.

Interview questions for systems roles are more practical: what a context switch costs, how Linux decides which thread runs, how nice values and CPU limits in containers (cgroups) affect a process, and why a busy-waiting thread hurts others on the same core.