Hello World
0%

MIT6.s081 学习记录

发表于 更新于 分类于

day 1 环境配置

linux安装vscode

linux安装clash gui

xv6教程

day 2 操作系统接口

操作系统的任务：在多个程序之间共享一台计算机，并提供比硬件本身支持的更有用的服务

内核：一个特殊的程序，为正在运行的程序提供服务

进程：每个正在运行的程序，都包含指令、数据和堆栈的内存

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

CPU提供硬件保护机制，内核程序的执行拥有操控硬件的权限，它需要实现这些保护；而用户程序执行时没有这些特权。

fork()：创建一个子进程，内存和父进程相同（虚拟内存）。父进程中，返回子进程的PID，子进程中返回0

exit(int status)：终止当前进程，0代表任务成功，1代表任务失败。子进程将status写入父进程的wait(int *status)中

wait(int status)：等待一个子进程退出; 将退出状态存入status; 返回子进程PID。

**exec(char *file, char *argv[])**：加载一个文件并使用参数执行它

文件描述符：一个小整数(small integer)，表示进程可以读取或写入的由内核管理的对象。进程从文件描述符0读取（标准输入），将输出写入文件描述符1（标准输出），并将错误消息写入文件描述符2（标准错误）。优先分配最小的未使用过的描述符

fork复制了文件描述符表，但是每个基础文件偏移量在父文件和子文件之间是共享的

dup：复制一个现有的文件描述符，返回一个引用自同一个底层I/O对象的新文件描述符。两个文件描述符共享一个偏移量

管道：作为一对文件描述符公开给进程的小型内核缓冲区，一个用于读取，一个用于写入。将数据写入管道的一端使得这些数据可以从管道的另一端读取。注意，写入结束后要关闭管道，否则会导致一直等待

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// user/sh.c
case PIPE:
  pcmd = (struct pipecmd*)cmd; // 把通用 cmd 转为 管道专用结构体

  if(pipe(p) < 0)              // 1. 创建管道 p[0]读, p[1]写
    panic("pipe");

  // --- 负责左边 (cmd1) 的子进程 ---
  if(fork1() == 0){            
    close(1);                  // 关闭标准输出
    dup(p[1]);                 // 把管道写入端(p[1]) 复制到 FD 1
    close(p[0]);               // 关闭不需要的读端
    close(p[1]);               // 关闭原始的 p[1]
    
    // 递归调用！继续去执行左边的命令
    runcmd(pcmd->left);        
  }

  // --- 负责右边 (cmd2) 的子进程 ---
  if(fork1() == 0){            
    close(0);                  // 关闭标准输入
    dup(p[0]);                 // 把管道读取端(p[0]) 复制到 FD 0
    close(p[0]);               // 关闭原始的 p[0]
    close(p[1]);               // 关闭不需要的写端

    // 递归调用！继续去执行右边的命令
    runcmd(pcmd->right);       
  }

  // --- Shell 父进程 (协调者) ---
  close(p[0]);                 // 关键：Shell 自己必须断开与管道的连接
  close(p[1]);                 // 否则读端永远等不到 EOF
  wait(0);                     // 等待左边结束
  wait(0);                     // 等待右边结束
  break;

同一个底层文件（叫做inode，索引结点）可以有多个名字（叫做link，链接）。只有当文件的链接数为零且没有文件描述符引用时，文件的inode和包含其内容的磁盘空间才会被释放

实验：sleep、pingpong

day 3 primes实验

管道存放的是带缓冲的字节流，而不是单独的数据。操作系统会自动协调顺序，不用手动控制

进程打开的文件描述符有限，不用的要立即关闭

进程的退出是逆序的，最末端的子进程先退出，一层一层直到父进程

day 4 find、xargs实验

1.find实验
  1. UNIX中，文件夹也是文件。结构体dirent存放文件的inode和名字，用来遍历文件夹。stat存放文件的详细信息，用stat(int fd,struct stat *st)访问。
  2. 递归读取文件夹时，注意”/.”和”/..”，避免死循环
2.xargs实验

  1. 用标准输入FD 0，通过管道传递参数

  2. 流程：输入字节流–>解析命令–>拼接出完整命令–>子进程中执行命令–>重置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 初始化参数数组、缓冲区
