Solved

Heap memory fragmentation in embedded environments

Posted on 1998-05-01
9
536 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 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
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!

 
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

Technology Partners: 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

Suggested Solutions

Title # Comments Views Activity
convert char array to number in c 5 91
sorting efficency of sorting algorithm 30 132
c++, dynamic object by json 1 60
Precision Problem in C++ 7 50
Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

726 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