Re: Worst case execution time problem

On Sat, 30 Dec 2006 13:32:08 -0600, gw7rib@xxxxxxx wrote
(in article <1167507128.779844.96800@xxxxxxxxxxxxxxxxxxxxxxxxxxx>):


Randy Howard wrote:
On Sat, 30 Dec 2006 11:31:52 -0600, gw7rib@xxxxxxx wrote
(in article <1167499912.126975.59540@xxxxxxxxxxxxxxxxxxxxxxxxxxx>):


Christian Christmann wrote:
Hi,

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? I appreciate any detailed explanations.

Perhaps an example will help.

We're talking a program running in an OS along with other tasks, kernel
code and device drivers though. Such simplifications are fine for CS
class, but not for measuring WCET in a real-time system.

[Snip example]

How long does this program take to run?

Now what's the right answer?

I was trying to make the point that even for a simple program, like the
one I demonstrated, it is not possible to work out the WCET. Adding
additional unspecified delays won't make it any easier to work out the
WCET so I'm not quite sure what you're driving at.

The point I was driving at was that it is /much/ harder to determine
than you hinted at, in the direction of the original claim that the
literature says "its calculation is undecidable in general".

You can get a reasonable figure with lots of empirical testing and
measurement, but not by staring at an algorithm.

--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw





.

Relevant Pages

  • Re: Worst case execution time problem
    ... Christian Christmann wrote: ... in real-time systems the worst case execution time is an important ... We're talking a program running in an OS along with other tasks, ... but not for measuring WCET in a real-time system. ...
    (comp.programming)
  • Re: Worst case execution time problem
    ... Christian Christmann wrote: ... in real-time systems the worst case execution time is an important ... We're talking a program running in an OS along with other tasks, ... but not for measuring WCET in a real-time system. ...
    (comp.programming)
  • Worst case execution time problem
    ... in real-time systems the worst case execution time (WCET) is an important ... In the literature I found the statement that its calculation is ...
    (comp.programming)
  • Worst case execution time problem
    ... in real-time systems the worst case execution time (WCET) is an important ... In the literature I found the statement that its calculation is ...
    (comp.arch.embedded)