malloc in embedded systems

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
I have an embedded system using an RTOS.  The one weakness of this
RTOS is that it has a weak memory manager.  You can pre-define the
block size that will be created in the memory pool, but this block
size is always fixed.  That means that it won't be able to allocate
the exact amount of memory that you need - it will turn out to always
be too much.  The only exception to this is if I pre-define the block
size to be the same as the size of my most often used data object.
But I have two different types of data objects (ie. different sizes),
and they are both used often. Soo, I have avoided using this memory
manager, and have been using static arrays instead.

I have a list of data objects that I will need to create during run
time.  The number of objects on this list at any given time during
runtime is unknown, although there can a be worst case maximum limit
to the size of this list.
So, my question is this:  Which is preferable for my situation,
malloc() or pre-defining a static array that is equal to the worst
case size ?


Thx.
Cheers,
Albert

Re: malloc in embedded systems
Quoted text here. Click to load it


I prefer static fixed-size allocations (just arrays / structs in code)
to dynamic allocation due to:

- there is no risk of fragmentation,
- if there is over-allocation, it's known at build time,
- there is no allocator overhead.

Are you going to free() the blocks?

If you have a complete heap with allocation and freeing of very
varying-size objects, you have a strong risk of memory fragmentation:
there is plenty of space, but no free areas large enough to
satisfy an allocation request. This is a very difficult situation
in an embedded system, as there is usually no user interface
suited for an error message of not enough memory.

Admitted, there are allocation schemes which minimise the risk
of fragmentation (e.g. the buddy system), but it comes for
a price: the allocation block size is usually limited to some
pre-defined sizes.

Your RTOS probably tries to get rid of the fragmentation problem
by fixing the allocation block size.

There is a way to recover from fragmentation: compressing the
allocated blocks together to combine all free blocks into one
large block. This is defragmetation or garbage collection. There
is a requirement, though: the pointers to the allocated blocks
have to be chaqnged to follow the movement of the allocated
blocks. This is often done by using indirect addressing to the
allocated blocks via an address vector in the memory allocator. An
example of thid kind of solution is the memory allocation handle
method in the early Windowses.

In general, you cannot get a dynamic allocation scheme with freely
selectable block size, no risk of fragmentation, no memory
space overhead and no garbage collector.

For more information, get Don Knuth's The Art of Computer Programming.

HTH

Tauno Voipio
tauno voipio @ iki fi


Re: malloc in embedded systems
Quoted text here. Click to load it

Perhaps a very basic compromise solution would be to include an allocater
that maintains two or more pools - each pool having different but fixed size
blocks.  When you require a block you check the pool of smallest blocks
first, then if they are too small or there are none left move on to check
the pool the next size up ... etc. until you find a free block.  This type
of scheme can then be tuned as you learn how your system is using memory
(assuming it cannot be determined up front).

In your RTOS you can have the idle process looking at how the pools are
used - how often a pool runs out of blocks, etc.   Information that can be
used to make adjustments on your next build.

Regards,
Richard.

http://www.FreeRTOS.org



Re: malloc in embedded systems

Quoted text here. Click to load it

malloc() is not really a good choice.

I do earn my money designing RTOS (and with this memory managers). And
I found that a fixed-buffer size allocator is best when it comes to
memory-usage and determinism.

But other than the RTOS (which ?) you are refering to, we give you the
choice of a) multiple pools and b) either 4,8 or 16 buffersizes per
pool.

With a little tuning of the buffersizes, it results in no
fragmentation (external and internal) and still very fast !

---
42Bastian
Do not email to snipped-for-privacy@yahoo.com, it's a spam-only account :-)
We've slightly trimmed the long signature. Click to see the full one.
Re: malloc in embedded systems
snipped-for-privacy@yahoo.com (phileo) wrote in message
Quoted text here. Click to load it


Perhaps this is good enough, it gives predictable performance and you
can more easily specify how the system will fail in case of an overload.

Quoted text here. Click to load it


