Evaluations: 04/25

Bianca ZADROZNY (zadrozny@cs.ucsd.edu)
Mon, 24 Apr 2000 22:16:56 -0700 (PDT)

On the Duality of Operating System Structures

This paper shows that two general categories of operating systems, namely
message-oriented systems and procedure-oriented systems, are duals of each
other. This is important because it implies that choosing between one
category over another should only be based on the architecture upon which
the operating system is built. The applications that run on the system
could be constructed using either one of the paradigms, with no difference
in performance.

The paper demonstrates this duality empirically by constructing canonical
models of each type of system. These models include the facilities which
each system provides, along with their basic primitives, and an outline of
a simple resource manager for each one of them. Then, it shows a
correspondence between the system facilities and the resource manager
models for each type of system. By giving examples, it argues that
applications written using one of the models could be rewritten using the
other model simply by applying the correspondences, and that their logic
would not affected by the transformation. Furthermore, it gives an example
which suggests that mechanisms that exist in one category but have no
counterpart in the other category are unnecessary and hard to understand.

Based on the observation that the logic of the programs is not affected
when they are transformed from one model to the other, the paper shows
that the execution times of the programs themselves are left unchanged.
Moreover, is asserts without proof that the facilities of one model can be
implemented as efficiently as the corresponding facilities of the other
model. Finally, it argues that the scheduling and dispatching of processes
can be made identical in each type of system. Thus, the time complexity of a
computation is the same for both models.

I found this paper very interesting because it attempted to empirically
demonstrate that two important categories of operating systems, which were
thought to be intrinsically different, are actually duals of each other. I
also like the idea of creating simple models of each category abstracting
away the less important features present on them. However, I think the
paper did not give enough experimental support for its claims. One idea
would be to experimentally compare the performance of dual programs using
real operating systems that fit in each one of the two categories.


The Structuring of Systems using Upcalls

This paper describes a methodology for constructing layered systems in
which service invocation is not restricted to be downward as in previously
designed systems, but it can also go upward. In this way, it is possible
to structure a layered system in which the upward flow of control is
implemented through procedure calls (or upcalls), instead of using
asynchronous signaling.

Another contribution of this paper was to point out that the usual mapping
between processes and layers is a source of inefficiency for the system.
Instead, it suggest that each layer should be implemented by a multi-task
module, i.e., by a set of subroutines in different tasks with shared
memory controlled by a monitor lock. Different layers can have subroutines
in the same task. The communication between layers (up and down) is done
strictly through subroutine calls between subroutines in the same task.
Interprocess communication is used only within each layer.

The paper argues that using asynchronous communication between layers is
inefficient for some applications. Thus, by applying the methodology
presented in the paper, it would be possible to increase the performance
of these applications. By allowing upcalls, it is possible for a lower
layer to "ask advice" to an upper layer in order to obtain information
about the type of service that it is providing. In this way, the lower
layer can optimize its performance according to the type of service.
Another advantage of this approach is that it is easier to program using
procedure calls than using signaling.

One disadvantage of allowing upcalls is that lower layers have to trust
upper layers when making upcalls. This is not desirable because a problem
that occurs in one of the clients of a layer can potentially affect the
other clients. The paper provides some guidelines for avoiding this
situation, such as separating and locking data that is not related to a
client before making a call to do that client. Another disadvantage of
upcalls is that there could be a cycle of procedure calls between two
layers, which can lead to unexpected bugs. The paper provides some
techniques for restricting the use of upcalls, such that this situation
cannot occur. Yet another problem of the approach presented is that it is
difficult for a programmer to organize a layer as a multi-task module.

In my opinion, the approach proposed by the paper is overly complicated.
The organization proposed is not a layered one, but one that resembles a
matrix. Communication can occur either between elements of the same
column, which are subroutines in different layers, or elements of the same
row, which are subroutines in different tasks. It makes me think if it
would not be easier to implement the system without any structure allowing
subroutine calls in any way that seems natural.