AN2345 Freescale Semiconductor / Motorola, AN2345 Datasheet - Page 2

• Manufacturer Part Number: AN2345
• Description: Real-Time Memory Manager for StarCore DSPs
• Manufacturer: Freescale Semiconductor / Motorola

Memory Manager Limitations
1.2 Deterministic Systems
2
Real-time systems are prolific within embedded environments. A real-time system must be deterministic,
that is, it must provide a required level of service in a bounded response time. Since most general memory
managers require some form of garbage collection, a process that is inherently non-deterministic,
real-time embedded systems are often unable to use these memory managers.
When memory becomes low in the traditional mark and sweep garbage-collection algorithm, the system
stops all user processes, locates the set of unreachable objects or memory blocks, and frees them. To
accomplish this task, it must examine every object reference, such as local variables and static structures.
Each referenced object is checked to determine whether it is already marked. If an object is not marked, it
is marked and all its references are processed; otherwise the system moves on to the next reference. When
this process is complete, any unmarked objects are deemed unreachable and can therefore be recycled.
This marking technique is superior to reference-counting schemes because it correctly detects groups of
dead objects that are referenced only by other dead objects. Figure 1 and Figure 2 show before and after
pictures of this process, respectively. Of course, the heap can become low on free space at any time, and
the time required to mark and sweep is proportional to the number of objects and references. The result is
a pattern in which the application periodically becomes unresponsive or stalls for a brief time. Such stalls
are unacceptable in real-time systems, even soft real-time systems.
One way to prevent fragmentation is to allocate pools of the same fixed-sized memory blocks so that a
careful implementation can have fixed execution times for allocating and freeing the blocks. More
general heap implementations always involve iterating through lists that can vary in size. The VSMM
eliminates fragmentation by using heaps that consist only of fixed-sized memory blocks. Moreover, all
1
2
A
1
1
2
A
1
Figure 1. Fragmented Memory Before Garbage Collection
Unreachable space
Marked space
Unreachable space
Marked space
B
2
Freescale Semiconductor, Inc.
D
1
Figure 2. Memory After Garbage Collection
C
2
For More Information On This Product,
D
1
Go to: www.freescale.com
E
1
E
1
G
1
F
2
H
1
G
1
H
1
2
I
Free Space
Free Space