Re: Ada.Execution_Time

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Mon, 27 Dec 2010 14:44:53 +0200, Niklas Holsti wrote:

> Dmitry A. Kazakov wrote:
>> On Sat, 25 Dec 2010 13:31:27 +0200, Niklas Holsti wrote:
>> 
>>> Dmitry A. Kazakov wrote:
>>>> On Sat, 18 Dec 2010 23:20:20 +0200, Niklas Holsti wrote:
>>> ...
>>>>> The concept and measurement of "the execution time of a task" does
>>>>> become problematic in complex processors that have hardware 
>>>>> multi-threading and can run several tasks in more or less parallel
>>>>> fashion, without completely isolating the tasks from each other.
>>>> No, the concept is just fine,
>>> Fine for what? For schedulability analysis, fine for on-line scheduling,
>>> ... ?
>> 
>> Applicability of a concept is not what makes it wrong or right.
> 
> I think it does. This concept, "the execution time of a task", stands 
> for a number. A number is useless if it has no application in a 
> calculation.

Technically, CPU_Time is not a number in any sense. It is not a numeric Ada
type and it is not a model of a mathematical number (not even additive).

Anyway, the execution time can be used in calculations independently on
whether and how you could apply the results of such calculations.

You can add the height of your house to the distance to the Moon, the
interpretation is up to you.

>>> However, this is a side issue, since we are (or at least I am)
>>> discussing what the RM intends with Ada.Execution_Time, which must be
>>> read in the context of D.2.1, which assumes that there is a clearly
>>> defined set of "processors" and each processor executes exactly one
>>> task at a time.
>> 
>> Why?
> 
> Because RM D.14 uses terms defined in RM D.2.1, for example "executing".

These terms stay valid for non-real time systems.

>> Scheduling does not need Ada.Execution_Time,
> 
> The standard schedulers defined in the RM do no not need 
> Ada.Execution_Time but, as remarked earlier in this thread, one of the 
> purposes of Ada.Execution_Time is to support the implementation of 
> non-standard scheduling algorithms that may make on-line scheduling 
> decisions that depend on the actual execution times of tasks. For 
> example, scheduling based on "slack time".

Even if somebody liked to undergo such an adventure, he also could use
Elementary_Functions in the scheduler. That would not make the nature of
Elementary_Functions any different.

>> it is the Ada.Execution_Time implementation, which needs some
>> input from the scheduler.
> 
> We must be precise about our terms, here. Using terms as defined in 
> http://en.wikipedia.org/wiki/Task_scheduling, Ada.Execution_Time needs 
> input from the task *dispatcher* -- the part of the kernel that suspends 
> and resumes tasks.

Let's call it dispatcher. Time sharing needs some measure of consumed CPU
time. My points stand:

1. Time sharing has little to do with real-time systems.

2. It would be extremely ill-advised to use Ada.Execution_Time instead of
direct measures for an implementation of time sharing algorithms.

>> How do you explain that CPU_Time, a thing about time sharing, appears in
>> the real-time systems annex D?
> 
> You don't think that execution time is important for real-time systems?

Real-time systems work with the real-time, they real-time intervals
(durations) are of much minor interest. Execution time is of no interest,
because a real-time system does not care to balance the CPU load.

> In my view, CPU_Time is a measure of "real time", so its place in annex 
> D is natural. In your view, CPU_Time is not "real time", which should 
> make *you* surprised that it appears in annex D.

It does not surprise me, because there is no "time-sharing systems" annex,
or better it be "it is not what you think" or "if you think you need this,
your are wrong." There are some other Ada features we could move there.
(:-))

>>> You have
>>> not given any arguments, based on the RM text, to support your position.
>> 
>> I am not a language lawyer to interpret the RM texts. My argument was to
>> common sense.
> 
> To me it seems that your argument is based on the difficulty (in your 
> opinion) of implementing Ada.Execution_Time in some OSes such as MS 
> Windows, if the RM word "time" is taken to mean real time.
> 
> It is common sense that some OSes are not designed (or not well 
> designed) for real-time systems. Even a good real-time OS may not 
> support all real-time methodologies, for example scheduling algorithms 
> that depend on actual execution times.

