Re: Can OO be successful in real-time embedded systems?

Re: Can OO be successful in real-time embedded systems?

[Jon S Anthony]

In article <316BF0C5.1FE1@condat.de> Henning Rietz <rietz@condat.de> writes:

I would believe that Ada folk have more to say on this than most.  So,
I am crossing it over to c.l.a too...

/Jon




> To whom it may concern:
> 
> For the last couple of weeks I have been involved in a major survey on
> the use of object oriented techniques in the area of telecommunications
> (mainly in the German speaking region).
> I can say "everybody" is using OO in some areas (mainly network
> management, switch provisioning, customer care), BUT there are (almost)
> no examples in the area of (small) embedded systems, main reasons for
> that being:
> 
>         - "OO systems are too slow"
>         - "OO systems eat up too much memory"
> 
> I believe, that this is not necessarily true but heavily related to
> experience. Now I=B4m asking you:
> 
>           How far "down" does the application of OO really go?
>           How far will it go in the future?
>           Who develops commercial(!) embedded real-time systems
>               using OO methods and languages?
>           Will OO ever be of major importance in that area?
> 
> If you have an opinion concerning these questions please share it with
> me! Even those who think they=B4ll "never use that OO-stuff".
> 
> Regards,
> 
> Henning
> -- =
> 
> Henning Rietz c/o
> Condat GmbH                             Telephone:      +49.30.39094-179
> Alt-Moabit 91D                          Fax:            +49.30.39094-300
> 10559 Berlin, Germany                   E-Mail:         rietz@condat.de
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Can OO be successful in real-time embedded systems?

[Richard Riehle]

On 5 May 1996, Paul Carlton wrote:

> Absolutely!!!  And recommended!!!
>
> We have a full-blown real-time predictive dialer designed with
> Raumbaugh/CRC techniques and implemented in c++.  Runs like a
> screaming demon!!

  Agree.  Used carefully, and selectively, object technology can be
  an excellent approach to embedded systems.  The question is whether
  all aspects of OO technology are appropriate.

  Also, OO technology has been used on countless Ada embedded,
  real-time, safety-critical projects for years.  In fact, this
  has been a niche market for Ada in which OO has achieved a fair
  amount of respectability.

  The new Ada 95 standard raises the ante, and makes OO technology even
  more attractive for embedded systems.  Already, OOP projects, using
  Ada 95, are in process in both the defense and non-defense domain.

  A key question for Ada developers has been the reliability associated
  with dynamic binding.  That issue comes in two flavors.  1) Is it
  possible to dynamically invoke a wrong or non-existent method, 2) Can we
  predict with certaintly that we will always meet hard deadlines.  The
  first issue is easily accomodated under the rules of the new Ada
  standard.  The second is more difficult.  Since a method is selected
  at run-time, it is impossible to guarantee the deterministic properties
  one requires for hard, real-time schedules.

  The consequence of the above issue is that many embedded systems
  developers approach dynamic polymorphism with great caution -- even
  avoid it altogether. Fortunately, for those of us in the Ada community,
  we can benefit from all the other capabilities of OOP, such as
  inheritance and encapsulation,  while choosing to not to use dynamic
  polymorphism when it could be dangerously non-deterministic.

  Richard Riehle

Re: Can OO be successful in real-time embedded systems?

[Richard Riehle]

 Robert A Duff wrote:
 >
 > Run-time dispatching is just like a case-statement, except the branches
 > are scattered all over the code.  To do white-box testing, you have to
 > track down all overridings of a given procedure.  Having done that, it's
 > no harder than testing a case statement.  So, I think you want a tool to
 > do that tracking down.  I use "grep" for that purpose, but one could
 > imagine something more helpful.

   I am aware of the notion of dynamic case vis a vis dispatching. Also,
   the built-in safety of Ada 95 has not escaped my notice.

   However, in hard, real-time systems (HRTS), run-time dispatching is a
   little more of an issue than a simple case statement.  The controlling
   factor is whether we can predict that a certain sequence of actions
   will be time-determinate.

   Granted, there will be many situations where this will be easily
   predicted.  However, extensive use of run-time dispatching can, I
   believe, make it more difficult to predict the kind of timing
   requirements which often characterize HRTS software environents.

   Since Ada 95 is new, there is likely to be little experience with
   dispatching in HRTS.  I am simply suggesting that it be approached
   conservatively.  Perhaps I am just too much of a "scaredy-cat" about
   such things.  However, I know I am not alone in this concern.

   Richard Riehle

Re: Can OO be successful in real-time embedded systems?

[Robert A Duff]

In article <m0uHHBP-0000ztC@crash.cts.com>,
Robert C. Leif, Ph.D. <rleif@MAIL.CTS.COM> wrote:
>Worse yet, how do you test dynamic binding for a medical or similar critical
>application.?  I suspect that any savings in code creation cost would be
>offset by the testing costs . I do not see an obvious way to do white box
>testing of run-time dispatching.

Run-time dispatching is just like a case-statement, except the branches
are scattered all over the code.  To do white-box testing, you have to
track down all overridings of a given procedure.  Having done that, it's
no harder than testing a case statement.  So, I think you want a tool to
do that tracking down.  I use "grep" for that purpose, but one could
imagine something more helpful.

>...  I do want to employ a tool to tell me did
>anyone in the group do run-time dispatching.

I think you *really* want a tool that tells you, for any given call,
which subprogram bodies might get executed.  Once you have that
information, testing is no harder than testing a case statement.

Timing analysis is similar: for a case statement, you need to worry
about the worst case, over all branches of the case statement.  For a
polymorphic call, you need to worry about the worst case, over all
overridings.  The only difference is that it's harder to track down all
the overridings, because they're scattered about.  (I have no idea how
you can really do worst-case timing analysis on modern machines, with
all kinds of complicated caching and whatnot.  But that's a separate
issue.)

Proofs are similar: you need to track down all overridings.
Alternatively, you can take the Eiffel approach, where you assert
something about the original operation, and prove that all overridings
obey that assertion.

You also need to deal with modifications to code.  For a case statement,
if somebody adds a new branch, you need to re-analyze, if your analysis
depends on that information.  Likewise, if you add a new overriding, you
need to re-analyze if your original analysis depended on tracking down
all overridings.

>...  I know that I could buy a
>compiler with the Safety and Security Annex. However, that is ridiculous
>over-kill. You have provably heard my line, that Ada 95 is the Safety and
>Security annex of C++.

That's an amusing typo.  How can you "prove" that I've heard your line?
Well, I guess if you read *this*, you can prove it beyond a reasonable
doubt.  ;-)

>...  First one switches a C or C++ developer to Ada 95,
>then, latter on, one can start discussion of the Safety and Security Annex.

But beware: there's a lot more to safety than is codified in the SS Annex.

- Bob

Re: Can OO be successful in real-time embedded systems?

[Ken Garlington]

Robert A Duff wrote:
> 
> Run-time dispatching is just like a case-statement, except the branches
> are scattered all over the code.  To do white-box testing, you have to
> track down all overridings of a given procedure.  Having done that, it's
> no harder than testing a case statement.  So, I think you want a tool to
> do that tracking down.  I use "grep" for that purpose, but one could
> imagine something more helpful.

For safety-critical systems, you might also want to use pragma Reviewable,
coupled with a tool that reads the resulting analysis file, to examine
the object code for each dispatch and verify that the case-ish object code meets
certain criteria. We do this now for case statements, and I would expect that
we would extend the technique for dispatching.

The real difference between dispatching and case statements, in my mind, is
that case statements usually only generate different code if the case statement
itself is changed. Even if the range of the case selector is changed, for
example, the case itself usually has the same object code. Thus, you can sometimes
limit the scope of analysis for regression test purposes.

For dispatching, this isn't going to be the case (so to speak.) We're going to
have to be more careful about doing analysis of dispatch points. However, with
reasonable tools and CM practices, this should not be insurmountable.