...
// 将xargs的参数放到参数数组中
...
// 从标准输入读取数据，存储在缓冲区 buf 中
    while (read(0, p, 1) != 0) {
        // 使用指针 p 遍历缓冲区，遇到空格或换行符时，将其替换为字符串结束符 \0
        if (*p == ' ' || *p == '\n') {
			
            *p = '\0';

            // 将参数添加到参数缓冲区 argsbuf 中
            *(pa++) = last_p;
			last_p = p+1;

            // 每当遇到换行符 \n 时，表示一组参数读取完毕，调用 run 函数执行程序，传递参数
            if (*p == '\n') {
				
				*pa = 0; 
				run(argv[1], argsbuf); 
				pa = args; 
			}
        }
        // 继续读取数据
        p++;
    }
// 如果最后一行不是空行，同样的逻辑再处理一次
...
// 等待所有子进程结束
    while (wait(0) != -1) {};
	exit(0);

day 5 系统调用

操作系统的作用：进行资源分配，并实现进程间的隔离与交互

宏内核：整个操作系统都驻留在内核中，这样所有系统调用的实现都以管理模式运行

微内核：最大限度地减少在管理模式下运行的操作系统代码量，并在用户模式下执行大部分操作系统

进程抽象：能防止一个进程破坏或监视另一个进程的内存、CPU、文件描述符等。它还防止一个进程破坏内核本身，这样一个进程就不能破坏内核的隔离机制。

操作系统中，用户无法直接操作硬件，也不能直接访问内核资源。通过系统调用，可以向内核请求服务：用户程序通过调用库函数间接发起系统调用，系统调用触发软件中断或陷阱，引发CPU切换到内核态，内核根据系统调用号确定要执行的服务，完成服务后，将结果或错误码存入用户程序的寄存器，并返回到用户态继续执行程序。

系统调用流程：用户调用跳板函数，将参数存在寄存器中–>跳板函数通过ecall指令，切换到内核态，将寄存器中的值保存的trapframe–>调用系统调用处理函数syscall()–> 根据trapframe中的系统调用编号，查表syscalls[]调用对应内核函数

user/user.h: 声明用户态函数原型。

user/usys.pl: 生成汇编跳板代码（entry stub）。

