操作系统的发展历程

1 . Recall: What is an operating system? CS162 •  Special layer of software that provides application software access to hardware resources Operating Systems and –  Convenient abstraction of complex hardware devices Systems Programming –  Protected access to shared resources Lecture 2 –  Security and authentication –  Communication amongst logical entities Introduction to Processes appln appln August 28th, 2017 appln OS Prof. Ion Stoica http://cs162.eecs.Berkeley.edu Hardware 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.2 Very Brief History of OS Very Brief History of OS •  Several Distinct Phases: •  Several Distinct Phases: –  Hardware Expensive, Humans Cheap »  Eniac, … Multics “I think there is a world market for maybe five computers.” – Thomas Watson, chairman of IBM, 1943 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.3 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.4 Page 1 

2 . Very Brief History of OS Very Brief History of OS •  Several Distinct Phases: •  Several Distinct Phases: –  Hardware Expensive, Humans Cheap –  Hardware Expensive, Humans Cheap »  Eniac, … Multics »  Eniac, … Multics –  Hardware Cheaper, Humans Expensive »  PCs, Workstations, Rise of GUIs Thomas Watson was often called “the worlds greatest salesman” by the time of his death in 1956 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.5 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.6 Very Brief History of OS Very Brief History of OS •  Several Distinct Phases: •  Several Distinct Phases: –  Hardware Expensive, Humans Cheap –  Hardware Expensive, Humans Cheap »  Eniac, … Multics »  Eniac, … Multics –  Hardware Cheaper, Humans Expensive –  Hardware Cheaper, Humans Expensive »  PCs, Workstations, Rise of GUIs »  PCs, Workstations, Rise of GUIs –  Hardware Really Cheap, Humans Really Expensive –  Hardware Really Cheap, Humans Really Expensive »  Ubiquitous devices, Widespread networking »  Ubiquitous devices, Widespread networking •  Rapid change in hardware leads to changing OS –  Batch ⇒ Multiprogramming ⇒ Timesharing ⇒ Graphical UI ⇒ Ubiquitous Devices –  Gradual migration of features into smaller machines •  Today –  Small OS: 100K lines / Large: 10M lines (5M browser!) –  100-1000 people-years 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.7 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.8 Page 2 

3 . OS Archaeology Migration of OS Concepts and Features •  Because of the cost of developing an OS from scratch, most modern OSes have a long lineage: •  Multics à AT&T Unix à BSD Unix à Ultrix, SunOS, NetBSD,… •  Mach (micro-kernel) + BSD à NextStep à XNU à Apple OS X, iPhone iOS •  MINIX à Linux à Android OS, Chrome OS, RedHat, Ubuntu, Fedora, Debian, Suse,… •  CP/M à QDOS à MS-DOS à Windows 3.1 à NT à 95 à 98 à 2000 à XP à Vista à 7 à 8 à 10 à phone à … 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.9 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.10 Today: Four Fundamental OS Concepts OS Bottom Line: Run Programs •  Thread Executable 0xFFF… Program Source OS –  Single unique execution context: fully describes program state –  Program Counter, Registers, Execution Flags, Stack compiler int main() Execute editor {…; data stack Load & •  Address space (with translation) Memory } –  Programs execute in an address space that is distinct from the memory instructions heap space of the physical machine •  Process a.out data foo.c –  An instance of an executing program is a process consisting of an address space and one or more threads of control •  Load instruction and data segments of instructions executable file into memory 0x000… •  Dual mode operation / Protection •  Create stack and heap PC: –  Only the “system” has the ability to access certain resources •  “Transfer control to program” –  The OS and the hardware are protected from user programs and user registers programs are isolated from one another by controlling the translation •  Provide services to program Processor from program virtual addresses to machine physical addresses •  While protecting OS and program 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.11 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.12 Page 3 

