A multilevel queue is suitable when the processes are classified in groups. The multilevel queue scheduling algorithm partition the queue into several separate queues.
Each of the processes are permanently assigned to one queue based on some property such as memory requirement, process priority, or process type.
Then each queue has its own scheduling algorithm. For example, processes could be divided into foreground queue (for interactive processes) and background queue (for batch processes).
The foreground queue has higher priority and background queue has lower priority. Hence, the scheduling scheme could be a preemptive one with fixed-priority. You can schedule a foreground queue by a round-robin algorithm and background queue with an FCFS algorithm.
Example of Multilevel Queue
Let us see another example of multilevel queue scheduling with five queues with different priorities:
- System proesses
- Interactive processes
- Interactive editing processes
- Batch processes
- User processes
Each upper-level queue has absolute priority over the lower-level queue. For example, if interactive editing process entered the ready queue, then currently running batch process will be preempted.
Another option is to time-slice the queues. Each queue gets a certain percent of the CPU time. If the priority is high it will be given more time and the lower queue will get less CPU time.
Multilevel Feedback Queue
There is another version of the multilevel queue called the multilevel feedback queue which allows a process to move between queues. If the process uses too much of CPU time, it is moved to a lower-priority queue. If the process starts aging (waits too much in a lower-priority queue) is moved to a higher-priority queue. This prevents the process from starvation.
The following properties define the multilevel feedback queue:
– The number of queues
– The scheduling algorithm for each queue
– The method for upgrading the process from lower-priority queue to higher-priority queue.
– The method for downgrading the process from higher-priority queue to lower-priority queue.
– The method to determine the queue in which process will enter.
Basically, the multilevel feedback queue seems very general CPU scheduling algorithm. However, it is quite complex to design and implement a multilevel feedback queue.
References
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne (July 29, 2008) Operating System Concepts, 8 edn., : Wiley.
- Tanenbaum, Andrew S. (March 3, 2001) Modern Operating Systems, 2nd edn., : Prentice Hall.
