操作系统学习笔记-12：内存分配（二）：非连续分配

在上一篇笔记中介绍的是连续分配，包括固定分区分配和动态分区分配。但前者容易产生内部碎片，后者容易产生外部碎片（虽然可以用紧凑技术解决，但是有一定的成本），都不是理想的解决方案。这篇笔记会介绍另一种分配方式，即非连续分配（离散分配），主要包括：基本分页存储管理、基本分段存储管理、段页式存储管理。

下面是这篇笔记的思维导图：

一. 基本分页存储管理

1. 基本思路

在连续分配中，一个进程不可被分割，只能整体放入一块连续的内存空间中；但在基本分页存储管理中，允许把一个进程按照固定大小 X 分割为多个部分，同时把内存也按照固定大小 X 分割为多个部分，并把前者对应地放到后者中（不要求连续存放）。通常来说，一个进程的最后一部分会小于 X ，这部分若放到内存的某个 X 空间中，则仍然会产生碎片（这种碎片称为页内碎片），要让这种碎片尽可能小， X 也必须尽可能小。

2. 页面、页框

• 页面：具体来说，把内存分割为多个固定大小 X 的部分，这些部分就叫做页框/页帧/物理块/内存块，每个页框会有一个数字编号，第一个页框就从 0 开始

• 页框：同样，进程分割为多个固定大小 X 的部分，这些部分就叫做页面/页，每个页面会有一个数字编号，第一个页面就从 0 开始

正如我们在上面讲过的，进程的最后一个页面通常无法利用完整个页框，会不可避免地产生页内碎片，为了让碎片足够小，必须控制好单个页框的大小，不能过大。

系统以页框为单位为各个进程分配内存空间，一个页面就对应一个页框，它具体放到哪个页框，这是随意的，无需顾虑先后顺序，无需顾虑是否连续或者相邻。

3. 地址转换的思路

这里还需要考虑一个地址转换的问题。假设我们采用的是动态重定位方式进行地址转换，那么在模块装入的时候，显然程序中还是逻辑地址，但在程序执行到需要访问地址的时候，就要进行逻辑地址到物理地址的转换了。

具体怎么转换，这是一个问题。这里先以十进制地址讲解地址转换，体会大概的过程，再用二进制地址讲解。

3.1 十进制地址

左边进程按照 50b 的大小分为 4 个页面，右边内存按照 50b 的大小分为若干个页框：

在程序执行到指令 1 的时候，需要访问地址 80，这是一个逻辑地址，需要转换成对应的物理地址。转换步骤如下：

• 计算逻辑地址的页号
• 根据页号找到页号对应页面在内存中的起始地址
• 计算逻辑地址在当前页面内的偏移量
• 物理地址 = 起始地址 + 页内偏移量

从左图可以看出，逻辑地址 80 在 1号页面内，而 1 号页面对应的是右图中的红色页框，起始地址为 450；逻辑地址 80 在 1号页面内的偏移量 为 30；所以物理地址 = 450 + 30 = 480

也可以用计算的方法，在已知逻辑地址的情况下：

• 页号 = 逻辑地址/页面长度，即 80/50 = 1（取整数部分）；
• 页内偏移量 = 逻辑地址%页面长度，即 80%50 = 30；

3.2 二进制地址

当然，地址实际上是用 32 位二进制数表示的。这时候计算页号和页内偏移量实际上更加简单，因为地址本身已经包含了这两者。以页面/页框大小 4kb 为例：

一个页面 4kb 大小，也即 2^12^b = 4096b 大小。那么，0 号页、1 号页、2 号页的表示就是：

这里会发现，地址的前 20 位（红色部分）表示页号：全是 0 表示 0 号页，末尾 1 表示 1 号页，末尾 10 表示 2 号页……以此类推；地址的剩余（黑色）部分表示页内偏移量。所以说地址本身其实已经包含了这两者的信息。

若页面/页框大小位 1kb，也即 2^10^b =1024b 大小，那么同样可以发现，地址的前 22 位表示页号，地址的剩余部分表示页内偏移量：

