《MIT-6S081笔记》

课程来源：MIT-6S081(20 summer)

课程lab：https://github.com/qlhhahaha/MIT6.S081-20fall

《MIT6.S081笔记》@qlhhahaha

Lecture1、Introduction and Examples

1. XV6采用传统的内核形式，分为用户态和内核态

   

   当一个进程需要调用一个内核服务时，它会调用一个系统调用，这是操作系统接口中的一个调用。系统调用进入内核，内核执行服务并返回。因此，一个进程在用户空间和内核空间之间交替执行

   ​

   ​ 💡 PS.

   ​ 注意，xv6和POSIX标准是不兼容的，它缺少许多syscall，且已有的syscall标准也和POSIX有差异；另外xv6没有用户概念或者提供一个机制来保护一个用户不受 另一个用户的影响，用Unix的术语来说，所有的xv6进程都作为root运行，所以我们说xv6只是一个”类unix系统”

   ​

   Q：系统调用跳到内核与标准的函数调用跳到另一个函数相比，区别是什么？

   A：Kernel的代码总是有特殊的权限。当机器启动Kernel时，Kernel会有特殊的权限能直接访问各种各样的硬件，例如磁盘。而普通的用户程序是没有办法直接 访问这些硬件的。所以，执行一个普通的函数调用时，所调用的函数并没有对于硬件的特殊权限。然而，如果触发系统调用到内核中，内核中的具体实现会具有 这些特殊的权限，这样就能修改敏感的和被保护的硬件资源，比如访问硬件磁盘。

2. argv[0]默认是程序名称，所以执行echo hello world时，argc=strlen(argv)为3，argv[1]=“hello”，argv[2]=“world”

3. 关于return和exit()

   首先在定义层面，return和exit()的区别是：

   • return是关键字，表示调用堆栈的返回，只结束一个函数，不一定结束整个程序

   • exit()是syscall，表示一个进程的结束，它会终止当前进程，并将状态报告给wait()函数，一般是 0 为正常退出， 非0 为非正常退出

   Q：在main()中return 0和exit(0)有啥区别？

   A：从效果上来讲，没区别

   Q：非main()的普通函数中呢？

   A：exit(0)可以放在任何位置来退出程序，类似于cpp的throw

   Q：为什么main()中是return 0而不是return 1？

   A：main中return就相当于exit()，而exit()的参数说明：

   • 如果参数为 0 或者 EXIT_SUCCESS，向外部环境报告程序运行圆满结束
   • 如果参数为 EXIT_FAILURE，向外部环境报告程序运行以失败告终
   • 如果参数为其它值，效果由实现定义

   所以说return 0是有明确语义的，而return 1则不具备可移植性

   Q：如果main()中不使用return呢（从汇编角度理解）？

   A：

   • 如果不写return，汇编会自动生成return
   • 如果写了return，汇编会生成相当于exit(main())的语句
   • 如果直接写exit()，就不会生成exit(main())，程序直接退出了

总结说，一个程序真正的退出，在C语言层面上，实际是exit()函数，而main函数的作用，则是给exit()提供返回值

4. atoi()

   int atoi(const char *s)
   {
       int n;
   
       n = 0;
       while ('0' <= *s && *s <= '9')
           n = n * 10 + *s++ - '0';
       return n;
   }

   细节：为什么要减去‘0’？

   因为n = n * 10 + *s++ - ‘0’这一行中其实包含了char到int的隐式类型转换，字符‘0’对应int值是48。比如输入“123”，第一次n = ’1‘ - ’0‘ = 1，没这个’0‘的话n就为49了

LECTURE2、OS organization and syscall

1. 操作系统的隔离性（isolation）

   motivation：用户空间中有多个应用程序（shell、echo、find），一个应用程序出错时不应该影响其它应用，所以不同的应用程序之间应该要有隔离性；类似的，我们也不希望应用程序的出错会导致整个OS的crash，所以应用程序和OS之间也应该具有隔离性

   想想如果没有隔离性会发生什么？

   各个应用程序直接与硬件交互，假如shell中某个函数有死循环，则shell永远不会释放cpu，甚至没办法通过一个第三方的程序去kill；而有了操作系统，不论应用程序在执行什么操作，multiplexing都会迫使应用程序时不时的释放CPU，这样其他的应用程序才能运行

   另外从内存的角度来说，如果应用程序直接运行在硬件资源之上，那么每个应用程序的文本，代码和数据都直接保存在物理内存中。物理内存中的一部分被Shell使用，另一部分被echo使用

   

   那么在这个例子中，为两个应用程序的内存之间没有边界，如果echo程序将数据存储在属于Shell的一个内存地址中（上图中的1000），那么就echo就会覆盖Shell程序内存中的内容

   ​

   ​ 💡 PS.

   ​ OS不是直接将CPU提供给应用程序，而是向应用程序提供“进程”，i.e. 进程抽象了CPU，应用程序不能直接与CPU交互，只能与进程交互

   ​

2. 操作系统的防御性（Defensive）

   motivation：OS应该能抵御外来应用程序的攻击，避免应用程序控制内核（一旦拥有内核就可以控制所有硬件资源）

3. 硬件对于隔离/防御的支持

   • user/kernel mode

     user模式下只能执行普通权限的指令，如add、sub、branch

     kernel模式下能执行特权指令，主要是直接操纵硬件的指令和设置保护的指令，如设置page table寄存器、关闭时钟中断

     当一个应用程序尝试执行一条特殊权限指令时，因为不允许在user mode执行特殊权限指令，处理器会拒绝执行这条指令。通常来说，这时控制权限会从user mode切换到kernel mode，当操作系统拿到控制权之后，或许会杀掉进程，因为应用程序执行了不该执行的指令

     ​

     ​ 💡 PS.

     ​ 具体来讲，是CPU中有一个bit，为1时表示user mode，0表示kernel mode，当CPU在解析指令时，若指令是特殊权限指令，且该bit被设置为1，则处理器会拒绝执行这条指令 —— 当然，同样需要特权指令才能更新这个bit

     ​

   • 虚拟内存

     每个进程都有自己独立的page table，只能访问出现在自己page table中的物理内存。而OS会设置page table，使得每一个进程都有不重合的物理内存，从而实现内存的隔离

