Scheduling Algorithm
The scheduling algorithm is a set of rules that determine how the CPU is allocated to processes. The scheduler decides which process to run next based on the scheduling algorithm. The scheduling algorithm uses information about the processes to determine which process should be executed next.
Types of Scheduling Algorithm
Following are the several types of scheduling algorithms, each with its own strengths and weaknesses. The different types of scheduling algorithms are:
- First-Come, First-Served (FCFS) Scheduling
- Shortest Job First (SJF) Scheduling
- Priority Scheduling
- Round Robin (RR) Scheduling
First-Come, First-Served (FCFS) Scheduling:-
FCFS stands for First Come, First Serve, and it is the simplest scheduling algorithm. In this algorithm, the process that arrives first gets the CPU first. The process runs until it either completes its task, or it gets blocked by I/O operations. The following process in the queue is then given access to the CPU. This algorithm is easy to implement and is fair because it treats all processes equally. However, it has some drawbacks.
For example, it can lead to poor utilization of resources if a long-running process arrives early and monopolizes the CPU.
Advantages
- Simple and easy to understand
- Fair to all processes as they are executed in the order they arrived
- No starvation: all processes eventually get CPU time
Disadvantages
- Not suitable for time-critical systems as it does not consider the length of the process
- Long processes may hold up the CPU, leading to increased waiting time for other processes
- It is not efficient as the average waiting time can be high
Shortest Job First (SJF) Scheduling:-
SJN stands for Shortest Job Next, and it is an improvement over the FCFS algorithm. In SJN, the process that requires the least amount of CPU time is given priority. The idea behind this algorithm is that short processes tend to complete faster, leading to a higher throughput and better resource utilization. To implement SJN, the scheduler must know the CPU burst time required by each process. The scheduler maintains a ready queue of processes, sorted by their CPU burst times in ascending order. When a new process arrives, the scheduler checks the ready queue and assigns the CPU to the process with the shortest CPU burst time.
Advantages
- It minimizes the average waiting time
- It is efficient for short processes
- It is optimal as it ensures that the process with the shortest CPU burst time is executed first
Disadvantages
- It can lead to starvation for longer processes
- It is difficult to predict the execution time of a process accurately
- It may cause problems when new short processes arrive frequently
Priority Scheduling:-
Priority Scheduling is a non-preemptive scheduling algorithm that prioritizes each process. The process with the highest priority is executed first, and the CPU is allocated to that process until it completes or is blocked. The following process with the highest priority is then executed. This algorithm assigns a priority to each process and allocates the CPU to the process with the highest priority. It can also be preemptive or non-preemptive. Priority scheduling can reduce the waiting time for important processes, but it may also cause starvation for lower-priority processes if higher-priority processes keep arriving. If two processes have the same priority, then it uses first-come, first-served (FCFS) scheduling.
Advantages of Priority Scheduling
- High-priority processes are executed first.
- Suitable for real-time systems.
- Ensures that important processes are completed quickly.
Disadvantages of Priority Scheduling
- Low-priority processes may suffer from starvation.
- It is not suitable for multiprogramming systems with a large number of processes.
- Processes with the same priority may face unfair treatment.
Round Robin (RR) Scheduling
Round Robin (RR) Scheduling is a preemptive scheduling algorithm that assigns a fixed time slice or quantum to each process. The process is executed for the specified time slice and then moved to the back of the ready queue. The next process in the queue is then executed for its time slice, and the process is rotated in a circular manner. This algorithm assigns the CPU to each process in the ready queue for a fixed time quantum (or slice). After the quantum expires, the process is preempted and moved to the end of the queue. RR is fair and simple to implement but may cause frequent context switches and overhead.
Advantages of Round Robin Scheduling
- Ensures that each process gets a fair share of the CPU time.
- Suitable for multiprogramming systems with a large number of processes.
- Low-priority processes do not suffer from starvation.
Disadvantages of Round Robin Scheduling
- Processes may experience overhead due to the context switching between processes.
- Short time slices may lead to poor performance for CPU-bound tasks.
- Long time slices may lead to poor response time for I/O-bound tasks.
