Scheduling Algorithms in RTOS

Understanding real-time scheduling algorithms, priority-based scheduling, and timing analysis in embedded systems with focus on FreeRTOS implementation and real-time scheduling principles

🎯 Concept → Why it matters → Minimal example → Try it → Takeaways

Concept

Scheduling algorithms are like traffic controllers for your CPU. Instead of letting tasks fight over who gets to run, the scheduler makes intelligent decisions about which task should execute when, ensuring everyone gets their turn and critical tasks don't get stuck in traffic.

Why it matters

In real-time systems, missing a deadline can mean the difference between a safe landing and a crash. Good scheduling ensures that critical tasks (like reading sensors or controlling actuators) always get CPU time when they need it, while less critical tasks (like status updates) wait their turn.

Minimal example

// Task priorities determine execution order
void highPriorityTask(void *pvParameters) {
    while (1) {
        readCriticalSensor();  // Must happen every 10ms
        vTaskDelay(pdMS_TO_TICKS(10));
    }
}

void mediumPriorityTask(void *pvParameters) {
    while (1) {
        processData();         // Can wait a bit
        vTaskDelay(pdMS_TO_TICKS(50));
    }
}

void lowPriorityTask(void *pvParameters) {
    while (1) {
        updateStatusLED();     // Not time-critical
        vTaskDelay(pdMS_TO_TICKS(100));
    }
}

// Create tasks with different priorities
xTaskCreate(highPriorityTask, "High", 128, NULL, 3, NULL);
xTaskCreate(mediumPriorityTask, "Medium", 128, NULL, 2, NULL);
xTaskCreate(lowPriorityTask, "Low", 128, NULL, 1, NULL);

Try it

Experiment: Create tasks with different priorities and observe execution order
Challenge: Design a system where three tasks must meet different deadlines
Debug: Use FreeRTOS hooks to monitor task switching and timing

Takeaways

Good scheduling is about making intelligent trade-offs between urgency, importance, and resource efficiency, ensuring your system meets all its timing requirements.

🎯 Overview

Scheduling algorithms are the heart of real-time operating systems, determining which tasks run when and for how long. Understanding scheduling algorithms is essential for designing embedded systems that can meet real-time requirements, handle multiple concurrent operations, and provide predictable performance under various conditions.

Key Concepts

Scheduling algorithms - Methods for determining task execution order
Priority management - Assigning and managing task priorities
Timing analysis - Analyzing system timing and schedulability
Real-time constraints - Meeting deadline and response time requirements
Resource utilization - Efficient use of system resources

🤔 What are Scheduling Algorithms?

Scheduling algorithms are mathematical methods that determine the order and timing of task execution in a real-time system. They ensure that system resources are used efficiently while meeting real-time constraints such as deadlines and response times.

Core Concepts

Scheduling Purpose:

Resource Allocation: Determine which tasks get CPU time and when
Timing Guarantees: Ensure tasks meet their timing requirements
System Efficiency: Optimize resource utilization and performance
Predictability: Provide predictable system behavior

Scheduling Characteristics:

Preemptive vs Non-preemptive: Whether higher priority tasks can interrupt lower priority ones
Static vs Dynamic: Whether priorities are fixed or can change
Optimal vs Heuristic: Whether the algorithm provides optimal solutions
Complexity: Computational complexity of the scheduling algorithm

Real-Time Requirements:

Hard Real-Time: Missing deadlines causes system failure
Soft Real-Time: Missing deadlines degrades performance
Firm Real-Time: Missing deadlines causes data loss
Mixed Real-Time: Combination of different real-time requirements

Scheduling System Architecture

Basic Scheduling System:

┌─────────────────────────────────────────────────────────────┐
│                    Task Queue                               │
│  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐        │
│  │   Task 1    │  │   Task 2    │  │   Task 3    │        │
│  │ (Priority 3)│  │ (Priority 2)│  │ (Priority 1)│        │
│  └─────────────┘  └─────────────┘  └─────────────┘        │
└─────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────┐
│                    Scheduler                                │
│  ┌─────────────────────────────────────────────────────┐   │
│  │           Scheduling Algorithm                      │   │
│  └─────────────────────────────────────────────────────┘   │
└─────────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────────┐
│                    CPU                                     │
│  ┌─────────────────────────────────────────────────────┐   │
│  │              Currently Running Task                 │   │
│  └─────────────────────────────────────────────────────┘   │
└─────────────────────────────────────────────────────────────┘

Scheduling Decision Process:

