On the Duality of Operating System Structures

0
0
1725 days ago, 706 views
PowerPoint PPT Presentation
On the Duality of Working Framework Structures. Hugh C. Lauer, Roger M. Needham. Duality Characterized. In Boolean variable based math, if f(i 1 , i 2 ,

Presentation Transcript

Slide 1

On the Duality of Operating System Structures Hugh C. Lauer, Roger M. Needham Dave Archer - CS533 - Spring 2006

Slide 2

Duality Defined In Boolean polynomial math, if f(i 1 , i 2 , … ) is valid, double f' is additionally valid, framed by swapping • with + , i with ¬i In this paper, OS models are double if practically identical can be changed into each other by exchanging primitives for process structure and participation an a = b Dave Archer - CS533 - Spring 2006

Slide 3

Motivation, Goals, Approach Motive "Religious contention" over plan moderates advancement Characterize and arrange working frameworks outlines As message-situated or technique situated Most frameworks one-sided toward one of these By procedure structure, synchronization, IPC Using an "admired" model for each Show duality, equality » cut off process "Exact" = "Building" approach Observation and speculation Informal thinking, experimental bolster Conclusion Goals Approach Dave Archer - CS533 - Spring 2006

Slide 4

Welsh's "Occasion Driven Server" Request FSM Consumer Request FSM Producer Event Queue Disk Request FSM Scheduler Network Request FSM Small number of strings Event lines Processing composed in "handlers" Server keeps up continuation state Request FSM Dave Archer - CS533 - Spring 2006

Slide 5

Lauer's Message-Oriented OS Execution "Stream" Data "Stream" Typically ongoing, e.g. Cisco Catalyst Small, static process number Explicit messages for correspondence Passing (channels), queueing (ports), sitting tight for (MsgWait) information Persistent ties = intricacy in making forms Cooperation by embodying information/ptrs in messages Pre-emption driven by message landing When a higher need process is holding up Little or no sharing of address spaces Data or pointers go in messages Channel Ports Wait Send Producer Consumer SendReply WaitReply Dave Archer - CS533 - Spring 2006

Slide 6

Welsh's "Strung Server" Request 1 Consumer Request 2 Producer Protected, Shared Data Network Request 3 Dispatcher Network Request 4 Request 5 Large, dynamic string tally Shared information structures Processing sorted out in strings Thread keeps up state Dave Archer - CS533 - Spring 2006

Slide 7

Procedure-arranged OS Typically time-sharing – most natural OSs today Large, dynamic process check Explicit shared information framework for correspondence Passing (vars), queueing (screens), sitting tight for (cond. vars) information Persistent state = multifaceted nature in making shared information Cooperation by exemplifying information in screens Pre-emption driven by arrival of bolt When a higher need process is holding up Little or no informing information or pointers gone in shared vars Wait Producer Consumer Signal Dave Archer - CS533 - Spring 2006

Slide 8

Execution "Stream" Data "Stream" Data "Stream" Execution "Stream" Channel   Ports  Wait Send  Producer Consumer  Producer Consumer  SendReply WaitReply   Signal   - double operations Dave Archer - CS533 - Spring 2006

Slide 9

Message-arranged framework Processes Message Channel IDs Port numbers SndMsg… WaitReply Immediate Delayed SendReply WaitForMsg Main circle CASE contentions Send message Procedure-situated framework Monitors ENTRY technique names Simple methodology names Procedure call/return Simple Fork/Join Return from Monitor Wait for bolt, condition variable ENTRY systems Signal condition variable Mapping Duality Dave Archer - CS533 - Spring 2006

Slide 10

Three Observations Two OS classes are duals One can be specifically mapped to the next by supplanting primitives Logically indistinguishable to each other practically down to grammar, on the off chance that we work at it Equivalent in execution? e.g. line lengths, hold up times, benefit rates Dave Archer - CS533 - Spring 2006

Slide 11

What about Performance? Three regions to stress over Execution of projects No distinction – indistinguishable program semantics Overhead of framework calls Send = Call Wait = Leave Process exchanging, VM get to indistinguishable Scheduling, dispatching, appropriation similarly proficient Can utilize same controls Queueing and sitting tight circumstances for shared assets Identical, since planning orders are equivalent Hypothesis: Lifetime of comparative calculation is equivalent Dave Archer - CS533 - Spring 2006

Slide 12

One Conclusion "In the message situated model, objects move between procedures in messages. In the technique arranged model, forms move between items by calling systems." (inexactly cited from Dearle et al, 1994) Choosing which model to embrace depends on 2 nd - arrange components 0 th arrange = comparative program structure, execution of customer projects 1 st arrange = comparable computational multifaceted nature 2 nd arrange = machine engineering highlights, programming condition – set from the earlier, so will drive choices Can drive choice conclusion on process structure and synchronization utilizing these 2 nd arrange variables Dave Archer - CS533 - Spring 2006

Slide 13

Believable? Natural, however no formal arrangement or confirmation Mixed acknowledgment among a (one-sided) peer group Only one "transformable" illustration 47 references, for the most part taking it on confidence One, Welsh[2002] debate that execution is proportionate when scaled to Internet server requests None question the guaranteed useful duality Bottom line: sufficiently close, with the exception of re execution Dave Archer - CS533 - Spring 2006

Slide 14

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, republished 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-molded Internet Services." PhD Thesis at UC Berkeley, 2002. Dave Archer - CS533 - Spring 2006

SPONSORS