4. user进入kernel的方式：ecall指令

   当一个用户程序想要将程序执行的控制权转移到内核，它只需要执行ECALL指令，并传入一个数字，数字参数代表了应用程序想要调用的System Call。 如，不论是Shell还是其他的应用程序，当它在用户空间执行fork时，它并不是直接调用操作系统中对应的函数，而是调用ECALL指令，并将fork对应的数字作为参数传给ECALL。之后再通过ECALL跳转到内核

5. what is QEMU？

   从功能上来说，QEMU可以理解为一个真正的计算机、一块RISC-V主板，它模拟实现了主板开关、插槽、内存芯片功能，运行QEMU等效于运行硬件；从代码角度说，QEMU是一个大型的开源C程序，在QEMU的主循环中，只在做一件事情：

   • 读取4字节或者8字节的RISC-V指令
   • 解析RISC-V指令，并找出对应的操作码（op code）。我们之前在看kernel.asm的时候，看过一些操作码的二进制版本。通过解析可以知道这是一个ADD指令，或者是一个SUB指令
   • 之后，在软件中执行相应的指令

6. XV6代码组织结构

   

7. XV6中的21个syscall

   

8. XV6寄存器

   
   • 0寄存器：risc-v专门为0设置了一个寄存器，这个寄存器只可读而不可写，永远保持0的状态。x0寄存器专门完成这一项工作。鉴于0的使用频率并不算少，这个简单的思路可以带来效率上惊人的提升。
   • 返回地址寄存器（ra）及栈指针寄存器（sp）：x1寄存器保存了栈数据中返回的地址，而x2保存了栈顶的位置
   • 全局指针寄存器（gp）：x3的作用为实现4KB大小范围内的访问加速。这对页内寻址有着非常不错的效果，不过对主体运行原理没有什么太大影响
   • 线程指针寄存器（tp）：当前硬件线程编号，主要是方便实现各个硬件线程的区分
   • 暂存寄存器（t0~t6）：用于保存临时数
   • 存储寄存器（s0~s10）：保存必要的数据。这部分数据在切换上下文的时候会得到保存，而不是覆盖
   • 参数寄存器（a0~a7）：保存函数参数。调用函数时，参数将按顺序存放在这些寄存器中，相应地，使用参数的步骤会在汇编中转化为读取参数寄存器的内容 但是注意：**a0和a1比较特殊。**它们不仅担任函数调用时的传参过程，还在返回时担任存放返回值； a7不仅是参数寄存器，还是用来表示系统调用号。当采取riscv的系统调用指令ecall后，硬件将根据a7内的数据，于中断向量表中启动对应编号的中断进程 （usys.pl中的”li a7, SYS_${name}”）

9. vscode中调试XV6

   • 每次在vscode中打开文件夹时不要打开MIT_6S081_20fall这个上级目录，要打开MIT6.S081-20fall这个子目录

   • 在MIT6.S081-20fall子目录下创建.vscode文件，把debug_json中的5个json文件全复制过去

     

   • 注释配置文件中的端口号

   

   • 在main.c的第一行打断点，直接按F5 debug

     

10. XV6中syscall的调用和实现过程

    user：

    • usys.pl：自动生成usys.S汇编文件，里面定义了某个syscall的用户态跳板函数
    
    • user.h：syscall函数声明
    

    kernel：

    • syscall.h：define syscall numbers

      

    • syscall.c：通过一个通用模板来执行syscall

      

    • sysproc.c：syscall的具体实现

      

    • proc.h：定义proc、trapframe、context等重要结构体

      

    • proc.c：proc相关函数的具体实现

      

      系统调用全流程：

      user/user.h:		用户态程序调用跳板函数 trace()
      user/usys.S:		跳板函数 trace() 使用 CPU 提供的 ecall 指令，调用到内核态
      kernel/syscall.c	到达内核态统一系统调用处理函数 syscall()，所有系统调用都会跳到这里来处理。
      kernel/syscall.c	syscall() 根据跳板传进来的系统调用编号，查询 syscalls[] 表，找到对应的内核函数并调用。
      kernel/sysproc.c	到达 sys_trace() 函数，执行具体内核操作

      这么繁琐的调用流程的主要目的是实现用户态和内核态的良好隔离。

      并且由于内核与用户进程的页表不同，寄存器也不互通，所以参数无法直接通过 C 语言参数的形式传过来，而是需要使用 argaddr、argint、argstr 等系列函数，从进程的 trapframe 中读取用户进程寄存器中的参数。

      同时由于页表不同，指针也不能直接互通访问（也就是内核不能直接对用户态传进来的指针进行解引用），而是需要使用 copyin、copyout 方法结合进程的页表，才能顺利找到用户态指针（逻辑地址）对应的物理内存地址。

LECTURE3、Page tables

1. 概念：

   页表是操作系统为每个进程提供私有地址空间和内存的机制。 RISC-V指令（包括用户指令和内核指令）使用的是虚拟地址，而机器的RAM或物理内存是由物理地址索引的。而页表就是将每个虚拟地址映射到物理地址，从而在两种地址间建立联系。

2. 页面工作过程

   

   • XV6只是用64位虚拟地址中的低39位，高25位不用

   • 39位中，有27位用来做**页表条目（Page Table Entries/PTE）**的索引，也就是有$2^{27}$个entry

   • 每个PTE包含一个44位的**物理页码（Physical Page Number/PPN）**和一些标志位

   • 生成的物理地址有56位，其中44位是PPN，还有12位是原始虚拟地址的Offset

   在实际的转换中还把页表分成了三级树结构

   

   每级有512个PTE，每个PTE中包含该树的下一级页表页的物理地址 如果转换地址所需的三个PTE中的任何一个不存在，页式硬件就会引发页面故障异常（page-fault exception），并让内核来处理该异常

   PTE中Flags的含义：

   

