VXworks malloc behaviour
Sergi Casas
Ibrahima Ndoye wrote:
> Hi,
>
> Does anyone know how malloc operates inside vxWorks i.e when vxWorks
> does the garbage collection ?
I think "Garbage Collection" applies only to the process used by Lisp
or Java (among others) to recover non-referenced blocks of memory
(which in C would result in memory leaks). VxWorks does nothing like
that,
even to deallocate blocks that "belong" to a task when it is destroyed.
There is no "task ownership" concept in vxWorks memory model, because it
is more a "multi-threading" model ("lightweight processes") than
a "multitasking" model.
Probably what you mean is "free-block coalescence", the mecanism to
merge
fragmented, contiguous free blocks into a single bigger one. This is
done
in vxWorks at every call to free(). Memory blocks in vxWorks, as in many
other general purpose implementations (not the most efficient, but very
generic), are managed as nodes in a linked list; when you add a free
block
into the free-list, vxWorks not only adds the node to the list, but
rather
looks into adjacent nodes and "coalesces" the new one with the
contiguous
blocks it may find, even including two previously separated blocks into
a single node if the incoming block happens to fill the gap between
them.
Hope this helps.
--
Sergi Casas
Software Engineer (R&D)
Hewlett-Packard Company
|===========================================================================|
| "The question of whether a computer can think is no more interesting
than |
| the question of whether a submarine can swim." E. W.
Dijkstra |
|===========================================================================|
Mike Anderson
At 11:47 PM 1/23/97 PST, you wrote:
>Submitted-by nd...@ocegr.fr Thu Jan 23 23:47:35 1997
>Submitted-by: Ibrahima Ndoye <nd...@ocegr.fr>
>
>Hi,
>
>Does anyone know how malloc operates inside vxWorks i.e when vxWorks
>does the garbage collection ?
>
VxWorks doesn't *do* garbage collection. However, it does coalesce
adjacent free partitions into larger partitions upon a "free" call.
Also, by default, when a task in VxWorks exits, it's TCB is automatically
freed, but its stack is not. To free the stack automagically on
task exit, you must set the task flag VX_DEALLOC_STACK either when
you spawned the task or using taskOptionsSet during task runtime.
Of course, this garbage collection issue brings up an interesting question
in my mind. How does the Java virtual machine (which is garbage collection
from Hell as an applett runs) behave in the VxWorks environment? I assume
that the Java VM mallocs a large block of RAM and then does GC internally
as needed, but is this actually the case? And, what impact does the Java
VM have on real-time performance? If I design something using the Java
VM, should I dedicate a CPU to that function to avoid compromising my
real-time apps? Inquiring minds want to know...
HTH,
==============================================================================
__ Real-Time System Development, Integration, Training and Services
//\\
// \\ Mike Anderson
// /\ \\ Chief Engineer Voice : (703) 448-0210 ext. 235
// / \ \\ SPARTA, Inc. FAX : (703) 893-5494
// \ \\ 7926 Jones Branch Drive EMAIL : m...@mclean.sparta.com
\\ \ // Suite 900 Web : http://www.mclean.sparta.com
\\ \ / // McLean, VA 22102
\\ \/ // "Software development is like making
\\ // a baby... You can't make a baby in one
\\// month by impregnating nine women.
-- "Pride in Performance" Some things just take time."
==============================================================================
Mike Anderson
At 10:11 AM 1/24/97 PST, you wrote:
>Submitted-by se...@bpo.hp.com Fri Jan 24 10:10:57 1997
>Submitted-by: Sergi Casas <se...@bpo.hp.com>
>
>
>
>Check http://www.softplc.com/machj/
>
Thanks for the info, Sergi. Now, I wonder if WRS really implemented it
that way?
Regards,
h.j. bae
the way vxworks coalesce adjacent free blocks can cause severe
memory fragmentation in many situations.
i've tried to replace the memLib with my own bucket oriented
memory allocater (similar to BSD malloc) but i gave up after
a while. there seemed to be lots of things that depend on
particular things from memLib to exist. (you can't simply
replace malloc/free, etc.) kinda hard to do with having source.
has anyone done a complete replacement of malloc/free/etc stuff
in vxworks without source code?
--
http://www.pso.com
mailto:h...@pso.com
Sergi Casas
Mike Anderson wrote:
> Of course, this garbage collection issue brings up an interesting question
> in my mind. How does the Java virtual machine (which is garbage collection
> from Hell as an applett runs) behave in the VxWorks environment? I assume
> that the Java VM mallocs a large block of RAM and then does GC internally
> as needed, but is this actually the case? And, what impact does the Java
> VM have on real-time performance? If I design something using the Java
> VM, should I dedicate a CPU to that function to avoid compromising my
> real-time apps? Inquiring minds want to know...
Check http://www.softplc.com/machj/
They claim they have a real-time garbage collector.
In fact, given the clever approach of Java to Garbage Collection, I don't
really see the need for a special "real-time" thing: let me explain.
In Java, the Garbage Collector runs as the lowest priority thread, which means
that while there is nothing to be done it will run, otherwise it waits till
all the memory has been used and some thread still needs more; in that case
the thread blocks and the garbage collector starts working till there is
enough free space for the task to go on.
As I see it, real time applications are typically reactive, event-driven
systems or periodic processes (this is, time-event driven), and they don't
usually take all the CPU (in fact, one usually allows for some CPU margin
just in case things go too tight). What real time applications need is that
when some external or timing event happens the response to it must be
deterministically within certain time limits, right?
Then, the only thing one has to take into account when designing real-time
systems with Java is to make sure that the ratio of busy vs. idle time for
application tasks in a given CPU leaves enough room for the Garbage
Collector to keep memory free enough so that no application task has to
sit waiting for free memory.
The only pathological application is the one that has one or more low
priority background tasks (accounting, monitoring, reporting) which never
block but yield the CPU only due to their low priority in a priority-driven
preemptive environment such as vxWorks (much like the Garbage Collector
itself!!). In those cases one must make sure that those continuous tasks
periodically yield the CPU and leave it idle enough for the Garbage
Collector to do its work.
In summary, the only problem with Java-style Garbage Collectors in real
time is guaranteeing that the system will NEVER reach the extreme memory
situation so as to force any task to sit waiting for any undeterministic
garbage collection process. The engineer has to chose a powerful enough
CPU that is able to run enough of the Garbage Collector during
application idle time. No need to dedicate a whole CPU to that process
as far as the system's CPU is powerful enough, because response times are
not compromised by the GC.
Is that right ?
PD: LISP is different 'cause common implementations are not multithreaded
and always wait to the extreme out-of-memory situation to start a non-
deterministic Garbage Collection process while the requesting program
waits.
h.j. bae
i've been playing around with Boehm-Demers-Weiser conservative garbage
collector which allows incremental and generational garbage
collection. it requires MMU support though. many java virtual
machine -> C compilers use this garbage collector. available free:
ftp://parcftp.xerox.com/pub/gc/gc.html
i have been looking at the java stuff for some time now for embedded
and realtime usage. i've come to the conclusion that a JVM -> C
compilation is the only way to go.
Gerardo Pardo-Castellote
>> Submitted-by se...@bpo.hp.com Fri Jan 24 10:10:57 1997
>> Submitted-by: Sergi Casas <se...@bpo.hp.com>
>> In fact, given the clever approach of Java to Garbage Collection, I don't
>> really see the need for a special "real-time" thing: let me explain.
>> In Java, the Garbage Collector runs as the lowest priority thread, which means
>> that while there is nothing to be done it will run, otherwise it waits till
>> all the memory has been used and some thread still needs more; in that case
>> the thread blocks and the garbage collector starts working till there is
>> enough free space for the task to go on.
... details ommitted ...
>> In summary, the only problem with Java-style Garbage Collectors in real
>> time is guaranteeing that the system will NEVER reach the extreme memory
>> situation so as to force any task to sit waiting for any undeterministic
>> garbage collection process. The engineer has to chose a powerful enough
>> CPU that is able to run enough of the Garbage Collector during
>> application idle time. No need to dedicate a whole CPU to that process
>> as far as the system's CPU is powerful enough, because response times are
>> not compromised by the GC.
>> Is that right ?
>> PD: LISP is different 'cause common implementations are not multithreaded
>> and always wait to the extreme out-of-memory situation to start a non-
>> deterministic Garbage Collection process while the requesting program
>> waits.
The problem with the Java garbage collector is that although it runs as
the lowest priority task, as soon as it starts running, it promotes itself to
the highest priority, and then runs to completion. I.e. it is not
capable of doing "incremental" garbage collection. This makes it really
unusable for real-time IMHO because even if you never exhaust the memory,
every now and then, whenever the GC starts running it will lock up the
system for an un-specified and un-controllable ammount of time. This
yields the same behavior as the LISP GC that Sergi describes.
My understanding is that the next release of Java will support incremental
garbage collection... then, depending on the granularity of the "increments"
it may stop being a problem as Sergi describes.
-Gerardo
===========================================================================
= = =
= Gerardo Pardo-Castellote = email: pa...@rti.com =
= Real-Time Innovations, Inc. = Phone: (408) 720-8312 =
= 155A Moffett Park Drive, Suite 111 = Fax: (408) 734-5009 =
= Sunnyvale, CA 94089 = http://www.rti.com =
= = =
===========================================================================
Rainer Joswig
In article <32E8FB...@bpo.hp.com>, Sergi Casas <se...@bpo.hp.com> wrote:
> Mike Anderson wrote:
> PD: LISP is different 'cause common implementations are not multithreaded
Multithreaded Lisp implementations are common:
Symbolics Common Lisp
Macintosh Common Lisp
Allegro Common Lisp
Liquid Common Lisp
LispWorks
...
> and always wait to the extreme out-of-memory situation to start a non-
> deterministic Garbage Collection process while the requesting program
> waits.
That is wrong, too.
Most Common Lisp implementations have very clever GC implementations
like generational incremental GCs and ephemeral GCs. Symbolics combines
a Lisp system with different memory management strategies:
- full GC
- full in-place GC
- dynamic copying generational GC
- ephemeral GC
- reseource management
Lisp is the mother language of GCs. There is a great deal of
literature on it.
Bret Indrelee
>> in my mind. How does the Java virtual machine (which is garbage collection
>> from Hell as an applett runs) behave in the VxWorks environment? I assume
>> that the Java VM mallocs a large block of RAM and then does GC internally
>> as needed, but is this actually the case? And, what impact does the Java
>> VM have on real-time performance? If I design something using the Java
>> VM, should I dedicate a CPU to that function to avoid compromising my
>> real-time apps? Inquiring minds want to know...
>In fact, given the clever approach of Java to Garbage Collection, I don't
>really see the need for a special "real-time" thing: let me explain.
>In Java, the Garbage Collector runs as the lowest priority thread, which means
>that while there is nothing to be done it will run, otherwise it waits till
>all the memory has been used and some thread still needs more; in that case
>the thread blocks and the garbage collector starts working till there is
>enough free space for the task to go on.
>
>systems or periodic processes (this is, time-event driven), and they don't
>usually take all the CPU (in fact, one usually allows for some CPU margin
>just in case things go too tight). What real time applications need is that
>when some external or timing event happens the response to it must be
>deterministically within certain time limits, right?
The problem is that you have to make sure that the high priority tasks can complete
in time, regardless of which low priority tasks have run.
You have described a priority inversion (high priority Java task waits for
low priority garbage collector), which is bad. It makes it tough to reliably
schedule a real time system. It really depends on how hard your deadlines are,
if your system can survive missing a deadline occationally then it probably
isn't as bad.
-Bret
--
Bret Indrelee
br...@bit3.com #include <std_disclaimer.h>
Christopher Pinkard
Our approach is also bucket oriented. Our design does a few
large mallocs at startup, and each area is administed by a
pair of utilities mallocNN and freeNN where NN represents the
block size. Thus we allocate and free similar size records
from separate pools. This is easier for us because we can
model and bound are throughput in terms of the objects that
are allocated and deallocated. This is not the most efficient
use of memory by a long shot, it is simply the easiest to
create and maintain.
------------------------------------------
may all your goats be free of fleas
and may your camels never spit
------------------------------------------
Sergi Casas
Gerardo Pardo-Castellote wrote:
> The problem with the Java garbage collector is that although it runs as
> the lowest priority task, as soon as it starts running, it promotes itself to
> the highest priority, and then runs to completion. I.e. it is not
> capable of doing "incremental" garbage collection. This makes it really
> unusable for real-time IMHO because even if you never exhaust the memory,
> every now and then, whenever the GC starts running it will lock up the
> system for an un-specified and un-controllable ammount of time. This
> yields the same behavior as the LISP GC that Sergi describes.
Yes, I completely agree. However, this is not a inherent failure of
Java to fulfil real-time requirements: the JVM Spec clearly leaves
the Garbage Collector implementation open to satisfy different needs
in different applications. What happens is that current Sun's implementation
is a typical mark-sweep algorithm that needs absolute control of the heap
during the process. As a consequence, current WindRiver's supplied
implementation has the same flaw and, as they say in their Tornado for Java
literature, it is not suitable for hard real time. I'm pretty sure that
not only for real-time, but also for user interface responsiveness, Sun's
implementation is likely to change.
> My understanding is that the next release of Java will support incremental
> garbage collection... then, depending on the granularity of the "increments"
> it may stop being a problem as Sergi describes.
I think that in an interpreted JVM it should be very easy to split
the mark-sweep algorithm updating the "mark" traces at every object
creation, reference, or assignment and then leaving to a background
process the "sweep" part of the algorithm. Hence the granularity of the
Garbage Collector would be *almost* that of each single free().
I guess it's something like this the reason for MachJ guys to claim they have
a real-time Garbage Collector.
Thanks a lot for the pointer, it's a very interesting source about the topic.
On the other hand, while I agree on that Java-byte-code-to-C static
(non JIT) compilation seems a very good way to go for embedded realtime,
I don't really see the need to use such a complex Garbage Collector in
Java. It's being used 'cause it compiles to C and then they use a Garbage
Collector for C, but would be easier and much more efficient to take
advantage of the byte-code-to-C compilation step to generate C code
for "marking" during application execution time, and then doing the
"sweep" phase in background. No need for MMU. It is "incremental" instead
of "generational", with very high "granularity". The compiler has to be
a bit smarter, though.
All this becomes more difficult in native Java environments such as the
"nanoJava" cores from Sun, because there is no Virtual Machine interpreter
nor intermediate byte-code-to-C compiler, right ?
Cheers.