Multilevel Queue (MLQ) Scheduling with Examples and Programs

In the Multilevel queue scheduling, all process are presented in the ready state that are divided into different group and then every group containing its own scheduling needs. So, here we will explain about what is multilevel queue scheduling algorithm in OS; involving with many examples and programs in C, C++, and Java with their outputs. This is unique article over the internet. Making ensure that at the end of this post; you will definitely fully aware about Multilevel Queue Scheduling without any hindrance.

What is Multilevel Queue Scheduling in OS?

Multilevel Queue Scheduling is a CPU scheduling algorithm that is used in operating systems to manage the allocation of CPU resources to different processes.

In this algorithm, the ready queue is divided into multiple queues based on the process characteristics such as priority, CPU burst time, memory requirement, etc. Each queue is assigned a different priority level, and each queue has its own scheduling algorithm. The highest priority queue gets the highest priority for CPU allocation, and the lowest priority queue gets the lowest priority.

Multilevel-Queue-Scheduling

In general, there are three types of queues: foreground (interactive) queue, background (batch) queue, and system queue. The foreground queue contains interactive processes that need quick response time, and the background queue contains processes that can run in the background with lower priority. The system queue contains processes that need to access system resources, such as device drivers.

The processes are initially assigned to the foreground queue, and after a certain amount of time, they are moved to the background queue. The processes in the foreground queue are scheduled using a round-robin algorithm to ensure that each process gets a fair share of the CPU time. The processes in the background queue are scheduled using a first-come, first-served algorithm.

The multilevel queue scheduling algorithm ensures that the processes that need quick response time are given higher priority, while the processes that can run in the background are given lower priority. This results in a more efficient use of CPU resources and ensures that the system is responsive to the user’s needs.

‘MLQ Scheduling’ Tutorial Headlines:

In this section, we will show you all headlines about this entire article; you can check them as your choice; below shown all:

  1. What is Multilevel Queue Scheduling in OS?
  2. Multilevel Queue Scheduling Working Principle
  3. How are the Queues Scheduled?
  4. Multilevel Queue Scheduling Example with Gantt Chart
  5. What is Real-Life Example of MLQ Scheduling?
  6. Multilevel Queue Scheduling Algorithm Implementation
  7. Multilevel Queue Scheduling Vs Multilevel Feedback Queue Scheduling
  8. What are the Advantages and Disadvantages of Multilevel Queue Scheduling?
  • Advantages of Multilevel Queue Scheduling
  • Disadvantages of Multilevel Queue Scheduling
  1. Features of Multilevel Queue Scheduling
  2. Multilevel Queue Scheduling Program in C
  3. Multilevel Queue Scheduling Program in C++
  4. Multilevel Queue Scheduling Program in Java

Let’s Get Started!!

Multilevel Queue Scheduling Working Principle

Here, we are going to explain about how Multilevel queue scheduling works, as follow them:

Also Read: Shortest Job First (SJF) Scheduling with Examples and Programs!!

Each queue contains the absolute priority over the low priority queues. It may be no execute any process until the higher priority queues are empty. Like as, showing above example, no other process might execute until and unless the queues for system, interactive, and editing processes are getting free. Whenever, the interactive editing process is getting to put the ready queues while a batch process is underway, then the batch process would be pre-empted.

Multilevel-Queue-Scheduling-working

Here, we will describe of all processes in brief that are applied in the upper example:

System Process: The operating system contains own process to execute that is referred as the System Process.

Interactive Process: In this process, same kinds of interaction should occur.

Batch Process: Batch processing is an operating system feature that helps to gather the programs and data into a batch before processing starts.

Student Process: As you know that the system process is always provide the highest priority, whereas the student processes are always given the lowest.

How are the Queues Scheduled?

In a Multilevel queue scheduling, the queues are typically organized into multiple levels, with each level containing a set of processes that have similar characteristics, such as the priority or type of the process. Each level has its own scheduling algorithm, and the processes are scheduled in the order of the levels.

Also Read: Priority Scheduling Algorithm in OS with Examples & Programs!!

The scheduling of the queues in a multilevel queue scheduling typically follows a few basic principles:

Each queue has a different priority level, with the highest priority queues at the top and the lowest priority queues at the bottom.

Each queue is assigned a different scheduling algorithm, which is appropriate for the type of processes in that queue. For example, the highest priority queue might use a Round Robin scheduling algorithm, while the lower priority queues might use a First-Come-First-Serve (FCFS) scheduling algorithm.