3. 进程的虚拟地址和内核虚拟地址

   OS的虚拟地址空间可以分为以下两个：

   • 进程虚拟地址（User Virtual Memory, UVM）：即用户级虚拟地址，指进程在用户空间下可访问的虚拟内存地址。进程虚拟地址由内存管理单元（MMU）通过三级页表映射到物理内存地址（xv6中，UVM到真实PA的转换是非线性映射，具体方式是三级页表查询+位左移右移）

   • 内核虚拟地址（Kernel Virtual Memory, KVM）：允许操作系统内核直接访问和管理所有的硬件资源和内存（xv6中，KVM到真实PA的转换是线性映射，如UART的VA和PA都是0x10000000L，这种线性映射一直持续到0x80000000L）

     

​ 每个进程都独享一个虚拟地址空间，但内核虚拟空间只有一个，整个OS共用

​

​ 💡 PS.

从CPU角度看，所谓内核空间地址/用户空间地址只是权限不一样而已，要获取它们的物理地址，从硬件层面上都要走MMU这套硬件机制。但是软件层面不一样，当需要知道一个用户空间虚拟地址对应的物理地址时，就是用上述三级页表来翻译得到它的物理地址；但是内核空间虚拟地址是所有进程共享的，而且效率很重要，这就有取巧优化的空间了： 内核在初始化时就创建内核空间的映射（因为所有进程共享一份就够了)，并且采用的是线性映射（即内核一整块内核空间页，一对一地映射到一块物理内存上）。这意味着，在软件层面(内核)，当内核需要知道它访问的一个内核空间页面Px的物理地址时，它只要知道第一页P0的物理地址即可，然后加上Px相距P0的偏移，即可快速知道Px的物理地址（线性映射的优势），而不需要走页表翻译这种类似哈希表的方式去计算。

​

4. 进程的地址空间

   

   为了检测用户栈是否溢出了所分配栈内存，xv6在栈正下方放置了一个无效的保护页（guard page）。如果用户栈溢出并且进程试图使用栈下方的地址，那么由于映射无效（PTE_V为0）硬件将生成一个页面故障异常。当用户栈溢出时，实际的操作系统可能会自动为其分配更多内存

5. some QA

   Q：因为存在很多个虚拟地址空间，所以设计时需要讲最大虚拟地址设置得足够小吗？

   A：不需要，虚拟内存可以比物理内存更大，page table的实现非常灵活

   Q：如果有太多的进程使用了虚拟内存，有没有可能物理内存耗尽了？

   A：有可能，这通过kallco可以看到，它保存了空余page的列表，当这个列表耗尽了的时候kalloc会返回一个空指针；而内核的一部分工作就是处理这样的情况 —— 应该给用户返回一个错误消息，而不是直接crash

   Q：代码/汇编指令中的地址是虚拟地址还是物理地址？

   A：任何一条带有地址的指令，其中的地址都是虚拟内存地址

   Q：page table由MMU保存吗？

   A：不是，page table也保存在内存中，MMU是从内存中读取page table并完成翻译

   Q：以XV6的三级page table为例，解释一下为什么给一个进程分配的最大虚拟内存是512GB？

   A：注意，一个entry对应的是一个4KB的page，三级列表，每个有512个entry，总共就有$512×512×512=2^{27}$个entry，每个4KB，总共就是$2^{27}×2^2KB=512GB$

   ​

   ​ 💡 PS.

   PS. 注意，index为27个bit，刚好对应2^{27}个entry；offset为12bit，刚好对应4KB。即index用来查找page，offset对应的是一个page中的哪个字节

   ​

   Q：4096Bytes作为一个page，这在物理内存中是连续的吗？

   A：是的，在物理内存中，这是连续的4096个字节。所以物理内存是以4096为粒度使用的

   Q：为什么要把page table分成3级？

   A：假设某个进程的地址空间只使用了1个page，也就是4094Bytes，在三级结构中要多少个entry呢？ 在最高级，你需要一个page directory。在这个page directory中，你需要一个数字是0的PTE，指向中间级page directory。所以在中间级，你也需要一个page directory，里面也是一个数字0的PTE，指向最低级page directory。所以这里总共需要3个page directory（也就是3 * 512个entry，12KB 内存） 而在不分级的结构中呢？ 只使用了一个page，但还是需要2^27个PTE（注，约 1GB 内存）

   ​

   ​ 💡 PS.

   这个3个page directory的例子具体由entry中的valid 标志位来实现，我们只使用了3个page directory，每个page directory中只有第0个PTE被使用了，所以只有第0个PTE的Valid bit位会被设置成1，其他的511个PTE的Valid bit为0。这个标志位告诉MMU，你不能使用这条PTE，因为这条PTE并不包含有用的信息

   ​

   Q：SATP寄存器中存的是什么？

   A：最高级的page directory的物理内存地址。当一个进程请求一个虚拟内存地址时，CPU中的MMU会查看SATP寄存器得到对应的最高一级page table的地址，这级page table会使用虚拟内存地址中27bit index的最高9bit来完成第一次索引

6. 用lab3中的例子解释一下页表中的几个点

   
   • 整个页表的地址=最高级的页表的entry0的地址
   • 用页表进行地址转换的过程是：先用整个页表的地址（也就是myproc()→pagetable这个变量）找到最高级页表，再用virtual address的高9位找到对应的那个entry，这个entry中的PTE通过某种转换算法变成真实的PA（XV6中是简单的bit左移右移操作），这个PA就是下一级页表的地址；好，找到下一级页表后又通过virtual address的中9位找对应entry，重复操作直至找到最低一级页表中的对应entry，其转换后的PA就是分配的那个4KB page的物理地址

