Multilevel feedback queue


Multilevel feedback queue

In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems:

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

Multiple FIFO queues are used and the operation is as follows:

  1. A new process is positioned at the end of the top-level FIFO queue.
  2. At some stage the process reaches the head of the queue and is assigned the CPU.
  3. If the process is completed it leaves the system.
  4. 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.
  5. If the process uses all the quantum time, it is pre-empted and positioned at the end of the next lower level queue.
  6. 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., and R. R. Muntz, "Processor Sharing Queueing Models of Mixed Scheduling Disciplines for Time Shared System," Journal of the ACM (JACM), Volume 19, Issue 3 (July 1972).



Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Multilevel Feedback Queue — Der Begriff Multilevel Feedback Queue bezeichnet einen dynamischen Prioritätsscheduling Algorithmus. Bei diesem Verfahren werden Prozesse nach ihrem bisherigen Ressourcenverbrauch dynamisch in mehrere Warteschlangen (engl. queue)… …   Deutsch Wikipedia

  • Multilevel queue — Multi level queueing, used at least since the late 1950s/early 1960s, is a queue with a predefined number of levels. Unlike the multilevel feedback queue, items gets assigned to a particular level at insert (using some predefined algorithm), and… …   Wikipedia

  • Scheduling (computing) — This article is about processes assignment in operating systems. For other uses, see Scheduling (disambiguation). Scheduling is a key concept in computer multitasking, multiprocessing operating system and real time operating system designs.… …   Wikipedia

  • Prozessverwaltung — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Schedule (Informatik) — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Scheduler (Informatik) — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Scheduling (Informatik) — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Shortest-Remaining-Time — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Prozess-Scheduler — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, die die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Prioritäts-Scheduling — Das Prioritätsscheduling (auch PS – priority scheduling) ist ein in Betriebssystemen häufig verwendetes Scheduling Verfahren. Das Prinzip ist einfach: Jedem Prozess wird eine Priorität zugewiesen und nur der lauffähige Prozess mit höchster… …   Deutsch Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.