MLFQ (Multi Level Feedback Queue) is a CPU scheduling algorithm that is applied by operating system to assign the CPU time to process; and its basic principle is to separate processes based on their CPU requirements, memory requirements, and I/O operations. Therefore, here we will define about what is multilevel feedback queue scheduling algorithm with examples; involving with MLFQ scheduling program in C, C++, and Java with their outputs. This is ultimate article over the internet. At the end of this post, you will fully aware about Multilevel Feedback Queue Scheduling without any obstacle.

What is Multilevel Feedback Queue Scheduling in OS?

Multilevel Feedback Queue Scheduling is a scheduling algorithm used in Operating Systems to allocate system resources, such as CPU time, to multiple processes. It is a combination of multiple FIFO queues, where each queue has a different priority level assigned to it. The priority level is determined by the characteristics of the process, such as its age, CPU burst time, and I/O burst time.

The algorithm works by initially assigning each process to the highest priority queue. The processes in the highest priority queue are given the CPU time in a round-robin manner, which means that each process is given a fixed time slice to execute. If a process completes its execution during the allocated time slice, it is removed from the queue. If not, it is moved to the next lower priority queue.

As the process moves to a lower priority queue, the time slice allocated to it increases. The lower priority queue is assigned a longer time slice because it is assumed that the process requires more CPU time to complete its task. The process can be moved to an even lower priority queue if it is continuously using the CPU for a long time. This is done to prevent the process from monopolizing the CPU time and to allow other processes to execute.

When a process requires I/O operations, it is moved to a separate I/O queue. Once the I/O operation is completed, the process is placed in the highest priority queue to complete its execution. If a process does not require I/O operations, it will remain in the priority queue until it completes its execution.

The multilevel feedback queue scheduling algorithm is flexible and can be adjusted to fit the specific needs of the system. It can improve the overall performance of the system by allowing shorter processes to complete their execution quickly while also preventing longer processes from monopolizing the CPU time.

‘MLFQ 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:

What is Multilevel Feedback Queue Scheduling in OS?
Why to Need for Multilevel Feedback Queue Scheduling?
Multilevel Feedback Queue Scheduling Example with Gantt Chart
What is the Real Life Example of Multilevel Feedback Queue Scheduling?
MFQS Algorithm Implementation
What are the Advantages and Disadvantages of (MLFQ) Scheduling?

Advantages of Multilevel Feedback Queue Scheduling
Disadvantages of Multilevel Feedback Queue Scheduling

Characteristics of Multilevel Feedback Queue Scheduling
Features of Multilevel Feedback Queue Scheduling
Multilevel Feedback Queue Scheduling Program in C with Arrival Time
Multilevel Feedback Queue Scheduling Program in C++
Multilevel Feedback Queue Scheduling Program in Java

Let’s Get Started!!

Why to Need for Multilevel Feedback Queue Scheduling?

Multilevel feedback queue scheduling uses multiple queues with different priorities and allows processes to move between the queues based on their behavior and resource requirements.

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

There are several reasons why multilevel feedback queue scheduling is needed:

Prioritization: Multilevel feedback queue scheduling allows for the prioritization of different types of processes. Processes that require more resources or have higher priority can be placed in a higher-priority queue, while lower-priority processes can be placed in lower-priority queues.

Response Time: Multilevel feedback queue scheduling can improve the response time of interactive processes. By giving higher priority to interactive processes, the system can respond quickly to user input and provide a better user experience.

Fairness: Multilevel feedback queue scheduling can ensure fairness in resource allocation. By allowing processes to move between queues, the system can prevent processes from monopolizing resources and ensure that all processes have a fair chance of accessing the CPU.

Resource Utilization: Multilevel feedback queue scheduling can improve resource utilization. By using multiple queues with different priorities, the system can efficiently allocate resources to processes based on their requirements and ensure that resources are not wasted.

Multilevel Feedback Queue Scheduling Example with Gantt Chart

Here, we will show you an example of Multilevel Feedback Queue Scheduling with a Gantt chart:

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

Suppose we have three queues: Q1, Q2, and Q3, with Q1 being the highest priority queue and Q3 being the lowest priority queue. Each queue has a time quantum of 4, 8, and 16 respectively.

Let’s consider the following processes with their arrival times, burst times, and priorities:

Process Arrival Time Burst Time Priority

