Problems With the Basic MLFQ Scheduler

 

Problems With the Basic MLFQ Scheduler

Although MLFQ does a good job of:

  • Favoring short and interactive jobs

  • Sharing the CPU among long-running jobs

…it still suffers from serious design flaws. These problems arise mainly because MLFQ infers job behavior indirectly and relies on heuristics.

1. Starvation of Long-Running Jobs

What Is the Problem?

  • If there are many interactive or I/O-bound jobs, they remain in high-priority queues

  • Long-running CPU-bound jobs are pushed into lower-priority queues

  • As a result, CPU-bound jobs may never get scheduled

📌 This situation is called starvation, where a job waits indefinitely without making progress.

Why It Happens in MLFQ

  • High-priority queues always run first

  • Interactive jobs frequently block for I/O and stay at high priority

  • Lower queues may never be reached if higher queues are always busy

Consequence

  • System becomes unfair

  • Batch jobs may never complete

2. Susceptibility to Scheduler Gaming (Unfair Advantage)

What Is Scheduler Gaming?

Scheduler gaming refers to intentionally manipulating program behavior to gain more CPU time than deserved.

How MLFQ Can Be Attacked

A clever program can:

  • Run for almost its entire time slice

  • Issue an I/O request just before its allotment expires

  • Voluntarily give up the CPU

  • Remain at the same high priority level

If done repeatedly, the job:

  • Never gets demoted

  • Gains a disproportionately large share of the CPU

  • Can nearly monopolize the processor

📌 This exploits Rules 4a and 4b, which reward early CPU release without proper accounting.

Why This Is Serious

  • Breaks fairness

  • Allows malicious or selfish users to harm others

  • Turns scheduling into a security concern, especially in shared systems (e.g., datacenters)

3. Inability to Adapt to Changing Process Behavior

The Problem

A process may change behavior over time:

  • Initially CPU-bound

  • Later becomes interactive (or vice versa)

Why Basic MLFQ Fails

  • Once a job is pushed to a low-priority queue, it stays there

  • Even if it later becomes interactive, it:

    • Does not regain high priority

    • Suffers long response times

Consequence

  • Poor responsiveness

  • Incorrect classification of job behavior

  • Reduced system performance

4. Dependence on Poorly Chosen Parameters (Voo-doo Constants)

The Issue

MLFQ relies on parameters such as:

  • Priority boost interval (S)

  • Number of queues

  • Time-slice length

  • Allotment per queue

These values:

  • Have no universally correct setting

  • Are difficult to tune

  • Can cause starvation or poor interactivity if misconfigured

📌 John Ousterhout calls such parameters “voo-doo constants” because they seem to require black magic to set correctly.

Summary Table: Problems With MLFQ

ProblemExplanation
Starvation        Too many interactive jobs can prevent CPU-bound jobs from running
Scheduler gaming        Programs can trick MLFQ to gain unfair CPU share
Poor adaptability        Cannot handle phase changes in process behavior
Voo-doo constants        Performance depends heavily on hard-to-tune parameters
Security concerns        Malicious users can exploit scheduling rules

Key Takeaway

MLFQ is powerful but fragile.
Without additional mechanisms (priority boosting, better accounting, tuning), it can be unfair, insecure, and inefficient

Comments

Post a Comment

Popular posts from this blog

Operating Systems OS PCCST403 Semester 4 BTech KTU CS 2024 Scheme

 About Me Scheme and Syllabus Module-1 Introduction to OS - 3 important pieces- virtualization, concurrency, persistence Operating System Services Operating System and Kernel Linux Versus Classic Unix Kernels Difference between Linux and Unix Kernels Process and Process Creation- overview Process States in Operating System Data Structures in Operating Systems Key Aspects of a Program and Process in an Operating System-Summary Sharing the Processor Among Processes System Boot Sequence Threads and Concurrency Case Study: Linux Kernel Process management Case Study: Linux Implementation of Threads CPU Scheduling Multi-level feedback Queue ( MLFQ) Scheduler How MLFQ Approximates Shortest Job First (SJF) I/O in MLFQ Problems With the Basic MLFQ Scheduler Solving the Issues with MLFQ Scheduler Case Study: Linux Completely Fair Scheduler (CFS)
Read more

Introduction to Operating System -Virtualization, Concurrency, and Persistence

  How Operating Systems Really Work: Virtualization, Concurrency, and Persistence Have you ever wondered how your laptop can play music, run a web browser, download files, and open a Word document—all at the same time—without melting down? It might look simple, but beneath the surface, your operating system (OS) is doing incredibly sophisticated work. In this , we’ll break down the three most important ideas that make modern operating systems possible: Virtualization Concurrency Persistence These concepts are the foundation of how computers manage programs(applications), memory, and data.  1. Virtualization: Making One Computer Look Like Many Virtualization is all about creating useful illusions . You might have Spotify playing, Instagram open, and a browser loading—all on one phone. It feels like all apps run simultaneously, but the phone is rapidly switching between them so smoothly you don’t notice. Virtualization = making one CPU appear like many. Ev...
Read more

Operating Systems PCCST403 Scheme and Syllabus

  OPERATING SYSTEMS (Common to  CS/CD/CM/CR/CA/AD/AI/CB/CN/CC/CU/CI/CG)   Course  Code PCCST403 CIE Marks 40 Teaching Hours/Week (L: T:P: R)   3:1:0:0   ESE Marks   60 Credits 4 Exam Hours 2Hrs.30 Min. Pre requisites(if  any) None Course Type Theory Course  Objectives: 1. To introduce the structure of a typical operating system and its core functionalities. 2. To impart to the students, a practical understanding of OS implementation nuances based on the Linux operating system. 1.        SYLLABUS   Module No. Syllabus  Description Contact Hours       1 Introduction to Operating Systems (Book 1 Ch 2 introductory part), Operating System Services (Book 3 Ch...
Read more