彭诗亮的博客

0%

页表加速

发表于

局部性原理

1
2
3
4
5
6
int i = 0;
int a[100];
while(i < 100) {
    a[i] = i
    i++
}

这个程序会很频繁的访问下图中的10号和20号内存块

img.png

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行：如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）

空间局部性： 一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的）

在地址转化过程中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项。既然如此，能否利用这个特性减少访问页表的次数呢？

快表

快表，又称联想寄存器(TLB) 是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

img_1.png

引入快表后，地址变换的过程的文字描述：

  1. CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
  2. 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号， 再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此， 若快表命中，则访问某个逻辑地址仅需一次访存即可。
  3. 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此， 若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表， 以便后面可能的再次访问。但若快表己满，则必须按照一定的算法对旧的页表项进行替换,也就是页面置换算法）

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。 因为局部性原理， 一般来说快表的命中率可以达到90%以上。 查询内存中的慢表(页表) 经过计算查询内存中物理地址的内存单元

例：某系统使用基本分页存储管理，并采用了具有快表的地址交换机构。访问一次快表耗时 1us,访 问一次内存耗时 100us。若快表的命中率为 90%，那么访问一个逻辑地址的平均耗时是多少？（1+100)* 0.9+ (1+100+100)0.1=111us 有的系统文持快表和投表同时查找，如果是这样，平均耗时应该是 (1+100) 0.9 + (100+100) *0.1 = 110.9 us 若未采用快表机制，则访问一个逻辑地址需要 100+100=200us 显然，引入快表机制后，访问一个逻辑地址的速度快多了。

单级页表所引发的问题

某计算机系统按字节寻址，支持32位的逻辑地址，采用分页存储管理，页面大小为4KB，页表项长度为 4B。 4KB= 2^12B，因此页内地址要用12位表示，剩余20位表示页号。 因此，该系统中用户进程最多有2^20页。相应的，一个进程的页表中，最多会有2^20 =1M=1,048,576个页表项，所以一个页表最大需要 2^20*4B=2^22B，共需要 2^22/2^12=2^10 个页框存储该页表。 根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。

  • 问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。
  • 问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面

问题一

上面提到了这两个问题，针对问题一，可以引入二级页表的概念来解决。

二级页表

在32位逻辑地址空间，页表项大小为4kb，页面大小4kb,页内地址占12位

31 … 1211 … 0
页号页面偏移量

img_9.png
将页表进行拆分
img_8.png
拆分后页表查找过程
img_7.png
二级页表的地转换过程：
例如：17407的32位二进制可表示为(0000000000,0000000100,001111111111)

  • 先去根据0000000000到页目录表查找页表内存块3，然后访问内存块3得到页表信息
  • 根据二级页表0000000100对应二级页表的下标为4，所以在页表0中下标4页号的内存块号为16；
  • 由与4kb页表被拆分成1024个页表，可得知，每个页表大小为4b,所以16内存号的起始地址为16*1024=16384
  • 偏移量001111111111计算得知为1023，所以最终物理地址为16384+1023=17407
    img_6.png

两级页表的访存次数分析（假设没有快表机制）

  • 第一次访存：访问内存中的页目录表
  • 第二次访存：访问内存中的二级页表
  • 第三次访存：访问目标内存单元

问题二

上面的部分我们解决了问题一，接下来是问题二，这里简单叙述一下,详细内容在页面置换算法文章中会提到

img_2.png

多级页表

若采用多级页表机制，则各级页表的大小不能超过一个页面

例：某系统按字节编址，采用 40 位逻银地址，页面大小为 4KB，页表项大小为 4B，假设采用纯页式存储，则要采用（）级页表，页内偏移量为（）位？

页面大小=4KB=2^12B，按字节编址，因此页内偏移量为12位 页号=40-12=28份 页面大小=2^12B，页表项大小=4B，则每个页面可存放 2^12/4=2^10个页表项 因此各级页表最多包含2^10个页表项， 需要10位二进制位才能映射到2^10个页表项，因此每一级的页表对应页号应为10位。总共28位的页号至少要分为三级

img_3.png

参考文献:王道计算机考研-操作系统