Choosing priorities for real applications in FreeRTOS - Time & Space Complexity

Time Complexity: Choosing priorities for real applications

O(n)

Understanding Time Complexity

When we assign priorities to tasks in FreeRTOS, it affects how often tasks run and how long they wait.

We want to understand how the time to complete tasks changes as we add more tasks with different priorities.

Scenario Under Consideration

Analyze the time complexity of scheduling tasks with different priorities.

// Create tasks with different priorities
xTaskCreate(task1, "Task1", 1000, NULL, 3, NULL);
xTaskCreate(task2, "Task2", 1000, NULL, 2, NULL);
xTaskCreate(task3, "Task3", 1000, NULL, 1, NULL);

// Start the scheduler
vTaskStartScheduler();
    

This code creates three tasks with different priorities and starts the scheduler to run the highest priority task ready to run.

Identify Repeating Operations

Look at what repeats during scheduling:

• Primary operation: The scheduler checks all ready tasks to find the highest priority one.
• How many times: This check happens every time a task finishes or blocks, so it repeats often.

How Execution Grows With Input

As the number of tasks (n) grows, the scheduler must check more tasks to find the highest priority ready one.

Input Size (n)	Approx. Operations
3	3 checks per scheduling decision
10	10 checks per scheduling decision
100	100 checks per scheduling decision

Pattern observation: The number of checks grows directly with the number of tasks.

Final Time Complexity

Time Complexity: O(n)

This means the scheduler's work grows linearly as you add more tasks with different priorities.

Common Mistake

[X] Wrong: "Adding more tasks won't affect scheduling time because priorities decide order instantly."

[OK] Correct: The scheduler still checks all ready tasks to find the highest priority one, so more tasks mean more checks.

Interview Connect

Understanding how task priorities affect scheduling time helps you design responsive systems and shows you can think about performance in real applications.

Self-Check

"What if all tasks have the same priority? How would the time complexity of scheduling change?"

Practice

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

easy

A. The task runs before lower priority tasks

B. The task uses less memory

C. The task runs slower

D. The task is paused

Solution

1. Step 1: Understand task priority meaning

   In FreeRTOS, task priority determines which task the scheduler runs first.

2. Step 2: Higher number means higher priority

   A higher priority number means the task is more important and runs before lower priority tasks.

3. Final Answer:

   The task runs before lower priority tasks -> Option A

4. Quick Check:

   Higher priority = runs first [OK]

Hint: Higher number means task runs first [OK]

Common Mistakes:

• Thinking higher priority means slower task
• Confusing priority with memory usage
• Assuming priority pauses the task

2. Which of the following is the correct way to set a task priority in FreeRTOS?

easy

A. xTaskCreate(taskFunction, "Task", stackSize, NULL, -1, NULL);

B. xTaskCreate(taskFunction, "Task", stackSize, NULL, "high", NULL);

C. xTaskCreate(taskFunction, "Task", stackSize, NULL, 5, NULL);

D. xTaskCreate(taskFunction, "Task", stackSize, NULL, 0.5, NULL);

Solution

1. Step 1: Check parameter for priority in xTaskCreate

   The fifth parameter in xTaskCreate is the task priority and must be an integer.

2. Step 2: Validate options

   xTaskCreate(taskFunction, "Task", stackSize, NULL, 5, NULL); uses integer 5, which is valid. xTaskCreate(taskFunction, "Task", stackSize, NULL, "high", NULL); uses a string, invalid. xTaskCreate(taskFunction, "Task", stackSize, NULL, -1, NULL); uses negative priority, invalid. xTaskCreate(taskFunction, "Task", stackSize, NULL, 0.5, NULL); uses float, invalid.

3. Final Answer:

   xTaskCreate(taskFunction, "Task", stackSize, NULL, 5, NULL); -> Option C

4. Quick Check:

   Priority must be integer >= 0 [OK]

Hint: Priority is an integer in xTaskCreate [OK]

Common Mistakes:

• Using string or float for priority
• Using negative numbers for priority
• Confusing parameter order

3. Given three tasks with priorities: TaskA=3, TaskB=5, TaskC=2. Which task will run first when all are ready?

medium

A. TaskA

B. They run simultaneously

C. TaskC

D. TaskB

Solution

1. Step 1: Compare task priorities

   TaskB has priority 5, TaskA has 3, TaskC has 2.

2. Step 2: Highest priority runs first

   Since 5 is highest, TaskB runs first when all are ready.

3. Final Answer:

   TaskB -> Option D

4. Quick Check:

   Highest priority = 5 = TaskB [OK]

Hint: Highest priority number runs first [OK]

Common Mistakes:

• Choosing lowest priority task
• Thinking tasks run simultaneously
• Ignoring priority values

4. You set two tasks with the same priority in FreeRTOS. What is a likely issue?

medium

A. Tasks will share CPU time but may cause unpredictable timing

B. Tasks may starve lower priority tasks

C. One task will never run

D. System will crash immediately

Solution

1. Step 1: Understand equal priority behavior

   Tasks with same priority share CPU time via time slicing.

2. Step 2: Effects of equal priority

   This can cause unpredictable timing because tasks switch frequently, but no starvation occurs.

3. Final Answer:

   Tasks will share CPU time but may cause unpredictable timing -> Option A

4. Quick Check:

   Same priority = time slicing, possible timing issues [OK]

Hint: Same priority tasks share CPU, timing may vary [OK]

Common Mistakes:

• Assuming one task never runs
• Expecting system crash
• Ignoring time slicing behavior

5. You have three tasks: SensorRead (must respond fast), DataLogging (less urgent), and UIUpdate (medium urgency). How should you assign priorities?

hard

A. DataLogging=3, UIUpdate=2, SensorRead=1

B. SensorRead=3, UIUpdate=2, DataLogging=1

C. UIUpdate=3, SensorRead=2, DataLogging=1

D. All tasks priority 1

Solution

1. Step 1: Identify task urgency

   SensorRead must respond fastest, so highest priority. UIUpdate is medium, DataLogging less urgent.

2. Step 2: Assign priorities accordingly

   Assign SensorRead=3 (highest), UIUpdate=2, DataLogging=1 (lowest).

3. Final Answer:

   SensorRead=3, UIUpdate=2, DataLogging=1 -> Option B

4. Quick Check:

   Fastest task gets highest priority [OK]

Hint: Fastest task gets highest priority [OK]

Common Mistakes:

• Giving low priority to fastest task
• Assigning same priority to all
• Reversing urgency order