Unit 2a – I/O Devices, Interrupts and DMA

Beyond CPU and Memory

• Memory Bus

  • Data/control path connecting CPU, main memory, and I/O Bus
  • Also called Front Side Bus

• I/O Bus

  • Data/control path connecting Memory Bus and I/O Controllers
  • E.g., PCI

• I/O Controller

  • A processor running software (firmware) for one type of device
  • Connects I/O Device to I/O Bus
  • E.g., SCSI, SATA, Ethernet

• I/O Device

  • I/O mechanism that generates or consumes data
  • E.g., disk, radio, keyboard, mouse

I/O Controller Communication

• I/O-mapped memory

  • Addresses beyond end of main memory
  • Ranges assigned to each controller
  • Configured at boot time

• Programmed I/O (PIO)

  • CPU transfers a word at a time to/from IO Controller
  • Standard load/store instructions to I/O-mapped memory

PIO Limitations

• Controller/device is much slower than cpu

  • CPU transfers one word at a time
  • Reading/writing large amounts of data slows CPU
  • CPU is mostly waiting for controller

• I/O Controller cannot initiate communication

  • Sometimes CPU asks for data

  • Sometimes controller receives data for the CPU

    • Example: incoming network packet, mouse click, keyboard press

  • CPU must request data, but data may not be available

  • Option: polling

Polling

• In CPU:

 
xxxxxxxxxx
9
1
int pollDeviceForValue() {
2
  volatile int *ready = 0x80000100;
3
  volatile int *value = 0x80000104;
4
  int v;
5
  while (!*ready) {}
6
  v = *value;
7
  *ready = 0;
8
  return v;
9
}

• In I/O Controller:

 
xxxxxxxxxx
7
1
int readyValueForCPUPoll(int v) {
2
  volatile int *ready = 0x80000100;
3
  volatile int *value = 0x80000104;
4
  while (*ready) {}
5
  *value = v;
6
  *ready = 1;
7
}

Polling Drawbacks

• Reading (or writing) I/O memory is slow

• Polling is ok if:

  • Poll has low overhead
  • High probability of "hit"

• CPU and controllers are independent processors

  • They should be permitted to work in parallel
  • Either should be able to initiate data transfer to/from memory
  • Either should be able to signal the other to get attention

Autonomous Controller Operation

• Direct Memory Access (DMA)

  • Controller can send/read data from/to any main memory address
  • CPU is oblivious to these transfers
  • DMA addresses and sizes are programmed by CPU using PIO

• CPU Interrupts

  • Controller can signal the CPU when data is available

  • CPU checks for interrupts on every cycle

    • Very fast, clock-speed poll

  • CPU jumps to controller's Interrupt Service Routine if its interrupting

Implementing Interrupts to Simple CPU

• New special-purpose CPU registers

  • isDeviceInterrupting: set by I/O controller to signal interrupt
  • interruptControllerID: set by I/O controller to identify device
  • interruptVectorBase: interrupt-handler jump table, initialized at boot time

• Modified fetch-execute cycle

  • Before fetching, check if a device is interrupting
  • If so, save current address in stack and call interrupt handler

Fetch-Execute with Interrupt

• Fetch-execute cycle:

 
xxxxxxxxxx
8
1
while(true) {
2
  if(isDeviceInterrupting) {
3
    r[5] <- r[5] - 4; m[r[5]] <- r[6]; r[6] <- PC;
4
    PC <- interruptVectorBase[interruptControllerID];
5
  }
6
  fetch();
7
  execute();
8
}

• RTI (Return From Interrupt) instruction:

 
xxxxxxxxxx
2
1
t <- r[6]; r[6] <- m[r[5]]; r[5] <- r[5] + 4;
2
isDeviceInterrupting <- 0; PC <- t;

Interrupt Control Flow

I/O Operations: Disk Access

• Hard disk is one possible device

• Disk stores blocks of data

  • Each block has a unique number

• PIO is used to request data

  • CPU sends operation (e.g., read, write), block number, and memory address
  • Controller reads/saves data in memory address
  • CPU obtains data from memory once operation is finished

Disk Read Timeinline

• Naïve implementation

• Using interrupts

The Power of the Sequence

• Consider a program that reads data from a disk

• A read can be considered to have three parts:

  • identify what data you want
  • get the data
  • do something with the data

• These steps must happen in order (sequence)

Data Read Sequence Example

• For example:

 
xxxxxxxxxx
10
1
char checksumDiskData(int blockNum, int numBytes) {
2
  char buf[numBytes];
3
  char xsum = 0;
4
  
5
  diskRead(buf, blockNum, numBytes);
6
  for (int i = 0; i < numBytes; i++)
7
    xsum ^= buf[i];
8
  
9
  return xsum
10
}

Making Code Asyncronous

