paper evaluations: 04/25

Alejandro Hevia (
Tue, 25 Apr 2000 03:27:06 -0700 (PDT)

Evaluation of paper
"The Structure of Systems using Upcalls"
by D.D. Clark

The paper describes a methodology for program structure; it is oriented to
programs already modularized using the principle of layering. The key idea of the
paper is the concept of "upcall", that is, a robust and efficient implementation of
call sequences from procedures in a low-level layer to procedures in a higher-level
layer (these calls are necessary to break some of the inefficiency and restrictions
of the "standard" - top down - application design). In order to make
this approach robust and efficient, concepts like multi-task modules (a set of
procedures implementing a layer) and client tasks (processes executing the
required layers on behalf of clients/events) are introduced. In particular,
the authors propose this a functional decomposition in "horizontal" layers
(set of procedures, or modules) executed by "vertical" tasks which operate by
calling procedures (from any of the layers) in a top down or bottom up (even in
a sideway) fashion. These tasks operate on behalf of clients requests or even
external events.

The proposed methodology intends to facilitate the design of applications
(particularly those dealing with OS services, communication and networks)
that, although implemented on layers, require upwards calls, which although are
useful and flexible implementation features, may be error prone.
The authors describe several methods to implement "upcalls" using the models
of multi-task module and user task, paying special attention to avoiding
those potential pitfalls or unwanted side-effects. The proposed scheme also
intends to help in the design of robust (client-side fault tolerant) systems.

One interesting aspect of the paper is its fresh approach to system implementation,
that is, an approach not based on processes as the unit of implementation or
basic abstraction. Likewise, the explanations about a correct design process
for applications in the "multi-task module" scheme are an excellent idea in order
to promote and facilitate further development in the system.

Nevertheless, the proposed scheme (including its practical realization, the
Swift OS), seems to rely too heavily on a very precise programmer's criteria
and experience. Because of that, it remains to be seen the actual degree of
success of the suggested approach in a fully-implemented application.

The paper also raises the question about how to implement a complete recovery
of the system after an arbitrary failure of one of the clients. Unfortunately,
it is not clear how the tradeoff of efficiency and protection can be balanced to
achieve this goal - complete system recovery - in a scheme that relies on
resources (potentially) highly shared by independent tasks.


Evaluation of paper
"On the Duality of Operating System Structures"
by H.C. Lauer, R.M. Needham

This paper defines and discusses two categories of operating systems,
"message-oriented" systems and "procedure-oriented" systems.
In the message-oriented model, there is a small, static number
of processes, each one associated with a set of "channels" to
communicate with each other by exchanging messages. Hence, message
passing is the main synchronization primitive. In the procedure-oriented
module, on the other hand, the system may be seen as a large, rapidly
changing number of small processes, which implement synchronization
by using shared data (by using shared memory and some sort of lock or
monitor). The paper discusses some of the key aspects of each model and
argues that system designed using one approach, have an "equivalent"
system designed using the other approach. This is the analyzed "duality" of
the OS structures.

Much of the motivation of this paper is based on trying to answer the
question about which model is "better". The authors claim that no-one is
better than the other, since there is this "mapping" from "message-oriented"
to "procedure-oriented" designs.

The "empirical" approach proposed in this paper is evaluated by just
enumerating how many different instantiations of operating systems
fall into one of the two categories. Furthermore, the authors justify
the suggested duality using rather imprecise and informal arguments
about how to duplicate all characteristics of one model (eg. scheduling
policies, interfaces, and - most importantly - efficiency), into its dual.

This paper is very enlightening in the sense that the proposed mapping
helps to further understand the extent and powerfulness of the abstractions
behind the tools/primitives present in each model. Moreover, it stresses
that the underlying machine architecture - and no the intended application
characteristics - is the fundamental criteria to decide whether the message-based
or the procedure-based approach must be taken in the final system design.