4 . Recall (61B): Instruction Fetch/Decode/Execute Recall (61C): What happens during program execution? The instruction cycle Addr 232-1 Memory R0 Processor next … … PC: R31 Fetch Data1 F0 Instruction fetch instruction … Exec Data0 decode F30 Inst237 Decode PC Inst236 … Registers Inst5 •  Execution sequence: Inst4 –  Fetch Instruction at PC Execute Inst3 PC –  Decode ALU Inst2 PC –  Execute (possibly using registers) Inst1 PC data –  Write results to registers/mem Inst0 PC –  PC = Next Instruction(PC) Addr 0 –  Repeat 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.13 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.14 First OS Concept: Thread of Control Second OS Concept: Program’s Address Space 0xFFF… •  Certain registers hold the context of thread •  Address space ⇒ the set of accessible stack addresses + state associated with them: –  Stack pointer holds the address of the top of stack –  For a 32-bit processor there are 232 = 4 »  Other conventions: Frame pointer, Heap pointer, Data billion addresses heap –  May be defined by the instruction set architecture or by compiler Static Data conventions •  What happens when you read or write to •  Thread: Single unique execution context an address? code –  Program Counter, Registers, Execution Flags, Stack –  Perhaps nothing 0x000… •  A thread is executing on a processor when it is resident in the –  Perhaps acts like regular memory processor registers. –  Perhaps ignores writes •  PC register holds the address of executing instruction in the –  Perhaps causes I/O operation thread »  (Memory-mapped I/O) –  Perhaps causes exception (fault) •  Registers hold the root state of the thread. –  The rest is “in memory” 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.15 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.16 Page 4 

5 . Address Space: In a Picture Multiprogramming - Multiple Threads of Control 0xFFF… PC: stack stack Proc Proc Proc SP: 1 2 n … heap heap Static Data OS code Processor registers Static Data stack instruction Code Segment heap Static Data 0x000… code •  What’s in the code segment? Static data segment? stack •  What’s in the Stack Segment? –  How is it allocated? How big is it? heap Static Data •  What’s in the Heap Segment? code –  How is it allocated? How big? 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.17 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.18 Administrivia: Getting started How can we give the illusion of multiple processors? •  Start homework 0 immediately ⇒ Due next Monday (9/4)! –  cs162-xx account, Github account, registration survey vCPU1 vCPU2 vCPU3 –  Vagrant and VirtualBox – VM environment for the course vCPU1 vCPU2 vCPU3 vCPU1 vCPU2 »  Consistent, managed environment on your machine Shared Memory Time –  Get familiar with all the cs162 tools, submit to autograder via git •  Assume a single processor. How do we provide the illusion of –  Homework slip days: You have 3 slip days multiple processors? –  Multiplex in time! •  THIS Friday (9/1) is early drop day! Very hard to drop afterwards… •  Each virtual “CPU” needs a structure to hold: –  Program Counter (PC), Stack Pointer (SP) •  Should be going to section already! –  Registers (Integer, Floating point, others…?) •  Group sign up form will be out after drop deadline •  How switch from one virtual CPU to the next? –  Save PC, SP, and registers in current state block –  Work on finding groups ASAP: 4 people in a group! –  Load PC, SP, and registers from new state block –  Try to attend either same section or 2 sections by same TA •  What triggers switch? –  Timer, voluntary yield, I/O, other things 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.19 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.20 Page 5 

