Round Robin & Multi-Level Queue Scheduling

In a well-designed organization, employees don't remain at the same level forever. High performers get promoted; underperformers may be reassigned. But the rules governing these transitions—the criteria, timing, and speed of movement—profoundly affect both individual careers and organizational effectiveness.

Multi-level scheduling systems face identical challenges. Queue movement policies determine how processes transition between priority levels. Should a process be demoted after one bad quantum or after sustained CPU-bound behavior? Should promotion happen instantly upon I/O completion or gradually over time? Should all processes be boosted simultaneously or individually?

These policies, while often overlooked in introductory treatments, are the heart of practical MLFQ implementation. The difference between a responsive system and a sluggish one often comes down to the details of queue movement—how aggressively the scheduler demotes, how generously it promotes, and how it handles edge cases like behavior phase changes.

Demotion policies determine when and how a process moves to a lower-priority queue. The choice of demotion strategy significantly affects both interactive responsiveness and CPU-bound throughput.

Policy 1: Single-Quantum Demotion

The simplest approach: demote after a single full quantum usage.

if (used_full_quantum) {
    priority--;
}

Characteristics:

• Aggressive: Rapid demotion of even slightly CPU-bound processes
• Responsive: Interactive processes are quickly distinguished
• Unfair: Bursty processes (occasional long bursts) unfairly penalized
• Gaming risk: Easy to exploit with minimal I/O

Policy 2: Threshold-Based Demotion

Demote only after multiple consecutive full-quantum usages.

if (used_full_quantum) {
    consecutive_full_quanta++;
    if (consecutive_full_quanta >= THRESHOLD) {
        priority--;
        consecutive_full_quanta = 0;
    }
} else {
    consecutive_full_quanta = 0;  // Reset on early yield
}

Characteristics:

• Tolerant: Handles occasional long bursts without penalty
• Slower classification: Takes longer to identify CPU-bound processes
• More resistant to bursts: Doesn't overreact to temporary behavior

Policy 3: Time Allotment Demotion (Cumulative Accounting)

Track cumulative CPU time at each priority level; demote when allotment exceeded.

time_at_priority += time_used;
if (time_at_priority >= allotment[priority]) {
    priority--;
    time_at_priority = 0;
}

Characteristics:

• Fair: Every process gets same total time at each priority
• Gaming-resistant: Cannot cheat by fragmenting CPU usage
• Predictable: Demotion timing is deterministic based on CPU consumption
• Industry standard: Used in most production MLFQ implementations

Policy 4: Weighted Demotion

Weight CPU usage based on context—giving processes partial credit for partial quantum usage.

demotion_score += (time_used / quantum) * weight;
if (demotion_score >= 1.0) {
    priority--;
    demotion_score -= 1.0;
}

Characteristics:

• Proportional: Processes demoted based on actual behavior intensity
• Gradual: Smooth demotion rather than step functions
• Complex: More state to track, more parameters to tune

Promotion policies determine when and how processes move to higher-priority queues. Unlike demotion (which follows CPU usage), promotion typically serves multiple goals: starvation prevention, behavior adaptation, and interactive responsiveness.

Policy 1: Periodic Global Boost

All processes are simultaneously promoted to highest priority at fixed intervals.

if (current_time % BOOST_PERIOD == 0) {
    for (all processes) {
        process.priority = 0;
        process.time_at_priority = 0;
    }
}

Characteristics:

• Simple: Single timer, uniform treatment
• Complete: Guarantees every process runs at high priority periodically
• Disruptive: All processes compete at once after boost—temporary congestion
• Phase-agnostic: Re-evaluates all processes regardless of recent behavior

Policy 2: Aging-Based Promotion

Promote processes individually after they've waited a certain time without CPU access.

for (each process in lower queues) {
    if (current_time - last_run_time >= AGE_THRESHOLD) {
        process.priority = max(process.priority - 1, 0);
        process.last_run_time = current_time;
    }
}

Characteristics:

• Individual: Each process promoted based on its own waiting time
• Starvation-focused: Directly addresses the starvation problem
• Smooth: No sudden congestion from mass promotion
• Complex: Requires per-process timestamp tracking

Policy 3: I/O Completion Boost

Promote processes when they complete I/O operations.

void on_io_completion(Process* p) {
    if (io_was_interactive(p->last_io)) {
        p->priority = 0;  // Boost to top
    } else {
        p->priority = max(p->priority - 1, 0);  // Partial boost
    }
}

Characteristics:

• Behavior-based: Rewards I/O-bound (typically interactive) behavior
• Immediate: Responsive to actual behavior, not timers
• Targeted: Only affects processes demonstrating interactive patterns
• Windows-like: Similar to Windows' priority boost mechanism

