What is Multi-level Feedback Queue Scheduling (MLFQ)?

May 3, 2018 Author: munishmishra04_3od47tgp
Print Friendly, PDF & Email

Effective and efficient scheduling is an important aspect of operating system. Scheduling is a process of deciding how to allocate resources between different possible tasks. Feedback scheduling is a kind of process scheduling mechanism where process doesn’t come with any priority. Process scheduling for real-time processes is a critical function of real-time operating systems, which are required to guarantee soft and hard deadlines for completing real-time processes. The behavior of Multi-Level Feedback Queue (MLFQ) scheduling mechanisms intrinsically support a scheduling that favors short CPU bursts to the complete exclusion of all other processes in the ready queues.



About Multi-level Feedback Queue Scheduling

In computer science, a multilevel feedback queue is a scheduling algorithm. This scheduling algorithm is intended to meet the following design requirements for multi-mode systems:

  • Give preference to short jobs.
  • Give preference to I/O bound processes.
  • Separate processes into categories based on their need for the processor.

The multilevel feedback queue scheduling algorithm, allows a process to move between queues. The idea is to separate processes according to the characteristics of their CPU bursts. If a process uses too much CPU time, it will be moved to a lower-priority queue. This scheme leaves I/O-bound and interactive processes in the higher-priority queues. In addition, 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.

Multilevel Feedback Queue Scheduling (MLFQ) keep analyzing the behavior (time of execution) of processes and according to which it changes its priority. Now, look at the diagram and explanation below to understand it properly.

In multilevel queue scheduling we assign a process to a queue and it remains in that queue until the process is allowed access to the CPU. That is, processes do not move between queues. This is a reasonable scheme as batch processes do not suddenly change to an interactive process and vice versa. However, there may be instances when it is advantageous to move process between queues. Multilevel feedback queue scheduling allows us to do this.




In general, a multilevel feedback queue scheduler is defined by the following parameters:

  • The number of queues
  • The scheduling algorithm for each queue
  • The method used to determine when to upgrade a process to a higher-priority queue
  • The method used to determine when to demote a process to a lower-priority queue
  • The method used to determine which queue a process will enter when that process needs service.

MLFQ Diagram

Figure: MLFQ Example

In the figure given above, we have a multilevel feedback queue scheduler with three queues, numbered from 0 to 2. The scheduler first executes all processes in queue 0. Only when queue 0 is empty will it execute processes in queue 1. Similarly, processes in queue 2 will only be executed if queues 0 and 1 are empty. A process that arrives for queue 1 will preempt a process in queue 2. A process in queue 1 will in turn be preempted by a process arriving for queue 0. A process entering the ready queue is put in queue 0. A process in queue 0 is given a time quantum of 8 milliseconds. If it does not finish within this time, it is moved to the tail of queue 1. If queue 0 is empty, the process at the head of queue 1 is given a quantum of 16 milliseconds. If it does not complete, it is preempted and is put into queue 2. Processes in queue 2 are run on an FCFS basis but are run only when queues 0 and 1 are empty.

The definition of a multilevel feedback queue scheduler makes it the most general CPU-scheduling algorithm. It can be configured to match a specific system under design. Unfortunately, it also requires some means of selecting values for all the parameters to define the best scheduler. Although a multilevel feedback queue is the most general scheme, it is also the most complex.

Advantages: A process that waits too long in a lower priority queue may be moved to a higher priority queue.

Disadvantage: Moving the process around queue produce more CPU overhead.



References

[1] Kenneth E. Hoganson, “Multi-core real-time scheduling in multilevel feedback queue with starvation mitigation (MLFQ-RT)”, Proceeding ACMSE ’18 Proceedings of the ACMSE 2018 Conference, Article No. 29, Richmond, Kentucky — March 29 – 31, 2018

[2] “Multilevel Feedback Queue”, available online at: https://tssurya.wordpress.com/tag/multilevel-feedback-queues/

[3] “Multi-Level Feedback Queue scheduling”, available online at: http://www.cs.nott.ac.uk/~pszgxk/courses/g53ops/Scheduling/sched09-mlfqs.html

[4] “Multilevel Feedback Queue Scheduling”, available online at: https://www.studytonight.com/operating-system/multilevel-feedback-queue-scheduling

One Comment

  • +905323495077 May 10, 2018 at 5:32 am

    I’m gone to convey my little brother, that he should
    also pay a visit this web site on regular basis
    to get updated from most up-to-date gossip.
    +905323495077

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert