Re: Using "delay until" in real-time

[Martin Gangkofer <mgangkof@esg-gmbh.de>]

Hello Ted,

I have seen your problem and I have seen a lot of answers, which seem to be
quite far away from the real problem. There is a german phrase, which would
translate into English like this: "Between the blind, the one-eyed is the
king". Well closing one eye I see a solution for your problem .. (Just some
motivation for all the greenhornes around),. in fact I know the problem from
another project and I also know the solution.
The problem you have is one of accuracy, you are getting a systematic error,
because your are using an inaccurate increment. The correct term for this kind
of problem, as I remember lessons on numerical mathmatics, is that the
algorithm you are using is badly conditioned and has to be turned into a well
conditioned algorithm:
Imagine the problem of drawing a straight line through two points, as closer
the points gets to each other the bigger is the deviation you get for a point
far  away. So thats exactly what you have done! You have chosen the smallest
possible separation of two points and expected accuracy forever, this kind of
approach only works in case of zero error and as computers usually use binary
arithmetics, this is only true if the frequency is can be expressed as
something like

    f = 1 / ( SIGMA(  a[i] * 2**i ) );

I have two solution solutions for you , both based on the idea to draw your
(imagined) straight line between two points which are separated as much as
possible, i.e. basically you take the start time of your task and the current
time. The solution is similar to the algorithm used to draw a straight line on
your screen.

1st solution:
=========
You have a defined start point (the startup time of your task) and a defined
end point, i.e. the current time.
Express the period in the form of a precise fixed point number:  1/f = dx / dy,
where dx and dy are integers.
Use a counter (n) to count cycles.

Use integer arithmetics, which is 100% accurate to calculate next time:

    NextTime  =  StartTime + ( 1/f ) * n  =  StartTime + ( n * dx ) / dy;

By calculating ( n * dx ) first and then divide you get a single error, which
do not accumulate.

2nd solution;
==========

(perhaps more fancy, but basically the same idea: use only a single unprecise
operation, it is just another way of using a counter)
Use precise fixed point arithmetics. Assuming the compiler does only use binary
deltas (I think the LRM does leave this open, but I am not sure), at least the
compiler I was using provided only binary deltas.

Then chose a fixed point type, which is able to accurately represent the period
you need:

    T = 1 / 60 = 1 / 2 / 2 / 3 / 5 ;

==> (only a choice)
type Precise_Time is delta 0.25;  -- Unit of time is 1/15 sec

Iteration : constant Precise_Time := 0.25;
Next_Time : Precise_Time := 0;
Start_Time : constant Ada.Real_Time.Time := Ada.Real_Time.Clock;
begin
   loop
         ....

        Next_Time := Next_Time + Iteration;
        delay until Start_Time + Ada.Real_Time.Time( Next_Time );
    end loop
end;

In this case the unprecise operation is the type cast.

I hope this helped you,
kind regards
Martin Gangkofer


Ted Dennison schrieb:

> I came across an interesting problem the other day that I'd like to
> share, in the hopes that someone here has another solution that the ones
> we thought up.
>
> We have a real-time scheduler that uses the "delay until" statement to
> perform its scheduling. So far, this shouldn't shock anyone, as
> real-time scheduling is supposedly what "delay until" was put in the
> language for.
>
> Our scheduling code looks something like this (very simplified, and not
> compiled. My apologies ahead of time if Deja screws up the formatting):
>
> ---
> Iteration_Hz : constant Float := 60.0;
>
> task Executive is
>    Iteration : constant Ada.Real_Time.Time_Span
>       := Ada.Real_Time.To_Time_Span (Duration(1.0/Iteration_Hz));
>
>    Next_Time : Ada.Real_Time.Time := Ada.Real_Time.Clock + Iteration;
> begin
>    loop
>       -- Perform scheduling tasks
>       ...
>
>       Next_Time := Next_Time + Iteration;
>       delay until Next_Time;
>    end loop;
> end Executive;
>
> ---
>
> That looks pretty straightforward, right? Well, unfortunately, its *WRONG*.
>
> 1/60 works out to about 0.016(6-repeating). That can't be accurately
> represented in an IEEE floating-point register. So what we get is
> something like 0.016667 (forgive me if I'm rounding the wrong digit).
> That rouding error slowly accumulates over time, until after about 52
> seconds our poor Executive task skips a tick. On our system ticks come
> at 240Hz, so that means that once every 52 seconds the executive
> scheduler waits about 20ms instead of 16.6(6-repeating)ms. Of course
> this wreaks havoc in our hard-realtime system.
>
> So the question is, what's the best way to solve this problem? Here's
> what we came up with so far:
>
>   o  Use the RTOS' "taskDelay" function to delay the appropriate amount
> of ticks (4).
>
> I don't like this one, as its a non-Ada solution, and thus renders our
> scheduler non-portable. Its also succeptable to drift if something
> causes an extra tick to pass before we get to the taskDelay.
>
>   o  Check the Ada.Real_Time.Clock every cycle when we awaken, and add
> the Iteration to that for the "delay until".
>
> I don't like this because the clock check is going to be fairly
> expensive, and this solution is also succeptable to drift.
>
>   o  Figure out what the denominator is (60 in this case), and redo the
> calculation every time that number of runs have happened.
>
> For instance, in the above code, I'd add something like:
>       Runs := Runs + 1;
>       if Runs >= Natural(Iteration_Hz) then
>          -- Adjust for drift due to rounding errors.
>          Runs := 0;
>          Run_Time := Run_Time + Ada.Real_Time.To_Time_Span (1.0);
>          Next_Time := Run_Time;
>       else
>          Next_Time := Next_Time + Iteration;
>       end if;
>
> I kind of like this option, as it is a mathematical solution to what is,
> in essence, a mathematical problem. This ought to work as long as the
> denominator can be counted on to be a whole (natural) number. In my
> case, I think it can.
>
> Since this problem should happen to anyone using "delay until" with an
> iteration rate divisible by 3, and 60, 30, and 15Hz are common rates in
> the industry, I can't be the first person to stumble on this problem.
> How does everyone else handle it?
>
> --
> T.E.D.
>
> http://www.telepath.com/~dennison/Ted/TED.html
>
> Sent via Deja.com
> http://www.deja.com/