简介和例子 Introduction and Examples

操作系统的目标：

  • 抽象硬件
  • 多路复用 multiplex，即同时运行多个程序
  • 隔离性
  • 不同活动共享信息
  • 安全或权限系统
  • 高性能
  • 大量不同的应用场景

分为用户空间和内核 kernel 空间，内核直接与硬件资源交互，应用程序通过系统调用 system call 来与内核交互

操作系统结构

系统调用包括了 write、open、fork 等，看起来和普通的函数调用差不多

操作系统设计的矛盾点：

  • 高效 - 抽象
  • 强大 - 简单的 API
  • 灵活 - 安全

组织和系统调用 Organization and System Calls

操作系统的隔离性和防御性

  • user/kernel mode
  • 虚拟内存

kernel mode 权限更高，能够执行一些 user mode 不允许执行的命令

每个进程都有自己的页表 page table

将程序的控制权转移到内核的指令是 ecall，其传入一个数字作为参数，表示要求的系统调用

内核有时被称为可被信任的计算空间 Trusted Computing Base，其必须将用户的进程当作是恶意的

什么代码该运行在 kernel mode？

  • 整个操作系统——宏内核 Monolithic Kernel Design
    • 绝大多数操作系统都这么做
    • 缺点：出现 bug 的概率较高
    • 优点：性能强
  • 微内核 Micro Kernel Design：运行尽可能少的代码
    • 嵌入式系统
    • 优缺点与上面的相反

页表 Page Tables

由于内存地址对应关系的表单也保存在内存中，所以需要一个寄存器来保存该表单在内存中的物理地址，这个寄存器叫 SATP

为了节省表单的空间，给出两个解决方案：

  • 4 KB 为一页
  • 三级表

虚拟地址与物理地址

对于物理地址：低于 0x80000000 的不存在 DRAM 中，而是对应其他 IO 设备

对于虚拟地址：

注意到存在 Guard page，其未被映射到某个物理地址，目的是当 kernel stack 耗尽时，会溢出到 Guard page，立刻出发 page fault，就能直到 kernel stack 出错了

隔离 & 系统调用的出入 Isolation & System Call entry/exit

用户空间和内核空间会发生在：

  • 系统调用
  • page fault，除 0 等错误
  • 中断

这种切换被称为 trap

涉及的一些寄存器：

  • 32 个通用寄存器
  • pc
  • 表示当前在 supervisor mode 还是 user mode 的标志位
  • SATP（Supervisor Address Translation and Protection）寄存器：指向 page table 的物理内存地址
  • STVEC（Supervisor Trap Vector Base Address Register）寄存器：指向内核中处理 trap 的指令的起始地址
  • SEPC（Supervisor Exception Program Counter）寄存器：在 trap 的过程中保存 pc 的值
  • SSRATCH（Supervisor Scratch Register）寄存器

整个过程需要对这些东西执行的操作：

  • 保存 32 个用户寄存器，因为这些寄存器会被内核代码使用，要防止其被弄乱
  • 保存 pc，能够继续执行程序
  • 改成 supervisor mode
  • SATP 从 user page table 指向 kernel page table
  • 堆栈寄存器指向位于内核的一个地址，因为需要一个堆栈来调用内核的 C 函数
  • 跳入内核的 C 代码

trap 机制的实现目标：

  • 只保存而不查看 32 个寄存器
  • trap 机制对用户代码透明

对于 supervisor mode 的特权，有一点值得注意：可以使用 PTE_U 标志位为 0 的 PTE，（在这里）不能使用 PTE_U = 1 的 PTE

trap代码执行流程

ecall 做的事：

  • 代码从 user mode 改到 supervisor mode
  • 将 pc 的值保存到 SEPC
  • 关中断
  • 跳转到 STVEC 寄存器指向的指令

RISC-V 的 ecall 的硬件做的事非常少，是秉持了提供灵活性的原则

内核将 trapframe page 映射到了每个 user page table，其包含了 32 个寄存器等数据，而在进入 user space 之前，内核会将 trapframe page 的地址保存在 SSCRATCH 寄存器中，配合交换两个寄存器的 csrrw 指令，实现保存另一个寄存器的值，并将自己的值加载给另一个寄存器

至于为什么要内核自己找一块地方自己来保存，是因为可能有的编程语言没有栈，或者栈的格式和寻常理解的不一样

