FreeRTOS heap implementations (heap_1 to heap_5) - Time & Space Complexity

Time Complexity: FreeRTOS heap implementations (heap_1 to heap_5)

O(n)

Understanding Time Complexity

When using FreeRTOS, memory allocation speed affects how fast tasks start and run. Different heap implementations manage memory differently, so their speed changes as memory requests grow.

We want to know how the time to allocate or free memory changes when the number of allocations increases.

Scenario Under Consideration

Analyze the time complexity of the heap_4 memory allocation function.

void *pvPortMalloc( size_t xSize ) {
    BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
    void *pvReturn = NULL;

    if( xSize > 0 ) {
        // Traverse free list to find a block big enough
        pxPreviousBlock = &xStart;
        pxBlock = xStart.pxNextFreeBlock;
        while( pxBlock != NULL && pxBlock->xBlockSize < xSize ) {
            pxPreviousBlock = pxBlock;
            pxBlock = pxBlock->pxNextFreeBlock;
        }
        // If found, allocate and adjust free list
        if( pxBlock != NULL && pxBlock->xBlockSize >= xSize ) {
            pvReturn = (void *)( ( uint8_t * ) pxBlock + heapSTRUCT_SIZE );
            // Adjust free list here
        }
    }
    return pvReturn;
}

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the number of free blocks grows, the search takes longer because it checks each block until it finds a fit.

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 in the heap.

Common Mistake

[X] Wrong: "Memory allocation always takes constant time regardless of heap size."

[OK] Correct: In FreeRTOS heap implementations like heap_4, allocation searches through free blocks, so more blocks mean more time.

Interview Connect

Understanding how memory allocation time grows helps you explain system responsiveness and resource management in embedded systems.

Self-Check

"What if the free blocks were kept in a sorted tree instead of a linked list? How would the time complexity change?"

Practice

1. Which FreeRTOS heap implementation does NOT support freeing allocated memory?

easy

A. heap_1

B. heap_2

C. heap_3

D. heap_4

Solution

1. Step 1: Understand heap_1 behavior

   heap_1 only allows allocation but does not provide a function to free memory once allocated.

2. Step 2: Compare with other heaps

   heap_2, heap_3, and heap_4 all support freeing memory, with heap_3 using standard malloc/free.

3. Final Answer:

   heap_1 -> Option A

4. Quick Check:

   heap_1 no free support = heap_1 [OK]

Hint: heap_1 never frees memory, others do [OK]

Common Mistakes:

• Confusing heap_1 with heap_2 which supports free
• Assuming all heaps support freeing memory
• Mixing heap_3's malloc/free with heap_1's behavior

2. Which of the following is the correct way to include the heap_3 implementation in your FreeRTOS project?

easy

A. #include "heap3.c"

B. #include "heap_3.c"

C. #include "FreeRTOSHeap3.c"

D. #include

Solution

1. Step 1: Check FreeRTOS heap file naming

   Heap implementations are included by adding the corresponding .c file, e.g., "heap_3.c".

2. Step 2: Verify correct syntax

   Using #include "heap_3.c" is the standard way to include heap_3 in the build.

3. Final Answer:

   #include "heap_3.c" -> Option B

4. Quick Check:

   Include heap_3.c with quotes = D [OK]

Hint: Include heap source file with quotes, not angle brackets [OK]

Common Mistakes:

• Using angle brackets instead of quotes
• Incorrect file name spelling or casing
• Trying to include a header instead of the .c file

3. Given the following code snippet using heap_4, what will be the output if the allocation fails?

void *ptr = pvPortMalloc(1000);
if(ptr == NULL) {
    printf("Allocation failed\n");
} else {
    printf("Allocation succeeded\n");
}

medium

A. Compilation error

B. Allocation succeeded

C. Allocation failed

D. No output

Solution

1. Step 1: Understand heap_4 allocation behavior

   heap_4 supports allocation and freeing with coalescing. If memory is insufficient, pvPortMalloc returns NULL.

2. Step 2: Analyze the if condition

   If ptr is NULL, the code prints "Allocation failed"; otherwise, it prints "Allocation succeeded".

3. Final Answer:

   Allocation failed -> Option C

4. Quick Check:

   pvPortMalloc NULL means failure = A [OK]

Hint: pvPortMalloc returns NULL on failure [OK]

Common Mistakes:

• Assuming allocation always succeeds
• Confusing NULL with zero pointer
• Ignoring the if condition logic

4. You are using heap_2 in your FreeRTOS project but notice memory is not being freed properly. Which of the following is the most likely cause?

medium

A. heap_2 does not support freeing memory

B. heap_2 uses standard malloc/free which is not thread-safe

C. heap_2 requires manual coalescing of free blocks

D. You forgot to call vPortFree() after allocation

Solution

1. Step 1: Recall heap_2 features

   heap_2 supports freeing memory via vPortFree(), but does not coalesce free blocks.

2. Step 2: Identify common mistake

   If memory is not freed, the most common cause is forgetting to call vPortFree() after allocation.

3. Final Answer:

   You forgot to call vPortFree() after allocation -> Option D

4. Quick Check:

   Missing vPortFree causes leaks = B [OK]

Hint: Always call vPortFree() to release heap_2 memory [OK]

Common Mistakes:

• Assuming heap_2 lacks free support
• Confusing heap_2 with heap_1 or heap_3
• Thinking heap_2 uses malloc/free internally

5. You want to use a FreeRTOS heap implementation that supports both allocation and freeing, minimizes fragmentation by coalescing adjacent free blocks, and is suitable for real-time systems. Which heap should you choose?

hard

A. heap_4

B. heap_2

C. heap_1

D. heap_5

Solution

1. Step 1: Review heap features

   heap_1 does not support freeing; heap_2 supports free but no coalescing; heap_4 supports free and coalesces adjacent free blocks; heap_5 extends heap_4 with multiple memory regions.

2. Step 2: Match requirements

   For minimizing fragmentation and real-time suitability, heap_4 is ideal as it coalesces free blocks and is deterministic.

3. Final Answer:

   heap_4 -> Option A

4. Quick Check:

   heap_4 coalesces free blocks = A [OK]

Hint: heap_4 coalesces free blocks, best for fragmentation [OK]

Common Mistakes:

• Choosing heap_5 without needing multiple regions
• Assuming heap_2 coalesces free blocks
• Picking heap_1 which lacks free support