Policy 4: Graduated Promotion

Promote processes gradually—one level at a time—rather than jumping to top.

void promote(Process* p) {
    if (p->priority > 0) {
        p->priority--;  // Move up one level
        p->time_at_priority = 0;
    }
}

Characteristics:

• Conservative: Slower to regain high priority
• Resistant to exploitation: Gaming produces limited benefit
• Stable: Less queue thrashing from rapid promotion/demotion cycles
• May under-respond: Truly interactive processes may suffer

Policy 5: Hybrid Promotion (Graduated with I/O Boost)

Combine gradual aging with instant boost for I/O events.

// Aging: gradual promotion over time
if (wait_time >= AGE_THRESHOLD) {
    priority = max(priority - 1, 0);  // One level up
}

// I/O boost: instant promotion for interactive I/O
if (io_completion && is_user_interaction(io_type)) {
    priority = 0;  // Jump to top
}

Characteristics:

• Balanced: General starvation protection plus interactive responsiveness
• Practical: Reflects that not all I/O is equally latency-sensitive
• Complex: Multiple promotion paths with different behaviors

Beyond which policy to use, the speed and granularity of queue movement significantly impact system behavior.

Movement Step Size:

Single-step movement (±1 level):

• Conservative, gradual adjustment
• More stable, less queue thrashing
• Slower response to behavior changes
• Used in most classic MLFQ implementations

Multi-step movement (jump multiple levels):

• Aggressive response to behavior
• Can cause oscillation between extremes
• Good for systems with distinct process classes
• Jump-to-top for promotion, single-step for demotion is common

Continuous priority (no discrete levels):

• CFS-style virtual runtime approach
• Infinitely fine-grained adjustment
• No discrete 'jumps'—smooth priority changes
• Complex implementation but optimal behavior

Movement Speed Tradeoffs:

The asymmetric approach (fast demotion, slow promotion) is common in production because:

• CPU-bound processes should quickly move out of high-priority queues
• Promotion should be earned through sustained interactive behavior
• This prevents processes from gaming by alternating between CPU and I/O phases

Real-world schedulers must handle numerous edge cases that simple MLFQ rules don't address:

Edge Case 1: Process Fork/Clone

When a process creates a child, what priority should the child have?

Options:

• Inherit parent priority: Child starts where parent is (Unix-like)
• Reset to highest: Child starts fresh at top (classical MLFQ)
• Split parent's allotment: Child shares parent's remaining allotment

Best practice: Inherit priority but reset allotment timer. This prevents fork bombs from gaming the system while maintaining priority inheritance for legitimate child processes.

Edge Case 2: Priority Inversion

A low-priority process holds a lock needed by a high-priority process.

Solutions:

• Priority inheritance: Temporarily boost the low-priority holder to high priority
• Priority ceiling: Holding certain locks grants automatic high priority
• Scheduler must integrate with lock subsystem

Edge Case 3: Sleeping/Resumed Processes

A process sleeps for extended time (user suspends laptop, process waits for rare event).

Options:

• Preserve priority: Resume at same priority as before sleep
• Treat as new: Reset to highest priority after long sleep
• Decay during sleep: Gradually reduce priority while sleeping

Best practice: Preserve priority for short sleeps; treat as new arrival for very long sleeps (> boost period).

Edge Case 4: Scheduler Tick Drift

Timer interrupts aren't perfectly accurate. A process may use slightly more or less than its quantum.

Solutions:

• Accumulate error: Track cumulative usage, not per-quantum
• Use TSC/HPET: High-resolution timers for accurate measurement
• Margin tolerance: Allow small overruns without penalty

Edge Case 5: Real-Time Process Interference

Real-time processes may starve MLFQ-managed processes entirely.

Solutions:

• Real-time bandwidth limit: Reserve percentage of CPU for non-real-time
• Real-time admission control: Limit number/intensity of real-time processes
• Separate scheduling domains: Real-time and non-real-time don't share CPU directly

Let's examine how major operating systems implement queue movement:

Linux CFS: Virtual Runtime Movement

Linux CFS doesn't use discrete queues but achieves equivalent effects through virtual runtime:

// Virtual runtime increases as process runs
vruntime += delta_exec * (NICE_0_WEIGHT / weight);

// Process with lowest vruntime is selected
// This naturally sorts by CPU consumption
current = pick_next_entity(cfs_rq);

Movement equivalents:

• Demotion: CPU usage increases vruntime → process sorted later
• Promotion: Sleeping resets vruntime → process moves forward
• Boost: sched_latency ensures all processes run within period

Key parameters:

