Stack size allocation in FreeRTOS - Time & Space Complexity

Time Complexity: Stack size allocation

O(n)

Understanding Time Complexity

When we allocate stack size in FreeRTOS tasks, we want to know how the time to allocate grows as the stack size changes.

We ask: How does increasing the stack size affect the time the system spends setting it up?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Create a task with a given stack size
xTaskCreate(
  TaskFunction,       // Task function
  "TaskName",        // Name
  stackSize,          // Stack size in words
  NULL,               // Parameters
  tskIDLE_PRIORITY,   // Priority
  NULL                // Task handle
);
    

This code creates a FreeRTOS task and allocates memory for its stack based on stackSize.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Allocating and initializing the stack memory of size stackSize.
• How many times: The system sets up each stack element once during allocation.

How Execution Grows With Input

As the stack size increases, the system spends more time setting up the stack memory.

Input Size (stackSize)	Approx. Operations
10	10 operations (setting up each stack word)
100	100 operations
1000	1000 operations

Pattern observation: The time grows directly with the stack size; doubling the stack size roughly doubles the setup time.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate and initialize the stack grows linearly with the stack size.

Common Mistake

[X] Wrong: "Allocating a larger stack size takes the same time as a smaller one because it's just one call."

[OK] Correct: Even though it's one function call, the system must set up each stack element, so bigger stacks take more time.

Interview Connect

Understanding how stack size affects allocation time helps you reason about resource use in embedded systems, a key skill for real-world programming.

Self-Check

"What if the stack memory was allocated from a pre-allocated pool instead of dynamically? How would the time complexity change?"

Practice

1. What does the stack size parameter specify when creating a FreeRTOS task?

easy

A. The total heap size available to the system

B. The number of tasks that can run simultaneously

C. The amount of memory allocated for the task's temporary data in words

D. The priority level of the task

Solution

1. Step 1: Understand stack size meaning in FreeRTOS

   The stack size defines how much memory a task can use for its temporary data and function calls.

2. Step 2: Identify the unit of stack size

   In FreeRTOS, stack size is given in words, not bytes, when creating a task.

3. Final Answer:

   The amount of memory allocated for the task's temporary data in words -> Option C

4. Quick Check:

   Stack size = task memory in words [OK]

Hint: Stack size means task memory in words, not bytes [OK]

Common Mistakes:

• Confusing stack size with heap size
• Thinking stack size is in bytes
• Mixing stack size with task priority

2. Which of the following is the correct way to specify stack size when creating a FreeRTOS task in C?

easy

A. xTaskCreate(taskFunction, "Task", 128 / sizeof(int), NULL, 1, NULL);

B. xTaskCreate(taskFunction, "Task", 128 * sizeof(char), NULL, 1, NULL);

C. xTaskCreate(taskFunction, "Task", 128 * sizeof(int), NULL, 1, NULL);

D. xTaskCreate(taskFunction, "Task", 128, NULL, 1, NULL);

Solution

1. Step 1: Recall stack size unit in FreeRTOS

   Stack size is specified in words, so just giving 128 means 128 words.

2. Step 2: Analyze each option

   xTaskCreate(taskFunction, "Task", 128, NULL, 1, NULL); uses 128 words directly, which is correct. xTaskCreate(taskFunction, "Task", 128 * sizeof(char), NULL, 1, NULL); and C multiply by size, which is incorrect. xTaskCreate(taskFunction, "Task", 128 / sizeof(int), NULL, 1, NULL); divides, which is also wrong.

3. Final Answer:

   xTaskCreate(taskFunction, "Task", 128, NULL, 1, NULL); -> Option D

4. Quick Check:

   Stack size = number of words, no sizeof needed [OK]

Hint: Use stack size as word count, no sizeof multiplication [OK]

Common Mistakes:

• Multiplying stack size by sizeof(int)
• Dividing stack size by sizeof(int)
• Confusing bytes and words in stack size

3. Given the code snippet:

void vTaskCode(void * pvParameters) {
    int x = 0;
    for(int i = 0; i < 10; i++) {
        x += i;
    }
    vTaskDelete(NULL);
}

xTaskCreate(vTaskCode, "Task1", 50, NULL, 2, NULL);

What is the minimum stack size allocation (in words) to safely run this task without overflow?

medium

A. 50 words

B. 10 words

C. 100 words

D. 5 words

Solution

1. Step 1: Analyze task stack usage

   The task uses a few local variables (x, i) and a small loop. This requires some stack but not very large.

2. Step 2: Check stack size given

   The task is created with 50 words stack size, which is enough for simple local variables and loop.

3. Final Answer:

   50 words -> Option A

4. Quick Check:

   Simple task needs moderate stack, 50 words is safe [OK]

Hint: Simple tasks need tens of words, not just a few [OK]

Common Mistakes:

• Assuming 10 words is enough for loop variables
• Overestimating stack need as 100 words
• Underestimating stack causing overflow

4. You have a FreeRTOS task created with stack size 20 words, but it crashes with stack overflow. What is the best fix?

medium

A. Decrease the stack size to save memory

B. Increase the stack size to a larger value like 100 words

C. Change the task priority to higher

D. Remove local variables from the task

Solution

1. Step 1: Identify cause of crash

   Stack overflow means the task's stack is too small for its needs.

2. Step 2: Choose appropriate fix

   Increasing stack size to a larger value like 100 words prevents overflow safely.

3. Final Answer:

   Increase the stack size to a larger value like 100 words -> Option B

4. Quick Check:

   Stack overflow fix = increase stack size [OK]

Hint: Stack overflow? Increase stack size [OK]

Common Mistakes:

• Reducing stack size to save memory
• Changing priority instead of stack size
• Ignoring local variables impact

5. You want to create two FreeRTOS tasks: Task A needs 80 words stack, Task B needs 40 words stack. The total heap is 100 words. How should you allocate stack sizes to avoid crashes and minimize wasted memory?

hard

A. Allocate 60 words to Task A and 40 words to Task B

B. Allocate 80 words to Task A and 40 words to Task B

C. Allocate 80 words to Task A and 20 words to Task B

D. Allocate 50 words to each task

Solution

1. Step 1: Understand total heap limit

   Total heap is 100 words, so sum of stack sizes must not exceed 100.

2. Step 2: Allocate stack sizes within limit

   Task A needs 80 words ideally, Task B needs 40 words, total 120 words which is over heap.

3. Step 3: Adjust allocation to fit heap

   Reduce Task A to 60 words and keep Task B at 40 words to fit 100 words total.

4. Final Answer:

   Allocate 60 words to Task A and 40 words to Task B -> Option A

5. Quick Check:

   Sum stack ≤ heap, adjust sizes accordingly [OK]

Hint: Sum stack sizes ≤ heap size to avoid crashes [OK]

Common Mistakes:

• Allocating more stack than heap allows
• Ignoring total heap limit
• Splitting stack sizes evenly without need