I/O Systems

A Simple Model

Device Properties

I/O Devices can be classified according to six properties:

Transfer mode:
char (terminal)
block (disk)
Access method:
sequential (modem)
random (CD-ROM)
Scheduling method:
synchronous (tape)
asynchronous (keyboard)
Sharing:
dedicated (tape)
sharable (keyboard)
I/O Direction:
read only (CD ROM)
write only (graphics monitor)
read/write (disk)
Speed

A UML Model

Applications work with interfaces

Character-Oriented Devices

Block-Oriented Devices

A Java Model

We can model a character device as an array of bytes:

class CharDevice {
final static int EOF = 128;
byte stream[] = new byte[EOF];
int nextByte = 0;
int direction = 0; // 0 = input, 1 = output
boolean sharable = true;
boolean randomAccess = false;
boolean blocking = true;
}

A block device can be represented as an array of blocks, where a block is an array of bytes:

class BlockDevice {
final static int BLOCK_SIZE = 128;
final static int NUM_BLOCKS = 32;
byte[][] blocks = new byte[NUM_BLOCKS][BLOCK_SIZE];
int nextBlock = 0;
int direction = 0; // 0 = input, 1 = output
boolean sharable = true;
boolean randomAccess = false;
boolean blocking = true;
}

Interfaces

Input Devices

interface IBlockInputDevice {
int read(byte[] block);
int seek(int num);
void reset();
void open();
}

interface ICharInputDevice {
int read(byte b);
int seek(int num);
void reset();
void open();
}

OutputDevices

interface IBlockOutputDevice {
int write(byte[] block);
void open();
}

interface ICharOutputDevice {
int write(byte b);
void open();
}

Implementations

A driver for an output block device

class OutputBlockDeviceDriver implements IBlockOutputDevice {
private BlockDevice device = new BlockDevice();
private int unsafeWrite(byte[] block) {
if (device.direction != 1) return 0;
if (device.NUM_BLOCKS <= device.nextBlock) return 0;
if (device.BLOCK_SIZE < block.length) return 0;
byte[] next = device.blocks[device.nextBlock++];
int count = 0;
for(;count < block.length; count++) {
next[count] = block[count];
}
return count;
}
public void open() {
if (device.sharable) {
device.direction = 1;
device.nextBlock = 0;
} else {
synchronized(this) {
device.direction = 1;
device.nextBlock = 0;
}
}
reset();
}

public int write(byte[] block) {
if (device.sharable) return unsafeWrite(block);
synchronized(this) { return unsafeWrite(block); }
}
}

A driver for an output character device

class OutputCharDeviceDriver implements ICharOutputDevice {
private CharDevice device = new CharDevice();
private int unsafeWrite(byte b) {
if (device.direction != 1) return 0;
if (device.EOF <= device.nextByte) return 0;
device.stream[device.nextByte++] = b;
return 1;
}
public int write(byte b) {
if (device.sharable) return unsafeWrite(b);
synchronized(this) { return unsafeWrite(b); }
}
public void open() {
if (device.sharable) {
device.direction = 1;
device.nextByte = 0;
} else {
synchronized(this) {
device.direction = 1;
device.nextByte = 0;
}
}
}
}

A driver for an input block device

class InputBlockDeviceDriver implements IBlockInputDevice {

private BlockDevice device = new BlockDevice();

private int unsafeRead(byte[] block) {
if (device.direction != 0) return -1;
if (device.NUM_BLOCKS <= device.nextBlock) return -1;
if (block.length < device.BLOCK_SIZE) return -1;
byte[] next = device.blocks[device.nextBlock++];
int count = 0;
for( ; count < block.length; count++) {
block[count] = next[count];
}
return count;
}

public int read(byte[] block) {
if (device.sharable) return unsafeRead(block);
synchronized(this) {
return unsafeRead(block);
}
}

public void reset() {
if (device.sharable) {
device.nextBlock = 0;
return;
}
synchronized(this) {
device.nextBlock = 0;
}
}

public int seek(int n) {
int pos = n + device.nextBlock;
if (!device.randomAccess) return -1;
if (device.NUM_BLOCKS <= pos) return -1;
if (device.sharable) {
device.nextBlock = pos;
} else {
synchronized(this) { device.nextBlock = pos; }
}
return pos;
}

public void open() {
if (device.sharable) {
device.direction = 0;
} else {
synchronized(this) { device.direction = 0; }
}
reset();
}
}

A driver for an input character device