总结下来，规律就是：

如果页面/页框大小为 2^k^ b，那么前面部分表示页号，末尾 k 位表示页内偏移量。在页面/页框大小为 2 的整数幂的时候，就可以直接从地址看出页号和页内偏移量，因此建议将页面/页框大小设置为为 2 的整数幂。

3.3 页表

根据地址，就已经可以知道页号和页内偏移量，剩下还有一个工作就是 根据页号找到页号对应页面在内存中的起始地址 。

对于每一个进程，可以维护一张页表，用它来记录页面号（页号）与页框号（块号）的映射关系，可以根据页号找到页号指代页面在内存中对应页框的编号：

根据地址知道页号后，从页表中找出页号对应的块号，再用块号 * 页面/页框大小，即可算出块的起始地址，再用起始地址加上偏移量，即可算出物理地址。

4. 地址变换机构

4.1 基本地址变换机构

上面所说的地址转换是通过 基本地址变换机构 这个硬件实现的，它借助页表将逻辑地址转换为物理地址。转换过程如下：

在程序未执行的时候，PCB 中存放程序对应页表的初始地址 F 以及页表长度 M（页表项个数）。程序一旦开始执行，F 和 M 会被送到页表寄存器中。在需要访问地址的时候，基本地址变换机构开始运行：

X + size*P

在上面例子中，由于涉及到的都是二进制数，所以要计算物理地址，只需要将块号二进制数与偏移量二进制数拼接即可，这是比较方便的，如果例子给出的是十进制数，那么可以用 块起始地址 + 页内偏移量 进行计算，计算结果可以再转化为二进制数，结果其实也是一样的。比如：

若给定的是十进制：

页面大小 1kb，块号 2，偏移量 1023。

那么块起始地址等于 2*1kb = 2*1024b=2048b ，又偏移量 1023，所以物理地址等于 2048+1023=3071 ，转化为 32 位二进制数，就是 0000000000000000000010,1111111111

若给定的是二进制：

页面大小 1kb，块号 2，偏移量 1111111111。

那么块号 2 转化为 22 位二进制数就是 0000000000000000000010 ，与偏移量拼接，就得到 0000000000000000000010,1111111111 ，可以看出与上面的结果是一样的。

4.2 具有快表的地址变换机构

在前面的基本地址变换机构中，存在两个问题：

• 每次存取数据都需要 访问内存两次 ：第一次访问内存中的页表，找到块号，并将块号与偏移量拼接得到物理地址；第二次，根据物理地址访问内存中存放的数据。第二次访存肯定是不能避免的，但是第一次访存其实可以想办法避免
• 若多条指令涉及到的逻辑地址的页号都相同，则每次都得经历第一次访存，找到该页号对应的块号

上面这两个问题可以通过引入快表来解决。

快表又叫做联想寄存器，它是一种访问速度比内存快很多的高速缓冲存储器，用以存放访问过的页表项的副本，从而加快地址转换的过程 —— 也就是说，引入快表后，地址转换可以不需要经历第一次访存，而是直接从快表中拿到需要的页表项。与之对应的，内存中原本的页表，叫做慢表。

此时，地址变换机构的运行过程和之前还是差不多的，只是多了一个快表的处理过程：

在程序未执行的时候，PCB 中存放程序对应页表的初始地址 F 以及页表长度 M（页表项个数）。程序一旦开始执行，F 和 M 会被送到页表寄存器中。在需要访问地址的时候，地址变换机构开始运行：

• 首先将地址拆分为页号和页内偏移量两个部分，然后将页号与页表寄存器中的页表长度作比较。若越界，则发生越界中断。若不越界，来到下一步
• 该页号被送往快表，并与其中的页表项一一比较，寻找是否有配对的页号，因为这里我们是第一次查询，所以是没有的，即 未命中 ，此时来到下一步
• 经历第一次访存，在内存的页表中找到页号对应的页表项的地址，找到这个地址就意味着找到了页号对应的块号
• 将该页表项拷贝一份副本放到快表中
• 将块号与偏移量（注意这两个都是二进制）拼接，就得到了物理地址
• 根据物理地址，就可以访问到目标

