Scheduling Algorithms in Operating System
Scheduling Algorithms in OS: Overview
In the operating system, everything is carried out by processes. At any given time, there is only one process that is running on the CPU. A process scheduler removes one process from the running state in the CPU and selects another process to run based on some scheduling algorithms in OS.
What is a Scheduling Algorithm?
A CPU scheduling algorithm is used to decide among different processes waiting for CPU access, determining which one will execute and which ones to hold or remove from execution. The main goal or objective of CPU scheduling algorithms in OS is to use different scheduling algorithms to keep cpu usage efficient while ensuring that the OS has at least one process ready for execution in the ready queue.
There are two types of scheduling algorithms in OS: The choice of algorithm depends on system goals such as fairness, responsiveness, and efficiency.
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Preemptive Scheduling Algorithms
In these algorithms, processes are assigned with priority. Whenever a high-priority process comes in, the lower-priority process that has occupied the CPU is preempted. That is, it releases the CPU, and the high-priority process takes the CPU for its execution.
Non-Preemptive Scheduling Algorithms
In these algorithms, we cannot preempt the process. That is, once a process is running on the CPU, it will release it either by context switching or terminating. Often, these are the types of algorithms that can be used because of the limitations of the hardware.
There are some important terminologies to know for understanding the scheduling algorithms:
Arrival Time: This is the time at which a process arrives in the ready queue.
Completion Time: This is the time at which a process completes its execution.
Burst Time: This is the time required by a process for CPU execution.
Turn-Around Time: This is the difference in time between completion time and arrival time. This can be calculated as:
Turn Around Time = Completion Time – Arrival Time
Waiting Time: This is the difference in time between turnaround time and burst time. This can be calculated as:
Waiting Time = Turn Around Time – Burst Time
Throughput: It is the number of processes that are completing their execution per unit of time.
Why Do We Need Scheduling?
A process to complete its execution needs both CPU time and I/O time. In a multiprogramming system, there can be one process using the CPU while another is waiting for I/O whereas, in a uni programming system, time spent waiting for I/O is completely wasted as the CPU is idle at this time. Multiprogramming can be achieved by the use of process scheduling, which lets the OS handle multiple processes efficiently while one waits for I/O and another uses the CPU.
The purposes of a scheduling algorithm are as follows:
-
Maximize the CPU utilization, meaning that keep the CPU as busy as possible.
-
Fair allocation of CPU time to every process
-
Maximize the Throughput
-
Minimize the turnaround time
-
Minimize the waiting time
-
Minimize the response time
Good scheduling improves system performance and overall system performance, not just individual process metrics.
Types of Scheduling Algorithms in OS
Turn Learning into Career Growth
First Come First Serve (FCFS) Scheduling Algorithm
First Come First Serve is the easiest and simplest CPU scheduling algorithm to implement. In this type of scheduling algorithm, the CPU is first allocated to the process which requests the CPU first. That means the process with minimal arrival time will be executed first by the CPU. It is a non-preemptive scheduling algorithm as the priority of processes does not matter, and they are executed in the manner they arrive in front of the CPU. This scheduling algorithm is implemented with a FIFO(First In First Out) queue. As the process is ready to be executed, its Process Control Block (PCB) is linked with the tail of this FIFO queue. Now when the CPU becomes free, it is assigned to the process at the beginning of the queue.
Advantages
-
Involves no complex logic and just picks processes from the ready queue one by one.
-
Easy to implement and understand.
-
Every process will eventually get a chance to run so no starvation occurs.
Disadvantages
-
Waiting time for processes with less execution time is often very long.
-
It favors CPU-bound processes then I/O processes.
-
Leads to convoy effect.
-
Causes lower device and CPU utilization.
-
Poor performance as the average wait time is high.
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Shortest Job First (SJF) Scheduling Algorithm
Shortest Job First is a non-preemptive scheduling algorithm in which the process with the shortest burst or completion time is executed first by the CPU. That means the lesser the execution time, the sooner the process will get the CPU. In this scheduling algorithm, the arrival time of the processes must be the same, and the processor must know beforehand how much time process execution will require for all the processes. If two processes have the same burst time, then First Come First Serve (FCFS) scheduling is used to break the tie.
The preemptive mode of SJF scheduling is known as the Shortest Remaining Time First scheduling algorithm.
Advantages
-
Results in increased Throughput by executing shorter jobs first, which mostly have a shorter turnaround time.
-
Gives the minimum average waiting time for a given set of processes.
-
Best approach to minimize waiting time for other processes awaiting execution.
-
Useful for batch-type processing where CPU time is known in advance and waiting for jobs to complete is not critical.
Disadvantages
-
May lead to starvation as if shorter processes keep on coming, then longer processes will never get a chance to run.
-
Time taken by a process must be known to the CPU beforehand, and time process estimation is difficult in practice.
RoundRobin Scheduling Algorithm
The Round Robin algorithm, or round robin rr, is related to the First Come First Serve (FCFS) technique but implemented using a preemptive policy. In this scheduling algorithm, processes are executed cyclically, and each process is allocated a fixed time quantum, sometimes described as a fix time slice. The ready queue of the processes is implemented using the circular queue technique in which the CPU is allocated to each process for the given time quantum and then added back to the ready queue to wait for its next turn. If the process executes until the quantum expires, then it will be preempted, and the CPU is assigned to some other process for the given period of time. But if the process is not completely executed within the given time quantum, then preempted processes are again added to the ready queue and wait for their turn to complete execution.
The round-robin scheduling is the oldest and simplest scheduling algorithm that derives its name from the round-robin principle. In this principle, each person will take an equal share of something in turn.
This algorithm is mostly used for multitasking in time-sharing systems and operating systems having multiple clients so that they can make efficient use of resources.
Advantages
-
All processes are given the same priority; hence all processes get an equal share of the CPU.
-
Since it is cyclic in nature, no process is left behind, and starvation doesn’t exist.
Disadvantages
-
The performance of Throughput depends on the length of the time quantum. Setting it too short increases the overhead and lowers the CPU efficiency, but if we set it too long, it gives a poor response to short processes and tends to exhibit the same behavior as FCFS.
-
The average waiting time of the Round Robin algorithm is often long.
-
Context switching is done a lot more times and adds to the overhead time.
Shortest Remaining Time First (SRTF) Scheduling Algorithm
Shortest Remaining Time First (SRTF) scheduling algorithm is basically a preemptive mode of the Shortest Job First (SJF) algorithm in which jobs are scheduled according to the shortest remaining time. In this scheduling technique, if a shorter process arrives, the currently running process is preempted and the shorter job is executed first. This helps improve process execution, and the arrival time of all processes need not be the same.
Advantages
- Processes are executed faster than SJF, being the preemptive version of it.
Disadvantages
-
Context switching is done a lot more times and adds to the overhead time.
-
Like SJF, it may still lead to starvation and requires the knowledge of process time beforehand, which is difficult to estimate when the execution length is not known in advance.
-
Impossible to implement in interactive systems where the required CPU time is unknown.
Master the complexities of operating systems with Scaler Topics Free certification course. Join now & learn the foundations of the operating system.
Conclusion
-
Scheduling algorithms tell the CPU which will be the next process to have CPU time.
-
The main goal of scheduling algorithms in OS is to Maximize Throughput.
-
Scheduling algorithms can be preemptive and non-preemptive.
-
First Come First Serve, Shortest Job First, Shortest Remaining Time First, and Round Robin are four widely used common scheduling algorithms in operating systems, each with its own advantages and disadvantages.
-
The best choice among scheduling algorithms in operating systems depends on the situation, and different scheduling algorithms suit different requirements, needs, and hardware and software capabilities.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more