Time-slicing for equal priority tasks in FreeRTOS - Time & Space Complexity

Time Complexity: Time-slicing for equal priority tasks

O(1/n)

Understanding Time Complexity

We want to understand how the CPU time is shared when tasks have the same priority in FreeRTOS.

How does the system decide how long each task runs before switching?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Two tasks with equal priority
void Task1(void *pvParameters) {
    for (;;) {
        // Task1 work
        vTaskDelay(1); // Yield after some work
    }
}

void Task2(void *pvParameters) {
    for (;;) {
        // Task2 work
        vTaskDelay(1); // Yield after some work
    }
}

// Both tasks run with same priority
xTaskCreate(Task1, "Task1", 1000, NULL, 2, NULL);
xTaskCreate(Task2, "Task2", 1000, NULL, 2, NULL);

This code creates two tasks with the same priority that repeatedly run and yield control.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each task runs an infinite loop doing work and then yields.
• How many times: The loop repeats indefinitely, switching between tasks each time.

How Execution Grows With Input

As the number of equal priority tasks increases, the CPU time is divided among them.

Number of Tasks (n)	Approx. CPU Time per Task
2	About half the CPU time each
5	About one fifth the CPU time each
10	About one tenth the CPU time each

Pattern observation: Each task gets a smaller slice as more tasks share the same priority.

Final Time Complexity

Time Complexity: O(1/n)

This means the CPU time per task decreases linearly as the number of equal priority tasks increases.

Common Mistake

[X] Wrong: "All tasks run fully one after another regardless of priority."

[OK] Correct: When tasks have equal priority, FreeRTOS switches between them frequently to share CPU time fairly, not running one task completely before switching.

Interview Connect

Understanding how time-slicing works helps you explain multitasking fairness and responsiveness in real-time systems.

Self-Check

"What if one task had higher priority than the others? How would the time complexity of CPU sharing change?"

Practice

1. What does time-slicing mean in FreeRTOS when tasks have equal priority?

easy

A. Higher priority tasks are paused to let lower priority tasks run.

B. The CPU time is shared fairly among tasks with the same priority.

C. Tasks with equal priority run one after another without switching.

D. Only the first created task runs until it finishes.

Solution

1. Step 1: Understand time-slicing concept

   Time-slicing means the CPU divides its time between tasks that have the same priority.

2. Step 2: Apply to FreeRTOS behavior

   FreeRTOS automatically switches between equal priority tasks to share CPU time fairly.

3. Final Answer:

   The CPU time is shared fairly among tasks with the same priority. -> Option B

4. Quick Check:

   Time-slicing = fair CPU sharing [OK]

Hint: Equal priority means tasks share CPU time fairly [OK]

Common Mistakes:

• Thinking only one task runs until it finishes
• Believing tasks run sequentially without switching
• Assuming lower priority tasks pause higher priority ones

2. Which of the following is the correct way to set two tasks to have equal priority in FreeRTOS?

easy

A. xTaskCreate(task1, "Task1", 1000, NULL, 2, NULL); xTaskCreate(task2, "Task2", 1000, NULL, 2, NULL);

B. xTaskCreate(task1, "Task1", 1000, NULL, 1, NULL); xTaskCreate(task2, "Task2", 1000, NULL, 3, NULL);

C. xTaskCreate(task1, "Task1", 1000, NULL, 0, NULL); xTaskCreate(task2, "Task2", 1000, NULL, 1, NULL);

D. xTaskCreate(task1, "Task1", 1000, NULL, 5, NULL); xTaskCreate(task2, "Task2", 1000, NULL, 4, NULL);

Solution

1. Step 1: Check task priority parameters

   In FreeRTOS, the fifth parameter in xTaskCreate is the task priority.

2. Step 2: Identify equal priorities

   Both tasks have priority 2 in xTaskCreate(task1, "Task1", 1000, NULL, 2, NULL); xTaskCreate(task2, "Task2", 1000, NULL, 2, NULL);, making them equal priority tasks.

3. Final Answer:

   Both tasks have priority 2, so they have equal priority. -> Option A

4. Quick Check:

   Same priority number = equal priority [OK]

Hint: Same priority number means equal priority [OK]

Common Mistakes:

• Assigning different priority numbers to tasks
• Confusing task stack size with priority
• Using priority 0 and 1 as equal

3. Given two tasks with equal priority in FreeRTOS, what is the expected behavior when both are ready to run?

medium

A. Both tasks run simultaneously on the same CPU core.

B. One task runs to completion before the other starts.

C. The second task never runs because the first task blocks it.

D. The scheduler switches between tasks periodically to share CPU time.

Solution

1. Step 1: Understand FreeRTOS scheduling for equal priority tasks

   FreeRTOS uses time-slicing to switch between tasks of equal priority.

2. Step 2: Predict scheduler behavior

   The scheduler switches tasks periodically, giving each task CPU time in turn.

3. Final Answer:

   The scheduler switches between tasks periodically to share CPU time. -> Option D

4. Quick Check:

   Equal priority tasks share CPU via switching [OK]

Hint: Equal priority tasks get CPU time by switching [OK]

Common Mistakes:

• Thinking tasks run one after another without switching
• Assuming tasks run simultaneously on one core
• Believing one task blocks the other forever

4. You have two tasks with equal priority, but one task never seems to run. What is the most likely cause?

medium

A. The task that never runs has a higher priority number.

B. FreeRTOS does not support time-slicing for equal priority tasks.

C. The task that never runs is blocked or waiting indefinitely.

D. The scheduler is disabled, so no task switching occurs.

Solution

1. Step 1: Check task states in FreeRTOS

   Even with equal priority, a task that is blocked or waiting will not run.

2. Step 2: Identify why a task never runs

   If a task never runs, it is likely blocked or waiting indefinitely, not ready to run.

3. Final Answer:

   The task that never runs is blocked or waiting indefinitely. -> Option C

4. Quick Check:

   Blocked task = no CPU time [OK]

Hint: Blocked tasks don't get CPU time even if priority is equal [OK]

Common Mistakes:

• Assuming higher priority task blocks lower priority always
• Believing FreeRTOS lacks time-slicing
• Ignoring task states like blocked or suspended

5. You have three tasks with equal priority in FreeRTOS. Task A runs for 10ms, Task B for 20ms, and Task C for 30ms before yielding. How does time-slicing affect their CPU time distribution?

hard

A. Each task gets equal CPU time slices regardless of run duration before yielding.

B. Tasks that run longer before yielding get more CPU time overall.

C. Task C will starve Tasks A and B because it runs longest.

D. FreeRTOS runs tasks in creation order ignoring time-slicing.

Solution

1. Step 1: Understand time-slicing with equal priority tasks

   FreeRTOS scheduler switches tasks periodically to share CPU time fairly among equal priority tasks.

2. Step 2: Analyze effect of different run durations before yielding

   Even if tasks run different times before yielding, the scheduler enforces time slices to balance CPU time.

3. Final Answer:

   Each task gets equal CPU time slices regardless of run duration before yielding. -> Option A

4. Quick Check:

   Time-slicing ensures fair CPU time despite run length [OK]

Hint: Time-slicing balances CPU time regardless of task run length [OK]

Common Mistakes:

• Assuming longer running tasks get more CPU time
• Thinking tasks can starve others with longer runs
• Believing task creation order controls CPU time