Solving the Issues with MLFQ Scheduler

 

Solving the Issues with the Multi-Level Feedback Queue (MLFQ)

The basic MLFQ scheduler is designed to favor short and interactive jobs while still allowing long-running jobs to make progress. However, as discussed earlier, it suffers from three major problems:

1. Starvation

2. Scheduler gaming

3. Inability to adapt to changing process behavior

To address these issues, the MLFQ design is refined through three key improvements:

---

1. Solving Starvation: Priority Boosting 

The Problem

• CPU-bound jobs may be pushed to the lowest-priority queue

• Continuous arrival of interactive jobs can prevent them from ever running

• This leads to starvation

---

The Solution: Priority Boost

The key idea is to periodically reset priorities so that all jobs get a fresh chance to run.

Rule 5 

After some fixed time period S, move all jobs in the system to the topmost queue.

---

Why Priority Boosting Works

Priority boosting solves two problems at once:

1. Prevents Starvation

• All jobs eventually reach the highest-priority queue

• Even CPU-bound jobs get scheduled

• Guarantees forward progress

2. Handles Phase Changes

• A job that was CPU-bound may later become interactive

• After the boost, it is treated like a new interactive job

• Improves responsiveness

---

Example

• Without boosting: long job starves once interactive jobs arrive

• With boosting (e.g., every 100 ms): long job periodically runs

---

The Challenge: Choosing S (Voo-Doo Constant)

• If S is too large → starvation can still occur

• If S is too small → interactive jobs lose responsiveness

• John Ousterhout refers to such parameters as “voo-doo constants”

In practice:

• Administrators tune S

• Modern systems may use automatic  tuning

Example: Effect of Priority Boosting in MLFQ Scheduling

Consider a system with:

• One long-running CPU-bound job

• Two short-running interactive jobs

We examine how the Multi-Level Feedback Queue (MLFQ) scheduler behaves in this scenario under two conditions, as illustrated in Figure 8.4.

---

Case 1: Without Priority Boost (Figure 8.4 – Left)

• The long-running job is gradually pushed down to the lowest-priority queue.

• When the two short-running interactive jobs arrive, they remain in higher-priority queues.

• Because MLFQ always schedules higher-priority jobs first:

  • The interactive jobs consume all available CPU time.

  • The long-running job never gets scheduled.

• This leads to starvation of the CPU-bound job.

🔴 Outcome:
The long-running job is starved and makes no progress.

---

Case 2: With Priority Boost Every 100 ms (Figure 8.4 – Right)

• A priority boost is applied every 100 milliseconds.

• During a priority boost:

  • All jobs in the system are moved to the highest-priority queue.

• As a result:

  • The long-running job periodically regains high priority.

  • It gets scheduled in a round-robin fashion along with other jobs.

  • Even though the boost interval (100 ms) is small for illustration, it ensures fairness.

🟢 Outcome:
The long-running job makes steady progress and is no longer starved.

---

2. Preventing Scheduler Gaming: Better Accounting 

The Problem

• Processes can exploit Rules 4a and 4b

• By issuing I/O before their time slice ends, they:

  • Avoid demotion

  • Stay at high priority

  • Gain unfair CPU share

This is called scheduler gaming.

---

The Solution: Better CPU Accounting

Instead of forgetting how much CPU time a process used when it performs I/O, the scheduler:

• Tracks total CPU time used at each priority level

• Demotes a job once it exhausts its entire allotment, regardless of how it uses the CPU

---

Revised Rule 4 (Anti-Gaming Rule)

Once a job uses up its time allotment at a given level—regardless of how many times it gives up the CPU—its priority is reduced.

---

Why This Works

• Whether CPU time is used:

  • In one long burst

  • Or in many short bursts with I/O

• The result is the same → demotion occurs

This eliminates unfair advantage and improves security and fairness.

Figure 8.5 illustrates how a process can game the MLFQ scheduler under the old rules, and how better CPU accounting eliminates this problem.

