Table of contents
1.
Introduction
2.
Multilevel Queue Scheduling
3.
Features of Multilevel Queue (MLQ) CPU Scheduling
3.1.
Process Priorities
3.2.
Various Queues
3.3.
Pre-emption Method
3.4.
Resource Allocation
3.5.
Feedback System
4.
Advantages of Multilevel Queue Scheduling
5.
Disadvantages of Multilevel Queue Scheduling
6.
Multilevel queue scheduling's working
6.1.
1. Fixed priority preemptive scheduling method
6.2.
2. Time slicing method
6.3.
Example Problem
7.
Frequently Asked Question
7.1.
Is multilevel queue scheduling preemptive or non-preemptive?
7.2.
Which types of process have highest priority in multilevel queue scheduling?
7.3.
What does multilevel queue scheduling suffer from?
7.4.
Is FIFO scheduling preemptive or non-preemptive?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Multilevel Queue Scheduling

Author Rahul Singh
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

At a time, you do so much work on your computer. You listen to music, practice coding questions on Coding Ninjas, chat on WhatsApp, etc. Have you ever wondered how all these processes can work at a time? You can argue about a multi-core CPU, but what if you had a single CPU available? 

multilevel queue scheduling

For this purpose, we use scheduling algorithms. Multilevel queue scheduling is one such CPU scheduling algorithm where the tasks to be performed by the CPU are divided into different groups based on various properties. 

We will learn more about multilevel queue scheduling in this article discussing its working, advantages, and disadvantages.

Multilevel Queue Scheduling

Multilevel queue scheduling is a type of CPU scheduling in which the processes in the ready state are divided into different groups, each group having its own scheduling needs. The ready queue is divided into different queues according to different properties of the process like memory size, process priority, or process type. All the different processes can be implemented in different ways, i.e., each process queue can have a different scheduling algorithm.

Features of Multilevel Queue (MLQ) CPU Scheduling

The features of a Multilevel Queue(MLQ) CPU Scheduling are as follows:

Process Priorities

  • Priority is given to each process. The highest priority process should be carried out first, and so on.
     
  • The process's type, importance, and attributes determine the priority of a process in MLQ CPU scheduling.
     
  • For instance, interactive operations, such as user input and output, might be prioritised over batch processes, such as file backups.

Various Queues

  • MLQ scheduling uses numerous queues, each with a different priority level.
     
  • Processes with greater priorities are put in queues with higher priority levels.
     
  • Processes with lower priorities are put in queues with lower priority levels.

Pre-emption Method

  • Preemption in computing is the act of briefly stopping a running process intending to pick it back up later. 
     
  • This ensures that high-priority processes are carried out promptly.

Resource Allocation

  • The process of allocating resources is how a computing system attempts to satisfy an application's hardware needs.
     
  • MLQ scheduling ensures that procedures with higher priority levels are executed promptly while allowing lower-priority processes to run when ready.

Feedback System

  • To guarantee that an interactive procedure is completed promptly, its priority may be raised if it has been sitting in a lower-priority queue for a long period.
     
  • A feedback mechanism may be used to change the process's priority based on a process's behaviour over time.

Advantages of Multilevel Queue Scheduling

  • Multilevel queue scheduling improves the response time of processes by assigning higher priority to interactive processes, which ensures that these processes are executed first before any other processes
     
  • Multilevel queue scheduling also improves equality as it makes sure that all processes get a chance of execution regardless of their priority. This is done by dividing the processes into different queues, and each queue has its own priority level set
     
  • It helps in reducing starvation which refers to a situation where a process is never able to run because it is always preempted by other higher-priority processes. By assigning lower priority to processes that have been running for a long time, we can reduce the chances of starvation
     
  • Multilevel queue scheduling can be customized in order to meet the specific needs of a system. For example, the number of queues and the priority levels of each queue can be adjusted to optimize the performance of the system

Disadvantages of Multilevel Queue Scheduling

  • Processes are permanently assigned to a queue based on their initial priority, which can lead to inefficiency if a process's priority changes over time.
  • Processes in lower-priority queues may experience starvation, as higher-priority queues are often served first, leading to prolonged wait times for lower-priority processes.
  • Managing multiple queues and their interactions can be complex, requiring careful coordination and additional overhead in the operating system.
  • The static nature of queue assignments can make it difficult to efficiently manage processes with varying CPU and I/O requirements, potentially leading to underutilization of system resources.

Multilevel queue scheduling's working

To understand multilevel queue scheduling, we can take an example where the processes are divided into three different queues given below.

  1. System Processes
  2. Interactive Processes
  3. Batch Processes
Multilevel queue scheduling's working

