Chapter 20 Paging: smaller tables
第 20 章 分页：较小的表
页表太大？消耗内存太多？
线性表的缺点之一...每个进程一个页表？？？
这样的性能开销是灾难级的...
1. 简单的解决方案：更大的页
更大的页 - 表示更小的页表
1.1. 问题
大内存页会导致每页内的浪费 - 称为 内部碎片（internal fragmentation）
结果是应用程序会分配页 但只用每页的一小部分...
内存很快就会充满...
2. 混合方法：分页和分段
2.1. 分页
分页就像是把一本大书分成很多小页。操作系统把内存分成一个个固定大小的小块，这些小块叫做“页面”（Page）。同样，程序的地址空间也被分成同样大小的小块，叫做“虚拟页”（Virtual Page）
优点：
简单易懂，管理起来方便。
不容易浪费内存，因为页面大小是固定的。
可以很好地利用内存，减少内存碎片。
缺点
有时候一个程序的逻辑结构（比如代码、数据等）会被分割到不同的页面里，不太直观。
如果页面太小，可能会有很多页面切换的开销；如果页面太大，可能会浪费内存。
2.2. 分段
分段就像是把一本书分成几个章节，每个章节是一个“段”（Segment）。每个段可以有不同的大小，比如一个段可以是代码，一个段可以是数据，一个段可以是堆（Heap），等等。
优点
很直观，因为每个段都有明确的含义（比如代码段、数据段等）。
可以根据程序的实际需求分配内存，不会浪费太多内存。
缺点
管理起来比较复杂，因为每个段的大小不一样。
容易产生内存碎片，特别是当很多小段被频繁分配和释放时。
2.3. 混合方法
混合方法就是把分页和分段结合起来用。操作系统先用分段把程序的地址空间分成几个逻辑部分（比如代码段、数据段等），然后再用分页来管理每个段里的内存。
优点
结合了分页和分段的优点：
逻辑清晰：分段可以很好地表示程序的逻辑结构（比如代码、数据等）。
高效管理：分页可以很好地管理每个段里的内存，减少内存碎片。
比单独使用分页或分段更灵活。
缺点
比较复杂，需要同时管理分段和分页
地址翻译的开销会稍微大一些，因为需要先找到段，再找到页
3. 多级页表
这种方法不依赖于分段，试图解决问题：
如何去掉页表中的所有无效区域，而不是将他们全部保留在内存中？
多级页表 multi-level page table
3.1. 优势
多级页表分配的页表空间，与你正在使用多个地址空间内存量成比例
它通常很紧凑，并且支持稀疏的地址空间
如果仔细构建页表的每个部分都可以整齐地放入一页中...从而更容易管理...
4. 反向页表
inverted page table
更极端的空间节省，这里我们保留一个页表，其中的项，代表了每个物理页...
4.1. 查找
现在要找到正确的项..就是要搜索这个数据结构，线性扫描是昂贵的...因此通常会建立一个散列表...以加速查找...
4.2. 启示
我们一开始就说过page tables are just data structures
You can do lots of crazy things with data structures, making them smaller or bigger, making them slower or faster.
本书的例子只是人类能做到的很多事情的两个例子...
5. 将页表交换到磁盘
we have assumed that page tables reside in kernel-owned physical memory.
但是页表有可能太大无法一次装入内存...这时候可以进行一部分的 swap 到 disk...
后面会再研究...
6. 作业（模拟作业）
这个有趣的小作业测试你是否理解了多级页表的工作原理。没错，上一句中“有趣”一词的使用存在一些争议。这个程序名为：paging-multilevel-translate.py
一些基本假设：
页面大小不切实际，只有 32 字节
所讨论进程的虚拟地址空间（假设只有一个）为 1024 页，即 32 KB
物理内存由 128 页组成
因此，虚拟地址需要 15 位（5 位偏移量，10 位 VPN）。物理地址需要 12 位（5 位偏移量，7 位 PFN）。
系统假设存在一个多级页表。因此，虚拟地址的高五位用于索引页目录；页目录项 (PDE)（如果有效）指向页表的某个页面。每个页表页面包含 32 个页表项 (PTE)。每个 PTE（如果有效）保存着该虚拟页面所需的转换信息（物理帧号，即 PFN）。
涉及好多底层的东西哇...我好犹豫要不要花时间在这上面...我现在只想花 20 时间 得到 80 经验，而不是 100 100...所以还是跳过了...
Last updated