操作系统（11）----内存管理5-阿里云开发者社区

操作系统（11）----内存管理4：https://developer.aliyun.com/article/1511166

快表是如何工作的？

假设某进程执行过程中要依次访问(0,0)、(0,4)、(0,8)（页号，块号）这几个逻辑地址。若访问TLB只需1us，而访问内存需要100 us。

注：当进程切换时，快表的内容需要被清除。

①首先将进程的页号与页表寄存器中的页表长度对比，若页号大于页表长度则越界异常。

②若没有越界，则查询快表，但是由于进程刚上处理机运行，因此快表中的内容为空，快表中找不到页号为0的页表项，因此快表没有命中

③若快表没有命中，那么就会访问慢表，通过页表始址+页号*页表项长度，得到内存块号，再根据内存块号和页内偏移量即可得到目标物理地址。

④因为快表中没有该页表项，所以会从慢表中复制一份，放到快表中。接着通过内存块号与页内偏移量拼接得到页号为0，页内偏移量为0的目标物理地址。

⑤接下来要访问的是页号为0，页内偏移量为4的地址。

⑥经过比较页号和页表长度，发现没有越界，则查询快表，此时快表中有相应的页表项。那么操作系统就能通过快表的相应页号，直接查询内存块号

⑦再通过内存块号和页内偏移量就可以得到目标物理地址

因为地址变换就需要查询慢表，而访问慢表需要100us的时间，若引入快表，快表中有相应的页表项，那么地址变换就只需要1us的时间。

注：快表中存放的是页表的一部分副本，因为快表造价高，容量小，不足以放下所有副本。

这里补充一下快表和Cache的区别，不知道Cache原理的可以先看：

http://t.csdnimg.cn/yKGyU

这样知识点就融会贯通了，即得到物理地址后，看Cache中是否有对应物理地址，若有，则直接访问Cache即可，这样极大提高了CPU访问速度，若没在Cache中，那么就从主存中访问目标数据(访存)。并将主存块调入Cache：

① 快表中存储的是页表项的副本;Cache中存储的是主存块的副本，每个主存块是相对较大的，如下图所示有1KB，而每个页表项可能只有4B左右

② 加入快表，是使逻辑地址到物理地址的转变速度更快，即可以减少一次访存，而Cache是会加快CPU对主存的访问效率，若Cache中有想要访问的目标数据，那么直接访问速度更快的Cache，无需访问主存

总结：

① CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。

② 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此若快表命中，则访问某个逻辑地址仅需一次访存即可。

③ 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此若快表未命中，则访问某个逻辑地址需要两次访存(注意:在找到页表项后，应同时将其存入快表以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换)

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。

因为局部性原理，一般来说快表的命中率可以达到 90%以上。

补充：

时间局部性:如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。

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

上面介绍的基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。

由于局部性原理，可能连续很多次查到的都是同一个页表项。

以上的1+100是快表中有相应页表项的时间，先访问快表（1us），若快表中有相应的页表项，则直接访问内存（100us）

1+100+100是快表中没有相应页表项的情况，即先访问快表（1us），没有相应的页表项，则先访问内存（慢表）（100us），计算得到内存块号后，在访问内存（100us）

若未采用快表机制，则访问一个逻辑地址需要100+100=200us

注：若慢表和快表同时查找，那么从（1+100+100）*0.1到（100+100）*0.1

经过下图可知，若慢表和快表同时查询，当查询快表使用1us的时间时，系统已经花费1us的时间查询慢表了，所以查询慢表的时间-1。

总结：

其实到这里我们就已经有CPU访问主存的大致框架了，当CPU访问主存时，主存中没有对应数据，就需要到磁盘中调入，对于替换主存中的哪一内存块，就涉及到页面置换算法。

若主存中有相应地址，CPU通过将逻辑地址转换为物理地址，得到物理地址，若物理地址存在于Cache中，直接在Cache中访问，若没在Cache中，那么就从主存中访问目标数据(访存)。并将主存块调入Cache。

这就连贯了以下过程：

•两级页表

单极页表存在的问题：

某计算机系统按字节寻址，支持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个页框存储该页表。

根据页号查询页表的方法:

K号页对应的页表项存放位置=页表始址+K*4

要在所有的页表项都连续存放的基础上才能用这种方法找到页表项

① 因此：需要专门给进程分配2^10=1024 个连续的页框来存放它的页表。页表很大，需要占用很多个连续的页框，并且这样丧失了非连续分配管理方式的优势。

② 根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。

对于问题①的解决方法：

我们可将长长的页表进行分组，使每个内存块刚好可以放入一个分组(比如上个例子中，页面大小4KB,每个页表项 4B，每个页面可存放 1K个页表项，因此每1K个连续的页表项为一组，每组刚好占一个内存块，再讲各组离散地放到各个内存块中)

为了在各个分组中找到各分组的先后顺序，需要再建立一个页表，称为页目录表，或称外层页表，或称顶层页表。

两级页表的地址结构：

32位逻辑地址空间，页表项大小为4B，页面大小为4KB，则页内地址占12位

单级页表结构如下：

进程最多有 2^20 个页面,用 20 位二进制刚好可以表示 0~2^20-1 个页号。

由于页面大小=内存块大小，所以每个内存块就可存放 4K/4 =1K=2^10=1024个页表项

注：一个页号对应一个页表项，这里的相除使想得到内存块中可存放的页表项数。

我们将页表分为1024个页表,所以原来页表中页号为1024的页表项，变为了下面红框中的页表项。

两级页表的结构如下：

上图的一级页号的10个2进制位用于表示页表数量，二级页号的10个2进制位用于表示每个页表中的页表项数量。

为区分各个小页表（二级页表）的顺序而设置的页表即页目录表

页目录表记录的是（页表+内存块号），例如0号页表存放在3号内存块中

如何对两级页表结构的逻辑地址进行地址变换？

例:将逻辑地址(0000000000,0000000001,111111111111)转换为物理地址(用十进制表示)。

① 按照地址结构将逻辑地址拆分成三部分

② 从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置。例如，0号页表放在内存中的3号内存块中

③再根据3号内存块存放的二级页表，得到最终需要访问的地址

由于二级页号=0000000001，所以对应的块号是4，访问4号内存块

④结合页内偏移量得到目标物理地址，即4号内存块号结合页内偏移量：

内存块大小*内存块号+页内偏移量

对于②问题：进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。

可以在需要访问页面时才把页面调入内存(虚拟存储技术)。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存

若想访问的页面不在内存中，则产生缺页中断，然后将目标页面从外存调入内存。

注：缺页中断指的是正在执行的某个指令，想访问暂时没有调入内存的页面产生的，所以此中断信号与当前执行的指令有关，属于内中断。

对于多级页表需要注意：

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

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

由于页面大小是4KB，而系统又是按字节存储的，所以页内偏移量为4KB=2^12B

页号=40-12=28位

页面大小=2^12B，页表项大小=4B，页面大小=内存块大小，则每个内存块可存放2^12/4=2^10个页表项

因此各级页表最多包含 2^10个页表项，需要 10 位二进制位才能映射到 2^10个页表项，因此每一级的页表对应页号应为10位。总共28位的页号至少要分为三级

如果只分为两级页表，则一级页号占 18 位，也就是说页目录表中最多可能有 2^18 个页表项，显然，一个页面是放不下这么多页表项的。

2.两级页表的访存次数分析(假设没有快表机构)

第一次访存:访问内存中的页目录表

第二次访存:访问内存中的二级页表

第三次访存:访问目标内存单元

而单级页表只需要进行两次访存，第一次访问页表，第二次访问目标内存单元

得出结论访问使用n级页表，访存次数为n+1次

所以两级页表在空间利用率上升的同时，牺牲了访存的时间，即访存的时间比单级页表长。

（2）基本分段存储管理

基本分段存储管理与与基本分页存储管理最大的区别就是离散分配时所分配地址空间的基本单位不同。

•分段

进程的地址空间会按照程序自身的逻辑关系划分为若于个段，每个段都有一个段名(在低级语言中，程序员使用段名来编程)，每段从0开始编址。以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。例如，0号段占据的是从80K开始的连续的7KB的地址空间。

由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高。例如，用户可用汇编语言（低级语言）写这样两条指令。

注：在用户编程时使用的是各个段名来操作各个段，但是在CPU具体执行时，使用的是段号这个参数，所以在编译程序中会将段名转换为段号。CPU在执行各个指令时是根据段号来区分各个段的。

分段系统的逻辑地址结构由段号(段名)和段内地址(段内偏移量)所组成。如：

段号的位数决定了每个进程最多可以分几个段，段内地址位数决定了每个段的最大长度是多少

在上述例子中，若系统是按字节寻址的，则段号占16位，因此在该系统中，每个进程最多有2^16=64K个段。

段内地址占16位，因此每个段的最大长度是 2^16=64KB

写程序时使用的段名 [D]、[X] 会被编译程序翻译成对应段号。单元、单元会被编译程序翻译成段内地址。