操作系统介绍

1 .CS 61C: Great Ideas in Computer Architecture Lecture 22: Operating Systems Krste Asanović & Randy H. Katz http:// inst.eecs.berkeley.edu /~ cs61c/fa17 1 Fall 2017 -- Lecture #22 11/13/17

2 .Memory CS61C so far… CPU Caches MIPS Assembly C Programs #include < stdlib.h > int fib( int n) { return fib(n-1) + fib(n-2); } .foo lw $t0, 4($r0) addi $t1, $t0, 3 beq $t1, $t2, foo nop HW 1 Project 1 Project 2 2 Fall 2017 -- Lecture #22 11/13/17

3 .So How is a Laptop Any Different? Keyboard Screen Storage 3 Fall 2017 -- Lecture #22 11/13/17

4 .Memory Adding I/O CPU Caches MIPS Assembly C Programs #include < stdlib.h > int fib( int n) { return fib(n-1) + fib(n-2); } .foo lw $t0, 4($r0) addi $t1, $t0, 3 beq $t1, $t2, foo nop HW 1 Project 2 I/O (Input/Output) Screen Keyboard Storage 4 Fall 2017 -- Lecture #22 11/13/17 Project 1

5 .CPU+$s, Memory Raspberry Pi (Less than $40 on Amazon in 2017) Storage I/O (Micro SD Card) Serial I/O (USB) Network I/O (Ethernet) Screen I/O (HDMI) 5 Fall 2017 -- Lecture #22 11/13/17

6 .It’s a Real Computer! 6 Fall 2017 -- Lecture #22 11/13/17

7 .But Wait… That’s not the same! When we run VENUS, it only executes one program and then stops. When I switch on my computer, I get this: Yes, but that’s just software! The Operating System (OS) 7 Fall 2017 -- Lecture #22 11/13/17

8 .Well, “Just Software” The biggest piece of software on your machine? How many lines of code? These are guesstimates: Codebases (in millions of lines of code). CC BY-NC 3.0 — David McCandless © 2013 http:// www.informationisbeautiful.net /visualizations/million-lines-of-code/ 8 Fall 2017 -- Lecture #22 11/13/17

9 .Operating System 9 Fall 2017 -- Lecture #22 11/13/17

10 .What Does the OS do? OS is first thing that runs when computer starts Finds and controls all devices in the machine in a general way Relying on hardware specific “device drivers” Starts services (100+) File system, Network stack (Ethernet, WiFi , Bluetooth, … ), TTY (keyboard), … Loads , runs and manages programs: Multiple programs at the same time (time-sharing) Isolate programs from each other (isolation) Multiplex resources between applications (e.g., devices) 10 Fall 2017 -- Lecture #22 11/13/17

11 .Agenda Devices and I/O Polling Interrupts OS Boot Sequence Multiprogramming/time-sharing 11 Fall 2017 -- Lecture #22 11/13/17

12 .Agenda Devices and I/O Polling Interrupts OS Boot Sequence Multiprogramming/time-sharing 12 Fall 2017 -- Lecture #22 11/13/17

13 .How to Interact with Devices? Assume a program running on a CPU. How does it interact with the outside world? Need I/O interface for Keyboards, Network, Mouse, Screen, etc. Connect to many types of devices Control these devices , respond to them, and transfer data Present them to user programs so they are useful cmd reg. data reg. Operating System Processor Memory PCI Bus USB SATA, SAS, … 13 Fall 2017 -- Lecture #22 11/13/17

14 .Instruction Set Architecture for I/O What must the processor do for I/O? Input: read a sequence of bytes Output: write a sequence of bytes Interface options Special input/output instructions & hardware Memory mapped I/O Portion of address space dedicated to I/O I/O device registers there (no memory) Use normal load/store instructions, e.g. lw / sw Very common, used by RISC-V 14 Fall 2017 -- Lecture #22 11/13/17

15 .Memory Mapped I/O Certain addresses are not regular memory Instead, they correspond to registers in I/O devices cntrl reg. data reg. 0xFFFFFFFF 0x00000000 0x8000000 address 15 Fall 2017 -- Lecture #22 11/13/17 0x7FFFFFFF Memory-mapped Program & Data Memory

16 .Processor-I/O Speed Mismatch 1 GHz microprocessor I/O throughput: 4 Gi -B/s ( lw / sw ) Typical I/O data rates: 10 B/s (keyboard) 100 Ki-B/s (Bluetooth) 60 Mi -B/s ( USB 2 ) 100 Mi -B/s ( Wifi , depends on standard) 125 Mi -B/s (G-bit E thernet) 550 Mi -B/s ( cutting edge SSD) 1.25 Gi -B/s (USB 3.1 Gen 2) 6.4 GiB /s (DDR3 DRAM) These are peak rates – actual throughput is lower Common I/O devices neither deliver nor accept data matching processor speed 16 Fall 2017 -- Lecture #22 11/13/17

17 .17 Fall 2017 -- Lecture #22 11/13/17

18 .Agenda Devices and I/O Polling Interrupts OS Boot Sequence Multiprogramming/time-sharing 18 Fall 2017 -- Lecture #22 11/13/17

