C6 分页：介绍
操作系统有两种方法来解决大多数空间管理问题，第一种是将空间分割成不同长度的分片，就像虚拟内存管理中的分段，但是当空间被切分成不同长度的分片后，空间本身会碎片化，随着时间的推移，分配内存会变得很困难
因此考虑第二种方法，
将空间分割成固定长度的分片，在虚拟内存中，这种思想成为分页
，分页不是将一个进程的地址空间分割成不同长度的逻辑段(代码段，堆段，栈段)，而是
分割成固定大小的单元，每个单元称为一页
，相应的
把物理内存看成定长槽块的阵列，叫做页帧，每个页帧包含一个虚拟内存页
6.1 分页示例
(1) 分页简单示例及分页优点
如图，地址空间64字节，被分成4个16字节的页，物理内存128字节，有8个页帧，虚拟地址空间的页被存放到了物理内存的不同页帧：
由此能看出分页的一些优点：
1，
灵活性，通过完善的分页方法，操作系统能高效地提供地址空间的抽象
，不管进程如何使用地址空间，不用假定堆和栈的增长方向，以及它们如何使用
2，
分页提供的空闲空间管理的简单性
，如果操作系统希望将64字节的地址空间放到128字节的物理内存中，只需要将找到4个空闲页帧。也许操作系统有一个所有空闲页帧的空闲列表，只需从空闲列表中找到4个页帧即可
(2) 页表
为了
记录地址空间中每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保存一个数据结构，称为页表
页表的主要作用是为地址空间的每个虚拟页面保存地址转换，从而让我们直到每个页在物理内存中的位置
，对上述的简单示例中，一个页表有4个条目：
(虚拟页0->物理页帧3),(VP1->PF7),(VP2->PF5),(VP3->PF2)
VP即virtual page PF即physical page
每个进程都有一个页表，如果要运行新的进程，操作系统就需要为它创建新的页表并管理
(3) 分页中的地址转换过程
假设一个64字节的进程正在访问内存：
movl <virtual address>, %eax
为了转换该过程生成的虚拟地址，首先要将其分成两个组件：
虚拟页面号(VPN)和页内的偏移量(offset)
，由于虚拟地址空间为64字节，所以地址空间需要6位表示(2^6=64)
页面大小位16字节，位于64字节的地址空间，因此需要表示4个页，所以用虚拟地址前2位表示是哪个页，即虚拟页号，后四位用来表示该地址在该页内的偏移量
地址转换的过程中，查询页表根据虚拟页号找到对应的物理页帧，偏移量保持不变就能得到真实的物理地址
6.2 页表存放在哪里
页表可以变得很大，假如一个32位地址空间，那么它有4kb的页，它的虚拟地址分成20位VPN和12位的偏移量，一个20位的VPN意味着操作系统必须为这个进程管理2^20(约100万)个地址转换，假设每个页表条目(PTE)需要4字节，那么每个页表需要4MB内存，假设机器中有100个进程，那么仅仅为了地址转换就需要400MB的内存，即使是现代计算机的内存，将这么多内存拿来仅仅做地址转换也是极不合理的
由于页表太大，因此没有在MMU中利用任何特别的片上硬件，来存储当前正在运行的进程的页表，将页表存储到操作系统的虚拟内存中，甚至交换到磁盘上
6.3 页表中有什么
页表就是一种数据结构，用于将虚拟地址(虚拟页号)映射到物理地址(物理页帧)
最简单的形式称为
线性页表
，即一个数组，操作系统通过虚拟页号(VPN)来检索该数组，并由该索引查找页表项(PTE)，以便找到期望的物理页帧号(PFN)
每个PTE中有许多不同的位：
1，
有效位
：通常用于指示特定地址转换是否有效，如当一个程序开始运行时，它的代码和堆在其地址空间的一端，栈在另一端，中间没被使用的空间被标记位无效，如果进程尝试访问这些内存，就会陷入内核，导致进程终止，
有效位对稀疏地址空间至关重要，通过简单地将地址空间中未使用地页面标记为无效，就不需要为这些页面分配物理帧，从而节省大量内存
2，
保护位
：表明页是否可以读取，写入或执行，同样地以这些位不允许地方式访问页，会陷入操作系统，终止进程
3，
存在位
：表示该页是在物理存储器中还是在磁盘上，
交换机制
可以让操作系统将很少使用的页移动到磁盘，从而释放物理内存
4，
脏位
：表明页面从磁盘被带入内存后是否被修改过
5，
参考位
：有时用于追踪页是否被访问，也用于确定哪些页被频繁使用，因此将其保留在内存中
一个x86架构的示例页表项：
它包含一个存在位§，确定是否允许写入该页面的读/写位(R/W)，确定用户模式进程是否可以访问该页面的用户/超级用户位(U/S)，有几位(PWT，PCD，PAT，G)确定硬件缓存如何为这些页面工作，一个访问位(A)，一个脏位(D)，最后是页帧号(PFN)
当进行地址转换时，先通过虚拟页号(VPN)查找到页表项(PTE)，根据其中的各个位做出可行性判断，最后得到需要的物理页帧号(PFN)，再根据物理页帧号和偏移量得到物理地址
6.4 分页很慢
内存中的页表很大，事实证明，它们还会让速度变慢，以一个简单的指令位例：
movl 21, %eax
系统要将虚拟地址转换成正确的物理地址117以便得到数据，但从地址117加载数据之前，
系统首先要从该进程的页表中找到适当的页表项，进行转换
，才能得到117，进而加载117中的数据
为此硬件必须知道当前正在运行的进程的页表的位置，硬件将从虚拟地址中取得虚拟页号(VPN)，通过虚拟页号查找页表中对应页表项(PTE)的位置，进而得到物理页帧号(PFN)，将它与虚拟地址的偏移量结合起来，形成最终需要的物理地址
对于每个内存引用，分页都需要执行一个额外的内存引用，以便首先从页表中获取地址转换，工作量很大，额外的内存引用开销很大
，这种情况下，可能使进程减慢两倍甚至更多
6.5 小结
分页有许多优点，首先，它不会导致外部碎片，因为分页将内存划分为固定大小的单元，其次，它非常灵活，支持稀疏虚拟地址空间
然而，实现分页支持而不小心考虑，会导致机器缓慢(有许多额外的内存访问来访问页表)和内存浪费(内存被页表塞满而不是有用的应用程序数据)，因此需要更好的分页系统