OS Scheduler

Multi-Level Feedback Queue (MFQ)

A MQF is scheduling algorithm with multiple priority levels managed using Round Robin queues, where a task is moved between priority levels based on how much processing time it has used.

Very important

Most commercial operating systems, including Windows, MacOS, and Linux, use this scheduling algorithm. (from the OS book)

Umm I googled this and it’s not true.

Feedback-Based Scheduling

From SE350: The way to do this is as follows. Scheduling is done on a preemptive (at time quantum) basis, and a dynamic priority mechanism is used. When a process first enters the system, it is placed in RQ0 (see Figure 9.4).

After its first preemption, when it returns to the Ready state, it is placed in RQ1. Each subsequent time that it is preempted, it is demoted to the next lower-priority queue. A short process will complete quickly, without migrating very far down the hierarchy of ready queues. A longer process will gradually drift downward. Thus, newer, shorter processes are favoured over older, longer processes. Within each queue, except the lowest-priority queue, a simple FCFS mechanism is used. Once in the lowest-priority queue, a process cannot go lower, but is returned to this queue repeatedly until it completes execution. Thus, this queue is treated in round-robin fashion.

Figure 9.10 illustrates the feedback scheduling mechanism by showing the path that a process will follow through the various queues. This approach is known as multilevel feedback, meaning the OS allocates the processor to a process and,when the process blocks or is preempted, feeds it back into one of several priority queues.