Very Brief History of OS Several Distinct Phases CS162 Operating Systems and Systems Programming Lecture 2 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 Concurrency Processes Threads and Address Spaces Rapid Change in Hardware Leads to changing OS Batch Multiprogramming Timeshare Graphical UI Ubiquitous Devices Gradual Migration of Features into Smaller Machines January 24th 2011 Ion Stoica http inst eecs berkeley edu cs162 Situation today is much like the late 60s Small OS 100K lines Large 10M lines 5M browser 100 1000 people years 1 19 10 Review Migration of OS Concepts and Features Ion Stoica CS162 UCB Spring 2011 Lec 1 2 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 1 19 10 Ion Stoica CS162 UCB Spring 2011 1 19 10 Lec 1 3 Page 1 Ion Stoica CS162 UCB Spring 2011 Lec 1 4 Goals for Today Threads How do we provide multiprogramming What are processes How are they related to threads and address spaces 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 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 1 19 10 Ion Stoica CS162 UCB Spring 2011 ManyCore Multiprogramming right 1 19 10 Lec 1 5 Recall 61C What happens during execution Addr R0 R31 F0 F30 PC Fetch Exec Execution sequence 1 19 10 Fetch Instruction at PC Decode Execute possibly using registers Write results to registers mem PC Next Instruction PC Repeat Ion Stoica CS162 UCB Spring 2011 Ion Stoica CS162 UCB Spring 2011 Lec 1 6 Uniprograming vs Multiprograming 232 1 Data1 Data0 Inst237 Inst236 Inst5 Inst4 Inst3 Inst2 Inst1 Inst0 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 PC PC PC PC Multics UNIX Linux OS 2 Windows NT 2000 XP Mac OS X Often called multitasking but multitasking has other meanings talk about this later Addr 0 1 19 10 Lec 1 7 Page 2 Ion Stoica CS162 UCB Spring 2011 Lec 1 8 Challenges of Multiprograming Processes Process unit of resource allocation and execution Each applications wants to own the machine virtual machine abstraction Owns memory address space Owns file descriptors file system context Encapsulate one or more threads sharing process resources Applications compete with each other for resources Need to arbitrate access to shared resources concurrency Need to protect applications from each other protection 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 Applications need to communicate cooperate with each other concurrency Application instance consists of one or more processes 1 19 10 Ion Stoica CS162 UCB Spring 2011 1 19 10 Lec 1 9 Ion Stoica CS162 UCB Spring 2011 Lec 1 10 How can we give the illusion of multiple processors The Basic Problem of Concurrency The basic problem of concurrency involves resources CPU1 CPU2 CPU3 Hardware single CPU single DRAM single I O devices Multiprogramming API processes think they have exclusive access to shared resources CPU1 Shared Memory OS has to coordinate all activity CPU2 CPU3 CPU1 CPU2 Time Assume a single processor How do we provide the illusion of multiple processors Multiple processes I O interrupts How can it keep all these things straight Multiplex in time Each virtual CPU needs a structure to hold Basic Idea Use Virtual Machine abstraction Program Counter PC Stack Pointer SP Registers Integer Floating point others Simple machine abstraction for processes Multiplex these abstract machines How switch from one CPU to the next Dijkstra did this for the THE system Save PC SP and registers in current state block Load PC SP and registers from new state block Few thousand lines vs 1 million lines in OS 360 1K bugs What triggers switch 1 19 10 Ion Stoica CS162 UCB Spring 2011 Timer voluntary yield I O other things 1 19 10 Lec 1 11 Page 3 Ion Stoica CS162 UCB Spring 2011 Lec 1 12 Properties of this simple multiprogramming technique How to protect threads from one another All virtual CPUs share same non CPU resources 1 Protection of memory I O devices the same Memory the same Every task does not have access to all memory Consequence of sharing 2 Protection of I O devices 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 Every task does not have access to every device 3 Protection of Access to Processor preemptive switching from task to task Use of timer Must not be possible to disable timer from usercode This unprotected model common in Embedded applications Windows 3 1 Machintosh switch only with yield Windows 95 ME switch with both yield and timer 1 19 10 Ion Stoica CS162 UCB Spring 2011 1 19 10 Lec 1 13 Address space the set of accessible addresses associated states Perhaps nothing Perhaps acts like regular memory Perhaps ignores writes Perhaps causes I O operation Heap 1 Code 1 Prog 1 Virtual Address Space 1 Prog 2 Virtual Address Space 2 Data 1 Heap 2 Code 2 OS code Translation Map 1 OS data Translation Map 2 OS heap Stacks Perhaps causes exception fault Ion Stoica CS162 UCB Spring 2011 Code Data Heap Stack Stack 1 Stack 2 Memory mapped I O 1 19 10 Data 2 Code Data Heap Stack Program Address Space What happens when you read or write to an address Lec 1 14 Providing Illusion of Separate Address Space Load new Translation Map on Switch Recall Program s Address Space For
View Full Document
Unlocking...