Preemptive scheduling behavior in FreeRTOS - Time & Space Complexity

Time Complexity: Preemptive scheduling behavior

O(1)

Understanding Time Complexity

When FreeRTOS uses preemptive scheduling, tasks can be paused and resumed based on priority.

We want to understand how the time spent switching tasks grows as more tasks run.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void vTask1(void *pvParameters) {
    for(;;) {
        // Task 1 work
        vTaskDelay(10);
    }
}

void vTask2(void *pvParameters) {
    for(;;) {
        // Task 2 work
        vTaskDelay(5);
    }
}

int main() {
    xTaskCreate(vTask1, "Task1", 1000, NULL, 2, NULL);
    xTaskCreate(vTask2, "Task2", 1000, NULL, 3, NULL);
    vTaskStartScheduler();
    return 0;
}
    

This code creates two tasks with different priorities and starts the scheduler that switches between them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The scheduler repeatedly selects the highest priority ready task.
• How many times: The selection happens on each potential context switch (timer tick, delay end, etc.).

How Execution Grows With Input

As the number of tasks increases, the scheduler selects the next task in constant time using an array of ready lists per priority level (fixed small number of priorities).

Input Size (number of tasks)	Time per Scheduling Decision
2	O(1) - checks priority lists
10	O(1) - same, independent of tasks
100	O(1) - scans at most configMAX_PRIORITIES (~32)

Pattern observation: Scheduling decision time is constant (O(1)) regardless of number of tasks, as it doesn't scan all tasks.

Final Time Complexity

Time Complexity: O(1)

This means the time the scheduler spends deciding which task to run is constant with respect to the number of tasks.

Common Mistake

[X] Wrong: "The scheduler must check all tasks linearly, so O(n)."

[OK] Correct: FreeRTOS uses an array of lists (one per priority level, constant size), finds highest non-empty list in O(1) time.

Interview Connect

Understanding scheduler efficiency (O(1) selection) shows knowledge of real-time OS design and why FreeRTOS scales well with many tasks.

Self-Check

"What if the scheduler used a single priority queue for all tasks instead of per-priority lists? How would the time complexity change?"

Practice

1. What happens in FreeRTOS when a higher priority task becomes ready while a lower priority task is running under preemptive scheduling?

easy

A. The scheduler ignores the higher priority task until the lower priority task yields.

B. The lower priority task continues running until it finishes.

C. Both tasks run at the same time.

D. The higher priority task immediately preempts the lower priority task and starts running.

Solution

1. Step 1: Understand preemptive scheduling behavior

   In preemptive scheduling, the system always runs the highest priority task that is ready.

2. Step 2: Apply to the scenario

   When a higher priority task becomes ready, it interrupts the lower priority task immediately.

3. Final Answer:

   The higher priority task immediately preempts the lower priority task and starts running. -> Option D

4. Quick Check:

   Preemptive scheduling = immediate switch to higher priority task [OK]

Hint: Higher priority tasks always interrupt lower ones immediately [OK]

Common Mistakes:

• Thinking tasks run simultaneously on a single core
• Believing lower priority tasks finish before switching
• Confusing preemptive with cooperative scheduling

2. Which of the following is the correct way to enable preemptive scheduling in FreeRTOS configuration?

easy

A. #define configUSE_PREEMPTION 1

B. #define configENABLE_PREEMPTION true

C. #define configPREEMPTIVE_SCHEDULING 1

D. #define configUSE_PREEMPTION 0

Solution

1. Step 1: Recall FreeRTOS config option for preemption

   The correct macro to enable preemption is configUSE_PREEMPTION.

2. Step 2: Identify correct value to enable preemption

   Setting configUSE_PREEMPTION to 1 enables preemptive scheduling.

3. Final Answer:

   #define configUSE_PREEMPTION 1 -> Option A

4. Quick Check:

   configUSE_PREEMPTION = 1 enables preemption [OK]

Hint: Enable preemption by setting configUSE_PREEMPTION to 1 [OK]

Common Mistakes:

• Using 0 instead of 1 to enable preemption
• Using wrong macro names
• Using boolean true instead of 1

3. Consider two tasks in FreeRTOS: TaskA with priority 2 and TaskB with priority 3. TaskA is running when TaskB becomes ready. What will be the output if both tasks print their names when running?

medium

A. TaskA prints first, then TaskB prints after TaskA finishes.

B. TaskB prints immediately, preempting TaskA.

C. Both tasks print simultaneously.

D. No output because tasks block each other.

Solution

1. Step 1: Identify task priorities and running state

   TaskA has priority 2 and is running; TaskB has higher priority 3 and becomes ready.

2. Step 2: Apply preemptive scheduling rules

   TaskB will preempt TaskA immediately and run first, printing its name.

3. Final Answer:

   TaskB prints immediately, preempting TaskA. -> Option B

4. Quick Check:

   Higher priority task runs first = TaskB prints first [OK]

Hint: Higher priority task prints first by preempting lower priority [OK]

Common Mistakes:

• Assuming lower priority task finishes before switching
• Thinking tasks run at the same time
• Ignoring task priorities

4. Given this FreeRTOS snippet, what is the error that prevents preemptive scheduling from working?

#define configUSE_PREEMPTION 0

void Task1(void *pvParameters) {
  while(1) {
    // Task code
  }
}

void Task2(void *pvParameters) {
  while(1) {
    // Task code
  }
}

medium

A. configUSE_PREEMPTION is set to 0, disabling preemption.

B. Tasks are missing priority assignments.

C. Task functions must return int, not void.

D. Tasks need to call vTaskDelay to allow switching.

Solution

1. Step 1: Check configUSE_PREEMPTION value

   The macro is set to 0, which disables preemptive scheduling.

2. Step 2: Understand effect on scheduling

   With preemption disabled, tasks will not be interrupted automatically by higher priority tasks.

3. Final Answer:

   configUSE_PREEMPTION is set to 0, disabling preemption. -> Option A

4. Quick Check:

   configUSE_PREEMPTION = 0 disables preemption [OK]

Hint: Preemption disabled if configUSE_PREEMPTION = 0 [OK]

Common Mistakes:

• Thinking tasks must return int
• Assuming missing priorities cause preemption failure
• Believing vTaskDelay is required for preemption

5. You have three tasks: TaskX (priority 2), TaskY (priority 3), and TaskZ (priority 3). TaskX is running, then both TaskY and TaskZ become ready at the same time. Which task will FreeRTOS run first under preemptive scheduling, and why?

hard

A. TaskY runs first because it was created before TaskZ.

B. TaskZ runs first because it has the same priority as TaskY but higher than TaskX.

C. Either TaskY or TaskZ runs first; FreeRTOS uses time slicing between equal priorities.

D. TaskX continues running until it yields.

Solution

1. Step 1: Identify task priorities and ready state

   TaskX priority 2 is running; TaskY and TaskZ both have priority 3 and become ready simultaneously.

2. Step 2: Understand FreeRTOS behavior with equal priority tasks

   FreeRTOS uses time slicing (round-robin) between tasks of equal highest priority.

3. Step 3: Determine which task runs first

   Either TaskY or TaskZ can run first; the scheduler switches between them fairly.

4. Final Answer:

   Either TaskY or TaskZ runs first; FreeRTOS uses time slicing between equal priorities. -> Option C

5. Quick Check:

   Equal priority tasks share CPU time via time slicing [OK]

Hint: Equal priority tasks share CPU time by time slicing [OK]

Common Mistakes:

• Assuming creation order decides first run
• Thinking lower priority task continues running
• Believing one equal priority task always runs first