Preemptive scheduling behavior in FreeRTOS - Time & Space Complexity

Time Complexity: Preemptive scheduling behavior

O(1)

Understanding Time Complexity

When FreeRTOS uses preemptive scheduling, tasks can be paused and resumed based on priority.

We want to understand how the time spent switching tasks grows as more tasks run.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void vTask1(void *pvParameters) {
    for(;;) {
        // Task 1 work
        vTaskDelay(10);
    }
}

void vTask2(void *pvParameters) {
    for(;;) {
        // Task 2 work
        vTaskDelay(5);
    }
}

int main() {
    xTaskCreate(vTask1, "Task1", 1000, NULL, 2, NULL);
    xTaskCreate(vTask2, "Task2", 1000, NULL, 3, NULL);
    vTaskStartScheduler();
    return 0;
}
    

This code creates two tasks with different priorities and starts the scheduler that switches between them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The scheduler repeatedly selects the highest priority ready task.
• How many times: The selection happens on each potential context switch (timer tick, delay end, etc.).

How Execution Grows With Input

As the number of tasks increases, the scheduler selects the next task in constant time using an array of ready lists per priority level (fixed small number of priorities).

Input Size (number of tasks)	Time per Scheduling Decision
2	O(1) - checks priority lists
10	O(1) - same, independent of tasks
100	O(1) - scans at most configMAX_PRIORITIES (~32)

Pattern observation: Scheduling decision time is constant (O(1)) regardless of number of tasks, as it doesn't scan all tasks.

Final Time Complexity

Time Complexity: O(1)

This means the time the scheduler spends deciding which task to run is constant with respect to the number of tasks.

Common Mistake

[X] Wrong: "The scheduler must check all tasks linearly, so O(n)."

[OK] Correct: FreeRTOS uses an array of lists (one per priority level, constant size), finds highest non-empty list in O(1) time.

Interview Connect

Understanding scheduler efficiency (O(1) selection) shows knowledge of real-time OS design and why FreeRTOS scales well with many tasks.

Self-Check

"What if the scheduler used a single priority queue for all tasks instead of per-priority lists? How would the time complexity change?"