NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/realtime/1351

Internet Message Format | 1992-11-17 | 9.0 KB

Path: sparky!uunet!charon.amdahl.com!pacbell.com!ames!sun-barr!rutgers!igor.rutgers.edu!cadenza.rutgers.edu!masticol
From: [e-mail] (Steve Masticola)
Newsgroups: comp.realtime
Subject: Re: Technical summary of NATO ASI
Keywords: Real-Time, NATO ASI
Message-ID: <[e-mail]>
Date: 18 Nov 92 03:06:35 GMT
References: <[e-mail]>
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 192

[e-mail] (Sias Mostert) writes:

>Hi,
>I was unable to attend the NATO ASI in St Maarten 5/10/92-17/10/92 having to
>abort my attendence at the last moment.  I am interested in the main
>conclusions reached at the NATO ASI, with regard to the future of research
>in Real-Time systems for the next 5 years.  Any summary or
>personal opinions are very welcome.

Well, the following position paper is not necessarily the main
conclusion of the whole conference, but I think it summarizes some of
the current issues in HRT language design. Others may disagree, I hope
:-) I'd like to get some discussion about languages going here, or at
least some that doesn't deal with the VME bus standard :-)

My summary of the language issues discussed at the conference follows
the position paper.

- Steve Masticola ([e-mail]).

-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----

    Static Analysis: Hard Real Time is Hard, ``Big Time!''

             Stephen P. Masticola
            Department of Computer Science
             Rutgers University,
               New Brunswick NJ 08903.
           Email: [e-mail].

                   - and -

              Thomas J. Marlowe*
              Department of Mathematics
            Seton Hall University
            South Orange NJ 07079.
           Email: [e-mail].

* In affiliation with the Real-Time Systems Laboratory of the New
Jersey Institute of Technology.


Hard real time (HRT) programs are correct only if they produce a
correct output within a specified time. Failure to meet timing
constraints can be disastrous, and can be caused by subtle bugs that
are difficult to find by testing [GA1]. While formal methods are often
proposed to deal with this problem [Os1], these cannot presently
handle large systems in full generality. We believe that the real-time
community should adopt programming language methodology, e.g., static
anomaly detection, to certify that programs meet termination [MR1] and
timing [HS1] constraints.

HRT applications may have complex requirements, making assembly
language programming unreasonably complicated. It is also hard to
ensure safe translation from such intricate specifications into
intermediate code without auxiliary analysis or testing.  Moreover, we
cannot afford (literally) to neglect issues of efficiency, i.e.,
optimization and parallelization. HRT optimization requires harder
static analysis than conventional programs, since semantically
``safe'' optimizations can cause missed deadlines, and since
previously uncoupled phases of compilation must interact for best
results [MM1].

Several languages [HS1], such as Real-Time Euclid [HS2], have been
proposed for HRT systems.  Most are akin to more common languages,
modified to eliminate constructs problematic for HRT (e.g., run-time
loop bounds), and to add features desirable for HRT (e.g., timing
exceptions).  HRT programming is harder in languages lacking the
problem features, but the programming language technique of partial
evaluation [NP1] can help to prove hard time bounds on at least some
programs that include them.

While some of the added HRT features are clearly needed, there are
penalties for adding them: increased complexity of both the semantics
of the language and the safety verification of programs.  Ada [AN1],
perhaps the most egregious example of this sort of ``creeping
featurism,'' is consequently difficult to learn, tedious to compile,
and nightmarish to analyze.

We propose, instead, that HRT languages should not only be predictable
and schedulable, but also simple.  Simplicity benefits all parties:
the language designer, the compiler writer, and the programmer. The
language should have few primitives, and these should interact only in
predictable, well-defined ways.  Design of the language and the
analysis techniques should proceed together, to assure efficient
program analysis.  The language specification should include a formal
semantics, including time, to facilitate correctness proofs of anomaly
detection and optimization algorithms (as well as potential proofs of
user program correctness).  We suggest that, although current
specification languages appear simple, they may cause problems in
translation or efficiency.

Static analysis of hard real time languages is hard --- and necessary.
Formally defined ``reduced instruction set languages,'' in the spirit
of CSP [Ho1], occam [In1], and Scheme [CR1], help to keep the
complexity of HRT analysis reasonable, and are easier to understand
and utilize.

 [AN1] American National Standards Institute: ``ANSI/MIL-STD 1815A
