bagpiper@pnet02.gryphon.com (Michael Hunter) (12/04/89)
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.comstt@inmet.inmet.com (12/04/89)
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
baker@IDA.ORG (Paul Baker) (12/04/89)
>>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 | --------------------------------------------------------------------
eachus@aries.mitre.org (Robert I. Eachus) (12/06/89)
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...