Multi-level Queue Scheduling (MLQ) – CPU Scheduling

Multi-level Queue Scheduling (MLQ)

• Multilevel Queue Scheduling classifies the processes according to their types. For example, a multilevel queue scheduling algorithm makes a common division between the interactive processes (foreground) and batch processes (background). These two processes have different response times, so they have different scheduling requirements. Also, the interactive process has higher priority than the batch process.
• In this scheduling, ready queue is divided into various queues that are called subqueues. A subqueue is a distinct operational queue.
• The processes are permanently assigned to subqueues, generally based on some property of the process such as memory size, priority or process type.
• Each subqueue has its own scheduling algorithm. For example, interactive processes at the foreground may use round robin scheduling while batch jobs at the background may use the FCFS method.
• In addition, there is a scheduling algorithm that works globally between the different subqueues. Usually this is a fixed priority preemptive scheduling. For example, the foreground queue may have absolute priority over the background queue.

• However for scheduling between the queues different approach can be used different approaches are to use absolute priority or time slicing.
• For example, consider a system with four different queues

1. System processes
2. Interactive processes
3. Batch processes
4. End-user processes

• In this example, each queue has absolute priority over low priority queues. No process in a batch queues could run unless the queues for system processes and interaction processes were all empty.

If an interactive process entered the ready queue while a batch process was running, the batch process would be preempted. For example, Solaris 2 operating system uses this form of algorithm.

An alternate approach is to assign a certain portion of CPU time to each queue. This time slice that each queue gets, can be further scheduled among the various processes the respective subqueue.

Advantage of multi-level queue scheduling

1. In multi-level queue scheduling, processes are permanently assigned to a queue entry to the system. Since processes do not change their foreground or nature, this set up has advantage of low scheduling overhead. background

Disadvantages of multi-level queue scheduling higher

1. In multi-level queue scheduling same processes may starve for CPU if some priority queues are never becoming empty.
2. It is inflexible as the processes can never change their queues.