THECS380L: Mike DahlinSeptember 4, 2008Be aware of the fact that experience does by no means automatically lead to wisdom andunderstanding; in other words, ma ke a conscio us effo rt to learn as much as possible fromyour previous experiences– E. W. Dijkstra. “The Structure of the ‘THE’ Multiprogramming System.” Communications ofthe ACM, 11(5), May 1968, pp. 341-3461 Preliminaries1.1 Review• Multics: key ideas– Specific technologies: fine-grained sharing, dynamic libraries– Principles∗ Designing for security: time tested principles (failsafe defaults, complete mediation,...)· Challenge: Psychological acceptability...KISS∗ Overall design:· Unified naming and addressing· Fine grained sharing· Dynamic linking· Autonomy (“Modularity”)1.2 Outline• THE: System structure• Admin: Project• THE: Perls of wisdom1.3 Preview• Historical perspective: UNIX• Minimal abstractions: exokernel, scheduler activations• Virtual machines: Disco, ESX12 Multix v. THE v. UnixPurpose of these papers in classAll provide useful historic context – how architecture of modern OS coalesced.“Flavor” of papers very different.• Multix– Important (and difficult) technical content– Research approach : Ambition. Build the ideal system. Push idea (sharing) to extreme• THE and Unix– Simplicity. Humility. Build something that works.– Research approach∗ THE: Scientific approach to design· Also...· Push how to build correct system to an extreme· → new abstractions (semaphore)∗ Unix: “Good taste” in design· “What are the right abstractions’?”· Lampson: Hints for computer system designThe designer usually finds himself floundering in a sea of possibilities, unclearabout how one choice will limit his freedom to make other choices, or affect thesize and performance of the e ntire system.· How to teach this?· Apologies – lots of philosophical musings today compared to last time (and mostof future meetings.)· Probably because I don’t know how to teach this...• Easy to see the contributions of mutix – plenty of “hard stuff.” Next two papers – THE andUnix – h ave a different flavor. Very little seems “hard.” Much seems “obvious in retrospect.”Many of the lessons are broader than “use this mechanism to solve this problem.” Instead,many of the lessons are about how to build systems that actually work – “taste”, “discipline,”“simplicity.” The su ccess of these systems came f rom “fear” and from the ability to choosejust the right subs et/variation of ideas th at had been floating around in the community.Two reasonable approaches to research – push an idea to the extreme, build something thatworks. Try to do both?• I feel I am very good at the multix style of research and pretty good at the THE style. I wishI was better at the THE and Unix style.• I have gotten much better at the “mechanical” process of building systems that work (“onlytrivial 10-minute to find and fix bugs”). Mostly from learning the hard way (doing it wrongand learning “fear”). Some from believing advice like that in this paper. The latter is easier.– I certainly have gotten better at “given a spec, spend enough time on design so thatbuilding/debugging easy”2– Maybe this also enforces a discipline of creating a spec that is sufficiently “humble”– (So maybe one way to teach/learn the hard idea of “good taste” is to practice some of(I think) straightforward pieces of advice on how to build working systems in this andother papers.)• QUESTION: Do you think successful class projects likely to look more like Multix or THE/Unix?– Hint Dijkstra: “h aving very limited resources (viz. a group of six people of, on theaverage, half-time availability) and wishing to contribute to th art of system design...wewere faced with the problem of how to get the necessary experience.”3 THE3.1 Historical perspective• Written at a time when OS complexity running amuck– IBM System 360 announced 1964, OS/360 delivered 1967;– IBM System 370 introduces virtual memory (1972)• Influ ential paper:– Overall architecture and approach: proposes “scientific” approach to OS design andimplementation– Specific abstractions:∗ Cooperating sequential processes∗ Synchronization∗ Virtual memory3.2 System structure• Core contribution: strict hierarchy of sequential processes → can reason about correctness ofsystem1. Strict hierarchical structure2. Sequential processes – “succession of the various states has a logical meaning but notthe actual speed with which the sequential process is performed.”– undefined speed r atios– semaphores – explicit mutual synchronization statements– Hugely influential – a formal way to reason about concurren cy.∗ Obvious (today). At the time, other systems assu med time bounds from, say, aninterrupt occurred until when it was serviced. Prob lems: (1) complexity ripplesthrough the system (now need to “protect” these assumptions throughout yourdesign – not mod ular, (2) difficult to test. I seem to recall Dijkstra writingabout a contemporary IBM OS that occasionally would lose a character of inputbecause it was written in this style, but I cannot find the cite.3• Another key contribution: clean definition (and one of the first working implementations) ofvirtual memory abstraction– Virtual addressing – separation of logical address (“segment” Note: not same as currentsegment – fixed size virtual page) and physical address (“page”).• The hierarchylevel 0 processor allocation (sequential processes) – “above level 0 the number of processorsactually shared is no longer relevant.”level 1 Segment controller (virtual memory) – “at all higher levels identification of informationtakes place in terms of segments, the actual storage pages [have] lost their identity [andhave] disappeared from the picture.”level 2 message interpreter – demultiplex consoles to processes – “Above level 2 it is as if eachprocess had its private conversational console.”level 3 buffering of streamslevel 4 user-level programslevel 5 the operator3.3 Evaluation of “strict” hierarchical structure and simplifying assumptions• If one can enforce strict hierarchy reasoning about system becomes simpler– The above statement is not controversial (right?). The question is: can one enforce astrict hierarchy?• Can sophisticated systems be constructed as strict