为什么要做内存管理？
内存太多，提高利用率 -> 内存不够，需要闪转腾挪
内存布局和分区分配
内存管理的第一个问题是如何在内存区中同时加载多个应用程序
将内存分区，不同程序加载进不同分区
-> 指令中的哪些数值是地址？
编译器在链接时标记了哪些是地址，可以在加载时动态修改
古早时期程序在运行前就知道所需内存的上限，且可以控制的内存区域<=物理内存
动态分区分配：程序加载执行时，分配一个进程，一次性指定某个地址连续的分区，此后就不再变化
-> 通过基于硬件的分段机制（段基址 + 长度）动态调整加载地址，硬件自动完成偏移计算和长度检查
操作系统需要维护所有进程的已分配分区，以及空闲分区 empty-block 的数据结构
如何存储内存布局？
- Bitmap and list
- 链表：标记 Hole (free)/Proc (occupied)、起始地址、长度、next 指针
分区管理分配算法：
- 分配时寻找 >= 进程要求的分区，若大于则分割合适的大小出来，剩下的仍然空闲；
- 回收时查阅当前分区状况，完成不同的回收操作。
分配哪个分区给进程？
- first-fit：第一个满足要求的分区
- 分配和释放的时间性能好，可以将较大空闲块保留在内存高端
- 但是随着低端分区不断划分，每次分配时查找时间会增加
- next-fit：从上次分配的分区开始查找，找到第一个满足要求的分区
- 分配和释放的时间性能好，空闲块分布均匀
- 但不易保留较大空闲块
- best-fit：满足要求的最小空闲分区
- 可以保留较大空闲块
- 但会形成很多碎片
- worst-fit：满足要求的最大空闲分区
buddy system：将块按照 2^i 大小组织，初始状态只有一个块，每次分配块时按最小的可用空闲块，如果还是过大就将其不断二分，直到满足要求
按二叉树形式组织内存布局
分页机制
内存不够用怎么办？
swapping：将进程放进硬盘里，有需要的时候再拿出来加载到内存
-> 交换哪些程序？
回收处于等待状态进程的分区，换出后状态转为挂起
内存覆盖技术：划分功能模块，确定覆盖关系，执行前预先加载和交换 -> 过于复杂，而且需要手动操作
能让机器自动完成覆盖和交换吗？
虚拟存储：
- 一个或多个进程的程序段、数据段、堆栈段总和可以大于物理存储空间
- 进程中的各段不必完全装入内存，就可启动进程运行
- 操作系统定时将暂时不用的信息换出内存，需要时再换入
怎么切块？怎么使用块？如何知道什么时候“需要”某块内存（被访问、即将被访问）？
Paging：将逻辑地址空间划分为固定大小的页
概念：page, frame, page table
分页后的逻辑地址由两部分组成：页号 addr/page size; 页内偏移 addr%page size
物理空间按页大小划分成页面，使用页表 page table 记录虚拟页和物理页面的对应关系（虚拟页号->物理帧号，页内地址是一致的）
内存中的进程可以是不连续的物理页，但映射为连续的虚拟地址。
如何感知程序需要哪个块？
MMU (memory management unit)在 CPU 和内存之间，会检测每个 CPU 访存操作，并发现程序在运行中使用了哪个块。
触发缺页异常（需要的块不在物理内存中）时，如果有空闲物理页，就直接分配一页；若没有，按照页面置换算法选择将被换出的物理页，将对应虚拟页写回外存，然后将要访问的页装入物理页，修改页表。
页表设计
页大小 4kB (2^12 byte)；页表项数不能太多，否则页表本身占用过多内存
如果只用一个页表完成全部映射，大部分进程并不需要那么多虚拟地址空间，但这样会映射全部的虚拟地址空间，造成内存浪费
-> 多级页表：经过间接引用将页号分为 k 级，建立页表“树”
每级页表所占的内存都是整数个 page，便于内存分配对齐。
多级页表中虚拟地址的构成：第 i 级页表的索引 + 页内偏移
上一级页表的页表项内容是下一级页表的物理地址，最后一级页表项中是物理页帧号，这样可以一级一级地通过虚拟地址找到它的页表项。
e.g. X86 页表结构
多级页表可以节省内存：如果某个一级页表的页表项没有被用到，就不需要创建这个页表项对应的二级页表了。
(页大小/页表项大小) 算出一页中可以容纳的页表项数，从而得到所需的地址位数：
- PageSize = 2^x bytes,
- PageTableEntrySize = 2^y bytes
- 页内偏移位数 x，每级页表索引位数 x-y
e.g. RISCV 的 sv39 三级页表机制：
- PageSize = 4 kB = 2^12 bytes，因此页内偏移有 12 位
- PTESize = 8 bytes = 2^3 bytes
- 一页可以容纳 PageSize/PTESize = 512 = 2^9 个页表项，因此页表索引位数有 9 (= 12-3) 位
- 使用三级页表，一共 9+9+9+12 = 39 位虚拟地址
- 虚拟内存空间中有 4kB 的页，2^9*4 kB = 2^21 bytes = 2 MB 的大页，2^9*2 MB = 2^30 bytes = 1 GB 的大大页
页表项中除了映射的物理页帧号，还存储了该页面的一些属性：
e.g. X86 页表项结构
多级页表增加了访存时间，为了弥补这一点，发明了其他策略：TLB（Translation Lookaside Buffer，在CPU 中，缓存近期访问的页表项）、cache、prefetch
页面置换
缺页（访问的虚拟地址没有对应的物理页），而且已经没有空闲物理页时，需要进行页面置换
在外存中采取特殊格式存储未被映射的页面，访问时将其加载进内存
页面置换算法选择哪个现存的物理页被换出，目标是尽可能减少页面的置换次数。
局部页面置换算法：选择范围仅限于当前进程占用的物理页
- OPT
- 选择在未来最长时间不访问的页面
- 最理想情况，无法实现，作为实际置换算法的性能评价依据
- FIFO
- 维护一个记录所有位于内存的虚拟页链表，按驻留内存的时间排序
- 性能较差，换出的页面可能是经常访问的
- Belady 现象：进程分配物理页数量增加时，缺页可能反而增加
- 原因是物理页数量增加后，留在内存中的内容和增加前无关
- LRU
- 维护一个按最近访问时间排序的虚拟页链表 / 最近使用页面的栈
- 开销比较大
- LFU
- 置换访问次数最少的页面
- 一开始访问频繁，但后来很少访问的页面很难换出去
- Clock
- 在页表项中增加访问位，页面组织成环形链表；指针指向最先换入的页面，从此开始顺序查找未被访问的第一个页面
- 周期性地清除访问位：如果某页被访问了，先将访问位置零再跳过它，这样访问位为 1 意味着这个页面在过去时钟转一圈的时间里被访问过
- LRU 和 FIFO 的折中
- enhanced：增加修改位（淘汰修改过的页面还需要写回硬盘，使得其置换代价大于未修改过的页面，所以优先淘汰没有修改的页，减少磁盘操作次数），在写操作时将其置位，同样周期性地清除，清除时写回磁盘；遇到全零属性时换出
全局页面置换算法：选择范围是所有可换出的物理页
基于进程频繁访问的页面，为其分配可变数目的物理页
需要一个额外的数据结构 frame map 把物理页映射到 <进程，虚拟页> 对
-> 进程频繁访问哪些页？
Working set 工作集 W (t, delta): 当前时刻 t 前的一段时间 delta 之内，进程访问的页面集合
一个程序的工作集是抖动的，它剧烈扩张和收缩时，性能会发生极大变化
常驻集：当前时刻，进程实际留在内存当中的页面集合
希望常驻集 >= 工作集，保持尽可能的贴合
- Working set 工作集置换算法
- 换出在时间窗口 T 内没有被访存的物理页，并缩小常驻集；如果发生缺页异常，就换入
- 问题：需要周期性地打断程序，释放页面，不现实
- Page Fault Frequency 缺页率置换算法
- 缺页率：缺页次数/内存访问次数
- 调节常驻集大小，使得每个进程的缺页率保持在合理范围内
- 缺页时，计算从上次缺页到现在的时间间隔，大于时间窗口 T 则换出所有在此期间没有被访问的页，<= T 则增加缺失的页面到工作集中
- 相对现实，只在缺页的时候一次性处理换入和换出
Linux 的内存管理
希望永远有空闲页面可用，维护一个线程 kswapd 收集空闲页面；当操作系统发现可用物理内存已经少到一定程度（低于一个常量 low watermark）时，就唤醒 kswapd，按照类似 clock 算法的模式查找并释放 access bit = dirty bit = 0 的页，直到可用页面数高于 high watermark，停止。
-> 系统中有若干 (low watermark) 个物理页从来不分配出去，浪费了；但是每次分配内存时，只要从这 <= high watermark 个页中拿一个出去即可，不需要再扫描
如果可用页面掉到一个非常危险的数量 min watermark，操作系统就冻结调度器，所有进程都进入 ready 状态，等到 kswapd 回收完足够的页面，再恢复调度器。
-> 为了用户体验，避免系统阻塞，一般在到达这步之前就强制杀死进程、回收内存
段地址空间
段机制的设计思路：把一个程序的空间切成若干个连续的段，相同属性的内容都放在一起
这样，编译器在链接的时候就可以把一片地址区域赋予一段属性，采取相应的措施
-> 段页结合式：每个段里有若干个页
段访问：基址 + 偏移
硬件实现：段表记录段对应的虚拟地址及其长度，访存时使用段号检索段表，得到基址和段长度，检测是否越界，加偏移
段相对页的优势：段表和段 TLB 都可以做得很简单
但段机制最大的问题是要求其内存必须是连续的，很难分配和管理