Overall, I don't have any real fear of using dispatching in our safety-critical
systems. Of course, I haven't tried to use it in practice, yet.

> But beware: there's a lot more to safety than is codified in the SS Annex.

That's certainly true. Further, I don't see the annex as being all that much
"over-kill." Except for Normalize_Scalars and 'Valid, you can pretty much have the
whole annex with current Ada 83 tools (although the implementation is
not the same, of course). I would like to believe that, for safety and security
related applications, the annex would serve as a perfectly reasonable tool kit.

> 
> - Bob

-- 
LMTAS - "Our Brand Means Quality"

Re: Can OO be successful in real-time embedded systems?

[Robert A Duff]

In article <3191DE76.130F@lmtas.lmco.com>,
Ken Garlington  <garlingtonke@lmtas.lmco.com> wrote:
>For safety-critical systems, you might also want to use pragma
>Reviewable, coupled with a tool that reads the resulting analysis file,
>to examine the object code for each dispatch and verify that the
>case-ish object code meets certain criteria. We do this now for case
>statements, and I would expect that we would extend the technique for
>dispatching.

The definition of pragma Reviewable is pretty vague.  We'll have to rely
on people who really care about this pragma, to admonish vendors to
produce useful information.

>The real difference between dispatching and case statements, in my
>mind, is that case statements usually only generate different code if
>the case statement itself is changed. Even if the range of the case
>selector is changed, for example, the case itself usually has the same
>object code. Thus, you can sometimes limit the scope of analysis for
>regression test purposes.

Right.  To test polymorphic code in this way, you have to track down all
overridings.

>For dispatching, this isn't going to be the case (so to speak.) We're
>going to have to be more careful about doing analysis of dispatch
>points. However, with reasonable tools and CM practices, this should
>not be insurmountable.

Dispatching calls are like case statements, except that the case
branches are open-ended.  One just needs to take that open-endedness
into account.

>That's certainly true. Further, I don't see the annex as being all that
>much "over-kill." Except for Normalize_Scalars and 'Valid, you can
>pretty much have the whole annex with current Ada 83 tools (although
>the implementation is not the same, of course). I would like to believe
>that, for safety and security related applications, the annex would
>serve as a perfectly reasonable tool kit.

The SS annex is very much UNDER-kill, and intentionally so.  If you say,
"my program obeys the SS annex, and therefore can be used safely", I'll
think you're a crackpot.  If you say, "my program uses the SS annex
(among other things) to ensure safety", then I'll take it more
seriously.

- Bob

Re: Can OO be successful in real-time embedded systems?

[Jon S Anthony]

In article <m0uHHBP-0000ztC@crash.cts.com> "Robert C. Leif, Ph.D." <rleif@MAIL.CTS.COM> writes:

> anyone in the group do run-time dispatching.  I know that I could buy a
> compiler with the Safety and Security Annex. However, that is ridiculous
> over-kill. You have provably heard my line, that Ada 95 is the Safety and
> Security annex of C++.  First one switches a C or C++ developer to Ada 95,
> then, latter on, one can start discussion of the Safety and Security Annex.

Why "overkill"?  BTW, you can just download a compiler that supports
the Safety and Security Annex - Gnat...

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Can OO be successful in real-time embedded systems?

[Robert A Duff]

In article <Pine.GSO.3.92.960509164924.1191A-100000@nunic.nu.edu>,
Richard Riehle  <rriehle@nunic.nu.edu> wrote:
>   However, in hard, real-time systems (HRTS), run-time dispatching is a
>   little more of an issue than a simple case statement.  The controlling
>   factor is whether we can predict that a certain sequence of actions
>   will be time-determinate.

What exactly do you mean by "a little more of an issue"?  The actual
dispatching call can be done in constant time, just like a case
statement does a jump through a table in constant time.  So the *only*
difference is what I mentioned in my previous post: with a case
statement, you have all the alternatives sitting there in one place,
whereas with a dispatching call, they are scattered all over.  Do you
see any *other* differences between case statements and dispatching,
that would affect the ability to do worst-case timing analysis?

