Choosing the right heap scheme in FreeRTOS - Time & Space Complexity

Time Complexity: Choosing the right heap scheme

O(n)

Understanding Time Complexity

When using FreeRTOS, choosing the right heap scheme affects how fast memory allocation and freeing happen.

We want to know how the time to allocate or free memory changes as the program runs longer or uses more memory.

Scenario Under Consideration

Analyze the time complexity of this heap allocation function from FreeRTOS heap_4 scheme.

void *pvPortMalloc( size_t xWantedSize ) {
    BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
    size_t xBlockSize;

    // Traverse free list to find a block big enough
    for( pxPreviousBlock = &xStart, pxBlock = xStart.pxNextFreeBlock;
         pxBlock->xBlockSize < xWantedSize && pxBlock->pxNextFreeBlock != NULL;
         pxPreviousBlock = pxBlock, pxBlock = pxBlock->pxNextFreeBlock ) {
        // loop body empty
    }

    if( pxBlock != &xEnd ) {
        // Allocate memory from this block
    }
    return NULL;
}
    

This code searches a linked list of free memory blocks to find a block large enough to allocate.

Identify Repeating Operations

Look for loops or repeated steps in the code.

• Primary operation: Loop through the free memory blocks linked list.
• How many times: Up to the number of free blocks in the list.

How Execution Grows With Input

The time to find a block grows as the number of free blocks grows.

Input Size (number of free blocks)	Approx. Operations (block checks)
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The time grows roughly in direct proportion to the number of free blocks.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate memory grows linearly with the number of free blocks to check.

Common Mistake

[X] Wrong: "Memory allocation always happens instantly regardless of heap size."

[OK] Correct: The allocator must search free blocks, so more blocks mean more time to find space.

Interview Connect

Understanding how heap schemes affect allocation time helps you explain trade-offs in embedded systems memory management.

Self-Check

What if the heap scheme used a balanced tree instead of a linked list? How would the time complexity change?

Practice

1. Which FreeRTOS heap scheme is known for being the most flexible and commonly used?

easy

A. heap_3

B. heap_1

C. heap_2

D. heap_4

Solution

1. Step 1: Understand heap scheme flexibility

   heap_4 supports both allocation and freeing of memory blocks and handles fragmentation well.

2. Step 2: Compare with other schemes

   heap_1 only allows allocation, heap_2 allows freeing but less fragmentation control, heap_3 uses standard malloc/free.

3. Final Answer:

   heap_4 -> Option D

4. Quick Check:

   Most flexible heap scheme = heap_4 [OK]

Hint: heap_4 is the flexible, common choice for FreeRTOS heaps [OK]

Common Mistakes:

• Confusing heap_1 as flexible since it allows allocation
• Thinking heap_3 is best because it uses malloc/free
• Assuming heap_2 handles fragmentation well

2. Which of the following is the correct way to enable heap_2 scheme in FreeRTOSConfig.h?

easy

A. #define configFRTOS_MEMORY_SCHEME 2

B. #define configFRTOS_MEMORY_SCHEME heap_2

C. #define configFRTOS_MEMORY_SCHEME 3

D. #define configFRTOS_MEMORY_SCHEME 1

Solution

1. Step 1: Recall heap scheme selection method

   FreeRTOSConfig.h uses numeric defines to select heap scheme, e.g., 1, 2, 3, or 4.

2. Step 2: Match number to heap_2

   heap_2 corresponds to the number 2, so #define configFRTOS_MEMORY_SCHEME 2 is correct syntax.

3. Final Answer:

   #define configFRTOS_MEMORY_SCHEME 2 -> Option A

4. Quick Check:

   Heap_2 scheme uses number 2 in config [OK]

Hint: Use numeric value 2 to select heap_2 scheme [OK]

Common Mistakes:

• Using string name instead of number
• Confusing heap_2 with heap_3 or heap_1 numbers
• Missing #define keyword

3. Given FreeRTOS is configured with heap_1 scheme, what happens if you try to free memory allocated by pvPortMalloc()?

medium

A. Memory is freed successfully without errors

B. Free operation is ignored; memory is not freed

C. System crashes due to invalid free

D. Memory is freed but causes fragmentation

Solution

1. Step 1: Understand heap_1 behavior

   heap_1 only supports allocation; it does not support freeing memory blocks.

2. Step 2: Effect of calling free in heap_1

   Calling free is ignored silently; memory is not actually freed, so no crash occurs.

3. Final Answer:

   Free operation is ignored; memory is not freed -> Option B

4. Quick Check:

   heap_1 ignores free calls [OK]

Hint: heap_1 does not free memory, free calls are ignored [OK]

Common Mistakes:

• Assuming free works normally in heap_1
• Expecting a system crash on free
• Thinking fragmentation is handled in heap_1

4. You configured FreeRTOS to use heap_3 but experience heap corruption errors. What is the most likely cause?

medium

A. Using standard malloc/free that conflicts with FreeRTOS allocations

B. Not defining configFRTOS_MEMORY_SCHEME in FreeRTOSConfig.h

C. heap_3 does not support freeing memory

D. heap_3 requires manual defragmentation calls

Solution

1. Step 1: Understand heap_3 implementation

   heap_3 uses standard malloc() and free() from the C library for memory management.

2. Step 2: Identify conflict cause

   If other parts of the system also use malloc/free independently, it can cause heap corruption due to overlapping or mismatched management.

3. Final Answer:

   Using standard malloc/free that conflicts with FreeRTOS allocations -> Option A

4. Quick Check:

   heap_3 uses malloc/free which can conflict [OK]

Hint: heap_3 uses malloc/free; conflicts cause corruption [OK]

Common Mistakes:

• Assuming heap_3 manages memory independently
• Forgetting to define configFRTOS_MEMORY_SCHEME
• Thinking heap_3 requires manual defragmentation

5. You need a FreeRTOS heap scheme that supports dynamic allocation, freeing, and minimizes fragmentation for a long-running embedded system. Which heap scheme should you choose and why?

hard

A. heap_1 because it is simple and fast

B. heap_2 because it supports freeing but has fragmentation issues

C. heap_4 because it supports allocation, freeing, and reduces fragmentation

D. heap_3 because it uses standard malloc/free

Solution

1. Step 1: Identify requirements

   The system needs allocation, freeing, and low fragmentation for long uptime.

2. Step 2: Match heap schemes to requirements

   heap_1 lacks freeing, heap_2 frees but fragments, heap_3 uses malloc/free which may fragment unpredictably, heap_4 supports freeing and has fragmentation control.

3. Step 3: Choose best fit

   heap_4 best fits all requirements for long-running embedded systems.

4. Final Answer:

   heap_4 because it supports allocation, freeing, and reduces fragmentation -> Option C

5. Quick Check:

   Best heap for allocation, freeing, low fragmentation = heap_4 [OK]

Hint: heap_4 balances freeing and fragmentation best for long runs [OK]

Common Mistakes:

• Choosing heap_1 for freeing support
• Ignoring fragmentation issues in heap_2
• Assuming heap_3 is best because it uses malloc/free