Skip to content

Scheduling

Jump to bottom
Enrico Fraccaroli (Galfurian) edited this page Jan 29, 2026 · 7 revisions

CPU scheduling algorithms in MentOS.

Overview

MentOS supports multiple scheduling algorithms, configurable at build time. The scheduler determines which process runs on the CPU and for how long.

Available Schedulers

1. Round-Robin (RR)

Type: Time-sharing, preemptive
Best for: General-purpose, interactive systems

Algorithm:

  • Each process gets a fixed time slice (quantum)
  • Processes are arranged in a circular queue
  • When quantum expires, process is preempted and moved to back of queue
  • All processes get equal CPU time

Configuration:

cmake .. -DSCHEDULER_TYPE=SCHEDULER_RR

Characteristics:

  • Fair: All processes get equal time
  • Simple: Easy to implement and understand
  • Low overhead: Minimal scheduling overhead
  • Poor for real-time: No priority or deadline support

Time Quantum: Driven by timer ticks (see kernel/inc/hardware/timer.h and scheduler_run() logic)

2. Priority-Based Scheduler

Type: Priority-based, preemptive
Best for: Systems with varied workload priorities

Algorithm:

  • Each process has a priority (lower value = higher priority)
  • Scheduler always picks highest priority ready process
  • Lower priority processes may starve if high-priority processes keep arriving
  • Same priority processes use round-robin

Configuration:

cmake .. -DSCHEDULER_TYPE=SCHEDULER_PRIORITY

Characteristics:

  • Prioritization: Important processes run first
  • Responsive: High-priority tasks get CPU immediately
  • Starvation risk: Low-priority processes may never run
  • No fairness guarantees

Priority Levels:

  • 0-99: Real-time priorities
  • 100-139: Normal priorities

Setting Priority:

#include <sched.h>

struct sched_param param;
param.sched_priority = 50;
sched_setparam(pid, &param);

3. Completely Fair Scheduler (CFS)

Type: Fair-share, time-based
Best for: Desktop/server systems, Linux-like behavior

Algorithm:

  • Tracks "virtual runtime" (vruntime) for each process
  • Always picks process with lowest vruntime
  • vruntime increases as process runs
  • Nice values affect vruntime increase rate
  • Uses a runqueue scan to select the minimum vruntime task

Configuration:

cmake .. -DSCHEDULER_TYPE=SCHEDULER_CFS

Characteristics:

  • Fair: Each process gets proportional CPU time
  • Responsive: Good interactive performance
  • Scalable: Efficient for many processes
  • Complex: More sophisticated algorithm

Nice Values:

  • Range: -20 (highest priority) to +19 (lowest)

  • Default: 0

  • Setting nice value:

    nice(10);  // Decrease priority by 10

4. Earliest Deadline First (EDF)

Type: Real-time, dynamic priority
Best for: Real-time systems with explicit deadlines

Algorithm:

  • Each task has a deadline
  • Scheduler always picks task with earliest deadline
  • Optimal for single-CPU real-time scheduling
  • Preempts if a task with earlier deadline arrives

Configuration:

cmake .. -DSCHEDULER_TYPE=SCHEDULER_EDF

Characteristics:

  • Optimal: Maximizes number of tasks meeting deadlines
  • Dynamic: Priorities change based on deadlines
  • Real-time: Suitable for hard real-time systems
  • Predictable: Behavior is deterministic

Setting Deadline:

struct sched_param param;
param.deadline = 1000;  // absolute deadline in ticks
sched_setparam(pid, &param);

5. Rate Monotonic (RM)

Type: Real-time, static priority
Best for: Periodic real-time tasks

Algorithm:

  • Each task has a fixed period
  • Priority is inversely proportional to period (shorter period = higher priority)
  • Static priorities never change
  • Preemptive

Configuration:

cmake .. -DSCHEDULER_TYPE=SCHEDULER_RM

Characteristics:

  • Simple: Static priorities, easy to analyze
  • Optimal: Among static-priority algorithms
  • Predictable: Behavior is deterministic
  • Limited: Only works for periodic tasks

Setting Period:

struct sched_param param;
param.period = 100;  // period in ticks
sched_setparam(pid, &param);

6. Adaptive Earliest Deadline First (AEDF)

Type: Real-time, adaptive
Best for: Mixed periodic/aperiodic real-time workloads

Algorithm:

  • Combines EDF with aperiodic task handling
  • Periodic tasks use EDF
  • Aperiodic tasks are scheduled in slack time
  • Adapts to varying workload

Configuration:

cmake .. -DSCHEDULER_TYPE=SCHEDULER_AEDF

Characteristics:

  • Flexible: Handles both periodic and aperiodic tasks
  • Efficient: Maximizes CPU utilization
  • Complex: More sophisticated than pure EDF
  • Research-oriented: Experimental scheduler

Comparison Table

Scheduler Type Preemptive Fair Real-time Complexity
RR Time-sharing Yes Yes No Low
Priority Priority Yes No Partial Low
CFS Fair-share Yes Yes No Medium
EDF Real-time Yes N/A Yes Medium
RM Real-time Yes N/A Yes Low
AEDF Real-time Yes Partial Yes High

