I/O Systems

I/O Systems

11. I/O Systems 11.1 Basic Issues in Device Management 11.2 A Hierarchical Model 11.3 I/O Devices 11.4 Device Drivers Memory-Mapped vs Explicit Device Interfaces Programmed I/O with Polling Programmed I/O with Interrupts Direct Memory Access (DMA) 11.5 Device Management Buffering and caching Error Handling Disk Scheduling Operating Systems

1 Basic Issues I/O devices: Communication devices Input only (keyboard, mouse, joystick, light pen) Output only (printer, visual display, voice synthesizers) Input/output (network card) Storage devices Input/output (disk, tape, writeable optical disks) Input only (CD-ROM)

Operating Systems 2 Basic Issues Every device type/model is different input/output/both, block/char oriented, speed, errors, Main tasks of I/O system: Present logical (abstract) view of devices Hide details of hardware interface Hide error handling Facilitate efficient use Overlap CPU and I/O Support sharing of devices

Protection when device is shared (disk) Scheduling when exclusive access needed (printer) Operating Systems 3 Hierarchical Model of the I/O System Operating Systems 4 I/O System Interface

Operating Systems 6 I/O System Interface Block-Oriented Device Interface direct access contiguous blocks usually fixed block size Operations: Open: verify device is ready, prepare it for access Read: Copy a block into main memory Write: Copy a portion of main memory to a block

Close: Release the device Note: these are lower level than those of the FS Used by File System and Virtual Memory System Applications typically go through the File System Operating Systems 7 I/O System Interface Stream-Oriented Device Interface character-oriented sequential access Operations: Open: reserve exclusive access

Get: return next character of input stream Put: append character to output stream Close: release exclusive access Note: these too are different from those of the FS but some systems try to present a uniform view of files and devices Operating Systems 8 I/O System Interface Network Interface key abstraction: socket endpoints of a line between two processes

once established, use protocol to communicate Connection-less protocols send messages, called datagrams Operations: send, receive (to/from sockets) Connection-based protocols establish a connection called virtual circuit Operations: connect, accept, read, write Operating Systems 9 I/O Devices Operating Systems

10 I/O Devices Output Display monitors character or graphics oriented Different data rates: 25 x 80 characters vs 800 x 600 pixels (1B allows 256 colors) Refresh 30-60 times/s for video Printers (ink jet, laser)

Interface write to controller buffer wait for completion handle errors Operating Systems 11 I/O Devices Input Keyboards most common: QWERTY Pointing devices Mouse

Trackball Joystick Scanners Interface device generates interrupt when data is ready read data from controller buffer low data rates, not time-critical Operating Systems 12 I/O Devices Storage Disks

Surface, tracks/surface, sectors/track, bytes/sector All sectors numbered sequentially 0..(n-1) (device controller provides mapping) Operating Systems 13 I/O Devices Storage Track skew Account for seek-to-next-track to minimize rotational delay Operating Systems

14 I/O Devices Storage Double-sided or multiple surfaces Tracks with same diameter = cylinder Sectors are numbered within cylinder consecutively to minimize seek time Operating Systems 15 I/O Devices Storage Optical disks

CD-ROM, CD-R (WORM), CD-RW Originally designed for music Data stored as continuous spiral, subdivided into sectors Higher storage capacity: 0.66 GB/surface Constant linear speed (200-530 rpm), high data rate Operating Systems 16 I/O Devices Storage Critical issue: data transfer rates of disks Sustained rate: continuous data delivery

Peek rate: transfer once read/write head is in place depends on rotation speed and data density Example: 7200 rpm, 100 sectors/track, 512 bytes/sector. What is the peak transfer rate? 7200 rpm: 60,000/7200=8.3 ms/rev 8.3/100 = 0.083 ms/sector 512 bytes transferred in 0.083 ms: ~6.17 MB/s What is the Sustained rate?Depends on file organization Operating Systems 17

Hierarchical Model of the I/O System Operating Systems 19 Device Drivers accept command from application get/put character read/write block send/receive packet interact with device

controller (hardware) to carry out command driver-controller interface: set of registers Operating Systems 20 Device Drivers: Interface to Controller How does driver read/write registers? Explicit: special I/ O instruction:

