Transcript ppt
On the Duality of Operating System Structures Hugh C. Lauer, Roger M. Needham Dave Archer - CS533 - Spring 2006 1 Duality Defined • In Boolean algebra, if f(i1, i2, …) is true, dual f’ is also true, formed by swapping • with +, i with ¬i a b a = b • In this paper, OS models are dual if – functionally equivalent – can be transformed into one another by interchanging primitives for process structure and cooperation Dave Archer - CS533 - Spring 2006 2 Motive Motivation, Goals, Approach • “Religious argument” over design slows innovation • Characterize and classify operating systems designs Goals – As message-oriented or procedure-oriented • Most systems biased toward one of these – By process structure, synchronization, IPC – Using an “idealized” model for each Approach • Show duality, equivalence » short-circuit decision process • “Empirical” = “Engineering” approach – Observation and generalization – Informal reasoning, empirical support – Conclusion Dave Archer - CS533 - Spring 2006 3 Welsh’s “Event-Driven Server” Network Event Queue • Small number of threads • Event queues • Processing organized in “handlers” • Server maintains continuation state Dave Archer - CS533 - Spring 2006 Consumer Disk Scheduler Producer Request FSM Request FSM Request FSM Request FSM Request FSM 4 Lauer’s Message-Oriented OS Execution “Stream” Data “Stream” • Typically real-time, e.g. Cisco Catalyst • Small, static process count • Explicit messages for communication Channel –Passing (channels), queueing (ports), waiting for (MsgWait) data Send WaitReply Wait SendReply Consumer Producer Ports –Persistent bindings = complexity in creating processes • Cooperation by encapsulating data/ptrs in messages • Pre-emption driven by message arrival –When a higher priority process is waiting • Little or no sharing of address spaces –Data or pointers passed in messages Dave Archer - CS533 - Spring 2006 5 Welsh’s “Threaded Server” • Large, dynamic thread count • Shared data structures • Processing organized in threads • Thread maintains state Consumer Network Protected, Shared Data Dispatcher Producer Request 1 Request 2 Request 3 Network Request 4 Request 5 Dave Archer - CS533 - Spring 2006 6 Typically time-sharing – most familiar OSs today • Large, dynamic process count • Explicit shared data system for communication – Passing (vars), queueing (monitors), waiting for (cond. vars) data – Persistent state = complexity in creating shared data • • Cooperation by encapsulating data in monitors Wait Wait Signal Signal Pre-emption driven by release of lock Consumer • Producer Procedure-oriented OS – When a higher priority process is waiting • Little or no messaging – data or pointers passed in shared vars Dave Archer - CS533 - Spring 2006 7 Data “Stream” Execution Data “Stream” “Stream” Channel WaitReply Wait SendReply Producer Send Consumer Producer Ports Wait Wait Signal Signal Consumer Execution “Stream” - dual operations Dave Archer - CS533 - Spring 2006 8 Mapping Duality Message-oriented system Procedure-oriented system • Processes • Monitors • Message Channel IDs • ENTRY procedure names • Port numbers • Simple procedure names • SndMsg…WaitReply • Procedure call/return – Immediate – Simple – Delayed – Fork/Join • SendReply • Return from Monitor • WaitForMsg • Wait for lock, condition variable • Main loop CASE arguments • ENTRY procedures • Send message • Signal condition variable Dave Archer - CS533 - Spring 2006 9 Three Observations • Two OS classes are duals – One can be directly mapped to the other by replacing primitives • Logically identical to each other – almost down to syntax, if we work at it • Equivalent in performance? – e.g. queue lengths, wait times, service rates Dave Archer - CS533 - Spring 2006 10 What about Performance? • Three areas to worry about – Execution of programs • No difference – identical program semantics – Overhead of system calls • Send = Call • Wait = Leave • Process switching, VM access identical • Scheduling, dispatching, preemption equally efficient – Can use same disciplines – Queueing and waiting times for shared resources • Identical, since scheduling disciplines are equal • Hypothesis: Lifetime of similar computation is equal Dave Archer - CS533 - Spring 2006 11 One Conclusion • “In the message oriented model, objects move between processes in messages. In the procedure oriented model, processes move between objects by calling procedures.” (loosely quoted from Dearle et al, 1994) • Choosing which model to adopt relies on 2nd-order factors – 0th order = similar program structure, performance of client programs – 1st order = similar computational complexity – 2nd order = machine architecture features, programming environment – set a priori, so will drive decisions • Can drive decision closure on process structure and synchronization using these 2nd order factors Dave Archer - CS533 - Spring 2006 12 Believable? • Intuitive, but no formal classification or proof • Mixed acceptance among a (biased) peer community • Only one “transformable” example • 47 citations, mostly taking it on faith – One, Welsh[2002] disputes that performance is equivalent when scaled to Internet server demands – None dispute the claimed functional duality • Bottom line: close enough, except re performance Dave Archer - CS533 - Spring 2006 13 References • Hugh C. Lauer, Roger M. Needham. “On the Duality of Operating System Structures.” in Proceedings of the Second International Symposium on Operating Systems, IRIA, October 1978, reprinted in Operating Systems Review, 13, 2, pp. 3-19. April 1979. • A. Dearle, R. Di Bona, J. Farrow, F. Henskens, A. Lindstrom. J. Rosenberg, F. Vaughan. “Grasshopper: An Orthogonally Persistent Operating System.” Computing Systems 7, 3 (Summer), pp. 289-312. 1994. • Matthew D. Welsh, “An Architecture for Highly Concurrent, Well-conditioned Internet Services.” PhD Thesis at UC Berkeley, 2002. Dave Archer - CS533 - Spring 2006 14