Solved

Heap memory fragmentation in embedded environments

Posted on 1998-05-01
9
485 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
  • 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 100 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
 
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
6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

 
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

What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

Join & Write a Comment

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…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

760 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

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now