7. 进程的内核栈（process‘s kernel stack）

   进程的内核栈是操作系统内核为每个进程分配的一块特殊内存区域，用于在内核模式下执行时存储临时数据和控制信息。当进程在用户模式下运行时，它使用的是用户栈；但当进程进行系统调用或遇到中断、异常时，CPU会切换到内核模式，此时就会使用内核栈。

   如上下文保存与恢复：当进程从用户模式切换到内核模式时，内核栈用于保存当前的CPU寄存器状态、程序计数器和其他必要的上下文信息。这些信息在进程再次回到用户模式时需要被恢复。

   ​

   ​ 💡 PS.

   1. 每个进程都独有一个用户栈和一个内核栈

   2. 内核栈的大小通常在进程创建时确定，并在进程的整个生命周期中保持不变

   ​

LECTURE4、Trap

1. 概念

   用户空间和内核空间的切换通常被称为trap，它通常发生在

   • 执行syscall
   • 程序出现类似page fault、运算时除以0的错误
   • 设备触发中断

2. trap代码执行流程

   以下是shell中调用write() syscall时trap的全过程

   

   a. write执行ECALL指令，切换到supervisor mode内核

   b. 执行内核代码trampoline.s中的函数uservec，代码执行跳转到trap.c中的函数usertrap()

   c. 在usertrap()中，执行syscall()函数；syscall()根据传入的代表系统调用的数字进行查找，并在内核中执行具体功能函数（在这个例子中是sys_write）

   d. syscall()执行结束后继续调用trap.c中的usertrapret()，该函数完成了部分方便在C代码中实现的返回到用户空间的工作

   e. 剩下的一些工作存在于trampoline.s中的userret中

LECTURE5、Page Fault

1. 概念

   应用程序通过 malloc 函数申请内存的时候，实际上申请的是虚拟内存，此时并不会分配物理内存。当应用程序读写了这块虚拟内存，CPU就会去访问这个虚拟内存， 这时会发现这个虚拟内存没有映射到物理内存， CPU就会产生缺页中断，进程会从用户态切换到内核态，并将缺页中断交给内核的 Page Fault Handler （缺页中断函数）处理

   XV6中处理page fault的方式很保守，遇到就直接kill掉进程；但正规的操作系统有一系列处理方式：

   • lazy allocation
   • copy-on-write fork
   • demand paging
   • memory mapped files

2. XV6中的page fault

   当出现page fault的时候，XV6内核会打印出错的虚拟地址，并且这个地址会被保存在STVAL寄存器中，且page fault和其他的异常使用与系统调用相同的trap机制来从用户空间切换到内核空间

   出现page fault时，有三个有价值的信息：

   • 引起page fault的内存地址（保存在STVAL寄存器中）
   • 引起page fault的原因类型（保存在SCAUSE寄存器中）
   • 引起page fault时的程序计数器值，这表明了page fault在用户空间发生的位置

   ​

   ​ 💡 PS.

   我们之所以关心触发page fault时的程序计数器值，是因为在page fault handler中我们或许想要修复page table，并重新执行对应的指令。理想情况下，修复完page table之后，指令就可以无错误的运行了。所以，能够恢复因为page fault中断的指令运行是很重要的。

   ​

   

3. sbrk()

   sbrk是XV6提供的系统调用，它使得用户应用程序能扩大自己的heap。当一个应用程序启动的时候，sbrk指向的是heap的最底端，同时也是stack的最顶端。这个位置通过代表进程的数据结构中的sz字段表示，这里以p->sz表示。

   

   当调用sbrk时，它的参数是整数，代表了你想要申请的page数量，即内存会分配一些物理内存并将其映射到用户地址空间，并将内存内容初始化为0（这种方式称之为eager allocation） 但这当中有个潜在问题：实际中的进程很难预测自己需要多少内存，若提前要太多内存，可能会出现有些分配的内存永远不会被使用到的浪费情况。为此，我们提出lazy allocation

4. lazy allocation

   核心思想：sbrk()基本上不做任何事情，唯一需要做的事情就是提升p->sz，将p->sz增加n，其中n是需要新分配的内存page数量。但是内核在这个时间点并不会分配任何物理内存。 之后在某个时间点，应用程序使用到了新申请的那部分内存，这时会触发page fault，因为我们还没有将新的内存映射到page table。所以，如果我们解析一个大于旧的p->sz，但是又小于新的p->sz（也就是旧的p->sz + n）的虚拟地址，我们希望内核能够分配一个内存page（使用kalloc），并且重新执行指令

   代码部分：

   首先修改sys_sbrk()，让它对p→sz增加n，但并不执行增加内存的操作

   

   但这个时候还是会page fault，因为sys_sbrk()并没有实际分配所需要的内存

   

   所以我们需要在usertrap()中根据不同的SCAUSE进行改进

   

   如果SCAUSE ==8，则表示是处理普通syscall时进入的trap；若SCAUSE==15，则表示是因为page fault进入的trap，之后分配一个物理内存page，如果ka等于0，表明没有物理内存我们现在OOM了，我们会杀掉进程。如果有物理内存，首先会将内存内容设置为0，之后将物理内存page指向用户地址空间中合适的虚拟内存地址

   但是这样修改之后还是会出错

   

   Why？报错信息显示是因为uvmunmap尝试对某些page进行unmap时发现这些page并不存在，这些page是哪儿来的？其实就是之前lazy allocation但是又没实际分配的内存，我们只需要将uvmunmap中原先的panic改成continue就行

   

   ​

   ​ 💡 PS.

   解释：之前的panic表明，我们尝试在释放一个并没有map的page。怎么会发生这种情况呢？唯一的原因是sbrk增加了p->sz，但是应用程序还没有使用那部分内存。因为对应的物理内存还没有分配，所以这部分新增加的内存的确没有映射关系。我们现在是lazy allocation，我们只会为需要的内存分配物理内存page。如果我们不需要这部分内存，那么就不会存在map关系，这非常的合理。相应的，我们对于这部分内存也不能释放，因为没有实际的物理内存可以释放，所以这里最好的处理方式就是continue，跳过并处理下一个page 为什么之前的panic会存在？对于未修改的XV6，永远也不会出现用户内存未map的情况，所以一旦出现这种情况需要panic。但是现在我们更改了XV6，所以我们需要去掉这里的panic，因为之前的不可能变成了可能

   ​

