Scheduling

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: 10ms (configurable in code)

2. Priority-Based Scheduler

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

Algorithm:

Each process has a priority (0 = highest, 139 = lowest)
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 red-black tree for efficient selection

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.sched_deadline = 1000;  // 1000ms deadline
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.sched_period = 100;  // 100ms period
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_init(void);

// Pick next task to run
task_struct *scheduler_pick_next(void);

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

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

// Handle timer tick
void scheduler_tick(void);

Scheduler Location

Source: kernel/src/process/scheduler.c
Header: kernel/inc/process/scheduler.h
Algorithm implementations: kernel/src/process/sched_*.c

Context Switch

Scheduler is invoked on:

Timer interrupt (every 10ms)
Process blocks (waiting for I/O, sleep, etc.)
Process exits
Process yields (explicit sched_yield())

Context switch process:

// Save current process state
save_context(current_task);

// Pick next task
next_task = scheduler_pick_next();

// Restore next task state
restore_context(next_task);

// Update current task pointer
current_task = next_task;

Scheduler Configuration

Time Quantum

Change time slice for RR scheduler:

// kernel/src/process/scheduler.c
#define SCHEDULER_QUANTUM_MS 10  // Change to desired value

Priority Ranges

Modify priority ranges:

// kernel/inc/process/scheduler.h
#define MAX_RT_PRIO   100  // Real-time priorities: 0-99
#define MAX_PRIO      140  // Total priorities: 0-139

CFS Parameters

Tune CFS behavior:

// kernel/src/process/sched_cfs.c
#define CFS_MIN_GRANULARITY_MS  10    // Minimum time slice
#define CFS_LATENCY_MS         100    // Target latency

Performance Metrics

Measuring Scheduler Performance

// In kernel code
uint64_t start = read_tsc();
scheduler_pick_next();
uint64_t end = read_tsc();
pr_debug("Scheduler overhead: %llu cycles\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

// From userspace
cat /proc/<pid>/status

Trace Context Switches

Enable tracing:

cmake .. -DENABLE_SCHED_TRACE=ON
make

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:

Create kernel/src/process/sched_custom.c
Implement scheduler interface functions
Add to kernel/CMakeLists.txt

Add CMake option in root CMakeLists.txt:

set(SCHEDULER_TYPE "SCHEDULER_CUSTOM" CACHE STRING "Scheduler type")

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:

Build: make sched_observer
Run: /bin/sched_observer
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:

Build with Round-Robin:

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

Run /bin/sched_observer, observe timing

Rebuild with Priority scheduler:

cmake .. -DSCHEDULER_TYPE=SCHEDULER_PRIORITY
make
make qemu

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:

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

Uh oh!

Scheduling

Scheduling

Overview

Available Schedulers

1. Round-Robin (RR)

2. Priority-Based Scheduler

3. Completely Fair Scheduler (CFS)

4. Earliest Deadline First (EDF)

5. Rate Monotonic (RM)

6. Adaptive Earliest Deadline First (AEDF)

Comparison Table

Choosing a Scheduler

Use RR when

Use Priority when

Use CFS when

Use EDF when

Use RM when

Use AEDF when

Implementation Details

Scheduler Interface

Scheduler Location

Context Switch

Scheduler Configuration

Time Quantum

Priority Ranges

CFS Parameters

Performance Metrics

Measuring Scheduler Performance

Typical Overheads

Debugging Schedulers

Enable Scheduler Logging

Monitor Process States

Trace Context Switches

Testing Schedulers

Custom Scheduler

Hands-On Exercises

Exercise 1: Observe Scheduling in Action

Exercise 2: Measure Context Switches

Exercise 3: Priority-Based Scheduling Test

Exercise 4: Switch Scheduler Algorithm

Exercise 5: Understand Preemption

Challenge: Implement Fair Queuing

Further Reading

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Clone this wiki locally