假设又一次地，我们需要访问某个地址，并且这个地址与前次访问的地址的页号一样：

• 首先将地址拆分为页号和页内偏移量两个部分，然后将页号与页表寄存器中的页表长度作比较。若越界，则发生越界中断。若不越界，来到下一步
• 该页号被送往快表，并与其中的页表项一一比较，寻找是否有配对的页号，因为之前我们已经在快表中存放了一份页表项的副本，所以找到了配对的页号，即 命中 ，此时来到下一步
• 从快表中读出该页号对应的块号，并与偏移量拼接，就得到了物理地址
• 根据物理地址，就可以访问到目标

这里可以注意到，由于第一次查询到页号对应的块号后，我们将页表项拷贝了一份副本放到快表中，所以以后再涉及到相同的页号时，只需要先来到快表查找即可，找到了就直接拼接得到物理地址，无需再到内存中去访问页表，寻找页号对应的块号。

当然，由于成本的关系，快表不会做得很大，但对于中小型作业来说也已经足够，只是对于大型作业来说，不太可能把全部页表项都存放到快表中。

某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。假设访问一次快表耗时 1us，访

问一次内存耗时 100us，快表的命中率为 90%。

• 若未引入快表，则访问一个逻辑地址耗时 100 + 100 = 200us

• 若引入快表，则访问一个逻辑地址耗时 (1+100) * 0.9 + (1+100+100) * 0.1= 111 us

• 若引入快表，且该系统支持同时查询快表和慢表，则访问一个逻辑地址耗时 (1+100) * 0.9 + (100+100) * 0.1 = 110.9us

  显然，引入快表后，访问一个逻辑地址的速度快多了。

5. 页表项的大小

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

4GB=2^32^ b， 4KB=2^12^b，因此 4GB 的内存总共会被分为 2^32^/2^12^ = 2^20^ 个内存块，因此内存块号的范围应该是 0～2^20^-1。因此对于单个页表项，它至少要用一个 20 位二进制数才能表示这样的一个内存块号，而一个字节 8 位，所以至少要三个字节才可以表示这样的一个内存块号。又由于实际不知道哪个页表项存放哪个内存块号，所以所有的页表项统一得用到至少三个字节。

但是一个页表项用三个字节其实会出现一些问题。类似于进程被拆分为多个页面存储在内存中一样，页表也是被拆分为多个页表项存储在内存中的。假设页面/页框大小为 4kb，也即 4096b，由于一个页表项 3b，所以一个页框至多可以放 4096/3=1365 个页表项，并且这个页框剩余 1b 的空间。由于 1b 不足以再存放一个页表项，所以第 1366 个页表项（1365 号页表项）只能放在下一个页框中了。

这就会导致，前面 1365 个页表项的地址依然可以采用 X + 3*P 的方式计算，但是第 1366 个页表项，它的地址却应该是 X + 3*P + 1 ，也就是说，我们无法以一个通用的式子去计算页表项的地址。

为此，建议一个页表项大小应为 4b 而不是 3b（选取 2 的整数幂）。因为如果页表项大小为 4b，那么一个页框就刚好可以放 4096/4=1024 个页表项，不会有剩余空间，而余下的页表项也可以依次放在下一个页框中。这样的话，涉及到页表项地址的计算，都可以用通用的式子 X + 4*P 来计算，就无需考虑 由于页框无法得到完全利用 而带来的查询麻烦的问题了。当然，为了这个式子能够通用，页表通常也应该 连续地存放在内存块 中，中间不出现断节。

6. 两级页表

6.1 单极页表的两个问题：

前面使用的单极页表存在两个问题：

① 页表占用过大的、连续的内存空间：

假设页面/页框大小 4kb，页表项大小 4b，可以考虑一下一个页表会占用多大的空间：

