Task starvation and priority inversion in FreeRTOS - Time & Space Complexity

Time Complexity: Task starvation and priority inversion

O(n)

Understanding Time Complexity

When tasks share resources in FreeRTOS, some tasks may wait longer than others.

We want to understand how waiting time grows when tasks compete for resources.

Scenario Under Consideration

Analyze the time complexity of this FreeRTOS snippet involving priority inversion.

// Task handles and mutex
SemaphoreHandle_t xMutex;

void vHighPriorityTask(void *pvParameters) {
  xSemaphoreTake(xMutex, portMAX_DELAY); // Wait for mutex
  // Critical section
  xSemaphoreGive(xMutex);
  vTaskDelay(10);
}

void vLowPriorityTask(void *pvParameters) {
  xSemaphoreTake(xMutex, portMAX_DELAY); // Wait for mutex
  // Critical section
  vTaskDelay(50); // Simulate long work
  xSemaphoreGive(xMutex);
}

This code shows a high priority task and a low priority task sharing a mutex.

Identify Repeating Operations

Look for loops or repeated waits that cause delays.

• Primary operation: The high priority task waits repeatedly for the mutex held by the low priority task.
• How many times: Each time the high priority task runs and tries to take the mutex.

How Execution Grows With Input

Imagine more tasks or longer critical sections increase waiting time.

Input Size (n)	Approx. Operations
1 (1 low priority task)	Low waiting time
5 (multiple low priority tasks)	Waiting time grows as tasks hold mutex longer
10+	Waiting time can grow much longer due to priority inversion

Pattern observation: Waiting time grows roughly with the number of lower priority tasks holding the resource.

Final Time Complexity

Time Complexity: O(n)

This means waiting time grows linearly with the number of lower priority tasks blocking the resource.

Common Mistake

[X] Wrong: "High priority tasks always run immediately without delay."

[OK] Correct: Because lower priority tasks holding resources can block high priority tasks, causing delays.

Interview Connect

Understanding how task priorities affect waiting helps you design better multitasking systems.

Self-Check

"What if we use priority inheritance on the mutex? How would the time complexity change?"