Lecture Notes for Operating Systems Concepts

14 October 2004 - Device Management

Home Truths

Devices are slow.
- Some are mechanical and have millisecond (at best) responses.
- Electronic ones operate a no where near the rate of a modern CPU.

OS Responsibilities

Provide a convenient device abstraction.
- Not only within a device class, but among them too.
Provide efficient device management.
- In particular, decouple device performance from the rest of the system.
Provide secure access to devices.
- Some devices can be shared, some can't

Device Abstraction

The layers of abstraction are: device, controller, driver, manager.
The device driver has a device on one end and an abstraction on the other.
One (Unix-based) trend is to abstractions that are like files.
- Each device is handled with the same file-like API: open(), close(), read(), write() and so on.
- Or each device can be treated like a file (Plan-9 based).
The device manager infrastructure ties together device classes.
- Printers look like networks look like disks look like...
- Or not, if performance or control is important.
A device manager has three interfaces.
- A device-dependent interface facing the device.
- A device-independent interface facing the rest of the system.
- A OS-specific interface for device management.

Device Performance

Concurrent execution is the principle means to good device performance.
- Wise use of the device is the second-most important performance principle.
Sequential (non-concurrent) execution slows the computation to the devices's speed.
```
std::cin >> x
std::cout << f(x)
```
Concurrent execution allows device operations and computation to proceed at the same time (with true concurrency, usually).
- There are two cases to consider:
  - Process P₁ issues a device request, and process P₂ executes concurrently with P₁'s request.
    - P₁ usually can't do anything without its data.
    - This is known as blocking or synchronous IO.
  - Process P₁ issues a device request, and and then continues executing concurrently with its request.
    - Sometimes P₁ can do other things while waiting for data.
    - This is known as non-blocking or asynchronous IO.
Implementation details.
- Inter-process device concurrency requires scheduler help.
  - Device requests result in the requester being context switched.
  - The context switch can be voluntary or pre-emptive (which is safer).
- Intra-process device concurrency requires scheduler help and a different device abstraction.
  - The scheduler should not block requesting processes, and should show affinity for other threads in the same process.
  - The device abstraction should allow for status-testing and synchronization operations.
    - Status testing determines when the device is done.
    - Synchronization reverts to inter-process device concurrency.
      io_op rid = read(fid, buffer, n); while not op_done(rid) and more work do_some_work() wait_for_op(rid); f(buffer, n);

Device Management Strategies

Device characteristics determine effective management strategies.
- The two major characteristics device-storage communication and device-to-CPU communication.
- Other characteristics, such as CPU-to-device communication, have influence, but are not as important.
A device having Direct Memory Access (or DMA) can read and write main storage.
- This is done with DMA hardware.
- Storage regions are delimited with command parameters.
A device having direct I-O can only access its own control and data registers.
- The CPU movings data between the device registers and other storage locations.
A device with interrupts can communicate directly with the CPU.
A device without interrupts communicates indirectly with the CPU via device-status registers.
- These are known as polling devices because of the CPU behavior required to interact with them.
Data movement strategies.
- DMA management is simple: load the proper parameters and set the device to work.
- Direct I-O management is about as simple: the CPU must move data unit-by-unit to or from the device.
- Direct I-O management is much more expensive than is DMA management.
Control strategies.
- Interrupt management is simple: run the proper interrupt-handling code.
- Polled management is about as simple: peroidically poll the device to test its status.
  - This is much harder without hardware timer support.
- Polled management is much more expensive than is interrupt-driven management.
Both DMA and interrupt hardware increase a system's monitary cost.

Device Manager Design

The device manager implements the device abstraction, which includes working the device.
Devices are brought out to processes in the system-call interface.
- Each device (or device class) may have its own set of system calls, or all devices have the same set.
- The OS calls the internal interface directly.

Each system-call set has a device interface table describing the internal system-call procedures.

struct device_table {
  status (* open)(char * name, int mode, int & did)
  status (* close)(int did)
  status (* read)(int did, char * buff, int size);
  status (* write)(int did, char * buff, int size);
  }

Each device manager implements a specific set of procedures for the device table.

status tty_open(char * name, int mode, int & did) { ... }
status tty_close(int did) { ... }
status tty_read(int did, char * buff, int size) { ... }
status tty_write(int did, char * buff, int size) { ... }

device_table tty_device_table = {
  tty_open, 
  tty_close,
  tty_read, 
  tty_write
  }

The OS-side of a system call maps to the apropriate device table and makes the apropriate call.

General Device Management Strategy

Receive device system call, context switch into the OS.
Enqueue (if the device is busy) or issue the request.
Release (for asynchronous operations) or block the requestor.
Context switch back to user processes.
Peroidically poll (timeout interrupt) or be triggered by the device interrupt, context switching to the associated handler.
Finish servicing the request and notify (for asynchronous operations) or unblock the requestor.
Deque the next pending request, if any, and issue it.
Context switch back to user processes.

Buffering

Buffering decouples data producers from data consumers.
- Without buffering, data producers and consumers must be ready at exactly the same time.
- Compare broadcast media with pre-recorded media (buffered data) or recording devices (data buffering).
Decoupling enables
- Economy of scale, amortizing the same work over more data.
- Concurrency of producer and consumer.
- Smoothing rates of production and consumption.
Buffers occur throughout the system, in devices (controllers), in drivers, in the OS, and in the user procsses.
- However, too much buffering is bad for performance because data copies are expensive, particularly across protection boundries.
Buffering techniques.
- Double buffering places two buffers between the producer and consumer.
  - Concurrently one buffer is filled, the other emptied.
  - Switch when both buffers are exhausted of data or free space.
  - Provides concurrency and (to some extent) rate matching.
- Multiple buffering.
  - Double buffering is ineffective with much faster producers, or many more producers than consumers.
    - Too much waiting for empty buffers.
  - This is a problem that can't be outrun: buffers are a finite resource, producers are effectively infinite.
  - However, adding extra buffers may help ease the wait.
    - Statistical properties tell the tale.
  - Linear buffering maintains a (usually fifo) queue of full buffers.
    - The queue length is usually bounded, but is adjustable.
    - A full queue blocks producers, or causes them to fail.
  - Circular buffering maintains a ring of empty and full buffers.
    - No free buffers may block the producer, or overwrite oldest data.

This page last modified on 14 November 2004.