5. Copy On Write（COW）

   motivation：XV6中的shell通常有4个物理page，在shell中执行echo hello时，shell会通过fork创建一个子进程，这个子进程创建4个新page并将父进程page中的内容拷贝到新page，然后调用exec来执行echo 那么就有一个问题，exec会丢弃从父进程拷贝过来的shell地址空间，取而代之的是一个包含了echo的地址空间，也就是刚把父进程地址空间拷贝过来就丢掉了，这看起来有些浪费 一个类似于懒分配的优化方案是：懒拷贝，即创建子进程时不立刻分配新的物理page，而是暂时和父进程共享，等到真的要对子进程写内存的时候再真正分配物理page

   具体做法：

   设置子进程的PTE指向父进程对应的物理内存page（注意，为了保证父子进程之间的隔离性，这里可以将父进程和子进程的PTE的flags都设置成只读的）

   

   写内存时会得到page fault（因为都是只读的），然后去真正分配一个新的物理page（只对子进程可见了，PTE可以设为读+写了），且刚刚出错的那个page也可以改为读+写了（因为它现在只对父进程可见了）

   

   然后调用userret()重新执行用户指令（userret()会回到用户空间）

   ​

   ​ 💡 PS.

   如何区分是copy-on-write还是普通的在向一个正常的只读地址写数据呢？（COW的话需要在page fault handler中去新分配内存，普通的就不用） 答：使用PTE中的RSW标志位，它有2bit，我们可以将copy-on-write设成特定flag

   ​

   另外，copy-on-write中需要注意的一个细节是，采用这种方案可能会导致多个进程指向同一片物理page，那么父进程退出时不能马上释放这些page，可能还有其它子进程指着的。 所以我们需要对每个物理page的引用进行计数（引入额外的数据结构，shared_ptr？），引用数为0时才能去释放物理page

LECTURE6、Multiprocessors and locking

1. 自旋锁（spinlocks）

   详见《南大OS笔记》

   XV6中自旋锁实现原理：

   核心还是使用原子汇编指令amoswap

   

   XV6中所有自旋锁

   

   __sync_synchronize()的作用：

   告诉编译器和CPU不要跨障碍重新排序load或者store指令，因为xv6在访问共享数据时使用了锁，xv6的acquire和release中的障碍在几乎所有重要的情况下都会强制顺序执行

2. xv6中UART模块对于锁的使用

   

   函数首先获得了锁，然后查看当前缓存是否还有空槽位，如果有的话将数据放置于空槽位中；写指针加1；调用uartstart；最后释放锁。 如果两个进程在同一个时间调用uartputc，那么这里的锁会确保来自于第一个进程的一个字符进入到缓存的第一个槽位，接下来第二个进程的一个字符进入到缓存的第二个槽位。这就是锁帮助我们避免race condition的一个简单例子。如果没有锁的话，第二个进程可能会覆盖第一个进程的字符。

   ​

   ​ 💡 PS.

   当第一个进程通过acquire()拿到锁之后，第二个进程就会卡在acquire()中的while循环里

   ​

3. acquire函数的最开始，会先关闭中断：why？

   我们回到uart.c中，假设uartputc()中的acquire在一开始并没有关闭中断，会发生什么呢？

   • UART完成字符传输后产生一个中断，运行uartintr函数
   • 在uartintr函数中，会获取同一把锁，但是这把锁正在被uartputc持有
   • 中断处理程序uartintr一直等待锁释放，但是CPU不出让给uartputc执行的话锁又不会释放
   • 造成死锁，引发panic

   这就解释为为啥acquire()首先要关掉中断，release()完后再开启中断 所以说，spinlock其实需要处理两类并发，一类是不同CPU之间的并发，一类是相同CPU上中断和普通程序之间的并发。

LECTURE7、Thread switching

1. 线程包含三个部分：

   • 程序计数器（PC）
   • 保存变量的寄存器
   • 程序的stack（记录函数调用）

2. xv6中的线程切换

   在XV6中，任何时候切换上下文都需要经历：

   • 从一个用户进程切换到另一个用户进程，都需要从第一个用户进程接入到内核中，保存用户进程的状态并运行第一个用户进程的内核线程

   • 再从第一个用户进程的内核线程切换到第二个用户进程的内核线程

   • 第二个用户进程的内核线程暂停自己，并恢复第二个用户进程的用户寄存器

   • 最后返回到第二个用户进程继续执行

     ​

     ​ 💡 PS.

     用户寄存器存在trapframe中，内核线程的寄存器存在context中

     ​

   

   proc结构体中和上下文切换相关的内容：

   • 保存了用户空间线程寄存器的trapframe字段
   • 保存了内核线程寄存器的context字段
   • 保存了当前进程的内核栈的kstack字段，用于进程在内核中执行时保存函数调用
   • state字段保存了当前进程状态：RUNNING，RUNABLE，SLEEPING
   • 自旋锁lock，很多地方都会用（如state字段的更新）

   demo程序：

   

   输出结果：

   

   yield函数：

   

   yield()将进程的状态改为RUNNABLE，这意味着当前进程要让出cpu，并切换到调度器线程 加锁的目的：如果不加锁的话，其它cpu的调度器线程可能看到进程的状态为RUNNABLE并尝试运行它，这就会导致进程就会在两个CPU核上运行了，而一个进程只有一个栈，这意味着两个CPU核在同一个栈上运行代码（注，因为XV6中一个用户进程只有一个用户线程）

   sched函数：

   

   主要是一些防御性检查，然后调用swtch()

   swtch()：

   

   swtch函数会将当前的内核线程的寄存器保存到p->context中。swtch函数的另一个参数c->context，c表示当前CPU的结构体

   ​

   ​ 💡 PS.

   为啥swtch函数要用汇编来实现，而不是C语言？ 因为C语言中很难与寄存器交互，除非在C中嵌套汇编，那就和定义一个汇编函数是等价的了

   ​

   scheduler()：

   

   所有xv6代码中，仅有每个cpu初始化的时候调用scheduler()，其主体是个死循环，仅当某个进程状态为RUNNABLE时才能swtch到该进程

