?
Solved

Heap memory fragmentation in embedded environments

Posted on 1998-05-01
9
Medium Priority
?
556 Views
Last Modified: 2010-07-27
What are the options for dealing with heap memory fragmentation in a real time embedded system?
0
Comment
Question by:richardbellairs
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 4
9 Comments
 
LVL 22

Expert Comment

by:nietod
ID: 1170027
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
 
LVL 11

Accepted Solution

by:
alexo earned 200 total points
ID: 1170028
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
 
LVL 22

Expert Comment

by:nietod
ID: 1170029
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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 11

Expert Comment

by:alexo
ID: 1170030
... 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
 
LVL 22

Expert Comment

by:nietod
ID: 1170031
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
 
LVL 11

Expert Comment

by:alexo
ID: 1170032
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
 
LVL 22

Expert Comment

by:nietod
ID: 1170033
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
 
LVL 11

Expert Comment

by:alexo
ID: 1170034
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
 
LVL 11

Expert Comment

by:alexo
ID: 1170035
The autograder hits again...
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question