Transcript ppt
On the Duality of Operating System Structures by Hugh C. Lauer, Xerox Corporation and Roger M. Needham, Cambridge University Presented by Scott Fletcher 1 Authors’ Claim • Most operating systems (or subsystems) can be classified into one of two models – Message-Oriented – Procedure-Oriented • These two models represent a duality – Identical in logic and performance • The argument should not be which model is “better”, but which model is “better suited” to the machine architecture upon which the system is being built 2 Message-Oriented Systems Small, static process count Explicit messages for communication – Passing (Message Channels) – Queuing (Message Ports) – Waiting for Data (MsgWait) • Execution “Stream” Channel Persistent Bindings Ports Primitive Message Transmission Operations: – – – – • Send Wait (WaitForMessage) SendReply AwaitReply Preemption driven by message arrival – When a higher priority process is waiting • Producer – complexity in creating processes • Data “Stream” Send AwaitReply Wait SendReply Consumer • • Little to no sharing of address spaces – Data or pointers passed in messages 3 Message-Oriented Systems Summary: – The number of processes and the connections between them are relatively static – Specific communications are established between particular pairs of processes – Messages are passed between processes – Processes rarely share data in memory 4 Procedure-Oriented System Characterized by: – A protection and addressing mechanism oriented toward procedures – Procedure call facilities which can rapidly take a process from one context to another – Cooperation among processes is achieved by some form of locks, semaphores, monitors, or other synchronizing data structures 5 Procedure-Oriented System • • Large, dynamic process count Shared data system for communication Persistent State – Complexity in creating shared data • Primitive Operations – – – – • Wait Signal Fork Join Preemption driven by release of lock Wait Wait Signal Signal Consumer • Producer – Passing (Variables) – Queuing (Monitors) – Waiting for Data (Condition Variables) – When a higher priority process is waiting • Little or no messaging – Data or pointers passed in shared variables 6 Procedure-Oriented System Summary: – Creating processes is easy as no communication channels have to be set up between them – Global/shared data is protected and accessed through locking mechanisms and synchronization – A process typically has only one goal or task, and it wanders throughout the system in order to get that thing done 7 Characteristics of the Models • The two styles of system design are a duality – Def: A duality translates concepts, theorems, or mathematical structures into other concepts, theorems or structures in a one-to-one fashion – A program for one kind of system can be mapped into a program appropriate for the other – As a result of this mapping, the logic of the programs in the dual systems is invariant – The performance of the system can be preserved across the mapping 8 The Duality Mapping Message-oriented system Procedure-oriented system Processes, CreateProcess Monitors, NEW/START External Message Channels Message Procedure identifiers ENTRY Ports Procedure identifiers simple SendMessage; AwaitReply (immediate) Procedure call SendMessage;... AwaitReply (delayed) FORK; . . .JOIN SendReply RETURN (from procedure) monitor main loop of standard resource manager, WaitForMessage statement, case statement Lock, ENTRY attribute Arms of the case statement selective ENTRY procedure declarations Waiting for messages Condition Variables, WAIT, SIGNAL 9 The Duality Mapping Data “Stream” Execution Data “Stream” “Stream” Channel WaitReply Wait SendReply Producer Send Consumer Producer Ports Wait Wait Signal - dual operations Signal Consumer Execution “Stream” 10 Similarity of Programs • The system, or subsystem, of one style can be transformed directly into the other by replacing each construct with its corresponding construct • The transformation does not affect the logic of the client programs: – no algorithms are changed – no data structures are replaced – no interface strategies are affected 11 Preservation of Performance The dynamic behavior of a system of programs has three components: – The execution times of the programs themselves – The computational overhead of the primitive system operations they call – The queuing and waiting times which reflect the congestion and sharing of resources, dependence upon external events, and scheduling decisions 12 Preservation of Performance Execution Time The duality transformation leaves the main bodies of the programs untouched: – The algorithms will compute at the same speed – The same amount of information will be stored in each data structure – The same amount of client code will be executed in each of the systems – The same number of additions, multiplications, comparisons, and string operations will be performed 13 Preservation of Performance Computational Overhead The facilities of each of the two canonical models can be made to execute as efficiently as the corresponding facilities of the other model: – Sending a message has the same computational complexity as that of calling or FORKING to an ENTRY procedure – Leaving a monitor has the same complexity as that of waiting for new messages – Process switching can be made equally fast in either system, and for similar machine architectures this means saving the same amount of state information – Virtual memory and paging or swapping can be used with equal effectiveness in either model 14 Preservation of Performance Queuing and Waiting Times The basic operations of the two models can also be made to behave identically with respect to the scheduling and dispatching of client processes (corresponding events will happen in the same order): – If the message has to be queued at the destination process, then the procedure call will also be queued at its monitor, WAIT statement, or JOIN statement (for the same length of time) – The peripheral devices will exhibit the same behavior with respect to latency, response time, and transfer times – The scheduling and dispatching can be arranged so that the same number of context switches and allocations of message blocks take place whether it is a message-oriented or a procedure-oriented system 15 Underlying Differences • There is no inherent difference between the two styles of system design or the programs that use them – 0th order = similar program structure and performance – 1st order = similar computational complexity – Preferring one style over another = 2nd order or higher 16 Final Arguments • Neither model is “better” than the other • Both strategies can be built to provide identical performance, logical soundness, elegance, and correctness • Deciding to use one strategy over the other will NOT introduce any fundamental incompatibilities • As both styles are duals in regards to the most important considerations for designing an OS, the design selected should be based, first and foremost, on the machine architecture upon which the system is being built 17 Thanks • Thanks to Dave Archer and his slides from Spring ‘06 for providing some nice graphics • Thanks for listening 18