Tick timer and scheduler in FreeRTOS - Time & Space Complexity

Time Complexity: Tick timer and scheduler

O(n)

Understanding Time Complexity

We want to understand how the time it takes for the tick timer and scheduler to run changes as the system workload grows.

Specifically, how does the scheduler's work increase when more tasks are ready to run?

Scenario Under Consideration

Analyze the time complexity of the following FreeRTOS tick handler and scheduler call.

void vApplicationTickHook(void) {
    // Called every tick interrupt
    if (xSchedulerRunning) {
        if (xTaskIncrementTick() != pdFALSE) {
            vTaskSwitchContext();
        }
    }
}
    

This code runs on every tick interrupt. It updates the system tick count and switches tasks if needed.

Identify Repeating Operations

Look for loops or repeated work inside the scheduler call.

• Primary operation: The scheduler checks all ready tasks to find the highest priority one.
• How many times: It examines each ready task once per tick.

How Execution Grows With Input

As the number of ready tasks increases, the scheduler must check more tasks each tick.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

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

Final Time Complexity

Time Complexity: O(n)

This means the scheduler's work grows linearly as more tasks are ready to run.

Common Mistake

[X] Wrong: "The scheduler always runs in constant time regardless of tasks."

[OK] Correct: The scheduler must check each ready task to pick the next one, so more tasks mean more work.

Interview Connect

Understanding how scheduler time grows helps you design efficient multitasking systems and shows you can reason about system performance.

Self-Check

"What if the scheduler used a priority queue to track ready tasks? How would the time complexity change?"

Practice

1. What is the main role of the tick timer in FreeRTOS?

easy

A. To handle input/output operations

B. To store task priorities

C. To allocate memory for tasks

D. To count time in small steps called ticks

Solution

1. Step 1: Understand tick timer function

   The tick timer counts time in small units called ticks, which are the basic time measurement in FreeRTOS.

2. Step 2: Differentiate from other functions

   Other options like storing priorities or handling I/O are not related to the tick timer's role.

3. Final Answer:

   To count time in small steps called ticks -> Option D

4. Quick Check:

   Tick timer = counts ticks [OK]

Hint: Tick timer counts time steps, not priorities or memory [OK]

Common Mistakes:

• Confusing tick timer with task priority management
• Thinking tick timer handles memory or I/O
• Mixing tick timer with scheduler directly

2. Which of the following is the correct way to delay a task for 100 ticks in FreeRTOS?

easy

A. xTaskDelay(100);

B. vTaskDelay(1000);

C. vTaskDelay(100);

D. delayTask(100);

Solution

1. Step 1: Identify correct function name

   The correct FreeRTOS function to delay a task is vTaskDelay().

2. Step 2: Check parameter correctness

   The parameter is the number of ticks to delay. For 100 ticks, vTaskDelay(100); is correct.

3. Final Answer:

   vTaskDelay(100); -> Option C

4. Quick Check:

   Delay task = vTaskDelay(ticks) [OK]

Hint: Use vTaskDelay with tick count to pause tasks [OK]

Common Mistakes:

• Using wrong function name like xTaskDelay or delayTask
• Passing milliseconds instead of ticks
• Using too large or incorrect delay values

3. Consider this code snippet in FreeRTOS:

TickType_t start = xTaskGetTickCount();
vTaskDelay(50);
TickType_t end = xTaskGetTickCount();
TickType_t diff = end - start;

What is the expected value of diff?

medium

A. 0

B. 50

C. 100

D. Depends on task priority

Solution

1. Step 1: Understand xTaskGetTickCount()

   This function returns the current tick count since the scheduler started.

2. Step 2: Analyze vTaskDelay(50)

   The task delays itself for 50 ticks, so the tick count advances by 50 during the delay.

3. Step 3: Calculate difference

   Subtracting start from end gives the delay duration, which should be 50 ticks.

4. Final Answer:

   50 -> Option B

5. Quick Check:

   Delay ticks = 50 [OK]

Hint: Delay of 50 ticks means tick count difference is 50 [OK]

Common Mistakes:

• Assuming delay is zero or doubled
• Thinking task priority affects tick count difference
• Confusing ticks with milliseconds

4. What is wrong with this FreeRTOS code snippet?

vTaskDelay(0);
TickType_t ticks = xTaskGetTickCount();

medium

A. vTaskDelay(0) does not delay the task

B. xTaskGetTickCount() returns an error

C. vTaskDelay requires a pointer argument

D. TickType_t is not a valid type

Solution

1. Step 1: Check vTaskDelay parameter

   Passing 0 to vTaskDelay means no delay; the task yields but continues immediately.

2. Step 2: Verify xTaskGetTickCount()

   This function correctly returns the current tick count; no error here.

3. Final Answer:

   vTaskDelay(0) does not delay the task -> Option A

4. Quick Check:

   Delay(0) means no wait [OK]

Hint: vTaskDelay(0) yields but does not pause task [OK]

Common Mistakes:

• Expecting delay with zero ticks
• Thinking xTaskGetTickCount returns error
• Misunderstanding TickType_t type

5. You want a task to run every 200 ticks precisely using FreeRTOS. Which approach ensures this timing despite task execution time?

hard

A. Use vTaskDelayUntil() with a previous wake time variable

B. Use vTaskDelay(200) at the end of the task loop

C. Use xTaskGetTickCount() inside the task and delay manually

D. Use vTaskDelay(100) twice in the task loop

Solution

1. Step 1: Understand vTaskDelay() limitation

   Using vTaskDelay(200) delays from current time, so task execution time adds up causing drift.

2. Step 2: Use vTaskDelayUntil() for fixed periodic timing

   vTaskDelayUntil() uses a previous wake time to maintain exact periodic intervals regardless of execution time.

3. Step 3: Evaluate other options

   Manual delay or multiple delays do not guarantee precise timing; only vTaskDelayUntil() does.

4. Final Answer:

   Use vTaskDelayUntil() with a previous wake time variable -> Option A

5. Quick Check:

   Precise periodic task = vTaskDelayUntil() [OK]

Hint: Use vTaskDelayUntil() for exact periodic task timing [OK]

Common Mistakes:

• Using vTaskDelay causes timing drift
• Trying manual delay calculations
• Ignoring task execution time in timing