Re: Ada.Execution_Time

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

Dmitry A. Kazakov wrote:
> 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).

RM D.14(12/2): "The type CPU_Time represents the execution time of a 
task. The set of values of this type corresponds one-to-one with an 
implementation-defined range of mathematical integers". Thus, a number.

However, the sub-thread above was not about CPU_Time in 
Ada.Execution_Time, but about the general concept "the execution time of 
a task". (Serves me right for introducing side issues, although my 
intentions were good, I think.)

> 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.

You are being absurd.

Dmitri, your arguments are becoming so weird that I am starting to think 
that you are just trolling or goading me.

>>> 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.

What do you mean by "time sharing"? The classical mainframe system used 
interactively by many terminals? What on earth does that have to do with 
our discussion? Such a system of course must have concurrent tasks or 
processes in some form, but so what?

If by "time sharing algorithms" (below in your point 2) you mean what is 
usually called "task scheduling algorithms", where several tasks 
time-share the same processor by a task-switching (dispatching) 
mechanism, your point 1 is bizarre. Priority-scheduled task switching is 
the canonical architecture for 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.

If by "direct measures" you mean the use of some external measuring 
device such as an oscilloscope or logic analyzer, such measures are 
available only externally, to the developers, not within the Ada program 
itself. The whole point of Ada.Execution_Time is that it is available to 
the Ada program itself, enabling run-time decisions based on the actual 
execution times of tasks.

> 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.

I am made speechless (or should I say "typing-less"). If that is your 
view, there is no point in continuing this discussion because we do not 
agree on what a real-time program is.

>>>> 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.

So what? Real-time systems need determinism. The clock only has to be 
accurate enough.

If your tasks suffer arbitrary millisecond-scale suspensions or 
dispatching delays (as is rumored for Windows) a microsecond-level clock 
accuracy is no help.

> 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.

Both are important. Many control systems are driven by timers that 
trigger periodic tasks. In my experience (admittedly limited), it is 
rare for sensors to generate periodic input streams on their own, they 
must usually be sampled by periodic reads. You are right, however, that 
some systems, such as automobile engine control units, have external 
triggers, such as shaft-rotation interrupts.

Anyway, your point has do to with the "time" that *activates* tasks, not 
with the measurement of task-specific execution times. So this is 
irrelevant.

> 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.

You should care, if the processor must also have time for some other 
tasks of lower priority, which are preempted by the control-loop task.

> 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.

In some cases (simple code or extensive tests, deterministic processor) 
CPU-time measurements can be used to prove that deadlines are met. But 
of course static analysis of the worst-case execution time is better.

> It useless at run-time because there
> are easier and safer ways to detect faults.

If you mean "deadline missed" or "task overrun" faults, you are right 
that there are other detection methods. Still, Ada.Execution_Time may 
help to *anticipate*, and thus mitigate, such faults.

For example, assume that the computation in a control algorithm consists 
of two consecutive stages where the first stage processes the inputs 
into a state model and the second stage computes the control outputs 
from the state model. Using Ada.Execution_Time or 
Ada.Execution_Time.Timers the program could detect an unexpectedly high 
CPU usage in the first stage, and fall back to a simpler, faster 
algorithm in the second stage, to ensure that some control outputs are 
computed before the deadline.

But you are again ignoring other run-time uses of execution-time 
measurements, such as advanced scheduling algorithms.

>> 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 (:-)).

Nonsense. I spend some part of my time asleep, some time awake. Both 
"sleeping time" and "awake time" are (pieces of) real time. A task 
spends some of its time being executed, some of its time not being 
executed (waiting or ready).

>>> 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.

I have only said that the sum of the CPU_Times of all tasks executing on 
the same processor should be close to the real elapsed time, since the 
CPU's time is shared between the tasks. This does not mean that 
Ada.Execution_Time.CPU_Time and Ada.Real_Time.Time must have a common 
time source, only that both time sources must approximate physical, real 
time.

> 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.

I agree. But in both cases the intent is to approximate physical, real 
time, not some "simulation time" where one "simulation second" could be 
one year of real time.

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

Yes! Therefore, under these conditions, CPU_Time (when converted to a 
Time_Span or Duration) does have a physical meaning. So we agree. At last.

And under the task dispatching model in RM D.2.1, these conditions can 
be extended to task switching scenarios with the result that the sum of 
the CPU_Times of the tasks (for one processor) will be numerically close 
to the elapsed 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.

You may well have this view, but I don't see that your view has anything 
to do with Ada.Execution_Time as defined in the Ada RM.

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