On the Duality of Operating System Structures
--- Lauer et al., 1978

Based on summary by Emre Kiciman et al.

* Theme: Message passing and procedure oriented systems are
essentially equivalent to each other in power, performance, and
structure.  The decision of which to use in designing a system should
therefore be based on "second order" factors, especially the ease of
implementation of the synchronization primitives on a particular
architecture.


- message passing ~= micro kernels;

- procedural ~= monolithic kernels;


Message Passing Style: 
---------------------

Message passing has large, static processes
which communicate by passing messages.  The messages are stored in
queues and handled serially.  Pre-emption occurs when a higher
priority message arrives for a process which is listening for that
type of message.  Virtual memories are placed in correspondence with
processes.  Processes are associated with system resources.  Messages
are like "tokens" which delimit when a process can access and modify
certain data structures.  Channels = link to other processes, Ports =
queues for arriving messages.

- messages are easily and efficiently passed among processes;

- number of processes and channels is relatively static;

- address spaces are usually placed in one-to-one correspondence with 
  processes;

- synchronization and queuing for congested resources is implemented in 
  the message queues.  No process touches the data unless is processing a 
  message referring to it;

- devices are also message-based, with messages from them used in place 
  of interrutps;

Good implementations:

- queue-based synchronization
- nobody touches shared data unless it is processing a msg referring to it
- device interrupts are messages
- static priorities associated with processes, based on resources they manage
- typically synchronous processing of messages

Procedure Oriented Style: 
------------------------

Procedure oriented systems are basically
multi-threaded servers.  Shared global data structures are protected
by locks, monitors, or other synchronization method.  Queues remember
all processes waiting for locks.  System resources are encoded in data
structures, and processes wander around the whole system.

- procedure call facilities are very fast;

- cooperation among processes is achieved by the use of synchronization
  data structures (monitors, locks, semaphores, etc);

- preemption occurs when a release operation is performed on a lock 
  which a higher priority process is waiting for;

- global data can be both protected and efficiently accessed;

- asynchronous call: FORK + JOIN;


Good implementations:

- associate lock w/ data + use a waiters queue
- lock small portions of data for short periods of time
- peripherals control/interrupts done via shared memory (DMA ?)
- global naming scheme for efficient context switches


- the two models are duals of each other, i.e., a program written in one model
  can be converted to an identical program in the other model;

- considerations for choosing which model to adopt in a given system are not
  found in the applications which that system is meant to support.  Instead,
  they lie in the substrate upon which the system is built;

* Implementation: Canonical models of the two styles are presented and
then the correspondence between the parts of each style are equated.
Some interesting correspondences:

  Message            		Procedure
  ----------------   		---------
  Processes          		Monitors
  Message Channels   		External procedure identifiers
  Send/Recv immed    		Procedure call
  Send/Recv+delay    		Fork/join
  Main loop switch   		Monitor lock + "extern" identifier
  Selective waiting  		Condition vars, Wait & Signal

Selective waiting = waiting for a message on a particular channel.


* Examples: CAP system was converted from message passing to procedure
oriented.  Claim architecture prompted a serendipitous design that
lent itself to easy conversion.

* Problems: Authors claim difficulty of converting most real systems
caused by the "underlying addressing issues, use of global data, and
styles of communication" -- but weren't these the same issues they are
trying to tell us can be easily converted b/t the two styles?

* Quote: The arguments about processes and synchronization which are
often found in the corridors of organizations actively designing a new
system take on a decidedly non-technical tone.

* Take: A very insightful piece which deserves a re-reading.  In
retrospect, it makes sense -- to the hardware the two styles look the
same, as the probably must, because the effect is always to manage
system resources in an efficient way.  The utility of each model is in
the way it structures how we think about synchronization, sharing, and
managing resources.


Discussion topics:
------------------

1. page 17, 2nd para: OS designer cannot influence hardware --
   certainly a bad thing. Still true? (how about MMX, SPARC/Solaris)

2. Since performance is equivalent, why are message-passing systems
   slower than procedure-based? (modulo Liedtke's SOSP '97 paper).

3. Come up with contemporary examples of mostly message-oriented /
   process-oriented OSs.

4. Empirical paper from 1977, w/ only evidence based on existing OSs
   --> Is duality thesis still true? Are there any perceptable
   influences of this paper on OS sdesign?

5. page 13: is a non-dual style/mechanism good or bad?

6. Paper says no global naming schemes useful in message-oriented
   systems. What about naming processes? Other counterexamples?

7. page 11, 2nd para: "Thus no process can be associated with a single
   address space unless that space be the whole system."