Scheduling Algorithms in OS

types of scheduling algorithms, Multilevel Queue Scheduling
Multilevel Queue Scheduling

Scheduling Algorithms decide which of the process in the ready queue is to allocated to the CPU. There are many types of CPU scheduling algorithms. Main algorithms discussed here in detail. Let's see.


Out of these, the algorithm who maximizes the CPU utilization and throughput, and minimizes the turnaround time, waiting time and response time, are the best of all.

It will be better to understand this topic if you have already read the article on CPU Scheduling.


FCFS Scheduling in OS

It is the simple CPU scheduling algorithm. The criteria of this algorithm are the process that requests the CPU first or the process which enters ready queue first, served first. If a process requests then it is loaded by short-term scheduler into the ready queue. The process is then connected to the CPU by a dispatcher for execution. It is called the FCFS scheduling in operating system.

To know more about the algorithm that 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 having the least CPU burst time, the scheduler selects that job and connect to the CPU, otherwise, continue 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 is expired, the CPU switches to another job. In this algorithm, the ready queue is a circular queue. The time quantum 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, this may impact on the performance of the CPU.


Shortest Job First(SRTF) Scheduling

The criteria of this algorithm in which 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 least average waiting time, average turnaround time and average response time.

Disadvantage

  1. Knowing the length of the next CPU burst time is difficult.
  2. It is an optimal algorithm. It cannot be implemented by at the level of short-term CPU scheduling.

New processes added to the tail of the ready queue. The CPU scheduler picks the first process from the ready queue, set a timer to interrupt after 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 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 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 in OS

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 average I/O burst to an average CPU burst have 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 OS

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 it's own scheduling algorithm. Each queue has absolute priority over low priority queues.

In the above example, the process of 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 was running the batch process would be preempted.


Multilevel Feedback Queue Scheduling in OS

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.

Multilevel Feedback Queue Scheduling Example

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, 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 multiprogramming environment server all process 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 processes, if not available, then the process has to wait until the resources release.

Sometimes the process does not release the resources they are blocked by the process. This situation is said to be Deadlock.

I hope you have cleared about the types of Scheduling Algorithms in OS.


Practice MCQ Questions on SabQuiz

Practice Now