Types of Scheduling Algorithms in OS
All scheduling algorithms in operating systems are either preemptive or non-preemptive. Following is the list of the most frequently used scheduling algorithms.
1. First Come First Serve (FCFS)
It is the simplest scheduling algorithm that schedules processes based on their arrival time. A process that arrives first is executed first, followed by the next. It is a non-preemptive scheduling algorithm that does not prioritize one process over another. They are executed in the order of their arrival at the CPU. FCFS uses the concept of First-in-First-out (FIFO).
Advantages
- It uses simple logic and is easy to implement.
- The chances of starvation are highly unlikely.
- Ensures that every process gets a chance to execute, preventing starvation.
- Low overhead in terms of implementation and system resources.
Disadvantages
- It consumes a lot of time and tends to minimize CPU utilization.
- It reduces performance as the average wait time is high.
- Inefficient when tasks have varying burst times, as short jobs wait behind long ones.
- Can result in higher turnaround time, especially with a mix of short and long jobs.
2. Shortest Job First (SJF)
This algorithm schedules processes based on their burst time. The process having the shortest burst time is scheduled first, provided that all the processes in the queue arrive at the same time. It is also known as the Shortest Job Next algorithm. SJF is a non-preemptive algorithm that requires the processor to know the burst time of all the processes in advance. If two or more processes have the same burst time, the FCFS is used to schedule them further.
Advantages
- Increased throughput and shorter turnaround time.
- It minimizes waiting time for processes that are ready for execution.
- Effective in batch processing where job lengths are known in advance.
- Provides predictable and deterministic performance.
Disadvantages
- It may lead to starvation, as longer processes have to wait for their turn until the shorter processes have been executed.
- Accurate prediction of job lengths is often challenging.
- Requires continuous monitoring of job lengths, adding complexity.
- A long job may need to wait indefinitely if shorter jobs keep arriving.
3. Longest Job First (LJF)
This algorithm works very much like the Shortest Job First Algorithm, the only difference being that LJF schedules processes with the longest burst time first.
4. Shortest Remaining Job First (SRJF)
Shortest Remaining Job First is the preemptive version of the Shortest Job First algorithm. Processes are scheduled according to the shortest remaining time. The process with the shortest burst time is scheduled to execute first. The arrival time of all processes need not be the same. If a process with the shortest burst time arrives during the execution of another process, then it will be preempted, and the newly arrived job is executed first.
Advantages
- Processes are executed at a much faster rate compared to the SJF algorithm.
- Effective in batch processing environments where job characteristics are known in advance.
- Leads to low turnaround time as short jobs are quickly executed.
- Tasks with shorter remaining execution times are scheduled first, minimizing overall waiting time.
Disadvantages
- It is impossible to implement it in systems where the required CPU time is unknown. It may lead to starvation and increased overhead.
- Accurately predicting the remaining execution time of each task is difficult.
- Long tasks may face starvation if constantly preempted by shorter tasks.
- Frequent preemption and context switching introduce overhead.
5. Longest Remaining Job First (LRJF)
The Longest Remaining Job First algorithm is similar to the SRJF algorithm. The only difference between the two is that the process with the longest burst time is scheduled to execute first.
6. Priority Scheduling
Priority Scheduling is a non-preemptive scheduling algorithm in which each process is assigned a priority. The process with the highest priority is scheduled first, followed by the ones with lower priority. Processes are given their priority based on memory, time and resource requirements.
Advantages
- Processes with high priority need not wait for long. Hence, it is suitable for applications with fluctuating time and resource requirements.
- Priorities can be adjusted based on the specific requirements of the system or application.
- High-priority tasks are executed promptly, leading to efficient resource utilization.
- Processes are assigned priority levels, allowing for the execution of higher-priority tasks first.
Disadvantages
- Since higher priority processes take over the majority of the CPU time, it leads to starvation of lower priority processes.
- Priority inversion can occur, where a low-priority task holds a resource needed by a higher-priority task.
- The need for dynamic adjustments to priorities adds complexity to the scheduling algorithm.
- Assigning accurate and meaningful priorities to diverse processes can be challenging.
7. Round Robin Scheduling
Round robin scheduling is a preemptive scheduling algorithm in which a process gets executed cyclically. Every process in the Ready queue has a time slice allotted to it. This is known as the time quantum. The CPU is assigned to the process for that time quantum. A process that completes the execution within the time quantum is terminated. If a process cannot complete its execution within the time quantum, it is suspended and added to the ready queue again. This algorithm is primarily used in time-sharing systems.
Advantages
- All processes have the same priority and are given an equal share of CPU time.
- There is no starvation and no process is left unattended.
- Short processes generally experience lower waiting times compared to some other scheduling algorithms.
- It is a straightforward and easy-to-implement scheduling algorithm.
Disadvantages
- It has a long average waiting time.
- Setting a short time quantum can reduce CPU utilization and reduce performance.
- The algorithm may result in lower throughput compared to other scheduling algorithms, especially when processes have varying burst times.
- Short processes can get stuck waiting behind a long process, leading to a convoy effect where short processes are delayed.
8. Highest Response Ratio Next (HRRN)
It is a non-preemptive scheduling algorithm that schedules processes based on a response ratio. The process with the highest response ratio is scheduled first. This helps reduce starvation in the system. The response ratio is calculated using the following formula.
Response ratio = (Waiting time + Burst time) / Burst time
9. Multiple-Level Queues Scheduling
In this algorithm, multiple algorithms with common characteristics combine to form a group and are scheduled as a whole. Multiple queues are made to store processes based on similar characteristics, and each queue has its own scheduling algorithm. The operating system assigns priority to every queue.
10. Multilevel Feedback Queues Scheduling
This algorithm is similar to multilevel queue scheduling, except that the processes can change their queue after partial execution. Higher priority queues can preempt lower priority queues. If a process uses too much CPU time, it moves to a lower priority queue.
You can also read about layered structure of operating system.
Must Read Evolution of Operating System
Frequently Asked Questions
What is scheduling algorithms in operating system?
Scheduling algorithms manage the order in which processes execute in an operating system. They determine which process to run next and for how long.
What are the 5 scheduling algorithm types?
The 5 scheduling algorithm types include First-Come, First-Served (FCFS), Shortest Job Next (SJN), Priority Scheduling, Round Robin, and Multilevel Queue Scheduling.
What are the 3 types of scheduling in operating system?
The three main types of scheduling in an operating system are short-term scheduling (CPU scheduling), medium-term scheduling (Swapping), and long-term scheduling (Job Scheduling).
Conclusion
In this article, we have extensively discussed Scheduling algorithms in Operating Systems. We started with a brief introduction to Scheduling algorithms and then moved on the see their types. We also explored the various scheduling algorithms in operating systems that are currently in use.
Recommended Readings:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Code360.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Code360.
38+ registered 