MIT 6.S081 OS_Notes

文章发布时间:

最后更新时间:

文章总字数:
6.2k

预计阅读时间:
22 分钟

课程文字稿见 MIT 6.s081

让我看看!

Lec3 ~ 10

本文记录Lec3~10的内容。包含虚拟内存,陷入机制和线程锁。文本使用AI润色注意。

lec3 os organization and syscall(操作系统的组织结构与系统调用)

操作系统需要对危险操作和普通操作进行隔离,为此设计了两种状态:内核态(Kernel Mode)和用户态(User Mode)。用户态的程序通过系统调用(System Call)进入内核态以完成危险操作。

假设没有操作系统,程序直接访问硬件,那么将无法实现调度功能,也无法防止恶意程序(例如陷入死循环的程序),此外,内存中的数据将无法得到保护,容易被随意读取或覆盖。因此,操作系统必须实现隔离功能。

操作系统还应具备防御性,确保自身不会轻易崩溃。简而言之,xv6 操作系统通过内核模式和虚拟内存(Virtual Memory)这两种设计,在硬件层面实现了强大的隔离机制。

当用户态程序执行了危险操作时,若某个受保护的位(bit)标记当前状态(0 表示内核态,1 表示用户态),操作系统将介入并杀死该程序。除了用户态和内核态外,RISC-V 架构还有一个机器模式(Machine Mode),用于启动机器。用户态程序只能通过系统调用进入内核态,而系统调用会触发软中断(Software Interrupt),通过查询中断表进而运行对应的中断处理程序,从而实现从用户态(1)到内核态(0)的切换。

实际上,ecall 指令接收一个数字,该数字代表用户想要调用的系统调用编号,进而执行相应的操作。所有的系统调用都从这里进入内核。

此外,通过硬件定时器,每隔一段时间就会将控制权从用户程序切换到操作系统,以便进行 CPU 调度等操作。

虚拟内存

每个应用程序都应只能看到自身内部的数据。通过使用页表(Page Table)对每个程序的内存进行管理,每个程序都有自己的页表,并且它们都从地址 0 开始,或许能增长到 MAXVA(最大虚拟地址)。

xv6 采用宏内核(Monolithic Kernel)设计。

xv6 源码

xv6 源码包含三个部分:kernel(内核)、user(用户态程序)、mkfs(用于创建一个空文件系统)。编译过程如下:使用 gcc 将 *.c 文件编译为 *.asm 文件,然后通过汇编器将 *.asm 文件编译为 *.o 文件,最后由链接器(Loader)收集所有 *.o 文件并链接生成内核文件,该文件可在 QEMU 中运行。

gdb 调试

可以使用 make CPUS=1 qemu-gdb 启动 QEMU 内的 gdb 服务器,在另一个终端启动 gdb 客户端并连接(gdb-multiarch -x .gdbinit,但不同环境下的效果可能有所不同)。xv6 的启动地址为 0x80000000,在此地址加载内核。文件 kernel.ld 定义了内核的加载方式。xv6 从 entry.s 开始启动,此时没有内存分页,也没有隔离性,并且运行在机器模式(M-mode)。xv6 会尽快跳转到内核模式(Kernel Mode)或监督模式(Supervisor Mode)。我们可以在 main 函数处设置断点,main 函数已经运行在监督模式下了。为了同时查看源码与汇编代码,在 gdb 中输入 layout split

main() 函数进行了一系列初始化操作:

  • kinit :设置好页表分配器(Page Allocator)。
  • kvminit :设置好虚拟内存,这部分内容将在下节课详细介绍。
  • kvminithart :打开页表,相关内容也将在下节课讲解。
  • processinit :设置好初始进程,或者说设置好进程列表。
  • trapinit/trapinithart :设置好用户态与内核态之间的转换代码。
  • plicinit/plicinithart :设置好中断控制器(PLIC,Platform Level Interrupt Controller),我们将在后续介绍中断时详细讲解这一部分,它是我们与磁盘和控制台进行交互的方式。
  • binit :分配缓冲区缓存(Buffer Cache)。
  • iinit :初始化 inode 缓存。
  • fileinit :初始化文件系统。
  • virtio_disk_init :初始化磁盘。
  • userinit :当所有设置都完成后,操作系统开始运行,并通过 userinit 函数启动第一个进程。接下来,我们具体看一下 userinit 函数的操作。

