Enough with the unga bunga puny algorithms.. did you know there exists an
scheduling algorithm that literally paved way for modern technology? and no it is not yet another FCFS where people just throw jobs in array order and call it a day without even bothering to sort...
What I am referring to is MLFQ (Multi Level Feedback Queue). Now a FCFS is fine.. it's like print("hello world") of OS scheduling but clearly we don't wanna "hello" the world forever.. there are in fact unhealthy amount of reasons why MLFQ is considered one of the greatest algorithms.. it outperforms every previous algorithm to exist..

• FCFS: just runs in arrival order
• SRTF: very dangerous as it is prone to starvation (gfg link to starvation article)
• RR: well... RR is just RR.. Equality is overrated in 2026 anyway, so we don't really care about it much.

These are all valid reasons but there's another massive reason that is common to all.. if you notice any algorithm before MLFQ demands a prerequisite number i.e. it's burst time... sure RR does not require it, but RR believes in equal quantum time... which honestly works but MLFQ is RR on steroids which is much better.

RR operates on a single queue. Job runs for certain quantum time then next one runs and so on until there's no active process left..

That clearly takes care of the scheduling but do you see why it is not so efficient? Imagine yourself in a supermarket, all you want are some
hot cheetos.. but grandma amy, Infront of you is buying half the store cuz she got 27 coupons. Now you gotta wait for 30 whole mins just to get your cheetos.. the point is, that is pretty inefficient. Not that it won't get the job done but why wait so long for something so insignificant? that is whole point of MLFQ..

In this blog/article/my rant from now we're gonna get into deep dive discussion on MLFQ including a working C code walk through.

Now comes the juicy part.. the actual C code on how to go about it..

IMPLEMENTATION

Stage 1: The Structure

Job Structure

struct Job {
int arrival_time;
int cpu_burst;
int start;
int end;
int turnaround;
int response;
int remaining_time;
bool inQueue;
int serial;
int alloted_time;
int alloted_left;
};

Node Structure

struct Node {
int data;
struct Node *next;
};

Stage 2: The Implementation

So, the structure we go ahead from now is list the rule and I show
how I implemented it in code

Rule 1: If a process has a higher priority (higher queue), it runs first. If the priorities are equal, the process runs in round-robin fashion.

if (head != NULL) {
currentNode = head;
activeHead = &head;
activeTail = &tail;
} else if (head2 != NULL) {
currentNode = head2;
activeHead = &head2;
activeTail = &tail2;
}

The above has some terms like activeHead and activeTail which you can ignore for now as they are a very special segment which i will discuss later but here what's important is the RULE that is applies... at present the rule says highest priority runs and lower one doesnt... here let say there are only 2 queues.. so we check if head which is the root of that queue(a linked list) is empty or not.. if it is then clearly no jobs are running on high priority so we go for second queue which is head2 in this case.. so now head2 is checked and jobs in there are ran.
But what about next part which is if same priority then jobs run in RR fashion? the next piece of code does exactly that.

(*activeHead) = currentNode->next;
currentNode->next = NULL;
(*activeTail)->next = currentNode;
(*activeTail) = currentNode;

Here activeHead indicates which head is active btw(wow! totally genius). all RR does is get the first job and attach it at the back after quantum time.. that way rotation happens and fairness is imposed.

Rule 2: If a process exhausts its allocated time slice in a higher priority queue, it is demoted to a lower priority queue.

