LEC 9 Device Drivers

主题：设备驱动程序

• CPU需要外部设备：存储、通信等
• 操作系统负责设备的编程
• 新问题/复杂性：
  • 设备通常有刚性且复杂的接口
  • 设备和CPU并行运行
  • 中断
    • 硬件需要立即注意！
    • 软件必须放下当前工作并响应
    • 在RISC-V上使用与系统调用和异常相同的陷阱机制

编程设备：内存映射I/O

• 设备控制器具有地址范围
• load/store访问这些地址读/写控制寄存器
• 平台设计者决定设备在物理内存空间中的位置

例子设备：UART

内核设备驱动程序如何使用这些寄存器？

• 简单示例：kernel/uart.c中的uartgetc()
• ReadReg(RHR)变成*(char*)(0x10000000 + 0)

设备驱动程序等待的方式？

• 可能是“忙等待”：

  while((LSR & 1) == 0)
    ;
  return RHR;
  

• 如果等待不太可能发生，这是可以接受的 - 如果输入几乎总是可用
• 因此，对于控制台来说是不可接受的！
• 通常在FIFO中没有等待（按键输入）
• 大多数设备都是这样的 - 可能需要等待很长时间才能进行I/O

解决方案：中断

• 当设备需要驱动程序关注时，设备发出中断
• UART在以下情况下中断：
  • rx FIFO由空变为非空，或
  • tx FIFO由满变为非满

内核如何看到中断？

• 设备 -> PLIC -> 陷阱 -> usertrap()/kerneltrap() -> devintr()
• trap.c devintr()
• scause高位指示陷阱是来自设备中断
• PLIC寄存器指示哪个设备中断
  • "IRQ" -- UART的IRQ是10

中断通常只是设备状态可能已更改的提示

• 真相在设备的状态寄存器中
• 设备驱动程序必须检查它们以决定如何行动（如果有的话）
• 对于UART，检查LSR以查看rx FIFO是否非空，tx FIFO是否非满
• uart.c uartintr()

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);
}

典型的设备驱动程序结构

• 顶半部：
  • 执行进程的系统调用，例如write()或read()
  • 启动I/O，会发生等待
• 底半部：
  • 中断处理程序
  • 从/发送设备硬件读取输入或输出
  • 需要与“顶半部”进程进行交互
    • 将输入放在顶半部可以找到的地方
    • 告诉它更多的输入已到达
    • 或者可以发送更多的输出
  • 不在顶半部进程的上下文中运行
    • 可能在不同的核上
    • 可能中断其他一些进程

让我们看看xv6如何设置中断机制

控制中断的寄存器

• sie
  • 每个软件中断、外部中断、定时器中断一个位
• UART IER
• PLIC claim --- 获取下一个IRQ；确认IRQ
• sstatus --- S-mode状态寄存器，SIE位启用中断

xv6的中断设置代码

• start()：

  w_sie(r_sie() | SIE_SEIE | SIE_STIE | SIE_SSIE);
  

• main()：

  consoleinit();
    uartinit()
  plicinit();
  scheduler();
    intr_on();
       w_sstatus(r_sstatus() | SSTATUS_SIE);
  

让我们看看从控制台/UART读取输入的shell

• % make qemu-gdb
• % gdb

(gdb) c

• (gdb) break sys_read
• (gdb) c
• (gdb) tui enable
• sys_read()
  • fileread()
    • consoleread()
      • 这是顶半部
      • 查看cons.buf、cons.r、cons.w - "生产者/消费者缓冲区"
      • sleep()

现在是底半部

• (gdb) break kerneltrap
• (gdb) c
• <按回车键>
• 我们是如何到达这里的？
  • (gdb) where
  • 在内核中；没有进程想要运行；scheduler()
  • UART -> PLIC -> stvec -> kernelvec

kernelvec.S

• kernelvec类似于跳板，但用于内核陷阱
  • 更简单：堆栈有效，页表已经是内核了
  • 因此可以将寄存器保存在堆栈上，跳转到kerneltrap
• 在当前堆栈上保存寄存器；哪个堆栈？
  • 在这种情况下，是特殊的调度程序堆栈
  • 如果在内核中执行系统调用，某个进程的堆栈

kerneltrap()

