Re: Ada.Execution_Time

["Randy Brukardt" <randy@rrsoftware.com>]

I think we're actually in agreement on most points. The main difference is 
that I contend that the theoretical "execution time" is, in actual practice, 
unmeasurable. ("Unmeasurable" is a bit strong, but I mean that you can only 
get a gross estimation of it.)

You have argued that there exist cases where it is possible to do better (a 
hardware clock, a single processor, a kernel that doesn't get in the way of 
using the hardware clock, no contention with other devices on the bus, 
etc.), and I wouldn't disagree. The problem is that those cases aren't 
realistic, particularly if you are talking about a language-defined package. 
(Even if there is a hardware clock available on a particular target, an 
off-the-shelf compiler isn't going to be able to use it. It can only use the 
facilities of the kernel or OS.)

This shows up when you talk about the inability to reproduce the results. In 
practice, I think you'll find that the values vary a lot from run to run; 
the net effect is that the error is a large percentage of the results for 
many values.

Your discussion of real-time scheduling using this still seems to me to be 
more in the realm of academic exercise than something practical. I'm sure 
that it works in very limited circumstances, but those circumstances are 
getting less and less likely by the year. Techniques that assume a strong 
correspondence between these values and real-time are simply fantasy -- I 
would hope no one depend on these for anything of importance. (With the 
possible exception of an all-Ada kernel, but even then you would be 
*writing* Ada.Execution_Time, not using it.) A weak correspondence (for 
choosing between otherwise similar tasks, for one instance) might make 
sense, but that is about it.

                       Randy.


"Niklas Holsti" <niklas.holsti@tidorum.invalid> wrote in message 
news:8o4k3tFko2U1@mid.individual.net...
> 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
>       .      @       .