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