┌─────────────────────────────────────────────────────────────┐
│                    Scheduling Cycle                        │
├─────────────────────────────────────────────────────────────┤
│  1. Check for new tasks or priority changes               │
│  2. Evaluate scheduling algorithm criteria                │
│  3. Select next task to run                               │
│  4. Perform context switch if needed                      │
│  5. Execute selected task                                 │
│  6. Monitor task execution and timing                     │
└─────────────────────────────────────────────────────────────┘

🎯 Why is Scheduling Important?

Effective scheduling is crucial for real-time systems because it directly affects system performance, reliability, and ability to meet timing requirements. Poor scheduling can lead to missed deadlines, system failures, and unpredictable behavior.

Real-Time System Requirements

Timing Constraints:

Deadline Compliance: Tasks must complete within specified time limits
Response Time: System must respond to events within required timeframes
Jitter Control: Minimize variation in task execution timing
Predictability: System behavior must be predictable under all conditions

Resource Management:

CPU Utilization: Efficient use of available processing resources
Memory Management: Optimize memory usage across multiple tasks
Power Efficiency: Manage power consumption during task execution
Resource Sharing: Coordinate access to shared resources

System Reliability:

Fault Tolerance: Continue operating despite component failures
Error Recovery: Implement recovery mechanisms for scheduling failures
System Stability: Maintain stability under varying loads
Performance Guarantees: Provide guaranteed performance levels

Scheduling Impact on System Performance

Performance Metrics:

Throughput: Number of tasks completed per unit time
Latency: Time from task ready to task completion
Jitter: Variation in task execution timing
Efficiency: Resource utilization and overhead

Quality of Service:

Real-time Guarantees: Meeting timing requirements
Predictability: Consistent performance under varying conditions
Responsiveness: Quick response to external events
Stability: Maintaining performance over time

🔧 Scheduling Concepts

Task Characteristics

Task Parameters:

Period: Time between consecutive task activations
Deadline: Maximum time allowed for task completion
Execution Time: Time required to complete task execution
Priority: Relative importance of the task
Resource Requirements: Resources needed for task execution

Task Classification:

Periodic Tasks: Tasks that execute at regular intervals
Aperiodic Tasks: Tasks that execute in response to events
Sporadic Tasks: Tasks with minimum inter-arrival times
Critical Tasks: Tasks that must meet strict timing requirements

Scheduling Metrics

Timing Metrics:

Response Time: Time from task arrival to completion
Worst-Case Response Time: Maximum possible response time
Average Response Time: Average response time over multiple executions
Jitter: Variation in response time

Utilization Metrics:

CPU Utilization: Percentage of CPU time used by tasks
Schedulability: Whether all tasks can meet their deadlines
Overhead: Time spent on scheduling decisions and context switches
Efficiency: Ratio of useful work to total time

Scheduling Constraints

System Constraints:

Resource Limitations: Limited CPU, memory, and I/O resources
Timing Requirements: Strict deadline and response time requirements
Precedence Constraints: Dependencies between tasks
Resource Conflicts: Shared resource access requirements

Algorithm Constraints:

Computational Complexity: Time required for scheduling decisions
Memory Requirements: Memory needed for scheduling data structures
Implementation Complexity: Difficulty of implementing the algorithm
Maintenance Requirements: Ongoing maintenance and tuning needs

🚀 Priority-Based Scheduling

Priority Scheduling Fundamentals

Basic Principles:

Priority Assignment: Each task has a numerical priority value
Preemptive Execution: Higher priority tasks can interrupt lower priority ones
Priority Inversion: Low-priority tasks can block high-priority tasks
Priority Inheritance: Tasks inherit priority of resources they access

Priority Assignment Strategies:

Rate Monotonic: Higher frequency tasks get higher priority
Deadline Monotonic: Shorter deadline tasks get higher priority
Value-based: Higher value tasks get higher priority
Application-specific: Custom priority assignment based on requirements

FreeRTOS Priority Implementation

Priority Configuration:

// Priority configuration
#define configMAX_PRIORITIES 32
#define configUSE_PREEMPTION 1
#define configUSE_TIME_SLICING 1
#define configUSE_TICKLESS_IDLE 0

// Priority levels
#define PRIORITY_CRITICAL    5    // System critical tasks
#define PRIORITY_HIGH        4    // High-priority user tasks
#define PRIORITY_NORMAL      3    // Normal operation tasks
#define PRIORITY_LOW         2    // Background tasks
#define PRIORITY_IDLE        1    // Idle tasks

