408

趁这个机会回顾下基础知识

哪天被开了就考研去

计算机系统

流水线

相联

t = m - s - b

直接映射

i % n 缺点是容易冲突, 导致还有空间但是频繁换出

组相联

i % s, 每组有多个槽位, 即使冲突也能尝试放在空余的槽里

几路组相联就是每组有多少个槽位

但是查找和写入的时候需要遍历每个组的槽

全相联

不需要哈希了, 直接遍历所有位置, 有空就往里放

查询的时候也要最坏遍历 n 次

链接

动态链接

模块用到动态库代码时就会在代码段增加 过程链接表 (PLT), 在数据段增加 全局偏移量表 (GOT)

GOT 在加载时由动态链接器重定位

  • PIC 数据: 对于每个模块, 无论被如何加载, 代码段和其数据段的相对位置不变; 同一个模块中的代码对数据 x 的访问就可以利用 GOT[x] 中存储的地址实现; 跨模块的访问可以通过 GOT 间接访问

&GOT[x] 是通过调用该变量的指令地址 (上一条语句的 PC 寄存器的值), 和一个编译期计算 (&GOT[x] - (&当前指令)) 好的 offset 相加得出的;

  • PIC 函数: 代码段可能被加载到任何位置

编译时可以给要用到的每个未确定的符号 (foo@plt) 进行编码 foo_plt_ind 和 foo_got_ind, 存在二进制文件中 或者可以通过存的东西算出来;

运行的时候

  1. 调用 foo@plt 跳转到 PLT[foo_plt_ind],
  2. 这一项会跳转 GOT[foo_got_ind] 指向的地址 (记住 PLT 是代码段的东西)
  3. 这个地址在在初始时指向 PLT[foo_plt_ind] 的下一条指令
  4. 接下来的两条命令会将 foo 的 ID 压入栈中作为 后续调用动态链接器时的一个参数, 后跳转 PLT[0]
  5. PLT[0] 会将 GOT[1] 压入栈中作为另一个参数, 然后跳转到 GOT[2] 的地址, 即动态链接器的指令地址
  6. 链接器通过这两个参数计算出 foo 的运行时地址, 写入 GOT[foo_got_ind]中, 然后跳转到 foo 的地址, 开始执行 foo

后续调用时步骤 2. 就直接跳转到正确的 foo 地址了

回过头看其实完全不需要走一层 PLT, 完全可以 “判断 GOT[foo_got_ind] 是否为空, 是的话就计算地址, 不是的话就直接调用”, PLT 实际上是通过跳转实现了这个 if 判断

当不需要惰性绑定的时候, gcc 也提供了 -fno-plt 选项可以不使用 PLT

库打桩

异常

异常处理前会保存状态, 哪怕之前运行在用户态, 也会保存在内核栈而非用户栈

异常处理程序都跑在内核模式

异常分为:

中断 陷阱 故障 终止

只有中断是异步的, 每次完成当前指令后 CPU 会检测中断引脚, 如果有, 就跳转到相应的执行, 完成后执行下条指令

陷阱是主动调用, 返回后执行下条指令

故障如果可以修复 (例如缺页), 就在修复完成后返回当前指令, 否则 abort

终止一般是硬件错误 (例如 ram 某位损坏被奇偶校验检测出来), 直接 abort

用户态 内核态

CPU 中控制寄存器有一位用于判断当前是用户态还是内核态

用户模式不能:

  • 执行特权指令: 停止处理器、改变模式位、发起 IO
  • 访问内核区的代码和数据

进程切换的过程也是在内核态 (时间片定时器等的中断触发的)

信号

信号就像轻量化的异常

不同的信号对应不同的二进制位, 只有收到和没收到两种, 不会排队

进程会在从内核态返回用户态时检查信号, 检查到第一个就执行这一个的 handler

也就是说信号发送和处理最晚可能延后一个 CPU 时间片加再次调度到此进程的时间

pause() 可以等待信号

信号处理程序应该避免再被中断, 例如可以通过 write 替代 printf; 一些可能被信号处理程序修改的共享变量应该用 volatile 避免被编译期优化

C C++ 的异常

C 有一种 setjmp/longjmp 函数, 可以保存当前位置, 并且在当前函数栈中的函数返回到这个位置, 但是不会自动清理资源

C++ 的 throw/catch 是会清理的

进程

shell 其实就是帮你用 fork 和 execve 跑别的程序

进程终止后不会被立刻回收, 需要等待父进程主动接受信号 SIGCHLD 回收 (这里的回收主要指调用 wait() 获取下面的信息, 告诉内核我已经拿到了, 不需要再保留了)

终止后大部分资源已经回收了, 但扔占用:

  • PID 等进程标识信息
  • 退出状态 (返回码)
  • 供父进程查询的进程退出记录

如果父进程提前终止, 孤儿进程会人 init 进程当父进程

虚拟内存

内存管理单元 (MMU): 将虚拟地址转换为物理地址, 并检查内存访问是否合法

页表: 将虚拟页映射到物理页, 自身存放在物理内存中

CPU 中的页表基地址寄存器 PTBR 存储页表的地址

页表的结构是硬件决定的 (但是可能提供多个页大小的选项, 可以供操作系统选择), 页面命中不需要操作系统的参与, 硬件就能完成:

  1. MMU 由虚拟地址生成页表项 (PTE) 的地址
  2. MMU 向主存/cache 请求和获取页表项的内容
  3. MMU 根据页表项的内容构造物理地址
  4. MMU 向主存/cache 请求物理地址上的数据, 由他们返回给 CPU

如果未命中(页表项中的有效位为 0), 则触发缺页异常, 由 操作系统的异常处理程序 处理; 程序处理完成后会更新内存中的 PTE 有效位, 返回到原先进程的导致缺页异常的指令; CPU 重新将引起缺页的虚拟地址发送给 MMU, 走页面命中的流程

快表 TLB (Translation Lookaside Buffer): MMU 中的高速缓存, 可能是 sram、cam 等, 是查页表 (第 1 2 步) 这一动作的缓存, 可以直接根据虚拟地址得到物理页框号; 是一个相联程度高的组相联缓存

缓存是使用物理地址的字段做 key 的, 而 TLB 是虚拟地址

单级页表

设:

  • n 为虚拟内存的地址位数
  • p 为页大小(字节)
  • m 为物理内存的地址位数

2 ** (n - p) 就是页表项 PTE 的个数

虚拟地址的 n 位中, 前 n - p 位用于确定哪个页表项; 后 p 位用作页内偏移, 等找到哪个 PTE 后参与计算

可以看到单级页表的总大小基本就是页大小节省下来的

以 4 字节的 PTE 大小为例, 每个页表项通常包含:

  • 物理页框号: 指向对应的物理页框 (m - p) 位
  • Present / Valid 位: 表示映射是否有效,具体语义取决于架构
  • R/W 权限位: 是否允许写入
  • U/S 权限位: 用户态是否允许访问
  • Accessed 位: 页面是否被访问过
  • Dirty 位: 页面是否被写过
  • 其他控制位: 如缓存策略、执行权限等,取决于架构

多级页表

k 级页表的虚拟地址本划分成了 k 个虚拟页号 (VPN), 和一个片内偏移(VPO)

  • 前 j in [1, k - 1] 级页表的 PTE 指向 j + 1 级页表的基地址 (物理地址)
  • 第 k 级页表的 PTE 指向物理页号 (PPN) 或者磁盘块地址

多级页表省的空间主要是有些节点的孩子是空, 如果真的都存满了, 比单级占的空间还大

计网