trampoline 的代码在 user page table 中的映射与 kernel page table 中的映射完全一样，所以切换 page table 时程序不会崩溃

页错误 Page Faults

page fault 的信息：

  • 引起 page fault 的内存地址
  • 引起 page fault 的原因类型
  • 引起 page fault 时的 pc 值，这表明了 page fault 在用户空间发生的位置

Lazy page allocation：可以不立刻为程序分配物理内存

Zero Fill On Demand：在 C 语言中，定义一个大数组，其内容默认全为 0，则只需要真正分配一块物理内存

Copy On Write Fork：在子进程复制父进程的虚拟地址空间时，并不复制，而是直接引用父进程的 page，初始时全是只读的，某一方需要写的时候才分配新的内存，并修改为可读写

  • PTE 中的 RSW 可以作为 copy-on-write 的标志位
  • 对于多重引用的问题，需要另外维护一个数据结构来完成引用的计数

Demand Paging：并不加载程序内存的 text，data 区域

Memory Mapped Files：即 mmap

中断 Interrupts

中断，即硬件想要得到操作系统的关注，处理过程和系统调用类似，但有以下几点不同：

  • 异步
  • 并发
  • 程序设备

处理器上通过 Platform Level Interrupt Control (PLIC) 来处理设备中断

PLIC

当 PLIC 接收到中断请求时，

  • 通知当前有一个待处理的中断
  • 其中一个 CPU 核会 Claim 接收中断，这样 PLIC 就不会把中断发给其他的 CPU 处理
  • CPU 核处理完中断之后，CPU 会通知 PLIC
  • PLIC 将不再保存中断的信息

驱动分为两部分：bottom/top

  • bottom 部分通常是 Interrupt handler
  • top 部分是用户进程或内核的其他部分调用的接口
  • 通常有 buffer，top 和 bottom 部分会同时读写数据

硬件的编程通常通过 memory mapped I/O 实现

RISC-V 中与中断有关的寄存器：

  • **SIE（Supervisor Interrupt Enable）**寄存器：这个寄存器中有一个 bit（E）专门针对例如 UART 的外部设备的中断；有一个 bit（S）专门针对软件中断，软件中断可能由一个 CPU 核触发给另一个 CPU 核；还有一个 bit（T）专门针对定时器中断。

  • SSTATUS（Supervisor Status）寄存器：每一个 CPU 核都有独立的 SIE 和 SSTATUS 寄存器，除了通过 SIE 寄存器来单独控制特定的中断，还可以通过 SSTATUS 寄存器中的一个 bit 来控制所有的中断。

  • **SIP（Supervisor Interrupt Pending）**寄存器：当发生中断时，处理器可以通过查看这个寄存器知道当前是什么类型的中断。

UART 驱动的 top 和 bottom 部分是一个 producer-consumer 模型

对于一个快速的设备，Interrupt 机制的开销太大了，一般使用 polling。有的驱动能够在 polling 和 Interrupt 之间动态切换

线程切换 Thread Switching

多线程原因：

  • 分时复用任务
  • 程序结构简单
  • 并行运算

这里对于线程 thread 的定义是单个串行执行代码的单元

线程的状态：

  • PC
  • 寄存器
  • Stack

多线程的并行运行主要有两个策略：

  • 是在多核处理器上使用多个 CPU
  • 一个 CPU 在多个线程之间来回切换

处理运算密集型线程（compute bound thread）：利用定时器中断，将 CPU 出让（yield）给线程调度器

这种流程叫做 pre-emptive scheduling，即用户代码本身没有出让 CPU，定时器中断仍然会将 CPU 的控制权拿走，并出让给线程调度器，与之相反的是 voluntary scheduling

在实际实现中是这样的：使用 pre-emptive scheduling 将 CPU 控制权从用户进程给到内核，然后使用 voluntary scheduling 内核中用户进程对应的内核线程会代表用户进程出让 CPU

为了区分线程，线程有一些状态：

  • RUNNING，线程当前正在某个 CPU 上运行
  • RUNABLE，线程还没有在某个 CPU 上运行，但是一旦有空闲的 CPU 就可以运行
  • SLEEPING，线程在等待一些 I/O 事件，它只会在 I/O 事件发生了之后运行

线程切换如图，即从用户进程进入对应的内核进程，然后进入该 CPU 的 schedulder 函数，其找到下一个进程，切换到该进程，最后退出该内核进程到用户进程中