在 gdb 中输入 s 进入 userinit 函数内部。第一个用户程序将负责与内核交互,其定义在 initcode 中,对应的含义可以在 initcode.S 文件中查阅。简单来说,该程序相当于执行 exec(init, argv) 操作,其中的 li a7, SYS_exec 将 exec 系统调用号(位于 syscall.h 文件中)传入 a7 寄存器,等待系统调用执行。

查看 init 程序,它配置好了控制台(console),调用了 fork 函数,并在子进程中通过 exec("sh", argv) 启动 shell。

lec4 page tables(页表)

每个程序所能看到的内存都从地址 0 开始,无论进行何种读写操作,都只能修改自身拥有的内存。然而,物理内存实际上是有限的,而虚拟内存近乎无限。操作系统需要能够优雅地处理物理内存耗尽的情况。最灵活的方法就是使用页表。

对于任何带有地址的指令,都应将其地址解释为虚拟地址(VA,Virtual Address),通过硬件内存管理单元(MMU,Memory Management Unit)将其翻译为物理地址(PA,Physical Address),然后再去内存中访问数据。通常,内存中的某个地址会存储 VA-PA 的对应关系,该地址会被保存在 SATP 寄存器(Supervisor Address Translation and Protection Register)中。当程序切换时,SATP 也会一同切换。

已知 VA 和 PA 是一一对应的,假设寄存器为 64 位,那么 VA 的数量可达 2^64 个,内存将因存储如此多的对应关系而耗尽(2^10 = 1Gb)。因此,并不是为每个 VA 都记录一条 PA,而是将多个 VA 集合成一个页(Page),一个页的大小为 4096B。即每 4096 个地址空间为 1 页,页内偏移(Offset)可以用 12 位二进制数表示。页表则只记录每个页的起始位置。

在 RISC-V 架构中,寄存器虽然是 64 位的,但实际上地址只使用了低 39 位,因此,虚拟内存空间大约是 2^39=512GB。一个 VA 的低 12 位用于表示页内偏移量(2^12 = 4096),中间 27 位用于页表索引(Index)。PA 则使用 56 位,这 56 位中的高 44 位是物理页号(PPN,Physical Page Number),剩下的 12 位将与 VA 的 offset 组合,完成最终的寻址。

即使有了这样的页表,单个程序仍需要存储 2^27 个条目,这是不可接受的。因此,我们并不采用这种单一的页表结构,而是将页表设计为一个多级结构,每 9bit 用于对下级页表进行索引。

索引流程如下:收到一个 VA 后,将其按 9bit 分割为 L2、L1、L0 和 12bit 的 offset。SATP 寄存器指向一个二级页表(Page Directory),在其中根据 L2 索引找到对应的 PPN,此 PPN 指向下一级页表的位置;在下一级页表中根据 L1 索引找到对应的 PPN,该 PPN 指向下一级页表的地址;再根据 L0 索引找到最终的 PPN,将此 PPN 与 VA 的 offset 拼接,得到正确的 PA。

页目录(Page Directory)中的值并非单纯的 PPN,而是一个复合的 64bit 条目,称为页表项(PTE,Page Table Entry)。PTE 的结构如下:PTE = EXT(可扩展区域) + PPN + FLAGs(标志位)。下图展示了 PTE 低 10 位的 flag 功能,例如 Access、Global、User、Executable、Readable、Valid。当 VA 的 index 查询到写标记为非法时,说明该 VA 不可写。