3. sleep & wakeup

   见《南大OS笔记》条件变量

4. 屏障机制

   

   假设只有一个线程，那thread()中的barrier()只需要简单地写成bstate.round++就行，就可以保证i和t始终一样；

   但如果有两个线程就不行了：第一个线程把bstate.round加一下，第二个又加一下，就触发assert了。这时候就需要所谓的屏障机制，来保证多个线程在barrier()处能“等一等大家”，没到齐就不能执行critical section，到齐了就其它线程睡眠，留出一个线程执行一次bstate.round++就行，将这种思想写成代码就是：

   

   任何一个线程进入barrier()之后都要把bstate.nthread（表示当前在barrier()中的线程数）加一并判断是否所有线程都到齐，假设只有一个线程那直接执行else，没啥问题； 假设有两个线程，那么先进去的那个会pthread_cond_wait()陷入睡眠，后进去的那个执行else，把bstate.round++后再用pthread_cond_broadcast()唤醒睡眠中的线程，被唤醒后执行第18行，不会改变bstate.round，这样一来就保证了所有线程都会在barrier处等待且critical section只执行一次，n个线程时同理，略

   至于为啥barrier中要对pthread_mutex lock和unlock呢？ 假设有两个线程，不使用互斥锁，那么第一个线程++bstate.nthread后、陷入睡眠前，第二个线程可能就已经执行了唤醒函数pthread_cond_broadcast()，那就相当于白唤醒了，第一个线程就会永远陷入睡眠，程序不会终止（如下），这就是所谓的lost wakeup

   

   而加上互斥锁后，第一个线程首先上锁、进行if判断、准备陷入睡眠，这个过程中第二个线程因为拿不到锁，一直还在第9行等待，等第一个线程陷入睡眠后才会释放锁（pthread_cond_wait()第二个参数就是要释放的那把互斥锁），然后第二个线程才能拿到锁、执行else

   最终测试执行：

   