6 . The Basic Problem of Concurrency Properties of this simple multiprogramming technique •  The basic problem of concurrency involves resources: •  All virtual CPUs share same non-CPU resources –  Hardware: single CPU, single DRAM, single I/O devices –  I/O devices the same –  Multiprogramming API: processes think they have exclusive access to –  Memory the same shared resources •  Consequence of sharing: •  OS has to coordinate all activity –  Each thread can access the data of every other thread (good for –  Multiple processes, I/O interrupts, … sharing, bad for protection) –  How can it keep all these things straight? –  Threads can share instructions (good for sharing, bad for protection) •  Basic Idea: Use Virtual Machine abstraction –  Can threads overwrite OS functions? –  Simple machine abstraction for processes •  This (unprotected) model is common in: –  Multiplex these abstract machines –  Embedded applications •  Dijkstra did this for the “THE system” –  Windows 3.1/Early Macintosh (switch only with yield) –  Few thousand lines vs 1 million lines in OS 360 (1K bugs) –  Windows 95—ME (switch with both yield and timer) 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.21 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.22 Protection Third OS Concept: Process •  Operating System must protect itself from user programs •  Process: execution environment with Restricted Rights –  Reliability: compromising the operating system generally causes it to –  Address Space with One or More Threads crash –  Owns memory (address space) –  Security: limit the scope of what processes can do –  Owns file descriptors, file system context, … –  Privacy: limit each process to the data it is permitted to access –  Encapsulate one or more threads sharing process resources –  Fairness: each should be limited to its appropriate share of system •  Why processes? resources (CPU time, memory, I/O, etc) –  Protected from each other! •  It must protect User programs from one another –  OS Protected from them •  Primary Mechanism: limit the translation from program address space –  Processes provides memory protection to physical memory space –  Threads more efficient than processes (later) –  Can only touch what is mapped into process address space •  Fundamental tradeoff between protection and efficiency •  Communication easier within a process •  Additional Mechanisms: •  Communication harder between processes –  Privileged instructions, in/out instructions, special registers •  Application instance consists of one or more processes –  syscall processing, subsystem implementation »  (e.g., file access rights, etc) 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.23 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.24 Page 6 

7 . Single and Multithreaded Processes Fourth OS Concept: Dual Mode Operation •  Hardware provides at least two modes: –  “Kernel” mode (or “supervisor” or “protected”) –  “User” mode: Normal programs executed •  What is needed in the hardware to support “dual mode” operation? –  A bit of state (user/system mode bit) –  Certain operations / actions only permitted in system/kernel mode »  In user mode they fail or trap –  User à Kernel transition sets system mode AND saves the user PC •  Threads encapsulate concurrency: “Active” component »  Operating system code carefully puts aside user state then performs the necessary operations •  Address spaces encapsulate protection: “Passive” part –  Kernel à User transition clears system mode AND restores appropriate –  Keeps buggy program from trashing the system user PC •  Why have multiple threads per address space? »  return-from-interrupt 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.25 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.26 User/Kernel (Privileged) Mode Administrivia (Cont’d) •  Ion’s office hours: Mondays 11-12, Wednesday 12-1 User Mode in 465 Soda interrupt exception – No office hours Wednesday 8/30 syscall rtn rfi •  Avoid private Piazza posts – others have same question exit exec Kernel Mode •  Three Free Online Textbooks: –  Click on “Resources” link for a list of “Online Textbooks” –  Can read O'Reilly books for free as long as on campus or VPN »  One book on Git, two books on C Limited HW access Full HW access •  Webcast: https://CalCentral.Berkeley.edu/ (CalNet sign in) –  Webcast is *NOT* a replacement for coming to class! 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.27 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.28 Page 7 

8 . Simple Protection: Base and Bound (B&B) code 0000… 0000… code Static Data Static Data heap heap 5 min break stack 0100… Base stack 0010… 1000… code 1000… >= Static Data Program 1010… address heap Bound < stack 1100… 1100… FFFF… 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.30 Simple Protection: Base and Bound (B&B) Another idea: Address Space Translation code 0000… 0000… •  Program operates in an address space that is distinct from the code Static Data physical memory space of the machine Static Data heap heap s” s” res res stack add stack 0x000… 0100… add l sica ual Base y t “ph “vir 0010… 1000… 1000… Processor Memory code >= translator Static Data Program 1010… address heap Addresses translated Bound < when program is loaded stack 1100… 1100… •  Requires relocating loader 0xFFF… •  Still protects OS and isolates program FFFF… •  No addition on address path 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.31 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.32 Page 8 