Choosing a Scheduler

Use RR when

  • Building a general-purpose system
  • Want simplicity and fairness
  • Interactive processes (shell, editor)
  • Learning OS concepts

Use Priority when

  • Some tasks are more important than others
  • Need explicit control over task importance
  • Background tasks should yield to foreground

Use CFS when

  • Want Linux-like behavior
  • Need fairness with some priority control
  • Desktop or server workloads
  • Many processes with varying importance

Use EDF when

  • Have real-time requirements with deadlines
  • Tasks have explicit timing constraints
  • Need optimal real-time scheduling
  • Willing to specify deadlines explicitly

Use RM when

  • All tasks are periodic
  • Want static priority analysis
  • Need predictable, deterministic behavior
  • Simple real-time system

Use AEDF when

  • Have both periodic and aperiodic real-time tasks
  • Need flexible real-time scheduling
  • Researching advanced scheduling algorithms

Implementation Details

Scheduler Interface

All schedulers implement:

// Initialize scheduler
void scheduler_initialize(void);

// Pick next task to run
task_struct *scheduler_pick_next_task(runqueue_t *runqueue);

// Enqueue a runnable task
void scheduler_enqueue_task(task_struct *task);

// Dequeue a task
void scheduler_dequeue_task(task_struct *task);

// Run scheduler (called from timer/interrupt paths)
void scheduler_run(pt_regs_t *f);

Scheduler Location

  • Source: kernel/src/process/scheduler.c
  • Header: kernel/inc/process/scheduler.h
  • Algorithm implementations: kernel/src/process/scheduler_algorithm.c

Context Switch

Scheduler is invoked on:

  1. Timer interrupt (PIT ticks)
  2. Process blocks (waiting for I/O, sleep, etc.)
  3. Process exits

Context switch process:

// Save current process state
// Save current process state
scheduler_store_context(f, current_task);

// Pick next task
next_task = scheduler_pick_next_task(&runqueue);

// Restore next task state
scheduler_restore_context(next_task, f);

// Update current task pointer
current_task = next_task;

Scheduler Configuration

Time Quantum

MentOS bases scheduling decisions on timer ticks (see kernel/inc/hardware/timer.h).

Priority Ranges

Modify priority ranges:

// kernel/inc/process/prio.h
#define MAX_RT_PRIO 100
#define MAX_PRIO    (MAX_RT_PRIO + NICE_WIDTH)

Performance Metrics

Measuring Scheduler Performance

// In kernel code
unsigned long start = timer_get_ticks();
scheduler_pick_next_task(&runqueue);
unsigned long end = timer_get_ticks();
pr_debug("Scheduler overhead: %lu ticks\n", end - start);

Typical Overheads

Scheduler Overhead (cycles) O() complexity
RR ~100 O(1)
Priority ~200 O(1)
CFS ~500 O(log n)
EDF ~400 O(n) or O(log n)
RM ~100 O(1)
AEDF ~600 O(log n)

Debugging Schedulers

Enable Scheduler Logging

// kernel/src/process/scheduler.c
#define __DEBUG_LEVEL__ LOGLEVEL_DEBUG

// Logs scheduler decisions
pr_debug("Switching from PID %d to PID %d\n", old_pid, new_pid);

Monitor Process States

Use procfs entries such as /proc/<pid>/stat and scheduler feedback in /proc/feedback.

Testing Schedulers

Test programs in userspace/tests/:

  • t_periodic1.c - Single periodic task
  • t_periodic2.c - Multiple periodic tasks
  • t_periodic3.c - Mixed periodic/aperiodic
  • t_schedfb.c - Scheduler feedback test

Run tests:

make qemu
/bin/tests/t_periodic1

Custom Scheduler

To add your own scheduler:

  1. Create kernel/src/process/sched_custom.c

  2. Implement scheduler interface functions

  3. Add to kernel/CMakeLists.txt

  4. Add your scheduler to SCHEDULER_TYPES in kernel/CMakeLists.txt.

  5. Build:

    cmake .. -DSCHEDULER_TYPE=SCHEDULER_CUSTOM
make

Hands-On Exercises

Exercise 1: Observe Scheduling in Action

Goal: See which processes are scheduled and their CPU time.

Program - userspace/bin/sched_observer.c:

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
#include <time.h>

int main() {
    printf("=== Scheduling Observer ===\n");
    printf("Running 3 processes with same priority\n\n");
    
    // Fork 3 child processes
    for (int i = 0; i < 3; i++) {
        pid_t pid = fork();
        
        if (pid == 0) {
            // Child: busy loop with periodic print
            printf("[Child %d, PID %d] Started\n", i, getpid());
            
            for (int j = 0; j < 5; j++) {
                // Simulate work (tight loop)
                volatile int sum = 0;
                for (int k = 0; k < 100000; k++) {
                    sum += k;
                }
                
                printf("[Child %d, PID %d] Iteration %d\n", i, getpid(), j);
            }
            
            printf("[Child %d, PID %d] Done\n", i, getpid());
            exit(0);
        } else if (pid < 0) {
            printf("Fork failed!\n");
            return 1;
        }
    }
    
    // Parent: wait for all children
    printf("[Parent] Waiting for children...\n");
    for (int i = 0; i < 3; i++) {
        wait(NULL);
    }
    printf("[Parent] All children done\n");
    
    return 0;
}