else if (job->alloted_left <= 0) {

Now if a job has alot of processing to do it will clearly take alot of time just like grandma amy and we all hate waiting.. hence MLFQ _gracefully _handles the situation by introducing concept of alloted time as mentioned earlier.

First we check "did the job use all of it's alloted time?" if yes then it has to go to counter two which only works after counter 1(queue1) is empty hence maintaining priority.

if (currentNode == head) {
temp = head;
head = head->next;
temp->next = NULL;
if (tail2 == NULL)
head2 = tail2 = currentNode;
else {
tail2->next = temp;
tail2 = temp;
temp = NULL;
}
}

then for our code we must check whether 2nd queue is empty or it already got someone else waiting.. if it's empty we just do head2 = tail2 = currentNode; which says hey, since there's no job in this queue point the head and tail of this to currentNode which is well.. the current node. But if it is not empty then we make the poor guy to go back to waiting by appending to end which we can see with this piece of code

tail2->next = temp;
tail2 = temp;
temp = NULL;

finally after we shift lower priority queue we would again want it to get it's alloted time as punishing the job forever just because it takes alot of time isn't fair.. so we do something like job->alloted_left = job->alloted_time; which resets the alloted timer and the job again get back to action (in lower priority)

Rule 3: After a fixed reset interval, all processes are boosted back to the highest priority queue.

if (reset_timer == 0) {
clearQueue(&head, &tail, &head2, &tail2, reset);
enqueueReset(jobs, &head, &tail, len);
reset_timer = reset;
}

Reset timer is another feature which makes MLFQ OP.. it not only treats the poor(you with hot cheetos) fairly but also the wealthy(grandma amy.. technically). It introduces reset which is a timer when it resets the whole system. By reset i mean taking all the jobs back to higher priority so that all get equal chance again avoiding starvation again.

This shows a clear queue function which is an approach that i used for reset. basically this is divided in 3 parts.

if (*head2 == NULL) return;

if 2nd queue is empty.. well just return as no need to reset since whole point of reset is get all stuff from queue2 to queue1.

if (*head == NULL) {
*head = *head2;
*tail = *tail2;
}

If head itself is null then head2(head of 2nd queue) is only active.. so we just map the 1st queue to 2nd and that's.

else {
(*tail)->next = *head2;
*tail = *tail2;
}

Finally if head2 is not null and head is also not null then just make the tail(last node of 1st queue) point to head2(first node of queue2) and make the tail of Q1 same as Q2.. Viola.. Now we have a single Q1 which has all current jobs.

Now we also need to insert new jobs available as we cannot leave any job unattended hence following can be done.

What the code does here is parse the entire array containing jobs, check whether it is still in queue and has not ended yet which indicates job is not finished yet. if found we make a new node out of it.

if(!(*head)) {
*head = *tail = newNode;
} else {
(*tail)->next = newNode;
*tail = newNode;
}

Then we check if head empty? if yes then there no active jobs and this new one is the highest priority if not then we just append the new job at tail of **FIRST **Queue not 2nd because new jobs are always assigned highest priority.

Now the an interesting approach here is use of double pointers a double pointer is as name suggests pointer to a pointer.

struct Node **activeHead, **activeTail;

What this does is declare a variable that points to something that is pointing to something else.. like activeHead -> head -> Node

essentially is like a of a train. Hypothetically let say there are only 3 compartments in a train. The engine which drives everything is a actual Node. 2nd compartment is connected to engine and 3rd is connected to 2nd.. similarly head -> Node and activeHead -> head.

Now how does this help in this scenario?

MLFQ is not restricted to only 2 Queues but more than 2 which makes it even more efficient. This double pointer helps avoid a huge if else statement by using activeHead, we write the scheduling logic once. We point activeHead to whichever queue has jobs, and the code treats it the same way whether it’s Queue 1, Queue 2, or Queue 10. It’s polymorphism for C programmers.

If you see it can get pretty ugly real fast. For more Queue's the if else string gets extended further which makes the code complete trash and stinky.

Now it leads us back to the snippet shared in the very first rule. This way we set the activeHead and activeTail by checking whether head is empty or not.

Conclusion

And that pretty much wraps up my implementation of MLFQ. What initially looked like “just another scheduling algorithm” ended up being one of the most interesting systems I’ve implemented so far.
Anyways if you actually read till here, congratulations. You survived queues, starvation, double pointers and my terrible supermarket analogies.