A visual tool for A-level Computer Science students
CPU scheduling is the process of determining which process in the ready queue gets the CPU time. The main objective is to maximize CPU utilization and throughput while minimizing response time, waiting time, and turnaround time.
CPU scheduling determines which process runs at a certain time. The algorithms demonstrated here include:
FCFS is the simplest scheduling algorithm. Processes are executed in the order they arrive in the ready queue. It's non-preemptive, meaning once a process starts executing, it continues until it completes or blocks.
Advantages: Simple to implement, fair in terms of arrival order.
Disadvantages: Can lead to the "convoy effect" where short processes wait behind long ones, resulting in higher average waiting times.
Round Robin is a preemptive scheduling algorithm designed for time-sharing systems. Each process gets a small unit of CPU time (time quantum), and if it doesn't complete within that time, it's moved to the back of the ready queue.
Advantages: Fair allocation of CPU time, good for time-sharing systems, responsive for short processes.
Disadvantages: Performance depends heavily on the time quantum size. Too small causes excessive context switching, too large makes it similar to FCFS.
SJF selects the process with the smallest burst time first. It's non-preemptive in its basic form, meaning once a process starts, it runs to completion.
Advantages: Provides minimum average waiting time among all scheduling algorithms when all processes arrive at the same time.
Disadvantages: Difficult to implement as it requires knowing the burst time in advance. Can lead to starvation of longer processes if shorter ones keep arriving.
SRTF is the preemptive version of SJF. If a new process arrives with a burst time less than the remaining time of the current process, the current process is preempted.
Advantages: Optimal average waiting time, responsive to short processes.
Disadvantages: High overhead due to frequent context switching, potential starvation of longer processes, requires knowing burst times in advance.
Preemptive scheduling allows the operating system to interrupt a running process and move it to the ready queue if a higher priority process arrives. This ensures better response times for high-priority or short processes.
Non-preemptive scheduling allows processes to run until they complete, block for I/O, or voluntarily yield the CPU. Once a process starts, it cannot be interrupted until it finishes its CPU burst.
Key differences:
Preemptive: Can interrupt running processes (RR, SRTF)
Non-preemptive: Processes run until completion (FCFS, SJF)
FCFS executes processes in the order they arrive. It's like a queue at a shop - the first customer to arrive gets served first.
How it works: When the CPU is free, the process that has been waiting the longest gets to run next. Once a process starts running, it continues until it completes.
Example: If Process 1 arrives at time 0 with burst time 10, Process 2 arrives at time 2 with burst time 3, Process 2 still has to wait until Process 1 completes at time 10.
Average Waiting Time
-
The average time processes spend waiting in the ready queue before getting CPU time. Lower values indicate better performance.
Waiting Time = Start Time - Arrival Time
Average Turnaround Time
-
The average time taken to complete a process from arrival to completion. It includes both waiting time and execution time.
Turnaround Time = Completion Time - Arrival Time
Round Robin is designed for time-sharing systems. Each process gets a small slice of CPU time called a time quantum, then returns to the queue if it needs more time.
How it works: Processes are kept in a circular queue. The CPU scheduler goes around the queue, allocating the CPU to each process for a time interval of up to 1 time quantum. New processes are added to the tail of the queue.
Example: With a time quantum of 2, a process with burst time 6 will run for 2 time units, then be preempted and placed at the end of the queue. It will need 3 turns to complete.
Average Waiting Time
-
Average Turnaround Time
-
SJF selects the process with the smallest execution time. It's optimal for minimizing average waiting time when all processes are available simultaneously.
How it works: When the CPU is available, the process with the shortest burst time among all ready processes is selected for execution. Once selected, a process runs to completion.
Example: If Process 1 (burst time 6) and Process 2 (burst time 3) are both ready, Process 2 will be executed first, even if Process 1 arrived earlier.
Average Waiting Time
-
Average Turnaround Time
-
SRTF is the preemptive version of SJF. It always chooses the process with the shortest remaining time to completion.
How it works: When a new process arrives, its total burst time is compared with the remaining time of the current executing process. If the new process has a shorter burst time, the current process is preempted.
Example: If Process 1 with remaining time 4 is running, and Process 2 with burst time 2 arrives, Process 1 will be preempted and Process 2 will start executing.
Average Waiting Time
-
Average Turnaround Time
-
Different scheduling algorithms perform better in different scenarios:
| Algorithm |
Average Waiting Time
Average Waiting TimeThe average time processes spend waiting in the ready queue. Lower values indicate better performance. |
Average Turnaround Time
Average Turnaround TimeThe average time taken to complete a process from arrival to completion. It includes both waiting time and execution time. |
|---|
The percentage of time the CPU is busy. Higher utilization is generally better.
The number of processes completed per unit time. Higher throughput means more work is being done.
The time taken to execute a process from submission to completion. Includes waiting time, execution time, and I/O time.
The total time a process spends waiting in the ready queue.
The time from submission of a request until the first response is produced. Important for interactive systems.
A situation where a process is ready to run but is never selected by the scheduler because other processes with higher priority or shorter burst times keep arriving.
A phenomenon in FCFS scheduling where all processes must wait for a long process to complete, similar to a convoy of vehicles stuck behind a slow truck.
The time and resources used when switching from one process to another. Includes saving and loading registers, memory maps, and updating various tables and lists.
A scenario where a higher priority process is indirectly preempted by a lower priority process. This happens when the higher priority process needs a resource held by a medium priority process, which is preempted by a lower priority process.