- Bob

Re: Can OO be successful in real-time embedded systems?

[Ken Garlington]

Robert A Duff wrote:
> 
> The definition of pragma Reviewable is pretty vague.  We'll have to rely
> on people who really care about this pragma, to admonish vendors to
> produce useful information.

True, and I don't expect each vendor will implement this pragma consistently.
It would be nice if everyone used an ASIS-type convention, but it's not clear to
me if that's reasonable for this kind of information.

Nonetheless, at least there is now some sort of common starting point for this
capability, so that I don't have to explain the basic idea to each vendor.
Since there are existing examples of this capability (e.g., Tartan's AdaList),
I'd hope that it will be easy to get such information from future toolsets.

> Dispatching calls are like case statements, except that the case
> branches are open-ended.  One just needs to take that open-endedness
> into account.

I assume you mean "open-ended" at the source level, not the object code level.
For any given compilation, I assume that object code analysis will be capable
of determining the number of cases that really exist, at least for the approach
that most vendors will take.

> The SS annex is very much UNDER-kill, and intentionally so.  If you say,
> "my program obeys the SS annex, and therefore can be used safely", I'll
> think you're a crackpot.  If you say, "my program uses the SS annex
> (among other things) to ensure safety", then I'll take it more
> seriously.

Absolutely. I don't see the annex as that difficult a challenge (except for
the interpretation of some of the pragma Restrictions issues, as has been
discussed before).

> 
> - Bob

-- 
LMTAS - "Our Brand Means Quality"

Re: Can OO be successful in real-time embedded systems?

[Richard Riehle]

On Fri, 10 May 1996, Robert A Duff wrote:

> In article <Pine.GSO.3.92.960509164924.1191A-100000@nunic.nu.edu>,
> Richard Riehle  <rriehle@nunic.nu.edu> wrote:
> >   However, in hard, real-time systems (HRTS), run-time dispatching is a
> >   little more of an issue than a simple case statement.  The controlling
> >   factor is whether we can predict that a certain sequence of actions
> >   will be time-determinate.
>
> What exactly do you mean by "a little more of an issue"?  The actual
> dispatching call can be done in constant time, just like a case
> statement does a jump through a table in constant time.  So the *only*
> difference is what I mentioned in my previous post: with a case
> statement, you have all the alternatives sitting there in one place,
> whereas with a dispatching call, they are scattered all over.  Do you
> see any *other* differences between case statements and dispatching,
> that would affect the ability to do worst-case timing analysis?

  Agreed that in small programs where the classwide operations are in
  the same package as the base type, there should not be too much
  of a problem with evaluation of timing.  As we override operators
  and add new classwide operators, it is going to become more difficult
  to do them kinds of timing analysis one can do with a simple case
  statement.

  One model for classwide operations will be something like:

       package Q is
          type T is tagged ...
          ...
       end Q;

       package Q.Classwide is
         procedure P1 (X : T'Class);
         procedure P2 (X : T'Class);
         ...
       end Q.Classwide;

  Now we have derivations of T, complete with overriding operations.  The
  Ada 95 model for this is crisp, clean, and clear.  And as long as no
  one begins extending package Q.Classwide or any of the other original
  derivations, everything is nice and neat.

  However, as we begin doing more extensions, it will become more
  difficult to apply the kinds of predicitive metrics we might be
  able to apply to a non-extensible model.  Even coverage analyzers
  will take a little longer to produce the information we require.

  Oh, and yes, are there any coverage analyzers that will work on the
  extensible, dispatching model built around child packages?

  I did not say this was impossible.  I do think we can count on it being
  a tad more difficult.  This should not discourage us from using the Ada
  95 model.  It is certainly not as unruly as that found in some other
  languages.  But I do think it adds a whole new dimension to the
  practice of predictive metrics.

  Richard Riehle