// Task creation with priorities
void vCreateTasks(void) {
    TaskHandle_t xTaskHandle;
    
    // Create critical task with highest priority
    xTaskCreate(
        vCriticalTask,           // Task function
        "Critical",              // Task name
        256,                     // Stack size
        NULL,                    // Parameters
        PRIORITY_CRITICAL,       // Priority
        &xTaskHandle             // Task handle
    );
    
    // Create high priority task
    xTaskCreate(
        vHighPriorityTask,       // Task function
        "High",                  // Task name
        256,                     // Stack size
        NULL,                    // Parameters
        PRIORITY_HIGH,           // Priority
        &xTaskHandle             // Task handle
    );
    
    // Create normal priority task
    xTaskCreate(
        vNormalTask,             // Task function
        "Normal",                // Task name
        256,                     // Stack size
        NULL,                    // Parameters
        PRIORITY_NORMAL,         // Priority
        &xTaskHandle             // Task handle
    );
}

Priority Management:

// Dynamic priority changes
void vPriorityManager(void *pvParameters) {
    TaskHandle_t xManagedTask = (TaskHandle_t)pvParameters;
    UBaseType_t uxCurrentPriority;
    
    while (1) {
        // Get current priority
        uxCurrentPriority = uxTaskPriorityGet(xManagedTask);
        
        // Adjust priority based on system conditions
        if (system_under_load()) {
            // Increase priority under load
            vTaskPrioritySet(xManagedTask, uxCurrentPriority + 1);
        } else {
            // Restore normal priority
            vTaskPrioritySet(xManagedTask, PRIORITY_NORMAL);
        }
        
        vTaskDelay(pdMS_TO_TICKS(1000));
    }
}

// Priority inheritance example
void vResourceTask(void *pvParameters) {
    SemaphoreHandle_t xMutex = (SemaphoreHandle_t)pvParameters;
    
    while (1) {
        // Take mutex (priority inheritance will occur)
        if (xSemaphoreTake(xMutex, portMAX_DELAY) == pdTRUE) {
            // Use shared resource
            vTaskDelay(pdMS_TO_TICKS(100));
            
            // Release mutex
            xSemaphoreGive(xMutex);
        }
        
        vTaskDelay(pdMS_TO_TICKS(1000));
    }
}

Priority Inversion Prevention

Priority Inheritance:

// Priority inheritance mutex
SemaphoreHandle_t xPriorityInheritanceMutex;

void vHighPriorityTask(void *pvParameters) {
    while (1) {
        // Wait for resource
        if (xSemaphoreTake(xPriorityInheritanceMutex, portMAX_DELAY) == pdTRUE) {
            // Critical section
            vTaskDelay(pdMS_TO_TICKS(50));
            
            // Release resource
            xSemaphoreGive(xPriorityInheritanceMutex);
        }
        
        vTaskDelay(pdMS_TO_TICKS(200));
    }
}

void vLowPriorityTask(void *pvParameters) {
    while (1) {
        // Take resource
        if (xSemaphoreTake(xPriorityInheritanceMutex, portMAX_DELAY) == pdTRUE) {
            // Long critical section
            vTaskDelay(pdMS_TO_TICKS(1000));
            
            // Release resource
            xSemaphoreGive(xPriorityInheritanceMutex);
        }
        
        vTaskDelay(pdMS_TO_TICKS(5000));
    }
}

// Initialize priority inheritance mutex
xPriorityInheritanceMutex = xSemaphoreCreateMutex();

⏰ Rate Monotonic Scheduling

Rate Monotonic Principles

Basic Concept:

Priority Assignment: Higher frequency tasks get higher priority
Optimality: Optimal for periodic tasks with deadlines equal to periods
Schedulability: Liu-Layland bound for schedulability analysis
Implementation: Simple priority assignment based on task frequency

Rate Monotonic Analysis:

// Rate Monotonic Schedulability Test
typedef struct {
    uint32_t period;        // Task period in ticks
    uint32_t execution;     // Worst-case execution time
    uint8_t priority;       // Assigned priority
} rms_task_t;

bool rms_schedulability_test(rms_task_t tasks[], uint8_t task_count) {
    double utilization = 0.0;
    
    // Calculate total utilization
    for (uint8_t i = 0; i < task_count; i++) {
        utilization += (double)tasks[i].execution / tasks[i].period;
    }
    
    // Liu-Layland bound for rate monotonic
    double bound = task_count * (pow(2.0, 1.0/task_count) - 1.0);
    
    return utilization <= bound;
}

// Example: Three periodic tasks
rms_task_t rms_tasks[] = {
    {100, 20, 3},   // Task 1: 100ms period, 20ms execution, priority 3
    {200, 40, 2},   // Task 2: 200ms period, 40ms execution, priority 2
    {400, 60, 1}    // Task 3: 400ms period, 60ms execution, priority 1
};