Steps:

  1. Build: make sched_observer
  2. Run: /bin/sched_observer
  3. Observe:
    • Which child prints most often?
    • How is CPU time distributed?
    • Look for interleaved output (context switches)

Exercise 2: Measure Context Switches

Goal: Count how many times your process is rescheduled.

Program - userspace/bin/context_count.c:

#include <stdio.h>
#include <unistd.h>
#include <signal.h>

static volatile int switches = 0;
static volatile int iterations = 0;

void signal_handler(int sig) {
    switches++;
    // Signal indicates process was scheduled
}

int main() {
    printf("=== Context Switch Counter ===\n");
    printf("This process will count context switches\n");
    printf("Use ps to see process switching\n\n");
    
    // Install signal handler
    signal(SIGALRM, signal_handler);
    
    // Set alarm to fire every 100ms
    alarm(1);
    
    // Do work
    for (int i = 0; i < 1000000; i++) {
        iterations++;
        
        // Simulate variable-length computation
        for (volatile int j = 0; j < 100; j++);
    }
    
    printf("Completed %d iterations\n", iterations);
    printf("Estimated context switches: %d\n", switches);
    
    return 0;
}

Advanced: Use /bin/ps to see process status during execution

Exercise 3: Priority-Based Scheduling Test

Goal: Demonstrate how high-priority processes get more CPU time.

Program - userspace/bin/priority_test.c:

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main() {
    printf("=== Priority Scheduling Test ===\n");
    printf("If your kernel has priority scheduling,\n");
    printf("high-priority processes should run more.\n\n");
    
    // Create processes with different priorities
    for (int priority = 0; priority < 3; priority++) {
        pid_t pid = fork();
        
        if (pid == 0) {
            // Child process
            // Try to set priority (if nice() is implemented)
            if (priority > 0) {
                nice(priority * 5);  // Lower priority
            }
            
            printf("[PID %d, Priority %d] Starting work\n", 
                   getpid(), priority);
            
            // Do work
            volatile long sum = 0;
            for (int i = 0; i < 10000000; i++) {
                sum += i;
            }
            
            printf("[PID %d, Priority %d] Finished\n", 
                   getpid(), priority);
            exit(0);
        }
    }
    
    // Parent waits
    for (int i = 0; i < 3; i++) {
        wait(NULL);
    }
    
    printf("Test complete\n");
    return 0;
}

Observation:

  • If priority scheduling works, process 0 (highest priority) finishes first
  • Processes 1 and 2 may take much longer

Exercise 4: Switch Scheduler Algorithm

Goal: Test different scheduling algorithms.

Steps:

  1. Build with Round-Robin:

    cd build
cmake .. -DSCHEDULER_TYPE=SCHEDULER_RR
make
make qemu

  2. Run /bin/sched_observer, observe timing

  3. Rebuild with Priority scheduler:

    cmake .. -DSCHEDULER_TYPE=SCHEDULER_PRIORITY
make
make qemu

  4. Run same test, compare behavior

Analysis:

  • RR: More balanced CPU distribution
  • Priority: High-priority processes get more CPU

Exercise 5: Understand Preemption

Goal: See how preemption works in real-time.

Program - userspace/bin/preemption_demo.c:

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
#include <signal.h>

static volatile int preempted = 0;

void preempt_handler(int sig) {
    preempted++;
    printf("  [Preempted! Count: %d]\n", preempted);
}

int main() {
    printf("=== Preemption Demo ===\n");
    printf("This shows how kernel preempts long-running processes\n\n");
    
    // Install signal to catch preemption
    signal(SIGALRM, preempt_handler);
    alarm(1);  // Signal every second
    
    printf("[PID %d] Starting long computation...\n", getpid());
    printf("Watch how I'm interrupted!\n\n");
    
    // Very long loop with prints
    for (int i = 0; i < 50; i++) {
        printf("Iteration %d\n", i);
        
        // Simulate work
        for (volatile int j = 0; j < 50000000; j++);
        
        sleep(0);  // Yield to other processes
    }
    
    printf("\nDone! Was preempted %d times\n", preempted);
    return 0;
}

Challenge: Implement Fair Queuing

Advanced Goal: Understand how the scheduler maintains fairness

Research:

  1. Read kernel/src/process/scheduler.c to understand current algorithm
  2. Look at process queue management
  3. Challenge: Modify scheduler to prioritize I/O-bound processes
  4. Test with programs that mix computation and I/O

Further Reading

Previous: Debugging | Next: Contributing →

Clone this wiki locally