PETCHER%SVDSD@eg.ti.COM (02/21/88)
Mike Linnig asks: > My question is... are we losing something here? Is there > a value to having multiple priorities even if we don't > have preemptive scheduling? My answer is an emphatic YES. Granted, in a general purpose, multi-user system multiple priorities lose a lot of meaning if a user can toss in a program that executes forever and the OS cannot regain control. However in an embedded, real-time system tasks can be (and should be) designed to cooperate. This means, among other things, a task should not execute indefinitely, and in fact should be designed to complete its intended function within a predictable period of time. This is consistent with most actual embedded applications, where a processor has certain inputs producing data at some predictable rate, and each task has some part in processing this data and producing the aggregate output of the system at some required rate. I have used prioritized, non-preemptive scheduling with reasonable success on a couple of recent projects (not using Ada.) The scheduling method used is one in which the scheduler searches a table of bid flags in order of descending task priority until it finds a flag set, whereupon it calls the task at an entry point supplied from another, corresponding table. When the called task exits (returns to the scheduler) the table search is started over from the top, thus guarranteeing the highest priority, eligible task never waits more than one tasks execution time before getting control. If the table is exhausted, meaning no tasks are bid, the scheduler continues to search it circularly until one is (in this case, necessarily, due to an interrupt.) To maintain performance goals and assure higher priority tasks are executed relatively soon, functions requiring excessive time are either broken up into multiple tasks, each completing its part of a process then bidding the next in the sequence, or are implemented as a single task with multiple checkpoints. The advantages to this method are time efficiency, since no context saving and restoring are required, ease of implementing the scheduler code itself, consisting of some half dozen lines of executable code in C, and the corresponding space efficiency. The main disadvantage lies in the need for all software designers on a project to be cognizant of task execution time constraints and stay within them. Malcolm Petcher Texas Instruments, Inc.
wes@wsccs.UUCP (Barnacle Wes) (03/01/88)
In article <8802202149.AA07429@ajpo.sei.cmu.edu>, PETCHER%SVDSD@eg.ti.COM writes: > Mike Linnig asks: > > My question is... are we losing something here? Is there > > a value to having multiple priorities even if we don't > > have preemptive scheduling? > > My answer is an emphatic YES. > [...] > This means, among other things, a task should not execute > indefinitely, and in fact should be designed to complete its intended > function within a predictable period of time. This is consistent with most > actual embedded applications, where a processor has certain inputs producing > data at some predictable rate, and each task has some part in processing this > data and producing the aggregate output of the system at some required rate. This is a workable, but simplistic viewpoint. The C3 systems I have worked on tended to be rather large and complicated, both in their scope and implementation. These systems typically had several background tasks to execute, and in some cases, several priorities of background tasks. To accomplish this without pre-emptive scheduling would be very difficult, perhaps impossible. At any rate, *I* wouldn't want to do it :-). Most of these systems achieved a simplicity at the low level by using features that the system gave them. For instance, on a system that has it's mass storage on a rotating drum device (OK, stop that snickering NOW!) the drum device driver is passed the address of a routine to execute when the I/O operation has completed. The driver does this by scheduling the routine in the I/O call at the time when the I/O operation will be completed. For a variety of reasons, once this routine is scheduled, it needs to execute ASAP according to the priority scheme used in the system. This would be difficult to do without using pre-emption. -- /\ - " Against Stupidity, - {backbones}! /\/\ . /\ - The Gods Themselves - utah-cs!utah-gr! / \/ \/\/ \ - Contend in Vain." - uplherc!sp7040! / U i n T e c h \ - Schiller - obie!wes
fortin@zap.UUCP (Denis Fortin) (03/07/88)
In article <8802202149.AA07429@ajpo.sei.cmu.edu> PETCHER%SVDSD@eg.ti.COM writes: > Mike Linnig asks: > > Is there a value to having multiple priorities even if we don't > > have preemptive scheduling? > > My answer is an emphatic YES. [...] in an embedded, real-time system > tasks can be (and should be) designed to cooperate. This means, among > other things, a task should not execute indefinitely, and in fact should > be designed to complete its intended function within a predictable > period of time. Well, I agree that non-preemptive prioritized task scheduling makes sense for some applications. But in order for it to work, a task has to be able to explicitly return the control to the "scheduler" when it has expended its time slice. The only unobtrusive way I can see to force a rescheduling event to occur in Ada is a "delay 0.0" statement. Unfortunately, I'm told that some compilers treat this as a no-op and simply ignore it. Has anybody encountered such a compiler? If so, is it legal? (section 9.6 of the LRM does say about the delay statement: "The execution of a delay statement evaluates the simple expression, and suspends further execution of the task that executes the delay statement [...]") -- Denis Fortin | fortin@zap.UUCP CAE Electronics Ltd | philabs!micomvax!zap!fortin The opinions expressed above are my own | fortin%zap.uucp@uunet.uu.net
barmar@think.COM (Barry Margolin) (03/10/88)
In article <415@zap.UUCP> fortin@zap.UUCP (0000-Denis Fortin) writes: >Well, I agree that non-preemptive prioritized task scheduling makes >sense for some applications. But in order for it to work, a task has to >be able to explicitly return the control to the "scheduler" when it has >expended its time slice. In a non-preemptive environment, there wouldn't be any notion of "time slice". A task returns control to the scheduler any time it executes a DELAY, ACCEPT, SELECT, or INITIATE statement, or when it calls a task entry. In this case, the purpose of task priorities is not to cause low-priority tasks to be suspended immediately, but to guide the choice of a new task to run when a task intentionally gives up the processor. If the tasks do a good deal of asynchronous I/O, they will give up the processor frequently while waiting for input or for an output buffer to empty. So you can get something that approximates preemptive scheduling. On Multics, we have software that implements non-preemptive prioritized multitasking in a process, using precisely this scheme, being used for network servers, so that one process can handle all incoming mail simultaneously; when one task goes blocked waiting for the text of a message another task can deliver its message. There's a controller task with high priority that waits for commands from the system operator; if a command is sent, it will always run as soon as one of the server tasks goes blocked for network input. (As an aside, it is theoretically possible to do pre-emptive scheduling with the above software, by using timer-driven process interrupts (similar to Unix signals), and having the timer interrupt handler invoke the multi-tasking scheduler, but I don't think anyone has actually tried this.) Barry Margolin Thinking Machines Corp. barmar@think.com uunet!think!barmar
terry@moogvax.UUCP (Terry Westley) (03/10/88)
In article <17701@think.UUCP> barmar@fafnir.think.com.UUCP (Barry Margolin) writes: >In a non-preemptive environment, there wouldn't be any notion of "time >slice". A task returns control to the scheduler any time it executes >a DELAY, ACCEPT, SELECT, or INITIATE statement, or when it calls a >task entry. I know about DELAY, ACCEPT, SELECT, and entry calls, but what is an INITIATE statement? -- Terry Westley Moog, Inc. (no, not the synthesizer company) East Aurora, NY 14052-0018 {boulder,decvax,rocksanne,rutgers,ames}!sunybcs!moogvax!terry
barmar@think.COM (Barry Margolin) (03/11/88)
In article <709@moogvax.UUCP> terry@moogvax.UUCP (Terry Westley) writes: >In article <17701@think.UUCP> barmar@fafnir.think.com.UUCP (Barry Margolin) writes: >I know about DELAY, ACCEPT, SELECT, and entry calls, but what is an >INITIATE statement? Perhaps my Ada text ("Programming with Ada: An Introduction by Means of Graduated Examples", by Peter Wegner) is out of date (it was published in 1980, so it was based on the original spec). INITIATE is the statement it uses to start a task. I don't actually do any real programming in Ada, so I haven't kept abreast of all the little changes that were made to the language between the time Green was chosen and it was standardized. Barry Margolin Thinking Machines Corp. barmar@think.com uunet!think!barmar