Multi-level Feedback Queue Scheduling (MFQ) – CPU Scheduling

Multi-level Feedback Queue Scheduling – CPU Scheduling

• Multi-level feedback queue scheduling is an enhancement of multi level queue scheduling. In this scheme, processes can move between the different queues.
• The various processes are separated in different queues on the basis of their CPU burst characteristics.
• If a process consumes a lot of CPU time, it is placed into a lower priority queue. Thus I/0 bound and interactive processes are placed in the higher priority queue and CPU bound processes are in lower priority queue.
• If a process waits too long in a lower priority queue it is moved higher priority queue Such an aging prevents starvation.
• The top priority queue is given smallest CPU time quantum.
• If the quantum expires before the process voluntarily relinquishes the CPU, the process is placed at the back of the next lower queue.
• In many multi-level feedback schemes, the quantum given to the process an it moves to each lower level queue becomes larger.

• The CPU time quantum given to the various queues usually change by the factor of 2 with each decreasing step in the priority of queue. For example, as shown in figure, process in first queue is given a time quantum of 8 milliseconds, If it does not finishes within this time, it is moved to the tail of next queue. In this queue each process is given quantum of 16 milliseconds.
• Again if it does not complete, it is ultimately put to the last priority queue. This has a large time quantum. The processes in this queue runs on an FCFS basis in contra to the round robin scheduling on the other queues. The various processes will run in this FCFS queue only if the previous queues are empty.
• Whenever any new process arrives in top priority queue, the running process in FCPS queue is preempted as it has lower priority.
• Any process that spends an amount of elapsed time exceeding the aging interval will promoted to the next higher priority queue.
• There are numbers of parameters on variables that defines multi-level feedback queue scheduling. These parameters makes system both flexible and complex. Thee parameters are:

1. The number of queues.
2. The scheduling algorithm for each queue.
3. The time slice associated with each queue.
4. The condition(s) that will cause a process to move downward into a lower priority queue.
5. The condition(s) that will cause and process to move upward into the higher priority queue.
6. The mechanism for determining which queue a new process should enter into.
7. Whether arrival of a process into a high level queue will preempt a process from a lower level queue.

Advantages of multi-level feedback queue scheduling

1. It is more flexible.
2. It allows the processes to move between different queues.
3. A process that waits too long in a lower priority queue may be moved to a higher priority queue. This form of aging prevents starvation.
4. The definition of a multi-level feedback queue scheduling makes it more general CPU scheduling algorithm. It can be configured to match a specific system under design.

Disadvantages of multi-level feedback queue scheduling

1. It requires some means of selecting values for all the parameters to define the be scheduler.
2. Moving the processes around the queues produces more CPU overheads.
3. It is the most complex scheduling algorithm.