Re: Worst case execution time problem

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.


Suppose you have a program something like the following pseudo-code:

max = 3

loop:
<possible kernel, task switching, or interrupt latency here>

for x = 1 to max
<possible kernel, task switching, or interrupt latency here>
for y = 1 to max
<possible kernel, task switching, or interrupt latency here>
for z = 1 to max
<possible kernel, task switching, or interrupt latency here>
for n = 3 to max
<possible kernel, task switching, or interrupt latency here>
if x^n + y^n = z^n then print "Solution found" : stop
<possible kernel, task switching, or interrupt latency here>
next n
<possible kernel, task switching, or interrupt latency here>
next z
<possible kernel, task switching, or interrupt latency here>
next y
<possible kernel, task switching, or interrupt latency here>
next x
<possible kernel, task switching, or interrupt latency here>
max = max + 1
<possible kernel, task switching, or interrupt latency here>
goto loop

How long does this program take to run?

Now what's the right answer?



--
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 ... In the literature I found the statement that its calculation is ... 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)