MFELDMAN@GWUVM.BITNET (Michael Feldman) (01/19/90)
A PROJECT IN CONCURRENT PROGRAMMING This project was developed for a course in comparative concurrent languages, but is easily adapted to Ada or occam or whatever other language. I have used it successfully for about seven years with a number of classes at different levels. It introduces a lot of the issues of concurrent programming, it's easy to implement, it's not too terribly contrived, and it's fun! The students are required to do a comparative exercise, to familiarize themselves with the languages under study, and to have some close-up experience with their concurrency and encapsulation mechanisms. Two important aspects of the comparative exercise are code modification and algorithm animation. Code Modification. Unless they have had jobs in industry, students often get little experience in re-using other peoples' code, perhaps adapting it to new uses; they need this experience. First, in practice much program "maintenance" (read enhancement) is done in industry; second, programs are too often - in school and industry as well - written from scratch for each new application, with little attention paid to development of rich libraries and re-usability of programs. In this project series, students write relatively little code ex nihilo. They are given listings and machine-readable files of pre-existing modules and directed to use them, perhaps after some enhancement work. Several sort programs, a terminal driver, a window manager, and a task dispatcher are all adapted, or translated from language to language, during the course of the project. Code adaptation fosters a positive attitude toward re-use; one builds on the work of others instead of competing with it or re-inventing it. Algorithm Animation. Projects like that at Brown University have developed schemes for dynamic algorithm visualization on high-resolution workstations. Animation is fun (!) and helps to hold students' interest, and - within limits - it can be done "cheaply" with 24x80 "dumb terminals." The advantage of the cheap approach is that it can be done portably. A very good way to understand the interaction of concurrent programs is to have them dynamically display - animate - their state. We have encouraged this idea through the vehicle of animated sort algorithms. Sorts are easy to work with: students understand them well and can therefore pay attention to the animation and the concurrency rather than to the algorithm being animated. Racing Sorts. Four files are provided: three are procedures, each implementing one well-known sorting algorithm for arrays of up to 64 characters, for example BubbleSort, LinearInsertionSort, HeapSort. The fourth file contains a module for a miniature terminal driver, exporting ClearScreen and SetCursorAt operations. A demonstration file is distributed, in which a single sort procedure displays its array of characters on a single row of the display, then posts the changes to the array as the sort proceeds. The requirements of the project are-for each of the four languages-to turn each of the three sort procedures into a process, then start the three processes in a simulation of a "race" to completion. The screen is a shared resource (at least conceptually), to which all sorts must write; further, ANSI terminal control requires several characters of overhead to position the cursor. In order to guarantee that a "transaction" to the screen is completed successfully, then, the synchronization and communication primitives of each language must be used to build a monitor or other mutual- exclusion mechanism. Execution of the program gives the visual effect of animation as values are interchanged. Indeed, depending on the implementation, the animation may be too rapid for the eye to perceive, so the student must slow the action down with a delay of some kind. For the student wishing to experiment a bit with methods of displaying text in different windows, the source code for a simple window manager is distributed. This window manager does not have any mutual-exclusion code; the student must build it in. I gave a paper on this course and this project in the Ada Software Engineering Education and Training Symposium, held last June in Houston. The presentation that follows is adapted from that paper; I'll be glad to send a copy of the paper to anyone who sends me their e-mail address (please respond personally to me, not to the net). If you'd like the code that goes along with the project, let me know and I can e-mail it to you. We have also developed IBM-PC and Macintosh versions of a subset compiler for Ada that emphasizes concurrent programming and the tasking model, using windowing to trace the execution of multiple tasks. The compiler generates P-code which is interpreted; since we built the intrerpreter we can do "fun" things like stopping the clock to do runtime monitoring.We have no intention of extending this to full Ada; the goal is specifically to play with the tasking model. I will give a paper on this in the upcoming SIGCSE Symposium in Washington Feb. 22-23. You're welcome to a copy of the paper if you e- mail me; should you be interested in the software itself, let me know and we'll talk. Prof. Michael B. Feldman Department of Electrical Engineering and Computer Science The George Washington University Washington, DC 20052 mfeldman@seas.gwu.edu +1-202-994-5253