P1 0 20 1

P2 2 15 2

P3 4 10 3

P4 6 5 2

P5 8 30 1

The Multilevel Feedback Queue Scheduling algorithm works as follows:

Initially, all processes are placed in the highest priority queue (Q1).

Each process is given a time quantum of 4 in Q1. If it doesn’t finish its execution within this quantum, it is moved to the next lower priority queue (Q2).

If a process completes its execution in Q1, it is removed from the system.

Each process in Q2 is given a time quantum of 8. If it doesn’t finish its execution within this quantum, it is moved to the next lower priority queue (Q3).

If a process completes its execution in Q2, it is removed from the system.

Processes in Q3 are executed in a First-Come-First-Serve (FCFS) manner until completion.

Here’s the Gantt chart for the above example:

Process P1 P2 P3 P4 P5 P1 P5

Queue Q1 Q1 Q1 Q2 Q1 Q3

Time 0-4 4-8 8-12 12-16 16-20 20-25 25-30

In the Gantt chart, each row represents a process, and each column represents a unit of time. The different colors represent the different queues. The time intervals during which a process is executing are shown in the corresponding color.

As we can see, P1 arrives at time 0 and gets executed in Q1 until time quantum 4. Then, P2 arrives and takes over the CPU until time quantum 8. After that, P1 continues to execute in Q1 until it finishes at time 20.

P3 arrives at time 4 but gets pre-empted by P2 until it finishes at time quantum 12. Then, P4 arrives and takes over the CPU until time quantum 16. However, since it doesn’t complete its execution in Q2, it gets demoted to Q3. Finally, P5 arrives at time 8 and gets executed in Q1 until time quantum 16. Then, it gets pre-empted by P4 until it finishes its execution in Q3 at time 30.

We hope this example helps you understand Multilevel Feedback Queue Scheduling better!

What is the Real Life Example of Multilevel Feedback Queue Scheduling?

A real-life example of multilevel feedback queue scheduling can be seen in a computer system that is running multiple applications simultaneously. Each application can be assigned to a particular queue based on its priority or resource requirements.

For instance, consider a server that is running three types of applications: email, web server, and database server. The email application is assigned to the highest priority queue as it requires immediate attention and should be processed before other applications. The web server is assigned to a medium priority queue as it requires less immediate attention than email, but still needs to be processed quickly. The database server is assigned to the lowest priority queue as it can afford to wait for longer periods before execution.

If the system receives a large number of email requests, the email queue will be given a higher priority, and more CPU time will be allocated to this queue to ensure that emails are processed quickly. Similarly, if the web server receives a high number of requests, the web server queue will be given a higher priority, and more CPU time will be allocated to this queue.

MFQS Algorithm Implementation

The MFQS (Multi-Level Feedback Queue Scheduling) algorithm is a process scheduling algorithm that uses multiple queues to prioritize processes. Here is a high-level workflow for implementing the MFQS algorithm:

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

Initialize the Queues: The MFQS algorithm uses multiple queues, each with its own priority level. The number of queues and the time quantum for each queue should be set based on system requirements.

Add Processes to the Appropriate Queue: When a new process arrives, it is added to the first queue. If the process exceeds its time quantum in the first queue, it is moved to the second queue. This process is repeated until the process is completed or it reaches the last queue.

Execute Processes in Each Queue: Processes in the highest priority queue are executed first, followed by processes in the lower priority queues. Each process is executed for its allocated time quantum. If the process completes its execution before the time quantum, it is removed from the queue. If the process does not complete its execution within the time quantum, it is moved to the next lower priority queue.

Adjust the Priorities: The priorities of the queues can be adjusted dynamically based on system conditions. For example, if the system is overloaded, the priority of the lower priority queues can be decreased to allocate more resources to the higher priority queues.

Repeat Steps 2-4: The above steps are repeated until all processes have completed their execution.

Terminate the Process: Once a process has completed its execution, it is removed from the queue and terminated.

Perform Housekeeping: At the end of each time quantum, the system performs housekeeping tasks such as updating the queue priorities and moving processes between queues as necessary.

What are the Advantages and Disadvantages of (MLFQ) Scheduling?

Multi-Level Feedback Queue scheduling is an essential type of CPU scheduling algorithm used in operating systems. Here are some advantages and disadvantages of MLFQ:

Advantages of Multilevel Feedback Queue Scheduling

