Qifan Wang
The Jungle Book
A blog for programming

MIT 6.S081 Lecture 9: Interrupts

There is some good in this world, and it’s worth fighting for.

6.S081第九课，课程教授中断的处理机制，并开始引入生产者/消费者模型与并发的概念。

Interrupts

中断的本质是硬件需要关注，如网络包到达，时钟中断等，软件需要放下当前工作及时回应。 RISC-V 架构使用与 syscall 和 exceptions 相同的 trap 机制处理中断。但中断带来一些新的议题，

  1. asynchronous 异步。中断会打断正在运行的进程，并且中断处理程序 interrupt handler 可能没有运行在引发中断的进程上下文。
  2. concurrency 并发。进程和设备需要并行运行。
  3. programming devices 编程设备。需要为不同设备编写 driver 驱动。

Where do device interrupts come from?

中断可以分为外部中断与内部中断。

PLIC: Platform-level interrupt controller 负责路由外部设备的中断，例如来自键盘，硬盘的中断。

CLIC: Core-local interrupt controller 负责管理每个 Core 与 Core 之间的中断，例如时钟中断。

Qemu 使用 UART(Universal asynchronous receiver/transmitter) 向控制台展示文本，可以将 UART 看作一种端口。内核中的驱动通过编程硬件完成工作（需要读硬件手册，例如读手册了解UART哪个寄存器用于读写等）。一般 interrupt handler 会调用驱动，其他方法也是可能的如轮询。驱动常见的范式是分为两部分，各自负责读与写。

RISC-V负责中断相关的寄存器，部分之前介绍过（同 trap ），这里简单列表，

reg name description
sie supervisor interrupt enabled register, one bit per software interrupt, external interrupt, timer interrupt
sstatus supervisor status register, one bit to enable interrupts
sip supervisor interrupt pending register
scause supervisor cause register
stvec supervisor trap vector register
mdeleg machine delegate register

寄存器 sie 中，有 external interrupts enable(SEIE)，timer interrupts enable(STIE)，和 internal interrupts enable(SSIE)。这三个位负责 enable 三种中断（时钟其实也可看作一种特殊的内部中断）。

寄存器 sstatus 的 SIE 位负责开启关闭中断。例如，

  • intr_on(): w_sstatus(r_sstatus() | SSTATUS_SIE);
  • intr_off(): w_sstatus(r_sstatus() & ~SSTATUS_SIE);

Case study: console output and keyboard input

课程通过 $ ls 举例，详细解读了控制台输出与键盘输入的xv6代码。

console output

通过绑定控制台到文件描述符，Unix将控制台设备当作文件。

Printing "$"
  shell is started with fd 0, 1, 2 for "console"
    setup by init
    Unix presents console device as a file!

需要输出字符时，print系函数最终用到系统调用向设备文件写字符，

  printf()
    putc()
      write(2, "$", 1)

实现上，函数 filewrite 通过文件类型是设备，找到对应的驱动程序函数位置，在这里是 consolewrite 函数。

  sys_write()
    filewrite() 
      consolewrite()

驱动的 uartputc 将字符送达 UART’s send FIFO 区，指示驱动可以消费 FIFO 区里的字符。

    uartputc()
	  add "$" to buffer
	  uartstart()   
    // return to user space ...
	// while at the same time UART is sending character to console

keyboard input

键盘键入字符时，启动中断，进入驱动程序函数，从 UART’s receive FIFO 读入字符。这个过程可以伴随 echo 回显，将字符再送到 console 相关区域。

具体看，外部设备中断后，PLIC将一个中断转发给CPU，CPU陷入的机制同之前的 syscall/exception 一样，不是 usertrap 就是 kerneltrap 。判断陷入类型是中断后，在 kernel/trap.c 的 devintr 函数判断中断类型，

// check if it's an external interrupt or software interrupt,
// and handle it.
// returns 2 if timer interrupt,
// 1 if other device,
// 0 if not recognized.
int devintr();

以键盘这种外设中断为例子，函数 devintr 在判断中断类型来自外设后，根据 IRQ (interrupt request) 判断设备类型。硬件平台会把每个设备定义一个 IRQ ，比如在 Qemu 里 UART0 的 IRQ 为 10 。不同硬件平台，即使是相同种类设备也可能定义不同。

if((scause & 0x8000000000000000L) &&
     (scause & 0xff) == 9){
    // this is a supervisor external interrupt, via PLIC.

    // irq indicates which device interrupted.
    int irq = plic_claim();

    if(irq == UART0_IRQ){
      uartintr();
    } else if(irq == VIRTIO0_IRQ){
      virtio_disk_intr();
    } else if(irq){
      printf("unexpected interrupt irq=%d\n", irq);
    }

    // the PLIC allows each device to raise at most one
    // interrupt at a time; tell the PLIC the device is
    // now allowed to interrupt again.
    if(irq)
      plic_complete(irq);

    return 1;
  }

函数 uartintr 处理中断，同时处理可能的输入以及输出，

// handle a uart interrupt, raised because input has
// arrived, or the uart is ready for more output, or
// both. called from trap.c.
void
uartintr(void)
{
  // read and process incoming characters.
  while(1){
    int c = uartgetc();
    if(c == -1)
      break;
    consoleintr(c);
  }

  // send buffered characters.
  acquire(&uart_tx_lock);
  uartstart();
  release(&uart_tx_lock);
}

What if several interrupts arrive?

