CS162Operating Systems andSystems ProgrammingLecture 3Concurrency:Processes, Threads, and Address SpacesSeptember 2nd, 2009Prof. John Kubiatowiczhttp://inst.eecs.berkeley.edu/~cs162Lec 3.29/2/09 Kubiatowicz CS162 ©UCB Fall 2009Review: History of OS• Why Study?– To understand how user needs and hardware constraints influenced (and will influence) operating systems• Several Distinct Phases:– Hardware Expensive, Humans Cheap » Eniac, … Multics– Hardware Cheaper, Humans Expensive » PCs, Workstations, Rise of GUIs– Hardware Really Cheap, Humans Really Expensive » Ubiquitous devices, Widespread networking• Rapid Change in Hardware Leads to changing OS– Batch Multiprogramming Timeshare Graphical UI Ubiquitous Devices Cyberspace/Metaverse/??– Gradual Migration of Features into Smaller Machines• Situation today is much like the late 60s– Small OS: 100K lines/Large: 10M lines (5M browser!)– 100-1000 people-yearsLec 3.39/2/09 Kubiatowicz CS162 ©UCB Fall 2009Review: Migration of OS Concepts and FeaturesLec 3.49/2/09 Kubiatowicz CS162 ©UCB Fall 2009Review: Implementation Issues(How is the OS implemented?)• Policy vs. Mechanism– Policy: What do you want to do?– Mechanism: How are you going to do it?– Should be separated, since policies change • Algorithms used– Linear, Tree-based, Log Structured, etc…• Event models used– threads vs event loops• Backward compatability issues– Very important for Windows 2000/XP/Vista/…– POSIX tries to help here• System generation/configuration– How to make generic OS fit on specific hardwareLec 3.59/2/09 Kubiatowicz CS162 ©UCB Fall 2009Goals for Today• How do we provide multiprogramming?• What are Processes?• How are they related to Threads and Address Spaces?Note: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne Note: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne. Many slides generated from my lecture notes by Kubiatowicz.Lec 3.69/2/09 Kubiatowicz CS162 ©UCB Fall 2009Concurrency• “Thread” of execution– Independent Fetch/Decode/Execute loop– Operating in some Address space• Uniprogramming: one thread at a time– MS/DOS, early Macintosh, Batch processing– Easier for operating system builder– Get rid concurrency by defining it away– Does this make sense for personal computers?• Multiprogramming: more than one thread at a time– Multics, UNIX/Linux, OS/2, Windows NT/2000/XP, Mac OS X– Often called “multitasking”, but multitasking has other meanings (talk about this later)• ManyCore Multiprogramming, right?Lec 3.79/2/09 Kubiatowicz CS162 ©UCB Fall 2009The Basic Problem of Concurrency• The basic problem of concurrency involves resources:– Hardware: single CPU, single DRAM, single I/O devices– Multiprogramming API: users think they have exclusive access to shared resources• OS Has to coordinate all activity– Multiple users, I/O interrupts, …– How can it keep all these things straight?• Basic Idea: Use Virtual Machine abstraction– Decompose hard problem into simpler ones– Abstract the notion of an executing program– Then, worry about multiplexing these abstract machines• Dijkstra did this for the “THE system”– Few thousand lines vs 1 million lines in OS 360 (1K bugs)Lec 3.89/2/09 Kubiatowicz CS162 ©UCB Fall 2009FetchExecR0…R31F0…F30PC…Data1Data0Inst237Inst236…Inst5Inst4Inst3Inst2Inst1Inst0Addr 0Addr 232-1Recall (61C): What happens during execution?• Execution sequence:– Fetch Instruction at PC – Decode– Execute (possibly using registers)– Write results to registers/mem– PC = Next Instruction(PC)– Repeat PCPCPCPCLec 3.99/2/09 Kubiatowicz CS162 ©UCB Fall 2009How can we give the illusion of multiple processors?CPU3CPU2CPU1Shared Memory• Assume a single processor. How do we provide the illusion of multiple processors?– Multiplex in time!• Each virtual “CPU” needs a structure to hold:– Program Counter (PC), Stack Pointer (SP)– Registers (Integer, Floating point, others…?)• How switch from one CPU to the next?– Save PC, SP, and registers in current state block– Load PC, SP, and registers from new state block• What triggers switch?– Timer, voluntary yield, I/O, other thingsCPU1 CPU2 CPU3 CPU1 CPU2Time Lec 3.109/2/09 Kubiatowicz CS162 ©UCB Fall 2009Properties of this simple multiprogramming technique• All virtual CPUs share same non-CPU resources– I/O devices the same– Memory the same• Consequence of sharing:– Each thread can access the data of every other thread (good for sharing, bad for protection)– Threads can share instructions(good for sharing, bad for protection)– Can threads overwrite OS functions? • This (unprotected) model common in:– Embedded applications– Windows 3.1/Machintosh (switch only with yield)– Windows 95—ME? (switch with both yield and timer)Lec 3.119/2/09 Kubiatowicz CS162 ©UCB Fall 2009Modern Technique: SMT/Hyperthreading• Hardware technique – Exploit natural propertiesof superscalar processorsto provide illusion of multiple processors– Higher utilization of processor resources• Can schedule each threadas if were separate CPU– However, not linearspeedup!– If have multiprocessor,should schedule eachprocessor first• Original technique called “Simultaneous Multithreading”– See http://www.cs.washington.edu/research/smt/– Alpha, SPARC, Pentium 4 (“Hyperthreading”), Power 5Lec 3.129/2/09 Kubiatowicz CS162 ©UCB Fall 2009Administriva: Time for Project Signup• Project Signup: Watch “Group/Section Assignment Link”– 4-5 members to a group» Everyone in group must be able to actuallyattend same section» The sections assigned to you by Telebears are temporary!– Only submit once per group!» Everyone in group must have logged into their cs162-xx accounts once before you register the group» Make sure that you select at least 2 potential sections» Due Tomorrow (Thursday 9/3) by 11:59pm• Sections:– Watch for section assignments next Monday/Tuesday– Attend new sections next weekJingtao Wang75 EvansTu 3:00P-4:00P 1044 Evans4 Evans4 Evans6 EvansLocationJingtao WangTu 2:00P-3:00P 103Alex SmolenTu 1:00P-2:00P 105 (New)Gunho LeeTu 11:00A-12:00P 102Gunho LeeTu 10:00A-11:00A 101TATimeSectionLec 3.139/2/09 Kubiatowicz CS162 ©UCB Fall 2009Administrivia (2)• Cs162-xx accounts:–
View Full Document
Unlocking...