Re: Real-time dyn allctn (was: Ada vs C++ vs Java)

[Niklas Holsti <nholsti@icon.fi>]

Nick Roberts wrote:
> 
> In the general case, the pattern of calls that will be made during the
> execution of a program - even a 'hard' real-time one - will be unpredictable
> (because it depends on unpredictable input values). The maximum possible
> stack usage can be calculated. However, this figure will often be vastly
> greater than any stack usage that will occur in practise (and thus be
> useless). The occurance of recursion which is controlled by an input value
> usually makes the aforementioned effect inevitable.

For real-time programs, I've found the maximum stack usage, as
computed by the compiler, to be very useful, and not a severe
overestimate. Of course, these programs do not use recursion --
to me, this restriction is quite natural, since the data in
real-time programs are usually not of recursive types.

Even if you think that the computed stack usage is an overestimate,
what is the alternative? Guess on a "reasonable" value, and hope
it works? Or use a deeper, context-sensitive static analysis to
eliminate infeasible call paths? The latter is OK, if you can do it...

> I also feel that the sentiment "don't use dynamic allocation in real-time
> programs" is somewhat naive, to put it mildly. I rather suspect that, in
> rejecting the use of 'malloc' or 'new', the programmer simply replaces these
> forms of dynamic allocation with others (a statically declared array used to
> hold dynamically changing data, for example), for no better reason than
> superstition.

I'll comment on this below.
 
> There is no need to take this attitude for any kind of program.
> 
> Taking the example of a program which flies an aeroplane, you will want to
> adopt a strategy of absolute robustness ('never crash').
> 
> [1] This means that, if the program uses dynamic allocation, either it must
> be possible to statically determine that memory will never be insufficient,
> or there must be a means of: (a) reliably detecting insufficient memory; and
> (b) upon detecting this, returning the software to a state that enables it
> to continue safely flying the aeroplane. These requirements are not usually
> impractical to achieve.

Yes of course (a) and (b) are essential. And using other forms of
dynamic allocation, such as bounded arrays of preallocated blocks,
is the traditional (and workable) method of achieving these
requirements.

Have you practical experience of achieving these requirements with a
standard or custom-made malloc(), without constraining the distribution
of the number of allocated blocks over block size? It seems to me that
the memory fragmentation problem will not be easy to beat, without
a lot of application-specific analysis.

> [2] If the software has interrupt servicing time constraints, the interrupt
> servicing routines which have these constraints must either: (a) be able to
> use the dynamic allocation in a way which is predictably fast enough; or (b)
> not use dynamic allocation. These conditions do not need to be imposed on
> any of the other parts of the software (if there are any).

Since we are considering real-time programs, we should omit the "other
parts". So your case (a) is the only real case, and it is rather common
opinion that the typical malloc()/free() implementations are
not predictably fast enough (I don't have any first-hand data, though).

> It may well be that typical supplied dynamic allocation facilities are too
> crude or unreliable to satisfy the special requirements of a real-time
> program. But the answer is not to simply abandon the use of 'malloc' and
> replace it with a large number of ad-hoc, hybrid solutions (involving arrays
> and indexes). Instead, all that is required is to reprogram the dynamic
> allocation facilities to your requirements: you may need a 'malloc_a', a
> 'malloc_b', and a 'malloc_c', or whatever. The result is likely to be better
> source code and better performing software, with no reduction in robustness.

Your malloc_a() etc. seem to be exactly the "other forms of dynamic
allocation" that you criticise earlier. Could you explain the
difference? Must malloc_x return a "pointer" (and not an index) to
count as true dynamic allocation?

> In addition, in view of my comments earlier in this posting about the
> dynamic nature of allocation on the stack, it will often be the case that my
> comments above about dynamic allocation can be applied to stack allocation
> as well (saving a lot of memory space wasted on making sure the stack cannot
> crash).

I don't understand your meaning here. Please elaborate. Do you mean
some application-specific method of allocating and deallocating
stack space? That would interfere wit typical compilers...

---
Niklas Holsti
Working at but not speaking for Space Systems Finland Ltd.