| Grumble Grumble Grumble
1. "Some think knowledge is sat in your lap". K.B.
2. Where my fingertips are is MY business.
I type with my toes. The toes knows.
3. Ain't got no friends. Don't need more enemies.
4. Wouldn't associate with anyone in MY business.
IpsoFatso: Sticking with the Internet. Kalisti.
I guess, Adam, on a slow day we could get together and
desam up a convincing application sure to exhaust all of
MCI's R&D budget before they figure out it's impossible to
implement. "Don't take comedy from strangers". ;-)
On with the free research on determining code behavior..
<chunk2>
Bounded Loops
Constructs for bounded loops differ from conventional loop
constructs in two ways:
1. All loop constructs specify a loop bound that is either:
a limit for the maximum number of iterations
exp. FOR(exp1;exp2;exp3) MAX_COUNT(const_expr)
statement1
ON_OVERRUN statement2
or a time limit for determination.
exp. FOR(exp1;exp2;exp3) MAX_TIME(const_expr)
statement1
ON_TIMEOUT statement2
This must be known at compile time.
2. If a loop bound is overrun, a specified action is
started. This can be a default exception handler,
or a programmer specified override.
To guarantee the limits of time-bounded loops are met,
determine the maximum amount of time execute one loop
and test at the start of a loop to determine if it will complete
within the alloted boundary. In many cases the actual=7F
timing of loops will differ from the behavior specified in
the program.
Exceptions
There are two types of exceptions, recoverable and
non-recoverable. The timing behavior of recoverable
exceptions must be accounted for in the timing analysis.
As the occurrence of a non-recoverable exception
leads to system failure, transfer to save state and shut
down.
Calculating an upper bound for MAXT
Programs that do not violate the cited constraints and
contain only simple constructs can be analysed by an
automated tool. MAXT can be calculated recursively
using a small set of formulae. The language constructs
for which the formulae are provided are simple statements,
statement sequences, alternatives, bounded loops,
and subroutines. The MAXT of a simple construct
can be derived from the time required for sequential
execution of the corresponding machine instructions
for a given processor obtained from the hardware
specifications.
To calculate the MAXT for sequences, sum the MAXT
of the single constructs. For an alternative (e.g., if then else),
add maximal time for conditional evaluation. For loops,
distinguish between loop boundary types (max iteration or
time). For limited iterations, multiply the number of iterations
by the excution time of the loop condition and body. Where
the condition is evaluated at the hsad (FOR, WHILE), add
the time for an extra evaluation of the condition. In a FOR,
also add the time for the initialization. Time bounded loops
are simply the value of the timing constant (e.g. MAX_TIME).
For both types of loops, add the time for the exception
handler or overrun default.
For subroutines, the MAXT sums the time for organization
(copy parameters, jump, return from subroutine) and the time
to execute the subroutine body.
Here are the formulae (Len apologizes in advance if
any formulae are transcribed with errors.) The function
r, takes a simple action whose MAXT is directly derived
from the number of machine instruction cycles as an
argument and returns the amount of time it takes to
execute this action. The MAXT function calculates
an upper bound for the execution time of its argument.
primitive: maxt(primitive) =3D r(primitive)
sequence: maxt(sequence) =3D sum i maxt(construct)
alternative: maxt(alternative) =3D maxt(condition) +
max(maxt(construct-sub1),
maxt(construct-sub2))
loop-subnumber: maxt(loop-subhsad) =3D maxt(init) +
maxt(condition) + count * (maxt(body)
+ maxt(condition)) + maxt(overrun_statement)
maxt(loop-subtail) =3D count * (maxt(body)
+ maxt(condition)) + maxt(overrun_statement)
loop-subtime: maxt(loop-subtime) =3D time + maxt(timeout_statement)
subroutine: maxt(subroutine) =3D r(organization) + maxt(body)
Adding Rules to Improve MAXT computation
Using the rules so far, we are able to compute an upper
bound for MAXT. Results can be improved by adding more
information about constraints on control flow to progam.
This will require new language constructs.
Def3: Scope - A scope is part of a program's instruction
code limited by a scope language construct embedded
into the syntax of the programming language.
Def4: Marker - A Marker is a special mark located within
a scope. It specifies the maximal number of times
the marked position may be passed by the program flow
between entering and leaving the scope.
Using markers, we can specify the maximal number
of times the control flow can pass through a specified
position within a special part of a program designated
by the scope construct. An arbitrary number of
markers may be set in each scope.
(to be continued)</chunk2>