Re: Ada.Execution_Time

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

Before I answer Randy's points, below, I will try to summarise my 
position in this discussion. It seems that my convoluted dialog with 
Dmitry has not made it clear. I'm sorry that this makes for a longish post.

I am not proposing or asking for new requirements on Ada.Execution_Time 
in RM D.14. I accept that the accuracy and other qualities of the 
implementation are (mostly) not specified in the RM, so Randy is right 
that the implementors can (mostly) just provide an interface to whatever 
services exist, and Dmitry is also (mostly) right when he says that 
Ada.Execution_Time can deliver garbage results and still satisfy the RM 
requirements.

However, I think we all hope that, as Randy said, implementers are going 
to provide the best implementation that they can. Speaking of a "best" 
implementation implies that there is some ideal solution, perhaps not 
practically realizable, against which the quality of an implementation 
can be judged. Moreover, since the RM defines the language and is the 
basis on which implementors work, I would expect that the RM tries to 
describe this ideal solution, perhaps only through informal definitions, 
rationale, implementation advice, or annotations. This is what I have 
called the "intent of Ada.Execution_Time" and it includes such questions 
as the intended meaning of a CPU_Time value and what is meant by 
"execution time of a task".

My background for this discussion and for understanding 
Ada.Execution_Time is real-time programming and analysis, and in 
particular the various forms of schedulability analysis. In this domain 
the theory and practice depend crucially on the execution times of 
tasks, usually on the worst-case execution time (WCET) but sometimes on 
the whole range or distribution of execution times. Moreover, the theory 
and practice assume that "the execution time of a task" has a physical 
meaning and a strong relationship to real time.

For example, it is assumed (usually implicitly) that when a task is 
executing uninterrupted on a processor, the execution time of the task 
and the real time increase at the same rate -- this is more or less the 
definition of "execution time". Another (implicitly) assumed property is 
that if a processor first runs task A for X seconds of execution time, 
then switches to task B for Y seconds of execution time, the elapsed 
real time equals X + Y plus some "overhead" time for the task switch. 
(As a side comment, I admit that some of these assumptions are becoming 
dubious for complex processors where tasks can have strong interactions, 
for example through the cache.)

I have assumed, and still mostly believe, that this concept of 
"execution time of a task" is the ideal or intent behind 
Ada.Execution_Time, and that approaching this ideal is an implementer's 
goal.

My participation in this thread started with my objection to Dmitry's 
assertion that "CPU_Time has no physical meaning". I may have 
misunderstood Dmitry's thought, leading to a comedy of 
misunderstandings. Perhaps Dmitry only meant that in the absence of any 
accuracy requirements, CPU_Time may not have a useful physical meaning 
in a poor implementation of Ada.Execution_Time. I accept that, but I 
think that a good implementation should try to give CPU_Time the 
physical meaning that "execution time" has in the theory and practice of 
real-time systems, as closely as is practical and desired by the users 
of the implementation.

My comments in this thread therefore show the properties that I think a 
good implementation of Ada.Execution_Time should have, and are not 
proposed as new requirements. At most they could appear as additions to 
the rationale, advice, or annotations for RM D.14. I measure the 
"goodness" of an implementation as "usefulness for implementing 
real-time programs". Others, perhaps Randy or Dmitry, may have other 
goodness measures.

This thread started by a question about how Ada.Execution_Time is meant 
to be used. I think it is useful to discuss the properties and uses that 
can be expected of a good implementation, even if the RM also allows 
poor implementations.

Randy Brukardt wrote:
> "Niklas Holsti" <niklas.holsti@tidorum.invalid> wrote in message 
> news:8o0p0lF94rU1@mid.individual.net...
>> 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.
> 
> Probably, but quality of implementation is rarely specified in the Ada 
> Standard. When it is, it generally is in the form of Implementation Advice 
> (as opposed to hard requirements). The expectation is that implementers are 
> going to provide the best implementation that they can -- implementers don't 
> purposely build crippled or useless implementations. Moreover, that is 
> *more* likely when the Standard is overspecified, simply because of the need 
> to provide something that meets the standard.

I agree.

>> 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'm honestly not sure. The problem is that while such a concept might 
> logicially exist, as a practical matter it cannot be measured outside of the 
> most controlled circumstances.

I don't think that measurement is so difficult or that the circumstances 
must be so very controlled.