Multilevel Feedback Queue (MLFQ) scheduling has several advantages over other scheduling algorithms. Some of the key advantages of MLFQ scheduling include:

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

Flexible Priority: MLFQ scheduling allows for flexible priority assignment to different processes. The priority of a process can change dynamically depending on its behavior and resource requirements.

Efficient Resource Utilization: MLFQ scheduling maximizes resource utilization by allowing processes with shorter burst times to execute first. This helps in reducing the average waiting time and turnaround time of processes.

Avoidance of Starvation: MLFQ scheduling avoids starvation of processes with lower priority. The algorithm ensures that every process gets a fair share of CPU time, regardless of its priority.

Effective Handling of Interactive and Batch Processes: MLFQ scheduling is an efficient algorithm for handling both interactive and batch processes. It allows interactive processes to have higher priority, ensuring a better user experience, while also ensuring that batch processes complete in a timely manner.

Implementation Simplicity: MLFQ scheduling is relatively simple to implement, requiring only a few priority queues and a set of rules for moving processes between them.

Overall, MLFQ scheduling strikes a good balance between priority-based and time-based scheduling, making it a popular choice in modern operating systems.

Disadvantages of Multilevel Feedback Queue Scheduling

Multilevel Feedback Queue (MLFQ) scheduling is a popular scheduling algorithm used in modern operating systems. Although it has several advantages, it also has some disadvantages, including:

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

Complexity: MLFQ scheduling is a complex algorithm that requires significant computational resources to implement and manage. The complexity increases with the number of processes and the number of levels in the queue.

Starvation: In an MLFQ system, a process that requires more resources may get starved if it is continually moved to lower priority queues. This problem can be addressed by implementing aging, but it also adds to the complexity of the algorithm.

Priority Inversion: MLFQ scheduling can lead to priority inversion, where a high-priority process may get blocked by a low-priority process holding a shared resource. This problem can be addressed by using priority inheritance or priority ceiling protocols, but they add to the complexity of the system.

Inefficient Resource Utilization: In an MLFQ system, the allocation of resources may not be optimized, resulting in inefficient utilization of system resources. This problem can be addressed by using a dynamic feedback mechanism, but it adds to the complexity of the algorithm.

Poor Response Time: MLFQ scheduling may result in poor response times for interactive processes that require immediate attention. This problem can be addressed by using a separate queue for interactive processes, but it adds to the complexity of the algorithm.

Characteristics of Multilevel Feedback Queue Scheduling

Here, we will discuss about some characteristics of this algorithm include:

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

Multiple Priority Queues: The algorithm uses multiple priority queues to organize processes with varying levels of priority. Each queue has a different priority level, and processes move between them based on their behavior.

Dynamic Priority Adjustment: The algorithm adjusts the priority of processes dynamically based on their CPU usage and resource requirements. For example, a process that uses the CPU heavily will be moved to a lower-priority queue to give other processes a chance to run.

Aging: The algorithm uses aging to prevent starvation. As a process waits in a queue, its priority level gradually increases to ensure that it eventually gets CPU time.

Pre-Emption: The algorithm allows for pre-emption, which means that a process can be interrupted and moved to a different queue if a higher-priority process becomes available.

Feedback Mechanism: The algorithm uses a feedback mechanism to ensure that long-running processes eventually get CPU time. For example, a process that has been waiting in a lower-priority queue for a long time may be moved to a higher-priority queue to give it a chance to run.

Overall, multilevel feedback queue scheduling is a flexible algorithm that can adapt to changing conditions and ensure that all processes eventually get a fair share of CPU time.

Features of Multilevel Feedback Queue Scheduling

Multilevel Feedback Queue scheduling is designed to provide efficient scheduling for systems with different types of processes that have varying scheduling requirements. The key features of MFQ scheduling are:

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

Multiple Queues: MFQ scheduling uses multiple queues to classify processes based on their scheduling requirements. Each queue is assigned a different priority level, with the highest priority assigned to the most important processes.

Priority Adjustment: The priority of a process changes as it waits in a queue. For example, a process that has waited for a long time may be given a higher priority to ensure that it is executed quickly.

Aging: To prevent starvation, the priority of a process is gradually increased over time. This ensures that a long-waiting process eventually gets a chance to execute.