• sched_latency_ns: Target latency for runnable processes (6ms default)
• sched_min_granularity_ns: Minimum runtime before preemption (0.75ms)
• Nice values: Weight the rate of vruntime accumulation

Windows: Dynamic Priority with Boost/Decay

Windows uses explicit priority levels (0-31) with dynamic adjustment:

// Priority boost on I/O completion
if (io_completed) {
    boost = get_io_boost(io_type);  // 1-15 depending on device
    current_priority = base_priority + boost;
}

// Priority decay each quantum
if (used_full_quantum) {
    current_priority = max(current_priority - 1, base_priority);
}

Movement characteristics:

• Boost events: I/O completion, foreground window, lock release
• Decay: One level per quantum until base priority
• Ceiling: Maximum of priority class (e.g., 15 for normal class)
• Foreground boost: 3× quantum for foreground process

FreeBSD ULE Scheduler:

ULE uses interactivity scoring to guide movement:

// Interactivity score based on sleep vs. run ratio
interactivity = SCHED_INTERACT_MAX - 
                (run_time / (sleep_time + run_time)) * SCHED_INTERACT_MAX;

// High interactivity → high priority
priority = base_priority - interactivity_boost(interactivity);

Movement characteristics:

• Continuous scoring: No discrete queues, smooth adjustment
• Sleep/run ratio: Interactive processes have high sleep ratio
• Dynamic recomputation: Score recalculated on each scheduling event

When designing queue movement policies for custom systems (embedded, real-time, specialized servers), consider these guidelines:

Step 1: Define Workload Characteristics

Before designing policies, understand your workload:

• Interactive ratio: What fraction of processes are interactive vs. batch?
• Burst distribution: What are typical CPU burst lengths?
• Phase change frequency: How often do processes change behavior?
• Latency requirements: What's the maximum acceptable response time?
• Throughput needs: How important is batch job completion?

Step 2: Set Demotion Parameters

allotment[i] = base_quantum * (quantum_multiplier ^ i) * demotion_factor

• demotion_factor = 1: Fast demotion, quick separation of process types
• demotion_factor = 3: Slow demotion, tolerant of bursts
• Typical: 2 for most workloads

Step 3: Set Promotion Parameters

aging_threshold = boost_period / num_queues  // Ensures progression
io_boost_levels = interactive_dominance ? ALL : 1-2

• Interactive workloads: Aggressive I/O boost (jump to top)
• Server workloads: Modest I/O boost (1-2 levels)
• Batch workloads: Aging only, no I/O boost

Step 4: Tune Boost Period

boost_period = max_acceptable_latency / (1 + starvation_tolerance)

• Low latency systems: 500ms-1s
• Throughput systems: 5s-10s
• Hybrid: 1s-2s (common default)

Step 5: Handle Edge Cases

Explicitly decide policy for:

• Fork/clone: Inherit or reset?
• Long sleep: Preserve or decay?
• Priority inheritance: Support or not?
• Real-time: Separate or integrated?

Movement policies directly impact key performance metrics. Understanding these relationships helps in policy tuning.

Impact on Response Time:

• Fast demotion: Quick separation of interactive from batch → better response
• Aggressive I/O boost: Interactive processes return to top quickly → better response
• Short boost period: Regular refresh of priorities → bounded worst-case response

Impact on Throughput:

• Slow demotion: CPU-bound processes stay up longer → throughput slightly better but response suffers
• Large quanta at low priority: Less context switching for batch → better throughput
• Long boost period: Less disruption from priority resets → slightly better throughput

Impact on Fairness:

• Cumulative time accounting: Fair regardless of burst pattern → better fairness
• Regular boosts: Every process gets periodic high-priority access → bounded unfairness
• Aging promotion: Starving processes eventually promoted → starvation prevention

Benchmark Example:

Consider tuning the boost period on a mixed workload (50% interactive, 50% batch):

Observation: The 500ms-1000ms range typically provides the best balance. Shorter periods disrupt batch work; longer periods harm interactive response.

We have comprehensively explored queue movement policies—the detailed algorithms governing how processes navigate between priority levels in multi-level scheduling systems.

Module Complete:

With this page, we have completed our comprehensive exploration of Round Robin and Multi-Level Queue Scheduling. You now understand:

1. Round Robin: The fundamental time-sharing algorithm with fair CPU allocation
2. Time Quantum Selection: The critical tradeoff between responsiveness and overhead
3. Multi-Level Queues: Separating processes by class for differentiated service
4. MLFQ: The adaptive scheduler that learns process behavior
5. Queue Movement Policies: The detailed rules governing priority transitions

This knowledge forms the foundation for understanding CPU scheduling in any operating system—from embedded RTOS to cloud hypervisors.