This paper appeared originally in Proc. 23rd ACM-SIGCSE Technical Symposium on Computer Science Education, Kansas City, MO, March 1992. We have added some hyperlinks, a brief update at the end, and several new references.
INTRODUCTION
PORTABILITY AS AN EDUCATION
ISSUE
MACHINE DEPENDENCE AND INDEPENDENCE
AS AN EDUCATION ISSUE
THE DINING PHILOSOPHERS
THE PORTABLE DINERS
ENCAPSULATING MACHINE
DEPENDENCIES
PORTABILITY TESTS
DISCUSSION
UPDATE
REFERENCES
This paper describes a course-related project in concurrent programming using the Ada language. Dijkstra's famous "dining philosophers" problem [Dijkstra 71] is used as a vehicle for developing a program rich enough in system construction problems to be realistic yet small enough to be manageable in a classroom situation. The program--Portable Diners--is also nicely animated and fun to observe in execution.
One of the most important advantages of Ada is its strong standard, which governs the entire language including modularization (package) and concurrency (task) constructs. This project demonstrates that sophisticated Ada programs, using a number of packages and tasks, can be written, without much difficulty, to be entirely portable.
The base version of Portable Diners has been compiled without error and executed successfully using nearly thirty different Ada compilers, from most major compiler vendors, running on computers ranging from the IBM PC and Apple Macintosh through several families of VMS and Unix workstations, to IBM and Cray mainframes.
An interesting aspect of the portability tests is the use of the Internet to carry them out. The Ada source modules for Portable Diners were posted to an Internet newsgroup (comp.lang.ada), then copied from the network by Ada users around the world and tested with the compilers they had available.
Many real-world programs depend to a certain extent on machine-dependent characteristics such as the capabilities of the display device. Only the machine-independent parts are therefore portable. Good system design dictates that machine-dependent information be separated and encapsulated.
To illustrate the importance of separating machine-dependent from machine-independent parts of a program, we have developed several versions of Portable Diners. These differ only in the style of animation, which is governed by the kind of graphics display.
Current animation styles include line-by-line output (completely portable), very simple window-oriented animation (requiring a 24 x 80 ANSI terminal), and IBM PC color (requiring a compiler-specific graphics library). Creating a new version requires modifying only a single package body embodying the display instructions.
The emergence of strong and enforced standards for production-oriented programming languages represents a maturation and professionalization of the software industry--an end to the "feature wars" and proprietary dialects that have characterized language development until recently (indeed, "feature wars" still rage in the Pascal industry).
The formal education of students in the computing disciplines should include some exposure to the benefits of language and system standards; it is an aspect of professionalism. A language standard, together with a validation process that assesses a compiler's conformance to that standard, makes it possible to develop programs that can be moved from today's hardware to tomorrow's without major coding changes. More immediately, a language standard encourages the existence of multiple compilers for a single computer system, each compiler having its strengths, e.g., in compilation vs. runtime efficiency, or user-friendliness vs. code optimization, but all compilers accepting the same language.
Ada is an especially good case in point, because its government sponsors mandated a standard [DoD 83, Nyberg 89] that governs the entire language, including features for modularization and configuration management (packages) and concurrent programming (tasks). The government also sponsors a validation process in which a compiler is tested, using a publicly available suite of several thousand programs, for conformance to the standard. Subsets and supersets are not allowed. It is not forbidden to market a non-conforming compiler--the government allowed its trademark to lapse in 1988--but only a conforming compiler can be advertised as "validated" and used for government work. To our knowledge, no non-conforming compilers are currently on the market.
The strong Ada standard and the validation process have spawned an industry of more than thirty compiler vendors, with perhaps a dozen major players. More than 300 compiler/computer pairs--a pair is a given vendor's product running on a given machine--are currently validated. A Sun-3 or VAX/VMS installation can choose from around ten distinct compilers each; five companies market MS-DOS-family compilers. An academic computer laboratory can therefore, without too much difficulty or financial hardship, create an environment with several compilers, in which students can be taught the benefits of portability. (A very useful counterexample is the difficulty experienced in moving a non-trivial Pascal program from, say, Borland's compiler to Microsoft's, or from MS-DOS to UNIX.)
A related issue is that of machine-dependence vs. machine-independence. Not every program can be written to be entirely machine-independent. A program may require access to specific "hard" memory locations, e.g., to communicate with specialized devices, or need to run on a display terminal with certain characteristics. In this case, good design principles dictate that machine dependencies be localized and encapsulated to the extent possible, with a clean interface to the machine-independent part of the program. In this way most of the program source code is machine-independent, and the machine-dependent code is easier to change because it is easier to find.
Students should be exposed to the issue of localizing machine dependencies, as part of their general study of abstraction mechanisms and good design.
We illustrate both portability and encapsulation of machine dependencies using an elaborate rendition of the Dining Philosophers. This famous metaphor for resource allocation and deadlocking problems was first stated in 1971 by Edsger Dijkstra [Dijkstra 71]. Five philosophers sit around a table; they spend their lives alternately thinking and eating. In the center of the round table is an infinite supply of Chinese food; before each philosopher is a plate; between each pair of plates is a single chopstick. To eat, a philosopher must obtain the chopsticks to his or her right and left. (Note: Dijkstra's original formulation involved spaghetti and forks; since most philosophers can eat spaghetti with a single fork, many writers now use the Chinese food metaphor instead.)
Figure 1 shows the situation in the dining room, with well-known modern philosophers at the table (apologies for the poor resemblance of the caricatures to their namesakes). Dijkstra's right chopstick is #1; the chopsticks are numbered clockwise around the table.
The diners must cooperate to remain alive. Each right stick is someone else's left one, so if each philosopher first acquires his or her right chopstick, holding it greedily until (s)he can acquire the other chopstick, all philosophers will starve. This is a classical circular-wait deadlock.
It is easy to see why discussion of this scene is an obligatory part of classes on operating systems and concurrent programming. Many non-deadlocking solutions exist; the one we use here, is for one of the philosophers to be a non-conformist, grabbing his or her left chopstick first. In such a case, the circularity is broken. At least one philosopher can always eat, finish the meal, and yield up the sticks, thus no deadlock occurs.
The classical Ada implementation of the diners is presented in the literature on Ada concurrent programming [Ben-Ari 90, Feldman 90, Gehani 91]. These examples illustrate Ada's task type construct for creating concurrent processes: Philosophers and chopsticks are represented as objects of their respective task types. Our implementation builds on the standard literature example, but in addition focuses attention on system design. The diners and chopsticks are really separate classes of objects, communicating via messages, which Ada calls rendezvous; each class should therefore be exported from its own package.
Many programs demonstrating the diners have allowed the philosopher processes to communicate with the world outside the room (via display statements). This is an incorrect implementation of the situation: The diners should concentrate only on eating and thinking. To allow an outside observer to follow the action, however, we compromise and permit philosophers to communicate their state via messages to a head waiter task. The head waiter serves as the interface between the dining room and the outside world; its job is not only to assign chopsticks but also to serve as a play-by-play announcer, interpreting the goings-on to the audience.
Figure 2 gives the system structure for Portable Diners. Each rectangular box represents a library package; the arrows show the import structure, e.g., Main imports Room, which in turn imports Philosophers, Chopsticks, and Text_IO (Ada's standard input/outpt library). Note that Philosophers and Room are mutually importing. This is allowable but a bit subtle to implement. A philosopher is assigned chopsticks by the head waiter.
A philosopher's life is ruled by the algorithm in Figure 3, which is adapted from the task body for the philosopher type. Each philosopher determines the length of the next meal or thinking session by drawing a random integer from 1 to 10; pseudo-random numbers are delivered by a function in the random numbers package. The pseudo-random sequence is seeded from the system time-of-day clock, so that action is unpredictable from run to run. A meal or thinking interval is simulated by a delay of the given number of seconds. Room imports Ada's Calendar package in order to time-stamp each output message with the number of seconds elpased since the beginning of the run.
The main program's only function is to bring the head waiter to life, then wait until the program is terminated. The head waiter creates the dining room and brings the philosophers to life, one by one, deciding whether each philosopher will grab the left or right stick first.
Figure 4 shows a few lines of the scrolling output produced by the head waiter. Stroustrup is the non-conformist, having been instructed by the head waiter to choose his left chopstick (#1) before his right one (#5).
This implementation of Dining Philosophers is believed to be entirely portable and will produce similar output regardless of the compiler, computer, or display used; our portability tests are discussed below.
Room.Head_Waiter.
Report_State(Who_Am_I, Breathing);
LOOP
Room.Sticks(First_Grab).Pick_Up;
Room.Head_Waiter.Report_State
(Who_Am_I, Got_One_Stick, First_Grab);
Room.Sticks(Second_Grab).Pick_Up;
Room.Head_Waiter.Report_State
(Who_Am_I, Got_Other_Stick, Second_Grab);
Meal_Time := Random.Random_Int(10);
Room.Head_Waiter.Report_State
(Who_Am_I, Eating, Meal_Time);
DELAY Duration(Meal_Time);
Room.Head_Waiter.Report_State
(Who_Am_I, Done_Eating);
Room.Sticks(First_Grab).Put_Down;
Room.Sticks(Second_Grab).Put_Down;
Think_Time := Random.Random_Int(10);
Room.Head_Waiter.Report_State
(Who_Am_I, Thinking, Think_Time);
DELAY Duration(Think_Time);
END LOOP;
T= 21 Eddy Dijkstra Thinking 7 seconds. T= 21 Moti Ben-Ari First chopstick 2 T= 21 Bjarne Stroustrup Second chopstick 5 T= 21 Bjarne Stroustrup Eating 6 seconds. T= 23 Barb Liskov Yum-yum (burp) T= 23 Moti Ben-Ari Second chopstick 3 T= 23 Barb Liskov Thinking 6 seconds. T= 23 Jean Ichbiah First chopstick 4 T= 23 Moti Ben-Ari Eating 4 seconds. T= 27 Bjarne Stroustrup Yum-yum (burp) T= 27 Bjarne Stroustrup Thinking 1 seconds. T= 27 Jean Ichbiah Second chopstick 5 T= 27 Jean Ichbiah Eating 5 seconds. T= 27 Moti Ben-Ari Yum-yum (burp) T= 27 Moti Ben-Ari Thinking 10 seconds. T= 28 Eddy Dijkstra First chopstick 1 T= 28 Eddy Dijkstra Second chopstick 2 T= 28 Eddy Dijkstra Eating 9 seconds. T= 29 Barb Liskov First chopstick 3 T= 32 Jean Ichbiah Yum-yum (burp) T= 32 Barb Liskov Second chopstick 4 T= 32 Jean Ichbiah Thinking 1 seconds.
To illustrate the importance of separating machine-independent from machine-dependent parts of a program, we have developed several versions of the package body for Room. The window version uses two reusable Ada packages. One package is called Screen and controls an ANSI-compatible terminal display (such as a VT100 or an IBM-PC under ANSI.SYS control); the other, larger package is called Windows, which manages output-only, non-overlapping windows on an ANSI display.
Figure 5 shows the relevant part of the new system structure.These packages are written in pure, portable Ada, but programs using them display output correctly only on an appropriate terminal. Only the body of the Room package requires modification to produce this version; the rest of the system is entirely unchanged and does not even need to be recompiled. Given Ada's standard library management facility, and assuming that Screen and Windows are already compiled into the library system, the new version is produced simply by compiling the new body of Room and relinking the system.
Figure 6 shows a snapshot of the screen output during a run of this version. The action is more heavily animated; each philosopher's state is displayed in a separate window, and the screen resembles the table in Figure 1.
We have developed a version of Room using the proprietary color graphics library supplied with a specific compiler for the IBM-PC; we are working on yet another version using the Ada binding to X-Windows. These versions are considerably more machine-dependent than the first two, yet the machine dependency is encapsulated in a single package body (Room) and creating the new versions requires only re-writing and re-compiling this package and re-linking the system. Exposing students to these different versions teaches an important lesson in system design: The philosophers concentrate on nourishing mind and body, remaining oblivious to the world outside their dining room.
An important goal of this project was to demonstrate that the resulting program is portable, that is, it will compile and execute correctly regardless of compiler or execution hardware. We had twelve Ada compilers, from six different vendors, readily available for six different systems. The line-by-line version eventually compiled and produced the desired output using all twelve systems. The window version compiled correctly on all systems and executed correctly on all but the Macintosh and IBM 4381; there is no ANSI-compatible display option on the latter two systems.
During the testing, only one significant change was necessary to get the program to execute correctly on all systems, namely the use of a compiler directive (pragma, in Ada terminology) to force a compiler-independent elaboration order on the two mutually-importing packages. The only unsuccessful test was carried out on a particular IBM-PC family compiler, which generated executable code that "hung" the computer. The test exposed a bug in the compiler's memory allocation scheme.
To broaden the scope of the portability tests, we posted a file containing the Portable Diners source code to the Ada newsgroup on the Internet, requesting that readers test the program on their favorite compilers and report back by electronic mail. Some thirty responses were received from academic and industrial sites in North America and Europe; adjusting for multiple respondents using the same compiler, fifteen more compiler/computer pairs could be added to the list of successful tests of either the window or line version.
The list of successful tests, by compiler vendor, is given below. The twelve companies in question represent most of the major Ada suppliers, especially suppliers of compilers to the academic world.
The correct behavior of Portable Diners under Macintosh, MS-DOS, VM, and VMS operating systems, not to mention many versions of UNIX, is possible only because the concurrent programming constructs were included in the programming language, instead of in a system-dependent library package.
Portable Diners is also a fairly small program. The line-oriented version, consisting of Main and the packages Room, Chopsticks, and Philosophers, is about 100 statements long, not including 40 statements of general-purpose packages for input/output instantiation and random-number generation, because these packages can be assumed to have been pre-compiled into the library.
The window-oriented version is only about 20 statements (40 lines) longer; the difference is in the more elaborate head waiter task. We do not count the packages Screen (25 statements) and Windows (150 statements), again because these are general-purpose packages assumed to be in the library already.
The entire system, including the reusable packages, is available from the author by Internet mail or on diskette. The system is included in the government-sponsored Ada Software Repository, and has already received wide Internet distribution. Several compiler vendors are considering it for inclusion in their demonstration libraries.
That such an interesting program can be written so portably and compactly is a commentary on the power of using reusable, pre-compiled components, and also on the benefit of including concurrent-programming constructs in the programming language. Exposure of students to programs like this is a valuable part of their educational experience.
Since this paper appeared in 1992, Ada 95 has come on the scene. An Ada 95 version of Portable Diners is being distributed as part of the demonstration library with the GNU Ada 95 compiler available by anonymous ftp. A description of the program is also published in Chapter 15 of [Feldman 96].
Much information on Ada and Ada 95 is available on the World Wide Web, starting from Ada Resources for Educators and Students