Feedback: The MFQ scheduling algorithm is designed to provide feedback to the system about the performance of its processes. This feedback is used to adjust the scheduling parameters in real-time, ensuring that the system is always optimized for performance.

Round-Robin Scheduling: Each queue in the MFQ scheduling algorithm uses round-robin scheduling to ensure that all processes in the queue are executed fairly.

Pre-emption: MFQ scheduling allows for pre-emption, which means that a process can be interrupted and another process can be scheduled to run if it has a higher priority.

Multilevel Feedback Queue Scheduling Program in C with Arrival Time

Here’s an example of a multilevel feedback queue scheduling program in C:

#include <stdio.h>

#define MAX_PROCESSES 10

#define MAX_PRIORITY 3

#define TIME_QUANTUM 4

int num_processes;

int current_time;

int current_process;

int remaining_time[MAX_PROCESSES];

int priority[MAX_PROCESSES];

int response_time[MAX_PROCESSES];

int waiting_time[MAX_PROCESSES];

struct Process {

int id;

int arrival_time;

int burst_time;

};

struct Queue {

int front, rear;

struct Process processes[MAX_PROCESSES];

} queues[MAX_PRIORITY];

void enqueue(struct Process process, int queue_number) {

queues[queue_number].processes[queues[queue_number].rear] = process;

queues[queue_number].rear++;

}

struct Process dequeue(int queue_number) {

struct Process process = queues[queue_number].processes[queues[queue_number].front];

queues[queue_number].front++;

return process;

}

int is_queue_empty(int queue_number) {

return queues[queue_number].front == queues[queue_number].rear;

}

