Lauer & Needham -- On the duality of operating system structures

2 OS categories: message-oriented and process-oriented. Thesis: 2
models are duals of each other and choice should be made solely based
on the underlying machine's architecture. No real OS falls in either
category, so this is more on the theory of OS design.

Message-oriented model (data centric)
-------------------------------------
Small, static number of big processes, typically associated with
specific system resources, connected via an explicit set of fast
message channels, bound early. Almost no direct data sharing.

  Messages w/ identifiers
  Messages channels and ports
  Operations: SendMessage, AwaitReply, WaitForMessage, SendReply
  Process declaration + CreateProcess

good implementations:

- queue-based synchronization
- nobody touches shared data unless it is processing a msg referring to it
- device interrupts are messages (a la DPCs in NT and VMS).
- static priorities associated with processes, based on resources they manage
- typically synchronous processing of messages

Procedure-oriented model (control centric)
------------------------------------------

Large, dynamic number of small processes, with efficient procedure
call and context switch mechanisms. Communication through sharing and
locking (locks, semaphores, monitors, etc.); process
creation/destruction is lightweight.

  Procedures that can be called synch/asynch
  Modules & monitors + instantiation
  Condition variables (Wait, Signal)

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

Bidirectional transformation
----------------------------

Message-oriented      <===>        Procedure-oriented
~~~~~~~~~~~~~~~~                   ~~~~~~~~~~~~~~~~~~
processes ------------------------ monitors
message channels ----------------- global procedure identifiers
message ports -------------------- monitor entry procedures
SendMessage; AwaitReply ---------- procedure call
SendMessage; ...; AwaitReply ----- FORK; ...; JOIN
SendReply ------------------------ RETURN from procedure
WaitForMessage; case statement --- monitor lock; entry procedure selection
case statement branches ---------- entry procedure body
selective WaitForMessage --------- WAIT on condition var (SIGNAL ??)

Observations
------------

- models are duals of each other and the dual programs/subsystems are
  logically identical (all semantic content is preserved).

- Performance (queue lengths, wait times, service rates):
    1. Isolated program execution time stays the same, due to
       unmodified algorithms, amount of information, etc.
    2. Computational overhead of primitive system calls are
       theoretically equivalent.
    3. Queing and waiting times can be made equal by ordering
       queueing/dequeueing and other events in the same way.

- Perhaps don't use O(t) or O(messages) for calculating performance...

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."