Multilevel Queue Scheduling

• If processes are easily classified into groups with similar resource use characteristics, then the application of multilevel queue scheduling becomes feasible.
• In this system, multiple ready-to-run queues operate with each one given its own scheduler algorithm and assigned to processes with certain characteristics.
• Example: one ready-to-run queue might contain highest priority processes scheduled by an RR algorithm e.g. system processes, another might contain high priority processes for interactive user processes, yet another might contain low priority processes for batch processing scheduled by a FCFS algorithm, etc.

• Figure shows the structure of a Multilevel Queue Scheduling system.

Figure: Multilevel Queue Scheduling

[IMAGE png]

• In Multilevel Feedback Queue Scheduling, processes may be moved between the queues:
• If a process uses too much CPU time, it will be moved to a lower priority queue.
• If a process spends too much time waiting in a low priority queue, it may be moved to a higher priority queue -- this prevents starvation, and might better match its (bursty) CPU use to the queue since high priority queues are likely to use schedulers such as RR.

• This scheme leaves IO bound and interactive processes in high priority queues.

• Multilevel Queue Scheduling is categorised by:
• the number of queues;
• the scheduling algorithm for each queue;
• the method to promote a process to a higher priority queue;
• the method to demote a process to a lower priority queue;
• the method to select the initial queue to hold a process.

• The definition of a multilevel feedback queue scheduler makes it the most general CPU scheduling algorithm, and therefore the most difficult to optimally tune.

• Figure (Silberschatz-et-al Figure 6.7) shows a simple Multilevel Queue Scheduling system where processes initially enter the highest priority queue and may only be demoted:
• If the process is not complete after some time spent in an RR scheduler with time quantum = 8, it is demoted to the next queue where an RR algorithm operates with time quantum = 16;
• If the process needs further CPU time, it is moved to a low priority scheduler queue using FCFS.
• Processes in the lower priority queues may only run if the queues above are empty.

Figure: Multilevel Feedback Queues (demotion only)

[IMAGE png]