The processes are initially placed in the queue that corresponds to their priority level. As the processes are executed, they may move up or down in the queue, depending on their behaviour and the scheduling algorithm used.

When a process is completed or blocked, it is removed from the current queue and placed in the appropriate queue according to its priority level.

The scheduling algorithm for each queue is run independently of the other queues, ensuring that each queue is processed according to its own priority and algorithm.

Overall, the aim of multilevel queue scheduling is to provide a balance between the needs of different types of processes, while ensuring that the system operates efficiently and fairly.

Multilevel Queue Scheduling Example with Gantt Chart

Sure, here’s an example of multilevel queue scheduling with a Gantt chart:

Suppose we have four processes: P1, P2, P3, and P4. We’ll use three queues for scheduling: a high-priority queue for real-time processes, a medium-priority queue for interactive processes, and a low-priority queue for batch processes. The time quantum for each queue is 2 units of time.

The arrival time and burst time for each process are as follows:

Process                Arrival Time      Burst Time

P1                                     0                  8

P2                                     1                  4

P3                                     2                  9

P4                                     3                  5

The scheduling algorithm is as follows:

Real-time processes are always scheduled first.

If there are no real-time processes, interactive processes are scheduled next.

If there are no interactive processes, batch processes are scheduled last.

Here’s how the scheduling would look like with a Gantt chart:

Time      Queue 1 (real-time)   Queue 2 (interactive) Queue 3 (batch)

0              P1                          

2              P1                          

4              P1                                                           P2          

6              P1                                                           P2          

8              P1                                                           P2                              P4

10           P3                                                           P2                              P4

12           P3                                                                                              P4

14           P3                                                                                              P4

16           P3                                                                                              P4

18           P3                          

19                                          

At time 0, P1 arrives and is placed in the high-priority queue. It is the only process in the queue, so it runs immediately. At time 1, P2 arrives and is placed in the medium-priority queue. However, since there are no real-time processes in the high-priority queue, P2 is allowed to run. P2 runs for 2 time units before being pre-empted by P1, which has returned to the high-priority queue.

At time 3, P4 arrives and is placed in the low-priority queue. However, since there are still real-time and interactive processes in the higher-priority queues, P4 does not run yet. P3 arrives at time 5 and is placed in the medium-priority queue. Since there are no real-time processes in the high-priority queue and P1 has finished, P3 is allowed to run.

At time 8, P4 is finally allowed to run, since there are no real-time or interactive processes waiting to run. P3 continues to run until it finishes at time 13. Finally, P4 finishes at time 18, and there are no more processes waiting to run. The Gantt chart shows that the CPU is idle for one time unit before the end of the scheduling.

What is Real-Life Example of MLQ Scheduling?

A real-life example of MLQ scheduling can be seen in a computer system that is running multiple applications simultaneously.

Also Read: Process Life Cycle in Operating System | Process State in OS

For instance, suppose a computer system has three queues: high priority, medium priority, and low priority. In this scenario, the high priority queue may contain processes that require immediate attention, such as critical system processes, while the medium and low priority queues may contain less important processes, such as background tasks or user applications.

The MLQ scheduler would allocate resources to the processes in each queue based on their priority level, with the high priority queue being given the highest priority for resource allocation. As the high priority processes complete, the scheduler would then allocate resources to the medium and low priority queues.

Overall, the MLQ scheduling algorithm helps to ensure that critical processes are given priority access to system resources, while also maintaining fairness and efficiency in the allocation of resources to other processes.

Multilevel Queue Scheduling Algorithm Implementation

There, we will show you basic flowchart for a multilevel queue algorithm:

Also Read: What is Process in OS? Types of Process in Operating System!!

Initialize the Queues: Create multiple queues for different types of processes.

Define the Priority Levels: Assign each queue a different priority level.

Allocate Processes to Their Respective Queues: When a process enters the system, it is placed in the queue that corresponds to its type.

Schedule the Processes: The scheduler selects the highest priority queue and runs all the processes in that queue until they are complete or until a higher priority queue needs attention.

Adjust Priorities: If a process in a lower priority queue waits for too long, its priority may be increased to prevent starvation.

Repeat: The process continues until all processes have been completed.

Note that this is a basic flowchart and there can be variations depending on the specific implementation of the algorithm.

Multilevel Queue Scheduling Vs Multilevel Feedback Queue Scheduling

Multilevel Queue Scheduling and Multilevel Feedback Queue Scheduling are two variations of process scheduling algorithms used by operating systems.