1
2
3
// 页表项结构示意
| 63 54 | 53 28 | 27 19 | 18 10 | 9 |8|7|6|5|4|3|2|1|0|
| Reserved | PPN[2] | PPN[1] | PPN[0] |保留|D|A|G|U|X|W|R|V|

为什么要采用这样的三级索引结构呢?它通过只在需要时才分配物理页,从而降低了内存占用。

页表缓存(TLB,Translation Lookaside Buffer)可以省去三次寻址的时间,直接从 VA 得到 PA。切换程序时,TLB 会一同改变。在 RISCV 中,清空 TLB 的指令是 sfence_vma。xv6 中的 walk 函数实现了类似 MMU 硬件的功能。

内核页表

首先看一下 VA 中的内核页表分布:从 0x0 到 0x8000 0000-1 是 IO 设备,内核从 KERNBASE(0x8000 0000,由硬件决定)开始,到 PHYSTOP 结束。PA 的理论最大值为 2^56-1,但实际的硬件可能没有搭载那么多 DRAM 内存,所以高于 PHYSTOP 的 PA 实际上被标记为未使用(Unused)。

VA 和 PA 稍有不同,PHYHTSTOP 以上的地址到最高位 MAXVA 间的地址通过映射放到物理内存中。这里有 Trampoline(跳板)、guardpage(隔离保护页,其 valid 标记为非法,当 stack 的 VA 溢出至此时会触发 page fault,物理内存上不会为其分配内存)、Kstack0(0 号内核栈)、guardpage、Kstack1 等。

对于教学用的 xv6,IO、KERNBASE、PHYSTOP 都采用了直接映射,即 VA 等于 PA。同时,页表记录了各个位置内存的权限,如 RWX 等。例如,kernel data 段的权限为 RW,不可执行,以防止代码伪装成数据被执行。

每个用户进程都有自己的内核栈。

Lec5

请阅读 RISCV-calling.pdf 文档。

RISC-V 寄存器

在实践编程中,通常使用 ABI(Application Binary Interface,应用程序二进制接口)名称。例如:ra(return address,返回地址)、sp(stack pointer,栈指针)、gp(global pointer,全局指针)、tp(thread pointer,线程指针)。

a0-a7 是专用参数寄存器,超出的参数必须通过内存传递。单个返回值使用 a0。

caller saved(调用者保存)的寄存器可能会被覆盖。例如,ra 寄存器属于 caller saved 类型。当 funcA 调用 funcB 时,ra 的值会被覆盖为 funcA 的地址。

栈(Stack)

栈是重要的概念,但相关内容可能更偏向计算机组成原理课程。

结构体(Struct)

结构体在内存中是一段连续的地址,类似于一个由不同数据类型组成的数组。在 gdb 下,可以使用 p *structName 的方式打印出结构体的具体内容。

Lec6 Trap(异常)

请阅读第 4 章(除了 4.6 节);阅读 RISC-V.h;阅读 trampoline.S;阅读 trap.c

触发系统调用(syscall)、引发内核恐慌(panic,如除零错误、page fault 等),或者设备触发中断,都会通过 trap 机制陷入内核,从而实现用户态与内核态之间的转换。

在转换过程中,需要保存正在执行的用户进程的 32 个寄存器状态,然后切换到内核的数值。以下是一些关键寄存器:

  • 硬件寄存器 :程序计数器(PC,Program Counter Register)。
  • 模式标志位(Mode Flag) :该标志位表明当前是监督模式(supervisor mode)还是用户模式(user mode)。
  • 控制 CPU 工作方式的寄存器 :例如 SATP(Supervisor Address Translation and Protection)寄存器,它指向 page table 的物理内存地址(详见 4.3 节)。
  • STVEC(Supervisor Trap Vector Base Address Register) :该寄存器指向内核中处理 trap 的指令的起始地址。
  • SEPC(Supervisor Exception Program Counter) :在 trap 过程中,该寄存器保存程序计数器的值。
  • SSRATCH(Supervisor Scratch Register) :这也是一个非常重要的寄存器(详见 6.5 节)。

