How do you design a custom memory allocator to eliminate fragmentation and guarantee deterministic execution time in a safety-critical embedded system?

Short answer

Test the candidate's ability to design custom memory management strategies, focusing on memory fragmentation, deterministic allocation times, and safety-critical constraints.

In automotive Electronic Control Units (ECUs) responsible for Advanced Driver Assistance Systems (ADAS), strict ISO 26262 ASIL-D safety requirements mandate absolute deterministic behaviour and prohibit unbounded execution times. Relying heavily on standard dynamic memory allocation functions (malloc and free) from the C standard library introduces unacceptable risks when allocating variable-sized blocks from a single global heap.

During prolonged operation, severe external memory fragmentation inevitably occurs. As blocks are allocated and freed, the heap becomes riddled with small, non-contiguous free gaps. Eventually, a request for a large contiguous buffer fails because no single free block is large enough, even if the total free memory is theoretically sufficient. Furthermore, the execution time of malloc exhibits massive jitter; traversing a fragmented free list takes an unpredictable amount of time, violating the hard real-time deadlines required for collision avoidance tasks.

Why compaction and buddy allocators still fail here

The typical novice response is to write a "better" compaction algorithm or a buddy allocator to manage the global heap more efficiently. This fundamentally misses the point of safety-critical embedded constraints. Heap compaction in software pauses the system, introducing the exact catastrophic jitter we are trying to avoid. Buddy allocators still suffer from unpredictable latency bounds when coalescing blocks under heavy load. General-purpose variable-size allocation is inherently hostile to hard real-time guarantees.

Fixed-size block allocation

The engineering standard for this domain is a Fixed-Size Block Allocator, commonly known as a Memory Pool. By partitioning the available RAM into multiple distinct pools—where each pool contains blocks of exactly one size (e.g., 32-byte, 128-byte, and 1024-byte pools)—external fragmentation is mathematically eliminated.

The allocation algorithm maintains a singly linked free list where the "next" pointer is stored directly within the free blocks themselves, demanding zero additional memory overhead for metadata. When memory is requested, the allocator determines the smallest pool that can satisfy the request and pops the first block. This push/pop operation is strictly constant and deterministic (O(1)), eradicating the jitter of heap traversal.

The explicit trade-off is the introduction of internal fragmentation. If a task requests 40 bytes, it receives a 128-byte block, wasting 88 bytes. This requires rigorous static analysis of the application's memory requirements at compile time to optimally size the pools and ensure total RAM consumption remains within hardware limits.

Concurrency and spatial isolation

In a preemptive multitasking environment, synchronisation mechanisms are required when concurrent tasks allocate from the same pool. Relying on traditional mutexes introduces priority inversion and blocking overhead. Lock-free atomic operations (such as Load-Linked/Store-Conditional or Compare-And-Swap) manage the free list pointers deterministically, provided the ABA problem is handled correctly.

Finally, memory corruption—where a buffer overflow in one task overwrites another's data—is mitigated by integrating the custom allocator with the hardware Memory Protection Unit (MPU). The MPU regions are configured dynamically during context switches, enforcing that a task can only read and write to the specific memory blocks it has explicitly allocated.

flowchart TD
    A["Memory Request (Size N)"] --> B["Determine Target Pool"]
    B --> C{"Pool Available?"}
    C -- "No" --> D["Trigger Fatal Error (Out of Memory)"]
    C -- "Yes" --> E["Atomic Pop from Free List"]
    E --> F{"Pop Successful?"}
    F -- "No (ABA/Contention)" --> E
    F -- "Yes" --> G["Assign Block Ownership"]
    G --> H["Configure MPU Region"]
    H --> I["Return Pointer to Task"]
    I --> J["Task Uses Memory"]
    J --> K["Memory Free Request"]
    K --> L["Clear MPU Region"]
    L --> M["Atomic Push to Free List"]

Designing custom memory allocators for safety-critical systems demands replacing non-deterministic variable-size heaps with Fixed-Size Block Allocators to guarantee O(1) execution times and eliminate external fragmentation, while utilising hardware MPUs to enforce strict spatial isolation.

© 2026 Preptima. Originally published at preptima.com.