void vRateMonotonicExample(void) {
    uint8_t task_count = sizeof(rms_tasks) / sizeof(rms_tasks[0]);
    
    if (rms_schedulability_test(rms_tasks, task_count)) {
        printf("System is schedulable with Rate Monotonic\n");
    } else {
        printf("System is NOT schedulable with Rate Monotonic\n");
    }
}

Rate Monotonic Implementation

Task Creation with RMS:

// Rate Monotonic task creation
void vCreateRMSTasks(void) {
    // Sort tasks by period (highest frequency = highest priority)
    qsort(rms_tasks, sizeof(rms_tasks)/sizeof(rms_tasks[0]), 
          sizeof(rms_tasks[0]), compare_period);
    
    // Create tasks with RMS priorities
    for (uint8_t i = 0; i < sizeof(rms_tasks)/sizeof(rms_tasks[0]); i++) {
        xTaskCreate(
            vPeriodicTask,                    // Task function
            "RMS_Task",                       // Task name
            256,                              // Stack size
            &rms_tasks[i],                    // Parameters
            rms_tasks[i].priority,            // RMS priority
            NULL                              // Task handle
        );
    }
}

// Periodic task implementation
void vPeriodicTask(void *pvParameters) {
    rms_task_t *task = (rms_task_t*)pvParameters;
    TickType_t xLastWakeTime;
    
    // Initialize the xLastWakeTime variable with the current time
    xLastWakeTime = xTaskGetTickCount();
    
    while (1) {
        // Perform task work
        vTaskWork(task);
        
        // Wait for next period
        vTaskDelayUntil(&xLastWakeTime, pdMS_TO_TICKS(task->period));
    }
}

// Task work function
void vTaskWork(rms_task_t *task) {
    printf("Task with period %lu executing for %lu ms\n", 
           task->period, task->execution);
    
    // Simulate work
    vTaskDelay(pdMS_TO_TICKS(task->execution));
}

⏱️ Earliest Deadline First

EDF Principles

Basic Concept:

Dynamic Priority: Task priority changes based on current deadline
Optimality: Optimal for preemptive scheduling of independent tasks
Schedulability: 100% CPU utilization possible
Complexity: More complex than fixed priority scheduling

EDF Schedulability Test:

// EDF Schedulability Test
bool edf_schedulability_test(rms_task_t tasks[], uint8_t task_count) {
    double utilization = 0.0;
    
    // Calculate total utilization
    for (uint8_t i = 0; i < task_count; i++) {
        utilization += (double)tasks[i].execution / tasks[i].period;
    }
    
    // EDF bound is 100% for independent tasks
    return utilization <= 1.0;
}

// EDF task structure with deadlines
typedef struct {
    uint32_t period;        // Task period
    uint32_t execution;     // Worst-case execution time
    uint32_t deadline;      // Task deadline
    uint32_t next_deadline; // Next deadline time
} edf_task_t;

// EDF priority calculation
uint32_t edf_calculate_priority(edf_task_t *task) {
    // Lower deadline = higher priority
    return task->next_deadline;
}

EDF Implementation

EDF Scheduler:

// EDF scheduler implementation
void vEDFScheduler(void *pvParameters) {
    edf_task_t *tasks = (edf_task_t*)pvParameters;
    uint8_t task_count = sizeof(tasks) / sizeof(tasks[0]);
    uint8_t highest_priority_task = 0;
    
    while (1) {
        // Find task with earliest deadline
        uint32_t earliest_deadline = UINT32_MAX;
        
        for (uint8_t i = 0; i < task_count; i++) {
            if (tasks[i].next_deadline < earliest_deadline) {
                earliest_deadline = tasks[i].next_deadline;
                highest_priority_task = i;
            }
        }
        
        // Execute highest priority task
        vExecuteTask(&tasks[highest_priority_task]);
        
        // Update deadlines for completed tasks
        tasks[highest_priority_task].next_deadline += tasks[highest_priority_task].period;
        
        vTaskDelay(pdMS_TO_TICKS(1));
    }
}

// Task execution function
void vExecuteTask(edf_task_t *task) {
    printf("Executing EDF task with deadline %lu\n", task->next_deadline);
    
    // Simulate task execution
    vTaskDelay(pdMS_TO_TICKS(task->execution));
}

🔄 Round Robin Scheduling

Round Robin Principles

Basic Concept:

Time Slicing: Each task gets a fixed time quantum
Fairness: Equal CPU time distribution among equal priority tasks
Preemption: Tasks are preempted when time quantum expires
Overhead: Context switching overhead affects performance

Time Quantum Selection:

