CPU Scheduling Algorithms The most commonly used CPU scheduling algorithms are First Come First Serve (FCFS), Shortest Job First (SJF), Round Robin (RR) and Priority
-
First Come First Serve Algorithm Scheduling Algorithm In First Come First Serve algorithm the process that arrives first is allocated the CPU first. A queue is maintained in the RAM (ready queue) and the processes are allocated to the CPU as per their position in the queue i.e., the process first in the queue is allocated the CPU first. Key Points of FCFS scheduling algorithm
-
The job that arrives first is scheduled first
-
Is non-preemptive algorithm
-
Implemented using queue.
-
Suffers from Convoy effect.
-
Shortest Job First (SJF) scheduling algorithm In shortest job first scheduling algorithm the process with the least burst time is allocated the CPU first. Shortest job first is of two types:
-
Non – Preemtive (NP)
-
Preemptive (also known as Shortest Remaining Time First(SRTF) 2.1 Shortest Job First (Non Preemptive) scheduling algorithm In SJF(NP) once a process gets the CPU, it releases the CPU only when the burst time is over. The decision of the shortest job is made out of those process which are in the ready queue at any given time thus, keep an eye on the arrival time (else you may get the answer wrong). 2.2 Shortest Job First (Preemptive) scheduling algorithm
-
While a process is running if a process with lower burst time arrives then it will pre-empt the currently running process.
-
Whenever a new process arrives check whether its burst time is less than the remaining burst of currently running process
-
Priority Scheduling algorithm
-
In priority scheduling a number is assigned to each process which indicates its priority level.
-
Lower the number, higher is the priority. 3.1 Priority Scheduling (Non-Preemptive) algorithm 3.2 Priority Scheduling (Preemptive) algorithm Issue with Priority scheduling algorithm Starvation – Priority scheduling can lead to starvation Solution- Solution to the starvation problem is Aging. In aging the priority of a process is increased by one unit after a fixed interval of time. In this way the process will have the highest priority after fixed interval of time and then it is sure to get the CPU.
-
Round Robin Scheduling Algorithm
-
Is pre-emptive algorithm
-
The CPU is shifted to next process after fixed interval of time called time quantum.
-
The process that is preempted is added to the end of the queue.
-
Multilevel Scheduling Algorithm In multilevel scheduling process are divided into groups and each group is assigned a separate queue. Each queue can have a separate scheduling algorithm. The queues themselves are also scheduled. For example, there can be different queues for foreground processes and background processes. The processes in foreground queue can be scheduled using FCFS while the queue containing background processes can be scheduled using SJF(P).