Multi Level Scheduling in OS

Multi-Level Queue Scheduling: A Hierarchical Approach to CPU Scheduling

Introduction

Multi-Level Queue Scheduling (MLQ) organizes processes into priority-based queues and assigns different scheduling algorithms to each queue. Think of it like an airport security checkpoint:

• First-Class Passengers: Fast-track queue (high priority).
• Economy Passengers: Regular queue (low priority).

Each queue has its own rules, and higher-priority queues are served first!

Key Characteristics

1. Multiple Queues: Processes are grouped by type, priority, or resource needs.
2. Fixed Priority: Queues have a strict hierarchy (e.g., system processes > user apps).
3. Queue-Specific Algorithms:
   • High-priority queues: Shortest Job First (SJF) or Priority Scheduling.
   • Low-priority queues: First-Come, First-Served (FCFS) or Round Robin (RR).
4. No Process Migration: Processes stay in their assigned queue.
5. Starvation Risk: Lower-priority queues may never get CPU time.

Real-Life Analogy

A hospital emergency room:

1. Critical Patients (Queue 1): Treated immediately (SJF).
2. Non-Critical Patients (Queue 2): Served in arrival order (FCFS).

Problem Statement

Schedule the following processes using MLQ with three queues:

1. System Processes (Q1): Round Robin (Time Quantum = 2).
2. Interactive Apps (Q2): Priority Scheduling (lower number = higher priority).
3. Batch Processes (Q3): FCFS.

Step-by-Step Solution

• Step 1: Execute Q1 (Round Robin)

  Time 0-2: P1 runs (Remaining: 2) Time 2-4: P2 runs (Remaining: 1) Time 4-6: P1 runs (Completes at 6) Time 6-7: P2 runs (Completes at 7)

• Step 2: Execute Q2 (Priority Scheduling)

  Time 7-12: P3 runs (Completes at 12) Time 12-14: P4 runs (Completes at 14)

• Step 3: Execute Q3 (FCFS)

  Time 14-20: P5 runs (Completes at 20)

• Final Timeline

  0──2──4──6──7────12────14──────20

  P1	P2	P1	P2	P3	P4	P5

• Step 4: Calculate Completion Times

  P1 = 6, P2 = 7, P3 = 12, P4 = 14, P5 = 20

• Step 5: Turnaround Time = Completion Time − Arrival Time

  P1 = 6, P2 = 7, P3 = 12, P4 = 14, P5 = 20 Average Turnaround Time = (6+7+12+14+20)/5 = 11.8

• Step 6: Waiting Time = Turnaround Time − Burst Time

  P1 = 2, P2 = 4, P3 = 7, P4 = 12, P5 = 14 Average Waiting Time = (2+4+7+12+14)/5 = 7.8

Advantages

• Prioritization
• Efficiency
• Simplicity

Disadvantages

• Starvation
• Rigidity
• Overhead

When to Use

• Distinct process categories
• Priority-sensitive environments

FAQ

Can processes move between queues?

No.

How to prevent starvation?

Aging.

Is MLQ used in modern OS?

Yes, in hybrid form.

Multi-Level Feedback Queue Scheduling: A Dynamic Take on MLQ

Introduction

Multi-Level Feedback Queue (MLFQ) is an enhancement over MLQ that allows process migration between queues based on behavior. It’s like a gaming rank system – if you play well, you get promoted; if not, you get demoted!

Key Characteristics

1. Process Migration: Unlike MLQ, processes can move between queues.
2. Feedback Mechanism: Behavior (CPU-bound vs I/O-bound) decides promotion/demotion.
3. Multiple Queues with Different Policies
4. Preemptive: Often uses Round Robin with varying time quanta.

Real-Life Analogy

Think of a school with merit-based sections:

• Top performers move up to elite classes.
• Others are shifted to average or basic-level sections depending on performance.

MLFQ Working

• New processes enter the highest-priority queue.
• If not finished in their time slice, they are demoted to a lower-priority queue.
• Higher-priority queues are always served first.

Advantages

• Flexible: Adapts to process behavior
• Reduces starvation with dynamic movement
• Good for general-purpose OS

Disadvantages

• Complexity in implementation
• Tuned parameters needed (queue count, time slices, aging rules)

MLFQ Use Cases

• General-purpose systems like Linux, Windows
• Mixed workloads (interactive + batch)

Example

Let’s say we have 3 queues:

• Q1: RR (TQ=2)
• Q2: RR (TQ=4)
• Q3: FCFS

Processes get demoted if they don’t complete within their queue’s time quantum. This dynamic adjustment balances fairness and responsiveness.

Why Use Multi-Level Feedback Queue over MLQ?

What is MLFQ Again?

MLFQ is an evolution of MLQ. It still uses multiple queues, but unlike MLQ (where processes are stuck in one queue), in MLFQ, processes can move up or down between queues depending on how they behave over time.

Core Idea Behind MLFQ

It tries to balance between responsiveness and efficiency by adapting to the nature of the process:

• If you’re an interactive process (like a text editor), you usually need short bursts of CPU. MLFQ will keep you in a high-priority queue so you get quick responses.
• If you’re CPU-hungry (like video rendering), you’ll eventually be moved to a lower-priority queue so you don’t hog the CPU at the cost of responsiveness for others.

Differences — MLQ vs MLFQ

Why MLFQ is Better in Real-World OS?

1. Real-Life Workloads Vary:

   • You might be browsing (short, interactive bursts) and rendering a video (long, CPU-heavy) at the same time.
   • MLFQ dynamically adjusts — giving the browser higher priority without starving the renderer forever.

2. Fairness + Performance:

   • Prioritizes interactive tasks ✅
   • Still allows background tasks to complete eventually ✅
   • No manual queue classification needed ✅

3. Avoids Starvation via Aging:

   • If a process has been waiting too long in lower queues, it gets promoted — ensuring fairness.

Think of it Like a Smart Traffic System

• MLQ is like having fixed lanes: VIPs stay in the fast lane forever, trucks stay in the slow lane forever.
• MLFQ is like a traffic cop who can say: “Hey, this truck’s in a hurry and hasn’t blocked traffic — move it to the fast lane for now!”