CPU scheduling is how the OS decides in what order to give the CPU to the processes waiting to run. This tool shows it as a Gantt chart. Switch between first-come first-served, shortest job first, shortest remaining time, round robin and priority scheduling to compare how the average waiting time and turnaround time change.
Favorites and recently used calculators are stored only in this browser (localStorage).
Results
Average turnaround time
–
Average waiting time
–
Average response time
–
Time when all finish
–
Comparison by algorithm
Turnaround time = completion time − arrival time, waiting time = turnaround time − burst time, and response time = time first given the CPU − arrival time. Among processes that tie, the one that arrived earliest is chosen, and if that also ties, the one higher in the table. In round robin, a process whose quantum expires is queued behind processes that arrive at the same time. The time taken to switch (context switch overhead) is treated as 0.
See it as a graph
Other inputs stay at their current values while the chosen input varies from 1/4 to 4 times its current value. The red dot is the current value.
What CPU scheduling is
With one CPU, only one process can run at a time. When several processes are ready to run, the OS's CPU scheduler decides which one gets the CPU next. Schedules are evaluated with measures such as turnaround time, from arrival to completion; waiting time, spent ready to run but kept waiting; and response time, until the process first starts running. Even for the same set of processes, these averages vary greatly with the order of allocation. In the example “All arrive at time 0”, first-come first-served, which runs the long 24-unit process first, gives an average waiting time of 17, but running the shortest first reduces it to 3.
First-come first-served, shortest job first and shortest remaining time
First-come, first-served (FCFS) is the simplest algorithm: processes run to completion in order of arrival. When short processes queue behind a long one, they too are kept waiting a long time (the convoy effect). Shortest job first (SJF) runs the process with the shortest burst time first, reducing the average waiting time. Shortest remaining time (SRT) compares remaining times whenever a new process arrives and, if the newcomer is shorter, takes the CPU from the running process (preemption). SRT minimizes the average waiting time, but it requires knowing burst times in advance, and long processes risk being postponed indefinitely (starvation).
Round robin and the time quantum
Round robin gives each process the CPU in turn for a fixed time (the time quantum or time slice) and sends a process whose quantum expires to the back of the ready queue. Every process starts running a little at a time soon after arrival, so response times are short, which suits interactive systems. If the quantum is too long, it behaves like first-come first-served; if it is too short, process switches (context switches) increase and their cost can no longer be ignored. Try changing the time quantum and see how the average response time and the number of switches change in the comparison table.
Priority scheduling and real operating systems
Priority scheduling runs the highest-priority process first and comes in non-preemptive and preemptive forms. To prevent starvation, where low-priority processes wait forever, a technique called aging raises a process's priority the longer it waits. Real operating systems combine these approaches. Examples include the multilevel feedback queue, which keeps a separate queue for each priority level, uses round robin within a level and gradually lowers the priority of processes that use a lot of CPU, and Linux CFS, which favors the processes that have run the least.
AThe contents of the disk files the process is using
BCPU execution state such as register values and the program counter
CThe entire contents of the process's physical memory
Show answer and explanation
Answer: B. CPU execution state such as register values and the program counter
A context switch saves CPU state, such as general registers, the program counter, the stack pointer and the operating mode, so the process can later resume exactly where it left off, and loads the state of the next process. When switching processes, the register pointing to the page table is also switched. Memory and file contents remain in place, so they need not be saved on each switch.
BThe program is reloaded from disk on every switch
CCache and TLB misses rise after the switch
Show answer and explanation
Answer: C. Cache and TLB misses rise after the switch
Saving and restoring registers is quick, but after the switch the caches and TLB hold the previous process's contents, so the new process misses until its data and translations are reloaded. On CPUs without ASIDs, the TLB must also be flushed when changing address spaces. This indirect cost can exceed the direct switching time. The clock does not slow down, and programs are not reloaded from disk.
FAQ
What is the difference between waiting time and turnaround time?
Turnaround time is the whole time from a process's arrival to its completion. Waiting time is the part of it spent ready to run but without the CPU, which is the turnaround time minus the burst time (when there is no I/O wait).
Which algorithm gives the shortest average waiting time?
When all processes arrive at the same time, shortest job first (SJF) minimizes the average waiting time; when processes arrive along the way and preemption is allowed, shortest remaining time (SRT) does. Both require knowing burst times in advance, which in practice are predicted from past burst times.
When two processes tie at the same time, which one is chosen?
This tool chooses the one that arrived earlier, and if that also ties, the one in the higher row of the table. Exam questions often state how ties are broken, so order the table rows to match.
How is this tested in exams?
IT certification exams such as Japan's Fundamental and Applied Information Technology Engineer Examinations often give a table of process arrival and burst times and ask when a particular process finishes under a given algorithm, or what the average turnaround time is. You can enter the table and check with the Gantt chart and the results table.