在 trap 刚开始时,我们仍处于用户态,需要保存用户寄存器状态、PC 值,切换到内核态,修改 SATP 寄存器从指向用户页表变为指向内核页表,并将栈指针寄存器切换到内核的某个地址(以便稍后在内核中运行 C 程序)。完成上述操作后,进入内核。

出于隔离性和安全性的考虑,我们不能信任用户的数据和指令。因此,XV6 的 trap 机制不会依赖这 32 个寄存器,而是将它们全部保存起来,以确保用户态的寄存器状态不会对内核造成不可预测的影响。

模式寄存器(Mode Register)用于表明当前是用户态还是内核态。

当调用 write() 函数时,汇编代码会调用 ECALL 指令切换到内核。内核执行的第一个指令来自 trampoline.S 文件中的 uservec,然后转入 usertrap() 函数(位于 trap.c 文件中)。

调用链如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
ECALL->uservec # trampoline.asm -> trap.c
->
usertrap() {
syscall() {
sys_write() {
return
}
usertrapret() {
userret # trap.c -> trampoline.asm
// 至此返回用户态
}
}
}

在 Lec6 中,从 6.3 节开始介绍 gdb 的启动方法。

ECALL 指令不会切换页表,因此第一个内核代码将在用户页表中执行。也就是说,它会映射到 trampoline page,而 STVEC 寄存器会指向那里。

ECALL 作为一条 CPU 指令,主要完成了以下三件事:

  1. 从用户模式切换到监督模式(内核模式)。
  2. 将用户程序的 PC 值存入 SEPC 寄存器。
  3. 跳转到 STVEC 寄存器所指向的指令地址。

在 RISC-V 架构中,ECALL 指令的设计尽量减少了不必要的操作,仅完成了上述必要的工作。

在调用链中,程序现在位于 trampoline 的 uservec() 起点。

当机器进入内核态时,页表仍然是用户页表,这显得有些尴尬。为了能够顺利找到内核地址,我们预先为每个用户页表添加了一个固定的跳板(trapframe page)。trapframe page 的地址会被存入 sscratch 寄存器。然后,sscratch 寄存器与 a0 寄存器交换值,以保护 a0 的原始值。根据 trapframe 内进程 proc 记录的内核地址进入内核,并将该地址加载到 SATP 寄存器中,从而进入 usertrap 函数执行内核代码。

在进入 usertrap 后,STVEC 寄存器指向 kernelvec(内核 trap 处理程序)。SCAUSE 寄存器会记录触发 trap 的系统调用号。在检查进程是否被杀死后,若进程未被杀死,则执行系统调用。系统调用执行完毕后,应使程序继续执行下一条指令,即 PC + 4 的位置。需要注意的是,中断在 trap 过程中会被关闭。对于一些耗时较长的系统调用,我们需要显式地打开中断,然后进入 syscall() 函数,读取 trapframe->a7 作为系统调用号,a0、a1、a2 作为参数。完成系统调用后,将返回值存入 a0 寄存器,最后调用 usertrapret 函数返回用户态。

Lec7 Q&A for lab(实验室答疑)

Pass

Lec8 Page Fault(缺页异常)

XV6 将 page fault 功能的实现留作实验室任务。

当触发缺页异常时,需要以下三个重要信息:

  1. 触发时的地址(需要为其分配内存)。
  2. 触发的原因(SCAUSE 值,例如是 load 操作还是 store 操作)。
  3. 触发的指令的地址(用于恢复指令执行)。

来看一下 sbrk(int k) 这个系统调用。它将扩展堆(heap)的大小(p->sz)为 k 字节(若接收负数,则压缩堆)。XV6 采用的 sbrk 设计是立即分配 k 字节内存。然而,程序往往倾向于申请更多的内存,这存在浪费现象。因此,我们考虑采用延迟分配(lazy allocation)的方式。

