←Back to Subject
Notes
Notes
Study material and explanations
Diagrams
Diagrams
Visualize concepts easily
Mnemonics
Mnemonics
Tricks to remember faster
One Night Prep
One Night Prep
Short and focused revision
Revision
Revision
Quick summary and key points
Important Questions
Important Questions
Practice most relevant questions
Notes

Multiple-Processor, Real-Time, Multilevel Queue & Multilevel Feedback Queue Scheduling

Study material and explanations for Unit 2

Multiple-Processor, Real-Time, Multilevel Queue & Multilevel Feedback Queue Scheduling

1. Multiple-Processor Scheduling

When a computer system has multiple CPUs (or a Multi-Core Processor), scheduling becomes more complex because multiple processes can run in parallel at the same time.

Two Approaches to Multiple-Processor Scheduling:

  1. Asymmetric Multiprocessing (AMP): A single processor (the Master Server) handles all scheduling decisions, I/O processing, and system activities, while the other processors (Slaves) execute only user code. It is simple because only one core accesses kernel data structures, but the Master CPU can become a bottleneck.
  2. Symmetric Multiprocessing (SMP — Standard Today): Every processor is self-scheduling. All CPUs either share a single common Ready Queue (protected by locks) or each CPU has its own private Ready Queue.

Two Key Issues in SMP Scheduling:

  • Processor Affinity: When a process runs on CPU Core 1, its data fills up Core 1’s high-speed Cache Memory. If the process is migrated to Core 2, Core 1’s cache is wasted and Core 2 must reload everything from RAM! Therefore, SMP systems try to keep a process running on the same processor (Soft Affinity or strict Hard Affinity).
  • Load Balancing: Ensures that one CPU core isn’t sitting idle while another core has 10 processes waiting in its queue. Achieved via Push Migration (busy CPU pushes tasks to idle CPU) or Pull Migration (idle CPU pulls waiting tasks from a busy CPU).

2. Real-Time CPU Scheduling

In Real-Time Operating Systems (RTOS), processes have strict Deadlines by which they must complete:

  • Soft Real-Time Scheduling: Guarantees that critical real-time processes are given higher priority than non-critical processes, though it does not guarantee when they will be scheduled.
  • Hard Real-Time Scheduling: A process must be serviced before its deadline expires; once admitted, the OS guarantees on-time completion using two famous algorithms:
Figure 2.7: Two Classical Hard Real-Time Scheduling Algorithms
1. Rate-Monotonic (RM) Scheduling
  • Static Priority algorithm for periodic tasks
  • Priority is assigned based on the inverse of the task's period ((1 / P))
  • Shorter period (runs more frequently) = Higher Priority!
2. Earliest-Deadline-First (EDF)
  • Dynamic Priority algorithm
  • Whenever a task needs the CPU, the scheduler picks the task whose deadline is closest!
  • Earlier deadline = Higher Priority (Optimal, up to 100% CPU utilization)

3. Multilevel Queue (MLQ) Scheduling

In real operating systems, all processes are not alike! For example, System processes (kernel tasks), Interactive GUI processes (foreground apps), and Batch jobs (background backups) have completely different response-time needs. Putting all of them into a single Ready Queue with one algorithm does not work well.

How Multilevel Queue (MLQ) Scheduling Works:

  1. The Ready Queue is partitioned into several separate, permanent queues based on the type/priority of processes.
  2. A process is permanently assigned to one queue when it enters the system (based on process type, memory size, or priority) and CANNOT move to another queue!
  3. Each queue has its own independent scheduling algorithm (e.g., Interactive queue uses Round Robin, while Batch queue uses FCFS).
Figure 2.8: Multilevel Queue (MLQ) Scheduling Architecture
Priority 1 (Highest)System Processes Queue
Kernel & OS tasks — Scheduled using Priority / RR
Priority 2Interactive Processes (Foreground)
GUI & User apps — Scheduled using Round Robin (RR)
Priority 3Interactive Editing Processes
Text editors & IDEs — Scheduled using RR / SJF
Priority 4 (Lowest)Batch Processes (Background)
Backups & Long jobs — Scheduled using FCFS

Scheduling Between the Queues in MLQ:

How does the CPU divide its time among the different queues? Using one of two methods:

  1. Fixed-Priority Preemptive Scheduling: No process in the Batch queue can run unless the System and Interactive queues above it are 100% empty! (Drawback: Can cause Starvation of lower queues).
  2. Time-Slicing Between Queues: Each queue gets a guaranteed percentage of CPU time—for example, the Foreground Interactive queue gets 80% of CPU time (using Round Robin), and the Background Batch queue gets 20% of CPU time (using FCFS).

4. Multilevel Feedback Queue (MLFQ) Scheduling

Why Was MLFQ Invented?

In standard Multilevel Queue (MLQ) scheduling, processes are permanently locked into one queue (inflexible) and low-priority queues can starve.

Multilevel Feedback Queue (MLFQ) Scheduling solves this by allowing a process to move (migrate) UP or DOWN between queues dynamically based on its actual runtime CPU burst behavior!

Figure 2.9: Multilevel Feedback Queue (MLFQ) — Processes Move Between Queues
Queue 0 (Highest Priority)Round Robin (Quantum = 8 ms)
→ If not finished in 8 ms, Demote ↓ →
Queue 1 (Medium Priority)Round Robin (Quantum = 16 ms)
→ If not finished in 16 ms, Demote ↓ →
Queue 2 (Lowest Priority)FCFS (Runs when Q0 & Q1 are empty)

How Multilevel Feedback Queue (MLFQ) Works:

  1. New Process Entry: Every new process enters at the top Queue 0 and is given a short time quantum of 8 ms (Round Robin).
    • If it is a short/interactive I/O process, it finishes within 8 ms and leaves immediately!
  2. Demotion (Punishing CPU Hogs): If the process does not finish within 8 ms, it is preempted and moved down (demoted) to Queue 1, where it gets a larger quantum of 16 ms.
  3. If it still does not finish in 16 ms, it is demoted to Queue 2 (FCFS) at the bottom.
  4. Promotion (Preventing Starvation via Aging): If a process waits too long in a lower queue (Queue 2) without getting the CPU, the OS promotes (upgrades) it back up to a higher-priority queue!

5. Comparison: Multilevel Queue (MLQ) vs Multilevel Feedback Queue (MLFQ)

This is a favorite 5- to 8-mark comparison question in DAVV BCA exams!

Basis Multilevel Queue (MLQ) Multilevel Feedback Queue (MLFQ)
1. Process Movement Processes are permanently assigned to one queue and cannot move between queues. Processes can move freely UP and DOWN between different queues based on CPU behavior.
2. Flexibility Rigid and Inflexible (requires knowing process nature in advance). Highly Flexible and Adaptive (learns whether a job is CPU-bound or I/O-bound automatically).
3. Starvation Risk High risk of Starvation for lower-priority queues under fixed priority. Prevents Starvation by promoting (aging) processes that wait too long in lower queues.
4. Design Complexity Simple to implement with low overhead. The most general and complex scheduling algorithm (used in Windows, macOS, and Linux variants).

💡 Exam Preparation Tips for DAVV BCA

  • Always draw Figure 2.8 for Multilevel Queue and Figure 2.9 (Q0: q=8ms → Q1: q=16ms → Q2: FCFS) for Multilevel Feedback Queue! That classic 8 ms → 16 ms → FCFS diagram is straight from Silberschatz (Galvin) and examiners love it.
  • Remember the 1-line difference: MLQ = No movement between queues; MLFQ = Processes move between queues based on feedback.