• 计算页表一共有多少个页表项：首先，4kb = 2^12^b，所以 32 位逻辑地址中，后 12 位表示偏移量，前 20 位表示页号。总共有 2^20^ 个页面，也就是有 2^20^ 个页表项需要存放。
• 计算一个页框可以放多少个页表项：一个页框 4kb，一个页表项 4b，所以一个页框可以放 4*1024/4 = 1024 个页表项
• 计算存放所有页表项需要多少个页框：2^20^/1024 = 1024

一共需要 1024 个页框才能放下整个页表，而且为了以通用的式子计算页表项地址，还要求页表必须是连续存放的，这其实违背了当初进行分页存储的初衷。

② 页表常驻内存

其实在执行某个程序的时候，我们往往只需要访问特定的几个页面，但即便如此，整个页表也还是常驻在内存中的，这其实是没有必要的。我们可以想办法只让当前需要用到的页表项调入内存。

6.2 解决问题一：引入两级页表

就像之前可以把进程拆分为多个页面一样，这里也可以考虑对页表本身进行拆分：

将长长的页表分为多个子页表，再将每一个子页表离散地存放到各个内存块中。比方说，前面我们说过，一个页框可以放 1024 个页表项，那么就可以每隔 1024 个页表项就拆分出一个子页表出来，由于页表一共有 2^20^ 个页表项，所以一共可以拆分出 1024 个子页表，这些子页表再各自存放到内存块中。

同样的，我们需要一张表用来记录子页表页号和块号之间的映射关系，这个表即页目录表/外层页表/顶层页表。如下图，页目录表此时作为一级页表，原页表拆分后形成的多个子页表作为二级页表：

同时，原有的逻辑地址的含义也发生了改变。在单级页表中，前 20 位表示页号；而在两级页表中，前 10 位表示一级页号，紧跟着的 10 位表示二级页号。这么划分之后，一级页号共有 2^10^=1024 种可能的取值，刚好就与页目录表有 1024 个页表项对应；而二级页号也有 2^10^=1024 种可能的取值，刚好就与子页表有 1024 个页表项对应。

在需要进行地址转换的时候：

• 首先将逻辑地址分为三个部分：一级页号、二级页号、页内偏移量
• 然后从 PCB 中读出页目录表的初始地址，结合一级页号以及每个页表项的大小，找到一级页号对应页表项的地址，即找到了对应页表项，也就找到了一级页号对应的内存块号
• 根据内存块号到内存中找到对应的那个二级页表（原页表的某个子页表）
• 在二级页表中，根据二级页号找到对应的块号
• 块号与偏移量结合，得到物理地址

上面的过程也可以直接看这幅图理解：

6.3 解决问题二：虚拟存储技术

事实上，没有必要在一开始就把所有的页表项都调入内存中，我们可以借助虚拟存储技术，在需要访问页面的时候才把对应的页表项调入内存。具体的知识后面再进行讲解。

6.4 补充

某系统按字节编址，采用 40 位逻辑地址，页面大小为 4kb，页表项大小为 4b，假设采用纯页式

存储，则要采用多少级页表？页内偏移量为多少位？

4kb = 4*1024b = 2^12^b，根据之前讲过的规律，页面偏移量应该是 12 位。40 - 12 = 28，所以前面 28 位用来表示页号。

因为 采用多级页表后，各级页表的大小不能超过一个页面 ，而一个页面最多只能放 1024 个页表项，所以应该限制页表最多最多只能包含 1024 个页表项（否则就放不下多余的页表项，导致页表超过一个页面了）。由于页号在逻辑地址中是用二进制数表示的，因此页号最多需要十位二进制数去表示所有的 1024 个页表项（比如第 1023 个页表项的页号就会是 1111111111）。当然，这考虑的都是“最多”的情况，页表实际上不一定都能包含 1024 个页表项，因此页号实际上不一定都需要 10 位二进制数来表示（意思是，若页表项没有这么多，位数就不需要这么多了，可以少于 10 位），但就这道题而言，在逻辑地址的前 28 位中，可以选择 10 位用于表示某一级的页号（这一级的页表假设页表项可能有 1024 个这么多），再用 10 位表示某一级的页号（这一级的页表假设页表项可能有 1024 个这么多），再用剩下的 8 位表示某一级的页号（这一级的页表假设页表项远远少于 1024 个）。

