Multilevel Queue (MLQ) CPU Scheduling

It may happen that processes in the ready queue belong to different classes where each class has its own scheduling needs. A common division is foreground (interactive) and background (batch) processes. These classes have different performance requirements and priorities; to handle such situations the Multilevel Queue (MLQ) Scheduling technique is used.

Multilevel Queue (MLQ) CPU Scheduling

In Multilevel Queue Scheduling the ready queue is divided into several separate queues; each queue corresponds to a specific class of processes. Each queue may use a different scheduling algorithm and have a distinct priority relative to other queues. Typical classes include system processes, interactive processes and batch processes. Each class is permanently assigned to one queue and does not move between queues.

Each queue can use an appropriate scheduling policy. For example, queue 1 and queue 2 may use Round Robin while queue 3 uses FCFS (First-Come, First-Served).

Scheduling among the queues

When several queues are non-empty, the scheduler must decide which queue's processes get the CPU. Two common schemes are used:

1. Fixed-priority preemptive scheduling: Each queue is given an absolute priority. For example, if the priority order is queue 1 > queue 2 > queue 3, then no process in a lower-priority queue runs while any higher-priority queue is non-empty. If a process from a higher-priority queue arrives while a lower-priority process is running, the lower-priority process is preempted immediately.
2. Time-slicing (percentage allocation): Each queue is allocated a fixed portion of the CPU time (for example, queue 1 gets 50% of CPU time, queue 2 gets 30%, and queue 3 gets 20%). During its allocated time slice, a queue schedules processes within itself according to its own scheduling policy.

Example

Problem: Consider the table of four processes under Multilevel Queue scheduling where the queue number denotes the queue of each process.

Assume priority of queue 1 is greater than queue 2. Queue 1 uses Round Robin with time quantum = 2, and queue 2 uses FCFS. A possible Gantt chart for this situation is shown below.

Explanation of the Gantt chart:

• At time 0 both queues have processes. Because queue 1 has higher priority, processes in queue 1 (P1, P2) run first in Round Robin order with quantum 2.
• After queue 1 processes complete (after 7 time units in this example), the scheduler switches to queue 2 and runs its process P3 in FCFS order.
• If a new process (P4) arrives in the higher-priority queue 1 while P3 is running, P3 is preempted and P4 runs immediately (fixed-priority preemptive policy). After P4 finishes, P3 resumes and completes.

Advantages

• Low scheduling overhead because processes are permanently assigned to queues; the scheduler only chooses among queues and then within a chosen queue.

Disadvantages

• Starvation can occur for processes in low-priority queues if higher-priority queues are frequently non-empty.
• Inflexible: permanent assignment to a queue may be unsuitable if a process's behaviour changes over time.

Multilevel Feedback Queue (MLFQ) CPU Scheduling

Multilevel Feedback Queue (MLFQ) is an extension of the multilevel queue idea that allows processes to move between queues. The scheduler observes process behaviour (for example, how long a process runs before blocking for I/O) and dynamically adjusts the process's priority by moving it between queues. This provides greater flexibility and allows the system to approximate algorithms such as SJF (Shortest Job First) without knowing exact burst times in advance.

One common implementation of MLFQ

1. When a process first arrives it is placed in the highest-priority queue (queue 1).
2. If it uses less than or equal to the time quantum of queue 1 (for example 4 units), or it voluntarily relinquishes the CPU for I/O during that quantum, it retains its priority and remains (or will re-enter) in the higher queue when it next becomes ready.
3. If it uses the entire time quantum of queue 1 without completing, its priority is lowered and it is moved to queue 2.
4. The same rule applies at queue 2 with a larger time quantum (for example 8 units): using up the queue-2 quantum moves the process to a lower-priority queue.
5. The lowest-priority queue is often scheduled with FCFS, though it can use Round Robin or another policy.
6. A process in a lower-priority queue executes only when all higher-priority queues are empty.
7. A process running in a lower-priority queue is preempted if a new process arrives in a higher-priority queue.

Implementations vary. For example, the last queue could use Round Robin instead of FCFS, or the demotion/promotion rules can differ.

Problems and a common solution

A long-running process placed in a lower-priority queue can suffer starvation if many short processes keep arriving and occupying higher-priority queues.

A common solution is priority boosting: at regular intervals the scheduler raises the priority of waiting processes (for example, moving all processes back to the highest-priority queue). This prevents indefinite starvation and rebalances the system periodically.

Why use a complex scheduler like MLFQ?

1. MLFQ is more flexible than static multilevel queue scheduling because it adapts to observed process behaviour.
2. It attempts to optimise turnaround time by favouring interactive or short CPU bursts: by running processes for a limited quantum and demoting those that use full quanta, the scheduler learns which processes are long and which are short and gives preference to short ones.
3. It reduces response time for interactive processes by keeping them in higher-priority queues when they frequently relinquish the CPU quickly.

Example

Consider a system which has a CPU bound process, which requires the burst time of 40 seconds. The multilevel Feed Back Queue scheduling algorithm is used and the queue time quantum '2' seconds and in each level it is incremented by '5' seconds.Then how many times the process will be interrupted and on which queue the process will terminate the execution?

Solution:

Process P needs 40 seconds for total execution.

At queue 1 it executes for 2 seconds and is interrupted and shifted to queue 2.

At queue 2 the time quantum is 2 + 5 = 7 seconds; it executes for 7 seconds and is interrupted and shifted to queue 3.

At queue 3 the time quantum is 7 + 5 = 12 seconds; it executes for 12 seconds and is interrupted and shifted to queue 4.

At queue 4 the time quantum is 12 + 5 = 17 seconds; it executes for 17 seconds and is interrupted and shifted to queue 5.

By now the process has executed 2 + 7 + 12 + 17 = 38 seconds; 2 seconds remain.

At queue 5 the time quantum would be 17 + 5 = 22 seconds, but only 2 seconds of remaining CPU time are needed; the process executes for 2 seconds and then completes.

Hence the process is interrupted 4 times and finishes execution in queue 5.

Advantages of MLFQ

• More flexible and adaptive than static multilevel queues.
• Allows processes to move between queues according to observed behaviour.
• Can reduce response time for interactive processes and approximate SJF behaviour without prior knowledge of burst times.

Disadvantages of MLFQ

• Requires careful tuning: selection of number of queues, time quanta and promotion/demotion rules affects performance and fairness.
• Produces higher scheduling overhead compared to simpler schedulers because it must track behaviour and move processes between queues.
• More complex to implement and reason about; incorrect parameters may cause poor performance or unfairness.

Summary (optional): Multilevel Queue Scheduling is suitable when processes naturally fall into fixed classes with different scheduling needs; Multilevel Feedback Queue adds adaptability by allowing processes to change priority based on behaviour, reducing response time for interactive tasks and helping approximate short-job favouring policies while taking care to avoid starvation through mechanisms such as priority boosting.