Multilevel Feedback-Queue Scheduling

• Normally, when the multilevel queue scheduling algorithm is used, processes are permanently assigned to a queue when they enter the system. If there are separate queues for foreground and background processes, processes do not move from one queue to the other, since processes do not change their foreground or background nature.
• This setup has the advantage of low scheduling overhead, but it is inflexible. The multilevel feedback-queue scheduling algorithm, in contrast, allows a process to move between queues.
• The idea is to separate processes according to the characteristics of their CPU bursts.
  • If a process uses too much CPU time, it will be moved to a lower-priority queue.
  • This scheme leaves I/O-bound and interactive processes in the higher-priority queues.
  • In addition, a process that waits too long in a lower-priority queue may be moved to a higher-priority queue.

  Figure 5.15: Multilevel feedback queues.

  
• This form of aging prevents starvation (see Fig. 5.15).
  • A process entering the ready queue is put in queue O. A process in queue 0 is given a time quantum of 8 milliseconds.
  • If it does not finish within this time, it is moved to the tail of queue 1.
  • If queue 0 is empty, the process at the head of queue 1 is given a quantum of 16 milliseconds.
  • If it does not complete, it is preempted and is put into queue 2.
  • Processes in queue 2 are run on an FCFS basis but are run only when queues 0 and 1 are empty.
• In general, a multilevel feedback-queue scheduler is defined by the following parameters:
  • The number of queues.
  • The scheduling algorithm for each queue.
  • The method used to determine when to upgrade a process to a higher-priority queue.
  • The method used to determine when to demote a process to a lower-priority queue.
  • The method used to determine which queue a process will enter when that process needs service.
• The definition of a multilevel feedback-queue scheduler makes it the most general CPU-scheduling algorithm. Unfortunately, it is also the most complex algorithm.