(no subject)

Brian TAM (btam@cs.ucsd.edu)
Tue, 25 Apr 2000 01:26:32 -0700 (PDT)

"On the Duality of Operating System Structures"

The authors propose that many operating systems can
be placed into two broad categories, differing in the
implementation and use of processes and synchronization.
The message-oriented system is characterized by a
relatively small, static number of processes with a
message passing system for communicating among them.
The procedure-oriented model has a large, dynamically
changing number of small processes whose execution can
be synchronized using shared data. In spite of these
differences, the paper argues that the two paradigms are
actually duals of each other, meaning a program or
subsystem constructed on primitives from one can be
mapped directly into a counterpart in the other.

The duality is shown by defining canonical models
containing primitives, features, and operations specific
to either of the two OS categories. A program for a
resource manager written with facilities from one, then
the other model, is provided for illustrating the
direct mapping that can be used to transform code
between the systems. The authors also argue that the
performance of programs built in terms of one will be
the same as their dual. Since there is no substantial
inherent difference between the two styles of design or
programs, the reason for favoring one over the other in
constructing real OS's lies ultimately in the nature of
the system base. The machine architecture and/or
programming environment thus dictates which paradigm is
more appropriate.

The ideas are presented in a straightforward way,
with the authors giving appropriate caveats to the
assertions they were making, especially the ones they
themselves term "controversial". While the thesis is
interesting, there is an obvious lack of sound evidence
to back up the claim, as the authors themselves admit.
The sample program they use to demonstrate duality is
itself contrived, since the authors demand that a strict
programming style be followed for the mappings to work.
Their thesis would be more convincing if they could show
more rigorously how performance is equivalent between
the two paradigms, and how programs that do not
necessarily follow their stringent requirements are
nevertheless still logically equivalent. The real-world
example they could cite to demonstrate mapping of a
message system to a procedure implementation is one of
the few things that save this paper from becoming
another exercise in hand-waving. It would be
interesting to see what "formalisms" the authors have
put off until later, to prove the validity of duality.
The authors seem to have written this paper as a prelude
to such a thorough treatment of the subject.

"The Structuring of Systems Using Upcalls"

A common way of structuring operating systems is to
arrange the various functions in hierarchical layers,
each of which is an abstracted view of the functions in
a lower layer. However, the fundamental structuring
component on most systems is the process. Experience
has shown that mapping of a layer onto a process is
rather clumsy and leads to inefficient implementation.
One major reason is that most systems permit flow of
control through procedure calls to go in only one
direction for protection reasons, from the top down (from
the client). The authors propose using an implementation
called the upcall so as to make flow of control more
flexible. They have done this in the Swift operating
system.

In this alternative implementation, the layer is a
a collection of different subroutines that access shared
memory and a process (or task) is a thread of activity
comprising various subroutines across different layers.
Flow of control takes place within a task between layers
through subroutine calls travelling up or down. The
advantages of this methodology over asynchronous
interprocess signalling are less overhead and less code
write for buffering between layers (because there is none
with upcalling). Swift provides the opportunity to
optimize performance through "advice-like" facilities
similar to those in Pilot. Providing multi-task modules
gives greater flexibility over direct layer-task mapping
in modifying an implementation. The authors have
suggested solutions to the problem of upper layer failure
with a lower layer upcall, and the problem of indirect
recursive subroutine calls between layers.

While this paper does a good job of proposing a new
implementation, complete with relevant examples and the
description of an actual system built, one thing it fails
to address is the issue of security. The ability of
upcalls to cross protection boundaries is actually
mentioned by the authors as a concern of those who feel
the "depends on" relationship of layering is important,
so it seems rather odd that this subject is not more
adequately expounded. Also, the solutions to the
problems cited by the paper seem unsatisfactory. They
rely heavily on programmers exercising good judgment in
avoiding complications that arise from the system itself,
rather than from thorny programming difficulties. The
question of how to distinguish a looping task from a task
running an unexpectedly long computation is yet another
item in the "to-do" list that it is hoped will be more
thoroughly covered in a future paper.