In computer science, a multilevel feedback queue is a scheduling algorithm. Scheduling algorithms are designed to have some process running at all times to keep the central processing unit (CPU) busy. The multilevel feedback queue extends standard algorithms with the following design requirements: The multilevel feedback queue was first developed by Fernando J. Corbató (1962). For this accomplishment, the Association for Computing Machinery awarded Corbató the Turing Award.

Process scheduling

Whereas the multilevel queue algorithm keeps processes permanently assigned to their initial queue assignments, the multilevel feedback queue shifts processes between queues. The shift is dependent upon the CPU bursts of prior time-slices.

Algorithm

Multiple FIFO queues are used and the operation is as follows: For scheduling, the scheduler always starts picking up processes from the head of the highest-level queue. Only if the highest-level queue has become empty will the scheduler take up a process from the next lower-level queue. The same policy is implemented for picking up in the subsequent lower-level queues. Meanwhile, if a process comes into any of the higher-level queues, it will preempt a process in the lower-level queue. Also, a new process is always inserted at the tail of the top-level queue with the assumption that it will complete in a short amount of time. Long processes will automatically sink to lower-level queues based on their time consumption and interactivity level. In the multilevel feedback queue a process is given just one chance to complete at a given queue level before it is forced down to a lower-level queue.

Scheduling parameters

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