Transcript On the Duality of Operating System Structures

On the Duality of
Operating System
Structures
Hugh C. Lauer
Xerox Corporation
Palo Alto, California
Roger M. Needham
Cambridge University
Cambridge, England
Proc. Second International Symposium on Operating Systems, IRIA, Oct. 1978



Overview
Nature of the Paper
Two Models







Message-Oriented Systems
Procedure-Oriented Systems
Characteristics of the Models
Empirical Support
Underlying Similarities
Underlying Differences
Conclusions
Outline
“Many operating system designs can be placed
into one of two very rough categories, depending
upon how they implement and use the notions of
process and synchronization.”
Overview



The paper is empirical in nature
The universe in the investigation is the class of
operating systems
The properties of interest are processes,
synchronization and inter-process
communication
Nature of the Paper

Message-Oriented
Systems
Two Models

Procedure-Oriented
Systems
Characterized by a relatively small, static number
of processes with an explicit message system for
communicating among them
Message-Oriented
Systems



Specific communication paths
Relatively static number of processes and
connections
Deletion of processes tends to be very difficult
Hallmarks

Messages


Message Identifiers


A message identifier is a handle by which a particular
message can be identified
Message Channels


A message is a data structure meant for sending
information from one process to another
A message channel is an abstract structure which
identifies the destination of the message
Message Ports

A message port is a queue capable of holding messages of
a certain type or class
Facilities




SendMessage [messageChannel, messageBody]
returns [messageId]
AwaitReply [messageId] returns
[messageBody]
WaitForMessage [set of messagePort] returns
[messageBody, messageId, messagePort]
SendReply [messageId, messageBody]
Message Transmission
Operations

IBM’s OS/360


A discontinued batch processing operating
system developed by the IBM Corporation for
their then-new System/360 mainframe computer,
announced in 1964
GEC 4080

16-bit minicomputer with its unique Nucleus
feature (Marconi-Eliot Division)
Examples
Characterized by a large, rapidly changing
number of small processes and a process
synchronization mechanism based on shared data
Procedure-Oriented
Systems


Global data can be both protected and
efficiently accessed
Process creation is very easy
Hallmarks

Procedures


Procedure call facilities – synchronous and asynchronous




A module is the primitive Mesa unit of compilation
A monitor is a special kind of Mesa module which has associated with it a
lock to prevent more than one process from executing inside of it at any one
time
Module Instantiation


The synchronous procedure call mechanism is just the ordinary Mesa
procedure call statement
The asynchronous procedure call mechanism is represented by the FORK and
JOIN statements
Modules and Monitors


A procedure is a piece of Mesa text containing algorithms, local data,
parameters and results.
Modules may be instantiated in Mesa by means of the NEW and START
statements
Condition Variables

Condition Variables provide more flexible synchronization among events
Facilities

HYDRA


An early capability-based, object-oriented,
microkernel implemented in the programming
language BLISS as part of the C.mmp project at
Carnegie-Mellon University
Plessey System 250

Capability-based multiprocessing operating
system kernel
Examples



The Duality Mapping
Similarity of Programs
Preservation of Performance
Characteristics of the Models
A program or subsystem constructed strictly
according to the primitives defined by one model can
be mapped directly into a dual program or subsystem
which fits the other model.
The Duality Mapping
The dual programs or subsystems are logically
identical to each other.
They can also be made textually very similar, differing
only in non-essential details.
Similarity of Programs
The performance of a program or subsystem from one
model, as reflected by its queue lengths, waiting times,
service rates, etc. is identical to that of its dual system
given identical scheduling strategies.
The primitive operations provided by the operating
system of one model can be made as efficient as their
duals of the other model.
Preservation of
Performance



It is not very easy to change the structure of
most operating systems in a way which would
reflect the duality
The underlying address structures, use of
global data, and styles of communication are
usually bound to the design and
implementation
The Cambridge CAP Computer
Empirical Support
Comparison of the Two
Models


The two styles lead to client systems with
similar program structure and performance
The computational complexity of the
implementation of the system facilities to
provide the two styles is similar
Underlying Similarities
between Styles


Machine Architecture
Programming Environment
Underlying Differences
between Styles
There lies merit in both styles with respect to
structure, performance, logical soundness, elegance
and “correctness”.
Neither model is inherently preferable.
The main consideration is the machine architecture
upon which the system is being built, not the
application which the system will ultimately support.
Conclusions
Presented By:
Amna Rafiq
Graduate Student
CS @ VT
Thank you!