《操作系统 - 清华大学》4 -5：非连续内存分配：页表一反向页表

1. 大地址空间的问题

接下来再考虑另一个问题，单级页表或者多级页表的大小都和逻辑地址空间大小有对应关系，逻辑空间越大，其实意味着对应的页表就越多，有什么办法使得页表大小不与逻辑地址空间大小尽量没有那么大的关系，尽量与物理地址大小建立对应关系。这其实就是反向页表的想法，这个想法其实也是逐步产生的，看看反向页表有什么样特点。

如果是 64 位的寻址空间，它为此要建立页表，即使用了五级页表，它占的空间也是很大。那么能不能有一个办法，建立一个数据结构，它里面存的信息的总容量和逻辑地址空间的大小没有关系，如果没有关系，那逻辑空间的地址和物理空间的地址的映射关系怎么建立？

一级或者多级页表都是以逻辑页的页号做 index ，来索引一个大数组，那反过来想想，能不能以物理页做 index，来查找对应逻辑页的页号呢？

2. 页寄存器（ Page Registers ）方案

首先第一个办法是页寄存器的设计方案:

可以理解为有一个页寄存器数组，但是需要注意，它这里面 index 变了，index 不是页号，而是物理页号，页帧号，根据物理页号可以查出来它对应的页号是多少。因为物理页号里面存的内容是页表里的内容，有属性、对应的页号，需要注意正好反过来了，它是以页帧号为索引，页表项内容是页好，而前面讲的是以页号为索引，页表项内容是页帧号，正好是反过来的。

这种方式就使得本身寄存器的容量只与物理地址空间大小相关，而以逻辑地址空间的大小是无关的，可以限制寄存器的数量。但是有这个设计之后，很明显的一个问题，之前查找的时候是根据 page number 来查找 frame number，那如果建立了这么一个数据结构之后，怎么去找到 page number 所在的位置？

因为得到的只是以 frame number 为index 的数组，其实如果采取页寄存器，最大的问题在于怎么去把根据页号来找到页帧号的关系建联起来，这好像是一个问题。

但是它的好处是占的空间很少。

> 举个例子，如果物理内存大小是 4K * 4K = 16M ，物理空间有16M，页的 size 定义是4K，也意味着页帧数量一共有4K，这时候一个页寄存器占 8 B，意味着整个页寄存器的数量应该是8 * 4K = 32K，那在整个页地址空间中占的比例是 32K/16M，大约0.2%，确实可以看到这种方法的内存占用确实比较小。

但是它的问题在于怎么把这两者映射关系给建立好，光建立这么一个数据结构好像还是没法去有效根据页号找的页帧号？

3. 基于关联内存(associative memory )的反向页表（inverted page table）

那可以采取另一种办法，关联内存存储器：

关联存储器是一个很特殊的存储器，有这个存储器之后，可以并行地查找页号所对应的页帧号，就是它的 key 是页号，它的 value 是页帧号，就类似于 TLB，其实可以设计个 TLB 专门这么来放。

那么基于关联存储器这种设计，但是它存在一个很大的问题：

它这个开销太大，设计成本太大，关联存储器用到硬件逻辑很复杂，所以导致它这个容量不可能做很大。即使刚才说的16M 容量，其实对于关联存储器来说也是一个很大的开销，而且这个还需要放到 CPU 里面去，如果说放到外面的话，那其实还存在一个问题是内存访问的开销问题，这个是它的一个缺陷。

就是说它设计可以做得很好，但是具体实现的时候会发现成本代价，导致它无法做得特别大，这是它的一个问题。而且对于关联寄存器来说，一个大容量的关联存储器，其实它的访问速度还会下降。这两者使得这种方式不够实用，为此我们还需要新的方式。

4. 基于哈希（hashed）查找的反向页表

第三种方式就是基于哈希计算的一个反向列表:
可以把刚才关联存储机制用另一种方法实现，把根据 page number 查找 frame number 过程用 hashtable 来实现，当然这里面需要注意什么呢？

1. hashtable 很明显是一个很简单的数学计算方法，哈希函数建好之后，只要给哈希函数输入一个值，它会得到一个输出，输入就是 page number，输出就应该是 frame number。哈希函数本身计算也可以用软件来计算，也可以用硬件来加速，为了能够提高效率，很明显应该用硬件加速方式，还需硬件帮助。
2. 需要注意为了提高效率，可以把哈希函数再加一个参数，PID 当前运行程序的 ID，PID 加上 page number 可以很好地做 input， 来设计出比较简洁的哈希函数，算出对应的帧号 page number，那整个组织结构还是没变，从基于寄存器的组织变成了基于关联存储器的组织，再变成基于 hash table 的组织，这种方式可以有效地缓解完成映射开销。

1. 当然相对而言这种方式还是有问题，问题在于查找的时候也许能查找，但是查找时候会出现哈希碰撞，比如对应一个 input，会存在多个 output。需要去了解对应的多个页帧号到底选的是哪一个？这是需要去了解的，在这里面也强调了为什么要通过程序的 ID 来缓解这种冲突。
2. 这种方式还是需要把整个反向页表放到内存里面去，所以做哈希计算的时候也需要到内存里面去取数，其实说白了内存的开销还是很大，为此还需要有一个类似于 TLB 的机制来把它缓存起来，降低访问反向页表的时间。这是要考虑的两个问题。

目前来说这种机制在高端的 CPU 里面才存在。它的好处很明显，它不受制于逻辑地址空间或者虚拟空间大小的限制。它的容量可以说很小，因为它只和物理空间有关。前面也讲到了每一个运行的程序都需要有一个 page table，二级或者多级的页表，但对于这个而言，整个系统只要一个，因为它用的是物理页帧的页帧号来做 index， 限定这个表，而这个表和有多少个进程其实也没有关系。所以说相对而言，它占的空间比一级页表、二级页表要节省很多。但它是有代价，它需要有一种高速的哈希计算硬件处理机制，还有个高效的函数，以及还有解决冲突机制，才能够有效地使得整个访问效率得到保障，那这种机制就是有硬件有相应的软件配合，操作系统软件配合可以在空间和时间上取得一个比较好的结果。

5. 小结

非连续内存管理机制，这里面包含两种方法，一种方法是基于段映射机制，一种是基于分页映射机制，重点是分页。特别是怎么去有效地设计一个页表来提高页表的访问的效率和节省页表所占的空间。