Table of Content
Scheduling Algorithms decide which of the processes in the ready queue is to be allocated to the CPU. There are many types of CPU scheduling algorithms. The main algorithms are discussed here in detail. Let’s see.
Out of these, the algorithm that maximizes the CPU utilization and throughput, and minimizes the turnaround time, waiting time, and response time, is the best of all.
It will be better to understand this topic if you have already read the article on CPU Scheduling.
FCFS Scheduling
It is a simple CPU scheduling algorithm. The criteria of this algorithm are the process that requests the CPU first or the process which enters the ready queue first served. If a process requests, it is loaded by a short-term scheduler into the ready queue. The process is then executed by a dispatcher and connected to the CPU. It is called the FCFS scheduling in an operating system.
To learn more about the algorithm and how it works practically, You can practice some problems related to FCFS.
The main disadvantage of this algorithm is aging. Due to this problem, big jobs have to wait for the CPU for a long time.
Shortest Remaining Time First(SRTF Scheduling)
This algorithm is the preemptive scheduling algorithm, in which the short-term scheduler always chooses the process that has the shortest remaining processing time. When the new process joins the ready queue, the short-term scheduler compares the time of the executing process and the new process.
If the new process has the least CPU burst time, the scheduler selects that job and connects to the CPU, otherwise, continues in the old process. You can practice some problems related to SRTF.
Round Robin(RR) Scheduling
It is a preemptive scheduling algorithm. It is designed typically for time-sharing systems. In this algorithm, the CPU switches between the processes when the time quantum has expired, and the CPU switches to another job. In this algorithm, the ready queue is circular. The time quantum is dependent on the operating system.
Advantage
The main advantage of this algorithm is easy to implement, and it is simple.
Disadvantage
The drawback of this algorithm is particularly troublesome for the time-sharing system, and another drawback is average waiting time is very high, which may impact the performance of the CPU.
Shortest Job First(SJF) Scheduling
The criteria of this algorithm in that the process having the smallest CPU burst time, CPU is assigned to the process next, if two processes have the same CPU burst time, FCFS is used to break the tie.
Advantage
It has the least average waiting time, average turnaround time, and average response time.
Disadvantage
- Knowing the length of the next CPU burst time is difficult.
- It is an optimal algorithm. It cannot be implemented at the level of short-term CPU scheduling.
New processes were added to the tail of the ready queue. The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after a one-time quantum, and dispatches the process.
One of the two things will happen in this algorithm.
If the process may have a CPU burst time is less than one time quantum, then the process releases the CPU voluntarily. The scheduler will then proceed to the next process in the ready queue.
Otherwise, if the CPU burst time of the concurrently running process is longer than the one-time quantum, then the process will be put at the tail of the ready queue. The CPU scheduler will then select the next process.
Priority Scheduling
Generally, priorities are of two types. One is the internal priority, and the second is the external priority. External priority means it is external to the operating system. The CPU is allocated to process with the highest priority.
The priorities use some measurable quantities to compute the priority of a process. For example, time limits, memory requirements, the number of open files, and the ratio of an average I/O burst to an average CPU burst have been used in computing priorities.
Disadvantage
The major problem with priority scheduling is starvation. Starvation means only high-priority processes are executing, but low-priority jobs are waiting for the CPU for a long time.
Multilevel Queue Scheduling
In this algorithm, there is a partition of the ready queue. Each queue is capable of loading the same type of jobs. Each ready queue has its scheduling algorithm. Each queue has absolute priority over low-priority queues.
In the above example, the process of the student queue cannot run without running the system process, the foreground process, and the background process queues. If any foreground process enters into the ready queue while a background process is running the batch process would be preempted.
Multilevel Feedback Queue Scheduling
The scheduling algorithm allows a process to move between the queues. The idea is to separate the process with different CPU burst characteristics. If any process consumes too much CPU time, it will move to the next low-priority queue. If a process is waiting for a long time in the lower priority queue may move to a higher priority queue. The main advantage of this algorithm is to prevent the starvation.
Consider a multilevel feedback queue scheduled with Q0, Q1, and Q2. The scheduler first executes all processes in Q0 only when Q0 is empty it will execute the process in Q1. Similarly, the process in Q2 will only be executed, if Q0 and Q1 are empty.
Advantage
The main advantage of this algorithm is, that the shorter process will complete quickly, and the longer process need not wait much time in the ready queue, and will gradually drift downward.
Disadvantage
In a multiprogramming environment server, all processes request the resources(I/O device, Clock, etc.) from the operating system. If the resources are available at that time, the OS grants the resources to that process, if not available, then the process has to wait until the resources are released.
Sometimes the process does not release the resources they are blocked by the process. This situation is said to be Deadlock.