221 Readings for 4/25

Mark Andrew SMITH (masmith@cs.ucsd.edu)
Tue, 25 Apr 2000 00:11:21 -0700 (PDT)

On the Duality of OS Structures:

This paper was intended to end debate or at least shed some light on the
debate that was raging at the time about the benefits of messagee passing
versus precedure oriented schemes for IPC. Lauer and Needham argue that
the two systems are in fact duals of one another, that they are logically
eqivalent, and that their performance is identical. The choice of one
system over another in an operating system should be made based on the
underlying hardware of the system for which the OS is being built. Proofs
of duality, logical equivalence, and performance preservation are all
given. For example, to proove logical equivalence, they show that only
textual substitutions are used when converting code from one form to the
other. Arguments become very detailed including how process priority is
preserved. They argue that in message oriented systems, preemption occurs
when a process with a higher priority receives a message it has been
waiting for. In the procedure oriented system, preemption occurs when a
process with a higher priority that has been waiting on a lock has that
lock unlocked. In each scheme, the occurance of one can be translated into
a similar occurance of the other. Very interesting empirical paper.

The Structuring of Systems Using Upcalls

Many structured operating systems, beginning with Dijkstra's THE have
attempted to solve complexity issues by layering the system. This layering
system takes advantage of the "uses" relation between different parts of
the OS. In this system, all calls move down the layers into the core which
presumably uses only its own code. However, it has become clear that
occasionally, it is the bottom of the code which is doing the calling, and
calls up, or "upcalls", have to occur. This leads to problems in
verification and performance, since for protection, presumably the calls
up would be implemented asynchronously. This paper presents a system which
allows for safe synchronous procedure call oriented calls up through a
layered system in order to increase performance and simplicity.

-Mark