Scheduling

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:

1. Timer interrupt (every 10ms)
2. Process blocks (waiting for I/O, sleep, etc.)
3. Process exits
4. 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:

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

2. Implement scheduler interface functions

3. Add to kernel/CMakeLists.txt

4. Add CMake option in root CMakeLists.txt:

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

5. Build:

   cmake .. -DSCHEDULER_TYPE=SCHEDULER_CUSTOM
   make

Further Reading

• Linux Scheduler Documentation
• Real-Time Scheduling
• Process Management - Process lifecycle
• Development Guide - Implementing features

---

Previous: Features | Next: Contributing →