Re: Fixed Frame Scheduling

[baker@IDA.ORG (Paul Baker)]

>>From: bagpiper@pnet02.gryphon.com (Michael Hunter)
>>Newsgroups: comp.lang.ada
>>Subject: Fixed Frame Scheduling
>>Date: 4 Dec 89 06:20:25 GMT
>>Sender: root@gryphon.COM

>>I have been implementing a fixed frame scheduler in Ada...  
>>If anyone has any hints please send them to me.

I've played with scheduling enough to have a few opinions, 
albeit mostly untested ones.

The program you want to write must handle 4 possibly 5 cases:
1) execute procedural steps on a scheduled basis.
2) execute low priority background jobs when time is available.
3) handle interrupt driven events
4) account for missed, scheduled steps (fail on case 1)
5) [possibly adapt schedule to prevent missed steps]

Case 2 is handled in any Ada environment with a continually running
task - which becomes the heart of the practical problem I will discuss
in a moment.

Case 3 can be handled if your Ada compiler lets you bind an
interrupt to a task entry point.  Most do that now. I don't know a
work-around if your compiler doesn't.

Case 1 requires some design analysis.  Steps with the same cycle
time are grouped together and run one after the other in a loop that
ends with computed delay statement.  Each cycle group becomes a
different task in the implementation.  

The computed delay is just the difference between the next cyclical
start time and the current time.  If that number is negative, whoops -
that's Case 4.  Notice that you have just detected "frame overrun" in
your Ada code.  Pre-Ada environments detect this at the operating
system level where the code doesn't understand the purpose of the
application and can't respond meaningfully.  If possible, detect when
the delay is getting small and consider rescheduling non-life-critical
activities to fail-soft when the interrupts overwhelm the system.
Rescheduling (Case 5) is optional but an awfully good idea.

If you want this to work right, you must understand how long each
cyclical step takes, how long each interrupt handling step takes, and
how often interrupts occur.  Before Ada, engineers knew without being
told that they will have to time their code to meet hard deadlines.
With Ada some feel AJPO guarentees an 8088 will trim the flaps on an
F-14 - no way! We're all smarter than that but here is the current
killer.

That background task is going to hang on to control until the Ada
run-time interrupts it.  On my PC that's 18 times a second but on my
old, unworthy Sun compiler it's only once a second.  Neither is
state-of-the-art response time.  Ideally, your vendor's Ada run-time
should actually schedule the delay statements in the cyclical tasks.
Ada does not require this, and it doesn't come as an extra-cost option
yet.  This should be a PIWG issue but I'm not up on the status of their
work.

Recommended workaround is this.  Go into your background processes,
understand how fast they execute and sprinkle "delay 0.0" statements in
the code with a sufficient density that no block of code will tie up
the cpu long enough the cause a missed deadline.  The delay 0.0
statements cause the run-time to look at its schedule and do the right
thing.  Sure, this isn't portable because the density of ad hoc delay
statements is cpu-dependent.  But hard-real-time scheduling can't be
cpu-independent or you could fly an F-14 with an 8088 or even a 1750A.
(My hat's off to those of you who try and even succeed!)

plb
____________________________________________________________________
Paul L. Baker        |       E-MAIL             | Phone:           |
CTA INCORPORATED     | baker@ida.org            |   (703) 845-3563 |
6116 Executive Blvd. | bakerp@ajpo.sei.cmu.edu  | Messages:        |
Rockville, MD 20815  |                          |   (301) 816-1242 |
--------------------------------------------------------------------