19 .Processor Checks Status before Acting Device registers generally serve two functions: Control Register , says it’s OK to read/write (I/O ready) [think of a flagman on a road] Data Register , contains data Processor reads from Control Register in loop Waiting for device to set Ready bit in Control reg (0  1) Indicates “data available” or “ready to accept data” Processor then loads from (input) or writes to (output) data register I/O device resets control register bit (1  0) Procedure called “ Polling ” 19 Fall 2017 -- Lecture #22 11/13/17

20 .Input: Read from keyboard into a 0 lui t0,0x7ffff #7ffff000 ( io addr ) Waitloop : lw t1,0(t0 ) # read control andi t1,t1,0x1 # ready bit beq t1,zero, Waitloop lw a0,4(t0 ) # data Output: Write to display from a1 lui t0,0x7ffff #7ffff0000 Waitloop : lw t1, 8 ($t0) # write control andi t1,t1,0x1 # ready bit beq t1,zero, Waitloop sw a1,12 (t0 ) # data “Ready” bit is from processor’s point of view! I/O Example (Polling) 20 Fall 2017 -- Lecture #22 11/13/17

21 .Cost of Polling? Assume for a processor with 1 GHz clock rate Taking 400 clock cycles for a polling operation Call polling routine Check device (e.g., keyboard or wifi input available) Return What’s the percentage of processor time spent polling? Example: Mouse Poll 30 times per second Set by requirement not to miss any mouse motion (which would lead to choppy motion of the cursor on the screen) 21 Fall 2017 -- Lecture #22 11/13/17

22 .Peer Instruction Hard disk: transfers data in 16-Byte chunks and can transfer at 16 MB/second. No transfer can be missed. What percentage of processor time is spent in polling (assume 1 GHz clock)? 2 % 4 % 20 % 40% 22 Fall 2017 -- Lecture #22 11/13/17

23 .What is the Alternative to Polling? Polling wastes processor resources Akin to waiting at the door for guests to show up What about a bell? Computer lingo for bell: Interrupt Occurs when I/O is ready or needs attention Interrupt current program Transfer control to special code “interrupt handler” 23 Fall 2017 -- Lecture #22 11/13/17

24 .Agenda Devices and I/O Polling Interrupts OS Boot Sequence Multiprogramming/time-sharing 24 Fall 2017 -- Lecture #22 11/13/17

25 .Traps/Interrupts/Exceptions: altering the normal flow of control I i-1 HI 1 HI 2 HI n I i I i+1 program trap handler An external or internal event that needs to be processed - by another program – the OS. The event is often unexpected from original program’s point of view. 25 Fall 2017 -- Lecture #22 11/13/17

26 .Interrupt-Driven I/O Label: sll t1,s3,2 add t1,t1,s5 lw t1,0(t1 ) or s1,s1,t1 add s3,s3,s4 bne s3,s2,Label Stack Frame Stack Frame Stack Frame handler : save registers decode interrupt cause handle interrupt c lear interrupt restore registers mret Interrupt(SPI0) CPU Vector Interrupt Table SPI0 handler … … Handler Execution Incoming interrupt suspends instruction stream Looks up the vector (function address) of a handler in an interrupt vector table stored within the CPU Perform a jal to the handler (save PC in special MEPC * register) Handler run on current stack and returns on finish (thread doesn’t notice that a handler was run) *MEPC : Machine Exception Program Counter 26 Fall 2017 -- Lecture #22 11/13/17

27 .Terminology In CS61C (other definitions in use elsewhere): Interrupt – caused by an event external to current running program E .g., key press, disk I/O Asynchronous to current program Can handle interrupt on any convenient instruction “Whenever it’s convenient, just don’t wait too long” Exception – caused by some event during execution of one instruction of current running program E.g., divide by zero, bus error, illegal instruction Synchronous M ust handle exception precisely on instruction that causes exception “Drop whatever you are doing and act now” Trap – action of servicing interrupt or exception by hardware jump to “interrupt or trap handler” code 27 Fall 2017 -- Lecture #22 11/13/17

28 .Precise Traps Trap handler’s view of machine state is that every instruction prior to the trapped one (e.g., overflow) has completed, and no instruction after the trap has executed. Implies that handler can return from an interrupt by restoring user registers and jumping back to interrupted instruction Interrupt handler software doesn’t need to understand the pipeline of the machine, or what program was doing! More complex to handle trap caused by an exception than interrupt Providing precise traps is tricky in a pipelined superscalar out-of-order processor! But a requirement, e.g., for Virtual memory to function properly (see next lecture) 28 Fall 2017 -- Lecture #22 11/13/17

29 .Trap Handling in 5 -Stage Pipeline Exceptions are handled like pipeline hazards Complete execution of instructions before exception occurred Flush instructions currently in pipeline (i.e., convert to nop s or “bubbles”) Optionally store exception cause in status register Indicate type of exception Note : several exceptions can occur in a single clock cycle! Transfer execution to trap handler PC Inst. Mem D Decode E M Data Mem W + Illegal Opcode Divide By 0 Data address Exceptions PC address Exception Asynchronous Interrupts 29 Fall 2017 -- Lecture #22 11/13/17