• devintr()
  • (gdb) p/x $scause
  • scause高位表示陷阱来自设备中断
    • 在riscv手册的第85页 / 表4.2中
  • plic_claim()找到IRQ（哪个设备）
  • (gdb) p irq
  • uartintr()
    • uartgetc()
    • x/1bx 0x10000005
    • 检查LSR以获取rx，从RHR复制到缓冲区，唤醒
    • consoleintr()
      • 打印cons
      • 打印cons.buf[cons.r]
      • wakeup()
      • x/1bx 0x10000005 -- 注意低位不再设置
    • plic_complete(irq)
  • 通过devintr、kerneltrap、kernelvec返回
  • (gdb) b *0x80005b92 -- kernelvec的结尾
  • ...
  • 调度程序现在将运行顶半部 -- sh的read()
    • 因为唤醒了
    • 让我们在顶半部中断 -- consoleread()
    • (gdb) b console.c:99
    • (gdb) c
    • (gdb) where
    • consoleread()的sleep()返回
    • consoleread()看到我们在cons.buf[cons.r]中的字符
    • sh的read()返回，带有我键入的字符

如果多个设备希望同时中断会怎么样？

• PLIC在核之间分发中断
  • 中断可以在不同核上并行处理
• 如果没有CPU claim中断，中断将保持挂起
  • 最终每个中断都被传递到某个CPU

如果内核在设备请求中断时禁用了中断会怎么样？

• 通过在sstatus中清除SIE，使用intr_off()
• PLIC/CPU记住待处理的中断
• 在内核重新启用中断时传递

// disable device interrupts
static inline void
intr_off()
{
  w_sstatus(r_sstatus() & ~SSTATUS_SIE);
}

中断涉及几种并发形式

1. 设备和CPU之间
   • 生产者/消费者并行性
2. 如果启用，中断可能发生在任何两条指令之间！
   • 在代码必须是原子的时候禁用中断
3. 中断可能在与顶半部并行运行的不同CPU上运行

中断的演进：

• 中断曾经在CPU周期中是廉价的；现在它们需要许多周期。
  • 由于流水线、大型寄存器集、缓存缺失等原因，中断开销约为一微秒，不包括实际设备驱动程序代码！
• 因此：
  • 旧的方法：简单的硬件，智能的软件，大量中断
  • 新的方法：智能硬件，在每个中断中执行大量工作

如果中断频率非常高呢？

• 例如：现代以太网每秒可传递数百万个数据包。
• 在这种情况下，CPU时间的大部分都用于中断开销。

轮询：一种高频事件通知策略

• Top-half 循环去pull，直到设备准备好
• 或者在一些频繁执行的内核代码中检查，例如：scheduler()
• 然后处理自上次轮询以来累积的所有内容
• 如果设备通常很快准备好，比中断更有效
• 可能根据测得的速率切换策略

DMA（直接内存访问）可以有效地传输数据

• xv6 uart驱动程序以软件逐字节读取字节
  • 对于低速设备，CPU效率不高：离芯片远，不可缓存，每次8位
• 但对于低速设备来说还可以
• 大多数设备会自动将输入复制到RAM -- DMA
  • 然后中断
  • 输入已经在内存中
  • CPU内存操作通常更加高效

LEC 10 Lock

1. 为什么要谈论锁？

   • 应用程序希望利用多核处理器以实现并行加速。
   • 内核必须处理并行系统调用以及对内核数据的并行访问
   • 锁有助于正确共享数据，但可能限制并行加速。

2. 锁的抽象：

   • 锁是一个对象，有acquire和release两个操作。
   • 锁不一定专门与某个数据关联，由程序员计划数据和锁的对应关系。

3. 何时需要锁：

   • 当两个线程使用内存位置，且至少有一个是写入时。
   • 持有正确的锁再触碰共享数据。

4. 锁是否可以自动处理？

   • 考虑语言是否能够将锁与每个数据对象关联起来。
   • 编译器在每次使用周围自动添加acquire/release，减少程序员的遗漏。
   • 通常这个想法太死板，因为程序员通常需要对锁的持有时间进行显式控制。

if present(table1, key1):
      add(table2, key1)

race:

• another thread may remove key1 from table1
• before this thread gets a chance to add to table2
  我们需要:

      lock table1
      lock table2
        present(..)
    add()
      unlock table1; unlock table2

6. 锁的作用：
   • 避免丢失更新。
   • 实现原子多步操作，隐藏中间状态。
   • 帮助操作维护数据结构的不变性。