线程切换

注意到，这里的 context switching 指一个内核线程和调度器线程之间的切换

Sleep 和 Wake Up

在 xv6 系统的设计中，进程在调用 switch 函数的过程中，有两个限制条件：

  • 必须要持有 p->lock
  • 同时又不能持有任何其他的锁

注意到 sleep 的接口 sleep(&tx_chan, &uart_tx_lock) 中需要传入一个锁，如果改成

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

要是在注释处发生中断，则有可能出现 wakeup 在 sleep 之前被调用，即 lost wakeup

还有要注意的是 sleep 的写法：

while (tx_done == 0)
    sleep(&tx_chan, &uart_tx_lock);

即写在一个循环里面，因为有可能出现被唤醒了，但是其他人将等待的事件拿走了，而只能继续 sleep 的情况

解决 lost wakeup 的问题需要遵循一系列规则：

  • 调用 sleep 时需要持有 condition lock，这样 sleep 函数才能知道相应的锁
  • sleep 函数只有在获取到进程的锁 p->lock 之后，才能释放 condition lock
  • wakeup 需要同时持有两个锁才能查看进程

对于如何关闭一个进程，存在两大问题：

  • 不能直接单方面的摧毁另一个线程
  • 即使一个线程调用了 exit 系统调用，并且是自己决定要退出，它仍然持有了运行代码所需要的一些资源

在 exit 系统调用中，我们将进程的状态设置为 ZOMBIE，注意并没有释放资源，只是进程不再运行了

在 wait 系统调用中，父进程会找到 ZOMBIE 进程，然后释放资源

kill 系统调用基本上不做任何事情，只是设置 killed 标志位；然后在 usertrap 函数中自我检查并调用 exit

特别的，对于 SLEEPING 中的进程，通常会在循环中检测并直接退出；但是，对于等待磁盘读写的进程，又最好完成整个系统调用再退出

文件系统 File Systems

文件系统的特性：

  • 对于用户友好的路径/文件名
  • 在用户之间和进程之间共享文件
  • 持久化

背后的机制：

  • 对硬件的抽象
  • crash safety
  • 磁盘排布
  • 性能

inode 是代表一个文件的对象，通过编号区分，有一个 link count 来跟踪指向这个 inode 的文件名的数量，此外还有 openfd count。一个文件只能在这两个计数器都为 0 的时候才能被删除

文件系统组织方式

有两个术语：

  • sector 通常是磁盘驱动可以读写的最小单元，它过去通常是 512 字节
  • block 由文件系统定义，在 XV6 中它是 1024 字节

从文件系统来看，布局为：

  • block0 要么没有用，要么被用作 boot sector 来启动操作系统。
  • block1 通常被称为 super block，它描述了文件系统
  • inode：多个 inode 会打包存在一个 block 中，一个 inode 是 64 字节。
  • bitmap block：只占据一个 block，记录了数据 block 是否空闲。
  • 数据 block：存储文件和目录的内容

文件系统布局

inode 的结构：

  • type：是文件还是目录
  • nlink：即 link 计数器，用来跟踪究竟有多少文件名指向了当前的 inode
  • size
  • direct block number
  • indirect block number

inode

目录包含了多条 directory entries，每一条 entry

  • 前 2 个字节包含目录中文件或子目录的 inode 编号，
  • 后 14 个字节包含文件或子目录名

block cache：

  • 在内存中，对于一个 block 只能有一份缓存
  • 使用 sleep lock 而不是 spinlock
  • 使用 LRU 作为 cache 替换策略
  • 有两层锁：第一层锁用来保护 buffer cache 的内部数据；第二层锁用来保护单个 block 的 cache

崩溃恢复 Crash Recovery

目标是为了在发生 crash 之后仍然能够正常使用文件系统

出现文件系统无法正常使用的原因在于有多个写磁盘的操作，这些操作必须作为一个原子操作出现在磁盘上

这里给出的解决方案是 logging

  • log write：任何写操作都先写入到 log
  • commit：当文件系统的操作结束，并且都存在于 log 中，我们会 commit 文件系统的操作
  • install：将 block 从 log 分区移到文件系统分区
  • clean：清除 log

重启后 reinstall

log 最开始有一个 header block，包括：

  • n：有效的 log block 的数量
  • b：每个 log block 实际对应的 block 编号