那么，就可以考虑前面 8 位作为一级页号，紧接着的 10 位作为二级页号，再紧接着的 10 位作为三级页号，这样刚好就用完了逻辑地址前 28 位。所以回到问题，这里需要采用三级页表。

我们也可以反过来考虑，若这里不采用三级页表，而强行使用二级页表，那么肯定有某一级的页号位数超过了 10，位数超过 10 说明页表的页表项个数超过了 2^10^=1024 个，很显然就会导致一个页框放不下这一级的页表，需要跨页，这与我们前面的规定 —— 采用多级页表后，各级页表的大小不能超过一个页面 ，是相悖的。

7. 习题

最后，可以做一些题目来巩固一下。

1.若系统采用两级分页存储方式，物理内存 64mb，页面大小 1kb，页表项大小 2b，则顶级页表有多少个页表项？

这里我们可以参考之前求页表项大小的思路。物理内存 64mb，即 2^26^b，所以逻辑地址一共 26 位。这 26 位中，一部分表示一级页号，一部分表示二级页号，剩下的表示页内偏移量。

因为页面大小 1kb，也即 2^10^b，所以页内偏移量一共需要 10 位来表示。一个页面大小 2^10^b，一个页表项 2b，所以一个页面可以最多可以放 2^9^ 个页表项，又由于 各级页表不能超过一个页面 ，所以各级页表不能超过 2^9^ 个页表项。在逻辑地址余下的 16 位中，可以用其中 9 位去表示二级页表的页号（此时该页表的页表项个数取到了最大值），剩下的 7 位表示另一个 —— 顶级页表的页号。因为顶级页表页号有 7 位，所以顶级页表可以包含 2^7^ 个页表项，即包含 128 个页表项。

2.若系统采用分页存储方式，物理内存 256mb，页面大小 1kb，页表如下：

页号 0，1，2，3，4，5，6，7，8，9，10 分别对应块号 15，16，20，28，29，30，31，32，36，38，39

则逻辑地址 1A68（16进制）对应的物理地址是多少？

为了方便计算，我们先统一用十进制计算，得到十进制的物理地址后再转换为十六进制。

1A68 按权展开转化为对应的十进制数字是 6760，对于逻辑地址 6760，可以计算它的页号和页内偏移量：

• 页号 = 6760/1024 = 6（取整数部分）
• 页内偏移量 = 6760%1024 = 616

根据页号 6 找到块号 31，根据块号 31 计算块初始地址为 31*1024 = 31744，偏移量和初始地址相加得到的物理地址为 31744+616 = 32360。32360 是十进制的物理地址，转化为对应的十六进制物理地址就是 7E68。

二. 基本分段存储管理

1. 基本思路

在基本分页存储管理中，我们是将程序分为多个大小相等的物理单元（页面）；而在基本分段存储管理中，我们倾向于从逻辑功能的角度去考虑，将程序 分为多个逻辑功能段 ，每个段都有自己的段名，并且都是从 0 开始编址的。在分配的时候是以段为单位进行分配的，在内存中，段内所占空间是连续的，但是各个段之间可以不相邻。

如下图，进程 A 按照逻辑功能被划分为三个段，每个段大小不一，最后再被分配到内存中不连续的各个空间中：

由于引入了分段存储管理，所以可以将程序按照逻辑功能模块进行划分，程序员在编写程序的时候也会更加方便，程序的可读性会更高，比如：

LOAD 1，[D]|<A>
STORE 1，[X]|<B>

分别表示：将分段 D 中 A 单元内的值读入寄存器 1，以及将寄存器 1 的值存入分段 X 的 B 单元中。很显然，逻辑上是非常清晰的。这里的分段 D 和 X 都是段名，程序员在编程的时候只需要使用段名，而在编译的时候，段名会转化为对应的短号，同理，A、B 单元表示的其实是地址，编译的时候也会转化为对应的地址。

2. 逻辑地址