8. 锁与模块化

   • 锁使得隐藏模块内部细节变得困难。（防止死锁）
   • 为了避免死锁，需要知道调用的函数获取的锁。

9. 锁与并行性

   • 锁阻止并行执行，需要以允许每个核使用不同数据和不同锁的方式划分数据和锁。
   • 选择数据/锁的最佳划分是一个设计挑战，可能需要重构代码。

10. 锁的粒度建议

    • 从大锁开始，例如保护整个模块的一个锁。
    • 只有在必要时才进行细粒度锁设计。

11. 在xv6中看锁的典型用法

    • 以uart.c为例，典型的设备驱动布局。
    • uart_tx_lock是唯一的锁，相对较粗粒度。
    • uartputc() 和 uartintr() 的锁的作用。
    • uartputc() -- uart_tx_lock 保护什么？
      1. 在 uart_tx_buf 操作中避免race condition。
      2. 如果队列不为空，UART硬件正在执行队列头部的操作。
      3. 防止对UART写寄存器的并发访问。

12. 如何实现锁？

    • 为什么不采用如下形式：

      struct lock { int locked; }
      acquire(l) {
        while(1){
          if(l->locked == 0){ // A
            l->locked = 1;    // B
            return;
          }
        }
      }
      

    • 存在A和B之间的竞争，如何原子性地执行A和B？

13. 原子交换指令：

    • __sync_lock_test_and_set 用于执行原子交换。
    • 硬件中的原子交换保证了在操作期间不会被中断。
    • xv6中的自旋锁实现使用了这个概念。

14. 为什么使用自旋锁？

    • 自旋锁会浪费CPU
    • 自旋锁指南：持有自旋锁的时间很短，不要在持有自旋锁时放弃CPU。
    • 系统提供"阻塞"锁用于更长的临界区，等待的线程会放弃CPU，但开销较高。

15. 建议：

    • 如果不必要，不要共享数据。
    • 从少数粗粒度锁开始。
    • 仔细检查代码，了解哪些锁阻止了并行性。
    • 只在需要并行性能时才使用细粒度锁。

LEC 11 Scheduling

上下文切换

• 从一个用户进程切换到另一个涉及多个转换：
• 用户->内核；在trapframe中保存用户寄存器
• 内核线程->调度程序线程；在context中保存内核线程寄存器
• 调度程序线程->内核线程；从ctx中还原内核线程寄存器
• 内核->用户；从trapframe中还原用户寄存器

proc.h中的struct proc

• p->trapframe保存了保存的用户线程的寄存器
• p->context保存了保存的内核线程的寄存器
• p->kstack指向线程的内核栈
• p->state是RUNNING、RUNNABLE、SLEEPING等
• p->lock保护p->state（和其他item...）

为什么需要一个单独的调度程序线程？

• 以便始终有一个堆栈可以运行调度程序循环
• 例如，切换到一个正在退出的进程
• 例如，CPU少于进程

代码细节：

https://mit-public-courses-cn-translatio.gitbook.io/mit6-s081/lec11-thread-switching-robert/11.6-yield-and-sched

为什么scheduler()在内核中启用中断，使用intr_on()？

可能没有可运行的线程，它们可能都在等待I/O（例如，磁盘或控制台）。启用中断是为了让设备有机会发出完成信号，从而唤醒一个线程。否则，系统将会冻结。

为什么sched()的注释说只能持有p->lock？

• 在单核计算机上，考虑以下情况：

  P1           P2
  acq(Lx)
  sched()
                 acq(Ly)
                 acq(Lx)
  

  • P2将永远等待：
    • P2会自旋等待P1释放Lx。
    • P2持有Ly，因此必须关闭中断。
    • 没有时钟中断，因此P1不会运行。
    • 因此Lx永远不会被释放。
  • 即使在多核上，有更多的锁/线程，也可能出现这种情况。
  • 解决方案：禁止在放弃CPU时持有锁！（除了p->lock）

为什么在swtch()期间要持有p->lock？

• 这一点影响xv6中的许多情况。
• yield()和scheduler()都要在swtch()调用期间持有p->lock的两个原因：
  1. 防止另一个核心的调度程序在原始核心停止执行线程之前看到p->state == RUNNABLE。
     • 需要在原始核心停止使用线程的堆栈之后。
  2. 防止在swtch()期间调用yield()的定时器中断。
     • （记住：acquire()关闭中断）。第二次的swtch()将覆盖context中已保存的寄存器。

