2、操作系统内存管理——分页

注：参考哈工大李治军老师公开课。

1、 分页原理

在内存管理中，为了减少内存的空间的浪费，采用了页作为分配的基本单位（大小通常是4K），而且在分配的过程中采用了页号（逻辑地址）和页框号（物理地址）的映射表，这样使得程序在内存中的分布就不需要严格的连续分布了。例子如下：

图一：页访问过程

在图一中,需要访问的地址是0x2240，且页面大小是4K，那么内存中的MMU就会进行计算0x2240/4K=0x0002（右移12位）得到页号，那么剩下的就是页内偏移量了。这样就的到了逻辑地址<0x0002，0x0224>，进程PCB中的页表指针就会根据逻辑地址中的页号去查询页号-页框号映射表，得到页框号3，在结合逻辑地址中的页内偏移量0x0224 ，得到物理地址<3，240>，然后进行访问。

这样的方式看起来简单方便，但是却有一个极其致命的问题，我们计算机的内存如果是4GB，页面大小是4KB，那么就有4GB/4KB=1M这么多个表项，这个表项的存储代价是巨大的。虽然我们的程序用不到这么多，有很多表项是不需要的；但是我们为了提高查找效率（起始地址+偏移量）就必须把那些不需要的表项页记录在表中。为了解决这个问题，有以下两种解决方案：

2、采用多级页表：

就像书的目录一样，先安装章排序，再每章按照小节排序，以此类推；这样的话如果需要找到某一项的话，就只需要先读入章目录，再读入特定章的小节目录，以此类推，这样就大大减少了内存的消耗，增加了内存使用的效率，节省了内存空间。

图二：多级页表

虽然这种方式极大的提高了空间的利用率，但是依然存在问题，就是每查一级目录就需要访问一次内存，这样导致每次访问内存都需要额外的访问几次。为了解决这一问题，可以采用一种类似cache结构的折中方式——快表。

3、 快表（TLB，类似cache）

快表是一种利用程序空间局部性（即一段时间内程序执行的是同一段程序），是一组相联快速存储，是寄存器（速度快，价格贵），大小一般在64-1024之间。

图三：程序空间局部性

 

快表的使用类似cache的使用，就是先直接在快表中顺序查找，如果找到就直接获得页框号，得到物理地址；如果没有找到，再采用多级页表查找。

图四：快表的使用