当调用 sbrk 时,仅修改 p->sz 的值,而不立即分配物理内存。这样,程序可以访问大于 sz 的地址空间,但那些地址对应的物理内存仍然是无效的(invalid),因此会抛出缺页异常。此时,调用缺页处理程序为其分配内存(kalloc),完成后重新执行该处指令。

不过,延迟分配也存在问题。当物理内存实际已满载时,再增加 p->sz 的值也毫无意义,此时实际的操作系统很可能会杀死该进程。

以下是一个实际的例子:将 sys_sbrk() 中分配内存的代码注释掉,仅修改 p->sz 的值。当使用 shell 执行 echo 命令时,会得到一个 not mapped panic 错误。这是因为 shell 在子进程中执行 exec 时会为其申请内存,从而触发了错误。出错时,XV6 会输出 scause(错误原因)、pid(进程 ID)、sepc(异常发生时的程序计数器值)、stval(触发异常的指令中的虚拟地址)等信息。其中,scause 的值为 15,表示 store page fault(存储页错误)。

查看 trap.c 文件,在 Lec6 中,我们因 scause == 8 而进入 trap 处理。现在,若 scause 不等于 8,则检查是否有设备中断,若无则杀死进程。我们需要添加一个 scause == 15 的情况。如果 sz > stval,则说明应该为该地址分配物理内存。需要注意的是,unmap 操作会试图释放 sz 中的所有内存,即使某些内存尚未实际分配,这会导致 not mapped panic 错误。为此,可以将 unmap 的 panic 改为 continue,以跳过错误处理。

对于未初始化和初始化为零的变量,它们会被映射到一个全零的页。该页可读但不可写。当程序使用这些变量时,会将其重新映射为可读可写的页表项(PTE),并指向新的物理页。

写时复制(copy-on-write)是操作系统中常见的优化方法。当 fork 一个子进程时,父子进程均指向相同的内存,但这些内存区域被标记为只读。一旦子进程试图写入这些内存区域,就会触发 page fault,进而触发分页操作,为子进程分配新的物理页。那么,当程序结束时,如何判断是否可以安全释放某块物理内存呢?可以采用类似文件系统中 unlink 的 “引用计数” 方法:每次释放一个虚拟页时,将其对应的物理页的引用计数减一。当引用计数为零时,才释放该物理页。

接下来介绍 “按需分页”(Demand Paging):操作系统仅为 text 和 data 分配好地址段(并标记某些区域可以读取),但并不立即分配实际的物理内存。只有当访问这些地址触发缺页异常时,才为其分配物理内存。如果内存已满,需要丢弃一些页。如何选择要丢弃的页呢?

这里有一个比喻:内存就像一个大餐盘,供人们取用披萨。不断有新的披萨饼上桌,多余的披萨需要被处理掉。优先处理掉那些最久没有人吃过的披萨,以及那些没有被加过料的披萨。因为加料比制作空披萨更费时间。

优先释放未被写过的页和长时间未被访问的页。可以通过定期(例如每 100ms)将访问位(access bit)清零,并利用 dirty bit(脏位)进行参考。

Memory mapped files(内存映射文件):将文件内容读入内存,修改后的数据在 unmap 时写回磁盘。

Lec9 Interrupt(中断)

请阅读第五章,以及 kernel/kernelvec.splic.cconsole.cuart.cprintf.c 等文件。

如果你使用 top 命令查看,会发现程序本身占用的内存其实并不多。但我们不希望内存过于空闲,因此会将大量的缓冲区(buffer)和缓存(cache)填充到内存中。VIRT 表示虚拟地址空间的大小,而 RES 表示实际使用的内存数量,通常 RES 远小于 VIRT。

