On the Duality of Operating System Structures

Lauer, Needham

Two types of “canonical” OS structures:

1) Message-oriented system
* relatively small, static number of processes with an explicit message system for communicating among them.
* relatively limited amount of direct sharing of data in memory

* identification of address space or context with processes

Characterized by facilities for passing messages (or events) between processes.
Processor is pre-empted when a message arrives at a “higher-priority” process.
Process creation and deletion is expensive.

Priorities are assigned to processes at design-time.
Messages are usually processed one at a time as they represent requests for a shared resource.

-> Processes tend to become associated with system resources (i.e. print daemons, what else?) Peripheral devices are treated as processes. Interrupts are processed as messages.

-> Synchronization is implemented in message queues
-> Shared data is passed around in messages and copied many times (passed by value)

Message channel is a destination for a message. (Very often a process?)
Message port is a queue that can receive messages.

Common operations: SendMessage, AwaitReply, WaitForMessage, SendReply

Main loop:
do forever:

[message, message id, port] <- WaitForMessage(set of port ids);
case port of
port1: alg1
port2: alg2
endcase;

2) Procedure-oriented system
* large, rapidly changing number of small processes, and a process synchronization mechanism based on shared data.
* rapid creation and deletion of processes
* communication by means of direct sharing of memory
* identification of the context of execution with the function being executed (rather than the process)

Efficient procedure call facilities; switch between processes very quickly.
Cooperation between processes is by locks, semaphores, monitors, etc.

Data is protected by procedures that use synchronization primitives.
Process creation requires no setup of communication channels with existing processes. (The equivalent of this takes place when a procedure call is made.)
Process usually has one goal, and accomplishes it by making many calls to other processes.
Data structures are locked for relatively short periods of time by a given process.

Peripheral devices may be represented by monitors.

-> System resources are encoded in global shared data structures and procedures are used to access these data structures in a synchronized fashion.

Common OS Structures: Procedures, procedure calls (synchronous), Fork/Join for asynchronous calls, Modules/Monitors, condition variables (wait/signal)

ResourceManager: Monitor
c: condition
data
entry proc1 () { alg1; }
entry proc2 () { alg2; }

Most systems are more like one kind or the other. Systems within a category are similar to each other. Few systems are exactly like the canonical models above.

Paper argues:

• these types of systems are duals of each other: programs constructed using one model can be mapped to the other model.
• Dual programs are logically identical
• Performance of dual programs can be made equivalent

Why choose one model or another? Do it based upon which model is best suited for a given machine architecture. Choice of model should be independent of application that needs to be built.

Duality Mapping:

Message-Oriented Procedure-Oriented

Processes, CreateProcess Monitor, New/Start
Message Channels External Procedure Identifiers

Message Ports ENTRY procedure identifiers

SendMessage; AwaitReply (sync) simple procedure call
SendMessage; AwaitReply (async) Fork; Join

SendReply return statement

Mainloop of process monitor

Case statements entry procedure declarations

Selective waiting for messages wait/signal

Most important correspondence: processes in message-oriented = monitor in procedure-oriented

Note that when transforming programs in one model to the other, the core logic/algorithms would not be affected at all. This is the basis for the claim about it being possible to have equal performance between the two models. (If this is true, then programs that would differ the most between the two models are likely to have a lot of synchronization, a lot of pass by reference of large data structures, or very little synchronization, or very small data structures that do not need to be shared often.)

They argue that scheduling can be made equivalent between the two, hence supporting the equivalent performance claim. I honestly am not quite sure I buy this whole equivalent performance business.