I disagree with almost everything here. To start with, comparing real-time
clock services of Windows and of VxWorks, we would notice that Windows is
far superior in both accuracy and precision. Yet Windows is a half-baked
time-sharing OS, while VxWorks is one of the leading real-time OSes. Why is
it so? Because real-time applications do not need clock much. They are
real-time because their sources of time are *real*. These are hardware
interrupts, while timer interrupts are of a much lesser interest. I don't
care how much processor time my control loop takes so long it manages to
write the outputs when the actuators expect them. Measuring the CPU time
would bring me nothing. It is useless before the run, because it is not a
proof that the deadlines will be met. It useless at run-time because there
are easier and safer ways to detect faults.

>>>>>> I am not a language lawyer, but I bet that an implementation of 
>>>>>> Ada.Execution_Time.Split that ignores any CPU frequency changes
>>>>>> when summing up processor ticks consumed by the task would be
>>>>>> legal.
>>>>> Whether or not such an implementation is formally legal, that would
>>>>> require very perverse interpretations of the text in RM D.14.
>>>> RM D.14 defines CPU_Tick constant, of which physical equivalent (if
>>>> we tried to enforce your interpretation) is not constant for many
>>>> CPU/OS combinations.
>>> The behaviour of some CPU/OS is irrelevant to the intent of the RM.
>> 
>> Nope, one of the killer arguments ARG people deploy to reject most
>> reasonable AI's is: too difficult to implement on some obscure platform for
>> which Ada never existed and never will. (:-))
> 
> Apparently such arguments, if any were made in this case, were not valid 
> enough to prevent the addition of Ada.Execution_Time to the RM.

That is because ARG didn't intend to reject it! Somebody wanted it no
matter what (like interfaces, limited results, asserts, then, like, I am
afraid, if-operators now). The rest was minimizing the damage...

> Is your point that Ada.Execution_Time was accepted only because the ARG 
> decided that the word "time" in RM D.14 should not be understood to mean 
> real time? I doubt that very much... Surely such an unusual meaning of 
> "time" should have been explained in the RM.

It is explained by its name: "execution time." Execution means not real,
unreal time (:-)).

>>> As already said, an Ada implementation on such CPU/OS could
>>> use its own mechanisms for execution-time measurements.
>> 
>> Could or must? Does GNAT this?
> 
> I don't much care, it is irrelevant for understanding what the RM means. 
> Perhaps the next version of MS Windows will have better support for 
> measuring real task execution times; would that change the intent of the 
> RM? Of course not.

You suggested that Ada implementations would/could attempt to be consistent
with your interpretation of CPU_Time. But it seems that at least one of the
leading Ada vendors does not care. Is it a laziness on their side or maybe
you just expected too much?

>>> 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.
>> 
>> If that was the intent, then I really do not understand why CPU_Time was
>> introduced in addition to Ada.Real_Time.Time / Time_Span.
> 
> Because (as I understand it) different processors/OSes have different 
> mechanisms for measuring execution times and real times, and the 
> mechanism most convenient for CPU_Time may use a different numerical 
> type (range, scale, and precision) than the mechanisms and types used 
> for Ada.Real_Time.Time, Time_Span, and Duration.

I see no single reason why this could happen. Obviously, if talking about a
real-time system as you insist, the only possible choice for CPU_Time is
Time_Span, because to be consistent with the interpretation you propose it
must be derived from Ada.Real_Time clock.

My point is that RM intentionally leaves it up to the implementation to
choose a CPU_Time source independent on Ada.Real_Time.Clock. This why
different range and precision come into consideration.

>>> And you still have not defined what you mean by "simulation time", and
>>> how you come there from the RM text.
>> 
>> Simulation time is a model of real time a physical process might have under
>> certain conditions.
> 
> Thank you. But I still do not see how your definition could be applied 
> in this context, so we are back at the start of the post... :-)

Under some conditions (e.g. no task switching) an execution time interval
could be numerically equal to a real time interval.

But in my view the execution time is not even a simulation time of some
ideal (real) clock. It is a simulation time of some lax recurrent process,
e.g. scheduling activity, of which frequency is not even considered
constant. It can be any garbage, and it likely is.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de