Let's assume a single-processor system and a measurement mechanism like 
the "Model A" that Dmitry described. That is, we have a HW counter that 
is driven by a fixed frequency. For simplicity and accuracy, let's 
assume that the counter is driven by the CPU clock so that the counter 
changes are synchronized with instruction executions. I think such 
counters are not uncommon in current computers used in real-time 
systems, although they may be provided by the board and not the 
processor. We implement Ada.Execution_Time by making the task-switching 
routines and the Clock function in Ada.Execution_Time read the value of 
the counter to keep track of how much the counter increases while the 
processor is running a given task. The accumulated increase is stored in 
the TCB of the task when the task is not running.

Randy, why do you think that this mechanism does not measure the 
execution time of the tasks, or a good approximation of the ideal? There 
are of course nice questions about exactly when in the task-switching 
code the counter is read and stored, and what to do with interrupts, but 
I think these are details that can be dismissed as in RM D.14 (11/2) by 
considering them implementation defined.

It is true that execution times measured in that way are not exactly 
repeatable on today's processors, even when the task follows exactly the 
same execution path in each measurement, because of external 
perturbations (such as memory access delays due to DRAM refresh) and 
inter-task interferences (such as cache evictions due to interrupts or 
preempting tasks). But this non-repeatability is present in the ideal 
concept, too, and I don't expect Ada.Execution_Time.Clock to give 
exactly repeatable results. It should show the execution time in the 
current execution of the task.

> Thus, that might make sense in a bare-board 
> Ada implementation, but not in any implementation running on top of any OS 
> or kernel.

The task concept is not so Ada-specific. For example, I would call RTEMS 
a "kernel", and it has a general (not Ada-specific) service for 
measuring per-task execution times, implemented much as Dmitry's Model A 
except that the "RTC counter" may be the RTEMS interrupt-driven "clock 
tick" counter, not a HW counter.

And what is an OS but a kernel with a large set of services, and usually 
running several unrelated applications / processes, not just several 
tasks in one application? Task-specific execution times for an OS-based 
application are probably less repeatable, and less useful, but that does 
not detract from the principle.

> As such, whether the concept exists is more of an "angels on the 
> head of a pin" question than anything of practical importance.

It is highly important for all practical uses of real-time scheduling 
theories and algorithms, since it is their basic assumption. Of course, 
some real-time programmers are of the opinion that real-time scheduling 
theories are of no practical importance. I am not one of them :-)

>> 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.
> 
> The problem is that that "practical level of accuracy" isn't realistic. 

I disagree. I think execution-time measurements using Dmitry's Model A 
are practical and can be sufficiently accurate, especially if they use a 
hardware counter or RTC.

> Moreover, I've always viewed such facilities as "profiling" ones -- it's the 
> relative magnitudes of the values that matter, not the absolute values. In 
> that case, the scale of the values is not particularly relevant.

When profiling is used merely to identify the CPU hogs or bottlenecks, 
with the aim of speeding up a program, I agree that the scale is not 
relevant. Profiling is often used in this way for non-real-time systems. 
It can be done also for real-time systems, but would not help in the 
analysis of schedulability if the time-scale is arbitrary.

If profiling is used to measure task execution times for use in 
schedulability analysis or even crude CPU load computations, the scale 
must be real time, because the reference values (deadlines, load 
measurement intervals) are expressed in real time.

>> 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.
> 
> That would be a wrong interpretation of a algorithms, I think. (Either that, 
> or the algorithms themselves are heavily flawed!). The important property is 
> that all of the execution times have a reasonably proportional relationship 
> to the actual time spent executing each task (that hypothetical concept); 
> the absolute values shouldn't matter much

I think you are wrong. The algorithms presented in the Burns and 
Wellings paper that I referred to implement "execution-time servers" 
which, as I understand them, are meant to limit the fraction of the CPU 
power that is given to certain groups of tasks and work as follows in 
outline. The CPU fraction is defined by an execution-time budget, say B 
seconds, that the tasks in the group jointly consume. When the budget is 
exhausted, the tasks in the group are either suspended or demoted to a 
background priority. The budget is periodically replenished (increased 
up to B seconds) every R seconds, with B < R for a one-processor system. 
The goal is thus to let this task group use at most B/R of the CPU time. 
In other words, that the CPU load fraction from this task group should 
be no more than B/R.

The B part is measured in execution time (CPU_Time differences as 
Time_Spans) and the R part in real time. If execution time is not scaled 
properly, the load fraction B/R is wrong in proprtion, and the CPU time 
(1-B/R) left for other, perhaps more critical tasks could be too small, 
causing deadline misses and failures. It is essential that execution 
time (B) is commensurate with real time (R). The examples in the paper 
also show this assumption.