// Time quantum configuration
#define TIME_QUANTUM_MS 10    // 10ms time quantum
#define TASK_SLICE_TICKS pdMS_TO_TICKS(TIME_QUANTUM_MS)

// Round Robin task structure
typedef struct {
    uint8_t priority;         // Task priority
    uint32_t time_remaining;  // Remaining time in current quantum
    bool is_running;          // Whether task is currently running
} rr_task_t;

// Round Robin scheduler
void vRoundRobinScheduler(void *pvParameters) {
    rr_task_t *tasks = (rr_task_t*)pvParameters;
    uint8_t task_count = sizeof(tasks) / sizeof(tasks[0]);
    uint8_t current_task = 0;
    
    while (1) {
        // Find next ready task with same priority
        uint8_t next_task = (current_task + 1) % task_count;
        
        // Check if next task has same priority and is ready
        if (tasks[next_task].priority == tasks[current_task].priority &&
            tasks[next_task].is_running) {
            current_task = next_task;
        }
        
        // Execute current task for time quantum
        vExecuteTaskRR(&tasks[current_task], TASK_SLICE_TICKS);
        
        vTaskDelay(pdMS_TO_TICKS(1));
    }
}

FreeRTOS Round Robin

Time Slicing Configuration:

// FreeRTOS time slicing configuration
#define configUSE_TIME_SLICING 1
#define configIDLE_SHOULD_YIELD 1

// Round Robin task creation
void vCreateRoundRobinTasks(void) {
    // Create tasks with same priority for Round Robin
    for (uint8_t i = 0; i < 3; i++) {
        xTaskCreate(
            vRoundRobinTask,              // Task function
            "RR_Task",                    // Task name
            256,                          // Stack size
            (void*)i,                     // Task number
            2,                           // Same priority for all tasks
            NULL                          // Task handle
        );
    }
}

// Round Robin task implementation
void vRoundRobinTask(void *pvParameters) {
    uint8_t task_number = (uint8_t)pvParameters;
    
    while (1) {
        printf("Round Robin Task %d executing\n", task_number);
        
        // Simulate work
        vTaskDelay(pdMS_TO_TICKS(100));
        
        // Yield to other tasks (optional with time slicing)
        taskYIELD();
    }
}

📊 Scheduling Analysis

Response Time Analysis

Basic RTA:

// Response Time Analysis for fixed priority scheduling
typedef struct {
    uint32_t period;        // Task period
    uint32_t execution;     // Worst-case execution time
    uint8_t priority;       // Task priority
    uint32_t response_time; // Calculated response time
} rta_task_t;

uint32_t calculate_response_time(rta_task_t *task, rta_task_t tasks[], uint8_t task_count) {
    uint32_t response_time = task->execution;
    uint32_t interference = 0;
    bool converged = false;
    uint32_t iterations = 0;
    
    while (!converged && iterations < 100) {
        interference = 0;
        
        // Calculate interference from higher priority tasks
        for (uint8_t i = 0; i < task_count; i++) {
            if (tasks[i].priority > task->priority) {
                interference += ceil((double)response_time / tasks[i].period) * tasks[i].execution;
            }
        }
        
        uint32_t new_response_time = task->execution + interference;
        
        if (new_response_time == response_time) {
            converged = true;
        } else {
            response_time = new_response_time;
        }
        
        iterations++;
    }
    
    return response_time;
}

// RTA example
void vResponseTimeAnalysis(void) {
    rta_task_t tasks[] = {
        {100, 20, 3, 0},   // High priority
        {200, 40, 2, 0},   // Medium priority
        {400, 60, 1, 0}    // Low priority
    };
    
    uint8_t task_count = sizeof(tasks) / sizeof(tasks[0]);
    
    // Calculate response times
    for (uint8_t i = 0; i < task_count; i++) {
        tasks[i].response_time = calculate_response_time(&tasks[i], tasks, task_count);
        printf("Task %d: Response time = %lu ms\n", i, tasks[i].response_time);
    }
}

Schedulability Testing

Utilization Bound Testing:

// Utilization bound testing
bool test_utilization_bound(rta_task_t tasks[], uint8_t task_count) {
    double total_utilization = 0.0;
    
    // Calculate total utilization
    for (uint8_t i = 0; i < task_count; i++) {
        total_utilization += (double)tasks[i].execution / tasks[i].period;
    }
    
    // Rate Monotonic bound
    double rms_bound = task_count * (pow(2.0, 1.0/task_count) - 1.0);
    
    // EDF bound
    double edf_bound = 1.0;
    
    printf("Total utilization: %.3f\n", total_utilization);
    printf("RMS bound: %.3f\n", rms_bound);
    printf("EDF bound: %.3f\n", edf_bound);
    
    return total_utilization <= rms_bound;
}

