Lecture 16 - Input/Output, Disks

- I got a rock. - Charlie Brown, It's the Great Pumpkin, Charlie Brown.

Agenda

Announcements

  • Boo. Have some pumpkin pi.
  • The change from a self-scheduled to a take-home final exam is official.
  • This week in CS Colloquium: The CS Faculty talk about graduate school. Friday 2:35 PM, TCL 206.

    • Input/Output

    We will not spend much time in class going over the background - just highlights. Read Chapter 5 if you're not comfortable with some of the background.

    The OS provides I/O instructions to control devices. Control may be by

  • direct I/O instructions - send out data on a port or bus

    Read/Write chunks of data directly on an I/O Port with special machine instructions.

  • memory-mapped I/O - read/write memory in special locations assigned to a device

    Can use regular machine instructions to read and write the portion of memory reserved for communication with each device.

    • Accessing devices

    Either way, how do we know when the device needs the attention of the CPU? Remember that "I/O Wait" means the process is not in the ready queue or on the CPU, ideally.

  • Polling - When OS has control of the CPU, it queries the device. This could end up being a busy-wait if the data will not remain available for long, such as on a port.

    We saw an example of this with the Commodore 64 manual, where we could examine a memory location to get, for example, the state of a joystick controller.

  • Interrupts -

    We have seen interrupts before - this is what makes a process leave the CPU when a time quantum expires.

    1. CPU Interrupt request line triggered by I/O device
    2. CPU switched to interrupt handler
    3. Maskable to ignore or delay some interrupts (consider an interrupt being interrupted!)
    4. Interrupt vector to dispatch interrupt to correct handler (Interrupt Service Routine - ISR)

    Interrupt service can be complicated on modern machines - consider pipelined execution (see text).

  • Direct Memory Access - I/O controller gets data and puts the results directly in memory at a specified location

    Used to avoid programmed I/O for large data movement

    Requires DMA-capable controller

    Bypasses CPU to transfer data directly between I/O device and memory - CPU can be doing other things - avoid the need to copy things from a device buffer into user space

    • Application I/O Interface

    I/O system calls encapsulate device behaviors using a common interface for a wide variety of devices

    Device drivers hide differences among I/O controllers from kernel - same kernel routines can call functions in specific device drivers without worrying about the details of the device

    Device characteristics

  • Character-stream or block
  • Sequential or random-access
  • Sharable or dedicated
  • Speed of operation
  • read-write, read only, or write only

    • Block devices

  • "large" blocks of data read/written at once
  • include disk drives
  • read, write, seek operations
  • Raw I/O (kernel) or file-system (user) access

    • Character devices

  • include keyboards, mice, serial ports, printers, modems
  • get, put operations on individual characters

    • Network Devices

    Similar to block and character, but different enough to be unique

  • socket interface to separate network protocol from network operation
  • other options: pipes, FIFOs, streams, queues, mailboxes
  • need to deal with large amounts of data rapidly as well as short interactive traffic

    • Blocking vs. Nonblocking I/O

  • Blocking - process suspended (removed from ready/run) until I/O completed
  • Easy to use and understand
  • Insufficient for some needs
  • Nonblocking - I/O call returns as much as available
  • User interface, data copy (buffered I/O)
  • Implemented via multithreading
  • Returns quickly with count of bytes read or written
  • Asynchronous - process runs (doing something else) while I/O executes
  • Difficult to use
  • I/O subsystem signals process when I/O completed
  • need to wait for the data explicitly
  • overlap I/O with other computation

    • Kernel I/O Subsystem

    Beyond just the interface, the kernel manages devices to improve efficiency

  • Scheduling
  • some I/O request ordering via per-device queue
  • consider a series of disk access requests - what order to use? efficiency? priorities?
  • Buffering - may be needed because of
  • device speed mismatch (disk to printer, modem to disk)
  • device transfer size mismatch (gather network packets)
  • Caching - fast memory holding copy of data
  • always just a copy
  • key to performance
  • has come up before and will come up again
  • Spooling - hold output for a device
  • if device can serve only one request at a time
  • printing, maybe tape I/O
  • Device reservation - provides exclusive access to a device
  • system calls for allocation and deallocation
  • deadlock avoidance/detection/recovery
  • Error Handling
  • OS can recover from disk read, device unavailable, transient write failures (retry)
  • switch to another device, if possible
  • return failure code when I/O request fails
  • error logs
  • Bookkeeping and Kernel Data Structures
  • state info (open files, network connections, etc.)
  • complex data structures (i.e., Unix buffer cache)

    • Performance

    I/O performance is a critical factor in overall system performance:

  • reduce number of context switches
  • reduce data copying
  • reduce interrupts by using large transfers, smart controllers, polling
  • use DMA
  • balance CPU, memory, bus, and I/O performance for highest throughput

    • Disks and Disk Structures

    We will consider disks and file structures in much more detail than most of the other types of I/O devices.

    The data is written to the surface of the disk. How can it be arranged?

    CD/DVD is arranged in a "spiral" for a continuous stream.

    We'll concentrate on magnetic disks (floppy disk, hard disk). A hard disk may have multiple surfaces, or platters. For simplicity, assume there is only one disk, or platter, involved.

    A read/write head is needed for each platter.

    The data on a disk is arranged in concentric rings called cylinders or tracks.

    Each cylinder of the disk is divided into chunks called sectors that contain blocks, the minumum allocatable and addressable unit on the disk. Since there is more space on the outside of the disk, there may be more blocks in outer cylinders than there are on inner cylinders.

    The particular configuration of cylinders, sectors and the number of platters is the drive geometry. The actual drive geometry may be difficult to determine, as modern disk drives lie, controllers lie, and by the time you get the numbers they may be completely meaningless.

    So to read or write data on the disk, a cylinder and sector must be specified. The read/write head must be positioned over the desired cylinder and sector. The read/write heads are typically connected to the end of a moveable arm. This arm is moved to position the head at the correct cylinder. When the disk rotates and the desired sector reaches the read-write head, the read or write operation can proceed.

    The speed of this operation depends on two major factors:

  • seek time - the time it takes to move the read/write head to the correct cylinder
  • rotational latency - the time it takes for the correct sector to rotate under the read/write head

    • We can minimize seek time by minimizing the distance the read/write head has to move in order to service the incoming requests.