Heap memory fragmentation in embedded environments

What are the options for dealing with heap memory fragmentation in a real time embedded system?
richardbellairsAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

nietodCommented:
Are you asking about options for preventing fragmentation or for cleaning it up?  Are you talking about an application that uses a heap or that is providing one?  (i.e.  do you manage the heap or is this a heap provided by the C++ run-time library and out of your hands).
0
alexoCommented:
Best way of dealing with heap fragmentation is making sure it does not appear.

Provide multiple heaps and allocating fixed sizes (or in multiples of a fixed size) from each.  E.g., 85 byte allocations from one heap, 7456 byte allocations from another heap, multiples of 453 from a third one, etc.

This can be achieved by subclassing the operators new, delete, new[] and delete[] for your classes.

Anther possible solution is periodic heap compaction but I don't think it is suitable for RT systems.

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
nietodCommented:
But If you do allocations that are multiples of the fixed size, you could be faced with problems caused by fragmentation again.  For example if you have a heap for 32 byte allications and want to allocate 64 bytes from it you may have to search past lots of 32 byte free spaces before funding a 64 byte free space.  However, this should be less of a problem than if all allocations were from a single heap.  

Since, you don't want to provide a seperate heap for every size allocation (unless you know that the allocations will be in a minimal number of sizes) You probably would want to the allocation sizes in the heaps to go in steps.  Like a heap for 1-16 bytes.  another heap for 17-32 etc.  You would still allocate a fixed size from these heaps, you would just waste a little at the end.  How would you chose what sizes to use?  I guess in part it would depend on the range in sizes you would have to allow for.
0
Cloud Class® Course: Certified Penetration Testing

This CPTE Certified Penetration Testing Engineer course covers everything you need to know about becoming a Certified Penetration Testing Engineer. Career Path: Professional roles include Ethical Hackers, Security Consultants, System Administrators, and Chief Security Officers.

alexoCommented:
... which boils down to using multiple heaps :-)

Another possible solution is <gasp!> not to use the heap at all.
If the maximum memory requirements are known in advance and reachable (they usually do in embedded systems), you can preallocate all the memory you may need (even statically).
0
nietodCommented:
alex,
You missunderstood me.  Not suprising considering my explanation.  My point/question was that unless there are minimal number of sizes of allocations needed (which is possible in an embedded system) then you don'e want seperate heaps for each size.  That could be a lot of heaps!.  You would probably want each heap to handle a range of sizes.  It would always allocate a fixed size and possibly waste a little at the end.  
0
alexoCommented:
Todd, I understood you perfectly.  We were both talking about multiple heaps, the differences were the criteria for chosing the heap.  In my experience, the number of object types that are dynamically allocated in an embedded system usually allows one heap per allocation size (or multiple thereof).  It that is not the case than your suggestion is probably more suitable.

On the other hand, I still think that in some embedded systems one can eliminate dynamic allocation altogether.
0
nietodCommented:
Yes, I see that, now.  Although one area where you might have a weakness would be if you had character arrays to allocate.  These could be any length.  But you could have a heap just for these and then a heap for each object type.  

Technically what is an embedded system?  My company produced a program that was placed on chip (EPROM?) for controlling firetruck ladders.  The program though whas witten in ordinary C and used the standard run-time library etc.  Is that considered an embedded sytstem?
0
alexoCommented:
An embedded system is any system where the computer is acting as a contoller of a device and is embedded in it (yea, I know...)  Generally you have a fairly underpowered processor (80188, i386 but there are exceptions such as a PowerPC), limited amount of RAM, a real-time OS, no terminal/keybord/mouse.
Examples abound.  From your microwave to the F15i targeting system.

richardbellairs, can you give us more info about your system?
0
alexoCommented:
The autograder hits again...
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.