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, 存在二进制文件中
或者可以通过存的东西算出来;
运行的时候
- 调用
foo@plt跳转到PLT[foo_plt_ind], - 这一项会跳转
GOT[foo_got_ind]指向的地址 (记住PLT是代码段的东西) - 这个地址在在初始时指向
PLT[foo_plt_ind]的下一条指令 - 接下来的两条命令会将 foo 的 ID 压入栈中作为
后续调用动态链接器时的一个参数, 后跳转
PLT[0] PLT[0]会将GOT[1]压入栈中作为另一个参数, 然后跳转到GOT[2]的地址, 即动态链接器的指令地址- 链接器通过这两个参数计算出
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 存储页表的地址
页表的结构是硬件决定的 (但是可能提供多个页大小的选项, 可以供操作系统选择), 页面命中不需要操作系统的参与, 硬件就能完成:
- MMU 由虚拟地址生成页表项 (PTE) 的地址
- MMU 向主存/cache 请求和获取页表项的内容
- MMU 根据页表项的内容构造物理地址
- 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) 或者磁盘块地址
多级页表省的空间主要是有些节点的孩子是空, 如果真的都存满了, 比单级占的空间还大