计算机组成原理：简单页表和多级页表（虚拟内存的映射）
我们的指令和数据，都必须先加载到内存，才会被CPU拿去执⾏。但是程序并不能直接访问到物理内存。从可以知道，程序是怎么装载到内存中执⾏的。
那么，这些虚拟内存地址究竟是怎么转换成物理地址的呢？
内存保护的主要⽬的是防⽌某个进程去访问不是操作系统配置给它的寻址空间
女星名单简答页表
想要把虚拟内存地址，映射到物理内存地址，最直观的⽅法，就是来键⼀张映射表。这个映射表，能够实现虚拟内存⾥⾯的页，到物理内存⾥⾯的页的⼀⼀映射。这会映射表，在计算机⾥⾯，就叫做页表（page table）
页表这个地址转换的办法，会把⼀个内存地址分成页号（Directory）和偏移量（Offset）两个部分。以⼀个32位的内存地址为例：前⾯的⾼位，就是内存地址的页号，后⾯的低位，就是内存地址的偏移量
做地址转换的页表，只需要保留虚拟内存地址的页号和物理内存地址的页号之间的映射关系就可以了。
同⼀个页⾥⾯的内存，在物理层⾯是连续的
总结⼀下，对于⼀个内存地址转换，其实就是这样三个步骤：
1. 把虚拟内存地址，切分成页号和偏移量的组合；
2. 从页表⾥⾯，查询出虚拟页号，对应的物理页号；
3. 直接拿物理页号，加上前⾯的偏移量，就得到了物理内存地址
看起来这个逻辑似乎很简单，很容易理解，不过问题马上就来了清华马艺妮
32 位的内存地址空间，页表⼀共需要记录 个到物理页号的映射关系。这个存储关系，就好⽐⼀个 ⼤⼩的数组。⼀个页号是完整的 32 位的4 字节（Byte），这样⼀个页表就需要 4MB 的空间。听起来 4MB 的空间好像还不⼤啊，毕竟我们现在的内存⾄少也有 4GB，服务器上有个⼏⼗ GB 的内存和很正常。
但是，这个空间⼜不⽌占⽤⼀份。我们每⼀个进程，都有属于⾃⼰独⽴的虚拟内存地址空间。这也意味着，每⼀个进程都需要这样⼀个
女孩子生日送什么好页表。不管我们这个进程，是个本⾝只有⼏ KB ⼤⼩的程序，还是需要⼏ GB 的内存空间，都需要这
样⼀个页表
这还只是 32 位的内存地址空间，现在⼤家⽤的内存，多半已经超过了 4GB，也已经⽤上了 64 位的计算机和操作系统。这样的话，⽤上⾯这个数组的数据结构来保存页⾯，内存占⽤就更⼤了。那么，我们有没有什么更好的解决办法呢？
多级页表
仔细想⼀想，我们其实没有必要存下这 2^20 个物理页表啊。⼤部分进程所占⽤的内存是有限的，需要的页也⾃然是有限的，我们只需要去存那些⽤到的页之间的映射关系就好了。
也就引⼊了多级页表（Multi-Level Page Table）。那为什么不⽤哈希表呢？（哈希表有哈希冲突，⽽且顺序乱，不符合局部性原理）
中国第一部动画片我们先来看⼀看，⼀个进程的内存地址空间是怎么分配的。在整个进程的内存地址空间，通常是“两头实，中间空”。在程序运⾏的时候，内存地址从顶部往下，不断分配占⽤的栈的空间。⽽堆的空间，内存地址则是从底部往上，是不断分配占⽤的。
所以，在⼀个实际的程序地址⾥⾯，虚拟内存占⽤的地址空间，通常是两端连续的空间。⽽不是完全随机的内存地址。⽽多级页表，就特别适合这样的内存地址分布。
我们以⼀个4级的多级页表为例，来看⼀下，同样⼀个虚拟内存地址，偏移量的部分和上⾯简单页表⼀样不变，但是原先的页号部分，
郑家榆我们把它拆成四段，从⾼到低，分成 4 级到1 级这样 4 个页表索引。
对应的，⼀个进程会有⼀个 4 级页表。我们先通过 4 级页表索引，到 4 级页表⾥⾯对应的条⽬（Entry）。这个条⽬⾥存放的是⼀张 3 级页表所在的位置。4 级页⾯⾥⾯的每⼀个条⽬，都对应着⼀
张 3 级页表，所以我们可能有多张 3 级页表。
202202
到对应这张 3 级页表之后，我们⽤ 3 级索引去到对应的 3 级索引的条⽬。3 级索引的条⽬再会指向⼀个 2 级页表。同样的，2 级页表⾥我们可以⽤ 2 级索引指向⼀个 1 级页表。
⽽最后⼀层的 1 级页表⾥⾯的条⽬，对应的数据内容就是物理页号了。在拿到了物理页号之后，我们同样可以⽤“页号 + 偏移量”的⽅式，来获取最终的物理内存地址。
我们可能有很多张 1 级页表、2 级页表，乃⾄ 3 级页表。但是，因为实际的虚拟内存空间通常是连续的，我们很可能只需要很少的 2级页表，甚⾄只需要 1 张 3 级页表就够了
事实上，多级页表就像⼀个多叉树的数据结构，所以我们常常称它为页表树。因为虚拟内存地址分布的连续性，树的第⼀层节点的指针，很多就是空的，也就是不需要有对应的⼦树了。所谓不需要⼦树，其实就是不需要对应的 2 级、3 级的页表。到最终的物理页号，就好像通过⼀个特定的访问路径，⾛到树最底层的叶⼦节点。
以这样的分成 4 级的多级页表来看，每⼀级如果都⽤ 5 个⽐特表⽰。那么每⼀张某 1 级的页表，只需要 2^5=32 个条⽬。如果每个条⽬还是 4 个字节，那么⼀共需要 128 个字节。⽽⼀个 1 级索引表，对应 32 个 4KiB 的也就是 16KB 的⼤⼩。⼀个填满的 2 级索引表，对应的就是 32 个 1 级索引表，也就是 512KB 的⼤⼩。
我们可以⼀起来测算⼀下，⼀个进程如果占⽤了 1MB 的内存空间，分成了 2 个 512KB 的连续空间。那么，它⼀共需要 2 个独⽴的、填满的 2 级索引表，也就意味着 64 个 1 级索引表，2 个独⽴的 3 级索引表，1 个 4 级索引表。⼀共需要 69 个索引表，每个128 字节，⼤概就是 9KB 的空间。⽐起 4MB 来说，只有差不多 1/500。
不过，多级页表虽然节约了我们的存储空间，却带来了时间上的开销，所以它其实是⼀个“时间换空间”的策略。原本我们进⾏⼀次地址转换，只需要访问⼀次就能到物理内存地址。但是，⽤了4级页表，我们就需要访问4次内存，才能到物理页号了。
问题是：内存访问其实⽐Cache要慢很多。我们本来只是要做⼀个简单的物理地址转换，现在却要多了访问多次内存。对于这个时间性能的损失，有什么好的办法吗？
总结
如何灭老鼠
多级页表就像⼀棵树，因为⼀个进程的内存地址相对集中和连续，所以采⽤这种页表树的⽅式，可以⼤⼤节省页所需要的空间。⽽因为每⼀个进程都需要⼀个独⽴的页表，这个空间的节省是⾮常客观的
在优化页表的过程中，我们可以观察到，数组这样紧凑的数据结构，以及树这样稀疏的数据结构，在时间复杂度和空间复杂度的差异。另外，纯粹理论软件的数据结构和硬件的设计也是⾼度相关的。
发布评论