进入Memory Management 部分，该文介绍 main memory。
Background
Main memory and registers are only storage CPU can access directly.
但主存访问速度慢于寄存器，可能导致memory stall
Protection：通过base和limit寄存器确保进程只能访问地址空间内的内存地址
地址绑定：将逻辑地址转换为物理地址，编译时、加载时、运行时
MMU：Memory Management Unit，硬件设备，负责逻辑地址到物理地址转换
Contiguous Memory Allocation
two partitions: OS and user processes(low and high memory)
逻辑地址为
Variable Partition
根据需求从hole(空闲内存区域)中分配内存，但会产生碎片(external fragmentation)
- First-fit: Allocate the first hole that is big enough
- Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size
- Produces the smallest leftover hole
- Worst-fit: Allocate the largest hole; must also search entire list
Produces the largest leftover hole
很明显，不管哪种方式都会造成很多fragmentation，可通过compaction解决，但效果有限
Non-contiguous Memory Allocation
Paging
简而言之，将物理内存和逻辑内存都按一定大小进行划分，分别称为frame(帧)和page(页)，由page table进行映射(可减少external fragmentation，但无法减少internal fragmentation)
在分页内存管理系统中，CPU生成的逻辑地址会被划分为页号（p）和页偏移（d）两部分，用于实现从逻辑地址到物理地址的转换。
- 页号（p）：页号是页表的索引，页表存储了每个逻辑页在物理内存中的基地址，通过页号可在页表中找到对应的物理帧号，建立虚拟页到物理帧的映射关系。例如，若页表中页号3对应的物理帧号为7，当CPU生成的逻辑地址页号为3时，就能找到对应的物理帧7。
- 页偏移（d）：页偏移与页表中查到的物理帧基地址组合，确定内存单元的物理地址。由于页和帧大小相同，页偏移在虚拟页和物理帧中表示的位置相同，所以能直接与物理帧基地址结合定位物理地址。如页大小为4KB（4096字节），页偏移为100，若物理帧基地址为8192，那么物理地址就是8192 + 100 = 8292。
- 位分配：对于给定的逻辑地址空间
和页大小 ，页号占 位，页偏移占 位。例如，逻辑地址空间为 （32位地址空间），页大小为 （4KB），则页号占32 - 12 = 20位，页偏移占12位。这种位分配方式能确保逻辑地址正确映射到物理地址。
TLB(Translation Lookaside Buffer)
页表查找的时间开销较大(两次内存访问)，TLB是一个小的高速缓存，存储了页表中的常用内容，用于加速逻辑地址到物理地址的转换。命中(hit)时，直接从TLB中获取物理帧号，否则从页表中获取。
Memory protection implemented by associating protection bit with each frame to indicate if read-only or read-write access is allowed.
Structure of the Page Table
One simple solution is to divide the page table into smaller units
- Hierarchical Paging：多级页表，类似于B+树？
- example：两级页表
- Hashed Page Tables
- Inverted Page Tables
Hierarchical Paging
| 优点 | 缺点 |
|---|---|
| 降低内存开销：仅映射活跃使用的地址空间部分 | 增加内存访问延迟：转换虚拟地址需遍历多级页表，产生额外开销 |
| 可扩展性：适应更大地址空间，内存开销不会成比例增加 | 页表尺寸增大：在大地址空间系统中，存储页表项消耗大量内存 |
| 改善局部性：利用空间局部性，虚拟页常映射到相邻物理帧 | 实现复杂：相比扁平页表，实现和管理更复杂 |
| 灵活性：可根据系统需求和内存特性采用不同层次结构 | 碎片化：在稀疏地址空间系统中，易出现碎片化问题 |
Hashed Page Tables
| 优点 | 缺点 |
|---|---|
| 降低内存开销：仅映射活跃使用的地址空间部分 | 冲突处理：哈希冲突可能导致查找效率降低 |
| 灵活性：适应不同地址空间大小 | 实现复杂：哈希函数设计和冲突处理复杂 |
| 降低内存访问延迟：查找效率高 | 内存开销：哈希表存储开销较大 |
Inverted Page Tables
Inverted Page Table即反向页表，是一种与传统正向页表不同的内存分页管理方式，用于解决大地址空间下页表占用内存过多的问题 。
- 基本原理：传统页表以进程为单位，每个进程都有自己的页表，记录该进程的虚拟页到物理帧的映射关系。而反向页表则以物理帧为索引，每个物理帧在反向页表中对应一个条目。条目中记录了存储在该物理帧中的页面所属的进程标识符（PID）以及该页面在进程虚拟地址空间中的页号 。
- 优势：反向页表显著减少了页表占用的内存空间。在大地址空间系统中，若采用传统页表，每个进程的页表可能会占用大量内存；而反向页表只需为每个物理帧维护一个条目，无论有多少进程，页表的大小只取决于物理帧的数量，从而有效降低了内存开销 。
- 不足与解决办法：反向页表的主要问题是查找效率较低。在进行地址转换时，由于无法直接通过虚拟页号找到对应的物理帧号，需要遍历整个反向页表来匹配进程标识符和虚拟页号。为解决这个问题，通常会结合使用转换后备缓冲器（TLB）。TLB是一种高速缓存，存储了近期使用的虚拟页到物理帧的映射关系。当进行地址转换时，先在TLB中查找，若找到（TLB命中），则可快速获取物理帧号；若未找到（TLB未命中），再遍历反向页表进行查找，并将查找到的映射关系添加到TLB中，以便下次快速访问 。
Swapping
用于在内存资源紧张时，将暂时不使用的进程或部分数据从内存转移到磁盘的后备存储（backing store）中，腾出内存空间给更需要的进程使用；当被交换出去的进程或数据需要再次使用时，再将其从磁盘调回内存。