(1983) reference manual for the Ada programming language.'' U.S.
Gov't. Printing Office, 1983.

 [CR1] Clinger, W. and Rees, J., ed.: ``Revised Report on the
Algorithmic Language Scheme.''  LISP Pointers , 4:3 , July 1, 1991.

 [GA1] U.S. Government Accounting Office: ``Patriot Missile Defense:
Software Problem Led to System Failure at Dhahran, Saudi Arabia.''
GAO/IMTEC-92-26, February 1992.

 [Ho1] Hoare, C. A. R.: Communicating sequential processes.
Prentice/Hall, 1985. ISBN 0-1315-3271-5.

 [HS1] Halang, W. A. and Stoyenko, A. D.: ``Comparative evaluation of
high-level real-time programming languages.''  Real-Time Systems , 2:4
, November 1990, 365--382.

 [HS2] Halang, W. A. and Stoyenko, A. D.: Constructing predictable
real-time systems.  Kluwer, 1991.  ISBN 0-7923-9202-7.

 [In1] Inmos, Ltd.: Occam programming manual.  Prentice/Hall, 1984.
ISBN 0-1362-9296-8.

 [MM1] Marlowe, T. J. and Masticola, S. P.: ``Safe Optimization for
Hard Real-Time Programming.'' 2nd IEEE Int'l.  Conf.  on Syst.
Integration, Morristown, NJ, June 15-18, 1992.

 [MR1] Masticola, S. P. and Ryder, B. G.: ``A Model of Ada Programs
for Static Deadlock Detection in Polynomial Time.''  SIGPLAN Notices
26:12 , December 1991, 97-107.

 [NP1] Nirkhe, V. and Pugh, W.: ``Partial Evaluation of High-level
Imperative Languages, with Applications in Hard Real-Time Systems.''
ACM 19th POPL , 1992, 269--280.

 [Os1] Ostroff, J. S.: ``Survey of formal methods for the
specification and design of real-time systems.'' In Tutorial on
specifications of time --- abstractions, design methods, languages ,
K. M. Kavi ed., IEEE Press, 1991.

Copyright (C) 1992 by Stephen P. Masticola and Thomas J. Marlowe.
All rights reserved.


-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----

         Language Discussions at the NATO ASI

There were some lively discussions about language issues at the ASI.
There seemed to be about three camps: the formal methods camp, the
static analysis camp, and the "just count the object code statements
and use worst-case time" camp.

W.J. Cullyer and John McDermid were vocal proponents of the first
camp, and I think they had some impressive arguments and practical
results. Formal methods are more accurate, and yield lower defect
rates, than any other language technology available for demonstrating
schedule satisfaction. However, it appears that formal methods are not
yet mature enough for widespread use; formal proof is associated with
a heavy manpower cost, long lead times, and limitations on the size of
programs that can be proved to meet schedule, even with the aid of
current tools.

The second camp consisted mostly of the people who were doing static
schedulability analysis, most prominently Alex Stoyenko and (I think!)
Carlo Ghezzi. Notable in the schedulability subgroup was Ken Tindell
of York University, who was working on schedulability analysis through
simulated annealing, and who spoke in one of the birds-of-a-feather
sessions. I had some posters on static deadlock detection and safe
optimization of HRT programs (the latter coming out of work with Tom
Marlowe). Apologies to other people I've omitted.

The third camp was, I believe, mostly industry people, who'd been
doing it their way for years. As an engineer, I can see their point;
it's something that can be done. A lot of people in this camp also
seemed to be in the, "Let's throw every feature possible into the
source language" camp.

I think such approaches get them into serious problems of efficient
scalability and ease of use, respectively. As systems get larger and
more complex, overestimates of worst-case execution time get more
serious, if you only pay attention to the code at the machine
instruction level. Also, as features proliferate, they interact, in
ways that are hard to predict and which introduce bugs. The first
problem can be addressed by research; the second requires the use of a
"reduced instruction set language."

In this regard, there's a quote I saw that might be pertinent:

"The Americans say, `If it ain't broke, don't fix it.' The Japanese
say, `If it isn't perfect, make it better.'"
                    - Stephen Schwartz
                      IBM Senior Vice President