Page 1 CS162!Operating Systems and!Systems Programming!Lecture 2!Concurrency:!Processes, Threads, and Address Spaces"January 24th, 2011!Ion Stoica!http://inst.eecs.berkeley.edu/~cs162!Lec 1.2!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!Very Brief History of OS"• 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!– 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-years!Lec 1.3!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!Review: Migration of OS Concepts and Features"Lec 1.4!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!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 compatibility issues!– Very important for Windows 2000/XP/Vista/…!– POSIX tries to help here!• System generation/configuration!– How to make generic OS fit on specific hardware!Page 2 Lec 1.5!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!Goals 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 are"adapted from slides ©2005 Silberschatz, Galvin, and Gagne. Many slides generated from lecture notes by Kubiatowicz."Lec 1.6!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!Threads"• Unit (“thread”) of execution:!– Independent Fetch/Decode/Execute loop!– Unit of scheduling!– Operating in some address space"• Uniprogramming: one thread at a time!– MS/DOS, early Macintosh, Batch processing!• Multiprogramming: more than one thread at a time!– Multics, UNIX/Linux, OS/2, Windows NT/2000/XP, Mac OS X!• ManyCore ⇒ Multiprogramming, right?"Lec 1.7!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!Fetch"Exec"R0"…"R31"F0"…"F30"PC"…"Data1"Data0"Inst237"Inst236"…"Inst5"Inst4"Inst3"Inst2!Inst1"Inst0"Addr 0"Addr 232-1"Recall (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 !PC"PC"PC"PC"Lec 1.8!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!Uniprograming vs. Multiprograming"• Uniprogramming: one thread at a time!– MS/DOS, early Macintosh, Batch processing!– Easier for operating system builder!– Get rid of concurrency (only one thread accessing resources!)!– 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)!Page 3 Lec 1.9!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!Challenges of Multiprograming"• Each applications wants to own the machine virtual machine abstraction"• Applications compete with each other for resources!– Need to arbitrate access to shared resources concurrency"– Need to protect applications from each other protection"• Applications need to communicate/cooperate with each other concurrency"Lec 1.10!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!Processes"• Process: unit of resource allocation and execution!– Owns memory (address space)!– Owns file descriptors, file system context, …!– Encapsulate one or more threads sharing process resources!• Why processes? !– Navigate fundamental tradeoff between protection and efficiency!– Processes provides memory protection while threads donʼt (share a process memory)!– Threads more efficient than processes (later)!• Application instance consists of one or more processes !Lec 1.11!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!The Basic Problem of Concurrency"• The basic problem of concurrency involves resources:!– Hardware: single CPU, single DRAM, single I/O devices!– Multiprogramming API: processes think they have exclusive access to shared resources!• OS has to coordinate all activity!– Multiple processes, I/O interrupts, …!– How can it keep all these things straight?!• Basic Idea: Use Virtual Machine abstraction!– Simple machine abstraction for processes!– Multiplex these abstract machines!• Dijkstra did this for the “THE system”!– Few thousand lines vs 1 million lines in OS 360 (1K bugs)!Lec 1.12!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!How can we give the illusion of multiple processors?"CPU3"CPU2"CPU1"Shared 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 things!CPU1" CPU2" CPU3" CPU1" CPU2"Time "Page 4 Lec 1.13!1/19/10! Ion Stoica CS162 ©UCB Spring 2011!Properties 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 1.14!1/19/10!
View Full Document
Unlocking...