虚拟地址
通过地址翻译, 可以利用统一的虚拟地址空间来为用户程序提供内存, 同时还能隔离不同进程增强安全性
基于分页的地址翻译涉及到页表和radix-tree这种数据结构, 以及 TLB 这样的部件, 具体看ICS/CSAPP
虚拟地址的引入也可以让进程间共享数据, 只需要将某段物理内存同时映射给两个不同的进程即可.
当然per-process的地址空间带来了进程切换时的cache问题: 需要冲刷TLB,
预热缓存等等. 解决方法很多, 可以给 TLB 引入 ASID
使得不同地址空间的同一虚拟地址可以同时被缓存(会有安全问题吗?), 顺便增强
TLB 冲刷的粒度控制.
缺页异常
把内存视为硬盘的cache, 那么就会出现访问虚拟地址时cache miss的情况. 这时就产生了缺页异常, 需要进exception handler从硬盘上读出被缓存的页
这里还有很多可说的, 例如可以把不常用数据压缩以节省内存, 压缩后的数据也能更快在硬盘上读写.
换页策略
- FIFO, 每次换出最早缓存的页
- Second-Chance, 在FIFO的基础上给每个活跃的页一次机会(如果FIFO队尾曾被访问过, 就移回队头)
- LRU, 算频率, 通常通过定期打标记来判断近一段时间是否活跃
- MRU, 在某些场合有用, 例如假设播放过的电影片段不会再立刻放一次
理论上最优的策略是换出在未来最晚被访问的页
大页
可以设置页的大小以减少TLB miss次数, 同时(在相同总内存下)降低页表的层数
物理内存管理
操作系统需要管理物理内存, 评价维度包括效率 利用率和Scalability
利用率
- 外部碎片: 未分配且无法利用的部分
- 内部碎片: 已分配但用不到的部分
感觉这两种划分得不是很有必要...
Buddy-System
只能分配页面的 \(2^k\) 倍大小的物理内存. 每次找到能容纳需求的最小块, 将其分裂成相等的两半直至恰好能容纳需求, 取走一块.
本质上是个线段树, 但是可以用若干个独立的链表串联相同大小的块(也即写成非递归的线段树)
若只考虑分配不考虑回收，那么任意时刻块的总数量不会超过 \(O(\log n)\) 个.
考虑 \(n\) 位二进制数字 \(B_n=10\ldots0\), 其中第 \(i\) 位为 \(1\) 表示有一个大小为 \(2^i\) 的块 每次划分出大小为 \(2^k\) 的块等价于计算 \(B_n'=B_n - B_k\), 其中 \(B_k=0\ldots010\ldots0\), 第 \(k\) 位为 \(1\) 每次分裂等价于二进制向高位借位, 利用均摊分析可以轻松得到比特翻转操作的上界, 根据位数立即可得任意时刻块数量的上界
实际上任意时刻, 特定大小的块至多有一个
freelist
因为空闲内存是空的, 因此可以任意摆布. 一种玩法就是用链表的形式串联起来, 这样每次的分配就是遍历链表-删除节点
SLAB
关键在于, 大块分配次数少且生存周期比较长, 小块分配频繁释放也频繁. 利用这一点可以结合 freelist + Buddy-System 来实现小块本地取 + 大块上锁统一分配。
利用Buddy-System分配大块内存, 然后划分成相等的若干小块, 这样小块内存分配直接从 SLAB 中取走, 几乎是 \(O(1)\) 的, 多核也有很好的表现.
一个小细节是可以把元数据放在 SLAB 的头部并保证 SLAB 按页面对齐, 这样释放的时候就可以快速查询元数据了.