6.004-20,Communication issues: busses, networks, protocols

MIT OpenCourseWarehttp://ocw.mit.edu For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.004 Computation Structures Spring 2009 L19 – Devices & Interrupts 1 6.004 – Spring 20094/16/09Devices & InterruptsLab #6 due tonight! Loop: LD(R3,0,R0) ADDC(R3,4,R3) SUBC(R2,1,R2) BNE(R2,Loop) … (Cough) Excuse me, sir… modified 4/13/09 10:14 L19 – Devices & Interrupts 2 6.004 – Spring 20094/16/09Why an OS? What we’ve got: •A Single Sequence Machine, capable of doing ONE thing at a time – one instruction, one I/O operation, one program. •A universe of gadgets – e.g. I/O devices – that do similar things slightly differently.What we’d like: •To listen to MP3s while reading email. •To access disk, network, and screen “simultaneously”. •To write a single program that does I/O with anybody’s disk. Plausible approaches: •An infinite supply of identical computers with uniform, high-level peripherals for every conceivable purpose… or •An illusion: Make one real computer look like many “virtual” ones. L19 – Devices & Interrupts 3 6.004 – Spring 20094/16/09Operating Systems An OS is the Glue that holds a computer together. -Mediates between competing requests -Resolves names/bindings -Maintains order/fairness KERNEL -a RESIDENT portion of the O/S that handles the most common and fundamental service requests.vir.tu.al \'v*rch-(*-)w*l, 'v*r-ch*l\ \.v*r-ch*-'wal-*t-e-\ \'v*rch-(*-)w*-le-, 'v*rch-(*-)le-\ aj [ME, possessed of certain physical virtues, fr. ML virtualis, fr. L virtus strength, virtue : being in essence or effect but not in fact -vir.tu.al.i.ty n Hardware Registers ALUs PCsCaches Kernel Operating System Applications Device Drivers Scheduler Process Control Blocks (PCBs) Shared Libraries Word Processors Graphical User Interface (GUI) Games Spread Sheets Web Browser Page Tables Device Queues Network Interfaces Security File system I/O Devices L19 – Devices & Interrupts 4 6.004 – Spring 20094/16/09OS organization “Applications” are quasi-parallel “PROCESSES” on “VIRTUAL MACHINES”,each with: •CONTEXT (virtual address space) •Virtual I/O devicesO.S. KERNEL has: •Interrupt handlers •SVC (trap) handlers •Scheduler •PCB structures containing the state of inactive processesSchedulerKERNELP1P2SVC 1 handler SVC 0 handler I/O Handler Device0Alarm Clock I/O Handler Device1…DPYNum=0…DPYNum=1PCBs: P1: P2: loop:SVC(0)...SVC(1)...BR(loop)loop:SVC(0)...SVC(1)...BR(loop) L19 – Devices & Interrupts 5 6.004 – Spring 20094/16/09Asynchronous I/O Handling SVC call from application Application: …ReadKey()| read key into R0 …. . . “A” Device Buffer(in OS Kernel) KEYhit_h() { (read ASCII code, put in buffer)}INTERRUPT from Keyboard n INTERRUPTto OS INOUT ReadKEY_h() { (remove next char from buffer, return in R0) …} TRAP to OS INOUT L19 – Devices & Interrupts 6 6.004 – Spring 20094/16/09Interrupt-based Asynchronous I/O struct Device { char Flag, Data; } Keyboard; KEYhit_h() { Buffer[inptr] = Keyboard.Data; inptr = (inptr + 1) % BUFSIZE; }OPERATION: NO attention to Keyboard during normal operation • on key strike: hardware asserts IRQ to request interrupt • USER program interrupted, PC+4 of interrupted inst. saved in XP • state of USER program saved on KERNEL stack; • KeyboardHandler invoked, runs to completion; • state of USER program restored; program resumes. TRANSPARENT to USER program. Keyboard Interrupt Handler (in O.S. KERNEL): Assume each keyboard has an associated bufferL19 – Devices & Interrupts 7 6.004 – Spring 20094/16/09ReadKey SVC: Attempt #1 Asupervisor call (SVC) is an instruction that transfers control to the kernel so it can satisfy some user request. Kernel returns to user program when request is complete. First draft of a ReadKey SVC handler (supporting a Virtual Keyboard): returns next keystroke on a user’s keyboard to that user’s requesting application: Problem:Can’t interrupt code running in the supervisor mode… so the buffer never gets filled.ReadKEY_h(){int kbdnum = ProcTbl[Cur].DPYNum; while (BufferEmpty(kbdnum)) { /* busy wait loop */}User.Regs[0] = ReadInputBuffer(kbdnum); }int kbdnum = ProcTbl[Cur].DPYNum; while (BufferEmpty(kbdnum)) { /* busy wait loop */}User.Regs[0] = ReadInputBuffer(kbdnum); L19 – Devices & Interrupts 8 6.004 – Spring 20094/16/09ReadKey SVC: Attempt #2 A BETTER keyboard SVC handler: ReadKEY_h(){int kbdnum = ProcTbl[Cur].DPYNum; if (BufferEmpty(kbdnum)) { /* busy wait loop */User.Regs[XP] = User.Regs[XP]-4; } else User.Regs[0] = ReadInputBuffer(kbdnum); }That’s a funny way to write a loop Problem: The process just wastes its time-slice waiting for someone to hit a key... This one actually works! L19 – Devices & Interrupts 9 6.004 – Spring 20094/16/09ReadKey SVC: Attempt #3 EVEN BETTER: On I/O wait, YIELD remainder of quantum: ReadKEY_h(){int kbdnum = ProcTbl[Cur].DPYNum; if (BufferEmpty(kbdnum)) { User.Regs[XP] = User.Regs[XP]-4; Scheduler( ); } else User.Regs[0] = ReadInputBuffer(kbdnum); }RESULT: Better CPU utilization!! Does timesharing cause CPU use to be less efficient?•COST: Scheduling, context-switching overhead; but •GAIN: Productive use of idle time of one process by running another. L19 – Devices & Interrupts 10 6.004 – Spring 20094/16/09Sophisticated Scheduling To improve efficiency further, we can avoid scheduling processes in prolonged I/O wait:•Processes can be in ACTIVE or WAITING (“sleeping”) states; •Scheduler cycles among ACTIVE PROCESSES only; •Active process moves to WAITING status when it tries to read a character and buffer is empty; •Waiting processes each contain a code (eg, in PCB) designating what they are waiting for (eg, keyboard N); •Device interrupts (eg, on keyboard N) move any processes waiting on that device to ACTIVE state. UNIX kernel utilities:•sleep(reason) -Puts CurProc to sleep. “Reason” is an arbitrary binary value giving a condition for reactivation. •wakeup(reason) -Makes active any process in sleep(reason). L19 – Devices & Interrupts 11 6.004 – Spring 20094/16/09ReadKey SVC: Attempt #4 ReadKEY_h() { … if (BufferEmpty(kbdnum)) { User.Regs[XP] = User.Regs[XP] -4; sleep(kbdnum); … }sleep(status s) { ProcTbl[Cur].status = s; Scheduler() }Scheduler() { … while (ProcTbl[i].status != 0) { i = (i+1)%N; } … }wakeup(status s) { for (i = 0; i < N; i += 1) { if (ProcTbl[i].status == s) PCB[i].status = 0; } }SVC call from application KEYhit_h() { … WriteBuffer(kbdnum, key) wakeup(kbdnum); … }INTERRUPT from Keyboard n L19 – Devices & Interrupts 12 6.004 – Spring 20094/16/09The Need for “Real Time” Side-effects of CPU virtualization + abstraction of machine resources (memory, I/O, registers, etc. ) + multiple “processes” executing concurrently+ better CPU utilization -Processing throughput is more variable Our approach to dealing with the asynchronous world -I/O -separate “event handling” from “event processing” Difficult to meet “hard deadlines” -control applications-playing videos/MP3s Real-time as an alternative to time-slicedor fixed-priority preemptive schedulingL19 – Devices & Interrupts 13 6.004 – Spring 20094/16/09Interrupt Latency One way to measure the real-time performance of a system is INTERRUPTLATENCY: •HOW MUCH TIME can elapse between an interrupt request and the START of its handler? time Request Latency Service Time Deadline? OFTEN bad things happen when service is delayed beyond some deadline -"real time" considerations: Missed characters System crashes Nuclear meltdowns “HARD”Real time constraints L19 – Devices & Interrupts 14 6.004 – Spring 20094/16/09Sources of Interrupt Latency What causes interrupt latency: •State save, context switch. •Periods of uninterruptability: Long, uninterruptable instructions --eg block moves, multi-level indirection. Explicitly disabled periods (eg for atomicity, during service of other interrupts). GOAL: BOUND (and minimize) interrupt latency! •Optimize interrupt sequence context switch •Make unbounded-time instructions INTERRUPTABLE (state in registers, etc). •Avoid/minimize disable time •Allow handlers to be interrupted, in certain cases (while still avoiding reentranthandlers!). time Request Latency Service Time Deadline? We can consider this when we write our O/S We can address this in our ISA But, this is application dependent! L19 – Devices & Interrupts 15 6.004 – Spring 20094/16/09Interrupt Disable/Enable EInterrupt Enable/Disable bit (Misc. other stuff:Context, K/U mode, etc.) INTERRUPT DISABLE BIT (part of processor status)... in PC: Often in separate Processor StatusWord ... E=1: DISABLED E=0: ENABLEDe.g.•BETA K-mode bit (disables interrupts, other functions) •Often separate bit/mechanism PCTYPICAL OPERATION: (as with Beta K-mode bit): •ONLY take interrupts if E=0; else defer. •SAVE OLD E on interrupt, install new E from interrupt vector (along with PC, etc). New E=1 (to disable interrupts during handler). •Run handler, with interrupts disabled. •On JMP (at return from handler), saved state restored to processor, resuming interrupted program (with E=0 again). L19 – Devices & Interrupts 16 6.004 – Spring 20094/16/09Scheduling of Multiple Devices DEVICE Keyboard Disk Printer Service Time 800 500 400 Actual w/c Latency ________ ________ ________ "TOY" System scenario: What is the WORST CASE latency seen by each device? Req: K,P,DPKDReq: D,P,KDPKReq: K,D,PKDPAssumptions:•Infrequent interrupt requests (each happens only once/scenario) •Simultaneous requests might be served in ANY order…. Whence •Service of EACH device might be delayed by ALL others! … can we improve this? 500 + 400 = 900 800 + 400 = 1200 800+ 500 = 1300 L19 – Devices & Interrupts 17 6.004 – Spring 20094/16/09Weak (non-preemptive) Priorities ISSUE: Processor becomes interruptable (at fetch of next instruction), several interrupt requests are pending. Which is served first? LATENCIES with WEAK PRIORITIES: Service of each device might be delayed by: •Service of 1 other (arbitrary) device, whose interrupt request was just honored; PLUS •Service of ALL higher-priority devices. DPKReq:P,D,KReq:K,P,DKPDDEVICE Keyboard Disk Printer Service Time 800 500 400 Actual w/c Latency ________ ________ ________ 9008001300WEAK PRIORITY ORDERING: Check in prescribed sequence, eg: DISK > PRINTER > KEYBOARD. vs 1200 – Now delayed by only 1 service! L19 – Devices & Interrupts 18 6.004 – Spring 20094/16/09The Need for Preemption Without preemption, ANY interrupt service can delay ANY other service request… the slowest service time constrains response to fastest devices. Often, tight deadlines can’t be met using this scheme alone. EXAMPLE: 800 uSec deadline (hence 300 uSec maximum interrupt latency) on disk service, to avoid missing next sector... DEVICE Keybrd Disk Printer Serv. Time 800 500 400 Actual Latency 900 800 1300 Max. Delay 300 need PREEMPTION: Allow handlers for LOWER PRIORITY interrupts to be interrupted by HIGHER priority requests! Latency w/preemption Priority 132~0[D] 500 D,P 900 CAN'T SATISFY the disk requirement in this system using weak priorities! L19 – Devices & Interrupts 19 6.004 – Spring 20094/16/09Strong Priority Implementation SCHEME:•Expand E bit in PC to be a PRIORITY integer PRI (eg, 3 bits for 8 levels) •ASSIGN a priority to each device. •Prior to each instruction execution: Find priority Pi of highest requesting device, say DiTake interrupt if and only if Pi > PRI, set PRI = Pi.Strong priorities: KEY: Priority in Processor state Allows interruption of (certain) handlers Allows preemption, but not reentrance BENEFIT: Latency seen at high priorities UNAFFECTED by service times at low priorities. PC:Program Counter PRIL19 – Devices & Interrupts 20 6.004 – Spring 20094/16/09Recurring Interrupts DEVICE Keybrd Disk Printer Serv. Time 800 500 400 Actual Latency 900 0500 Max. Delay 300 P354Max. Freq 100/s 500/s 1000/s Consider interrupts which recur at bounded rates: Note that interrupt LATENCIES don't tell the whole story—consider COMPLETION TIMES, eg for Keyboard in example to the right.Keyboard service not complete until 3ms after request. Often deadlines usedrather than max. delays. DPKPPDPPDDPKDPDPPL19 – Devices & Interrupts 21 6.004 – Spring 20094/16/09Interrupt Load DEVICE Keybrd Disk Printer Serv. Time 800 500 400 Actual Latency 900 0500 Max. Delay 300 P354Max. Freq 100/s 500/s 1000/%Load ______ ______ ______ How much CPU time is consumed by interrupt service? DPKPPDPPDPPDDPKPPDP10 ms. cycle 800u*100/s = 8% 500u*500/s = 25% 400u*1000/s = 40% Remaining fraction (27%) is left over for application; trouble if its <0! L19 – Devices & Interrupts 22 6.004 – Spring 20094/16/09< 10 mS TaskPeriodService time Deadline Supply ship guidance30ms5ms 25ms Gyroscopes4010 20 Cabin pressure100? 100 Example: Ben visits ISS International Space Station’s on-board computer performs 3 tasks: •guiding incoming supply ships to a safe docking •monitoring gyros to keep solar panels properly oriented •controlling air pressure in the crew cabin Assuming a weak priority system:1.What is the maximum service time for “cabin pressure” that still allows all constraints to be met? 2.Give a weak priority ordering that meets the constraints 3.What fraction of the time will the processor spend idle? 4.What is the worst-case delay for each type of interrupt until completion of the corresponding service routine? 16.6 % 25%10%G > SSG > CP 48.33%C,G = 10 + 10 + (5) = 25 C = 10 + (10) = 20 S,G = 5 + 10 + (10) = 25 10L19 – Devices & Interrupts 23 6.004 – Spring 20094/16/09Example: Ben visits ISS (cont’d) Our Russian collaborators don’t like the sound of a “weak” priority interrupt system and lobby heavily to use a “strong” priority interrupt system instead. TaskPeriodService time Deadline Supply ship guidance30ms5ms 25ms Gyroscopes4010 20 Cabin pressure100? 100 Assuming a strong priority system, G > SSG > CP: 1.What is the maximum service time for “cabin pressure” that still allows all constraints to be met? 2.What fraction of the time will the processor spend idle? 3.What is the worst-case delay for each type of interrupt until completion of the corresponding service routine? 100 – (3*10) – (4*5) = 50 5016.6%25%50%8.33%[G] 10 + 5 10100L19 – Devices & Interrupts 24 6.004 – Spring 20094/16/09SummaryDevice interface – two parts: •Device side: handle interrupts from device (transparent to apps) •Application side: handle interrupts (SVCs) from application Scheduler interaction: •“Sleeping” (*inactive) processes waiting for device I/O •Handler coding issues, looping thru User mode Real Time constraints, scheduling, guarantees” •Complex, hard scheduling problems – a black art! •Weak (non-preemptive) vs Strong (preemptive) priorities help… •Common real-world interrupt systems: -Fixed number (eg, 8 or 16) of strong priority levels -Each strong priority level can support many devices, arranged in a weak priority chain