9 . A simple address translation with Base and Bound Tying it together: Simple B&B: OS loads process 0000… 0000… 0000… code code code Proc Proc Proc Static Data 1 2 … n Static Data Static Data heap Addresses translated on-the-fly heap OS heap stack stack stack Base Address sysmode 1 1000… code 1000… 1000… code Base xxxx … 0000… Static Data 0010… Program 0010… Static Data Bound xxxx… FFFF… heap address uPC xxxx… heap stack 1100… PC Bound < code 3000… stack 1100… regs Static Data 0100… … heap •  Can the program touch OS? stack 3080… •  Can it touch other programs? FFFF… FFFF… 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.33 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.34 Simple B&B: OS gets ready to execute process Simple B&B: User Code Running 0000… 0000… Proc Proc Proc code RTU Proc Proc Proc code 1 2 … n 1 2 … n Static Data Static Data OS heap OS heap stack stack sysmode 1 1000… sysmode 0 1000… code code Base 1000 … 0000… Static Data Base 1000 … 0000… Static Data Bound 1100… FFFF… heap Bound 1100… FFFF… heap uPC 0001… uPC xxxx… stack 1100… •  How does stack 1100… •  Privileged Inst: PC kernel switch PC 0001… code 3000… code 3000… set special regs Static Data between regs Static Data registers 00FF… … heap processes? 00FF… … heap •  RTU •  First question: stack 3080… stack 3080… How to return FFFF… to system? FFFF… 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.35 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.36 Page 9 

10 . 3 types of Mode Transfer •  Syscall –  Process requests a system service, e.g., exit –  Like a function call, but “outside” the process How do we get the system target address of the –  Does not have the address of the system function to call “unprogrammed control transfer?” –  Like a Remote Procedure Call (RPC) – for later –  Marshall the syscall id and args in registers and exec syscall •  Interrupt –  External asynchronous event triggers context switch –  e. g., Timer, I/O device –  Independent of user process •  Trap or Exception –  Internal synchronous event in process triggers context switch –  e.g., Protection violation (segmentation fault), Divide by zero, … •  All 3 are an UNPROGRAMMED CONTROL TRANSFER –  Where does it go? 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.37 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.38 Interrupt Vector Simple B&B: User => Kernel 0000… Proc Proc Proc code Address and properties of 1 2 … n each interrupt handler Static Data interrupt number (i) OS heap stack sysmode 0 1000… code Base 1000 … 0000… Static Data Bound 1100… FFFF… heap intrpHandler_i () { …. uPC xxxx… } stack 1100… PC 0000 1234 code 3000… regs Static Data 00FF… •  How to return … heap •  Where else do you see this dispatch pattern? to system? stack 3080… FFFF… 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.39 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.40 Page 10 

11 . Simple B&B: Interrupt Simple B&B: Switch User Process 0000… 0000… Proc Proc Proc code Proc Proc Proc code RTU 1 2 … n 1 2 … n Static Data Static Data OS heap OS heap stack stack sysmode 1 1000… sysmode 1 1000… code 1000 … code Base 1000 … 0000… Static Data Base 3000 … 0000… Static Data 1100 … Bound 1100 … FFFF… heap Bound 0080 … FFFF… heap 0000 1234 uPC 0000 1234 uPC 0000 0248 stack 1100… regs stack 1100… PC IntrpVector[i] PC 0001 0124 code 3000… 00FF… code 3000… regs regs Static Data Static Data 00FF… 00D0… •  How to save … heap •  How to save … heap registers and stack 3080… registers and stack 3080… set up system set up system stack? FFFF… stack? FFFF… 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.41 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.42 Simple B&B: “resume” Conclusion: Four fundamental OS concepts 0000… Proc Proc Proc code RTU •  Thread 1 2 … n –  Single unique execution context Static Data heap –  Program Counter, Registers, Execution Flags, Stack OS •  Address Space with Translation stack –  Programs execute in an address space that is distinct from the memory sysmode 0 1000… 1000 … code space of the physical machine Base 3000 … 0000… 1100 … Static Data •  Process Bound 0080 … FFFF… heap 0000 1234 –  An instance of an executing program is a process consisting of an uPC xxxx xxxx regs stack 1100… address space and one or more threads of control PC 000 0248 00FF… code 3000… •  Dual Mode operation/Protection regs 00D0… Static Data –  Only the “system” has the ability to access certain resources •  How to save … heap –  The OS and the hardware are protected from user programs and user registers and stack 3080… programs are isolated from one another by controlling the translation set up system from program virtual addresses to machine physical addresses stack? FFFF… 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.43 8/28/17 Stoica CS162 ©UCB Fall 2017 Lec 2.44 Page 11