io_store cpu_reg, dev_no, dev_reg Memory-mapped: CPU instruction: store cpu_reg, n (n is memory address) Operating Systems 21 Programmed I/O with Polling

Who moves the data? How does driver know when device is ready? CPU is responsible for moving every character to/from controller buffer detecting when I/O operation completed Protocol to input a character/block: Operating Systems 22 Programmed I/O with Polling Driver operation to input sequence of characters or blocks:

i = 0; do { write_reg(opcode, read); while (busy_flag == true) {??...}; //waiting mm_in_area[i] = data_buffer; increment i; compute; } while () Operating Systems 23 Programmed I/O with Polling

Driver operation to output sequence of characters or blocks: i = 0; do { compute; data_buffer = mm_out_area[i]; increment i; write_reg(opcode, write); while (busy_flag == true) {??...}; } while (data_available) Operating Systems 24

Programmed I/O with Polling What to do while waiting? Idle (busy wait) Some other computation (what?) How frequently to poll? Give up CPU Device may remain unused for a long time Data may be lost Operating Systems 25

Programmed I/O with Interrupts CPU is responsible for moving data, but Interrupt signal informs CPU when I/O operation completes Protocol to input a character/block: Operating Systems 26 Programmed I/O with Interrupts Compare Polling with Interrupts: i = 0; do { write_reg(opcode, read);

while (busy_flag == true) {}; //active wait mm_in_area[i] = data_buffer; increment i; compute; } while () i = 0; do { write_reg(opcode, read); block to wait for interrupt; mm_in_area[i] = data_buffer; increment i; compute; } while ()

Operating Systems 27 Programmed I/O with Interrupts Example: Keyboard driver do { block to wait for interrupt; mm_in_area[i] = data_buffer; increment i; compute(mm_in_area[]); } while (data_buffer != ENTER) Note: there is no write_reg command, pressing a key generates interrupt

compute depends on type of input: raw/cooked E.g. trying to type text but with typos raw: t e s t BS x cooked: t e x t Operating Systems 28 Programmed I/O with Interrupts I/O with interrupts: more complicated, involves OS Example: sequence of reads More overhead (OS) but better device utilization

Operating Systems 29 Direct Memory Access (DMA) CPU does not transfer data, only initiates operation DMA controller transfers data directly to/from main memory Interrupts when transfer completed

Input protocol: Operating Systems 31 DMA Driver (CPU) operation to input sequence of bytes: write_reg(mm_buf, m); // give parameters write_reg(count, n); write_reg(opcode, read); // start op block to wait for interrupt; Writing opcode triggers DMA controller DMA controller issues interrupt after n chars in memory

Cycle Stealing DMA controller competes with CPU for memory access generally not a problem because: Memory reference would have occurred anyway CPU is frequently referencing data in registers or cache, bypassing main memory Operating Systems 32 Device Management Operating Systems

34 Device Management Device-independent techniques: Buffering/caching Error Handling Device Scheduling/Sharing Operating Systems 35 Buffering Reasons for buffering

Allows asynchronous operation of producers and consumers Allows different granularities of data Consumer or producer can be swapped out while waiting for buffer fill/empty Operating Systems 36 Buffering Single buffer operation Double buffer (buffer swapping) Increases overlap

Ideal when: time to fill = time to empty = constant When times differ, benefits diminish Operating Systems 37 Buffering Circular Buffer (bounded buffer from Ch. 2) Producer and consumer each use an index nextin gives position of next input nextout gives position of next output Both are incremented modulo n at end of operation When average times to fill/empty are comparable but

vary over time: circular buffer absorbs bursts Buffer Queue Variable size buffer to prevent producer blocking Implement as linked list needs dynamic memory management Buffer Cache: pool of buffers for repeated access Operating Systems 38 Error Handling Types of error Persistent vs Transient SW vs HW

Persistent SW error Repair/reinstall program Transient SW/HW errors: Error detecting/correcting codes e.g., Hamming code (separate lecture) Retry operation, e.g. disk seek/read/write Persistent HW errors: Redundancy in storage media Operating Systems 39 Bad block detection/handling

Block may be bad as a manufacturing fault or during use Parity bit is used to detect faulty block The controller bypasses faulty block by renumbering A spare block is used instead Two possible re-mappings: a) simple b) preserves