5. 内存分配器中的锁优化

   motivation：

   kalloc原本的实现中用freelist链表来管理空闲物理页，即把空闲物理页本身直接当作链表项（这样可以不使用额外空间），在分配的时候将物理页从链表中移除，回收时将物理页放回链表中

   // kernel/kalloc.cstruct {
   struct spinlock lock;
   struct run*freelist;
   } kmem;

   分配物理页的实现（原版）：

   // kernel/kalloc.c
   void*kalloc(void)
   {
   		struct run*r;
   		
   	  acquire(&kmem.lock);
   	  r= kmem.freelist;// 取出一个物理页。页表项本身就是物理页。if(r)
   	  kmem.freelist= r->next;
   	  release(&kmem.lock);
   		
   		if(r)
   		    memset((char*)r, 5, PGSIZE);// fill with junkreturn (void*)r;
   }

   释放物理页（原版）：

   void
   kfree(void* pa)
   {
       struct run* r;
   
       if (((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
           panic("kfree");
   
       // Fill with junk to catch dangling refs.
       memset(pa, 1, PGSIZE);
   
       r = (struct run*)pa;
   
       acquire(&kmem.lock);
       r->next = kmem.freelist;
       kmem.freelist = r;
       release(&kmem.lock);
   }

   图示：

   

   不论是分配物理页还是释放，都需要修改freelist，加锁是为了保证多线程一致性，否则可能会出现多个线程同时操纵一个物理页的情况，导致出错；但这样的锁设计在保证正确性的同时也导致了多线程无法并发申请内存（因为只有一个freelist链表，所有可用的物理空间都由这个freelist管理，所以加锁既防止了“同时操纵同一个物理空间”，也阻止了“同时操纵不同的物理空间”），也就是所谓的“锁竞争频繁”

   解决思路：

   锁竞争优化的常用思路：

   • 只在必须共享的时候共享（对应为将资源从 CPU 共享拆分为每个 CPU 独立）
   • 必须共享时，尽量减少在关键区中停留的时间（对应“大锁化小锁”，降低锁的粒度）

   该 lab 的实验目标，即是为每个 CPU 分配独立的 freelist，这样多个 CPU 并发分配物理页就不再会互相排斥了，提高了并行性。

   但由于在一个 CPU freelist 中空闲页不足的情况下，仍需要从其他 CPU 的 freelist 中“偷”内存页，所以一个 CPU 的 freelist 并不是只会被其对应 CPU 访问，还可能在“偷”内存页的时候被其他 CPU 访问，故仍然需要使用单独的锁来保护每个 CPU 的 freelist。但一个 CPU freelist 中空闲页不足的情况相对来说是比较稀有的，所以总体性能依然比单独 kmem 大锁要快。在最佳情况下，也就是没有发生跨 CPU “偷”页的情况下，这些小锁不会发生任何锁竞争。

   代码实现：

   

   注意，kinit()阶段为每个cpu都建立了一个freelist链表，在freerange()中调用kfree()，把所有可用的物理空间均分给了每一个cpu（理论上几乎均分）

   

   在分配内存的时候，若CPU freelist 中空闲页是充足的那就直接分配，各个cpu各忙各的； 若空闲页不够了则运行12-30行，去“偷”别的cpu的freelist的物理页

   图示：

   

   每成功循环运行一次偷一个物理页，最多偷64个（数值是随意取的，在现实场景中，最好进行测量后选取合适的数值，尽量使得“偷”页频率低，因为偷页时也要调用锁，影响效率）

   最终锁竞争降到了0

   

LECTURE8、File System

1. 文件系统主要做的事

   • 基本功能：用数据结构来表示目录和文件名称树，记录每个文件内容块、以及磁盘的哪些区域是空闲的
   • 崩溃恢复（crash recovery）：若发生崩溃（如电源故障），文件系统必须重启后仍能正常工作。其难点在于崩溃可能会中断一系列更新，并使磁盘上的数据结构不一致（如一个块在某个文件中使用但同时仍被标记为空闲）
   • 原子性：不同的进程可能同时在文件系统上运行，因此文件系统必须协调以保持不变量
   • 速度不一致：访问磁盘的速度比访问内存慢几个数量级，因此文件系统必须保持常用块的内存缓存

2. XV6中的文件系统

   XV6文件系统分为7层

   层级	作用
   磁盘（Disk）	实际保存数据，硬件层面提供持久化
   缓冲区高速缓存（Buffer cache）	避免频繁的读写磁盘
   日志（Logging）	实现崩溃恢复，软件层面提供持久化
   索引节点（Inode）	将每个文件表示为一个索引节点，其中包含唯一的索引号和一些保存文件数据的块
   目录（Directory）	将每个目录实现为一种特殊的索引节点
   路径名（Pathname）	如***/usr/rtm/xv6/fs.c***
   文件描述符（File descriptor）	抽象Unix资源（如管道、设备、文件）

   怎么理解持久化：

   关闭计算机，过几天再开机而文件仍然在那，我可以继续基于文件工作。这一点与进程和其他资源不一样，这些资源在计算机重启时就会消失，之后需要重新启动它们。这就是文件系统所谓的持久化

   索引节点（Inode）：

   文件系统中的核心数据结构就是inode和file descriptor。 inode代表一个文件的对象，但它不依赖于文件名，而是通过自身的编号来进行区分。所以说文件系统内部通过一个数字（而非文件路径名）来引用inode XV6和UNIX中都有一个syscall，叫做link，用来给同一文件指定多个名字，如

   link("X/Y", "X/Z")   // 为文件"X/Y"创建另一个名字"X/Z"

   而inode必须有一个link count来跟踪指向这个inode的文件名的数量。一个文件（inode）只能在link count为0的时候被删除

   XV6中一个inode的大小是64字节

   • type字段：表明inode是文件还是目录
   • nlink字段：也就是link计数器，用来跟踪究竟有多少文件名指向了当前的inode
   • size字段：表明了文件数据有多少个字节。
   • direct block number：这12个block编号指向了构成文件的前12个block。举个例子，如果文件只有2个字节，那么只会有一个block编号0，它包含的数字是磁盘上文件前2个字节的block的位置。
   • indirect block number：指向其它的block（有点类似于page table的思想）
   

   文件系统如何使用磁盘：

   两个术语：

   • sector通常是磁盘驱动可以读写的最小单元，它过去通常是512字节。
   • block通常是操作系统或者文件系统视角的数据。它由文件系统定义，在XV6中它是1024字节。所以XV6中一个block对应两个sector。通常来说一个block对应了一个或者多个sector。

   （但二者有时也会混用）

   

   大致结构就是，磁盘、cpu、内存都连到总线上，文件系统运行在cpu上，将内部的数据存储在memory中，同时也会以读写block（read/write的系统调用）的形式存储在磁盘中

   从文件系统的角度来看磁盘，其实就是一个巨大的block的数组，其中：

   • block0要么没有用，要么被用作boot sector来启动操作系统
   • block1通常被称为super block，它描述了文件系统。它可能包含磁盘上有多少个block共同构成了文件系统这样的信息
   • 在XV6中，logging从block2开始，到block32结束
   • 接下来在block32到block45之间，XV6存储了inode，一个inode是64字节
   • 之后是bitmap block，用于记录数据block是否空闲，它只占据一个block
   • 之后就全是数据block了，数据block存储了文件的内容和目录的内容

   

   block cache的锁策略

   block cache用的是sleep lock，区别于一个常规的spinlock

   

   首先用acquire()获取一个普通的自旋锁，然后如果这个锁被持有了，就进入sleep状态，并将自己从当前cpu调度开

   ​

   ​ 💡 PS.

   Q、既然sleep lock是基于spinlock实现的，为什么对于block cache，我们使用的是sleep lock而不是spinlock？ A、因为磁盘操作需要很长的时间。spinlock在加锁时中断必须要关闭，所以持有spinlock时永远不能从磁盘收到数据（假设只有一个cpu）；而sleep lock的优势是，持有锁时不关闭中断，在等待sleep lock的时候，我们并没有让CPU一直空转，而是通过sleep将CPU出让出去了

   ​

3. XV6中的崩溃恢复

   概述：logging是故障恢复的最关键机制，在数据库、文件系统、分布式系统中都有大量应用（有些地方会把log叫做journal）

   创建文件时，操作系统与磁盘block的交互过程：

   

   • 首先是分配inode，因为首先写的是block 33
   • 之后inode被初始化，然后又写了一次block 33
   • 之后是写block 46，是将文件x的inode编号写入到x所在目录的inode的data block中
   • 之后是更新root inode，因为文件x创建在根目录，所以需要更新根目录的inode的size字段，以包含这里新创建的文件x
   • 最后再次更新了文件x的inode

   logging的工作流程：

   首先，将磁盘分割为log和文件系统两个部分，文件系统可能比log大得多

   （log write）将写操作记录到log中，而非直接写入到block所在的位置 （commit op）当文件系统的操作结束后，记录同一个文件系统的操作的个数，即commit （install log）真正执行log中记录的操作 （clean log）完成后清除log，即将同一个文件系统的操作个数设置为0

   为什么这样能实现崩溃恢复呢？

   假设crash并重启了。在重启的时候，文件系统会查看log的commit记录值，如果是0的话，那么什么也不做。如果大于0的话，我们就知道log中存储的block需要被写入到文件系统中，很明显我们在crash的时候并不一定完成了install log，我们可能是在commit之后，clean log之前crash的。所以这个时候我们需要做的就是reinstall（注，也就是将log中的block再次写入到文件系统），再clean log

   XV6中的log结构：

   

   开始有一个header block，里面包含了log记录条数 和 每个log block的实际对应的block编号； 之后就是log的数据，也就是block的数据

   log_write()函数：

   前面提到仅应该在所有的写操作完成之后写入commit record，那么应有手段来表明事务（transaction）的开始和结束，以创建文件的sys_open()为例，每个文件系统操作都有begin_op和end_op来表示事务的开始和结束（end_op中实现commit操作）

   

   log_write是文件系统的logging实现的方法，任何一个文件系统调用的begin_op和end_op之间的写操作总是会走到log_write

   

   基本思路：先获取log header的锁，再更新log header。首先代码会查看block 45是否已经被log记录了。如果是的话，其实不用做任何事情，因为block 45已经会被写入了。如果block 45不在需要写入到磁盘中的block列表中，接下来会对n加1，并将block 45记录在列表的最后

   end_op()函数：

   end_op()中最关键的是commit()

   

   其中主要有两个操作，write_log将位于cache中的log header中的block编号对应的block，移到磁盘的log区域中；write_head实现真正的commit

   文件系统恢复：

   当系统crash并重启时，首先调用initlog函数

   

   

   其中调用install_trans函数，读取log header中的n，然后根据n将所有的log block拷贝到文件系统的block中。recover_from_log在最后也会跟之前一样清除log

4. 真实世界中的崩溃恢复

   包括XV6在内的大部分logging系统需要遵循的：

   • write ahead rule：先将所有的写操作记录在log中，然后才能将这些写操作应用到文件系统的实际位置，而不是写一条更新一条（从而保证原子性）
   • freeing rule：直到log中所有的写操作被更新到文件系统之前，我们都不能释放或者重用log

   linux中的ext3文件系统：

   ext3 = ext2 + logging ext3通过3种方式提升性能：

   • 提供异步的系统调用：即系统调用在写入到磁盘之前就返回了，系统调用只会更新缓存在内存中的block，并不用等待写磁盘操作。 即应用程序可以调用一些文件系统的系统调用，但是应用程序可以很快从系统调用中返回并继续运算，与此同时文件系统在后台会并行完成之前的系统调用所要求的写磁盘操作。这被称为I/O concurrency
   • 提供批量执行（batching）的能力：可以将多个系统调用打包为一个transaction，从而分摊了transaction带来的固有的损耗
   • 提供并发（concurrency）：可以有多个不同状态的transaction同时存在，而XV6中新的系统调用就需要等待前一个transaction完全完成

LECTURE9、Mmap

1. motivation

   使用常规的read和write来读取文件数据时，要涉及两次数据复制（磁盘到内核空间一次，内核空间再到用户空间一次），而mmap则是将文件直接映射到进程的地址空间（即用户空间），从而减少数据复制；此外mmap可以利用操作系统的内存管理机制，如页面缓存和MMU管理来优化性能，所以比read write更高效。简而言之，mmap更复杂，但也更高效

2. 微内核（micro kernel）

   unix、XV6这种叫做monolithic kernel，全面而庞大，但针对特定的任务可能只需要其中一部分功能，也就是需要所谓的简化的微内核

   架构

   一个典型的微内核的核心是**IPC（Inter-Process Communication）*以及*线程和任务的tiny kernel。所以微内核只提供了进程抽象和通过IPC进程间通信的方式，除此之外别无他物。

   如下图，还是用户空间和kernel两层，用户空间中会有各种各样常见的程序，以及文件系统、磁盘驱动、网络协议栈、虚拟内存系统等

   

   当文本编辑器VI读取文件时，它通过IPC会发送一条消息到文件系统进程。文件系统进程中包含了所有的文件系统代码，它知道文件，目录的信息。文件系统进程会发送另一个IPC到磁盘驱动程序

   而内存唯一要做的事是支持进程/任务/线程，以及支持IPC；但没有文件系统、没有设备驱动、没有网络协议栈，这些东西都放在了用户空间

   这种简单的OS架构在很多嵌入式系统中都大有应用

LECTURE10、Network

Ring Buffer

一个基本的网卡、网络驱动的结构是：网卡收到一个packet后尽快将其拷贝至计算机内存（因为网卡自身内存小），之后由操作系统中一个叫IP processing thread的独立线程来读取内存中的packet队列，然后再来决定如何处理这些packet，可能是上传给UDP；也可能这是个路由器，要转发给另一个路由器（RX是接收队列，TX是发送队列）

其中队列的作用是：

• 应对短暂大流量：如IP processing thread只能以特定的速度处理packet，但是网卡可能会以快得多的速度处理packet，所以需要队列缓存
• 让网卡在空闲时持续发送packet，使其利用率达到100%
• 帮助组件解耦：即IP processing thread不需要知道中断的具体实现（网卡收到一个packet后生成中断，系统触发中断处理程序来获取packet），用队列来统一接口

​

​ 💡 PS.

同一个网卡可以既是发送方又是接收方，但不用的网络要用不同的网卡来连接

​

当网卡监听到网线上的电信号时，会直接将packet拷贝到主机的内存中，内存中的packet就会等待驱动来读取自己，所以网卡需要事先知道应该将packet拷贝到哪个位置。 具体方式为，主机格式化好一个DMA ring数组，其中存的是packet指针（之所以叫ring是因为若用到数组的最后一个buffer，则下一次又会使用第一个buffer），主机上的驱动程序会告诉网卡DMA ring在内存中的位置，这样网卡就可以将packet拷贝到内存中的对应位置

此外，也会有一个TX ring，驱动会将需要网卡传输的packet存储在 TX ring中，网卡也需要知道TX ring的地址