In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:
- Give preference to short jobs.
- Give preference to I/O bound processes.
- Separate processes into categories based on their need for the processor
Multiple FIFO queues are used and the operation is as follows:
- A new process is positioned at the end of the top-level FIFO queue.
- At some stage the process reaches the head of the queue and is assigned the CPU.
- If the process is completed it leaves the system.
- If the process voluntarily relinquishes control it leaves the queuing network, and when the process becomes ready again it enters the system on the same queue level.
- If the process uses all the quantum time, it is pre-empted and positioned at the end of the next lower level queue.
- This will continue until the process completes or it reaches the base level queue.
- At the base level queue the processes circulate in round robin fashion until they complete and leave the system.
- Optionally, if a process blocks for I/O, it is 'promoted' one level, and placed at the end of the next-higher queue. This allows I/O bound processes to be favored by the scheduler and allows processes to 'escape' the base level queue.
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.
See also
References
- Kleinrock, L.; Muntz, R. R. (July 1972). "Processor Sharing Queueing Models of Mixed Scheduling Disciplines for Time Shared System". Journal of the ACM 19 (3): 464–482. doi:10.1145/321707.321717.