contiguity of allocation Operating Systems 45 Stable storage Some applications cannot tolerate any loss of data (even temporarily) Stable storage protocols: Use 2 independent disks, A and B Write: write to A; if successful, write to B; if either fails, go to recovery

Read: read from A and B; if A!=B, go to Recovery Recovery from Media Failure: A or B contains correct data (parity); remap failed disk block Recovery from Crash: if while reading, just repeat the read if while writing A, B is correct; if while writing B, A is correct; recover from whichever is correct Operating Systems 46 RAID RAID = Redundant Array of Independent Disks Increased performance through parallel access

Increased reliability through redundant data Maintain exact replicas of all disks most reliable but wasteful Maintain only partial recovery information (e.g. error correcting codes) Operating Systems 47 Device Management Disk Scheduling Requests for different blocks arrive concurrently from

different processes Minimize rotational delay: re-order requests to blocks on each track to access in one rotation Minimize seek time: Conflicting goals: Minimize total travel distance Guarantee fairness Operating Systems 48

Device Management Algorithms FIFO: requests are processed in the order of arrival simple, fair, but inefficient SSTF (Shortest Seek Time First): always go to the track thats nearest to the current positions most efficient but prone to starvation Scan (Elevator): maintain a direction of travel always proceed to the nearest track in the current direction of travel if there is no request in the current direction, reverse direction fair, acceptable performance

Operating Systems 49 Device Management Example: assume moving from 0 to 5; then 12,4,7 arrive Operating Systems 50

Recently Viewed Presentations

  • Title Here

    Title Here

    Be clear about expectations Goals Measurable change Ongoing participation Next Phase: 2016 Focus on 2 businesses, fully engaged Manager support from beginning to end Hospital food service, eldercare facility, local convenience store Seek advanced tech support from Lean Path Consider...
  • BBC Radio 1/1Xtra R1/1X Stories: R1 Sun, 16:00-19:00

    BBC Radio 1/1Xtra R1/1X Stories: R1 Sun, 16:00-19:00

    Slide . In the past three years this slot has seen 15-34s fluctuate between 450k and 770k. Reach (000s) by age groups for R1/1X Stories Sun, 16:00-19:00
  • Lukas 7:36-8:3 Lukas 7:36-8:3  God nooi ons uit

    Lukas 7:36-8:3 Lukas 7:36-8:3 God nooi ons uit

    * Simon kom tweede Jesus gaan self voort en kontrasteer Simon se optrede teenoor Jesus met diƩ van die vrou. En Simon kom ernstig tweede. Nie dat hy soseer verkeerd opgetree het nie, maar in vergelyking met die vrou het...
  • Note Taking Kathleen High 1 Fundamentals  Observe  Record

    Note Taking Kathleen High 1 Fundamentals Observe Record

    Note Taking Kathleen High Fundamentals Observe Record Review Observing involves: Set the stage "Be here now" in class Watch for clues Set the Stage Complete outside assignments Bring the right materials Sit front and center Conduct a short pre-class review...
  • Junior Advisement Night - Fultonschools.org

    Junior Advisement Night - Fultonschools.org

    www.gafutures.org. Graduate from high school with a . GPA of 3.7 . At least a 1200 SAT score (combined reading/math) or at least a 26 ACT score . Pays 100% of tuition (Covers full standard-rate tuition at a public college...
  • Allergy and Anaphylaxis - Missouri

    Allergy and Anaphylaxis - Missouri

    Journal of Allergy Clinical Immun. 2009;124:175-183. Sampson, HA, "Food Allergy", from Biology Toward Therapy, Hospital Practice, 2000: May * * * * * * * * * * * * Allergy and Anaphylaxis Pre-Test Questions Name 6 of the 8...
  • IP Fragmentation - Columbus State University

    IP Fragmentation - Columbus State University

    The router Not the subnet Multiple Fragmentations Original packet may be fragmented multiple times along its route Defragmentation Internet layer process on destination host defragments, restoring the original packet IP Defragmentation only occurs once Fragmentation and IP Fields More Fragments...
  • Weld Quality - PC\|MAC

    Weld Quality - PC\|MAC

    Incomplete fusion is the failure of a welding process to fuse layers of weld metal or weld metal and base metal. Incomplete fusion may occur at any point in a groove or fillet weld. Causes for incomplete fusion include: Insufficient...