在引入分段存储管理后，逻辑地址的含义也不同了。假设仍然是用 32 位二进制数表示逻辑地址，此时，地址的前 16 位将表示段号，后 16 位表示段内偏移量：

• 由于段号是 16 位二进制数，也就是说段号有 2^16^ 种取值，即每个进程最多最多可以被分为 2^16^ 个段；
• 由于段内偏移量也是 16 位二进制数，也就是说在一个段内，段内地址可能有 2^16^ 种取值，所以一个段的最大长度为 2^16^

3. 段表

3.1 段表的三列

类似的，我们需要用 段表 来记录某个编号段与实际物理存放位置之间的映射关系。在分页存储管理中，程序被分为多个大小相等的页面，内存被分为多个大小相等的页框，一个页面对应一个页框，因此只需要用页号和块号这两列即可记录两者之间的映射关系。推导出块的初始地址也是很简单的，只需要用块号乘以块的大小。

但在分段存储管理中，程序被分为大小不等的多个段，我们没办法像之前一样只需要块号即可推导出块的初始地址，为了准确地找出段存放在内存中的位置，我们要将 段号、段长、基址 这三者作为段表的三列。这样，根据段号可以在段表中找到对应段在内存中的初始地址（基址），再结合段长，可以知道这个段具体占用了哪里的空间。

如下图所示：

3.2 确定段表项的大小

还需要考虑的一个问题是每一个段表项的大小。每个段表项由段号、段长、基址构成，我们可以依次考虑每一列可能占用的空间（假设物理内存 4GB，按字节寻址）：

• 基址：因为物理内存 4GB，也就是 2^32^b，那么内存中的地址最多可能取到 2^32^ 种值，因此为了让基址列 足够 表示完这样的值，设定基址列大小占用了 32 位
• 段长：前面说过了，在逻辑地址中，段号和段内偏移量都是 16 位，所以段内偏移量最多可能取到 2^16^种值，为了让段长列足够表示完这样的值，设定段长列大小占用了 16 位
• 段号：在逻辑地址中，段号是占用了 16 位的。但是其实在段表中可以不显式指出段号，因为我们只需要知道 段表的起始地址、每个段表项的大小以及段号 ，就能很容易地知道某个段号对应的段表项的地址，而无需去维护一个从段号到段表项的映射，也即，无需显式指出某一个段表项的段号是多少。段号是隐含的，它不需要占用存储空间。

综上，每个段表项占用了 16+32=48 位，由于一个字节 8 位，所以占用了 6 个字节， 即 6b。

4. 地址转换

转换过程我们可以直接看下图理解：

可以联系之前使用分页存储时的地址转换过程来理解，两者的基本流程其实是差不多的，只需要格外注意个别差异。

• 在需要将逻辑地址转换为物理地址的时候，首先会将逻辑地址分为段号和段内偏移量两个部分，段表寄存器中的段表长度代表了程序总共被分为多少个段，因此段号不应该超过段表长度，若超过则发生了越界中断，若不超过，进入下一步
• 根据段号、段表初始地址以及段表项的大小，找到段号对应的段表项。比较段表项中的段长 C 和逻辑地址中的段内偏移量 W，若 W>=C，说明越界了；反之则进入下一步（ 注意这里要与分页存储相区分 ）
• 在段表项中找到段号对应的基址，将该基址与段内偏移量拼接，得到物理地址
• 根据物理地址来到内存中访问相关的目标单元

5. 两种基本存储方式的对比

5.1 划分的角度和维度

5.2 信息的共享和保护

在分段存储方式中，更容易实现信息共享和保护：

在分页存储方式中，则很难：

5.3 访存次数

关于访存次数，两者都是一样的：

• 在不引入快表的情况下，分页存储方式的第一次访存是访问内存中的页表，第二次是访问内存中的目标单元；若引入快表，则第一次访存有可能因为命中而得到避免
• 分段存储方式的第一次访存是访问内存中的段表，第二次是访问内存中的目标单元。它也可以引入快表，若引入快表，则第一次访存有可能因为命中而得到避免

段页式存储管理

1. 基本思路

