存储器管理（非连续分配管理方式）——操作系统笔记

@Yi-Xing 2020-11-28 0 评论 0 浏览

操作系统

一、基本分页存储管理

连续分配：为用户进程分配的必须是一个连续的内存空间；
非连续分配：为用户进程分配的可以是一些分散的内存空间；
- 基本分页存储管理；
- 基本分段存储管理；
- 基本段页式存储管理。

1、分页存储

将内存空间分为一个个大小相等的分区，每个分区就是一个页框（页框，页帧，内存块，物理块，物理页面）。每个页框有一个编号，即页框号（页框号，页帧号，内存块号，物理块号，物理页号），页框号从 0 开始。将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个页或页面。每个页面也有一个编号，即页号，页号也是从 0 开始。

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。

注意：进程的最后一个页面可能没有一个页框那么大。也就是说，分页存储有可能产生内部碎片，因此页框不能太大，否则可能产生过大的内部碎片造成浪费。

2、页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。注：页表通常存在PCB（进程控制块）中。

（1）页号是隐含的

假设页表中的各页表项从内存地址为 X 的地方开始连续存放… 如何找到页号为 i 的页表项？

页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组）；
当每个页表项占 3B，则 i 号页表项的存放地址 = $ X+3*i$。

（2）每个页表项占多少字节？

知道计算机中内存块的数量，求页表项中块号至少占多少字节？

假设某系统物理内存大小为 4GB，页面大小为 4KB，则每个页表项至少应该为多少字节？

内存块大小 = 页面大小 = 4KB = $ 2^{12}B$；
4GB 的内存总共会被分为 $ 2^{32}/2^{12}$ =$ 2^{20}$个内存块；
内存块号的范围应该是 0~$ 2^{20}-1$；
内存块号至少要用 20bit 来表示；
至少要用 3B 来表示块号（3*8=24bit）；
由于页号是隐含的，因此每个页表项占 3B，如果进程有 n 个页面，存储整个页表需要 $ 3*(n+1) B$。

注意：页表记录的只是内存块号，而不是内存块的起始地址。J 号内存块的起始地址 = J * 内存块大小。

3、分页存储管理的逻辑地址结构

地址结构包含两个部分：前一部分为页号，后一部分为页内偏移量 W。

如果有 K 位表示“页内偏移量”，则说明该系统中一个页面的大小是 $ 2^K$个内存单元。
如果有 M 位表示“页号”，则说明在该系统中，一个进程最多允许有 $ 2^M$ 个页面。

4、如何实现地址的转换

进程在内存中连续存放时，操作系统是如何实现逻辑地址到物理地址的转换的？用重定位寄存器：指明了进程在内存中的起始位置。

将进程地址空间分页之后，操作系统该如何实现逻辑地址到物理地址的转换？虽然进程的各个页面是离散存放的，但是页面内部是连续存放的。逻辑地址可以拆分为：页号，页内偏移量。通过页号查询页表，可知页面在内存中的起始地址。如果要访问逻辑地址 A，则：逻辑地址 A 对应的物理地址 = P 号页面在内存中的起始地址 + 页内偏移量 W。

（1）如何确定一个逻辑地址对应的页号、页内偏移量？

在某计算机系统中，页面大小是 50B。某进程逻辑地址空间大小为 200B，则逻辑地址 110 对应的页号、页内偏移量是多少？

页号=逻辑地址/页面长度（取除法的整数部分），页号=110/50=2；
页内偏移量=逻辑地址%页面长度（取除法的余数部分），页内偏移量=110%50=10；

计算机计算页号和页内偏移量

如果每个页面大小为 $ 2^kB$，用二进制数表示逻辑地址，则末尾 K 位即为页内偏移量，其余部分就是页号。

（2）为何页面大小要取 2 的整数幂？

逻辑地址的拆分更加迅速。如果每个页面大小为 $ 2^KB$，用二进制数表示逻辑地址，则末尾 K 位，即为页内偏移量，其余部分就是页号。因此，如果让每个页面的大小为 2 的整数幂，计算机硬件就可以很方便地得出一个逻辑地址对应的页号和页内偏移量，而无需进行除法运算，从而提升了运行速度。

物理地址的计算更加迅速。根据逻辑地址得到页号，根据页号查询页表从而找到页面存放的内存块号，将二进制表示的内存块号和页内偏移量拼接起来，就可以得到最终的物理地址。

5、总结

二、基本地址变换机构

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

1、逻辑地址到物理地址的变换过程

设页面大小为 L（页面大小是 2 的整数幂），逻辑地址 A 到物理地址 E 的变换过程如下：

计算页号 P 和页内偏移量 W（如果用十进制数手算，则 P=A/L，W=A%L；但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量）。
比较页号 P 和页表长度 M，若 P≥M，则产生越界中断，否则继续执行。（注意：页号是从 0 开始的，而页表长度至少是 1，因此 P=M 时也会越界）。
页表中页号 P 对应的页表项地址 = 页表起始地址 F + 页号 P * 页表项长度 M，取出该页表项内容 b，即为内存块号。（注意区分页表项长度、页表长度、页面大小的区别。页表长度指的是这个页表中总共有几个页表项，即总共有几个页；页表项长度指的是每个页表项占多大的存储空间；页面大小指的是一个页面占多大的存储空间）。
计算 $ E=b*L+W$，用得到的物理地址 E 去访存。（如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了）。

2、例题

