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