Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Multilevel feedback queue
open-in-new
<h2 id="process-scheduling">Process scheduling</h2> <p>Whereas the <a href="/facts/Multilevel_queue/GbVSpR9V">multilevel queue</a> algorithm keeps processes permanently assigned to their initial queue assignments, the multilevel feedback queue shifts processes between queues.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> The shift is dependent upon the CPU bursts of prior <a href="/facts/Preemption_(computing)/wjgIbWel">time-slices</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p> <ul><li>If a process uses too much CPU time, it will be moved to a lower-priority queue.</li> <li>If a process is I/O-bound or an interactive process, it will be moved to a higher-priority queue.</li> <li>If a process is waiting too long in a low-priority queue and <a href="/facts/Starvation_(computer_science)/E9UjtIWS">starving</a>, it will be <a href="/facts/Aging_(scheduling)/PpQAfcon">aged</a> to a higher-priority queue.</li></ul> <h3>Algorithm</h3> <p>Multiple <a href="/facts/FIFO_(computing_and_electronics)/RctvBNgE">FIFO</a> queues are used and the operation is as follows: </p> <ol><li>A new process is inserted at the end (tail) of the top-level <a href="/facts/FIFO_(computing_and_electronics)/RctvBNgE">FIFO</a> queue.</li> <li>At some stage the process reaches the head of the queue and is assigned the <a href="/facts/Central_processing_unit/Jxp1bqMV">CPU</a>.</li> <li>If the process is completed within the time slice of the given queue, it leaves the system.</li> <li>If the process voluntarily relinquishes control of the CPU, it leaves the queuing network, and when the process becomes ready again it is inserted at the tail of the same queue which it relinquished earlier.</li> <li>If the process uses all the quantum time, it is <a href="/facts/Preemption_(computing)/wjgIbWel">pre-empted</a> and inserted at the end of the next lower-level queue. This next lower-level queue will have a time quantum that is more than that of the previous higher-level queue.</li> <li>This scheme will continue until the process completes or it reaches the base-level queue.</li></ol> <ul><li>At the base level queue the processes circulate in <a href="/facts/Round-robin_scheduling/7wpjbMRI">round robin</a> fashion until they complete and leave the system. Processes in the base level queue can also be scheduled on a <a href="/facts/First-come%2c_first-served/8NDl56EM">first come first served</a> basis.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a></li> <li>Optionally, if a process blocks for I/O, it is <i>promoted</i> 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 <i>escape</i> the base-level queue.</li></ul> <p>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. </p><p>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. </p> <h3>Scheduling parameters</h3> <p>In general, a multilevel feedback queue scheduler is defined by the following parameters:<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <ul><li>The number of queues.</li> <li>The scheduling algorithm for each queue which can be different from FIFO.</li> <li>The method used to determine when to promote a process to a higher priority queue.</li> <li>The method used to determine when to demote a process to a lower-priority queue.</li> <li>The method used to determine which queue a process will enter when that process needs service.</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="https://pages.cs.wisc.edu/~remzi/solaris-notes.pdf">Multilevel Feedback Queue Schedulers — Solaris 2.6 Time-Sharing</a></li> <li><a href="https://www.lk.cs.ucla.edu/data/files/Kleinrock/Processor%20Sharing%20Queueing%20Models%20of%20Mixed.pdf">Processor Sharing Queueing Models of Mixed Scheduling Disciplines for Time Shared System</a></li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Lottery_scheduling/BuM59yCt">Lottery scheduling</a></li> <li><a href="/facts/Fair-share_scheduling/8jqDbFL3">Fair-share scheduling</a></li> <li><a href="/facts/Round-robin_scheduling/7wpjbMRI">Round-robin scheduling</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Silberschatz, Abraham (1994). Operating System Concepts, Fourth Edition. Addison-Wesley. p. 131. ISBN 978-0-201-50480-4. <a href="978-0-201-50480-4" target="_blank">978-0-201-50480-4</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Corbató, Fernando J.; Merwin-Daggett, Marjorie; Daley, Robert C. (1962). "An experimental time-sharing system". Proceedings of the May 1-3, 1962, spring joint computer conference on - AIEE-IRE '62 (Spring). p. 335. doi:10.1145/1460833.1460871. S2CID 14363753. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014). "Multi-level Feedback Queue". Operating Systems: Three Easy Pieces (PDF). Arpaci-Dusseau Books. <a href="https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf" target="_blank">https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Silberschatz, Abraham (1994). Operating System Concepts, Fourth Edition. Addison-Wesley. p. 147. ISBN 978-0-201-50480-4. <a href="978-0-201-50480-4" target="_blank">978-0-201-50480-4</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Silberschatz, Abraham (1994). Operating System Concepts, Fourth Edition. Addison-Wesley. p. 148. ISBN 978-0-201-50480-4. <a href="978-0-201-50480-4" target="_blank">978-0-201-50480-4</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008). Operating system concepts (8th ed.). Hoboken, N.J.: Wiley. p. 198. ISBN 978-0470128725. <a href="978-0470128725" target="_blank">978-0470128725</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008). Operating system concepts (8th ed.). Hoboken, N.J.: Wiley. p. 198. ISBN 978-0470128725. <a href="978-0470128725" target="_blank">978-0470128725</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> </ol>