7.os kernel 实现

我们已经了解并发编程实践需要的几乎全部内容——线程、内存模型、互斥、同步和并发 bugs 的应对。但我们一直是在简化的线程模型 (thread.h) 上讲解的。但我们还没有回答一个关键问题：线程到底在计算机硬件上是如何实现的？即便系统中只有一个处理器，我们依然可以创建很多并发执行的线程。

讲并发，操作系统课，并不是编程课，为什么花这么多时间讲并发编程？

我们前面都是在简化的 api 上学习的，这部分我们考虑线程库如何实现？即便系统中只有一个处理器，我们依然可以创建很多并发执行的线程。

中断的机制奠定了现代操作系统的基础。

• 多处理器与中断

• 50行实现嵌入式操作系统

线程库是怎么实现的？操作系统内核里如何实现线程。

多处理器模型

做实验的时候，有个 AbstractMachine 的框架

AbstractMachine 的实验框架，使用 am.h 里的 api 可以直接使用 C 控制计算机硬件去控制一个操作系统内核。lab 的名字是 kernel，去实现一个小的 在 bare metal 上的 操作系统。

这一切的基础，Turing Machine，图灵机模型。一个有限状态机+一条纸带

读取当前的状态，然后根据状态找到下一个状态，还可以写出去。这个效果是在无限长的纸带写出 010101 就好像编了一个程序。

计算机科学领域里有个非常重要的定理：图灵机的表达能力非常强，强到我们可以写一个图灵机的程序去模拟另外一个图灵机。

我们可以做一台图灵机，可以解释执行写在纸上的 C 程序，这些都是可以证明的。

Turing Machine: 一个处理器，一个地址空间

• “无情的执行指令的机器” (rvemu) 的抽象

• 可用的内存是静态变量和 heap

• 只能执行计算指令和 putch, halt

(模拟器，指令的模拟执行)

risc-v 的模拟器，无情的执行指令的机器。从手册 reset 规定好的地方开始，不断执行。有限状态机上有个状态是停机，有个有意思的问题：halting problem，即能否写一个程序，这个程序可以输入另外一个程序，会不会在有限步内终止。这是个不可判定问题，即无法用图灵机解决。

这个简单的 risc-v 的指令模拟器，绝大多数指令都是计算指令

多处理器就不一样了，多个处理器的 mpe 功能，AbstractMachine 每个处理器类似一个线程，多个处理器共享一个地址空间，状态机模型也发生了一点变化。

• 状态：共享内存和每个处理器的内部状态 $(M,R_1,\cdots, R_n)$

• 多处理器上，机器是不确定的执行指令的机器

• 状态迁移：处理器 t 分隔出一个 “单处理器计算机”

任一时刻，我们可以让其中一个处理器带着内存往前走一步。这就让状态机变得非常复杂，也变得不符合直觉了。

简易的多处理器内核(L1 的模型)，和多线程程序一致，同步通过原子指令实现

uint8_t shm[MEM_SIZE]; // Shared memory

void Tprocessor() {
  struct cpu_state s;
  while (1) {
    fetch_decode_exec(&s, shm);
  }
}

