eberard@AJPO.SEI.CMU.EDU (10/20/87)
Concurrency is a concept that seems simpler than it really is. Most
people can easily envision two or more "processes" executing
simultaneously. However, concepts such as how concurrency behaves on a
single processor system as opposed to a multiple processor system,
deadlock, starvation, race condition, and inter-process communication
are not easily understood.
One of the fundamental characteristics of concurrency that is
difficult for most people to understand is the concept of
indeterminacy. Sequential software is deterministic i.e., one can
predict precisely how the software will behave (even at a microscopic
level of detail) for a given set of conditions. Concurrent software,
on the other hand, is nondeterministic. Specifically, while the
macroscopic behavior of the software may be reasonably predictable,
the microscopic behavior of the software cannot be predicted with a
high degree of precision.
Few programmers have an in-depth understanding of concurrency issues.
For example, there have been any number of complaints that "Ada does
not allow the programmer easy access to the underlying scheduling
algorithm," or that "Ada does not have a specific (published)
scheduling algorithm." Complaints such as these indicate little
knowledge of concurrency in software.
It is important for Ada software engineers to realize that if they
wish their concurrent software to behave in the same general manner
with any given Ada system, it is possible to implement their source
code in such a manner so that this can be accomplished, regardless of
such things as the underlying implementation of the scheduling
algorithm.
Recently, I have become aware of some attempts to get around the
"problem" of nondeterminism in concurrent Ada software. The code word
here is "tailoring." For example, some Department of Defense (DoD)
contractors have required that Ada development system vendors allow
their customers to supply their own scheduling algorithms for tasking.
(Note: All requests for tailoring are not attempts to circumvent good
software engineering. It is entirely reasonable for software engineers
to request some degree of tailoring. Further, there is a certain
degree of flexibility allowed by the standard. Finally, there are
issues which are truly "outside of Ada," and are properly addressed by
tailoring.)
"So what is the big deal," you ask, "if some DoD contractor requires
that the scheduling algorithm for tasking be supplied by the Ada
development system vendor, or that the vendor allow the contractor to
'tailor' the scheduling algorithm?" Suppose that the Ada software is
sold to the government and that it is recompiled in part, or in whole,
using a different Ada compiler. The software may not only behave in an
erroneous manner, but the cause of the erroneous behavior will not be
easily determined from a knowledge of the source code alone.
Further, suppose that all members of the development team are not
informed about the (now deterministic) task scheduling algorithm, or
that maintenance personnel are equally uninformed. Developing,
testing, debugging, and maintaining concurrent software is difficult
enough without attempting a partial removal of indeterminacy.
So we have a number of technical, legal, and ethical questions:
1. If an Ada software engineer just happens to know what the
underlying scheduling algorithm is, should he or she design their
Ada software in a manner which takes direct advantage of this
knowledge?
2. Should an Ada software developer require that an Ada development
system vendor supply the scheduling algorithm for tasking, with
the intention of using this knowledge in the design and
implementation of the Ada software?
3. How much "tailoring" of an Ada development is to be allowed?
Specifically, at what point (or points) do we cross the line
between issues which are truly outside of Ada, and issues which
are best left to "language lawyers"?
4. If certain types of tailoring or knowledge of the underlying
implementation are to be discouraged, what alternatives are
available to the Ada software developers?
5. Are there published lists of questionable practices relating to
the above? Are there any published policies?
On one hand, I am aware that some of the issues I have raised can be
resolved by "language lawyers." On the other hand, some of these
questions (and others) are clearly outside of domain of the Ada
language definition.
-- Ed Berard
(301) 695-6960
eberard@ajpo.sei.cmu.eduwerme@alliant.Alliant.COM (Ric Werme) (10/29/87)
In article <8710201049.AA16580@ajpo.sei.cmu.edu> eberard@AJPO.SEI.CMU.EDU writes on handling concurrency and determinism and asks the following questions. As an old time OS and realtime programmer (someone at CMU may still remember!) I'll toss my two bits in. For the purpose of this discussion, I'll concentrate on a system that is a realtime control system, i.e. an Ada program controlling an electro-mechanical system (be it rocket, power plant, dot-matrix printer, whatever). > 1. If an Ada software engineer just happens to know what the > underlying scheduling algorithm is, should he or she design their > Ada software in a manner which takes direct advantage of this > knowledge? In general any engineer should design for maximum portability and maintainability - unless the situation presents a strong reason otherwise. Taking advantage of local scheduling algorithms is not real portable.... On the other hand, knowing things like the time slice size is useful for, uh, well, it must be useful for something. I've never needed it. I have used the clock interrupt rate in a number of systems, that might apply here. > 2. Should an Ada software developer require that an Ada development > system vendor supply the scheduling algorithm for tasking, with > the intention of using this knowledge in the design and > implementation of the Ada software? Absolutely, if it's absolutely necessary. On a dot matrix printer I worked on I had to feed a FIFO every 500 usec. If I wanted to implement it in Ada (on a Z8??) I would ask about task response times before asking about anything else about the compiler. On the other hand, If I were writing a simulation of something, timing would be essentially no issue at all. > 3. How much "tailoring" of an Ada development is to be allowed? > Specifically, at what point (or points) do we cross the line > between issues which are truly outside of Ada, and issues which > are best left to "language lawyers"? ;l In some systems, much of the scheduling will be outside of Ada's domain. Alliant's Ada V1.1 is a good example. Our runtime has it's own task scheduler that schedules tasks on various processors. The tailoring within the Ada domain is the number of processors to use. For each processor we spawn a Unix process and the runtime runs tasks on any available process. Processors include IPs (slow I/O processors based on 68020's) and CEs (Fast computational processors designed for number crunching). We also allow tasks to run on the complex, a group of CEs running "concurrently". In our sense, concurrent means several CPUs running a single program in parallel. While the LRM makes it hard for Ada to do the vector/concurrent math the complex is for, we let Ada code call Fortran code to do fast matrix operations. On top of this Ada tailoring, we have hooks into Unix that adjusts the number of CEs devoted to the complex and the amount of time they run as the complex. All this makes it awfully hard to publish a description of how our tasks are scheduled, and even harder to take advantage of the scheduler. And of course, since the system is timeshared with other users, there's no way you'll get anything deterministic. > 4. If certain types of tailoring or knowledge of the underlying > implementation are to be discouraged, what alternatives are > available to the Ada software developers? I'm only working on Ada temporarily, so I'm not sure what you need. In general, the realtime, multitasking software I've worked on needs: 1) High priority tasks - things that get cycles as soon as possible when it needs them. 2) Access to interrupt service routines. These run essentially outside of tasks, and I don't think are covered by the LRM. 3) Interprocess communication (which can become interesting when a high priority task fills the buffers going to a low priority task). 4) Multiple priority levels - often useful in fixing problems due to 3). 5) Guaranteed access - tasks sometime need say, a second of cpu time every ten seconds. For example, a task that positions the control rods in a fission reactor isn't high priority, and doesn't have to be done on a regular basis, but it does need to be done. (Incidentally, process control systems have been all but ignored by computer science, although many of its discoveries are applicable. Scheduler research is good example - everything I've read has been on getting things done as efficiently as possible. My father designed a process control computer that had a hardware scheduler that switched register sets (including the PC) each clock tick. Sort of the ultimate round robin scheduler.) I fondly remember a couple of graphics hacks I wrote using a PDP-11 P&V kernel a friend wrote at Harvard. It didn't do much about interprocess communication or guaranteed access, but it handled the rest very nicely. > 5. Are there published lists of questionable practices relating to > the above? Are there any published policies? I can't help on this, except to suggest listening to what OS people have to say. The race conditions we have to deal with in OS's can be awfully painful to track down (they're even worse in networking - just ask them!) I suspect that many Ada programmers will be surprised and ill prepared to deal with such things. 6. Can determinism be achieved? [My question] No. At least, not in many systems that deal with the real world. Consider the carriage of a dot matrix printer. The carriage motor drives the head back and forth. With a stepping motor things may be deterministic, with a DC motor they can't be. Different motors have different torques, the bearings have different frictions, and everything changes with age. Each pass of the printhead will be as different as snowflakes. I don't worry about about determinism in software - I haven't seen much of it in my 19 years with computers. The biggest challenge in my mind is writing debuggers that can handle a multi-tasking environment and can simulate the various timing problems that will occur. It may be that Ada, with all its handholding and insistance on programming structure, may become best known for the new minefield it's springing on the unwary. -- | The Art of Programming | Eric J Werme | | needs to be tempered with | uucp: decvax!linus!alliant | | the Structure of Engineering | Phone: 603-673-3993 |