Fixed Frame Scheduling

Fixed Frame Scheduling

[Michael Hunter]

I have been implementing a fixed frame scheduler in Ada.  I had initially
planned (note for TH: designed) to do the context switches in some assembly
glue.  This was mainly due to the fact that I didn't feel comfortable enought
with Ada tasking to get the job done in time..I thought.  But after reading
some more in the LRM and Cohen I think I almost see a way.  If anyone has any
hints please send them to me.

(What I mean by fixed frame scheduler is the ability to start the execution of
a task for some predetermined amount of time, and then cut it off.  This looks
like round robin scheduling with very well defined time slices.  I just havn't
figured out how to allow the calling task to get control back from the
acceptor.)

I am working on a vax under VMS and will be running this program at the
highest priority...so I shouldn't have too much problem ensuring that it gets
a lot of CPU.  I would entertain solutions that use features specific to VMS
or specific to VAX Ada...but I would rather see a clean, portable, Ada
solution.

                                Michael

Mike Hunter - Box's and CPU's from HELL: iapx80[012]86, PR1ME 50 Series, 1750a
UUCP: {ames!elroy, <routing site>}!gryphon!pnet02!bagpiper
INET: bagpiper@pnet02.gryphon.com

Re: Fixed Frame Scheduling

[stt]

You haven't given enough information on "fixed-frame scheduling"
for me to give you a complete answer.  However, most
Ada tasking issues having to do with getting control
back to a caller involve allocating a "buffer task" of
some sort, and passing control to the caller via the buffer
task.  The initial call returns immediately, with an
access to a buffer task returned.  The caller then
calls an entry of the buffer task, remaining suspended
until the buffer task accepts it.  At a later time, 
the acceptor calls a different entry of the buffer
task which allows the buffer task to accept the
entry upon which the original caller is suspended.
In this way, the acceptor can control the activity
of the original caller without having to be itself
suspended as long as is the caller.

I don't really see how this would solve your
scheduling problem, but maybe you do... :-}

S. Tucker Taft
Intermetrics, Inc.
Cambridge, MA  02138

Re: Fixed Frame Scheduling

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

Re: Fixed Frame Scheduling

[Robert I. Eachus]

In article <23041@gryphon.COM> bagpiper@pnet02.gryphon.com (Michael Hunter) writes:

> (What I mean by fixed frame scheduler is the ability to start the
> execution of a task for some predetermined amount of time, and then
> cut it off.  This looks like round robin scheduling with very well
> defined time slices.  I just havn't figured out how to allow the
> calling task to get control back from the acceptor.)


     The answer to the original question is easy.  However, every time
I give it to someone requesting a cyclic scheduler, they want some
other solution.  (Which is in general a "good thing", the other
solutions are easier in Ada, and usually don't cause the plane to
crash.)  First of all, the executive has to have a priority higher
than all the application tasks.  Then each application task calls a
specific entry of the executive which is accepted (every appropriate
clock interval) to allow the application to run:

       task EXECUTIVE is
         entry CLOCK_INTERRUPT;
         entry GO(1..N);
         pragma PRIORITY(PRIORITY'LAST);
       end EXECUTIVE;

      An entry family makes the example simpler, but an actual
application will usually have many different entry declarations.
Notice that under no circumstances do you want two tasks queueing for
the same executive entry.

      task body EXECUTIVE is
      begin
        -- Create and initialize application tasks here or in the main
        -- program.
        loop
	  for I in 1..N loop
	    accept CLOCK_INTERRUPT;
	    accept GO(I);
          end loop;

        -- Now check for out of control tasks.  Note that in this
	-- version a timing slot is dedicated to this purpose.
	-- Alternatives are to make this part of one of the
	-- application tasks, or to check each task during its time
	-- slot (using selective waits).  Implementation of the
	-- alternatives is left to the designer.

          accept CLOCK_INTERRUPT;
          for I in 1..N loop
            if GO(I)'COUNT = 0 -- Uh oh!
            then
	      abort TASKS(I);
	      TASKS(I) := NEW_TASK(I);
            end if;
          end loop;

        end loop;       
      end EXECUTIVE;

    Application tasks look like:

      task type APPLICATION_TASK is
      begin
        loop
          EXECUTIVE.GO(I);
          DO_SOMETHING;
        end loop;
      end APPLICATION_TASK;

     If the task priorities are equal to their index, then lower
priority tasks come earlier in the cycle and are allowed to use any
free time later in the schedule without being aborted.  During
development of course the executive should check immediately for
overruns.

     Once you start writing executives and application tasks like
this, as I said above, the system designer will ask for some less
draconian paradigm which shuffles resources to meet current
requirements.  With this design it is very easy to do.  For example,
you may want to allow some tasks to skip one cycle of input before it
is killed, or some high priority tasks can be allowed to overrun their
slot and prevent a lower priority task from ever being started.

     By the time you are finished the design will look nothing like
what you started out to build, BUT 1) The changes will all be in the
executive program.  2) The system will be much more robust in the face
of unanticipated loads.  3) You may never execute an abort statement.

    Good luck...
--

					Robert I. Eachus

with STANDARD_DISCLAIMER;
use  STANDARD_DISCLAIMER;
function MESSAGE (TEXT: in CLEVER_IDEAS) return BETTER_IDEAS is...