Case 1: Old MLFQ Rules (Rules 4a and 4b) – No Anti-Gaming Protection

(Figure 8.5 – Left)

• Under the old rules, a process could:

  • Run almost until its time allotment expires

  • Then voluntarily give up the CPU by issuing an I/O request

• Because the process relinquishes the CPU before its allotment is fully used:

  • It retains its current priority level

  • It is not demoted to a lower queue

• By repeating this behavior carefully:

  • The process stays in a high-priority queue

  • It receives a disproportionately large share of CPU time

🔴 Result:
A clever process can dominate the CPU and unfairly starve other processes.

Case 2: New MLFQ Rule (Rule 4) – Anti-Gaming Accounting

(Figure 8.5 – Right)

• With improved accounting:

  • The scheduler tracks total CPU time used at each priority level

  • It does not reset usage counters when a process performs I/O

• Once a process exhausts its time allotment at a given level:

  • It is demoted to the next lower-priority queue

  • This happens regardless of how many times the process yielded the CPU

🟢 Result:
Even if a process frequently performs I/O, it:

• Gradually moves down the priority queues

• Cannot monopolize CPU time

• Receives only its fair share of processor time

---

Key Insight

Better CPU accounting prevents scheduler manipulation by ensuring that priority is reduced based on total CPU usage, not on how the CPU time is consumed.

---

3. Improving Fairness and Adaptability: Combining Boosting + Accounting

By combining:

• Priority Boosting (Rule 5)

• Accurate CPU Accounting (Rule 4)

MLFQ achieves:

• Starvation freedom

• Resistance to gaming

• Adaptability to changing workloads

---

4. Tuning MLFQ Parameters ( Practical Issues)

Even with these fixes, MLFQ still needs careful tuning.

Key Parameters

• Number of queues

• Time slice per queue

• Allotment per level

• Priority boost interval

There are no universal correct values — tuning depends on workloads.

---

Common Practical Strategies

1. Variable Time Slices

• High-priority queues → short time slices (interactive jobs)

• Low-priority queues → long time slices (CPU-bound jobs)

2. Reserved Priorities

• Highest priorities reserved for kernel/system tasks

3. User Advice

• Tools like nice allow users to influence priority

• OS may treat this advice flexibly

Summary: Varying Time Slices in MLFQ

Most MLFQ schedulers use different time-slice lengths for different priority queues to balance responsiveness and efficiency.

• High-priority queues contain interactive jobs, so they are assigned short time slices (e.g., ≤ 10 ms).
  This allows rapid context switching and quick response to user input.

• Low-priority queues contain CPU-bound, long-running jobs, so they are given longer time slices (e.g., hundreds of milliseconds).
  This reduces context-switch overhead and improves throughput.

Figure 8.6 illustrates this idea:

• Jobs run for 20 ms at the highest priority (10 ms slice),

• 40 ms at the middle priority (20 ms slice),

• and 40 ms at the lowest priority (40 ms slice).

👉 Key idea:

Short quanta improve responsiveness for interactive jobs, while longer quanta improve efficiency for CPU-bound jobs

---

5. Real-World Implementations

Solaris Time-Sharing (TS) Scheduler

• Uses configurable tables

• Controls:

  • Priority changes

  • Time slice lengths

  • Boost intervals

• Default:

  • ~60 queues

  • Boost every ~1 second

---

FreeBSD Scheduler

• Uses mathematical formulas instead of fixed queues

• Priority based on:

  • CPU usage

  • Decay over time

• Achieves priority boosting implicitly

---

Summary: How MLFQ Issues Are Solved

Problem	Solution
Starvation	Periodic priority boosting (Rule 5)
Gaming	Accurate CPU usage accounting (Rule 4)
Phase changes	Priority boost resets behavior
Fairness	Variable time slices
Tuning complexity	Tables, formulas, and user advice

---

Key Takeaway

MLFQ becomes practical only after adding priority boosts, better accounting, and careful tuning.

With these enhancements, it approximates SJF while remaining fair, responsive, and secure.