void execute_process() {

if (remaining_time[current_process] > TIME_QUANTUM) {

remaining_time[current_process] -= TIME_QUANTUM;

current_time += TIME_QUANTUM;

enqueue((struct Process) { current_process, current_time, remaining_time[current_process] }, priority[current_process]);

} else {

current_time += remaining_time[current_process];

remaining_time[current_process] = 0;

response_time[current_process] = current_time – priority[current_process];

waiting_time[current_process] = response_time[current_process] – queues[priority[current_process]].processes[current_process].burst_time;

}

void execute_processes_in_queue(int queue_number) {

while (!is_queue_empty(queue_number)) {

current_process = dequeue(queue_number).id;

execute_process();

}

void execute_all_processes() {

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

execute_processes_in_queue(i);

}

void calculate_waiting_time() {

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

waiting_time[i] -= queues[priority[i]].processes[i].arrival_time;

}

void calculate_average_waiting_time() {

float sum_waiting_time = 0;

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

sum_waiting_time += waiting_time[i];

}

float average_waiting_time = sum_waiting_time / num_processes;

printf(“Average waiting time = %.2f\n”, average_waiting_time);

}

void print_gantt_chart() {

printf(“Gantt chart:\n”);

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

printf(“Queue %d: “, i);

for (int j = 0; j < queues[i].rear; j++) {

printf(“P%d “, queues[i].processes[j].id);

}

printf(“\n”);

}

int main() {

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

scanf(“%d”, &num_processes);

printf(“Enter the arrival time and burst time of each process:\n”);

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

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

remaining_time[i] = queues[0].processes[i].burst_time;

priority[i] = 0;

queues[0].rear++;

}

Multilevel Feedback Queue Scheduling Program in C++

Here’s an example implementation of Multilevel Feedback Queue (MFQ) scheduling program in C++.

#include<iostream>

#include<vector>

#include<queue>

using namespace std;

const int MAX_PROCESSES = 100;

// process structure to hold process information

struct Process {

int pid;

int arrival_time;

int burst_time;

int remaining_time;

int priority; // lower number means higher priority

int wait_time;

int turnaround_time;

int response_time;

int queue_level;

};

// function to sort the processes by their arrival time

bool sortByArrivalTime(Process a, Process b) {

return a.arrival_time < b.arrival_time;

}

// function to sort the processes by their priority and arrival time

bool sortByPriority(Process a, Process b) {

if(a.priority == b.priority) {

return a.arrival_time < b.arrival_time;

}

return a.priority < b.priority;

}

// function to simulate the MFQ scheduling algorithm

void simulateMFQ(vector<Process>& processes, int num_queues, int time_quantum[], int aging_time[]) {

// initialize the queues

queue<Process> queues[num_queues];

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

queue<Process> q;

queues[i] = q;

}

// add all processes to the first queue

for(int i=0; i<processes.size(); i++) {

processes[i].queue_level = 0;

queues[0].push(processes[i]);

}

int current_time = 0;

int total_wait_time = 0;

int total_turnaround_time = 0;

int total_response_time = 0;

int completed_processes = 0;

while(completed_processes < processes.size()) {

bool found_process = false;

// check each queue for a process to execute

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

if(!queues[i].empty()) {

found_process = true;

// get the next process in the queue

Process current_process = queues[i].front();

queues[i].pop();

// calculate the response time for the process

if(current_process.remaining_time == current_process.burst_time) {

current_process.response_time = current_time – current_process.arrival_time;

total_response_time += current_process.response_time;

}

// execute the process for the time quantum or until completion

int execution_time = min(time_quantum[i], current_process.remaining_time);

current_time += execution_time;

current_process.remaining_time -= execution_time;

// add processes that have not completed back to the queue with priority change

if(current_process.remaining_time > 0) {

if(i < num_queues-1 && current_process.wait_time >= aging_time[i]) {

current_process.priority++;

current_process.wait_time = 0;

current_process.queue_level++;

}

queues[current_process.queue_level].push(current_process);

} else {

// calculate the wait time and turnaround time for the process

current_process.wait_time = current_time – current_process.arrival_time – current_process.burst_time;

current_process.turnaround_time = current_time – current_process.arrival_time;

total_wait_time += current_process.wait_time;

total_turnaround_time += current_process.turnaround_time;

completed_processes++;

}

break;

}

// if no process was found, increment the time

if(!found_process) {

current_time++;

}

Multilevel Feedback Queue Scheduling Program in Java

Here’s an example implementation of a multilevel feedback queue scheduling program in Java:

import java.util.*;

class Process {

int pid; // process ID

int burstTime; // burst time of the process

int priority; // priority of the process

int waitingTime; // waiting time of the process

int turnaroundTime; // turnaround time of the process

int completedTime; // time when the process completes

public Process(int pid, int burstTime, int priority) {

this.pid = pid;

this.burstTime = burstTime;

this.priority = priority;

this.waitingTime = 0;

this.turnaroundTime = 0;

this.completedTime = 0;

}

public int getPid() {

return pid;

}

public int getBurstTime() {

return burstTime;

}

public int getPriority() {

return priority;

}

public int getWaitingTime() {

return waitingTime;

}

public int getTurnaroundTime() {

return turnaroundTime;

}

public int getCompletedTime() {

return completedTime;

}

public void setCompletedTime(int completedTime) {

this.completedTime = completedTime;

}

public void setTurnaroundTime(int turnaroundTime) {

this.turnaroundTime = turnaroundTime;

}

public void setWaitingTime(int waitingTime) {

this.waitingTime = waitingTime;

}

public class MultilevelFeedbackQueueScheduling {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

System.out.print(“Enter the number of processes: “);

int n = sc.nextInt();

// create an array of processes

Process[] processes = new Process[n];

// get input for each process

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

System.out.print(“Enter burst time and priority for process ” + (i + 1) + “: “);

int burstTime = sc.nextInt();

int priority = sc.nextInt();

processes[i] = new Process(i + 1, burstTime, priority);

}

// sort the processes by priority (highest priority first)

Arrays.sort(processes, new Comparator<Process>() {

@Override

public int compare(Process p1, Process p2) {

return Integer.compare(p2.getPriority(), p1.getPriority());

}

});

// create three queues for the three levels

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

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

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

// add all the processes to the first queue

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

q1.add(processes[i]);

}

int time = 0; // current time

// run the simulation until all processes are completed

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

// process the first queue

while (!q1.isEmpty()) {

Process p = q1.poll();

int burstTime = p.getBurstTime();

int remainingTime = burstTime;

int completionTime = time + burstTime;

p.setCompletedTime(completionTime);

p.setTurnaroundTime(completionTime);

p.setWaitingTime(completionTime – burstTime);

time = completionTime;

// move to the second queue if the process is not completed

if (remainingTime > 0) {

p.burstTime = remainingTime;

q2.add(p);

}

Wrapping Up

Through this article, you have been fully educated about what is multilevel feedback queue scheduling algorithm with examples; involving with MLFQ Scheduling program in C, C++, and Java with their outputs. If this content is valuable 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.