The "buddy system memory allocator" might be a reasonable compromise.
A buddy system allows block sizes of e.g. 100, 200, 400, ..., 3200 bytes.
There is an implementation in the ABCD Proto-Kernel(tm) source code
available on the web site below. Integration into the kernel requires the
use of mutual exclusion semaphores.

Anyway, the selection of a good allocator is a debatable issue on any
system.

- Thierry Moreau

CONNOTECH Experts-conseils inc.
9130 Place de Montgolfier
Montreal, Qc
H2M 2A1

Tel.: (514)385-5691
Fax:  (514)385-5900

http://www.connotech.com
e-mail: snipped-for-privacy@connotech.com

Re: malloc in embedded systems
Quoted text here. Click to load it
 
I would recommend using the worstcase limit and creating a static
array of the objects. If you have to support the worstcase size, you
are not wasting any memory by dimensioning to the worst case.

Sandeep
--
http://www.EventHelix.com/EventStudio
EventStudio 2.0 - Real-time and Embedded System Design CASE Tool

Re: malloc in embedded systems
snipped-for-privacy@hotmail.com (EventHelix.com) wrote in message
Quoted text here. Click to load it

So is the "create on demand" philosophy invalid in this case ?
The worst case scenario would only occur if a certain combination of
event scenarios occur.  The probability of this specific combination
of event scenarios occuring is very low - something in the order of 1
in 10000.
Also, does that mean the embedded system philosophy is "prefer static
objects of malloc'd objects, unless you cannot avoid using malloc'd
objects."  ??


Thx.
Cheers,
Albert

Re: malloc in embedded systems

Quoted text here. Click to load it

And what do you do when that unlikely situation occurs ? Hide your
head in the sand (e.g. display Blue Screen of Death) ?

In many systems, hiding your head in the sand is simply not an option,
so you really have to allocate the resources required by the worst
case situation or manipulate the environment, so that this kind of
combinations of events can not occur (e.g. by high level flow control
of incoming requests).

Paul
 

Re: malloc in embedded systems
Quoted text here. Click to load it

I believe you will find that Murphy's Law covers this situation.  You should
see what we have to do to ensure that sort of thing does not happen with
our avionics software (people do not have a sense of humor when the
airplane falls out of the sky ..).  If it can happen, it will -- and if you
are not
the one who has to fix it, the next poor guy trying to figure out why it
crashes every third week when it is sunny out or whatever.

mikey



Re: malloc in embedded systems
Hi Phileo,

Most of the time, static memory allocation is better for
realtime application. But some application needs a good
dynamic memory allocator to optimize the memory available.
ie: data recorder, C++ GUI task running over RTOS, etc...

I had to do this with VxWorks. But the memory allocator was
really weak, generating too much fragmentation. I replaced it
by a port of Doug Lea's memory allocator : now, it's much
faster and reliable.

check this link : ftp://gee.cs.oswego.edu/pub/misc/malloc.c

If you needs a port to vxWorks 5.x, I had the source
(made by Bill Pringlemeir).

Regards
Emmanuel.

phileo wrote:

Quoted text here. Click to load it
...
...

Re: malloc in embedded systems
Quoted text here. Click to load it

Please do not toppost.

For a malloc system dependant only on flat byte addressing and the
availability of sbrk(), check out my nmalloc.zip.  It compiles
under gcc, and that limitation is largely due to the use of macros
with varargs for fundamental initial debugging.  On the x86 the
result is about 3k bytes.  The associated malldbg package (part of
the zip file) takes about 2.5k bytes, and allows extensive user
level debugging and analysis.  

I would be interested to know how easily it ports to other
systems.  Everything has been deliberately kept as close to
standard C as possible.  It is under the DJGPP licence, so there
are no barriers to usage in other systems.

The original reason for creation was the O(n) action of free,
which is now O(1).  This also applies to realloc.  It is not a
buddy system allocator, but it avoids fragmentation as far as
possible.  The memalign portion is not done, but not needed for
anything known except porting gcc.  The hooks for user level
debugging are very flexible and do not require any recompilation,
although they do require standards mandated zeroing of static
storage initialization.

It, with documentation info style, can be found at:

  <http://cbfalconer.home.att.net/download/

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.

Site Timeline