Re: Ada.Execution_Time

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

Randy, I'm glad that you are participating in this thread. My duologue 
with Dmitry is becoming repetitive and our views entrenched.

We have been discussing several things, although the focus is on the 
intended meaning and properties of Ada.Execution_Time. As I am not an 
ARG member I have based my understanding on the (A)RM text. If the text 
does not reflect the intent of the ARG, I will be glad to know it, but 
perhaps the ARG should then consider resolving the conflict by 
confirming or changing the text.

Randy Brukardt wrote:
> "Niklas Holsti" <niklas.holsti@tidorum.invalid> wrote in message 
> news:8nm30fF7r9U1@mid.individual.net...
>> Dmitry A. Kazakov wrote:
>>> On Sat, 18 Dec 2010 23:20:20 +0200, Niklas Holsti wrote:
> ...
>>> On a such platform the implementation would be as perverse as RM D.14
>>> is. But the perversion is only because of the interpretation.
>> Bah. I think that when RM D.14 says "time", it really means time. You
>> think it means something else, perhaps a CPU cycle count. I think the 
>> burden of proof is on you.
>>
>> It seems evident to me that the text in D.14 must be interpreted using
>> the concepts in D.2.1, "The Task Dispatching Model", which clearly
>> specifies real-time points when a processor starts to execute a task and
>> stops executing a task. To me, and I believe to most readers of the RM,
>> the execution time of a task is the sum of these time slices, thus a
>> physical, real time.
> 
> For the record, I agree more with Dmitry than Niklas here. At least the 
> interpretation *I* had when this package was proposed was that it had only a 
> slight relationship to real-time.

Oh. What would that slight relationship be? Or was it left unspecified?

> My understanding was that it was intended 
> to provide a window into whatever facilities the underlying system had for 
> execution "time" counting.

Of course, as long as those facilities are good enough for the RM 
requirements and for the users; otherwise, the implementor might improve 
on the underlying system as required. The same holds for Ada.Real_Time. 
If the underlying system is a bare-board Ada RTS, the Ada 95 form of the 
RTS probably had to be extended to support Ada.Execution_Time.

I'm sure that the proposers of the package Ada.Execution_Time expected 
the implementation to use the facilities of the underlying system. But I 
am also confident that they had in mind some specific uses of the 
package and that these uses require that the values provided by 
Ada.Execution_Time have certain properties that can reasonably be 
expected of "execution time", whether or not these properties are 
expressly written as requirements in the RM.

Examples of these uses are given in the paper by A. Burns and A.J. 
Wellings, "Programming Execution-Time Servers in Ada 2005," pp.47-56, 
27th IEEE International Real-Time Systems Symposium (RTSS'06), 2006. 
http://doi.ieeecomputersociety.org/10.1109/RTSS.2006.39.

You put "time" in quotes, Randy. Don't you agree that there *is* a 
valid, physical concept of "the execution time of a task" that can be 
measured in units of physical time, seconds say? At least for processors 
that only execute one task at a time, and whether or not the system 
provides facilities for measuring this time?

I think that the concept exists and that it matches the description in 
RM D.14 (11/2), using the background from D.2.1, whether or not the ARG 
intended this match.

If you agree that such "execution time" values are conceptually well 
defined, do you not think that the "execution time counting facilities" 
of real-time OSes are meant to measure these values, to some practical 
level of accuracy?

If so, then even if Ada.Execution_Time is intended as only a window into 
these facilities, it is still intended to provide measures of the 
physical execution time of tasks, to some practical level of accuracy.

> That had no defined relationship with what Ada calls "time".
> As usch, I think the name "execution time" is misleading, (and 
> I recall some discussions about that in the ARG), but no one had a better 
> name that made any sense at all.

Do you remember if these discussions concerned the name of the package, 
the name of the type CPU_Time, or the very concept "execution time"? If 
the question was of the terms "time" versus "duration", I think 
"duration" would have been more consistent with earlier Ada usage, but 
"execution time" is more common outside Ada, for example in the acronym 
WCET for Worst-Case Execution Time.

The fact that Ada.Execution_Time provides a subtraction operator for 
CPU_Time that yields Time_Span, which can be further converted to 
Duration, leads the RM reader to assume some relationship, at least that 
spans of real time and spans of execution time can be measured in the 
same physical units (seconds).

It has already been said, and not only by me, that Ada.Execution_Time is 
intended (among other things, perhaps) to be used for implementing task 
scheduling algorithms that depend on the accumulated execution time of 
the tasks. This is supported by the Burns and Wellings paper referenced 
above. In such algorithms I believe it is essential that the execution 
times are physical times because they are used in formulae that relate 
(sums of) execution-time spans to spans of real time.

Dmitry has agreed with some of my statements on this point, for example:

- A task cannot accumulate execution time at a higher rate than real 
time. For example, in one real-time second the CPU_Time of a task cannot 
increase by more than one second.

- If only one task is executing on a processor, the execution time of 
that task increases (or "could increase") at the same rate as real time.

Do you agree that we can expect these statements to be true? (On the 
second point, system overhead should of course be taken into account, on 
which more below.)

> In particular, there is no requirement in the RM or anywhere else that these 
> "times" sum to any particular answer.

I agree that the RM has no such explicit requirement. I made this claim 
to counter Dmitry's assertion that CPU_Time has no physical meaning, and 
of course I accept that the sum will usually be less than real elapsed 
time because the processor spends some time on non-task activities.

The last sentence of RM D.14 (11/2) says "It is implementation defined 
which task, if any, is charged the execution time that is consumed by 
interrupt handlers and run-time services on behalf of the system". This 
sentence strongly suggests to me that the author of this paragraph had 
in mind that the total available execution time (span) equals the real 
time (span), that some of this total is charged to the tasks, but that 
some of the time spent in interrupt handlers etc. need not be charged to 
tasks.

The question is how much meaning should be read into ordinary words like 
"time" when used in the RM without a formal definition.

If the RM were to say that L is the length of a piece of string S, 
measured in meters, and that some parts of S are colored red, some blue, 
and some parts may not be colored at all, surely we could conclude that 
the sum of the lengths in meters of the red, blue, and uncolored parts 
equals L? And that the sum of the lengths of the red and blue parts is 
at most L? And that, since we like colorful things, we hope that the 
length of the uncolored part is small?

I think the case of summing task execution time spans is analogous.

> I don't quite see how there could be, 
> unless you were going to require a tailored Ada target system (which is 
> definitely not going to be a requirement).

I don't want such a requirement. The acceptable overhead (fraction of 
execution time not charged to tasks) depends on the application.

Moreover, on a multi-process systems (an Ada program running under 
Windows or Linux, for example) some of the CPU time is spent on other 
processes, all of which would be "overhead" from the point of view of 
the Ada program. I don't think that the authors of D.14 had such systems 
in mind.

> Perhaps the proposers (from the IRTAW meetings) had something else in mind, 
> but if so, they communicated it very poorly.

Do you remember who they were? Are the IRTAW minutes or proposals 
accessible on the web?

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .