基本页式存储管理

基本地址变换机构

本节还是讲解基本页式存储管理，在上一节中我们学习了页式存储的地址变换方法，这里我们来理解基本地址变换机构（用于实现逻辑地址到物理地址转换的一组硬件机构）的原理和流程。

页表寄存器

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。通常我们要设置一个页表寄存器（PTR）存放页表在内存中的起始地址F和页表长度M。这样我们才可以找到页表，进程未执行时，页表的起始地址和页表长度放在进程控制块PCB中，当进程被调度室，操作系统内核会把他们放到页表寄存器。

地址变换过程

我们现在已图示的方法演示，注意这里页面大小是2的整数幂，设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

其实前面都讲过了，这里只是演示一下借助页表寄存器具体的转换流程。理解后不需要死记硬背。这里我们来练习一下：假设页面大小为1KB，页号2对应的内存块号b=8，将逻辑地址A=2500转换为物理地址E。相当于告诉了我们以下有效信息：

系统按字节寻址
页内偏移量占地址的10位
页号2对应页框8

那么我们首先计算页号=2500/1024=2,页内偏移为2500%1024=452。所以物理地址实际上就已经出来了是8*1024+452=8644。

所以在分页存储管理的系统中，只要确定了每个页面的大小，逻辑地址结构就可以啦，因此，页式管理中地址是一维的。即只要给出一个逻辑地址系统就可以自动地算出页号、页内偏移量两个部分，并不需要显示的告诉系统这个逻辑地址中，页内偏移量占多少位。

页表项大小的深究

我们知道页表项所占字节大小是根据最大页号所占的位数确定的并且每个页表项的长度是相同的，页号是“隐含”的。前面我们讲过一个例题：物理内存为4GB，页面大小4KB，我们最终算出来页表项至少要占3个字节也就是24bit。但是实际上一般我们是让页表项占4个字节，即即使我们一直页表项为20bit，3字节就已经可以表示了我们还是宁愿在让他多占一个字节为4字节。

思考：为什么要这样做，有什么意义？

我们知道页表项会按顺序连续地存放在内存中。那么如果页表在内存中的存放起始地址为X，那么M号页对应的页表项是存放在内存地址为X+3*M的。但是如果此时一个页面大小为4KB，那么每个页框都可以存放4096/3=1365个页表项（因为页表存在内存中，那么显然页表也是按页式存储的，所以页表项也是存在页框中的，只不过这几个页框会相邻这样就实现了连续存储了），但是这个页框还会剩余4096%3=1B页内碎片。这其实内部碎片大小是可以忽略的，但是此时就会导致X+3*M公式不适用了，即整体看来页表项不再是连续存储的了，而是每1365个页表项就间隔1B这可很难受。如下：

所以此时我们发现如果每个页表项按4B存储，那么一个页框就可以放4096/4=1024个页表项，并且刚刚好没有内部页内碎片，这样整体看来页表项就还是连续存储的也就说明此时公式X+3*M是可以适用的，所以明显4B更好，即使这样一个页框所存储的页表项就少了但是不差这一点空间。但是我们要注意不是每次都是4个字节都是刚刚好，根据页框大小的不同我们要动态更新但是原则上就是每次都要使得页面恰好可以装得下整数个页表项。

总结

具有快表的地址变换机构

实际上就是一种在基本地址变换机构的改进版本使得查询速率更快了。

什么是快表（TLB）

快表，又称联想寄存器（TLB,translation lookaside buffer)，是一种访问速度比内存快很多的高速缓存（注意TLB不是内存），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表（前面说过页表存放在内存中）称为慢表。

地址变换过程（引入快表）

一般访问快表TLB只需要1微秒，而访问内存需要100微秒。现在我们同样以图示演示一下用快表寻找（0,0）（0,4）（0,8）这几个逻辑地址。

我们发现和之前的过程不相同的是在得到页号后不是立刻取内存慢表中查找对应的内存块号，而是先在TLB寻找有没有最近刚刚查找过此页表项，如果有那么就可以直接命中知道内存块号了，这样就加速了查找速度，但是前提是TLB中得有即最近查找过这个表，如果没有那么还是需要去慢表中查找。

思考：两种查找方法的本质区别？

速度不同那是肯定地了，还有就是访问内存单元的次数也是不同的，对于直接TLB命中的，只需要一次内存单元访问即得到物理地址后访问内存中的存储数据的单元，而如果没有在TLB中命中，那么还需要额外在进行一次在内存中的慢表中查询页表项得到物理块号，所以需要两次内存的访问，当然如果这次未命中，那么查询完此次页表项后会将这个页表项的副本加入到TLB中以便下一次再查找这个页表项时可以命中快速查询。

思考：可以提速多少？

我们知道由于查询快表的速度比查询页表的速度快很多，所以只要尽可能多的快命中，就可以节省很多时间。由局部性原理（即CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中）一般来说快表的命中率可以达到90%以上。我们以一道例题来计算：

某系统使用基本分页存储管理，并采用了具有快表的基本地址变换机构，访问一次快表耗时1微秒，访问一次内存耗时100微秒。如果快表的命中率为90%，那么访问一个逻辑地址的平均耗时时间为多少？

（1+100）*0.9+（1+100+100）*0.1=111微秒

对于上面的计算可不要轻视，一定要理解透彻，前面是快表命中，需要一次查询快表的时间1微秒+一次内存访问时间（查询数据）100微秒，而对于未命中时也是查询了一次快表1微秒+两次内存访问时间200微秒（一次慢表查询，一次数据访问）。

思考：能否进一步提速？

可以，对于某些系统来说支持快表和慢表同时查找即两个搜索同时进行，谁先找到就用谁，这样快表找到的时间还是101微秒，但是慢表查询就是200微秒了（因为不查找快表了）这样计算一个逻辑地址平均查找时间为110.9微秒。而如果不采用快表，那么查找一个逻辑地址所用的平均时间为200微秒。显然引入快表以后，访问一个逻辑地址的速度快了一倍。

这里对于两种查询快表的方式进行对比：

思考：如果把所有页表全部放在TLB那么岂不是更快？

显然不可能，TLB造价高昂，肯定是容量有限不能容下所有页表，所以这种想法目前为止还不可能实现，但是这样就会出现一个问题，当TLB满了以后再添加新的页表项副本时就需要先淘汰一些页表项，这就涉及到了淘汰谁的问题，这里也大有讲究有许多置换算法后面细讲。

局部性原理

时间局部性原理：如果执行了程序的某条指令，那么不久后这条指令很有可能会再次执行，如果某个数据被访问过，那么不久之后这个数据很有可能会再次被访问。（因为程序中存在大量的循环）
空间局部性原理：一旦程序访问了某个存储单元，在不久之后其附近的存储单元也很有可能再次被访问。（因为许多数据在内存中都是连续存放的）

所以对于上节介绍的无快表的基地址变换机构中，每次访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能很多次查到的都是同一个页表项。

总结：

这里我们在学习了机组原理后知道有一个和TLB非常类似的机构叫做Cache实际上两者是由区别的：TLB中只有页表项的副本，而普通Cache中可能会有其他各种数据的副本。但是解决问题的思路是类似的，实战请参考：缓存Cache实验

两级页表

单级页表存在的问题

我们以一个例题为例：某计算即系统按字节寻址，支持32位的逻辑地址，采用分页存储管理，页面大小为4KB，页表项长度为4B。

那么4KB=2^12B，因此页内地址要用12位表示，所以剩余的20位表示页号。因此，该系统中用户进程最多有2^20页。相应的，一个进程的页表，最多会有2^20=1M=1,048,576个页表项，所以一个页表最大需要2^20*4B=2^22B=4M，共需要2^22/2^12=2^10个页框存储该页表。即需要专门给进程分配1024个连续的页框来存放它的页表。

注意：页表的存储方式！

这里我还是想再谈一谈页表的存储方式，虽然我们知道按照分页存储，数据是可以离散存放的，但是对于页表这一特殊的数据结构在分页内存中存放时还是要连续放的，所以这就要求页框必须是连续的，并且为了地址好查询即X+4*M还尽量要求页框能够放入整数个页表项。

思考：上面的单级页表存储有什么问题？

页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框
没有必要让整个页表常驻内存，因为局部性原理进程可能一般在一个时间段内只会访问几个特定的相邻的页面。

所以我们想把页表再分页并离散存储，然后在建立一张页表记录各个部分的存放位置，称为页目录表，或称外层页表，或称顶层页表。这就是两级页表甚至多级页表的由来。

两级页表的原理、地址结构

我们先来看一下单机页表时怎么存储的，此时将页表分为了1024个部分即1024个连续页框，每个页框里有1024个页表项如下：

现在我们将这1024个部分也离散存放然后建立一张表格来记录各部分所存储的位置。如下：

此时一级页号（页目录号）有1024项记录的是1024个部分所存储的页框号，然后二级页号对应的是某个页表中的页号（即页号），最后12位还是页内偏移量。例如此时

此时我们发现实际上空间并没有变大，还是只能存储2^20页，但是此时可以不用连续存储了并且最终的计算还是满足X+4*M的公式。但是此时内存里的分布就比较复杂了，原先是某一连续区间里存放的全是页表（里面放的是页表项），然后另外的地方存储着数据单元，但是现在3号存放的是页表（里面对应的是页表项）但是2号页框里面存储的就是数据了，所以数据存储和页表存储夹杂在一起了。并且分成二级发现无论是哪个页表都是最大为1023的数不会再出现1048575这么大的数了就是因为两级导致的拆分。相当于原先的0~1048575的一张大表变成了1024个小页表了每个页表时0~1023并且每个小页表有了编号为0#~1023#。

现在还没有解决页表常驻的问题，所以我们还需要在页目录中添加一栏状态标志位表示此时i#页表是否在内存中如下：

只有在需要访问i#页表时才放入到内存中（虚拟存储技术），当然页目录肯定是得一直在内存中的。如果想访问的页面不在内存中，就是缺页中断了（内中断/异常：自发指令触发，在cpu中发出中断信号）然后将目标页面从外村调入内存（此时不能说是中级调度，因为不是挂起进程进入调入内存而是缺的页表调入）。

思考：之前为什么说当缺页率高时说明内存紧张了？

毕竟内存有限，如果内存很小时那么每次调入缺的页表同时还需要调出某些页表腾地方，那么老缺页中断就说明没有足够的地方存放被访问页的地方了。

使用多级页表是有没有什么变化？

我们知道在单级页表时每一个页表项的地址就是起始地址+页号*页表大小，但是当使用多级页表时只有同一张页表中的页表项还使用（因为一张页表内还是连续存储的）但是此时页表间的页表项就不再适用了，因为此时各个页目录表是离散存储的了。

思考：什么时候使用多级页表？

若分为两级页表后，页表依然很长，那么我们就可以采用更多级页表，一般来说各级页表的大小不能超过一个页面，毕竟页目录最好就放入一个页框中最合适。例如：某系统按字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式存储，则需要几级页表？页内偏移量多少位？

页面大小=4KB=2^12B，按字节编址所以页内偏移量就是12位。

那么页号所占位数=40-12=28。又因为页面大小为4KB=2^12B,页表项为2^2B，那么每个页面可以放2^10个页表项。因此各级页表最多包含2^10个页表项，需要10位二进制才能映射到2^10个页表项，因此每一级的页表对应页号为10位（可以少但是不要多于10要不就会出现一张表放不下两张表多于的情况，少的话后面就空着呗）。所以需要三级页表，逻辑地址结构如下：

思考：如果就要用两级页表会怎么样？

按理论你要是非得用也不是不可以，但是此时就会出现一级页号18位即有2^18个二级页表，那么页目录一张放不下，需要1.8个这就很不优雅。所以不推荐。而如果是8,10,10这样分布就很好，一级页号对应有多少个二级页目录一共有2^8个二级页目录，然后二级页号每一个都是一张二级页目录，页目录中的每一项映射着一个三级页表，三级页号表项映射着页号所对应的物理块号。这样一共是有2^28个物理块存储着数据。

思考：为什么不是10,10,8分布？

这样很不优雅，意味着有2^20个表都是填不满的，虽然对于查找没什么影响，但是页内碎片多，而8,8,10就只有一级页目录有页内碎片。既节省空间还优雅。

思考：两级页表和三级页表查询步骤（没有快表）？

两级页表：

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

三级页表：

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

总结

超级重点，必须会计算！