Priority numbering in FreeRTOS - Time & Space Complexity

Time Complexity: Priority numbering in FreeRTOS

O(1)

Understanding Time Complexity

When working with FreeRTOS, tasks have priorities that affect how the system runs them.

We want to understand how the priority numbering impacts the time it takes to pick the next task to run.

Scenario Under Consideration

Analyze the time complexity of selecting the highest priority ready task.

// Assume configMAX_PRIORITIES = 5
TaskHandle_t xTaskToRun = NULL;
for (int priority = configMAX_PRIORITIES - 1; priority >= 0; priority--) {
    if (uxListLength(&pxReadyTasksLists[priority]) > 0) {
        xTaskToRun = listGET_OWNER_OF_HEAD_ENTRY(&pxReadyTasksLists[priority]);
        break;
    }
}
// xTaskToRun is the highest priority ready task
    

This code checks task lists from highest to lowest priority to find a ready task to run.

Identify Repeating Operations

We look at the loop that checks each priority level.

• Primary operation: Loop through priority levels to find a ready task.
• How many times: Up to configMAX_PRIORITIES times, which is a fixed number.

How Execution Grows With Input

The number of priorities is fixed and small, so the loop runs a few times at most.

Input Size (configMAX_PRIORITIES)	Approx. Operations
5	Up to 5 checks
10	Up to 10 checks
100	Up to 100 checks

Pattern observation: The work grows linearly with the number of priority levels, but this number is usually small and fixed.

Final Time Complexity

Time Complexity: O(1)

This means the time to find the highest priority task does not grow with the number of tasks, only with the fixed number of priority levels.

Common Mistake

[X] Wrong: "The time to pick the next task grows with the total number of tasks in the system."

[OK] Correct: The scheduler only checks priority lists, which are fixed in number, not all tasks individually.

Interview Connect

Understanding how FreeRTOS uses priority numbering helps you explain how real-time systems keep scheduling fast and predictable.

Self-Check

"What if the number of priority levels was not fixed but grew with the number of tasks? How would the time complexity change?"