From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=0.7 required=5.0 tests=BAYES_00,MSGID_RANDY
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,f8311a3a7edd715,start
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2000-12-12 08:40:08 PST
Path: 
 supernews.google.com!sn-xit-02!supernews.com!newsfeed.mesh.ad.jp!feed2.onemain.com!feed1.onemain.com!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!nntp2.deja.com!nnrp1.deja.com!not-for-mail
From: Ted Dennison <dennison@telepath.com>
Newsgroups: comp.lang.ada
Subject: Using "delay until" in real-time
Date: Tue, 12 Dec 2000 16:27:31 GMT
Organization: Deja.com - Before you buy.
Message-ID: <915jl7$jt5$1@nnrp1.deja.com>
NNTP-Posting-Host: 204.48.27.130
X-Article-Creation-Date: Tue Dec 12 16:27:31 2000 GMT
X-Http-User-Agent: Mozilla/5.0 (Windows; U; WinNT4.0; en-US;
 m18) Gecko/20001207
X-Http-Proxy: 1.0 x58.deja.com:80 (Squid/1.1.22) for client 204.48.27.130
X-MyDeja-Info: XMYDJUIDtedennison
Xref: supernews.google.com comp.lang.ada:2998
Date: 2000-12-12T16:27:31+00:00
List-Id: <comp.lang.ada>

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/