然后是每个 block 的数据，内存中也有一份 header block 的拷贝

log结构

尽管示例的文件系统很简单，但也有几个微妙的注意点：

  • cache eviction：buffer cache 不能撤回任何还位于 log 的 block
  • 文件系统操作必须适配 log 的大小：要是一个文件系统操作写入数据超过了 log 大小，则会被分割成多个小一点的写操作，这样就失去了写操作的原子性，但至少保全了文件系统
  • 并发执行的 transaction 写入的总 log 数小于 log 区域的大小，这里的方法是通过限制并发文件系统操作的个数

文件系统性能与快速崩溃恢复 File System Performance and Fast Crash Recovery

在这里 ext3 = ext2 + journal

logging 系统需要满足的：

  • write ahead rule：需要预先在 log 中定义好所有需要具备原子性的更新，之后才能应用这些更新
  • freeing rule：直到 log 中所有的写操作被更新到文件系统之前，我们都不能释放或者重用 log

xv6 很慢的原因：系统调用对于写磁盘操作来说是同步的

ext3 维护了一些 transaction 信息，所以可以维护多个在不同阶段的 transaction 的信息，包括

  • 序列号，block 编号
  • 对应了系统调用的 handles

ext3 log结构

descriptor block 和 commit block 会以一个 32bit 的 magic number 作为起始，以同 data block 区分开

注意 log 中会有多个 transaction，但是一个时间只有一个正在进行的 transaction

ext3 提升性能的方法：

  • 异步的系统调用
  • 批量执行 batching，即将多个系统调用打包成一个 transaction
  • 并发

异步执行的优点在于能够同时进行磁盘操作和应用程序运算，缺点在于系统调用的返回并不能表示其应该完成的工作实际完成了，故会提供一个 fsync 的系统调用来同步

batching 的优点：

  • 分摊了 transaction 带来的固有的损耗
  • write absorption，即多个系统调用写了同一个 block
  • disk scheduling，即大量连续写的请求

两种 concurrency：

  • 多个系统调用同时执行
  • 多个不同状态的 transaction 同时存在

ext3 需要跟踪正在进行的系统调用个数，通过 handle 识别并记住系统调用所属的 transaction

transaction commit 步骤：

  1. 阻止新的系统调用
  2. 等待 transaction 中未完成的系统调用完成
  3. 开始一个新的 transaction
  4. 更新 descriptor block
  5. 将实际的 block 写入到 log 中
  6. 等待写 log 结束
  7. 写 commit block
  8. 等待写 commit block 结束
  9. 将 transaction 包含的 block 写入到文件系统中的实际位置
  10. 写完后，重用那些 log 空间

用户应用程序使用的虚拟内存 Virtual memory for applications

虚拟内存的特性：

  • trap：用户定义 Page Fault handler（sigaction）
  • Prot1：降低一个 Page 的 accessability（mprotect）
  • ProtN：类似于 Prot1，但是可以将成本分摊到 N 个 Page，使得操作单个 Page 的性能损耗更少（mprotect）
  • Unprot：增加一个 Page 的 accessability（mprotect）
  • Dirty：查看内存 Page 是否是 Dirty
  • map2：一段物理内存对应两份虚拟内存，注意可以有不同的 accessability（多次 mmap）

Virtual Memory Areas（VMAs）：记录一些有关连续虚拟内存地址段的信息

构建大缓存表：其实就是在 Page Fault Handler 中计算，而在外部看来，就是一张非常大的缓存表

copying GC：将对象从 from 空间复制到 to 空间

Baker's Real-Time Copying Garbage Collector：和上面类似，但是是 incremental GC，即不必停止程序一次完成，而是一步步完成

  • 应用程序调用 new 来申请内存时，扫描几个对象，并将这些对象从 from 空间 forward 到 to 空间
  • 每次获取一个指针指向的对象（dereference）时，都需要检查对象是否在 from 空间中，是的话将其从 from 空间 forward 到 to 空间

注意到有两个问题：

  • 检查指针的开销
  • 难以并发

论文中给出的方法：将空间进一步划分为 scanned 和 unscanned，将 unscanned 权限设置为 None

  • 在 Page Fault Handler 中，扫描位于内存的所有对象，将这些对象所指向的其他对象从 from 空间 forward 到 to 空间，然后该对象标记为 scanned 并恢复权限

注意到这种方法本质上是将指针检查交给硬件完成了，除此之外，同步也交给硬件完成了

