Re: Ada.Execution_Time

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

On Mon, 27 Dec 2010 22:11:18 +0200, Niklas Holsti wrote:

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

This is true for any value of any type due to finiteness. I think
D.14(12/2) refers to an ability to implement Split. But that is irrelevant.
CPU_Time is not declared numeric, it does not have +.

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

Because this is the only case where execution time might be any relevant to
the algorithm of task switching.

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

, which architecture makes execution time irrelevant to switching
decisions.

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

You forgot one external device called real time clock.

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

, which would be ill-advised to do.

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

Sorry, are you saying that lesser accuracy of real-time clock is a way to
achieve determinism?
 
> If your tasks suffer arbitrary millisecond-scale suspensions or 
> dispatching delays (as is rumored for Windows) a microsecond-level clock 
> accuracy is no help.

And conversely, the catastrophic accuracy of the VxWorks real-time clock
service does not hinder its usability for real-time application. Which is
my point. You don't need good real-time clock in so many real-time
applications, and you never need execution time there.

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

Exactly

> So this is irrelevant.

No, it is the execution time which is irrelevant for real-time systems,
because of the way tasks are activated there.

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

Why? It is straightforward: the task of higher priority level owns the
processor.

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

It is difficult to imagine. This is done either statically or else by
running tests. Execution time has drawbacks of both approaches and
advantages of none.

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

No, in our systems we use a different schema. The "fall back" values are
always evaluated first. They must become ready at the end of each cycle. A
finer estimation is evaluated in background and used when ready. Actually,
according to your schema, the finer estimation always "fail" because it is
guaranteed too complex for one cycle. It takes 10-100 cycles to compute at
least. So your schema would not work. In general, real-time systems are
usually designed for the worst case scenario, because when something
unanticipated indeed happens you could have no time to do anything else.
 
>>> 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).

A very good example. Now consider your perception of time. Does it
correspond to the real time? No it does not. The time spent in sleep can be
sensed from very short to very long. This felt time is an analogue of the
task execution time. You better do not use this subjective time to decide
when to have next meal. That could end in obesity.

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

What is the reason to use different sources?

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

Certainly the latter. Consider a system with n-processors. The execution
time second will be 1/n of the real time second. With shared memory it will
be f*1/n, where f is some unknown factor. That works in both directions, on
a single processor board with memory connected over some bus system, it
could be f<1, because some external devices might block CPU (and thus your
task) while accessing the memory. Note that the error is systematic. It is
not an approximation 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.

Since these conditions are never met, the model you have in mind is
inadequate (wrong).

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