⚙️ FreeRTOS Scheduler

Scheduler Configuration

Basic Configuration:

// FreeRTOS scheduler configuration
#define configUSE_PREEMPTION           1
#define configUSE_TIME_SLICING         1
#define configUSE_TICKLESS_IDLE        0
#define configUSE_IDLE_HOOK            0
#define configUSE_TICK_HOOK            0
#define configCPU_CLOCK_HZ             16000000
#define configTICK_RATE_HZ             1000
#define configMAX_PRIORITIES           32
#define configMINIMAL_STACK_SIZE       128
#define configMAX_TASK_NAME_LEN        16
#define configUSE_16_BIT_TICKS         0
#define configIDLE_SHOULD_YIELD        1
#define configUSE_MUTEXES              1
#define configUSE_RECURSIVE_MUTEXES    0
#define configUSE_COUNTING_SEMAPHORES  1
#define configUSE_ALTERNATIVE_API      0
#define configCHECK_FOR_STACK_OVERFLOW 2
#define configUSE_MALLOC_FAILED_HOOK   1
#define configUSE_APPLICATION_TASK_TAG 0
#define configUSE_QUEUE_SETS           1
#define configUSE_TASK_NOTIFICATIONS   1
#define configSUPPORT_STATIC_ALLOCATION 1
#define configSUPPORT_DYNAMIC_ALLOCATION 1

Scheduler Hooks:

// Scheduler hooks
void vApplicationIdleHook(void) {
    // Called when idle task runs
    // Can be used for power management
    __WFI();  // Wait for interrupt
}

void vApplicationTickHook(void) {
    // Called every tick
    // Can be used for periodic operations
    static uint32_t tick_count = 0;
    tick_count++;
    
    if (tick_count % 1000 == 0) {
        // Every 1000 ticks
        printf("System running for %lu seconds\n", tick_count / 1000);
    }
}

void vApplicationMallocFailedHook(void) {
    // Called when malloc fails
    printf("Memory allocation failed!\n");
    
    // Handle memory allocation failure
    // Could restart system or free memory
}

void vApplicationStackOverflowHook(TaskHandle_t xTask, char *pcTaskName) {
    // Called when stack overflow detected
    printf("Stack overflow in task: %s\n", pcTaskName);
    
    // Handle stack overflow
    // Could restart system or task
}

Scheduler Control

Scheduler Control Functions:

// Scheduler control
void vSchedulerControl(void *pvParameters) {
    while (1) {
        // Suspend scheduler
        vTaskSuspendAll();
        
        // Perform critical operations
        vCriticalOperation();
        
        // Resume scheduler
        xTaskResumeAll();
        
        vTaskDelay(pdMS_TO_TICKS(1000));
    }
}

// Critical operation
void vCriticalOperation(void) {
    // Operations that must not be interrupted
    printf("Performing critical operation...\n");
    
    // Simulate critical work
    for (volatile uint32_t i = 0; i < 1000000; i++) {
        // Critical work
    }
    
    printf("Critical operation completed\n");
}

🚀 Implementation

Complete Scheduling System

System Initialization:

// System initialization with scheduling
void vSystemInit(void) {
    // Create system tasks with different priorities
    xTaskCreate(vSystemMonitorTask, "SysMon", 256, NULL, 5, NULL);
    xTaskCreate(vCommunicationTask, "Comm", 512, NULL, 4, NULL);
    xTaskCreate(vDataProcessingTask, "DataProc", 1024, NULL, 3, NULL);
    xTaskCreate(vBackgroundTask, "Background", 128, NULL, 2, NULL);
    xTaskCreate(vIdleTask, "Idle", 64, NULL, 1, NULL);
    
    // Start scheduler
    vTaskStartScheduler();
}

// Main function
int main(void) {
    // Hardware initialization
    SystemInit();
    HAL_Init();
    
    // Initialize peripherals
    MX_GPIO_Init();
    MX_USART1_UART_Init();
    
    // Initialize system
    vSystemInit();
    
    // Should never reach here
    while (1) {
        // Error handling
    }
}

⚠️ Common Pitfalls

Priority Inversion

Common Scenarios:

Resource Contention: Low-priority task holds resource needed by high-priority task
Nested Locks: Multiple mutexes acquired in wrong order
Long Critical Sections: Extended periods with interrupts disabled

Solutions:

Priority Inheritance: Automatically raise task priority when holding resource
Priority Ceiling: Assign priority ceiling to resources
Resource Ordering: Always acquire resources in consistent order
Timeout Handling: Use timeouts to prevent indefinite blocking

Scheduling Overhead

Overhead Sources:

Context Switching: Time to save and restore task context
Scheduling Decisions: Time to make scheduling decisions
Interrupt Handling: Time to handle scheduling-related interrupts
Memory Management: Time for memory allocation and deallocation

Optimization Strategies:

Minimize Context Switches: Reduce unnecessary task switching
Optimize Critical Paths: Focus optimization on time-critical sections
Use Hardware Features: Leverage hardware acceleration when available
Profile and Measure: Use profiling tools to identify bottlenecks

Memory Fragmentation

Fragmentation Causes:

Variable Allocation Sizes: Different sized memory blocks
Frequent Allocation/Deallocation: Memory churn
No Memory Compaction: Fragmented memory not reclaimed

Mitigation:

Memory Pools: Use fixed-size memory pools
Static Allocation: Pre-allocate memory when possible
Memory Defragmentation: Periodically compact memory
Garbage Collection: Automatic memory management

✅ Best Practices

Scheduling Design Principles

Priority Assignment:

Clear Priority Hierarchy: Establish clear priority levels
Consistent Assignment: Use consistent priority assignment strategy
Documentation: Document priority assignment rationale
Review and Update: Regularly review and update priorities

Task Design:

Single Responsibility: Each task should have one primary function
Clear Interface: Well-defined input/output interfaces
Minimal Dependencies: Reduce coupling between tasks
Error Handling: Robust error handling within tasks

Performance Optimization

Scheduling Efficiency:

Minimize Overhead: Reduce scheduling decision overhead
Optimize Context Switches: Minimize context switch time
Use Appropriate Algorithms: Choose algorithms based on requirements
Monitor Performance: Continuously monitor scheduling performance

Resource Management:

Efficient Allocation: Minimize resource allocation overhead
Resource Sharing: Use appropriate synchronization mechanisms
Cleanup: Properly clean up resources when tasks terminate
Monitoring: Monitor resource usage and availability

🔬 Guided Labs

Lab 1: Priority-Based Scheduling

Objective: Understand how task priorities affect execution order Steps:

Create three tasks with different priorities (1, 2, 3)
Each task toggles a different GPIO pin
Use oscilloscope to observe execution patterns
Change priorities and observe the difference

Expected Outcome: Higher priority tasks get more CPU time and execute more frequently

Lab 2: Rate Monotonic Scheduling

Objective: Implement and observe RMS behavior Steps:

Create tasks with different periods (10ms, 20ms, 50ms)
Assign priorities based on frequency (higher frequency = higher priority)
Monitor task execution and timing
Verify that all deadlines are met

Expected Outcome: All tasks meet their deadlines with proper priority assignment

Lab 3: Scheduling Performance Measurement

Objective: Measure scheduling overhead and performance Steps:

Use GPIO to measure context switch time
Monitor CPU utilization under different loads
Measure worst-case response time
Profile scheduling algorithm performance

Expected Outcome: Understanding of scheduling overhead and optimization opportunities

✅ Check Yourself

Understanding Check

Can you explain why preemptive scheduling is better for real-time systems?
Do you understand the difference between RMS and EDF scheduling?
Can you identify when priority inversion occurs?
Do you know how to determine if a system is schedulable?

Practical Skills Check

Can you set up tasks with different priorities in FreeRTOS?
Do you know how to debug scheduling issues?
Can you implement proper priority management?
Do you understand how to measure scheduling performance?

Advanced Concepts Check

Can you explain response time analysis?
Do you understand how to optimize scheduling algorithms?
Can you implement custom scheduling policies?
Do you know how to handle resource contention in scheduling?

🔗 Cross-links

Prerequisites

C Language Fundamentals - Basic programming concepts
Task Creation and Management - Understanding tasks
GPIO Configuration - Basic I/O setup

Next Steps

Interrupt Handling - How interrupts affect scheduling
Real-Time Debugging - Debugging scheduling issues
Response Time Analysis - Analyzing task timing

📋 Quick Reference: Key Facts

Scheduling Fundamentals

Purpose: Determine which task runs when and for how long
Types: Preemptive, non-preemptive, static, dynamic
Characteristics: Priority-based, deadline-aware, resource-efficient
Benefits: Predictable timing, efficient resource usage, real-time guarantees

Priority-Based Scheduling

High Priority: Critical tasks that must meet strict deadlines
Medium Priority: Normal system operations and data processing
Low Priority: Background tasks and status updates
Priority Assignment: Based on criticality, frequency, and deadline requirements