当中断发生时,例如网卡接收到数据包(package)或者键盘接收到输入,会触发中断,交由操作系统处理。需要注意的是,中断的发生可能与当前正在运行的 CPU 进程没有任何关联,它是异步的。CPU 和触发中断的设备是并行工作的,需要通过编程进行处理。网卡、键盘、UART(通用异步收发器,用于收发数据的硬件)等设备发起的中断会通过 PLIC(Platform Level Interrupt Controller,平台级中断控制器)发送到 CPU。

看一下 console 中的 $ 提示符,以及 ls 命令的输出是如何显示出来的。

查看 uart.c 文件,管理设备的代码称为驱动(Driver),存放在内核中。大部分驱动分为 top 和 bottom 两端:bottom 部分基本是中断处理程序,被 CPU 调用;top 部分向用户提供更高级别的调用接口。

例如,将数据写入设备的缓冲区,用户通过 top 部分的 read 函数读取数据。就像管道的两端。缓冲区及其对应的地址被映射在内存中,以便于读取,这种方式称为内存映射 I/O(Memory-mapped I/O)。

设备将字符传给 uart 设备,经过其内部寄存器后,通过中断发送到 console。键盘的工作原理类似。uart 会将 bit 数据合并成 Byte,然后触发中断发送到处理器。这个过程需要一些硬件的配合。

以下是与中断处理相关的寄存器:

  • SIE(Supervisor Interrupt Enable) :有专门的位记录硬件中断、软件中断和定时器中断是否被使能。
  • sstatus :记录是否开启中断。
  • sip(Supervisor Interrupt Pending) :中断发生时,处理器通过此寄存器获取当前中断的类型。
  • stvec :保存进程 trap 和中断发生时的向量地址,中断处理结束后恢复进程。

查看 start.c 文件。

Lec10 多线程和锁

单 CPU 的性能增长趋势逐渐放缓,因此通过使用多核来增强系统的整体性能。然而,当多个 CPU 同时试图读取同一个地址时,可能会出现读取到错误数据的情况。因此,需要使用锁(Lock)对关键数据进行保护。当一个 CPU 锁定某个数据时,其他 CPU 不能对该数据进行操作,从而避免出现竞态条件(Race Condition)。

通过 acquirerelease 函数来获取或释放一个锁。上锁操作必须是一个原子(Atomic)指令,不可被分割。也就是说,一旦 acquire 操作开始执行,那么在被打断前一定会执行完毕。

被锁保护的代码区域称为 “临界区”(Critical Section)。临界区的特性是:要么完整执行,要么完全不执行,不会被其他 CPU 打断或交错执行。

操作系统通常会使用多把锁而不是一把大锁。这是因为如果使用一把大锁,那么所有系统调用都得排队执行,完全没有并行性可言。而多把锁可以让不同的系统调用能够同时执行,从而提高系统的整体效率。程序员必须自行决定哪些数据结构需要锁保护,以及在代码的什么位置进行加锁和解锁操作。

那么,什么时候应该使用锁呢?一般来说,当两个进程需要访问同一个数据,并且其中有一个进程要修改该数据时,就需要使用锁。然而,这个规则有些宽松。例如,printf 函数虽然没有共享数据,但也需要加锁,否则输出的内容可能会交错混合。在某些情况下,可以通过无锁编程(Lock-free Programming)来提高性能。

不当使用锁可能会引发一些令人头疼的问题,例如死锁。例如,进程 A 先获取锁 d1,然后尝试获取锁 d2;而进程 B 先获取锁 d2,然后尝试获取锁 d1。这可能导致 A 和 B 互相等待对方释放锁,从而陷入死锁。

解锁一下B 你必须先解除A才能解除B 我得先解B才能解除A! 你必须先解除A才能解除B!!

一种避免死锁的方法是为所有的锁编号并排序。例如,规定 CPU 执行操作时必须按照锁的编号顺序依次获取锁。这样可以避免死锁的发生。

一些剧透

lec14 15 16 文件系统

Lec18 微内核

Lec19 虚拟机

Lec20 使用高级语言实现 OS

Lec21 网络