Multilevel Queue Scheduling is a scheduling algorithm that divides processes into separate queues based on their properties, such as priority, memory requirements, or type of processing. Each queue has its own scheduling algorithm, which determines how processes are selected for execution. Processes are permanently assigned to a specific queue and cannot move between queues.

In contrast, Multilevel Feedback Queue Scheduling is a dynamic scheduling algorithm that allows processes to move between queues. Each queue has a different priority level, and processes can move between queues based on their behavior and resource requirements. Processes that use more resources, such as CPU time, are moved to higher-priority queues, while those that use fewer resources are moved to lower-priority queues.

The main difference between these two algorithms is that Multilevel Queue Scheduling is a static algorithm that assigns processes to a fixed set of queues based on their properties, while Multilevel Feedback Queue Scheduling is a dynamic algorithm that allows processes to move between queues based on their resource requirements and behavior.

What are the Advantages and Disadvantages of Multilevel Queue Scheduling?

Multilevel queue scheduling is a variant of CPU scheduling algorithm that uses multiple queues to manage processes with different priorities. Each queue has a different priority level, and processes are assigned to the appropriate queue based on their priority. Here are some advantages and disadvantages of multilevel queue scheduling, as follow them:

Advantages of Multilevel Queue Scheduling

The following are some advantages of using multilevel queue scheduling:

Also Read: Multiprogramming Operating System: Example, Types, and Advantage!!

Efficient Use of Resources: Multilevel queue scheduling allows for the efficient use of resources by ensuring that high-priority tasks are executed first. This results in better system performance and faster response times for critical applications.

Prioritization of Tasks: With multiple queues, tasks can be prioritized based on their importance, making it easier to manage different types of tasks. This can help ensure that time-critical tasks are completed before less important tasks.

Better Resource Allocation: Multilevel queue scheduling ensures that the CPU and other system resources are allocated fairly to different types of tasks. This means that system resources are not wasted on low-priority tasks, which can improve overall system efficiency.

Enhanced Responsiveness: By prioritizing high-priority tasks, multilevel queue scheduling can help improve system responsiveness. This can be especially important in real-time systems or systems that require quick response times.

Customizable: Multilevel queue scheduling can be customized to meet the specific needs of a particular system. For example, different priority levels can be assigned to different types of tasks, and the number of queues and their priority levels can be adjusted to suit the system’s requirements.

Disadvantages of Multilevel Queue Scheduling

While multilevel queue scheduling has several advantages, there are also some disadvantages that should be considered:

Complexity: Implementing a multilevel queue scheduling algorithm can be complex, particularly when there are many different queues with different priorities or characteristics. This complexity can make the scheduling algorithm difficult to maintain and optimize.

Overhead: Multilevel queue scheduling requires a significant amount of overhead in terms of memory and processing power. Each queue requires its own data structures and scheduling algorithms, which can increase the overall complexity of the system.

Inefficient Resource Utilization: Multilevel queue scheduling can lead to inefficient resource utilization if processes with low priority are starved of resources due to high-priority processes monopolizing the CPU. This can lead to low system performance and slow response times.

Lack of Flexibility: Multilevel queue scheduling may lack the flexibility needed to adapt to changes in the workload or system environment. For example, if a high-priority process suddenly becomes less important, it may still be given priority over other processes, even if it no longer needs it.

Inadequate Fairness: In some cases, multilevel queue scheduling may not provide fair allocation of resources among processes. For example, if a high-priority process is constantly added to the queue, it may prevent lower-priority processes from ever being scheduled, leading to poor overall performance.

Features of Multilevel Queue Scheduling

Here are some of the features & characteristics of multilevel queue scheduling:

Also Read: Multitasking Operating System? Example, Types, and Advantages!!

Multiple Queues: Multilevel queue scheduling involves multiple queues, with each queue being assigned a different priority level or criteria for sorting processes.

Predefined Priorities: The priorities of processes in each queue are predefined and may not change during runtime.

Independent Scheduling: Each queue is scheduled independently, and processes in one queue do not affect processes in another queue.

Fixed Allocation: Processes are assigned to a particular queue based on specific criteria, and once they are assigned, they stay in that queue until completion.

Flexible Scheduling: Each queue can use a different scheduling algorithm, such as first-come, first-served (FCFS), round-robin, or priority scheduling.

Priority Inversion: In multilevel queue scheduling, higher-priority processes may starve lower-priority processes, leading to priority inversion. To prevent this, priority aging is often used to increase the priority of lower-priority processes over time.

