What is Multilevel feedback queue?

Answer 1

A multi-level feedback queue scheduling policy gives preference to short and I/O bound processes, it also rapidly establishes the nature of a process and schedules it accordingly. Multi-level feedback queues work on priorities. Processes are placed in separate queues based on their priority, this in turn is based on their CPU consumption and If a process uses too much of the CPU, it will be given a lower priority and therefore get less CPU time than fast and I/O bound processes. Any processes that do not complete in their allocated time slice / quantum are demoted to a queue of less priority, these lower priority queues generally have larger quantums / time slices. Each of the queues may use a different scheduling algorithm, this is done to make the overall scheduling method as efficient as possible. The features that may vary between different multi-level feedback queue scheduling methods are: - The number of queues - The scheduling algorithm assigned to each queue - The method used to promote/demote processes to different queues - The method that determines which queue a process enters --- Thomas Lee

Answer 2

So the general idea of a multi-level queue is as follows:

You have several queues, each has a level which corresponds to a level of priority, each level has its own scheduler, there is one main scheduler which handles the scheduler for each queue.

So you might have:

Queue 1: High Priority, Shortest Job First

Queue 2: Medium Priority, Round-Robin 10ms Quantum

Queue 3: Low Priority, Round Robin 100 ms Quantum

Then overall queue could be a priority queue so Q1 gets 50% of CPU time, Q2 gets 35% of the CPU time, Q3 gets the remaining 15%.

The problem with this is that once a job is put on a queue, it must remain there until it completes. This could create some problems with CPU hogging and starvation. If a very long job is put on Q1, it could hog all of the time given to Queue 1, preventing the other jobs from running. This is bad because jobs in Q1 are high priority.

Feedback queues attempt to solve this, what they do is have a few Round-Robin queues with increasingly larger Quantums, and then the final queue which handles all of the very long jobs.

So a feed back queue might look like:

Q1: 5 ms quantum

Q2: 10 ms quantum

Q3: First come first serve

Note: Quantum is used with Round-Robin scheduling, it is the amount of time a job runs before it is interrupted to start another job.

The important part is that all jobs start at Queue 1, and once their quantum elapses, they are moved to the next queue down. That way long jobs continue to move down as they continue to use quantums. Short jobs will often complete before they reach the last queue. Since shorter jobs rarely reach lower queues, they are given priority and allowed to complete.

The main distinction is that feedback allows jobs to move from one queue to another.