当有多个外部中断，PLIC 负责给CPUs转发。多核平台可以同时有多个CPU并行处理中断。如果暂时没有CPU负责中断，中断请求将 pending ，最终将有CPU处理。

Concurrency

中断带来了并发。

  1. Between device and CPU. 在设备与CPU并行时，需要引入一些并发模型，如生产者/消费者模型，在 UART 处理键盘输入时，设备是生产者，CPU是消费者；但在处理输出时，则反之。
  2. Interrupt may interrupt the CPU that is returning to shell (still in kernel). 所以需要在陷入时关闭中断，保证代码原子性。
  3. Interrupt may run on different CPU in parallel with shell (or returning to shell). 多个 CPU 同时处理中断，并行化需要锁来保证一致性。

Producer/consumer parallelism

以输出为例子， shell进程是生产者，外设是消费者。驱动提供一个 buffer (一般设计成循环队列) 用于解耦。 top-half 将字符放入 buffer ，在满队列时等待，一般运行在 calling process 的上下文（主动调用进入内核），而 bottom half 将队列中的字符移除，写特定寄存器输出，可能不在 calling process 的上下文中（这两部分可能在不同CPU上并行，所以需要锁）。

以键盘读入为例子，外设是生产者，用户进程是消费者。还是有一个 buffer 解耦。

用户需要读入时，

$ 
  shell is in read system call to get input from console
    usertrap() for system call
      w_stvec((uint64)kernelvec);
      consoleread()
        sleep()
	  scheduler()
	    intr_on()

用户键入键盘字符引发中断，

$ l
  user hits l, which causes UART interrupt

在中断后，进入 kerneltrap 生产字符于 buffer 并唤醒消费者，最后通过 sret 回到 scheduler loop 中，由 scheduler 运行 shell 消费字符。

kernelvec:
  save space on current stack;  which stack?
    save registers on the current stack
    in our example, the scheduler thread's stack
  kerneltrap()
    devintr()
      uartintr()
        c = uartgetc()
        consoleintr(c)
	  handle ctrl characters
	  echo character ('l') using uartput_sync()
	  put c in buffer
  	  wakeup reader
    return from devintr()
  return from kerneltrap()
  load registers back
  sret

Interrupt evolution

中断曾经相对较快，现在偏慢。

  • old approach 每一个 event 引发一次中断，硬件很简单，软件很容易处理。
  • new approach 硬件在中断前完成许多工作。

现在很多设备生成中断事件快于 one per microsecond ，例如 gigabit 以太网可以每秒传递 1.5 million 的包。中断花费开销为 microsecond 级别。

Polling: another way of interacting with devices

处理器可以保持 spin 直到设备需要关注，比如 consoleread 不 sleep 而是一直 spin 进行请求。如 Xv6 的 uartputc_sync 函数如此实现。

  • Pro: inexpensive if device is fast. No saving of registers etc. If events are always waiting, no need to keep alerting the software.
  • Con: Wastes processor cycles if device is slow

对于高速设备， Polling 要优于中断。但对于低速设备，如键盘，中断更好，轮询反而会浪费 CPU 时间。所以 OS 可以为不同速度的设备，在两种方式间切换。

DMA(direct memory access)

UART驱动程序通过读UART控制寄存器检索数据字节；此模式称为 programmed I/O，因为软件推动数据移动。 Programmed I/O很简单，但太慢，无法以高数据速率使用。需要高速移动大量数据的设备通常使用直接内存访问（DMA）。DMA设备硬件直接将传入的数据写入RAM，并从RAM读取传出数据。

现代磁盘和网络设备一般使用DMA。DMA设备的驱动程序将在RAM中准备数据，然后使用一次写入控制寄存器来告诉设备处理准备好的数据。

UART驱动程序首先将传入的数据复制到内核中的缓冲区，然后再复制到用户空间。这在低数据速率下是有意义的，但这种双重拷贝会显著降低生成或消耗数据非常快的设备的性能。一些操作系统能够直接在用户空间缓冲区和设备硬件之间移动数据，这通常使用DMA实现。

Safety

设备中断要求系统在有限时间内回应，对于一些安全相关的系统错过 deadline 时间会导致灾难。xv6 并不适合这种硬实时设置。一个硬实时OS将提供许多库与应用链接，允许实现最坏情况回应时间的分析。但 xv6 也不是软实时系统，软实时系统在错过 deadline 时通常可以接受。因为 Xv6 的 scheduler 过于简单且 kernel code path 会长时间关闭中断。从此，我们可以学习真正在有限时间回应的OS需要，

  • hard 库与应用链接，分析最坏时间。
  • soft 精细的调度机制与较短的关闭中断的 kernel code path 。

Conclusion

这一节课教授中断。从中断的处理，我们可以看到OS与硬件的紧密性很大程度体现在驱动上，学习到关于硬件中断陷入的流程（Case study of $ ls），了解中断带来的并发问题（设备与CPU，内核重入，多CPU中断），多种与设备交互的方式（中断，轮询与DMA）。仔细审视这些问题，可以看到所谓的 ACID (Atomic, Consistent, Isolated & Durable) 可以体现在多实体的交互上。陷入内核关闭中断保证内核一部分指令原子化，设计并发模型保持 buffer 读写的一致性，用户态与内核态的隔离，响应超时需要保证的持久性等。这本质上也是OSTEP里说的虚拟化（I），并发(AC)与持久化(D)。

Reference

  1. MIT 6.S081 2021
  2. Video

Table of Contents