CPU scheduling is the process of deciding which task should use the CPU while others wait. Since multiple tasks may be ready at the same time, the system needs a way to manage them efficiently. Scheduling ensures that the CPU is always working and that tasks are completed in a fair and timely manner. Some methods allow a task to finish before moving to the next one, while others may pause a task to let another one run. The goal is to reduce waiting time, improve response speed, and make the system more efficient based on workload needs.
CPU scheduling Terminologies
Arrival Time: when a process enters in a ready state
Burst Time/Execution Time: is the total time a process requires for execution on the CPU without interruption.
Completion Time: when process complete and exit from a system
Turnaround Time (TAT): is the total time taken for a process to complete execution, from submission to completion.
Response Time (RT): is the time from when a process is submitted until it starts execution for the first time.
Process: A process is an executing program with its own memory, resources, and state.
Types of CPU scheduling Algorithm
There are mainly five types of process scheduling algorithm
First Come First Serve (FCFS)
Concept of FCFS Scheduling
First-Come, First-Served (FCFS) is the simplest CPU scheduling algorithm. In this method, the process that arrives first in the ready queue gets executed first.
It follows a queue-based structure, where processes are scheduled in the exact order of their arrival. Once a process starts execution, it runs until completion without being interrupted.
Advantages of FCFS:
✅ Easy to implement using a queue.
✅ Fair scheduling—processes are executed in the order they arrive.
✅ Minimal overhead—no context switching overhead as processes are not interrupted.
Disadvantages of FCFS:
❌ Convoy effect - If a long process arrives first, it delays all others.
❌ Not ideal for time-sharing systems since it lacks preemption.
❌ Higher waiting time for shorter processes, leading to inefficiency.
Shortest-Job-First (SJF) Scheduling
Concept of SJF Scheduling
Shortest-Job-First (SJF) is a CPU scheduling algorithm where the process with the shortest execution time is selected first.
This method minimizes waiting time and improves overall efficiency. It can be either preemptive or non-preemptive, depending on
whether a new process with a shorter burst time can interrupt an ongoing process.
Advantages of SJF:
✅ Reduces average waiting time, improving overall system performance.
✅ Efficient for batch processing, as shorter processes get completed quickly.
✅ Minimizes turnaround time by prioritizing shorter jobs.
Disadvantages of SJF:
❌ Requires knowledge of burst time beforehand, which may not always be available.
❌ Starvation - Longer processes may be delayed indefinitely if short processes keep arriving.
❌ Difficult to implement in real-time systems due to unpredictable job lengths.
Shortest Remaining Time (SRT) Scheduling
Concept of SRT Scheduling
Shortest Remaining Time (SRT) is the preemptive version of Shortest Job First (SJF). At any given time, the process with the smallest remaining execution time is selected.
If a new process arrives with a shorter burst time than the currently running process, it preempts the execution and takes over.
Advantages of SRT:
✅ Provides better turnaround time compared to non-preemptive SJF.
✅ More responsive for shorter processes in a dynamic system.
✅ Reduces average waiting time for processes.
Disadvantages of SRT:
❌ Starvation - Long processes may face indefinite delays due to frequent interruptions.
❌ More complex to implement as the scheduler must continuously monitor burst times.
❌ Increased CPU overhead due to frequent preemptions.
Priority Scheduling
Concept of Priority Scheduling
Priority Scheduling assigns a priority to each process, and the CPU is allocated to the process with the highest priority. If multiple processes have the same priority, they are scheduled in FCFS order.
It can be either preemptive or non-preemptive.
Advantages of Priority Scheduling:
✅ Ensures that critical tasks with high priority get CPU time quickly.
✅ More control over process execution based on priority levels.
✅ Can be optimized for different use cases like real-time systems.
Disadvantages of Priority Scheduling:
❌ Starvation - Lower priority processes may never get executed if high-priority processes keep arriving.
❌ Requires an external mechanism like aging to prevent indefinite blocking of lower-priority processes.
❌ Complexity increases with dynamic priority adjustments.
Round Robin (RR) Scheduling
Concept of Round Robin Scheduling
Round Robin (RR) is a preemptive CPU scheduling algorithm where each process is assigned a fixed time slice (quantum).
Processes are executed in a cyclic order, ensuring fairness. If a process does not complete within its quantum, it is moved to the end of the queue.
Advantages of Round Robin:
✅ Provides a fair and equal share of CPU time to all processes.
✅ Reduces starvation since all processes get a chance to execute.
✅ Well-suited for time-sharing and interactive systems.
Disadvantages of Round Robin:
❌ Higher average turnaround time compared to SJF or Priority Scheduling.
❌ Performance depends on the time quantum—too small increases context switching, too large behaves like FCFS.
❌ Frequent context switching leads to increased CPU overhead.