Input/output (I/O)

Required reading: Chapter 15, 16, and 17

Overview

• Programs perform input/output through devices that interact with the real world. An electronic device controler typically controls the device. The controler is connected through a bus to the rest of the computer (processor and memory). By programming the controler, a program on the processor can control the device. Typically the software to control the device is divided in two pieces: the device-independent software and the device-dependent software, the driver.
  Interface issues:
  • Devices in general fall in two categories: block devices (e.g., disk) and character devices (e.g., terminal, printer). Block devices break bytes up into block. Character devices represent a continuous stream of bytes.
  • Names for devices allow users to interact with devices (e.g., mount /dev/rk0/ /mnt). For example, /dev/rk0 specifies the i-node for a special file. the i-node contains a major device number and a minor number. The major device number indexes into bdevsw (block device) or cdevsw (character device). The minor number indexes into an array within that device driver (if there are multiple devices of the same type).
  • The driver can access the driver either has through special memory locations (memory-mapped I/O) or with reserved instructions. Most common today is memory-mapped I/O.
  • The device works in parallel with the main processor. Therefore, the processor and controler need a way to coordinate. The two main styles for coordination are polling and interrupts.
  • Many computers support DMA (direct-memory access) for larger data transfers between device and memory. This allows a device to transfer data from device to memory (and vice versa) without the CPU's involvement. DMA reduces the load on the CPU and makes better use of the bus.
  Writing software for device drivers is challenging:
  • devices are designed by hardware designers
  • concurrency within driver (e.g., interrupt handler). typically addressed by disabling and enabling interrupts carefully.
  • concurrency between driver and device. typically addressed by ensuring that each register has only one writer.
  • potential for deadlock
  • address translation
• Buffer Cache. Disk I/O is slow compared to CPU. The fastest I/O is the one you don't do; thus, cache data blocks in main memory. Buffer cache design issues:
  • Division of memory between programs and buffer cache.
  • Replacement policy. LRU, MRU, etc.
  • Write behind or not? Benefit: delays writes, which may provide write absorption (multiple writes to same block result in one I/O operations). Write behind, unfortunately, opens the window for system failures. Write behind also introduces additional concurrency (e.g., a read request may have to wait until a dirty buffer has been written out).
  • Asynchronous operations. Can caller of operations on the buffer cache proceed while the buffer cache is performing the requested operation?

V6 code examples

• Device driver: RK. Salient properties: 1,228,800 words, 10msec track-to-track seek, 85 msec worst case. Compare with today disks? What improved most capacity or seek time? (Answer: capacity!)

  Driver fits in 3 pages of code.

  • Does the PDP-11 use memory mapped I/O? (Yes, device is accessed through the address RKADDR).
  • How is the device controled? Through the registers ds (driver status), er (error), cs (control status), wc (word count), ba (disk address), and da (data buffer).
  • Concurrency control between processor and device controler: if bit 7 is set in cs, the driver is allowed to manipulate the registers; otherwise, the controler has control. the processor indicates that the controler should take control through bit 0 (GO). the driver caches this information in d_active.
  • Concurrency control within driver: spl5().
  • Polling versus interrupts: bit 6 says whether to issue an interrupt or not on completion of a command.
  • Does device use physical addresses or virtual addresses? (Answer: physical addresses.)
  • How are block numbers translated to disk location? (Answer: rkaddr).
• Buffer cache. v6 keeps a cache of NBUF buffers, which each contain one block. The buffer flags include: B_DONE (I/O operation has completed), B_BUSY (in use by a device), B_WANTED (another threads wants this buffer), B_ASYNC (buffer is used in an asynchronous operation), B_DELWRI (don't write buffer until it leaves the free list), and B_ERROR (I/O operation aborted). Are these flags non exclusive? (No, multiple can be set at the same time, but many combinations are not possible.)
  • If only one application is running, can it use all available memory for buffer cache? (No: buffer cache has a fixed size.)
  • What is the cache replacement policy? (Answer: LRU. brelse puts buffers at the end of the freelist. getblk grabs them from the beginning of the freelist).
  • Why are disk blocks cached? The buffer is placed on the freelist immediately after it has been used. (Yes, but when it is put on the freelist, it also stays on the device list, thus getblk will find it there and avoid doing a disk access.)
  • Does the buffer cache support write behind? (Yes: writes are delayed optionally, writedb versus writeb.) How long are they delayed? (Until buffer is needed, but still is dirty (4961), or a user utility forces them out, which apparently runs once every 30 seconds.)
  • Buffer cache also support asynchronous operations. The caller can continue while the I/O operation is in progress (e.g., see 4820). iodone() releases the buffer when the I/O operation is complete.
  • Various form of concurrency control: (1) no buffers available at all; (2) desired buffer in cache, but in use for an I/O operation (B_BUSY, B_WANTED); (3) dirty buffers needs to be used for something else (B_DELWRI); (4) asynchronous operation in action (B_ASYNC); and (5) operation completed (B_DONE).
  • Can bio overwrite a part of a block? If so, must bio read the block in first? (No. A write always overwrites a block completely.)
  • Can a thread ever be blocked on a disk write it earlier issued (i.e., is it possible that a thread can a second write to the same block that is used by the first write)? (Yes, it can get blocked if it attempts to write a block for which it just issued an asynchronous write).
  • Can you delete 1 line of code from bio.c and cause a deadlock?