316_基本分页存储管理的基本概念
# 3.1_6_基本分页存储管理的基本概念
各位同学大家好，在这个小节中我们会学习基本分页存储管理的几个基本概念，在之前的几个小节中，我们学习了几种连续分配的内存管理方式，但是连续分配方式都有一些很明显的缺点
比如说如果采用的是固定分区分配的方式的话，由于每一个分区只能分配给某一个进程使用，如果进程占不满一个分区的话，分区当中就会有很大部分的内存是被浪费掉的，这就导致会产生大量的内部碎片，从而内存的利用率会很低
如果说采用的是动态分区分配方式的话，也会有一另外的问题，各个进程之间会留下一些难以利用的很小的外部碎片，这些外部碎片虽然说可以用紧凑技术来处理，但是紧凑技术要付出的时间代价是很高的
所以很显然连续分配的这些存储管理方式都有一些很显而易见的缺点，其实造成连续分配方式的这些缺点的一个本质原因就在于连续分配方式要求进程占用的必须是以一整段的连续的内存区域。
因此人们自然而然的想到能不能让一个进程分散的装到许多个不相邻的分区当中呢？比如说一个 6 兆的进程进入这个系统，能不能把 6 兆的进程拆分为 2，2，2 这样三个部分，然后分别放到这三个地方。如果说能实现这个事情，就可以更充分的利用内存，并且就不再需要紧凑这种代价很高的操作。
所以基于这个思想就产生了非连续分配方式或者说离散分配方式。所以连续分配管理方式和非连续分配管理方式的区别就在于，连续分配管理方式要求为用户进程分配的必须是一个连续的内存空间。
而如果采用的是非连续分配的管理方式的话，为用户进程分配的就可以是一些分散的离散的内存空间。从小节开始，我们会学习这样的几种非连续分配管理方式，这个小节中我们先介绍基本分页存储管理
# 把固定分区分配 改造为 非连续分配版本
接下来我们再沿着刚才的思路继续往下分析。假设一个系统采用的是固定分区分配方式，并且每个分区的大小相等，把用户区分为了 10 兆、10 兆、10 兆这样的一些部分，
此时如果说有一个进程 a，大小为 23 兆字节的进程到达了在固定分区分配方式当中，由于规定每一个进程只能使用某一个分区，因此由于分区的大小只有 10 兆，所以进程 23 兆显然是放不下的，除非采用了覆盖技术
但是如果说我们能够把固定分区分配方式改造成一种非连续分配的版本，这个问题其实就可以解决了。比如说我们可以把 23 兆字节的进程把它拆分为 10 兆、10 兆、3 兆这样三个部分，然后再把这三个部分分别放到不同的分区里，显然第一个部分和第二个部分，他们都可以占满自己的对应的分区。只有第三个部分是会产生一些内部碎片的内部碎片大小为 7 兆，内部碎片的大小还是比较大的
能不能用某种方法让一个进程产生的内部碎片变得更小？其实我们可以考虑把分区的大小再缩小一些，比如说我们把整个用户区间把它分为大小为两兆的若干个分区，然后把进程 a 拆分成 11 个 2 兆字节的部分，再加上一个一兆字节的部分，也就是总共 23 兆字节，总共 12 个部分，只有最后一个一兆字节的部分会占不满两兆字节的分区。不过最后一个部分它只会产生一兆字节的内部碎片，所以可以看到如果我们把每个分区的大小比从 10 兆便缩小为了两兆，显然内部碎片是会更小的。显然如果我们把每个分区的大小再设置的更小一些的话，内部碎片还可以再更小，大家可以自己推一下，从而内存的利用率就会变得更高。
其实我们刚才把固定分区分配方式改造成非连续分配版本的这种思想，其实就是基本分页存储管理的思想。基本分页存储管理会把内存分为一个个大小相等的小分区，再按照分区的大小再把进程也拆分成一个一个小的部分。
# 分页存储管理的基本概念
我们可以把内存分为一个个大小相等的分区，比如说每个分区的大小是 4KB 这么多，这样一个分区就是一个页框，或者叫一个页帧，一个内存块或者物理块这个名词很多，但是不同的出题人可能会用不同的名词来进行描述，大家对所有的这些描述方式都需要有印象
每一个页框会有一个编号，这是操作系统为了方便管理这些页框而设置的，而这个编号就是所谓的页框号或者叫内存块号，页帧号物理快号，需要注意的是页框号是从零开始的，而不是从一开始。那编号小的页框是在低地址部分，编号大的页框是在高地址部分，
相应的我们可以把一个用户进程的地址空间也分割成一个个和页框大小相等的区域，比如说我们的页框大小是 4kb，那么我们就把进程分割成 4k，4k，4k 这样的几个部分，每一个部分就称之为一个页或者一个页面，而相应的每个页面也会有一个编号，并且这些编号也是从 0 开始的，这个编号就是所谓的页号或者叫页面号，这个地方一定要注意页面和页框页帧的区别，在刚开始学习这部分的内容的时候，这几种描述都是很容易混淆的。
另外一个进程的最后一个页面可能并没有一个页框那么大，比如说进程假如它只有 15KB 的话，最后这个页面的大小就应该是 3KB，那 3KB 的页面放到一个页框里，显然是会产生 1KB 的内部碎片的，因此我们的页框不能设置的太大，否则就有可能会产生过大的内部碎片。就像咱们在前一页 PPT 里讲的那样，
在进行这样的设置之后，操作系统会以页框为单位，为各个进程分配内存空间，进程的每一个页面会被放入到一个相应的页框里，也就是说页面和页框是有一一对应的关系的。
另外由于我们采用的是非连续分配的思想，所以这些进程的页面不一定必须连续的存放在一些相邻的页框当中，也不一定按照先后顺序来。
# 如何实现地址转换
在了解了这些基本概念之后，我们再来展开探讨应该怎么实现这种分页存储的功能。在采用了分页技术之后，一个进程会被分为不同的一个一个的页面，并且这些页面会被离散的，不按顺序的放到内存的各个页框当中。
所以在采用了这种技术之后，其实最大的难点是在于我们应该如何实现从逻辑地址到物理地址的转换。在聊这个问题之前，我们来看一下之前咱们学过的那些地址转换的思想，能不能被迁移到分页这种机制当中。
之前咱们学过进程，如果在内存当中连续存放的话，那么我们可以采用动态重定位的方式来实现逻辑地址到物理地址的转换。如果采用的是这种方式，那么我们在装入这个模块之后，这些指令使用的地址依然是逻辑地址，而地址转换的过程会一直到指令执行的时候才会进行，
那系统会设置一个重定位寄存器，用来存放此时这个模块的起始地址到底是多少。假如现在 CPU 正在执行指令 1 操作，由于现在要操作的是逻辑地址为 80 的内存单元，这个逻辑地址对应的实际物理地址应该是逻辑地址的值，再加上重定位寄存器里存放的模块的起始位置的值，也就是 180，用这种方式 CPU 就可以对实际的物理地址进行相应的操作。
所以动态重定位这种方式的核心思想就是我们要记录下各个模块的起始位置，而由于每一个模块之内是连续存放的，因此我们只需要用模块的起始位置，再加上我们实际要访问的内存单元的逻辑地址，就可以得到最终的物理地址。
这个逻辑地址其实我们也可以把它理解为是我们要访问的内存单元，相对于起始位置来说的一个偏移量。因此我们只要能够知道一个模块的起始地址，和我们要访问的内存单元相对于模块起始位置来说的偏移量，只要知道这两个东西，我们肯定就可以算出一个逻辑地址对应的物理地址到底是多少。
接下来我们再把这种思想迁移到分页技术当中，在采用了分页技术之后，一个进程的逻辑地址会被分为一个个页面，比如说像刚才的例子当中，如果我们规定这个系统当中每个页面的大小是 50 个字节，也就 50 个内存单元，那么进程它会被分为 4 个页面，01230。号页对应的是进程的逻辑地址 0~49，这样 50 个地址空间，1 号页对应的是 50~99 这样 50 个地址空间，2 号页和 3 号页以此类推，这些页面会被离散的放到内存的各个页框当中，比如说 0 号页面放到内存的一个页框当中，它对应的实际物理地址是 100~149 这样 50 个内存单元，而一号页放到内存当中对应的是 450~499 这样 50 个内存单元
如果说此时 CPU 正在执行指令 1，而指令 1 又要求 CPU 去访问逻辑地址为80 的内存单元，我们应该怎么找到这个逻辑地址对应的实际物理地址呢？
其实这个地方我们可以把每一个页面看作一个个连续存放的模块，虽然各个页面之间是离散的存放的，但是页面之内这些内存单元其实是连续的，所以利用之前提到的那种思想，如果我们能够知道一个模块的起始地址是多少，并且能够知道这个逻辑地址对应于这个模块的起始地址而言，偏移量是多少，那么我们就可以很方便地算出这个逻辑地址，实际对应的物理地址。
结合这个图我们会发现 80 这个逻辑地址肯定是在一号页内，而一号页在内存当中存放的起始地址应该是 450 内存单元，因为这个模块是从地址为 450 内存单元开始存放的，因此 50逻辑地址对应的偏移量应该是 0，而 51 就是 450+1，所以 51 逻辑地址对应的偏移量应该是 1，以此类推，52 的偏移量应该是二，,53 的偏移量是 3，那 80 的偏移量就应该是 30 这么多，所以80 这个逻辑地址对应的实际物理地址，我们只需要用它所属的模块的起始位置，起始地址也就是 450，再加上它在这个模块当中的偏移量 30，也就是得到 480，这就是逻辑地址为 80 的内存单元对应的实际物理地址。
我们可以把上面的过程总结一下，如果说一个系统采用了分页存储管理的方式的话，那么我们想要得到某一个逻辑地址对应的物理地址需要做这样几件事。
- 第一，我们要算出这个逻辑地址对应的页号到底是多少。
- 第二，我们要知道这个页面在内存当中存放的起始地址到底是多少。
- 第三，我们还需要算出我们想要访问的逻辑地址在页面当中的偏移量到底是多少，得到了这些信息之后，我们只需要用页面在内存当中的起始地址，也就是页面始址再加上逻辑地址在页面内的偏移量就可以得到这个逻辑地址实际对应的物理地址了
其实这些计算很简单，我们只需要用逻辑地址除以页面长度，就可以得到页号，比如说刚才的这个例子当中，我们想要访问的逻辑地址是 80，而页面长度是 50，80÷50 取整数部分就是一，因此 80 这个逻辑地址对应的页号应该是一号页，页的偏移量的计算也很简单，只需要用逻辑地址，对页面长度取余就可以了，刚才这个例子当中逻辑地址是 80，对页面长度 50 取余也就是 30，那 30 就是最终的页内偏移量。
除了页号和页内偏移量之外，我们还需要知道这个页号对应的页面在内存当中存放的起始位置，为了知道每个页面在内存当中的存放位置，操作系统会用某种数据结构来记录这些信息，比如说操作系统中记录了进程的一号页，在内存当中存放的起始位置是 450
这个页号和业内偏移量的计算方法是十分重要的，在考试当中经常会给出一个逻辑地址，还有页面长度，让我们手动的计算页号和业内偏移量。
不过手动计算是这样计算的，但是对于计算机来说，其实还有一种更简单更快捷的方式来计算页号和业内偏移量。因为计算机当中的这些地址，还有所有的这些数据肯定都是用二进制来表示的，因此操作系统一般会把一个页面的大小设置为二的整数幂这么多，这样的话就可以很方便的计算页号和页内偏移量了。
我们直接来看一个例子，假设一个计算机系统当中用 32 个二进制位来表示逻辑地址，并且这个系统规定每个页面的大小是 2 的 12 次方个字节，也就是 4096 个字节，4KB，这就满足了页面的大小是二的整数幂这个条件。
由于每个页面的大小是 4096 个字节，因此每个页面对应的逻辑地址应该是有 4096 个，所以 0 号页的逻辑地址空间对应的应该是 0~4095 这么多，如果用二进制表示的话，就是这个样子这样一串的二进制位总共是 32 个，黑色画线部分是 12 位，然后红色部分是 20 位，总共 32 位。一号页的逻辑地址空间应该是 4096~8191，如果用二进制表示的话是这样子。同样的二号页的逻辑地址空间，我们也可以用二进制来表示，就是在这个范围内，这个地方大家有没有发现一个规律，每一个页面的逻辑地址空间，最后的这 12 位肯定都是从 000 一直到 111 这么个范围，而不同的页面之间的区别是在于前面的这 20 位不同，0 号页的前面这 20 位全部是 0，1 号页的前面这 20 位只有最后一个是一，别的也全部是 0，如果把这个数字转换为 10 进制的话，它对应的数字刚好是一和 1 号页的页号刚好是相同的，而 2 号页的前面 20 位把它转换成 10 进制的话，刚好是二，也就是对应二号页的页号，这个地方其实并不是巧合，如果说学过计算机组成原理，关于二进制加法相应的计算的话，为什么会呈现出这种规律，大家是可以理解的。
如果暂时还没有学到计组的同学，大家可以之后学完了再回头来看一下这个部分为什么会呈现出这样的规律，我们来看一下怎么利用这个规律。
假设我们要访问的是逻辑地址为二的内存单元，由于计算机当中所有的这些数据，包括地址这些肯定是用二进制表示的，二这个数用二进制表示就应该是这样子。我们可以根据他前面的 20 位就判断出他的页号应该是 0。另外如果我们用逻辑地址二对页面长度 4096 进行取余操作的话，那么余数刚好是二，也就是说业内偏移量应该是二，而二这个数字刚好又是后面的这 12 位二进制数转换成 10 进制之后所对应的一个数值。所以如果我们能够知道0 号页在内存当中的起始地址 x 那么逻辑地址二对应的物理地址，就可以用 x 再加上它后面的这 12 个二进制位就可以得到最终的物理地址了。
如果我们要访问的是逻辑地址为 4097 的内存单元，用二进制表示的话，它应该是这样一个数字。同样的前面的这 20 个二进职位对应的就是页号，所以页号应该是 1 号页，而在一号页内的页内偏移量，我们可以用后面的 12 位来表示，所以如果我们知道 1 号页在内存当中的起始地址为 x，那么 4097 这个逻辑地址对应的物理地址，就是 x 再加上它的业内偏移量，也就是也就是后面的这 12 个二进之位对应的数字，这个地方大家也可以和之前咱们介绍的这种手动的算法进行一个对比。
同样的如果说这个系统的页面大小是 2 的 10 次方个字节也就是 1024，或者说 1KB 这么多，那么 0 号页的逻辑地址空间应该是 0~1023，对应这样一个二进制数的范围，一号页和二号页分别是对应这样的两个二进制范围，所以这个地方大家也可以动手试一下，1026 和 2055 这两个逻辑地址，如果用二进制表示的话应该是多少？他们的页号和页内偏移量如果用这种方法算出来是多少？而如果用咱们刚才介绍的就是取前面的红色部分作为页号，取后面的这些黑色部分作为页内偏移量得到的数值又到底是多少？不过需要注意的是在这个地方我们把页面大小改为了 2 的 10 次方个字节，所以应该是后面的这 10 位来表示业内偏移量，然后前面的这 22 位来表示页号。
因此经过刚才的这一系列分析，我们得到这样的结论，如果说我们把每个页面的大小设置为 2 的 k 次方个字节，如果用二进制数来表示逻辑地址的话，那么末尾的 k 位既是页内偏移量，而其余部分也就除了这末尾的 k 位之外，前面的那些部分表示的就是页号。当然这是用二进制表示的，不过对于计算机来说这是十分方便的
所以如果系统当中每个页面的大小是二的整数幂，那么计算机就可以很方便的根据这个逻辑地址的二进制数就快速的得到它对应的页号和页内偏移量了。
因此基于这样的特性，如果一个系统使用的是分页存储管理的话，那么这个系统当中的逻辑地址的结构其实是固定不变的。假如说一个系统当中的页面的大小是 2 的 12 次方个内存单元，那么用二进制表示的逻辑地址当中，末尾的 12 位就应该是页内偏移量，而其余的部分就应该是页号。所以一个地址结构会包括页号和页内偏移量这样两个部分。
比如在这个例子当中，地址的长度为 32 位，0~11 位，总共 12 个而二进制位来表示页内偏移量或者叫页内地址，然后用 12~31 这些总共 20 个二进制位表示页号。
这个地方再次强调页内偏移量的二进制位数和页面的大小的一个关系。如果说有 k 位来表示页内偏移量的话，那么说明这个系统当中一个页面的大小应该是二的 k 次方的内存单元，而如果有 M 位来表示页号的话，那么说明在这个系统当中一个进程最多允许有二的 m 个次方个页面。
所以经过刚才的这一系列分析，我们知道了系操作系统应该怎么快速的根据一个逻辑地址来算出它对应的页号和页内偏移量，因为一个系统当中的逻辑地址结构是确定的，所以可以根据这个逻辑地址结构很快速的分区分出页号和页内偏移量分别是多少。不过计算机是用二进制数来算的，但是在考研当中也经常会用 10 进制数来出题，用十进制数来表示一个逻辑地址，在这种情况下，大家也需要会用之前所介绍的这种方式来计算页号和页内偏移量。
# 页表
那么在回答了怎么从逻辑地址找到对应的页号和页内偏移量这两个问题之后，我们再来看一下应该怎么找到每个页面在内存当中的起始地址。
那为了能够知道进程的每个页面在内存当中存放的位置，操作系统会为每个进程创建一个页表，也就是说一个进程会对应一张页表，并且每个进程当中的每一页会对应其中的某一个页表项，而一个页表项由页号和块号组成，所以其实页表的作用就是用于记录进程的页面，和这些页面在内存当中实际存放的内存块之间的这种对应关系。
比如说假设此时我们要访问某个逻辑地址，根据之前介绍的方法，我们可以用逻辑地址算出它应该所属于哪一页，之后就可以根据这个页面的页号去查询页表，并且就可以知道这个页面应该是存放在内存当中的哪一个页框当中，或者说存放在哪一个内存块当中我们只需要用内存块的块号，再乘以每个内存块的大小，就可以得到内存块的起始地址到底是多少了。相应的这也就知道了我们想要查询的页面在内存当中的起始地址应该是多少。
那之后我们再用这个逻辑地址的页内偏移量加上这个页面的起始地址，就可以得到这个逻辑地址最终对应的物理地址是多少了。这个地址转换的详细过程，我们会在下个小节再结合一些硬件相关的考点再进行进一步的介绍
这个地方我们还需要注意一点，每个页表项的长度是相同的，但是页号是隐含的。接下来我们来解释一下这句话
假设我们一个系统当中物理内存大小是 4GB，页面的大小是 4KB，那么每个页表项至少应该是多少字节？
我们可以这么来计算。4GB 就是 2 的 32 次方个字节，4KB 就是 2 的 12 次方个字节，所以这么大的内存空间，我们把它分成一个一个的和页面大小相等的页框之后，总共会有二的 20 次方个页框，或者说二的 20 次方个内存块，因此这么多的内存块对应的内存块号就应该是 0~220-1 这么多的数字，总共需要 20 个二进制位才可以表示。
因此我们在页表项当中，要表示内存块号至少需要用 3 个字节才能够，因为每个字节是 8 个二进制位，3 个字节的话就是 24 个二进制位，这是足够表示这个范围的数字的，而如果只有两个字节的话，总共只有 16 个二进制为就不能表示这么大范围的内存块号了。
所以根据我们物理内存的大小的总和和我们的页面的大小，我们就可以得到我们的一个页表项，至少应该有多少个二进制位。这些页表项会根据页号递增的顺序连续的存放在内存当中。所以如果我们能够知道页表存放的起始地址为 x 的话，那么 m 号页对应的页表项一定就是存放在页表项的起始地址 x 再加上 3×m这个地方的。
因此页表当中的页号是不需要 显式 的表示出来的，我们只需要知道页表存放的起始地址，还有页表项的长度是多少，我们就可以用上面介绍的这种方法来找到各个液号对应的页表项存放的位置是多少了。
那么在这个例子当中每个页表项占三个字节，如果进程是有 n 个页面的话，那么进程的页表就应该总共会占 3 乘以 n 个字节。
# 小结
那么在这个小节当中，我们介绍了基本分页存储管理的一些基本概念，我们从这种管理方式的思想入手，介绍了一些重要概念，这些概念都十分容易混淆，特别是刚开始第一次学的时候，大家在做题的时候，在遇到页框，页，页面或者页帧这些很容易混淆的名词的时候，一定要想一下它指的到底是什么，然后这些概念最好是对比来记忆
之后基于分页存储的思想，我们一步一步分析了，我们应该怎么实现分页存储管理当中的地址转换。
- 第一步我们需要计算出逻辑地址对应的页号。
- 第二步我们需要找到页号对应的页面在内存当中存放的起始位置。
- 第三步我们还需要根据逻辑地址算出对应的页内偏移量。
- 第四步我们就可以根据这个页面的起始地址，再加上页内偏移量就可以得到最终的物理地址了。
那么根据第一个和第三个问题怎么算出页号和业内偏移量，我们探讨了这样的两种方式。第一种方式我们可以用逻辑地址除以页面大小得到页号，然后用逻辑地址对页面大小取余操作得到页内偏移量。另外我们还可以根据一个系统的逻辑地址结构来计算页号和业内偏移量。一个逻辑地址在结构上可以分为页号和页内偏移量这样两个部分，页号占 p 位，页内偏移量占 w 位。另外大家还需要知道页内偏移量的位数和页面大小之间的关系，
那么最后我们介绍了要怎么找到的一个页面在内存当中存放的位置的一种方式，就是页表机制，关于一个进程对应一张页表，每一页对应一个页表项，每个页表项由页号和块号组成，这些是比较容易理解的，不太容易理解，并且书上没有详细介绍的是每个页表项的长度是相同的，而页号又是隐含的，我们需要知道怎么根据内物理内存的总容量和页面大小来计算出每个页表项的长度应该是多少，并且要能够理解为什么页号可以是隐含的不必要显示的给出来。在下个小节当中，我们会结合硬件相关的一些考点，再来详细的介绍怎么实现分页存储当中逻辑地址到物理地址的转换这个问题，相应的这些知识点还需要大家再结合课后习题进行进一步的巩固和输出。