kernel/syscall.h: 定义系统调用号宏 (#define SYS_xxx)。

kernel/syscall.c: 在函数指针数组 syscalls[] 中注册处理函数，并添加函数声明。

kernel/sysproc.c: 编写具体的 C 语言实现逻辑uint64 sys_xxx(void)。

xv6启动第一个程序的流程：

  1. 上电，运行ROM中的引导程序。加载内核并跳转到内核入口_entry
  2. 设置初始栈，跳转到C语言入口函数start()
  3. 用mret指令，从机器模式转换到管理模式
  4. 内核初始化main()，调用userinit()创建第一个用户进程
  5. 加载/init程序
syscall-trace实验

流程：

  1. 在struct proc中添加mask，用掩码代表系统调用号。用argint(0,&dst)获取用户传入的掩码，并将掩码保存到myproc->mask中。

  2. 子进程也要跟踪，在fork()时将掩码复制给子进程

  3. 在进行系统调用syscall()后，用掩码判断是否需要跟踪，然后打印

sysinfo实验

流程：

  1. 添加系统调用

  2. 在sysinfo()中获取空闲内存和进程数量。内核页表和用户页表不同，需要将内核中的sysinfo结构体拷贝到用户空间：

    copyout(p->pagetable, dst_addr, (char *)&info, sizeof(info))

  3. 获取空闲内存：上锁acquire(&kmem.lock)，遍历 kmem.freelist 链表，遍历完后release。空闲内存=空闲页数 * PGSIZE

  4. 获取进程数量：静态数组 struct proc proc[NPROC] 管理所有进程，遍历proc数组得到进程数量

day 6 页表

1.页表

操作系统为每个进程提供私有地址空间和内存的机制。页表决定了内存地址的含义，以及物理内存的哪些部分可以访问。

RISC-V指令（用户和内核指令）使用的是虚拟地址，而机器的RAM或物理内存是由物理地址索引的。RISC-V页表硬件通过将每个虚拟地址映射到物理地址来为这两种地址建立联系。

虚拟地址：

虚拟地址

页表条目PTE：

页表条目

物理地址：

物理地址

虚拟地址中包含三级树结构，每个树是一个4KB的页表页，包含512个PTE。每个PTE记录下一级页表的物理位置，直到第三级PTE。在不同的进程中，虚拟地址可能相同，但由于页表中的映射不同，最终的物理地址也会不同。

地址转换过程：通过虚拟地址的前27位（三层页表）找到对应的PTE，PTE中的44位PPN与12位页内偏移组成物理地址。

2.TLB

处理器会对最近使用过的虚拟地址进行缓存，称为Translation Lookside Buffer，TLB。下一次访问时通过TLB得到物理地址，避免每次都需要读取三次内存寻址。切换页表时清空TLB。

day 7 页表

1.内核地址空间
  • 启动：上电后，从0x1000开始执行Boot ROM，将内核加载到0x80000000
  • 地址映射空间：对于低于 PHYSTOP 的虚拟地址，虚拟地址 == 物理地址。低于0x80000000的地址映射到I/O设备，高于0x80000000的地址映射到DRAM
  • 保护页：在内核栈下方设置一个未映射的页面，栈溢出时访问无效页，触发panic
  • 标志位：设置PTE的标志位，代码段可读可执行不可写，数据段可读可写不可执行
  • 空闲内存管理：物理内存中剩余的部分分配给用户进程，当内核运行某个进程时，会将该进程的根页表地址加载到 SATP 寄存器，CPU 随即切换到该进程的虚拟地址空间。
  • PGROUNDUP：一页终点，不小于a的PGSIZE的最小倍数；PGROUNDDOWN：一页起点，不大于a的PGSIZE的最大倍数，这与栈从高向低生长是两码事。

打印页表实验

流程：

  1. 遍历页表的512个PTE
  2. 检查标志位，仅被使用的页表打印
  3. 将PTE转换为物理地址
  4. 递归调用，打印每级页表

day 8 页表

内核栈：每个进程在内核中都有一个独立的栈，安全可靠。存放trapframe和内核函数调用链。

每个进程分配单独内核页表实验

实验目的：原生xv6中所有进程共享一个全局内核页表，存在安全隐患。

流程：

  1. 在struct proc中添加字段kernel_pgtbl
  2. 内核代码和硬件映射在所有进程中都一样。创建进程时，分配页表并复制全局内核页表中的页表项，并将用户页表的映射同步到进程的内核页表。
  3. 每个进程只访问自己的内核栈，所以可以把每个进程的内核栈映射到各自内核页表的固定位置
  4. 切换进程时注意，在调度器将 CPU 交给进程执行之前，加载进程的内核页表到SATP寄存器，切换到该进程对应的内核页表。切换回调度器线程时，切换回全局内核页表
  5. 释放内核栈，释放进程专属页表中的映射，并释放页表占据的空间，但不释放页表指向的物理页

day 9 页表

简化copyin、copyinstr实验

实验目的：原生xv6中内核读取用户态地址时需要模拟硬件，通过翻阅用户页表找到物理地址。简化copyin，将用户态页表复制到内核态，内核直接解引用用户态的指针。

要点：用户态页表每次发生变化时，内核态页表就需要同步更新

流程：

  1. 复制页表的函数，用于将用户态页表复制到内核态：遍历用户页表的指定范围，查找到有效的 PTE，获取其物理地址和标志位，然后在内核页表中建立相同的映射。注意标志位去除PTE_U，因为内核态没有权限读写带有 User 标志位的页
  2. 缩减内存的函数，用于内核页表和用户页表内存映射的同步：将程序内存从 oldsz 缩减到 newsz，但不释放实际内存
  3. 映射地址要低于PLIC，映射时进行检查
  4. 涉及到用户态页表的修改，都要将修改同步到内核页表，包括fork()、exec()、growproc()、userinit()
  • fork()：子进程复制完用户内存后，需要将新进程的用户页表复制到内核页表
  • exec()：加载新程序时，清除内核页表中对程序内存的旧映射，然后重新建立映射
  • growproc()：用户态页表扩大/缩小时，内核态同步扩大/缩小
  • userinit()：用户态初始化时，复制页表到内核

实验总结：创建进程时，分配了独自的内核页表，并将用户态页表中的映射复制到内核页表。切换到内核态后，satp寄存器指向内核页表。当用户程序要传递数据给内核时，内核通过copyin获取。copyin中将用户虚拟地址当作内核可直接访问的地址，触发MMU查阅内核页表寻址，找到物理地址后实现数据读写。

day 10 中断

trap机制

用户态和内核态间的切换叫做trap，包括三种情况：

  • 系统调用
  • 异常：Page falut、除0等
  • 设备终端

关键寄存器：

  • 程序计数寄存器PC
  • 表明当前mode权限的标志位
  • 控制CPU工作方式的寄存器
  • STVEC寄存器，指向了内核中处理trap的指令的起始地址
  • SEPC寄存器，在trap的过程中保存程序计数器的值
  • SSCRATCH寄存器

进行的操作：

  • 保存32个用户寄存器，以便恢复用户程序
  • 保存程序计数器
  • 将mode改为supervisor mode
  • 将SATP指向内核页表
  • 将堆栈寄存器指向位于内核的一个地址，因为需要一个堆栈来调用内核的函数
  • 跳入内核代码

总结trap的流程：保存现场-跳入内核-内核处理-恢复现场

ECALL

用户执行系统调用时，实际是调用一个库函数，把系统调用编号放进a7寄存器中，然后执行ecall指令

ecall只做三件事：

  1. 从user mode改到supervisor mode
  2. 保存程序计数器
  3. 将STVEC拷贝到程序计数器，让程序执行trampoline page的代码

trampoline：内核在每一个用户的页表最顶端，都强制映射了同一个物理页面

  • 原因：ecall不会切换页表，如果直接跳转执行内核代码，会因为没有内核态映射崩溃
  • 方式：内核提前把 stvec 寄存器的值设置成了这个 trampoline 页的起始地址
  • 结果：把用户的寄存器状态存下来，然后才真正将页表切换为内核全局页表
uservec函数

在trampoline起始时，需要保存寄存器的内容。在RISC-V中，supervisor mode下的代码不允许直接访问物理内存，所以只能使用页表中的内容。uservec将所有用户寄存器保存到trapframe中，并映射到用户页表中。然后让satp指向内核页表，切换到内核页表。

  1. 内核为每一个进程都分配了一个专属的物理页面，叫做 trapframe，内含32个空槽位来保存用户寄存器。内核把这个 trapframe 页面强行映射到了用户进程的页表里。
  2. 在进入到用户态之前，内核会将trapframe page的地址保存在SSCRATCH寄存器中，RISC-V有一个指令允许交换任意两个寄存器的值。而SSCRATCH寄存器的作用就是保存另一个寄存器的值，并将自己的值加载给另一个寄存器。

trapframe：

对于用户：进入内核态前，保存寄存器的值。返回用户态时再恢复寄存器的值。

对于内核：存放一些关键地址、程序计数器

day 11 中断

usertrap函数：判断trap的类型，并根据类型选择是否执行系统调用

  1. 更改STVEC寄存器，指向kernelvec

  2. 获取当前进程

  3. 使用trapframe保存程序计数器，避免SPEC寄存器被覆盖

  4. 找到进入usertrap的原因，判断是否系统调用

    如果是：

  5. 检查进程是否被杀死

  6. 程序计数器+4，以便恢复时执行ecall的下一条指令

  7. 打开中断

  8. 调用syscall，执行系统调用

  9. 检查进程是否被杀死

  10. 调用usertrapret函数

syscall函数：从寄存器a7获取系统调用号，调用内核函数sys_xxx()，返回值在寄存器a0中
usertrapret函数：设置stvec指向trampoline（为下一次trap），准备返回用户态的上下文
  1. 关闭中断，避免内核出错
  2. STVEC指向trampoline，执行sret返回用户空间
  3. 在trapframe中保存内核页表指针、用户进程的内核栈、usertrap函数的指针、CPU核编号
  4. 设置SSTATUS寄存器，SPP位置0表示用户模式，SPIE位置1打开中断
  5. SPEC寄存器恢复为之前的程序计数器值
  6. 根据用户页表生成相应SATP值
  7. 执行userret函数
userret函数：satp指向用户页表，恢复用户态上下文
  1. 切换至用户页表
  2. 将系统调用的返回值保存到SSCRATCH寄存器
  3. 交换SSCRATCH和a0寄存器，a0持有的是系统调用的返回值，SSCRATCH持有的是trapframe的地址
  4. 执行sret，切换至user mode，SPEC寄存器的值拷贝到PC寄存器，重新打开中断
backtrace实验

目的：打印用过函数的地址

要点：fp 指向当前栈帧的开始地址，sp 指向当前栈帧的结束地址。 （栈从高地址往低地址生长，所以 fp 虽然是帧开始地址，但是地址比 sp 高）。栈帧中包含函数返回地址ra8字节和上一层栈帧的地址fp8字节，剩下还有局部变量、寄存器等。

流程：

  1. 用汇编代码获取s0寄存器的值，即当前栈帧fp

  2. 递归调用函数，打印ra，直到fp跳出本页

day 12 中断

alarm实验

目的：模拟用户态中断，定时发出提醒

逻辑：用户态调用sigalarm；每发生一次中断，内核态在usertrap中计数。计数达到设定值后，拷贝trapframe，epc指向回调函数。返回用户态，执行回调。回调结束，调用sigreturn，恢复trapframe和epc。继续执行中断前的任务。

流程：

  1. 修改struct proc，添加字段：alarm_interval,alarm_ticks,alarm_handler,alarm_goingoff,alarm_trapframe

  2. 在allocproc()和freeproc()中，对上述字段进行初始化和释放

  3. 实现sys_sigalarm()：用argint()和argaddr()获取用户态参数，存进proc

  4. 实现中断：当定时结束，且没有其他定时器运行时，触发警报。

    保存trapframe中的寄存器

    将PC指针指向handler，执行回调函数

    上锁，设置goingoff为1

  5. 实现sys_sigreturn()：恢复trapframe中的寄存器；解锁，设置goingoff为0

day 13 惰性分配

页面错误异常

三种页面错误：加载页面错误、存储页面错误、指令页面错误，这些页面错误信息保存在 RISC-V 的两个寄存器中：scause：指示页面错误的类型（加载、存储或指令）；stval：保存无法转换的虚拟地址。其中，scause保存trap机制中进入supervisor mode的原因，页面错误也是通过trap机制进入内核态。

当出现了page fault，有3个极其有价值的信息，分别是：
●引起page fault的内存地址
●引起page fault的原因类型
●引起page fault时的程序计数器值，这表明了page fault在用户空间发生的位置

写时复制COW

标准fork中，父进程将内存完全拷贝给子进程，开销大。在 COW fork 中，父进程和子进程会共享相同的物理内存页面，而不是立刻复制内存。共享的页面被标记为只读。当父进程或子进程修改页面内容时，就会触发页面错误异常，执行操作：1.为子进程分配一个新的物理内存副本，为父进程分配一个新的物理内存副本。2.将新页面的物理地址映射到父子进程中产生页面错误的虚拟地址，并且更新页表中的权限为可读/写。3.返回到引发异常的指令位置，重新执行导致页面错误的写操作。

惰性分配

申请内存后，内核将新地址标记为无效。用户访问这些无效空间后触发错误，内核会分配一个新的物理页面，并将该虚拟地址映射到新页面上，更新页表中的该地址条目为有效状态，并重新执行触发异常的指令。

页面换出

进程内存需求超出物理内存时，系统将不常用的内存页面写入磁盘，将其PTE标记为无效，访问时触发异常，重新分配物理内存，从磁盘取回内存。

Lazy allocation实验

流程：

  1. 改造sys_sbrk()：申请增加内存时，只增加sz，不分配物理内存

  2. 改造usertrap()：判断中断原因，如果是缺页，通过STVAL获取缺页的虚拟地址va。若va不超出合法范围，分配一页内存并映射到页表

  3. 当内核复制用户页表时（copyin，copyinstr），内核可能访问到没分配的虚拟地址，此时需要立即分配

day 14 写时复制

COW实验

要点：在 COW 中，一页内存可能同时被父进程和多个子进程共享。用物理页引用数纪录有多少个进程映射同一个物理页

  • kalloc() 分配新页时，引用计数初始化为 1。
  • fork()时，引用计数加 1。
  • 发生COW拷贝或进程退出时计数-1。
  • kfree() 被调用时，只把计数减 1。只有当计数降为 0 时，才真正清空内存并还给空闲链表。

流程：

  1. 定义全局数组，记录每个物理页被多少个进程引用
  2. 改造uvmcopy()：不分配新内存，给对应页添加COW标志位，并将父进程的物理页映射到子进程，引用数+1
  3. 改造usertrap()：当向进程中写入时，触发trap，判断是COW导致的页面错误，则执行COW
  4. 实现COW：申请一页内存，将旧物理页的数据拷贝到新页，修改触发缺页的进程的 PTE，让它指向新物理页，恢复 PTE_W 写权限，并清除 PTE_COW 标志。旧页计数-1，如果到0就回收

day 15 多线程

线程状态包括：

●程序计数器（Program Counter），它表示当前线程执行指令的位置
●保存变量的寄存器
●程序的Stack。每个线程都有属于自己的Stack，Stack记录了函数调用的记录，并反映了当前线程的执行点

切换线程实验

要点：切换线程时，保存指定寄存器ra、sp、s0-s11。ra指向ret的返回值，sp指向栈。

流程：

  1. 定义寄存器结构体，存放寄存器对应值，并添加到线程中
  2. 汇编函数，通过a0、a1寄存器传递值
  3. 创建新线程，将sp指向栈顶，ra指向func，执行线程专属函数
  4. 轮询线程时调用线程切换函数
哈希表并发实验

目的：当两个线程同时计算出相同的哈希桶索引，并尝试插入新节点时，会发生覆盖

要点：在修改数据的put()函数中上锁，但如果是对整体上锁，会导致效率下降。解决方法是为每个哈希桶分配一把锁，仅当两个线程遇到同一个桶时才互斥。

线程屏蔽实验

目的：多个线程在跑循环，但必须保证所有线程都完成了第 N 轮，才能一起进入第 N+1 轮。

要点：当线程进入屏蔽后，上锁，计数+1。如果计数达到要求，重置计数并唤醒其他线程。如果没达到要求，线程睡眠（自动释放锁）

day 16 锁

竞态条件：多个线程或进程在没有同步控制的情况下，同时读写共享数据，导致最终结果取决于它们执行的相对先后顺序

自旋锁：当一个 CPU 尝试获取锁而锁被占用时，它会原地循环等待（自旋），直到锁被释放

  • 通过原子指令，设置spinlock结构体中locked的值，实现上锁或释放
Memory Allocator实验

目的：原始xv6中，所有CPU共享一个锁和空闲链表，多核并行时会发生大量锁争用

要点：

  • 给每个CPU分配独立的锁和空闲页面链表
  • 获取页面时，首先从当前CPU的链表中获取，如果不够则遍历其他CPU的链表，挪动一部分到本CPU的链表中
  • 获取当前CPU编号时，先关闭中断避免进程被调度到另一个CPU上

day 17 锁

Buffer Cache实验

目的：内存中有多个缓存块串成链表用来读写磁盘，用一个大锁保护。当不同CPU要操作缓存块时会发生严重的锁争夺。通过降低锁粒度来提高并行效率

要点：

  • 降低锁粒度：建立哈希桶，用n个桶存放缓存块，每个桶用一个锁保护

  • 给每个缓存块添加时间戳，记录上一次被使用的时间

  • 缓存池满了后，寻找最久没用（LRU）的缓存块

  • 驱逐锁：当要找的磁盘块不在桶中且桶内无空余空间，遍历其他桶找LRU。为防止不同CPU争抢，添加全局驱逐锁。只有拿到锁的CPU才能遍历桶

  • bufmap_locks 保护单个桶的链表结构，以及桶内所有节点的 refcnt

  • eviction_lock 保护所有桶的链表结构，但是不保护任何 refcnt

  • bufmap[n]是一个虚拟头节点，不存放数据，通过next指针来串联桶，否则在驱逐时需要进行深拷贝

流程：

  1. 初始化锁，将缓存区添加到桶中
  2. 获取桶号，上桶锁，遍历当前桶查询缓存区块是否已经在缓存区中
  3. 若不在缓存区中，释放当前锁，上驱逐锁
  4. 再次遍历当前桶查询缓存区块是否已经在缓存区中
  5. 若仍然不在缓存区，遍历所有桶，查找LRU
  6. 若找到LRU且不在当前桶，则将其驱逐

day 18 文件系统

文件系统分七层：

磁盘层：读写硬盘

缓冲区高速缓存层：缓存磁盘块并同步对它们的访问

日志记录层：保证多步磁盘操作的原子性

索引节点层：给每个文件分配一个唯一的ID

目录层：将每个目录实现为一种特殊的索引结点

路径名层：分层路径名

文件描述符层：提供一个统一的抽象接口