还有权限问题：应用程序要求 unscanned 权限为 None，而 GC 则要求读写权限，这里使用 map2 实现

OS 架构 OS organization

微内核：进程抽象和通过 **IPC（Inter-Process Communication）**进程间通信

其余，如文件系统是通过一个用户空间进程来实现

现在微内核一般出现在微型嵌入式系统中

大量使用 IPC，故 IPC 的速度很重要

为了兼容现有的程序，该论文对 Linux 进行了一些修改，使其能够作为一个用户进程运行在 L4 上

虚拟机 Virtual Machines

**Virtual Machine Monitor（VMM）**上面是 Guest 空间，下面是 Host 空间

由于 Guest kernel 运行在 User mode，所以使用 privileged 指令会触发 trap 走回到 VMM 中，VMM 获得控制权

VMM 会为每一个 Guest 维护一套虚拟状态信息

Trap and Emulate 的实现还包括了 Page Table。VMM 会为每个虚拟机维护一个映射表，将 Guest 物理内存地址映射到真实的物理内存地址

Shadow Page Table 的地址是 VMM 向真实 SATP 寄存器写入的值，使得 Guest kernel 认为自己使用的是一个正常的 Page Table，但是实际的硬件使用的是 Shadow Page Table

对于设备，有三种策略：

  • 模拟一些设备
  • 提供虚拟设备
  • 对于真实设备的 pass-through

Intel 的 VT-x 在硬件上提供了对虚拟机的支持

**EPT（Extended Page Table）**会指向一个 Page Table，对 Guest 的地址进行第二次的翻译

Dune 能够在硬件层面支持进程同时拥有 Guest Supervisor mode 和 Guest User mode，这样进程可以在自己的 User mode 中运行未被信任的插件代码

网络 Network

packet的控制流程

曲线的下降被称为中断的 Livelock，是由于输入中断的优先级更高，使得转发 packet 的任务可能分配不到任何 CPU 时间

解决方案是关中断，唤醒处理 packet 的线程，从网卡一次拉取多个 packet 并处理，不断重复，直到网卡中没有等待处理的 packet，然后重新打开网卡中断并 sleep

实际上是在高负载时将中断模式（Interrupt Scheme）转变成了轮询模式（Polling Scheme）

Meltdown

Meltdown 涉及利用 CPU 内隐藏的实现细节，因此被称为 Micro-Architectural Attack

攻击者依赖 CPU 的两个实现技巧：预测执行和缓存

  • Intel CPU 的超前的预测执行会忽略权限将数据取出
  • 该论文发布时绝大多数操作系统为了性能，不会在内核空间和用户空间之间切换的时候更换 Page Table，所以缓存不会在切换时被刷新。因此可以通过时间来得到缓存的信息

原因类似的还有 Spectre

操作系统给出的修复方案是切换 Page Table

RCU

目标结构是一个链表，且有多个并发读，只有一个写

第一种方案是读写锁，代码：

struct rwlock {
    int n;
};

r_lock(l):
	while 1:
		x = l->n
        if x < 0
            continue
        if CAS(&l->n, x, x + 1)
            return

w_lock(l):
	while 1:
		if CAS(&l->n, 0, -1)
            return

可以注意到，问题在于每次循环都只能有一个成功，同时由于要修改计数器 l->n，导致每次都需要让其余核的缓存失效

于是出现了 RCU（Read Copy Update），通过增加写入者的负担来使读取速度加快

注意这种方法的要求是 committing write 必须是原子的，因此双向链表无法使用，但树却非常合适

有的编译器可能会重排读操作，从而导致出现问题，所以应该设置 memory barrier，强制完成之前的操作

最后一个问题在于何时释放旧对象，RCU 使用的方法是：

  • 读取者不允许在 context switch 时持有一个链表元素的指针
  • 写入者在每一个 CPU 核都执行过至少一次 context switch 之后再释放链表元素

这是简单的代码：

rcu_read_lock()
e = head
while (p) {
    e = rcu_dereference(e)
    look at e->x
    e = e->next
}
rcu_read_unlock()

acquire(lock)
old = head
e = alloc()
e->x = ...
e->next = head->next
rcu_assign_pointer(&head, e)
release(lock)

synchronized_rcu()
free(old)

RCU 是否有用取决于工作负载，通常对于读频繁的业务有一定的提升