Task priority assignment in FreeRTOS - Time & Space Complexity

Time Complexity: Task priority assignment

O(1)

Understanding Time Complexity

When assigning priorities to tasks in FreeRTOS, it is important to understand how the time to assign or change priorities grows as the number of tasks increases.

We want to know how the system handles priority changes as more tasks are added.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void vSetTaskPriority(TaskHandle_t xTask, UBaseType_t uxNewPriority) {
    taskENTER_CRITICAL();
    if (uxNewPriority != uxTaskPriorityGet(xTask)) {
        vTaskPrioritySet(xTask, uxNewPriority);
        vTaskPriorityInherit(xTask);
    }
    taskEXIT_CRITICAL();
}

This code changes the priority of a given task if the new priority is different from the current one, protecting the operation with a critical section.

Identify Repeating Operations

• Primary operation: The function vTaskPrioritySet internally may traverse the ready task lists to move the task to the correct priority list.
• How many times: It depends on the number of priority levels and tasks in those lists, but typically it involves a constant number of steps per priority level.

How Execution Grows With Input

As the number of tasks increases, the time to update priority involves moving the task between lists, which depends on the number of priority levels, not directly on total tasks.

Input Size (number of tasks)	Approx. Operations
10	Few steps to update priority list
100	Still a few steps, mostly constant
1000	Same few steps, does not grow with tasks

Pattern observation: The time to assign priority stays mostly the same even as tasks increase.

Final Time Complexity

Time Complexity: O(1)

This means changing a task's priority takes about the same time no matter how many tasks exist.

Common Mistake

[X] Wrong: "Changing a task's priority takes longer as more tasks are added because it must check all tasks."

[OK] Correct: The system uses priority lists, so it only moves the task between lists without scanning all tasks.

Interview Connect

Understanding how task priority assignment scales helps you explain real-time system behavior clearly and confidently.

Self-Check

"What if the system had to reorder tasks within the same priority list when changing priority? How would the time complexity change?"

Practice

1.

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

easy

A. The task runs only when idle

B. The task runs after lower priority tasks

C. The task runs before lower priority tasks

D. The task is deleted automatically

Solution

1. Step 1: Understand task priority meaning

   In FreeRTOS, tasks with higher priority numbers get CPU time before lower priority tasks.

2. Step 2: Relate priority number to execution order

   A higher number means the task is more important and runs first.

3. Final Answer:

   The task runs before lower priority tasks -> Option C

4. Quick Check:

   Higher priority = runs first [OK]

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

Common Mistakes:

• Thinking lower number means higher priority
• Confusing priority with task state
• Assuming priority controls memory usage

2.

Which of the following is the correct way to assign a priority of 3 to a task in FreeRTOS using xTaskCreate?

void vTaskFunction(void *pvParameters) { /* Task code */ }

xTaskCreate(vTaskFunction, "Task1", 1000, NULL, ?, NULL);

easy

A. taskPriority = 3

B. "3"

C. priority = 3

D. 3

Solution

1. Step 1: Check xTaskCreate parameters

   The fifth parameter is the task priority and expects an integer value.

2. Step 2: Identify correct priority assignment

   Passing 3 directly as an integer is correct; strings or assignments are invalid here.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Priority parameter = integer value [OK]

Hint: Priority is an integer, no quotes or assignments [OK]

Common Mistakes:

• Using quotes around priority number
• Writing assignment expressions inside parameters
• Passing variable names without declaration

3.

Given the following FreeRTOS code snippet, which task will run first?

void TaskA(void *pvParameters) { while(1) {} }
void TaskB(void *pvParameters) { while(1) {} }

xTaskCreate(TaskA, "A", 1000, NULL, 2, NULL);
xTaskCreate(TaskB, "B", 1000, NULL, 4, NULL);

medium

A. TaskB

B. TaskA

C. Both run simultaneously

D. Neither runs

Solution

1. Step 1: Identify task priorities

   TaskA has priority 2, TaskB has priority 4.

2. Step 2: Determine which runs first

   TaskB has higher priority, so it runs before TaskA.

3. Final Answer:

   TaskB -> Option A

4. Quick Check:

   Higher priority task runs first [OK]

Hint: Higher priority number runs first [OK]

Common Mistakes:

• Assuming tasks run in creation order
• Thinking equal priority means simultaneous run
• Ignoring priority values

4.

What is wrong with this FreeRTOS task creation code snippet?

void vTask(void *pvParameters) { /* code */ }

xTaskCreate(vTask, "Task", 1000, NULL, 5, NULL);
xTaskCreate(vTask, "Task", 1000, NULL, -1, NULL);

medium

A. Priority cannot be negative

B. Task name must be unique

C. Stack size must be zero

D. Task function must return int

Solution

1. Step 1: Check priority values

   FreeRTOS priorities must be zero or positive integers; negative values are invalid.

2. Step 2: Validate other parameters

   Task name can be reused, stack size 1000 is valid, and task function returns void as required.

3. Final Answer:

   Priority cannot be negative -> Option A

4. Quick Check:

   Priority >= 0 required [OK]

Hint: Priority must be zero or positive [OK]

Common Mistakes:

• Using negative priority values
• Thinking task names must be unique
• Expecting task function to return int

5.

You have three tasks with priorities 1, 3, and 3. How should you assign priorities to ensure the most important task runs first and the least important runs last?

Choose the best priority assignment:

• A: Task1=1, Task2=3, Task3=3
• B: Task1=3, Task2=3, Task3=1
• C: Task1=3, Task2=1, Task3=3
• D: Task1=1, Task2=1, Task3=3

hard

A. Task1=1 (lowest), Task2=3, Task3=3 (highest)

B. Task1=3 (highest), Task2=3, Task3=1 (lowest)

C. Task1=3 (highest), Task2=1, Task3=3 (highest)

D. Task1=1, Task2=1, Task3=3 (highest)

Solution

1. Step 1: Identify importance order

   The most important task should have highest priority (3), least important lowest (1).

2. Step 2: Match priorities to tasks

   Task1=3 (highest), Task2=3, Task3=1 (lowest) assigns highest priority (3) to Task1 and Task2, and lowest (1) to Task3, ensuring important tasks run first.

3. Final Answer:

   Task1=3 (highest), Task2=3, Task3=1 (lowest) -> Option B

4. Quick Check:

   Highest priority = most important task [OK]

Hint: Assign highest number to most important task [OK]

Common Mistakes:

• Assigning same priority to all tasks
• Giving lowest priority to important tasks
• Ignoring task importance order