Re: Ada.Execution_Time

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

Dmitry A. Kazakov wrote:
> On Wed, 29 Dec 2010 14:48:20 +0200, Niklas Holsti wrote:
> 
>> 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.
> 
> Hold on, that is only true if a certain model of CPU_Time measurement used.

In my view, it is true within the accuracy of the execution-time 
measurement method.

> There are many potential models. The one we discussed was the model A:
> 
> Model A. Get an RTC reading upon activation. Each time CPU_Time is
> requested by Clock get another RTC reading, build the difference, add the
> accumulator to the result. Upon task deactivation, get the difference and
> update the accumulator.

OK. This is, I think, the most natural model, perhaps with some 
processor performance counter or CPU-clock-cycle counter replacing the RTC.

> This is a very strong model. Weaker models:
> 
> Model A.1. Get RTC upon activation and deactivation. Update the accumulator
> upon deactivation. When the task is active CPU_Time does not change.

That model is not permitted, because the value of 
Ada.Execution_Time.Clock must change at every "CPU tick". The duration 
of a CPU tick is Ada.Execution_Time.CPU_Tick, which is at most one 
millisecond (RM D.14(20/2)).

It is true that CPU_Tick is only the "average length" of the 
constant-Clock intervals, but the implementation is also required to 
document an upper bound, which also forbids your model A.1.

(I think that this "average" definition caters for implementations where 
the execution time counter is incremented by an RTC interrrupt handler 
that may suffer some timing jitter.)

> Model B. Use a time source different from RTC. This what Windows actually
> doest.

I don't think that this is a different "model". No time source provides 
ideal, exact real time. If the time source for Ada.Execution_Time.Clock 
differs much from real time, the accuracy of the implementation is poor 
to that extent. It does not surprise me that this happens on Windows.

I admit that the RM does not specify any required accuracy for 
Ada.Execution_Time.Clock. The accuracy required for 
execution-time-dependent scheduling algorithms is generally low, I believe.

Analogously, there are no accuracy requirements on Ada.Real_Time.Clock.

> Model B.1. Like A.1, CPU_Time freezes when the task is active.

Forbidden like A.1 above.

> Model C. Asynchronous task monitoring process

That sounds weird. Please clarify.

> Note that in either model the counter readings are rounded. Windows rounds
> toward zero, which why you never get more load than 100%. But it is
> thinkable and expectable that some systems would round away from zero or to
> the nearest bound. So the statement holds only if you have A (maybe C) + a
> corresponding rounding.

So it holds within the accuracy of the measurement method, which often 
involves some sampling or rounding error. In my view.

>> - 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.
> 
> This also may be wrong if a B model is used. In particular, task switching
> may be (and I think is) driven by the programmable timer interrupts. The
> real-time clock may be driven by the TSC. Since these two are physically
> different, unsynchronized time sources, the effect can be any. It is to
> expect a systematic error accumulated with the time.

Again, it holds within the accuracy of the measurement method and the 
time source, which is all that one can expect.

The points I made were meant to show how CPU_Time is related, in 
principle, to real time. I entirely accept that in practice the 
relationships will be affected by measurement inaccuracies.

For the task scheduling methods that depend on actual execution times, I 
believe that long-term drifts or accumulations of errors in CPU_Time are 
unimportant. The execution time (span) measurements need to be 
reasonably accurate only over time spans similar to the period of the 
longest-period task. The overhead (execution time not charged to tasks) 
will probably be much larger, both in mean value and in variability, 
than the time-source errors.

As discussed earlier, the time source for Ada.Real_Time.Clock that 
determines when time-driven tasks are activated may need higher fidelity 
to real time.

>> The question is how much meaning should be read into ordinary words like 
>> "time" when used in the RM without a formal definition.
> 
> Time as physical concept is not absolute. There is no *the* real time, but
> many real times and even more unreal ones.

When RM D.14(11/2) defines "the execution time of a given task" as "the 
time spent by the system executing that task", the only reasonable 
reading of the second "time" is as the common-sense physical time, as 
measured by your wrist-watch or by some more precise clock.

Let's not go into relativity and quantum mechanics for this.

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