Common Scheduling Algorithms

Rate Monotonic (RMS): Fixed priorities based on task frequency
Earliest Deadline First (EDF): Dynamic priorities based on current deadlines
Round Robin: Equal priority tasks share CPU time equally
Priority Preemptive: Higher priority tasks can interrupt lower ones

Scheduling Analysis

Utilization Bound: Maximum CPU utilization for schedulability
Response Time Analysis: Calculate worst-case response times
Deadline Miss: When tasks cannot meet their timing requirements
Schedulability Test: Determine if system can meet all deadlines

❓ Interview Questions

Basic Concepts

What is the difference between preemptive and non-preemptive scheduling?
- Preemptive: Higher priority tasks can interrupt lower priority ones
- Non-preemptive: Tasks run until completion or voluntary yield
- Preemptive provides better responsiveness but more overhead
How do you determine if a system is schedulable?
- Use utilization bound tests (RMS, EDF)
- Perform response time analysis
- Consider system constraints and requirements
- Test with worst-case scenarios
What is priority inversion and how do you prevent it?
- Low-priority task blocks high-priority task
- Use priority inheritance or priority ceiling
- Order resource acquisition consistently
- Use timeout mechanisms

Advanced Topics

Explain the differences between Rate Monotonic and EDF scheduling.
- RMS: Fixed priorities based on task frequency
- EDF: Dynamic priorities based on current deadlines
- RMS: Simpler but less optimal
- EDF: More complex but optimal
How do you analyze the worst-case response time of a task?
- Use response time analysis (RTA)
- Calculate interference from higher priority tasks
- Consider blocking from shared resources
- Iterate until convergence
What strategies do you use for scheduling optimization?
- Minimize context switch overhead
- Optimize critical execution paths
- Use appropriate memory management
- Leverage hardware features

Practical Scenarios

Design a scheduling system for a real-time control application.
- Define task priorities and timing requirements
- Choose appropriate scheduling algorithm
- Implement priority management
- Handle resource sharing and synchronization
How would you debug scheduling issues in an RTOS?
- Use scheduling hooks and monitoring
- Analyze task states and priorities
- Check for priority inversion
- Monitor system performance
Explain how to implement a custom scheduling algorithm.
- Define scheduling criteria and policies
- Implement priority calculation
- Handle task selection and execution
- Integrate with RTOS framework

This enhanced Scheduling Algorithms document now provides a comprehensive balance of conceptual explanations, practical insights, and technical implementation details that embedded engineers can use to understand and implement robust RTOS scheduling systems.

FilesExpand file tree

Scheduling_Algorithms.md

Latest commit

History

Scheduling_Algorithms.md

File metadata and controls

Scheduling Algorithms in RTOS

🎯 Concept → Why it matters → Minimal example → Try it → Takeaways

Concept

Why it matters

Minimal example

Try it

Takeaways

📋 Table of Contents

🎯 Overview

Key Concepts

🤔 What are Scheduling Algorithms?

Core Concepts

Scheduling System Architecture

🎯 Why is Scheduling Important?

Real-Time System Requirements

Scheduling Impact on System Performance

🔧 Scheduling Concepts

Task Characteristics

Scheduling Metrics

Scheduling Constraints

🚀 Priority-Based Scheduling

Priority Scheduling Fundamentals

FreeRTOS Priority Implementation

Priority Inversion Prevention

⏰ Rate Monotonic Scheduling

Rate Monotonic Principles

Rate Monotonic Implementation

⏱️ Earliest Deadline First

EDF Principles

EDF Implementation

🔄 Round Robin Scheduling

Round Robin Principles

FreeRTOS Round Robin

📊 Scheduling Analysis

Response Time Analysis

Schedulability Testing

⚙️ FreeRTOS Scheduler

Scheduler Configuration

Scheduler Control

🚀 Implementation

Complete Scheduling System

⚠️ Common Pitfalls

Priority Inversion

Scheduling Overhead

Memory Fragmentation

✅ Best Practices

Scheduling Design Principles

Performance Optimization

🔬 Guided Labs

Lab 1: Priority-Based Scheduling

Lab 2: Rate Monotonic Scheduling

Lab 3: Scheduling Performance Measurement

✅ Check Yourself

Understanding Check

Practical Skills Check

Advanced Concepts Check

🔗 Cross-links

Related Topics

Prerequisites

Next Steps

📋 Quick Reference: Key Facts

Scheduling Fundamentals

Priority-Based Scheduling

Common Scheduling Algorithms

Scheduling Analysis

❓ Interview Questions

Basic Concepts

Advanced Topics

Practical Scenarios