页表的结构

本质是一个大数组。索引就是页号，索引对应的内容就是帧号。
特殊的bit：Flags(标志位）
存在位，修改位，引用位等：逻辑地址空间很大，可能有一部分逻辑地址空间是没有到对应到物理地址空间的，那么这个时候他的存在位的属性就应该是不存在了。假设为0【1代表存在0代表不存在】。还有比如代表读写的情况，会有一系列的表示方法来表示这些特殊属性。

实例分析：
$2^{16}B(byte)=2^{10}B*2^6=2^6KB=64KB$216B(byte)=210B∗26=26KB=64KB
内存空间大小：16位系统：16byte（64KB），但是物理内存只有32KB【1KB=1024B，1B=8bit】
他们的页内偏移是一样的，因为页的大小是一样的，页的大小和页帧的大小都是1024byte（1K）。在这种情况下逻辑页的两个地址（4,0）和（3,1023）分表表示页号是4偏移量是0对应的物理页帧的页号是3，页内偏移是1023对应的物理页（页帧）的地址是多少。

首先CPU开始找这个地址，第一个的存在标志位是0，代表当前物理页帧不存在，这个页对应的页帧不存在，没有这个映射关系，此时CPU如果访问了这个地址会产生一个内存访问异常。第二个的存在位是1，对应的物理页帧确实在物理地址中存在，然后就可以查到他的页帧号（这里是00100也就说是4），然后映射出来页帧内偏移是1023【和页的页内偏移量相等】，此时结合公式计算可得：

$Addr.physical=2^S*f+o=2^{10}*4+1023$Addr.physical=2S∗f+o=210∗4+1023
内存非法访问：一般会杀死进程。【存在位属性为不存在时，内存访问异常会发生】

页表机制的性能问题

分页机制存在性能问题，主要是空间的代价问题。
1.我们希望空间占用越小越好
2.执行速度越快越好
页表访问：访问一个内存单元需要两次内存访问，一次用于获取页表项，一次用于访问数据。
现在的计算机64位很常见，64位机器如果每页1024Byte，那么一个页表会是$2^{64}\div2^{10}=2^{54}KB$264÷210=254KB 现在的一般计算机是完全无法存下这样一个页表的。
计算机内存中同时跑多个程序，为了有效地实现地址空间的隔离，我们需要每一个运行的程序都有自己的页表，所以页表所占的空间也相应增加。页表的整个组织空间过大，就不能放在CPU里，因为CPU的Cache很小。那么就需要把页表放到内存里，那么每次寻址都要访问一次页表要访问两次内存,这也存在不小的开销。因此我们需要一些对策。
一般由两种处理方法：
1.缓存：我们希望把常用的数据缓存到距离CPU距离比较近的地方（比如Cache，可以提高访问速度）
2.间接（Indirection）访问：通过多级页表机制可以有效缓解页表空间占据过大的问题

页表的时间问题

TLB：Translation Look-aside Buffer.快表
CPU里的MMU（内存管理单元）有TLB，是一个cache，他缓存的是页表里的内容。TLB是一个特殊的区域，位于CPU内部，它包含了两项（p和f）。p是key，f是value，这两部分形成了一个TLB的表项；而TLB的表项是有相关存储器（associative memory）来实现的，具备快速访问功能，可以并发查找，但是容量有限，执行代价较大。可以把当前/经常用到的页表项放入TLB，这样每次访问就不需要访问页表了。

当CPU得到一个逻辑地址，首先根据p查找TLB，如果TLB里有p则可以直接找到f，然后f加上页帧偏移量o就可以直接得到物理地址，然后找内存中对应的地址和内容，这样就避免了一次对页表的访问。但是TLB容量有限，总有访问不到的情况，此时TLB miss，这时候会再去查页表，若存在（存在位为1），则取回frame number，然后用一个TLB表项来存储和缓存这一数据。这时也使得TLB本身效率提高。通过TLB，我们可以尽量避免对内存页表的访问，降低整体开销。
miss之后，把页表的项存入TLB的这个过程是由操作系统完成的。（MIPS）；但是如果是x86系统，则是由硬件本身（CPU）完成的，这两种情况都存在。

页表的空间问题

多层次多级页表可以有效缓解空间开销大的问题。

二级页表

偏移量object不变，但是把页号再分为两块，p1和p2对应的分别是一级页表和二级页表的页号，拆分使得对一个大地址的寻址变成对N个小页表的寻址。
CPU寻址，会先找一级页表，一级页表的起始地址CPU是知道的，只要把p1作为index(索引）可以查找对应的一级页表的页表项，一级页表的页表项存储的是二级页表的起始地址（基址）。二级基址知道后，会根据二级页表的p2(作为index）找到对应p2的页表项。二级页表项的表项内容就是页帧号（Frame number），又因为页内偏移量和帧内偏移量是一样的，所以此时只需要加上偏移量o就可以获得完整的物理地址。
这个处理过程又多了一次寻址、查找、处理且页表都放在内存中，看似开销很大，但是这种方式使得某些不存在映射关系的页表项就没必要占用内存了。如果p1中的存在位是0，那么就没有对应二级页表中某项的必要了。如果是单一页表，即使映射关系不存在，对应的空间仍然需要保留在页表中，这样就可以极大节省了存储空间。

多级页表

进一步细分。一级页表的页表项对应二级页表的基址，二级页表的页表项对应三级页表的基址，三级页表的页表项对应页帧号。这种结构可以表示一个更大的地址空间。页表级数越多，访问开销会越来越大，时间花的很多，空间也省的很多。这种情况下我们需要结合前面的TLB来节省时间开销。

反向页表

页表大小和逻辑地址空间大小有直接关系，逻辑空间越大，那么对应的页表就越多。访问的开销也就相对越大，当地址空间足够大时，访问开销也将非常大

那么我们为什么不试着去让页表与物理地址空间建立对应映射关系呢？我们设计一个数据结构，它的存储信息容量与逻辑地址空间大小无关的同时，还要建立物理与逻辑地址空间的映射关系。前面的所有方式都是用逻辑页号做index，反页表就是把物理页帧表做index。

页寄存器：也是一个数组。这里的index是页帧号（物理页号），对应的表项内容是页号（逻辑页号）。正好反过来，这种方式使得寄存器的容易只与物理地址的大小相关，而与逻辑地址空间的大小无关。这也就限制了寄存器数量。
但是这里存在的问题：
我们查找是根据页号来找页帧号，我们用这种数据结构的话，怎么去找到页号所在的位置呢，因为我们只得到了以页帧号为索引的数组（通过页帧号找到页号）。 【也就说怎么根据页号找到页帧号】

例子：
物理内存大小：16MB(4K4K)
页帧数（size）：4K
页寄存器使用的空间：（假设8字节/寄存器）：4K8=32K
那么页寄存器带来的额外开销就是32K/16M=0.2%
确实内存开销比较小。

基于关联内存的方案：

p是页号，值是页帧号，但是开销太大。设计成本太大，关联存储器用到的硬件逻辑很复杂，导致容量不可能足够大。如果帧数较少，可以通过关联存储器储存页寄存器。在关联存储中查找逻辑页号，成功则页帧号被提取，失败则返回页错误异常（Page fault）
存在的问题：

所以这种方式不够实用。

基于哈希计算的反向页表：

把关联存储器中通过页号查找页帧号的过程通过哈希计算来实现。哈希表是一个数学计算方法，只要给哈希函数一个输入值，那么就应该有一个输出值。这里的输入值是页号，输出就是页帧号。哈希可以用软件计算也可以用硬件加速，为了效率明显应该选择硬件加速。
为了提高效率，我们增加一个PID【当前运行程序的ID】，算出对应的帧号。关联存储器的变成了继续哈希表的组织，这种方式可以有效缓解映射开销。当然相对而言这种方式还是有问题，查找的时候虽然可行，但是查找的时候会出现哈希冲突，也就说一个输入可能会对应多个输出（不同的输入可能存在相同输出）。这就需要明确多个页帧号到底选哪一个，这也就强调了为什么要通过PID来解决这个问题。

反页表放入内存，所以哈希计算也需要从内存取值，也就说内存的开销仍然大，为此还需要一个类似TLB的机制来降低访问反页表的时间。
整个系统只需要一个反页表，因为使用页帧号做的映射表，所以相对而言比多级页表在空间上节省了很多。但是他需要有高效的哈希计算函数，以及解决冲突的机制，才能让访问效率得到保障。这种机制就是软件硬件相互配合，在空间和时间上取得一个比较好的结果。

段页式存储

段式存储在内存保护方面有优势，页式存储在内存利用和优化转移到后备存储方面有优势。所以，二者的结合：段页式储存。兼顾了段式在逻辑上的清晰和页式在管理上方便的特点