CSE 221 Paper Evaluations

Greg Johnson (johnson@SDSC.EDU)
Tue, 25 Apr 2000 00:00:01 -0700 (PDT)

H. Lauer and R. Needham, 1978.

This paper takes a look at the two generalized categories of operating
system designs. One of these is the message-passing class, characterized
by a smaller number of larger processes, which communicate via exchanging
messages. Processes tend to be static entities (lifetime is fixed to the
duration of the user program) and synchronization between processes relies
on waiting for one to send a message to the queue of another. The second
class is represented by OS designs which are procedure-oriented in nature.
Here, processes exchange information by manipulating data structures stored
in shared memory, and synchronization takes the form of locking or access
mechanism. Processes in this model are dynamically created and destroyed
as dictated by calls to procedures.

The authors show (by informal reasoning) that a program written for one
model can be transformed (in a straightforward and logically equivalent
way) into a program for the other model. They go about this by showing
a facility-to-facility mapping between the two models (almost reducing
the transformation process to relabeling keywords). Continuing, Lauer
and Needham reason that the relative performance of the two programs
should be similar given underlying hardware of similar capability.

Since any program implemented in one system can be implemented in the
other as effectively (conceptually), the authors state the selection
of a model is driven not by its inherent capabilities, but by external
considerations such as hardware characteristics.

The authors acknowledge that in order to translate a program from one
class to another, it must adhere strictly to the style they dictate.
In cases where this is not true, they suggest the program (or facility
it requires) might be a victim of sickly design. I tried to conjure a
counter-example from the world of parallel computing in which message
passing and shared memory programming models closely match the duality
the authors describe. Unfortunately, the design-choice examples I came
up with were driven by hardware considerations and not fundamental flaws
in either model. Even so, I don't believe the two OS models to be fully
equivalent. If for no other reason, hardware resources are finite and
must (eventually) impact the design.


D. Clark, 1985.

This paper describes a design schema which provides efficient support of
very interactive programs such as those which handle network traffic.
This methodology is based upon a layering concept in which "clients" run
in higher layers and invoke services in lower layers, and in which lower
layers may invoke routines in higher layers. The latter is necessary to
support network communication for example. In this case, a lower layer
must have the ability to efficiently invoke a function at a higher layer
(an arriving message might invoke a client handler routine for example).
"Upcalls" denotes the capability of a lower layer to invoke something in
a higher layer, and is a major aspect of the design methodology described.

Another aspect is the structuring of layers. Clark's are composed of sets
of tasks (multi-task modules), themselves composed of multiple subroutines.
Communication between tasks occurs with the help of state variables stored
in single address space shared memory, not interprocess signals like those
used in Dijkstra's THE system (also a layered design).

Clark goes on to describe several advantages (efficiency and simplicity
being two) and solutions to problems inherent in a layered design which
allows upcalls (such as the potential for cyclic calling paths - Clark
applies several solutions to solve specific manifestations).

In several places, Clark mentions that his design depends on the ability
of the programmer to write high quality, well-structured code to minimize
potential sources of failure. One advantage of Dijkstra's layered design
is that it assisted the programmer in debugging, by allowing lower levels
to be tested in advance of implementing upper layers. The use of upcalls
in Swift would seem to complicate a layer-by-layer test program. Further,
heavy reliance on the correctness of the programmer limits the scalability
of this design methodology.

Clark likely would have been a critic of Lauer and Needham's "duality"
paper. In his conclusion, Clark states that he does not see how a layered
system such as his could be efficiently implemented in an explicit message
passing system. Doing so would require placing one task at every layer to
handle ownership of and access to (via messages) state variables.

Greg Johnson office: (858) 534-8367
Senior Programmer Analyst fax: (858) 534-5152
San Diego Supercomputer Center email: johnson@sdsc.edu
University of California San Diego