When a new process comes, that process is added to one of the above-given three process queues based on the classification specified for those process queues. Let us assume that an interactive process like online gaming wants to utilize the CPU.

Then this process will be placed in the Interactive processes queue. Or if any process owned by the operating system itself comes, it is placed in the System Processes queue, and similarly for other processes.

Now we have the question of which process will go first in the CPU if all the process queues have some processes. This dilemma can be solved in different ways. We have discussed two different ways to solve it.

1. Fixed priority preemptive scheduling method

Each queue is assigned an absolute priority over other queues in this method. For example, let us consider the following priority order: 

System Processes queue > Interactive Processes queue > Batch Processes queue

According to this priority order, all the processes in the System Processes queue are initially run, and we don't move to the next process queue until the current process queue is empty. When all the system queue processes are executed, we move to the following priority process queue. And similarly, for the next lower-priority queues.

Suppose we are running the processes from the Interactive process queue, and a new process arrives in the System processes queue which is of higher priority. Then we will run the system process first, and then we will move to the interactive process, and that too only when the system process queue is empty.

So the overall gist of this method is that run the processes with higher priority first and then the processes with subsequent priority.

2. Time slicing method

In this method, processes from each queue are run for a fixed amount of time, and then we move on to the next queue. When we arrive at the last queue, we run it for a specific amount of time, and then we move back to the first queue.

For example, queue1 runs for 50% of CPU time, queue two runs for 30% of CPU time, and queue three runs for 20% of CPU time. In this way, the total CPU time is divided among each queue to run their processes.

We have solved our problem of processes of which queue is to be run first. Now, we come to the fate of individual queues. In each queue, we have multiple processes, so how to decide which process should be run first and for how much time. And do we need to run the processes in all the queues in the same manner as we did in queue one, or can we implement different ways to run the processes in different queues?

The answer to this question is that we can have different implementations for each queue. And there are many algorithms using which we can decide the process to be run first and for how long.

For example:

  • The system process queue can use FCFS(First Come, First Serve) scheduling.
  • The interactive process queue can use SJF(Shortest Job First) scheduling.
  • The batch process queue can use RR(Round Robin) scheduling.
     

Note: The choice of the scheduling algorithms for each queue depends on the use case. It is up to you which scheduling algorithm you want to implement for each queue. The choice of algorithms given above is just for example's sake.

We will now look at an example to understand the overall working of multilevel queue scheduling algorithm.

Example Problem

Let us consider the following four processes.

Example

Let's assume that the priority order of the queues is as follows:

Queue1 > Queue2 > Queue3

The Gantt chart will look as follows:

Gantt Chart

In this example, the processes P1, P2, and P3 arrive at t=0, but still, P1 runs first as it belongs to queue number 1, which has a higher priority. After the P1 process is over, the P2 process in queue 2 runs before the process P3 which is present in queue 3 because queue 2 has a higher priority than queue 3, and then P3 runs. While the P3 process is running, the process P4 belonging to queue 1 arrives. Since queue 1 has higher priority than queue 3, process P3 is stopped (paused), and P4 starts executing. After the execution of P4 is completed, the execution of P3 is resumed.

Now, we have understood how the multilevel queue schedule works. We know that everything has some advantages and disadvantages, which are important to know as they can help determine when it can be used and when it can't be used. So, let's discuss the advantages and disadvantages of multilevel queue scheduling.

Frequently Asked Question

Is multilevel queue scheduling preemptive or non-preemptive?

Multilevel queue scheduling can be either preemptive or non-preemptive in nature, depending on the scheduling algorithm used in each queue. For example, a Round Robin algorithm is preemptive, whereas First Come, First Serve is non-preemptive. 

Which types of process have highest priority in multilevel queue scheduling?

The highest priority is given to interactive processes because these are processes that interact with the user, such as web browsers, word processors, and email clients. This is because so that users get response quickly. 

What does multilevel queue scheduling suffer from?

Multilevel queue scheduling can suffer from thrashing. Thrashing occurs when a process is constantly being preempted by other higher-priority processes. This reduces the performance of the system.

Is FIFO scheduling preemptive or non-preemptive?

FIFO (First In, First Out) scheduling is a non-preemptive scheduling algorithm, where the process that arrives first is executed first and runs to completion before the next process can start, without any interruption.

Conclusion

We have extensively discussed multilevel queue scheduling in operating systems in this article. We hope that this blog has helped you understand what multilevel queue scheduling is, how it works, and its advantages and disadvantages. You can refer to the below-given articles to enhance your knowledge of Operating systems.

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 AmazonAdobeGoogleUberMicrosoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive Programming, etc., as well as some Contests, Test Series and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do upvote our blog to help other ninjas grow.

Happy Learning!!!

Live masterclass