IO Devices

There exists a large variety of IO devices:

  • Many of them with different properties.
  • They seem to require different interfaces to manipulate and manage them.
    • We don’t want a new interface for every device.

Challenge:

  • Uniform and efficient approach to IO.

Device Drivers

  • Drivers originally compiled into kernel.
  • Nowadays dynamically loaded when needed.
    • Linux modules.
      • Number and types vary greatly.
        • Even while OS is running (hot-plug USB devices).

Role and Requirements of a Driver

  • Translate requests through the device-independent standard interface (open, close, read, write) into appropriate sequence of commands (register manipulations) for the particular hardware.
    • After issuing command to device, the device either:
      • Completes immediately and the driver simply returns to the caller.
      • Or, device must process the request and driver usually blocks waiting for an IO complete interrupt.
  • Initialise the hardware at boot time, and shut it down cleanly at shutdown.
  • Must be thread safe as they can be called by another process while a process is already blocked in the driver.

Driver Categories

  • Drivers classified into similar categories.
    • Block devices and character (stream of data) device.
  • OS defines a standard (internal) interface to the different classes of devices.

Driver To Kernel Interface

Major issue is uniform interfaces to devices and kernel:

  • Uniform device interface for kernel code.
    • Allows different devices to be used the same way.
    • Allow internal changes to device driver without fear of breaking kernel code.
  • Uniform kernel interface for device code.
    • Drivers use a defined interface to kernel services (e.g. kmalloc, etc).
    • Allows kernel to evolve without breaking existing drivers.
  • Both uniform interfaces together avoid a lot of programming implementing new interfaces.
    • Retains compatibility as drivers and kernels change over time.

Acessing IO Controllers

  • Separate IO and memory space.
    • IO controller registers appear as IO ports.
    • Accessed with special IO instructions.
  • Memory-mapped IO.
    • Controller registers appear as memory.
    • Use normal load/store instructions to access.
  • Hybrid:
    • Both ports and memory mapped IO.

IO Interaction

Programmed IO

  • IO module (controller) performs action, not the processor.
  • Sets appropriate bits in the IO status register.
  • No interrupts occur.
  • Processor continually checks status until operation is complete.
    • Polling/busy waiting.

Pros:

  • Can be efficient if IO completes quickly.

Cons:

  • Wastes CPU cycles espeically for long IO actions.

Interrupt Driven IO

  • Processor is interrupted when IO module (controller) ready to exchange data.
  • Processor is free to do other work.

Pros:

  • No needless waiting.

Cons:

  • Consumes a lot of processor time because every word read or written passes through the processor.

IO Using Direct Memory Accesss

  • DMA controller transfers a block of data directly to or from memory.
  • An interrupt is sent when the task is complete.
  • Processor only involved at beginning and end of transfer.

Pros:

  • Reduces interrupts.
    • Less (expensive) context switches or kernel entry-exits.

Cons:

  • Requires contiguous regions (buffers).

Interrupt Handlers

  • Save registers not already saved by hardware interrupt mechanism.
  • (Optionally) set up context for interrupt service procedurre.
    • Typically, handler runs in the context of the currently running process.
      • No expensive context switch.
  • Set up stack for interrupt service procedure.
    • Handler usually runs on the kernel stack of current process.
    • Or nests if already in kernel mode running on kernel stack.
  • Ack/Mask interrupt controller, reenable other interrupts.
    • Implies potential for interrupt nesting.
  • Run interrupt service procedure.
    • Acknowledges interrupt at device level.
    • Figures out what caused the interrupt.
      • Received a network packet, disk read finished, UART transmit queue empty, etc….
    • If needed, it signals blocked device driver.
  • In some cases, will have woken up a higher priority blocked thread.
    • Choose newly worken thread to schedule next.
    • Set up MMU context for process to run next.
  • Load new/original process’s registers.
  • Re-enable interrupt; start running the new process.

Top Half / Bottom Half

Interrupt handlers are split in two:

  • Top half:
    • Actually responds to interrupt.
    • Interrupts are disabled.
    • Execution time should be short.
      • Most of the complex computation deferred to bottom half.
      • Don’t want to miss other interrupts.
  • Bottom half:
    • Does deferred work (e.g. IP stack processing).
    • All interrupts are enabled.
      • Allows top half to service a new interrupt while bottom half is still working.
    • Cannot sleep, access user space or invoke the scheduler.

Buffering

Buffering improves performance as processes don’t need to read/write a device a byte/word at a time.

  • Each syscall adds a significant overhead.
  • Process must wait until each IO is complete.
    • Blocking/interrupt/waking adds to overhead.
    • Many short runs of a process is inefficient.

User Level Buffering

Process specifies a memory buffer that incoming data is placed in until it fills.

  • Filling can be done by interrupt service routine.
  • Only a single system call, and block/wakeup per data buffer.
    • Much more efficient.

Problems:

  • If buffer is paged out to disk.
    • Could lose data while unavailable buffer is paged in.
    • Could lock buffer in memory (needed for DMA), however many processes doing IO reduce RAm available for paging. Can cause deadlock as RAM is limited.
  • Consider write case:
    • Buffer is available for reuse when:
      • Either process must block until potential slow device drains buffer.
      • Or deal with asynchronous signals indicating buffer drained.

Single Kernel Buffer

OS assigns a buffer in kernel’s memory for an IO request.

Stream-oriented scenario:

  • Used a line at a time.
  • User input from a terminal is one line at a time with carriage return signalling the end of the line.
  • Output to the terminal is one line at a time.

Block-oriented scenario:

  • Input transfers made to buffer.
  • Block copied to user space when needed.
  • Another block is written into the buffer.
    • Can be read ahead to improve performance.
  • Swapping can occur since input is taking place in system memory, not user memory.
  • OS keeps track of assignment to system buffers to user processes.

Speed up:

  • Computation and trasnfer can be done in parallel.
  • (No buffering cost) / (Single buffering cost) = (T + C) / (max(T, C) + M).
    • Usually M is smaller than T, giving favourable results.

Problems:

  • If kernel buffer is full.
    • User buffer is swapped out, or

    • Application is slow to process previous buffer.

    • Start to lose chracters or drop network packets.

Double Kernel Buffer

OS uses two kernel buffers instead of one.

  • Process can transfer data to or from one buffer whiile the OS empties or fills the other buffer.

Speed up:

  • Computation and memory copy can be done in parallel.
  • (No buffering cost) / (double buffering cost) = (T + C) / (max(T, C + M)).

Advantages:

  • Potential speed up over single buffer.

Disadvantages:

  • May be insufficient for really bursty traffic.
    • Lots of application writes between long periods of computation.
    • Long periods of application computation while receiving data.
    • Might want to read-ahead more than a single block for disk.

Circular Buffer

OS uses more than two buffers.

  • Generalisation of double buffer.