非连续内存分配的背景与需求
之前已经讲到操作系统的连续内存分配，但比如在WFA（worst-fit allocation，先拆最大块方法）中，随着分配的进行，较大的内存申请很可能将不再能一次满足。所以我们思考有没有一种方法将较为离散的内存块组织起来，组织成逻辑上的相对大块的内存。借用段式存储管理中的这张图，我们将这个过程示意如下：
另外，连续内存的申请和释放都伴随着一些麻烦，同时还不免地产生内外碎片。
非连续分配的提出就是为了提高内存的利用率和管理的灵活性。
- 允许程序使用非连续的物理地址空间
- 允许共享代码和数据
- 支持动态加载和动态链接
非连续分配的实现过程中需要解决的问题： 实现虚拟地址和物理地址的转换
- 软件实现：利用类似外排序的思路，灵活地组织处在不同区域的内存，但是开销大；
- 硬件实现：每执行一条指令都需要做转换，那么直接使用硬件做映射是比较好的。
非连续分配硬件辅助机制：如何选择非连续分配中的内存分块大小（拆多大？如何组织？）
- 段式存储管理（segmentation）
- 页式存储管理（paging）
访问不在当前段的地址的错误就叫段错误（segmentation fault），这在初学算法题时十分常见。当一个程序找不到某个地址时，它会认为你所需要的地址在其他段上，而不是说它不存在。
段式存储管理
段式存储管理概念
段表示访问方式和存储数据等属性相同的一段地址空间，对应一个连续的内存“块”，由若干个“段”组成进程逻辑地址空间。
进程的地址空间由多个功能不同的段构成：主代码段，子模块代码段、公用库代码段、stack、heap、初始化数据段、符号表等。
将各个功能区隔离开之后，段式存储就实现了更细粒度的灵活的分离与共享。段式存储在做内存保护方面有优势。
各个部分内部连续，但之间相对去耦合，从而实现（这里是相对底层的）复用。这和高级语言编程中加入函数和模块的考量是一致的。
段式存储的访问
利用基址+长度这种描述方法访问段的地址。思路如下：
段的地址可以用一个二元数来表示，其中一个是基址，原理上基址加指定的偏移，就可以完成重定位，即可找到段的地址。 二元数的另一个元素是长度，在重定位之前就要验证段长度是否会溢出（这又是经典的segfault了qwq）。
页式存储管理
页式存储和段式存储是两种不同粒度的管理策略，但是其总体思路是一致的，认识如下量方面即可：
- 单元划分的标准
- 单元访问方式
页式存储的基本单元
将分块进行较小的划分之后，由于数量增多，我们希望这种效率提高，基于二进制的位运算是符合这种目标的。 我们将2的n次方的内存片段作为页式存储的单元，如512、4k、8k。4k是很常见大小。
- 物理地址空间中的单元叫做物理页面，一般地，称为页帧（page frame），简称帧（frame）。
- 逻辑地址空间中的单元称为逻辑页面，一般地，称为页面，简称页（page）。
- 帧和页的大小必须相同。
页式存储的地址转换
首先看物理内存中的单元：帧
物理内存被划分为2的n次方大小的帧，其内存物理地址仍然可以用二元组（f,o）表示，f为帧号（占s位），o为偏移。 则物理地址为： $f*2^s+o$
例题：
页和帧有一定的对应关系，在两个对应的页和帧中，页内偏移和帧内偏移一致，但通常页号大小和帧号大小不同。
构建的逻辑地址合乎人的使用习惯，页号是连续的。而物理地址空间中的帧号并不是连续的。
注意：并不是所有的页都有对应的帧。
在这种情况下，在比较大的内存空间中，需要做的仅仅是简单映射：
页表
基本要点
- 每个进程都有一个页表，每一个页面都有一个页表项。
- 页表是按照逻辑页密排的，所以页号并不需要存入页表项。
- 页表项中只储存物理帧号以及一些标志位。
- 页表中的内容随着进程的运行状态而动态变化。为了表征这些变化所以引入标志位，比如存在位、修改位、引用位等（这些后续会讲到）。
例子：假定一个16位系统，物理内存32KB，页大小1k，则 - 有32页。09存储页内数据，AF存储页号。
- 页表有32项。
- 物理帧号的地址位数一般少于逻辑地址，因为并不是进程的每一个页面都要调入内存，所以物理帧号的位数小于页号位数。
解决页式存储管理的问题：
- 需要访问两次：使用缓存（快表）
- 页表可能非常大：间接访问（多级页表）
快表
快表（TLB，translation look-aside buffer）就是将最近使用过的页表存入CPU，使用caching的方式加快页表的查询对应。
- 如果TLB命中，则物理页号将会快速且并行地获取。
- 未命中时查询页表，随后更新TLB。
如果命中率高，那么TLB对于页表查询开销的改善作用是非常有效的。
多级页表
将线性页表转换为树形结构，即可构建多级页表，可以减小每一级的长度。
如果逻辑地址空间全满的话，对于存储空间来说，其实并没有非常显著的提升，但是实际使用过程中，会有很多空的分支，这样就可以节省一部分空间。
反置页表
另一种减小页表大小的方法。
由于多级页表是树形结构，对于大地址空间（虚拟地址），多级页表仍会变得非常繁琐。 而且因为每个进程都有独立的页表，所以页表的大小会随着进程的增加而增加。
为了解决这些问题，我们可以不让页表和逻辑地址空间的大小相对应，而是让页表与物理地址空间的大小相对应。这就是页寄存器和反置页表的思路。
在这种情况下，如果页面本身相对于页表项很大的话，页表的内存开销就不足为惧了。
具体的实现方法是，让每一个物理帧都和一个页寄存器相关联。页寄存器包含如下的标志位：
- 使用位（residence bit）：此帧是否被进程占用
- 占用页号（occupier）：对应的页号p
- 保护位（protection bits）
这种方法的好处在于：
- 大大减省页表占用内存
- 页表大小与逻辑地址空间相比往往很小
缺点在于其反转了逻辑，要能够依据帧号找页号（建立联系），同时在用页号查找时就相对困难。
- 对逻辑地址进行哈希，随后就可以在页寄存器反向建立的查找表（通过哈希的方法建立）中进行小范围查找。
- 这里还可以引入快表。尽管快表功耗大
- 如果有冲突需要遍历冲突项。
反置页表是在页寄存器的基础上引入PID（进程标识）一同哈希，随后与反置页表中指定哈希值处对应验证，如果不一样就说明有冲突，继续遍历冲突项。如果PID和虚拟基址都相同，则找到了对应的页表。多余的开销来自于hash冲突。总体仍然是一个很好的思路。
段页式存储管理
段式存储在做内存保护方面有优势，页式存储在内存利用和优化转移到后备存储方面有优势。
提出段页式因而是很自然的，通过这样的结合设计，既可以使用页式结构便利高效的内存利用，也可以使用段式的功能隔离、保护与共享。
段页式存储管理中的内存共享：
课后题知识点整理
可有效应对大地址空间可采用的页表手段是(多级页表和反置页表)
描述段管理机制正确的是：
- 段的大小可以不一致
- 段可以有重叠(是因为共享的需求？)
- 段可以有特权级
- 段与段之间是可以不连续的
描述页管理机制正确的是：
- 页表在内存中
- 页可以是只读的
- 页可以有特权级（*）
页表项标志位包括：
- 存在位(resident bit)
- 修改位(dirty bit)
- 引用位(clock/reference bit)
- 只读位(read only OR read/write bit)