int main() {
  for (int i = 0; i < NPROC; i++) {
    create(Tprocessor);
  }

代码模拟的简易的多处理器系统模型容易理解，但同时也有缺陷：它上似乎没办法运行任何 “正经” 的操作系统：如果任何处理器上的应用程序死循环，那么这个处理器就彻底 “卡死” 了。而使真正得我们的线程可以 “逃出” 死循环的核心机制，就是操作系统管理的硬件中断。

中断机制

如果模拟的这个简易处理器，一旦某个 CPU 运行了死循环，直接卡死，这个 CPU 就和消失一样。

这和我们的直觉不同，为什么我们写 C 程序，while(1) 为什么不会卡死 CPU 呢？

为此，我们需要引入 CPU 的一个重要机制：中断。

8086 里有中断，我们如何理解中断这个行为呢。

中断在硬件上就是一根信号线。边沿触发或者低电平触发

面包板上搭 74 处理器的电路，手作的乐趣，是写 verilog 感受不到的。

中断告诉 CPU 有事情来了，不管你在干什么，都停下来。停下来以后的行为，由处理器确定。

实际的处理器并不是 “无情地执行指令”

• 无情的执行指令

• 同时有情地响应外部的打断

每个指令周期的结束都会检测中断信号。

中断有两个脚，$\overline{INTR}$ 和 $\overline{NMI}$ 不可屏蔽中断。

中断发生了，应该干什么，即中断的响应

• 首先检查处理器配置是否允许中断(相关寄存器的配置)

  • 如果处理器关闭中断，则忽略(IF=1)

• x86 Family

  • 询问中断控制器获得中断号 n

  • 保存 CS, RIP, RFLAGS, SS, RSP 到堆栈

  • 跳转到 IDT[n] 指定的地址，并设置处理器状态 (例如关闭中断)

• RISC-V (M-Mode)

  • 检查 mie 是否屏蔽此次中断

  • 跳转 PC = (mtvec & ~0xf)

  • 更新 mcause.Interrupt = 1

跳转这个行为以为着不正常。中断响应 x86 做的多一点，有点像强行插入了一个函数跳转，这个地址是我们可以设置的，即此函数可以任意实现。RISC-V 流程基本上也相差不大。

教科书到此为止了。如果想更深入，需要去写能执行的代码，即实现一个模拟器。

struct MiniRV32IMAState {
  uint32_t regs[32], pc;
  uint32_t mstatus;
  uint32_t cyclel, cycleh;
  uint32_t timerl, timerh, timermatchl, timermatchh;
  uint32_t mscratch, mtvec, mie, mip;
  uint32_t mepc, mtval, mcause;
  // Note: only a few bits are used.  (Machine = 3, User = 0)
  // Bits 0..1 = privilege.
  // Bit 2 = WFI (Wait for interrupt)
  // Bit 3+ = Load/Store reservation LSBs.
  uint32_t extraflags;
};

这个 CPU 有 32 个 32 bit 寄存器，一个 pc 寄存器，以及一段其它寄存器，以及一个死循环，模拟一步指令执行，以及最主要的，中断。这个简单模拟器里关于中断的代码就十几行，有助于对中断的理解。

中断是奠定操作系统“霸主地位”的机制，操作系统具有中断的完整控制权，随意开关，然而应用程序做不到，这就意味着即使是死循环也可以被中断打断，然后操作系统的代码就开始执行了。

如果想强行在用户程序里关中断会怎么样呢？

int main()
{
    asm volatile("cli");
}

会报一个段错误。x86 在保护模式下，应用程序执行了非法操作，也会触发一个中断告知操作系统，然后报错。

框架代码里的中断 api，

bool cte_init(Context *(*handler)(Event ev, Context *ctx));
bool ienabled(void);
void iset(bool enable);

检查是否开了中断，然后提供了一个设置中断函数的 api。这使得我们使用框架代码学习操作系统的时候不需要写汇编语言了。

每当中断发生的时候，就跳转到了框架代码执行，在 cte_init 传入了事件原因，然后还保存了上下文。操作系统最早的并发性就来自于并发，如中断处理中访问了共享数据，所有有些教科书上会说关闭中断就能实现互斥。单处理器系统上，关了中断永远也不会和别人并发，就可以安全的把一个数据结构做完操作，然后打开中断。这也是 MCU 上跑的 RTOS 实现互斥的方式。

• 最早操作系统的并发性就是来自于中断 (而不是多处理器)

• 关闭中断就能实现互斥

  • 系统中只有一个处理器，永远不会被打断

  • 关中断实现了 “stop the world”

一个真正的计算机系统模型，不仅仅有多处理器，还有中断，每个 CPU 都可以中断。数据竞争到处都有可能发生。

理解了中断，结合前面，就有了一个有趣的挑战，如何实现一个中断安全的自旋锁？

这个事情没那么简单，中断和多处理器是两个并发来源。

AA 型的死锁，哪怕我们在 lock 的时候关中断，unlock 的时候开中断，也有可能会有问题。

50 行代码实现操作系统内核

中断还能来做什么呢？框架代码里的 API

Context *handler(Event ev, Context *ctx) {
  ...
}

一个参数是 Event ev 告诉是什么类型的中断，还有个 Context *ctx ，来研究这个参数。

一个程序执行流，往前走，突然来了个中断，不管我们执行了什么代码，中断程序是可以任意修改寄存器的，即原来代码里放在寄存器里的东西会被破坏。

所以框架代码需要考虑这个事情并妥善处理，所以框架代码干了更多的事情。

如何让被中断的代码回到原来的状态去执行？即要保存原来的状态，中断发生的时候保存，返回的时候，handler 就返回了需要恢复的寄存器的数据所在的地址。

这是一个非常小心的操作，每恢复一个寄存器，这个寄存器就不能再用了，所以这部分代码是操作系统里很有趣，也很精巧的代码，即上下文切换的代码。

x86-64 下的 Context

#ifndef ARCH_H__
#define ARCH_H__

struct Context{
  void      *cr3;
  uint64_t  rax, rbx, rcx, rdx,
            rbp, rsi, rdi,
            r8, r9, r10, r11,
            r12, r13, r14, r15,
            rip, cs, rflags,
            rsp, ss, rsp0;
}

#define GPR1 rdi
#define GPR2 rsi
#define GPR3 rdx
#define GPR4 rcx
#define GPRx rax

#endif

一些比较特殊的寄存器 rip,

程序的状态，一个程序要可以运行起来，关键的地方 rip 此程序的代码，rsp 指向此程序的栈，这些都是程序独有的，实打实存在的内存，如何在只有一个 CPU 的情况下，放两个程序执行？

只要把两个程序的代码，数据、堆栈，都放到内存里。当然对于线程来说代码和数据是共享的，堆栈独享。

只要把两个线程的寄存器都放在内存里，中断的时候，把需要的数据般上去。

所以在中断处理程序开始执行时，所有可以被执行的线程，所有的内存、寄存器都在内存里，所有的线程看起来一样，随便把那个线程的寄存器往 CPU 上一贴，这个线程就开始执行了。

这就是现代操作系统实现分时的方法。

这就是上下文切换，状态机在执行……

• 发生了中断

  • 操作系统代码开始执行

  • 状态机被 “封存”

  • 我们可以用代码 “切换” 到另一个状态机

• 中断返回另一个状态机的状态

  • “封存” 的状态还在

  • 下次可以被恢复到处理器上执行

看代码，我们如何表示一个线程？线程就是一个数据结构，这个数据结构的定义

typedef union task {
  struct {
    const char *name;
    union task *next;
    void      (*entry)(void *);
    Context    *context;
  };
  uint8_t stack[8192];
} Task;  // A "state machine"

定义了名字、下一个线程、入口、以及私有的一个栈，整个数据结构 8kb，正好栈还是往数据头的方向在增长。

现在的 RTOS 都是这么设计的，可以直接去看看现在正在用的，跑在单核 MCU 上的 RTOS 内核，可以实际的调试一块板子上的东西，更好玩。

比在 unbuntu 用 abstract machine 更有感觉。

当然这是个一通百通的事情，原理就是这么个原理，具体实现各有不同，研究通一个再看类似的也会很容易。

当然这个地方是个难点。在做了 “状态机” 和 “并发” 足够的铺垫后，我们终于回到了机器指令 (状态机) 和操作系统内核了。本次课回答了为什么 while (1) 不会把操作系统 “卡死”：

• 在操作系统代码切换到应用程序执行时，操作系统内核会打开中断

• “不可信任” 的应用程序定期会收到时钟中断被打断，且应用程序无权配置中断

• 操作系统接管中断后，可以切换到另一个程序执行

要更深入的理解，还是得去读代码，这个过程必不可少，毕竟学习理论最终也是为了能更容易理解代码在干什么。

某种意义上讲，CPU 是一个状态机的容器，并不在意执行那段代码，操作系统把状态机放在 CPU 这个容器上，状态机就开始往前走了。