Introduction to Multi-Level Feedback Queue (MLFQ)

The Multi-Level Feedback Queue (MLFQ) is an advanced scheduling algorithm used in operating systems to manage processes. Its primary objective is to dynamically prioritize processes based on their behavior and execution history, ensuring efficient CPU utilization and improved overall system performance.

Key Features of MLFQ:

1. Multiple Queues:

   • MLFQ consists of several queues, each with a different priority level. Processes are placed into these queues based on their priority, which can change over time.

2. Dynamic Prioritization:

   • Processes can move between queues based on their behavior. For example, if a process uses too much CPU time, it might be moved to a lower-priority queue. Conversely, processes that wait for long periods may be moved to higher-priority queues.
   • 

3. Aging:

   • To prevent starvation (where low-priority processes never get CPU time), MLFQ implements aging. Aging gradually increases the priority of long-waiting processes, ensuring they eventually get executed.

4. Feedback Mechanism:

   • The "feedback" aspect of MLFQ allows the system to adjust the priority of processes based on their execution history. Interactive processes that require quick responses are prioritized over CPU-bound processes.

How MLFQ Works:

1. Initialization:

   • At the start, all processes are placed in the highest-priority queue.

2. Execution and Adjustment:

   • The scheduler selects a process from the highest-priority non-empty queue. If the process uses the CPU for too long, it is moved to a lower-priority queue. If it yields the CPU before its time quantum expires, it may remain in the same queue or be moved to a higher-priority queue.

3. Time Quanta:

   • Each queue can have different time quanta, with higher-priority queues typically having shorter time quanta to quickly serve interactive processes.

4. Preemption:

   • Higher-priority processes can preempt lower-priority ones, ensuring that critical tasks are executed promptly.

Benefits of MLFQ:

• Efficiency: MLFQ efficiently handles a mix of short and long processes, improving CPU utilization.
• Responsiveness: It ensures that interactive and I/O-bound processes receive quick responses.
• Fairness: Through aging and dynamic prioritization, MLFQ provides a fair distribution of CPU time among processes, preventing starvation.

Coding:

#ifndef MSTWOOS_QUEUE_H
#define MSTWOOS_QUEUE_H
#include "Process.h"
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define LEVELS 4
#define MAX_PROCESSES 3

// front and rear are indices
typedef struct {
    Process *queue[MAX_PROCESSES];
    int front;
    int rear;
    int capacity;
    int time_quantum;
} Queue;
int isQueueEmpty(Queue* queues) {
    return queues->rear == -1;
}
int isQueueFull(Queue* queues) {
    return queues->rear+1 == queues->capacity;
}

void enqueue(Queue *queue, Process * process) {
    if(isQueueFull(queue)){
        printf("Queue is Full\n");
        return;
    }
    queue->queue[++queue->rear] = process;
}
Process* dequeue(Queue *queue) {
    Process *process = queue->queue[0];
    for(int i = 0; i < queue->rear; i++){
        queue->queue[i] = queue->queue[i+1];
    }
    queue->rear--;
    return process;
}
void printQueue(Queue *queue){
    for(int i = 0;i <= queue->rear; i++)
        printf("%d ", queue->queue[i]->pcb->processID);
}


Queue queues[LEVELS];
const int quanta[] = {1, 2, 4, 8};

int isAllEmpty(){
    for(int i = 0; i<LEVELS; i++)
        if(!isQueueEmpty(&queues[i]))
            return 0;
    return 1;
}
void initQueue() {
    for (int i = 0; i < LEVELS; i++) {
        queues[i].front = 0;
        queues[i].rear = -1;
        queues[i].capacity = 3;
        queues[i].time_quantum = quanta[i];
    }
}
void printML(){
    printf("Multi level feedBack Queue:\n");
    for(int i = 0; i<LEVELS; i++){
        printf("Level %d: ", i+1);
        printQueue(&queues[i]);
        printf("\n");
    }
}

void enqueueML(int level, Process *process) {

    if (isQueueFull(&queues[level])){
        printf("Queue of level %d is full\n", level);
        return;
    }
    printf("enqueue process %d\n", process->pcb->processID);
    enqueue(&queues[level], process);
    printf("\n");
    printML();
    printf("\n");
}

Process* dequeueML(Memory *memory) {
    Process *process;
    for(int i = 0; i<LEVELS; i++){
        if(isQueueEmpty(&queues[i]))
            continue;
        process = dequeue(&queues[i]);
        printf("\n");
        printf("dequeue process %d\n", process->pcb->processID);
        printML();
        printf("\n");

        changeState(process->pcb, memory, "Running");
        int rem = process->pcb->memoryUpperBoundary - process->pcb->pc+1;
        process->remaining_time = rem < quanta[i]? rem : quanta[i];
        return process;
    }
    return NULL;
}


#endif //MSTWOOS_QUEUE_H

Conclusion

The Multi-Level Feedback Queue is a versatile and adaptive scheduling algorithm that enhances the performance and responsiveness of operating systems. By dynamically adjusting the priority of processes based on their behavior, MLFQ ensures efficient CPU utilization and fair process management.