HIPS Invited Talks

``A Discipline of Multiprogramming'' by Jayadev Misra (University of Texas at Austin, USA)

Two major goals in multiprogramming research are: (1) to design and understand the modules (e.g., processes or data objects) of a program in isolation, without considerations of interference by the other modules, and (2) to implement the modules on separate processors with a fine grain of interleaving so that no processor is ever locked out of accessing common data for long periods of time. Much effort has gone into limiting interference among the modules by employing a variety of synchronization mechanisms: locks or semaphores, critical regions, monitors and communication. We believe that it is essential to devise a model in which the distinction between computation and communication is removed; in particular, the methods for designing and reasoning about the interfaces should be no different from those employed for the computations at the nodes of the network.

We have constructed a sparse model that meets most of the criteria described above: a program is built out of boxes (a box is similar to a process/object/monitor) and a box is built out of procedures (which are similar to monitor-procedures). No specific communication or synchronization mechanism, except procedure call, is built into this model. The traditional schemes for communication using bounded or unbounded channels, semaphores, and accesses to shared memory can be encoded as boxes in our model. We propose two distinct kinds of procedures, to model sequential and concurrent aspects of programming. Our programming model allows for disciplined interactions between these two types of procedures.

A program can be designed and understood box by box, and each box by its procedures (a transaction, in a database sense, is a chain of procedure invocations). Thus, a programmer has to understand only a single thread of control, associated with invocation of one procedure. Yet, the programming model permits concurrent executions of the procedures and we have devised an efficient implementation strategy. One of the reasons for introducing two different kinds of procedures is to obtain an appropriate theory that permits a greater degree of concurrency to be exploited.