若页面大小 L 为 1K 字节，页号 2 对应的内存块号 b=8，将逻辑地址 A=2500 转换为物理地址 E。等价描述：某系统按字节寻址，逻辑地址结构中，页内偏移量占 10 位，页号 2 对应的内存块号 b=8，将逻辑地址 A=2500 转换为物理地址E。

页号：$ P=A/L=2500/1024=2$；页内偏移量：$ W=A%L=2500%1024=452$；
根据题中条件可知，页号 2 没有越界，其存放的内存块号 b=8。
物理地址$ E=b* L+W=8* 1024+452=8644$。

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

3、对页表项大小的进一步探讨

还是上面的题。假设某系统物理内存大小为 4GB，页面大小为 4KB，则每个页表项至少应该为多少字节？经过计算得出每个页表项至少位 3B。各页表项会按顺序连续地存放在内存中，如果该页表在内存中存放的起始地址为 X，则 M 号页对应的页表项是存放在内存地址为$ X+3*M$。

一个页面为 4KB，则每个页框可以存放 $ 4096/3=1365个$ 页表项，但是这个页框会剩余 $ 4096%3=1B$ 页内碎片。因此，1365 号页表项存放的地址为 $ X+3*1365+1$。如果每个页表项占 4 字节，则每个页框刚好可存放 1024 个页表项。

结论：理论上，页表项长度为 3B 即可表示内存块号的范围，但是，为了方便页表的查询，常常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项。

4、总结

三、具有快表的地址变换机构

具有快表的地址变换机构就是基本地址变换机构的改进版本。

1、局部性原理

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

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

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

2、什么是快表（TLB）

快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓存（TLB 不是内存），用来存放近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。

3、引入快表后，地址的变换过程

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

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到90%以上。

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

$ (1+100)*0.9+(1+100+100)*0.1=111 us$；
有的系统支持快表和慢表同时查找。如果是这样，平均耗时应该是 $ (1+100)*0.9+(100+100)*0.1= 110.9 us$；
若未采用快表机制，则访问一个逻辑地址需要 $ 100+100=200us$ 显然，引入快表机制后，访问一个逻辑地址的速度快多了。

4、总结

TLB 和普通 Cache 的区别：TLB 中只有页表项的副本，而普通 Cache 中可能会有其他各种数据的副本。

四、两级页表

1、单级页表存储什么问题？如何解决？

某计算机系统按字节寻址，支持 32 位的逻辑地址，采用分页存储管理，页面大小为 4KB，页表项长度为 4B。

4KB = $ 2^{12}B$，因此页内地址要用 12 位表示，剩余 20 位表示页号；
因此，该系统中用户进程最多有 $ 2^{20}$ 页。相应的，一个进程的页表中，最多会有 $ 2^{20}$ = 1M = 1,048,576 个页表项，所以一个页表最大需要 $ 2^{20}*4B=2^{22} B$，共需要 $ 2^{22}/2^{12} =2^{10}$ 个页框存储该页表。
根据页号查询页表的方法：K 号页对应的页表项存放位置=页表始址+K*4，要在所有的页表项都连续存放的基础上才能用这种方法找到页表项。
根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。

问题一：

页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。

解决办法：使用两级级页表。

问题二：

没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。

解决办法：可以在需要访问页面时才把页面调入内存（虚拟存储技术）。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存。若想访问的页面不在内存中，则产生缺页中断（内中断/异常），然后将目标页面从外存调入内存。

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

把页表再分页并离散存储，然后再建立一张页表记录页表各个部分的存放位置，称为页目录表，或称外层页表，或称顶层页表。

3、如何实现地址变换？

按照地址结构将逻辑地址拆分成三部分；
从 PCB 中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置；
根据二级页号查二级页表，找到最终想访问的内存块号；
结合页内偏移量得到物理地址。

4、两级页表问题需要注意的细节

（1）各级页表的大小不能超过一个页面

若分为两级页表后，页表依然很长，则可以采用更多级页表，一般来说各级页表的大小不能超过一个页面。

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

页面大小 = 4KB = $ 2^{12}B$，按字节编址，因此页内偏移量为 12 位；
页号 = 40-12 = 28 位；
页面大小 = $ 2^{12}B$，页表项大小 = 4B，则每个页面可存放 $ 2^{12}/4=2^{10}$ 个页表项。

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

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

（2）访存次数分析

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

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

5、总结

五、基本分段存储管理方式

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

1、分段

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从 0 开始编址。

内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）所组成。

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

2、段表

程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”。

每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称 “基址”）和段的长度。
各个段表项的长度是相同的。例如：某系统按字节寻址，采用分段存储管理，逻辑地址结构为（段号 16 位，段内地址 16 位），因此用 16 位即可表示最大段长。物理内存大小为 4GB（可用 32 位表示整个物理内存地址空间）。因此，可以让每个段表项占16+32=48 位，即 6B。由于段表项长度相同，因此段号可以是隐含的，不占存储空间。若段表存放的起始地址为 M，则 K 号段对应的段表项存放的地址为 $ M+K*6$。

3、地址变换

4、分段、分页管理的对比

页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的（只需让各进程的段表项指向同一个段即可实现共享）。可修改的代码是不能共享的（比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致）。

5、总结

六、基本段页式管理方式

分页和分段的优缺点：

名称	优点	缺点
分页管理	内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片	不方便按照逻辑模块实现信息的共享和保护
分段管理	很方便按照逻辑模块实现信息的共享和保护	如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片

分段+分页=段页式管理。将进程按逻辑模块分段，再将各段分页（如：每个页面 4KB）再将内存空间分为大小相同的内存块/页框/页帧/物理块，进程前将各页面分别装入各内存块中。