class InputCharDeviceDriver implements ICharInputDevice {

private CharDevice device = new CharDevice();

private int unsafeRead() {
if (device.direction != 0) return -1;
if (device.EOF <= device.nextByte) return -1;
return device.stream[device.nextByte++];
}

public int read(byte[] block) {
if (device.sharable) return unsafeRead();
synchronized(this) {
return unsafeRead();
}
}

public void reset() {
if (device.sharable) {
device.nextByte = 0;
return;
}
synchronized(this) {
device.nextByte = 0;
}
}

public int seek(int n) {
int pos = n + device.nextByte;
if (!device.randomAccess) return -1;
if (device.EOF <= pos) return -1;
if (device.sharable) {
device.nextByte = pos;
} else {
synchronized(this) { device.nextByte = pos; }
}
return pos;
}

public void open() {
if (device.sharable) {
device.direction = 0;
} else {
synchronized(this) { device.direction = 0; }
}
reset();
}
}

The Driver-Controller Interface

At a lower level, device (controllers) can be classified as PIO devices or DMA devices.

Programmed I/O (PIO)

A PIO device is passive. It depends on the CPU to transfer bytes. There are two techniques: polling and vector interrupt.

Polling

The driver polls the controller's busy flag using a busy-wait loop:

class InputCharDeviceDriver implements ICharInputDevice {

private CharDevice device = new CharDevice();

private int read() {
while(device.busy); // wait
// my turn:
device.command = device.READ;
while(device.status != device.READY); // wait
return device.nextByte;
}

// etc.
}

The device produces and consumes bytes:

class CharDevice extends Thread {
// commands:
static final int READ = 0;
static final int WRITE = 1;
static final int OPEN = 2;
static final int RESET = 3;
int command;
// status:
boolean busy = false;
boolean ready = false;
// data register:
byte nextByte = 0;
public void run() {
while(true) {
switch(command) {
case READ:
ready = false;
Thread.sleep(1000); // simulate read time
nextByte = ???;
ready = true;
break;
// etc.
}
}
}
}

Interrupt-Driven I/O

An I/O device raises an interrupt by asserting an interrupt. The CPU catches the interrupt and dispatches to the interrupt handler. The handler clears the interrupt by servicing the device.

Assume memory is modeled by a giant array of bytes:

int[] memory;

Here's a high-level model of the CPU's fetch-execute cycle:

class CPU {
static boolean interrupt = false;
static int vector; // index into dispatch table
static int[] dispatch; // interrupt handlers
static int instruction; // next instruction to execute
static int ip = 0; // instruction pointer;
static int sp = 0; // stack pointer
static void fetchExecute() {
while(true) {
if (interrupt) {
interrupt = false;
memory[sp++] = ip; // save ip
ip = dispatch[vector]; // goto handler
}
instruction = memory(ip++);
execute(instruction);
}
}
}

Direct memory Access (DMA Controllers)

1. CPU places a DMA command block in memory, signals the DMA controller, then resumes its work.

2. The DMA then begins the transfer of data from the device to memory.

To do this the DMA must steal bus cycles from the CPU, but doesn't slow the CPU down as much as programmed I/O.

Streams

The stream I/O model (STREAMS) was introduced by UNIX System V. A stream is a message queue/pipe (or a pair of message queues/pipes) that connects an application to a device driver:

In fact, a stream is a pipeline of filters:

Filters are reusable and can be combined in different ways to produce streams with different functionalities. Examples of filter functionalities include:

Buffering

Error Detection

Byte to Data conversion

Encryption/Decryption

Compression/Inflation

Progress monitoring

unread/unwrite

File Systems

A file system is a high level API the OS provides to mass storage devices such as disks. A file system is a collection of objects called files.

A file is basically a stream of bytes or characters. A pointer marks the current byte being read or written.

A file manager manages provides secure access to the files.

A directory is a file of files, or rather a file of references to files.

Here's a rough Java model:

class File {
private byte[] stream;
private int pos = 0;
private String name;
private int id; // handle
private int type; // .doc, .txt, etc.
private int mode; // 0 = input, 1 = output
private int protection; // = 0755, etc.
private User owner; // = "Fred"
private Date lastModified;

public byte write() throws EOFException {
if (data.length < pos) throw new EOFException();
return stream[pos++];
}
public void read(byte b) {
if (data.length < pos) throw new EOFException();
stream[pos++] = b;
}
public void open(int mode) {
this.mode = mode;
}
public void seek(int n) {
pos += n;
}
}

A file manager maintains a table of open files:

class FileManager {
private Map openFiles = new HashMap();
private Map files = new HashMap();
public int open(String fname) {
File f = (File)files.get(fname);
openFiles.put(f.getID(), f);
}
public byte read(int id) {
File f = openFiles.get(id);
if (f != null) return f.read();
}
// etc.
}