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?"

Practice

1. In FreeRTOS, what does a higher priority number mean for a task?

easy

A. The task runs before lower priority tasks

B. The task runs after lower priority tasks

C. The task runs at the same time as lower priority tasks

D. The task is ignored by the scheduler

Solution

1. Step 1: Understand priority numbering

   In FreeRTOS, priority numbers start at 0 for the lowest priority and increase for higher priorities.

2. Step 2: Relate priority to task execution

   Higher priority tasks are scheduled to run before lower priority tasks to ensure responsiveness.

3. Final Answer:

   The task runs before lower priority tasks -> Option A

4. Quick Check:

   Higher priority number = runs first [OK]

Hint: Higher number means higher priority and runs first [OK]

Common Mistakes:

• Thinking higher number means lower priority
• Assuming tasks run simultaneously regardless of priority
• Confusing priority with task creation order

2. Which of the following is the correct way to define the highest priority in FreeRTOS if configMAX_PRIORITIES is 5?

easy

A. 5

B. 6

C. 4

D. 0

Solution

1. Step 1: Understand priority range

   Priority numbers start at 0 and go up to configMAX_PRIORITIES - 1.

2. Step 2: Calculate highest priority

   With configMAX_PRIORITIES = 5, highest priority is 5 - 1 = 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Highest priority = configMAX_PRIORITIES - 1 = 4 [OK]

Hint: Highest priority = configMAX_PRIORITIES minus one [OK]

Common Mistakes:

• Using configMAX_PRIORITIES as highest priority directly
• Using 0 as highest priority
• Choosing a number outside the allowed range

3. Given three tasks with priorities 2, 4, and 1, which task will FreeRTOS schedule to run first?

medium

A. Task with priority 4

B. Task with priority 2

C. Task with priority 1

D. All run simultaneously

Solution

1. Step 1: Identify task priorities

   Tasks have priorities 2, 4, and 1 respectively.

2. Step 2: Determine highest priority

   Priority 4 is the highest number, so that task runs first.

3. Final Answer:

   Task with priority 4 -> Option A

4. Quick Check:

   Highest priority runs first = 4 [OK]

Hint: Task with highest priority number runs first [OK]

Common Mistakes:

• Choosing the lowest priority task
• Assuming tasks run in creation order
• Thinking tasks run simultaneously

4. What is wrong with this priority assignment if configMAX_PRIORITIES is 3?
vTaskPrioritySet(taskHandle, 3);

medium

A. Priority 3 is valid and highest

B. Priority 3 is out of range; max is 2

C. Priority must be zero

D. Priority must be negative

Solution

1. Step 1: Check allowed priority range

   Priorities go from 0 to configMAX_PRIORITIES - 1, so 0 to 2 here.

2. Step 2: Validate assigned priority

   Priority 3 is outside this range and invalid.

3. Final Answer:

   Priority 3 is out of range; max is 2 -> Option B

4. Quick Check:

   Max priority = 2, 3 is invalid [OK]

Hint: Priority must be less than configMAX_PRIORITIES [OK]

Common Mistakes:

• Using configMAX_PRIORITIES as a valid priority
• Assigning negative priorities
• Assuming priority zero is highest

5. You have tasks with priorities 0, 1, and 2. You want the system to always run the task with priority 1 before the others, but currently priority 2 runs first. How can you fix this using FreeRTOS priority numbering?

hard

A. Set all tasks to priority 0

B. Set the task currently at 1 to priority 0

C. Set the task currently at 2 to priority 0

D. Set the priority of the task currently at 1 to 3 and others lower

Solution

1. Step 1: Understand current priorities

   Task with priority 2 runs first because it has highest priority.

2. Step 2: Adjust priorities to reorder execution

   Increase the priority of the task currently at 1 to a number higher than 2 (e.g., 3) so it runs first.

3. Step 3: Lower other tasks' priorities

   Set other tasks to lower priorities to ensure the desired task runs first.

4. Final Answer:

   Set the priority of the task currently at 1 to 3 and others lower -> Option D

5. Quick Check:

   Higher priority number runs first, so raise desired task's priority [OK]

Hint: Raise desired task priority above others to run first [OK]

Common Mistakes:

• Lowering all priorities to zero
• Not increasing the desired task's priority
• Assuming priority 0 is highest