LEC 12 Coordination

线程经常等待特定事件或条件：

  - 等待磁盘读取完成（事件来自中断）
  - 等待管道写入者生成数据（事件来自线程）
  - 等待子进程退出

• 协调是线程编程的基本构建块，但受到可能引发难题的规则约束。

为什么不直接使用while循环自旋直到事件发生？

• 更好的解决方案是使用能够放弃CPU的协调原语。
• 有很多，例如屏障、信号量、事件队列。
• xv6使用sleep和wakeup，类似于“条件变量”。

示例：uartwrite()和uartintr()在uart.c中的使用

• UART是连接到控制台的设备硬件。
• 基本思想：
  • UART硬件一次接受一个字节的输出（实际上是几个）。
  • 写控制台的进程必须等待UART发送上一个字符。
  • UART硬件在发送每个字符后都会发生中断。
  • 写()调用uartwrite()。
    • uartwrite()写入第一个字节（如果可能）。
    • uartwrite()调用sleep()等待UART的中断。
    • uartintr()调用wakeup()。
  • &tx_chan参数用于连接sleep和wakeup。

为什么sleep()需要锁参数？

• sleep()不能简单地是“等待此事件”。
• 问题被称为“丢失唤醒”。
• 这个问题潜伏在所有序列协调方案背后，是一个痛苦的问题。

假设只是sleep(chan)，我们如何实现？

• 这里是一个错误的sleep/wakeup实现：

  broken_sleep(chan)
    // 在“通道”上休眠，一个数字/地址 用于标识我们正在等待的条件/事件
    p->state = SLEEPING;
    p->chan = chan;
    sched();
  
  broken_wakeup(chan)
    // 唤醒在chan上睡眠的所有线程
    // 可能唤醒多个线程
    for each p:
      if p->state == SLEEPING && p->chan == chan:
        p->state = RUNNABLE
  

• 我省略了p->lock，两者都需要，后面再加。

uart代码如何使用这个（错误的）sleep/wakeup？

• int busy
  int chan
  uartwrite(buf):
    for each char c:
      while busy:
        broken_sleep(&chan)
      send c
      busy = 1
  uartintr():
    busy = 0
    broken_wakeup(&chan)
  

• busy==0是我们等待的条件
• &chan是休眠通道（一个虚拟变量）

但是锁怎么办呢？

• 驱动程序的数据结构（例如busy）和UART硬件都需要锁。
• uartwrite()和uartintr()都需要锁。
• uartwrite()是否应该在整个序列中持有锁？
  • 不行：因为uartintr()无法获取锁并清除忙标志。
• uartwrite()是否应该在sleep()之前释放锁？
  • 让我们尝试一下 - 修改uart.c以调用broken_sleep()：

    release(&uart_tx_lock);
    broken_sleep(&tx_chan);
    acquire(&uart_tx_lock);
    

• make qemu ; cat README

当uartwrite()在broken_sleep()之前释放锁，会出什么错？

• uartwrite()发现前一个字符还没有完成发送。
• 在释放锁之后，发生中断，broken_sleep()之前。
• uartwrite()去休眠，即使UART TX已经完成。
• 现在没有东西可以唤醒uartwrite()，它将永远休眠，直到下一个UART中断，由于输入。

这就是“失去唤醒”的问题。

• 我们需要消除uartwrite()检查条件和sleep()标记进程为睡眠之间的窗口。
• 我们将使用锁防止在整个窗口期间运行wakeup()。
• 我们将更改sleep()接口和使用方式。
• 我们要求存在一个保护条件的锁，并要求sleep()和wakeup()的调用者都持有这个“条件锁”。

sleep(chan, lock)：调用者必须持有锁，sleep释放锁，返回前重新获取。
wakeup(chan)：调用者必须持有锁。

让我们看看proc.c中的wakeup(chan)：

• 它扫描进程表，查找SLEEPING和chan的进程。
• 它获取每个p->lock。
• 还要记住调用者在调用wakeup()之前获取了条件锁。
• 因此，wakeup()同时持有条件锁和每个p->lock。

让我们看看proc.c中的sleep()：