• The function will be idle while waiting for data

• We can separate the code into two parts

  • Request something

     
    xxxxxxxxxx
    2
    1
    char buf[numBytes];
    2
    diskRead(buf, blockNum, numBytes);
    

  • Handle data once request finished

     
    xxxxxxxxxx
    3
    1
    char xsum = 0;
    2
    for (int i = 0; i < numBytes; i++)
    3
      xsum ^= buf[i];
    

Writing Asynchronous Code in C

• Events are "things" that cause asynchronous code to run

  • Example: disk read completion

• Event Handlers are the code that runs when event occurs

  • Example: the code that computes the checksum

• Handlers are registered to a specific event

• Events are fired to trigger the execution of the handler

• In code:

  • Request and handler registration are usually listed together
  • Handler runs asynchronously when event occurs

Asynchronous Data Read Example

 
xxxxxxxxxx
12
1
void computeCheckSum(char *buf, int blockNum, int numBytes) {
2
  char xsum = 0;
3
  for (int i = 0; i < numBytes; i++)
4
    xsum ^= buf[i];
5
  // save checksum somewhere
6
}
7
​
8
void checksumDiskData(int blockNum, int numBytes) {
9
  char buf[numBytes];
10
  
11
  diskRead(buf, blockNum, numBytes, computeChecksum);
12
}

Implementing Disk Read (Simplified)

 
xxxxxxxxxx
39
1
#define MAX_DEVICES 16
2
void (*interruptVector [MAX_DEVICES])();
3
​
4
int diskID = 4;
5
interruptVector [diskID] = diskISR;
6
​
7
struct handler_dsc {
8
  void (*handler) (char*, int, int);
9
  char* buf;
10
  int blockNum;
11
  int numBytes;
12
}
13
​
14
int* diskAddress = (int*) 0x80001000;
15
​
16
#DEFINE DISK_OP_READ 1
17
#DEFINE DISK_OP_WRITE 2
18
​
19
struct disk_ctl {
20
  int op;
21
  char* buf;
22
  int blockNum;
23
  int numBytes;
24
}
25
​
26
void diskISR() {
27
  struct handler_dsc hd;
28
  dequeue_handler (&hd);
29
  hd.handler (hd.buf, bd.blockNum, hd.numBytes);
30
}
31
​
32
void diskRead(char* buf, int blockNum, int numBytes, void (*whenComplete) (char*, int, int)) {
33
  struct disk_ctl* dc = (struct disk_ctl*) diskAddress;
34
  enqueue_handler (whenComplete, buf, blockNum, numBytes);
35
  dc->op        = DISK_OP_READ;
36
  dc->buf       = buf;
37
  dc->blockNum  = blockNum;
38
  dc->numBytes  = numBytes;
39
}

Problems with Asyncrony

• The original version of checksumDiskData returned a char

  • This is no longer possible: function returns before its data is ready

• So we are forced to rethink our processs

• Whatever was done with return value will now need to be done after handler runs

  • It must also be triggered by the event handler
  • We want to isolate (modularize) code, so can't be something fixed

Improving Isolation, but not Readibility

 
xxxxxxxxxx
19
1
void printByte(char c) {
2
  printf("0x%1x\n", c);
3
}
4
​
5
void computeCheckSum(char* buf, int blockNum, int numBytes,
6
                     void (*whenComplete) (char)) {
7
  int xsum = 0;
8
  for (int i = 0; i < numBytes; i++)
9
    xsum ^= buf[i];
10
  whenComplete(xsum);
11
  free(buf);
12
}
13
​
14
void checksum(int blockNum, int numBytes, void (*whenComplete) (char)) {
15
  char* buf = malloc (numBytes);
16
  diskRead(buf, blockNum, numBytes, whenComplete, computeChecksum)
17
}
18
​
19
checksum(1234, 4096, printByte);

Asynchrony makes code harder to write

• Humans like synchrony

  • We expect each step of a program to complete before the next one starts
  • We use the result of previous steps as input to subsequent steps

• Computer systems are asynchronous

  • The disk controller takes 10-20 milliseconds (10^-3s) to read a block

  • CPU can execute millions of instructions while waiting for the disk to complete one read

  • we must allow the CPU to do other work while waiting for I/O completion

  • many devices send unsolicited data at unpredictable times

    • e.g., incoming network packets, mouse clicks, keyboard-key presses

• Asynchrony makes programs more difficult to write

  • and much more difficult to debug

Possible Solutions

• Some languages simplify event-driven programming

  • Observer design pattern
  • Java GUI (event handlers)
  • Javascript handles page and user events
  • CSP language: based directly on event-driven programming

• Some abstractions can provide illusion of synchrony

  • Code is listed in synchronous order, but executed on events

• Best option is still "research in progress"