The Embedded New Testament

The "Holy Bible" for embedded engineers

---

Project maintained by theEmbeddedGeorge Hosted on GitHub Pages — Theme by mattgraham

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.

---

📋 Table of Contents

• Overview
• What are Scheduling Algorithms?
• Why is Scheduling Important?
• Scheduling Concepts
• Priority-Based Scheduling
• Rate Monotonic Scheduling
• Earliest Deadline First
• Round Robin Scheduling
• Scheduling Analysis
• FreeRTOS Scheduler
• Implementation
• Common Pitfalls
• Best Practices
• Interview Questions

---

🎯 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:

1. Create three tasks with different priorities (1, 2, 3)
2. Each task toggles a different GPIO pin
3. Use oscilloscope to observe execution patterns
4. 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:

1. Create tasks with different periods (10ms, 20ms, 50ms)
2. Assign priorities based on frequency (higher frequency = higher priority)
3. Monitor task execution and timing
4. 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:

1. Use GPIO to measure context switch time
2. Monitor CPU utilization under different loads
3. Measure worst-case response time
4. 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

Related Topics

• FreeRTOS Basics - Understanding the RTOS context
• Task Creation and Management - How tasks are created and managed
• Kernel Services - Services that support scheduling
• Performance Monitoring - Measuring scheduling performance

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

1. 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
2. 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
3. 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

1. 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
2. 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
3. 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

1. 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
2. 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
3. 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.