Re: Worst case execution time problem

David T. Ashley wrote:
"Hans-Bernhard Bröker" <HBBroeker@xxxxxxxxxxx> wrote:
Christian Christmann wrote:

in real-time systems the worst case execution time (WCET) is an important
issue. In the literature I found the statement that its calculation is
undecidable in general. Why?

Because _in_general_, it's even impossible to decide whether a given program will *ever* finish. This is known as the Halting Problem, and its impossibility was proven by Turing long before most of us were born.

I suspect that the OP posed a more general question than he intended ...

I don't think so. He asked why he found what he did, in literature. And the reason for that is what I told him: it's because the statement he found is correct; a corollary of the Halting Theorem.

Hans, ... in general the problem is undecideable, but for most specific practical examples in embedded work you can just examine all the branch paths and loops and find a maximum.

There's a fiercely dangerous dragon hiding behind that little word "just". There will often be way more branch paths and loops to examine than expected, turning this innocent looking "just" into one heck of a lot of work.

.

Relevant Pages

  • Re: Worst case execution time problem
    ... specific practical examples in embedded work you can just examine ... There will often be way more branch paths and loops to ... So I prefer to avoid globals. ...
    (comp.arch.embedded)
  • Re: Worst case execution time problem
    ... specific practical examples in embedded work you can just examine ... There will often be way more branch paths and loops to ... can be used, in turn, for the calling functions. ...
    (comp.arch.embedded)
  • Re: Worst case execution time problem
    ... specific practical examples in embedded work you can just examine ... There will often be way more branch paths and loops to ... variables can easily defeat this effort. ...
    (comp.arch.embedded)
  • Re: Worst case execution time problem
    ... specific practical examples in embedded work you can just examine ... There will often be way more branch paths and loops to ... Globals aren't evil becuase they're global. ...
    (comp.arch.embedded)