As usual for academic papers in real-time scheduling, Burns and Wellings 
make no explicit assumptions about the meaning of execution time. They 
do mention measurement inaccuracies, but a systematic difference in 
scale is not considered.

> (just as the exact priority values 
> are mostly irrelevant to scheduling decisions).

The case of priority values is entirely different. I don't know of any 
real-time scheduling methods or analyses in which the quantitative 
values of priorities are important; only their relative order is 
important. In contrast, all real-time scheduling methods and analyses 
that I know of depend on the quantitative, metric, values of task 
execution times. Perhaps some heuristic scheduling methods like 
"shortest task first" are exceptions to this rule, but I don't think 
they are suitable for real-time systems.

> Moreover, when the values 
> are close, one would hope that the algorithms don't change behavior much.

Yes, I don't think the on-line execution-time dependent scheduling 
algorithms need very accurate measures of execution time. But if the 
time-scale is wrong by a factor of 2, say, I'm sure the algorithms will 
not perform as expected.

Burns and Wellings say that one of the "servers" they describe may have 
problems with cumulative drift due to measurement errors -- similar to 
round-off or truncation errors -- and they propose methods to correct 
that. But they do not discuss scale errors, which should lead to a much 
larger drift.

> The values would be trouble if they bore no relationship at all to the 
> "actual time spent executing the task", but it's hard to imagine any 
> real-world facility in which that was the case.

I agree, but Dmitry claimed the opposite ("CPU_Time has no physical 
meaning") to which I objected. And indeed it seems that under some 
conditions the execution times measured with the Windows "quants" 
mechanism are zero, which would certainly inconvenience scheduling 
algorithms.

>> 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 think you are inventing things.

Possibly so. RM D.14 (11/2) tries to define "the execution time of a 
task" by using an English phrase "... is the time spent by the system 
...". I am trying to understand what this definition might mean, as a 
description of the ideal or intent in the minds of the authors, who 
certainly intended the definition to have *some* meaning for the reader.

I strongly suspect that the proposers of D.14 meant "execution time" as 
understood in the real-time scheduling theory domain, and that they felt 
it unnecessary to define it or its properties more formally, partly out 
of habit, as those properties are implicitly assumed in academic papers, 
partly because any definition would have had to include messy text about 
measurement errors, and they did not want to specify accuracy requirements.

> There is no such requirement in the standard, and that's good:

I agree and I don't want to add such a requirement.

> I've never seen a real system in which this has been true.

I don't think it will be exactly true in a real system. I continue to 
think that it will be approximately true in a good implementation of 
Ada.Execution_Time (modulo the provision on interrupt handlers etc), and 
that this is necessary if Ada.Execution_Time is to be used as Burns and 
Wellings propose.

> Even the various profilers I wrote for MS-DOS (the closest system to a bare 
> machine that will ever be in wide use) never had this property.

I can't comment on that now, but I would be interested to hear what you 
tried, and what happened.

>> 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.
> 
> I disagree, in the sense that the ARG as a whole certainly considered the 
> use of this facility in all environments.

Aha. Well, as I said above on the question of Ada vs kernel vs OS, the 
package should be implementable under and OS like Windows or Linux, too. 
I don't think D.14 makes any attempt to exclude that, and why should it.

> (I find that it would be very 
> valuable for profiling on Windows, for instance, even if the results only 
> have a weak relationship to reality).

Yes, if all you want are the relative execution-time consumptions of the 
tasks in order to find the CPU hogs. And the quant-truncation problem 
may distort even the relative execution times considerably.

Randy wrote in another post:
 > It's clear that he [Niklas] would never be happy
 > with a Windows implementation of Ada.Execution_Time -- too bad,
 > because it still can be useful.

I probably would not be happy to use Windows at all for a real-time 
system, so my happiness with Ada.Execution_Time is perhaps moot.

But it is all a question of what accuracy is required and can be 
provided. If I understand the description of Windows quants correctly, 
an implementation of Ada.Execution_Time under Windows may have tolerable 
accuracy if the average span of non-interrupted, non-preempted, and 
non-suspended execution of task is much larger than a quant, as the 
truncation of partially used quants then causes a relatively small error.

I don't know if the scheduling methods of Windows would let one make 
good use the measured execution times. I have no experience of Windows 
programming on that level, unfortunately.

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