Multilevel feedback queue

from Wikipedia, the free encyclopedia

The term multilevel feedback queue describes a dynamic priority scheduling algorithm. With this method, there are several queues with different priorities. Processes are dynamically assigned to one of these queues depending on their previous resource consumption.

realization

Several FIFO queues are used. The processing takes place as follows:

  1. A new process is added at the end of the top FIFO queue.
  2. After a while, the process will reach the top of the queue and be assigned to the processor .
  3. Once the process has been completed, it leaves the system.
  4. If the process gives up the processor voluntarily, it leaves the queue. As soon as the process becomes ready again, it is put back in the same queue.
  5. If the process takes up the entire time slice, it is interrupted and placed at the end of the next lower queue.
  6. This process continues until the process is either completely processed or has reached the lowest queue.
  7. In the lowest queue, the processes rotate in a round robin manner until they are terminated and exit the system.

In the multilevel feedback queue procedure, a process only has one opportunity to be completely processed in a specific queue before it is pushed into a lower queue.

The scheduler always assigns the processor to the process at the beginning of the top non-empty queue.

Advantages and disadvantages

Short jobs are preferred because they are given higher priorities. Jobs with a large number of input and output operations are preferred, as they are returned to the original waiting list after the processor has voluntarily given up, i.e. they retain their priority. New processes are quickly classified and assigned to a priority class. No heuristics (e.g. to estimate the runtime of the process) are required for classification.

If there are always new processes, computationally intensive processes in the lowest priority class can "starve", ie they are never executed to the end. A priority inversion may occur.

Individual evidence

  1. ^ Abraham Silberschatz, Peter B. Galvin, Greg Gagne: Operating system concepts . 7th edition. John Wiley & Sons, Hoboken 2005, ISBN 0-471-69466-5 , pp. 168 (English).
  2. ↑ Markus Weinländer: Development of Parallel Operating Systems - Design and Implementation of Multithreading Concepts in C ++ , Vieweg + Teubner 1995, ISBN 3-322-83080-2 . from. P. 106