Multilevel Feedback Queue: A variant of multilevel queue scheduling is the multilevel feedback queue (MLFQ), which allows processes to move between queues based on their behaviour and resource needs.

Overall, multilevel queue scheduling is a useful algorithm for managing different types of processes with different resource requirements and priorities.

Multilevel Queue Scheduling Program in C

Here is an example of a multilevel queue scheduling program in C:

#include <stdio.h>

#include <stdlib.h>

#define MAX_PROCESSES 10

// Process struct

struct process {

    int pid; // process ID

    int burst_time; // process burst time

    int priority; // process priority

};

// Function to swap two processes

void swap(struct process *a, struct process *b) {

    struct process temp = *a;

    *a = *b;

    *b = temp;

}

// Function to sort processes based on priority

void sort_processes(struct process *p, int n) {

    for (int i = 0; i < n – 1; i++) {

        for (int j = 0; j < n – i – 1; j++) {

            if (p[j].priority < p[j + 1].priority) {

                swap(&p[j], &p[j + 1]);

            }

        }

    }

}

int main() {

    int n; // number of processes

    struct process processes[MAX_PROCESSES]; // array to store processes

    int q1_time = 10; // time quantum for first queue

    int q2_time = 20; // time quantum for second queue

    int q1_count = 0; // count of processes in first queue

    int q2_count = 0; // count of processes in second queue

    int q3_count = 0; // count of processes in third queue

    printf(“Enter the number of processes: “);

    scanf(“%d”, &n);

    // Input the processes

    for (int i = 0; i < n; i++) {

        printf(“Enter the burst time and priority for process %d: “, i + 1);

        scanf(“%d %d”, &processes[i].burst_time, &processes[i].priority);

        processes[i].pid = i + 1;

        // Assign the process to the appropriate queue

        if (processes[i].priority >= 0 && processes[i].priority <= 3) {

            q1_count++;

        }

        else if (processes[i].priority >= 4 && processes[i].priority <= 6) {

            q2_count++;

        }

        else {

            q3_count++;

        }

    }

    // Sort the processes based on priority

    sort_processes(processes, n);

    // Execute the processes in the queues

    int time = 0; // current time

    int q1_index = 0; // index of the process in the first queue

    int q2_index = q1_count; // index of the process in the second queue

    int q3_index = q1_count + q2_count; // index of the process in the third queue

    while (q1_index < q1_count || q2_index < q1_count + q2_count || q3_index < n) {

        // Execute the processes in the first queue

        for (int i = 0; i < q1_count; i++) {

            if (processes[q1_index].burst_time > 0) {

                printf(“Time %d: Process %d is executing in queue 1.\n”, time, processes[q1_index].pid);

                processes[q1_index].burst_time -= q1_time;

                time += q1_time;

                if (processes[q1_index].burst_time <= 0) {

                    printf(“Time %d: Process %d completed in queue 1.\n”, time, processes[q1_index].pid);

                    q1_index++;

                }

            }  

Multilevel Queue Scheduling Program in C++

Here, we will try to show example of multilevel queue scheduling program in C++:

#include <iostream>

#include <queue>

using namespace std;

struct Process {

    int id;

    int arrival_time;

    int burst_time;

    int priority;

};

int main() {

    int n;

    cout << “Enter the number of processes: “;

    cin >> n;

    queue<Process> q1, q2, q3;

    for (int i = 0; i < n; i++) {

        Process p;

        cout << “Enter the arrival time, burst time, and priority of process ” << i + 1 << “: “;

        cin >> p.arrival_time >> p.burst_time >> p.priority;

        p.id = i + 1;

        if (p.priority >= 1 && p.priority <= 3) {

            q1.push(p);

        } else if (p.priority >= 4 && p.priority <= 6) {

            q2.push(p);

        } else {

            q3.push(p);

        }

    }

    int time = 0;

    cout << “Gantt Chart:” << endl;

    while (!q1.empty() || !q2.empty() || !q3.empty()) {

        if (!q1.empty()) {

            Process p = q1.front();

            q1.pop();

            cout << “P” << p.id << “\t”;

            for (int i = 0; i < p.burst_time; i++) {

                time++;

                if (!q1.empty() && q1.front().arrival_time <= time) {

                    q1.push(p);

                    break;

                }

                if (!q2.empty() && q2.front().arrival_time <= time) {

                    q1.push(p);

                    break;

                }

                if (!q3.empty() && q3.front().arrival_time <= time) {

                    q1.push(p);

                    break;

                }

            }

        } else if (!q2.empty()) {

            Process p = q2.front();

            q2.pop();

            cout << “P” << p.id << “\t”;

            for (int i = 0; i < p.burst_time; i++) {

                time++;

                if (!q1.empty() && q1.front().arrival_time <= time) {

                    q1.push(p);

                    break;

                }

                if (!q2.empty() && q2.front().arrival_time <= time) {

                    q2.push(p);

                    break;

                }

                if (!q3.empty() && q3.front().arrival_time <= time) {

                    q2.push(p);

                    break;

                }

            }

        } else {

            Process p = q3.front();

            q3.pop();

            cout << “P” << p.id << “\t”;

            for (int i = 0; i < p.burst_time; i++) {

                time++;

                if (!q1.empty() && q1.front().arrival_time <= time) {

                    q1.push(p);

                    break;

                }

                if (!q2.empty() && q2.front().arrival_time <= time) {

                    q1.push(p);

                    break;

                }

                if (!q3.empty() && q3.front().arrival_time <= time) {

                    q1.push(p);

                    break;

                }

            }

        }

    }

    cout << endl;

    return 0;

}

This program reads in the number of processes and their arrival time, burst time, and priority. It then places each process into one of three queues based on its priority, with the first queue having the highest priority and the third queue having the lowest priority.

Multilevel Queue Scheduling Program in Java

Here, we will illustrate the example of Multilevel Queue Scheduling program in Java:

import java.util.*;

class Process {

    String name;

    int priority;

    int burstTime;

    public Process(String name, int priority, int burstTime) {

        this.name = name;

        this.priority = priority;

        this.burstTime = burstTime;

    }

}

public class MultilevelQueueScheduling {

    public static void main(String[] args) {

        // Create three queues

        Queue<Process> q1 = new LinkedList<>();

        Queue<Process> q2 = new LinkedList<>();

        Queue<Process> q3 = new LinkedList<>();

        // Add processes to the first queue

        q1.add(new Process(“P1”, 3, 5));

        q1.add(new Process(“P2”, 2, 4));

        q1.add(new Process(“P3”, 1, 2));

        // Schedule processes in the first queue

        while (!q1.isEmpty()) {

            Process p = q1.poll();

            System.out.println(“Running process ” + p.name + ” from Queue 1″);

            p.burstTime -= 2;

            // Move process to second queue if its priority is greater than 1

            if (p.priority > 1) {

                q2.add(p);

            }

            // Move process to third queue if it has remaining burst time

            if (p.burstTime > 0) {

                q1.add(p);

            }

        }

        // Schedule processes in the second queue

        while (!q2.isEmpty()) {

            Process p = q2.poll();

            System.out.println(“Running process ” + p.name + ” from Queue 2″);

            p.burstTime -= 2;

            // Move process to third queue if its priority is greater than 1

            if (p.priority > 1) {

                q3.add(p);

            }

            // Move process to first queue if it has remaining burst time

            if (p.burstTime > 0) {

                q2.add(p);

            }

        }

        // Schedule processes in the third queue

        while (!q3.isEmpty()) {

            Process p = q3.poll();

            System.out.println(“Running process ” + p.name + ” from Queue 3″);

            p.burstTime -= 2;

            // Move process to second queue if it has remaining burst time

            if (p.burstTime > 0) {

                q3.add(p);

            }

        }

    }

}

In this example, there are three queues, each with its own priority level. Processes are added to the first queue and scheduled first. If a process has a priority greater than 1, it is moved to the second queue. If a process has remaining burst time, it is moved back to the first queue.

Processes in the second queue are scheduled next. If a process has a priority greater than 1, it is moved to the third queue. If a process has remaining burst time, it is moved back to the second queue.

Finally, processes in the third queue are scheduled last. If a process has remaining burst time, it is moved back to the third queue.

This is just one example of a Multilevel Queue Scheduling program in Java. There are many different ways to implement this type of scheduling algorithm, and the specifics will depend on the requirements of your particular use case.

Wrapping Up

Now i hope that you have been completely educated about what is multilevel queue scheduling algorithm in OS; involving with many examples and programs in C, C++, and Java with their outputs. If this article is helpful for you, then please share it along with your friends, family members or relatives over social media platforms like as Facebook, Instagram, Linked In, Twitter, and more.

Also Read: Batch Processing Operating System: Examples, Advantage, & Disadvantage!!

If you have any experience, tips, tricks, or query regarding this issue? You can drop a comment!

Happy Learning!!

Leave a Reply

Your email address will not be published. Required fields are marked *