• sleep 必须释放条件锁，因为在调用swtch()时不能持有锁（除了p->lock）。
• 问题：如何防止在sleep()释放条件锁后运行wakeup()？
• 答案：在释放条件锁之前获取p->lock。
  • 因为wakeup()同时持有两个锁，sleep()只需持有其中一个，以强制wakeup()自旋而不是查看这个进程。
• 现在，wakeup()不能在swtch()完成之前进行，因此wakeup()保证能看到p->state==SLEEPING和p->chan==chan。
• 因此，没有失去唤醒！

请注意，uartwrite()在循环中包装sleep()。
即在sleep()返回后重新检查条件，可能再次休眠的两个原因：

1. 可能有多个等待者，另一个线程可能已经使用了事件。
2. kill()即使条件不成立也会唤醒进程。
   所有sleep的使用都包装在循环中，因此它们会重新检查。

另一个协调挑战 - 如何终止一个线程？

问题：线程X不能只是销毁线程Y

• 如果Y正在另一个核心上执行怎么办？
• 如果Y持有锁怎么办？
• 如果Y正在对重要数据结构进行复杂的更新怎么办？

问题：一个线程不能释放所有自己的资源

• 例如，它自己的堆栈，它仍在使用
• 例如，它的struct context，可能需要调用swtch()

xv6有两种方法来终止进程：exit()和kill()

普通情况：进程通过exit()系统调用自愿退出

• 策略：
  • exit()释放一些东西，但不释放proc slot或堆栈
  • 父母的wait()进行最后的释放
• 目标：
  • p->state = UNUSED，以便将来的fork()可以使用这个proc[]slot
• exit()在proc.c中：
  • 一些清理
  • 唤醒wait()的父母
  • p->state = ZOMBIE
    • ZOMBIE意味着准备好父母的wait()
    • 不是UNUSED - 因此不会被fork()分配
    • 不会再次运行
  • （请注意，堆栈和proc[]条目仍然被分配...）
  • swtch()到调度程序
• wait()在proc.c中（parent最终会调用）：
  • sleep()等待任何子进程退出
  • 扫描proc[]表，找到p->state==ZOMBIE的子进程
  • 调用freeproc()
    • p->lock持有
    • 释放trapframe，pagetable等，p->state=UNUSED
• 因此，wait()不仅仅是为了应用程序方便，还为了操作系统。
  • 必须对每个进程进行wait()。
  • 一些复杂性是由于
    • 先等待然后退出 或 先退出然后等待
    • parent已经退出了怎么办？

那么kill(pid)呢

• 问题：强制终止一个进程可能是不安全的
  • 它可能正在内核中执行
    • 使用它的内核堆栈、页表、proc[]条目、trapframe
  • 它可能持有锁
    • 例如，在fork()新进程的中间
    • 必须完成以恢复不变性
• 解决方案：
  • kill()设置p->killed标志，什么也不做
  • 目标进程本身检查p->killed
    • 并调用exit()自己
  • 在usertrap()中查找if(p->killed) exit(-1);
    • 在这里没有在执行中，也没有持有锁，因此安全退出

如果kill()目标正在sleep()呢？

• 在这种情况下，它既没有持有锁，也没有执行！
• kill()立即销毁目标是否可以？
  • 不行：如果在文件创建的中途等待磁盘怎么办？

xv6对kill()的解决方案

• 参见proc.c中的kill()：
  • 将SLEEPING更改为RUNNABLE - 类似于wakeup()
  • 因此，sleep()将返回，可能在条件为真之前
• 一些sleep循环检查p->killed
  • 例如，piperead()，consoleread()
  • 否则，对于已经被杀死的进程，读可能会无限期挂起
• 一些sleep循环不检查p->killed
  • 例如，virtio_disk.c
  • 不必检查p->killed，因为磁盘读取相当快
• 因此，被kill()的进程可能会继续一段时间
  • 但是usertrap()将在系统调用完成后调用exit()

xv6对kill的规范

• 如果目标在用户空间
  • 在它下次进行系统调用或接受定时器中断时会死亡
• 如果目标在内核中
  • 目标将永远不会执行另一条用户指令
  • 但在内核中可能还要花一段时间

总结

• sleep/wakeup允许线程等待特定事件
• 并发意味着我们必须担心唤醒丢失
• 终止在线程系统中是一个麻烦