• 采用分页存储管理，内存利用率高，不会产生外部碎片，仅会产生少量内部碎片；但是不方便按照逻辑模块实现信息的共享和保护
• 采用分段存储管理，很方便按照逻辑模块实现信息的共享和保护，但是若逻辑过多则会导致段过长，另外，这种方式也会产生外部碎片

所以结合二者之长，出现了段页式存储管理方式。

如下图，段页存储管理会首先将进程按照逻辑模块划分为多个段，针对每个段再划分为多个页；同时也把内存划分为多个页框。分配内存的时候，一个页面就对应了一个页框。

2 逻辑地址

在分段存储管理中，给出一个逻辑地址，可以划分为段号和段内地址两个部分；而在段页存储管理中，段内地址还要继续细分成页号和页内偏移量两个部分。所以逻辑地址由 段号、页号和页内偏移量 三个部分组成。

段号的位数仍然决定了一个进程可以被划分为多少个段，而页号的位数则决定了一个段可以被划分为多少个页面，页内偏移量则决定了一个页面可以有多大，即页面/页框大小。

和分段存储管理一样，段页存储管理的地址结构也是二维的。

3. 段表

段页存储管理中的段表不同于分段存储管理中的段表。由于我们是将程序划分为多个段，相当于划分为多个子程序。对于每一个子程序而言，它会再次被划分为多个页面，因此每一个段（每一个子程序），它都维护着属于自己的一张页表。对于我们的段表来说，它需要记录的就是段号与段号对应段的页表之间的映射关系 —— 具体地说，包括这个页表的长度，以及这个页表所在块的块号（或者页表所在块的起始地址也可以）。

所以，段表应该有三列： 段号、页表长度、页表所在块的块号 。如下图所示：

4. 地址转换

关于地址转换，可以直接看下图理解：

这里，地址转换机构的运行其实是结合了分页存储和分段存储的方式。

• 在需要将逻辑地址转换为物理地址的时候，首先会将逻辑地址分为 段号、页号和页内偏移量 三个部分，段表寄存器中的段表长度仍然代表了程序总共被分为多少个段，因此段号不应该超过段表长度，若超过则发生了越界中断，若不超过，进入下一步
• 根据段号、段表初始地址以及段表项的大小，找到段号对应的段表项。这个段表项记录了段号对应段的页表的相关信息。 注意这里 ，同样要比较段表项中的页表长度和逻辑地址中的页号 P，若页号大于等于页表长度，说明越界了；反之则进入下一步
• 我们已经找到了段表项，也就找到了段的页表所在块的块号。根据这个块号，在内存中找到这个块，再从块中找到页表
• 根据逻辑地址中的页号，在页表中找到页号对应的块号，将块号和逻辑地址中的页内偏移量拼接，得到物理地址
• 根据物理地址，再次来到内存中访问相关的目标单元

5. 访存次数

在不采用快表的情况下，段页式存储管理需要经历三次访存：第一次访存，访问内存中的段表，找到段表中记录的页表信息；第二次访存，访问内存中的页表，找到了目标单元所在的块；第三次访存，访问内存中的目标单元。而如果是采用了快表，那么同样会有一个专门的高速缓冲寄存器保存一份副本，可以利用段号和页号去寄存器中进行检索，若检索到（命中），则无需经历第一次和第二次访存，可直接拿到块号并和偏移量进行拼接，得到物理地址，之后只需要访存一次即可。也就是说，引入快表后，省下了两次访存。

操作系统系列学习笔记：

操作系统学习笔记-1：基础概念

操作系统学习笔记-2：体系结构和运行机制

操作系统学习笔记-3：初识进程和进程控制

操作系统学习笔记-4：进程同步与进程互斥（一）

操作系统学习笔记-5：进程同步与进程互斥（二）：信号量机制

操作系统学习笔记-6：进程同步与进程互斥（三）：经典问题

操作系统学习笔记-7：进程通信

操作系统学习笔记-8：线程

操作系统学习笔记-9：调度

操作系统学习笔记-10：死锁

操作系统学习笔记-11：内存分配（一）：连续分配 )