操作系统入门（六） 内存篇之30张图爆肝内存连续分配管理、页式存储、段式存储和段页式存储

操作系统内存知识体系大纲

上一节介绍了内存的逻辑空间和物理空间以及程序如何装入内存，本节将介绍操作系统如何分配和回收内存。整个内存空间会分为系统区（在低地址）和用户区（高地址），分别存放系统进程和用户进程的数据与指令，从而将系统进程和用户进程的隔离开来，做到内存保护。因此用户进程所用的内存会分配到内存空间的用户区，而系统进程所用的内存则会分配到系统区。

内存分配策略，主要分为 连续分配管理和离散分配管理 。

01 内存的连续分配管理

连续分配是指，整个进程在物理内存中是连续存储的，分配给进程的内存空间是连续的内存空间。连续分配策略分为单一连续分配、固定分区分配和动态分区分配3种。

固定分区分配是指在进程装入内存之前，就将整个用户区分为多个分区，进程装入内存时选择一个大小大于等于该进程所需内存的分区给该进程。

动态分区分配：进程装入内存时才对内存分区，分区的大小就是进程所需的所有内存大小。

固定分区分配和动态分区分配都是一个进程只能占用一个分区，不能占用多个分区。

- 单一连续分配

单一连续分配是指将内存中整个用户区空间分配给1个用户程序，无需对用户区再分区，内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点：

实现简单；

无外部碎片；

如果用户区内存不足以装下整个进程，可以采用覆盖技术扩充内存；

不一定需要采取内存保护。

缺点：

内存只装入一个进程的信息，内部碎片可能极大，内存利用率极低。

无法实现进程并发，并发率低。

- 固定分区分配

固定分区分配是指整个用户空间划分为若干个大小固定的分区，每个分区中只装入一道作业，进程装入内存时选择一个大小大于等于该进程所需内存的分区给该进程。

按照分区大小是否相等，又有两种分法：

固定分区分配如何实现内存分配和回收？

操作系统需要建立一个分区分配表的数据结构，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的
大小、起始地址、状态（是否已分配）。可以使用数组或者链表在逻辑上实现这个分区分配表。

优点：实现简单，无外部碎片。

缺点：

a. 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；

b. 会产生大量内部碎片，内存利用率低。

c.难以合理预先划分分区,
分区个数划分少了意味着物理内存中能装入的进程个数少了，降低并发度。分区个数划分多了，每个分区大小就小了，就会造成大进程无法装下任何一个分区。

- 动态分区分配

这种分配方式不会预先划分内存分区，而是在进程装入内存时， 根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此动态分区的大小是不固定的。

动态分区分配可以使用空闲分区表或者空闲分区链管理，表项 中包含分区号、 分区大小、分区 起始地址等信息。

如果回收分区的时候，待回收的分区和其他空闲分区相连，需要合并这些分区的表项为一个表项。

动态分区分配的过程如下图所示，在一开始给多个进程分配分区时，这些进程在内存中是紧挨着的，随着多次回收和分配，进程在内存中会变成离散分布，并可能出现大量外部碎片。动态分区不会产生内部碎片，因为每个分区大小都等于该进程所需内存大小。

此时可以用紧凑技术解决，将离散的进程变成在内存中紧密相连。

紧凑技术是指将所有进程占用的分区移动到一端使其紧凑的挨在一起，空闲区留在另一端
。如下图所示，原本所有碎片分区都容纳不下进程5，但移动后所有碎片分区相邻融合为一个连续的空闲区就能放下进程5：

紧凑技术要将进程在内存中的物理位置“搬家”，因此需要在分区表对所有进程与地址有关的项修改，例如基址寄存器、程序计数器等，还会造成内存数据大量拷贝。因此紧凑会花费大量CPU时间。

紧缩的时机：当所有空闲分区的大小不满足要装入内存的进程大小时发生。

动态分区的优点：

分区大小可变，进程在内存的起始位置可变，空闲分区可合并，更灵活，内存利用率更高；

无内部碎片；

缺点：

有外部碎片，外部碎片过多就可能触发“紧凑”，导致系统开销变大；

一个进程需要占用连续的内存空间，相比于离散分配而言，内存利用率低，这点是静态分区和单一连续分配都有的问题，而离散分区管理可以解决该问题；

- 动态分区分配算法

动态分区分配算法研究的是，内存中有空闲分区时，动态分区分配法优先选择哪个分区给进程。动态分区算法分为首次适应算法、最佳适应算法、最坏适应算法和邻近适应算法。

首次适应算法

从低地址开始查找分区，找到第一个能满足待装入进程大小的空闲分区。

如何实现：空闲分区在空闲分区链中以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区 表），找到大小能满足要求的第一个空闲分区。

缺点：低地址空闲区会产生很多外部碎片，查找空闲区链表时会重复遍历低地址的外部碎片分区，增加了查找的开销。

最佳适应算法

从所有空闲分区中选择满足待装入进程大小的最小空闲分区，目的是预留大分区给大进程。

如何实现：空闲分区在空闲分区链中按容量递增次序排序。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

缺点：每次都选最小的分区进行分配，会留下越来越多的、小到难以利用的外部碎片。

最坏适应法

从所有空闲分区中选择满足待装入进程大小的最大空闲分区。目的是尽可能避免生成外部碎片。

如何实现：空闲分区在空闲分区链中按容量降序排序实现。

缺点：每次都选最大的分区进行分配，可以让分配后留下的空闲区更大，避免外部碎片。但是会导致较大的连续空闲区被迅速用完，“大进程”到达就没有内存分区可用了。

邻近适应算法

该算法按照首次适应算法的逻辑查找，但下次查找按上次查找结束的位置开始检索，目的是解决首次适应算法查找时间递增的缺点。

如何实现：空闲分区在空闲分区链中以地址递增的顺序排列，排成一个循环链表。使用一个头指针指向上次分配内存时查找结束的位置，下次从该位置开始查找空闲分区链，找到大小能满足要求的第一个空闲分区。

缺点：进程装入时，头指针之前的空闲分区（低地址的分区）即使有足够空间分配给该进程，系统还是会选择头指针之后的空闲分区来分配。因此该算法会导致高地址和低地址分区可无大分区可用。

四种算法中，首次适应算法的效果反而最好。
首次适应算法和邻近适应算法的优点是分配分区后，无需移动链表节点，而最佳适应和最坏适应算法则需要移动链表节点。邻近适应算法的查找效率最高。

连续分配的方式分配内存的最大缺点在于会产生很多内存碎片，内存利用率低，而产生很多内存碎片的根本原因在于必须为进程分配连续的内存空间，虽然可以通过紧凑技术解决，但是需要花费很多CPU时间。

为什么连续存储会造成很多内存碎片？

因为对于较大的进程，系统要挑选大块的空闲空间给进程，而很小块的空闲空间可能连较小的进程都无法容纳而永远无法被利用，就变成了内存碎片。进程换入和换出的次数多了之后就会产生很多碎片。

离散分配则允许为进程分配分散的内存块，即一个进程可以分布在不相邻的多个小分区中。 离散分配管理分为分页存储、分段存储和段页式存储3种。

02 内存离散分配 - 页式存储

页式存储又称分页存储，是指在物理上将内存空间分为多个大小相等的物理块（又叫内存块），在逻辑上将进程的逻辑地址空间分为多个页面（又叫逻辑页），每个页面和物理块一样大。

操作系统分配与进程占用页面数量相同的物理块给该进程，该进程的页面可以离散的存放在内存的块中，与内存块一一对应，每个进程会维护一个逻辑页和物理块映射关系的页表。

页面是逻辑空间单位，块是物理空间单位。页面的编号叫页号，内存块的编号叫块号，编号和页号都是从0开始。页面大小由硬件决定，一般为2的若干次幂，有些是512B，有些是4K等，不同机器的页面大小不同。

- 逻辑地址的构成

一个逻辑地址可能是32位或者64位。一般来说，32位的逻辑地址的前 20 位 就是页号，后12位就是页内偏移，也就是说逻辑地址是由 页号 和 页内偏移
组成的。这里有个通用的结论：页面大小 是 2 ^ k 情况下，页号 是 逻辑地址的前 32 - k 位，页内偏移 是 逻辑地址的末尾 k 位。

页号P表示这个逻辑地址位于逻辑空间的第几个页，页内偏移W表示这个逻辑地址位于页面的第几个字节。

- 分页存储如何实现地址转换

分页存储采用动态重定位，即装入时不进行地址转换，运行指令时才进行地址转换。指令中的地址是逻辑地址。逻辑地址转为物理地址的过程如下：

例如，程序中某个数据的逻辑地址L为80，页面大小p为50，页号块号映射关系为 块号数 =
页号数+10，求物理地址（这里为了方便计算所以用公式表示映射关系，实际上页号与块号的映射关系需要查询页表得出）。

页号P = floor(80 / 50) = 1

页内偏移i = 80 % 50 = 30

块号B = 1 + 10 = 11

物理地址S = 11 * 50 + 30 = 580

- 页表

页表是操作系统为每个进程创建的进程页号与内存块号的映射关系表。

进程的页表保存在内存中，而 页表在内存的指针存在PCB内 。

需要注意：

1. 一个进程都有属于自己的页表，进程的每个页面对应一个页表项，每个页表项的大小是相同的。

2. 每个页表项由“页号”和“块号”组成，但页号是“隐含”的，不占存储空间，页表实际只保存了块号。

4. 如果不采用多级页表，则一个页表是连续存放在内存中的。

一个页表项的大小取决于内存最多有多少个物理块。

假设某系统物理内存大小为 4GB，页面大小为 4KB，则 4GB 的内存总共会被切分为 40G / 4K = 2^32 / 2^12 =
2^20个内存块，因此内存块号的范围应该是 0 ~ 2^20 -1，内存块号至少要用 20 bit
来表示，即页表项至少需要3B的大小才能保存下最大的块号（3*8=24bit）

- 基本地址变换机构

基本地址变换机构是帮助系统将逻辑地址转换为物理地址的硬件设施。这些硬件中最重要的是页表寄存器（PTR）。页表寄存器存放页表在内存中的起始地址F
和页表长度（页表项个数）M。

进程未执行时，页表的始址 和 页表长度 放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们load到页表寄存器中。下图是CPU将 程序计数器
中指令的逻辑地址 转为 物理地址 的过程。

从上面的过程中我们注意两点：

1、页式管理的地址是一维的，因为只需向系统提供一个 逻辑地址 系统就能算出物理地址。

2、CPU根据逻辑地址访问某个指令或数据时会发生2次内存IO，一次是根据页号+页表地址查页表，一次是实际访问目标指令或数据。

为了让CPU根据逻辑地址寻址可以更快，计算机会使用一种叫快表的硬件把访问过的页表项缓存到CPU中，如果下次根据页号命中快表中的页表项，则可以避免查页表的过程，减少1次内存IO。

在介绍快表之前需要先介绍局部性原理，局部性原理分为时间局部性和空间局部性。

- 局部性原理

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很可能会再次被执行；如果某个数据被访问过，不久之后该数据很可能会再次被访问。（典型的例子就是循环）

空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。

时间局部性强调对同一个指令或数据的重复访问。空间局部性强调对邻近指令或数据的访问。

例如下面这段代码：

int i = 0;int a[100];while(i < 100){    a[i] = i;    i++;}

while代码块内的重复执行就是时间局部性的体现，会重复访问相同的指令和 i
这个数据；数组a的访问就是空间局部性的体现，a[0~99]是连续存储的，对a[0]~a[99]的访问很可能是访问同一个页面。

- 快表

快表（TLB）本质上是一种被称为联想寄存器的硬件，用来缓存CPU最近访问过的若干个页表项，可以加快地址转换的速度。访问快表的速度远高于访问内存的速度。

根据时间和空间局部性，CPU根据逻辑地址查找物理块时，可能多次查询不同逻辑地址都会查到同一个页表项和同一个物理块，因此快表正是利用了局部性原理优化了地址转换的过程。而局部行原理也可以使快表的命中率高达90%。下图为添加了快表之后的地址变换机构。

①
CPU给出逻辑地址，由硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较（遍历所有页号是O(n)复杂度，但该过程快到耗时可以忽略不计，因为这是高速缓存）。

② 如果页号命中快表则从快表读出对应的块号，块号+页内偏移量拼接得到物理地址，访问该物理地址对应的内存单元。若快表命中则访问某个物理地址仅需一次访存即可。

③ 如果没有命中快表，则需要访问内存中的页表，将查到的页表项存入快表，
以便后面可能发生的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换。若快表未命中，则访问某个逻辑地址需要两次访存。

- 多级页表

采用单级页表会有两个问题。

1、页表必须连续存放在内存，当页表很大时，页表需要占用多个连续的内存块。而从上面的内容我们知道连续存储会造成内存碎片。对于该问题，系统采用多级页表来解决。

2、根据局部性原理，进程一段时间内可能只访问特定的几个页面，因此没有必要让整个页表常驻内存。对于该问题，系统采用虚拟内存技术解决。

举个例子，某32位计算机系统按字节编址，采用分页存储管理，页面大小P=4KB，页表项长度L= 4B。那么内存存储一个页表需要耗费 1024
个页面。已知页面大小是12位。（下面给出计算过程，不感兴趣的朋友可以跳过）

计算过程：

最大页号N = 2 ^ (32-12) = 2^20

页表总大小S = 4 * N = 2 ^ 22

内存存储一个页表所需页面个数 = S / P = 2^22 / 2^12 = 2^10 = 1024 个页面

这就意味着每个进程的页表就可能占用连续1024个物理块。为了解决页表的存储需要连续占用多个物理块这个问题，操作系统使用 两级页表 。

操作系统将原本的单级页表划分为多个页，每页包含若干个表项，一个单级页表被分散存储在内存中。再用一个作为目录的页表记录这些离散的单级页表的页与其对应的块号，目录页表就是一个一级页表，或称为
页目录表 ，原本的单级页表变成多个二级页表。一级页表的一个表项代表一个二级页表的位置。如下如所示：

地址转换过程：

1、使用二级页表时，系统会将一个逻辑地址按照位数解释为3个部分：一级页号、二级页号和数据所在的页内偏移。

2、从PCB 中读出页目录表的起始地址，再根据一级页号和页目录表的起始地址在内存查询页目录表，找到下一级页表在内存中的存放位置。

3、根据二级页号和二级页表的始址在内存中查二级页表，找到最终想访问的内存块号。

4、根据目标内存块号 + 页内偏移得到物理地址。

注意两个细节：

1、对于一个更长的逻辑地址，意味着系统的页面数量上限更多，系统可能使用三级或四级页表才能实现页表离散存储。 **
非顶级页表的个数可以有多个，但每个页表的大小不能超过一个页面；顶级页表的个数只能有一个，只占用1个页面 **
。根据这个原则可以判断出一个系统需要采用几级页表。

2、无论是多少级页表，进程的PCB只记录顶级页表的起始指针。因此n级页表下，CPU根据逻辑地 址 访问目标值需要进行 n+1 次内 存访问。

- 页式存储下的内部碎片

考虑一种情况，系统的页面大小是4K，一个进程大小为49K，会占用13个页面，但是最后一个页面只用了1K，剩余3K没有被该进程使用，也不会被其他进程使用，于是会造成3K的内存碎片。

因此页式存储不会产生外部碎片，但会产生内部碎片，而且每个进程产生的碎片大小范围为 0~页面大小p，可以认为每个进程平均产生 p/2 字节的内部碎片大小。

- 页面尺寸

页面尺寸（也就是页面大小）是影响分页管理中内存使用效率的重要因素。

如果页面尺寸太大，就会出现越大的内存碎片；

如果页面太小，同一个进程所需的页面数会越多，该进程的页表占用的空间越多，而且会造成多级页表，每多一级页表，CPU根据逻辑地址找到目标值就需要多一次内存IO。

03 内存离散分配 - 段式存储

通常用户程序由若干个逻辑模块组成，例如一个C程序中有一个主函数main，它调用子函数f1~f3，又调用标准函数库的printf和scanf，每一个函数都是一个独立的逻辑结构，都应该有自己独立的内存空间，每个内存空间的地址从0开始。

段式存储（又叫做分段存储）是指将进程按独立的逻辑结构划分为若干个段，每个段都被分配连续的内存空间，段与段之间离散存储。

用户程序进行编译时，编译程序会为该程序的各个逻辑结构构建段，例如在编译程序中会为下面内容建立单独的段：

1.全局变量

2.函数调用栈，用来放参数和返回地址

3.每个函数的代码部分

4.每个函数的局部变量

一个进程的程序段和数据段不止一个，而是程序中有多少个独立的逻辑模块就会产生多少个段。

例如进程A包含 main()、f()和g()这3个函数，其中 main()调用了f()和g()，此时进程A会产生3个程序段存放 main()/f()/g()
对应的机器指令，产生3个数据段存放 main()/f()/g() 生成的临时数据。而且这些段相互独立，相互离散。

如果main()先调用 f() 后调用 g() ，那么f() 和 g()的数据段不会同时出现在内存中，而是f()的数据段先被回收再创建g()的数据段，但
main()的数据段和f()的数据段肯定是同时在内存中的。

分段存储中，每个段都有一个段名和段号。和分页存储不同的是，每个页的长度是相同的，由操作系统决定；而每个段的长度是不同的，是由模块内的代码量和产生的数据量决定。

分段系统的逻辑地址结构由段号（也就是段名）和段内地址（段内偏移量）所组成。段号的位数决定了每个进程最多可以分几个段，段内地址位数决定了每个段的最大长度是多少。分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

- 段表

和页表类似，为了方便系统找到进程的某个段在物理内存中的起始地址，系统为分段存储管理下的每个进程建立了一个段表。如下所示：

1、每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称 “基址”）和段的长度（要记录长度是因为每个段的长度不同，而页的长度都相同）。

2、各个段表项的长度是相同的。段表项长度取决于段长的位数和段基址的位数（即操作系统位数）。由于段表项长度相同，因此段号是隐含的，不占存储空间。

- 分段存储的地址变换

①根据逻辑地址得到 段号、段内地址。

②判断段号是否越界。若S≥M，说明CPU正访问一个不存在于该进程的段，产生越界 中断，否则继续执行。

③根据段表基址和段号查询段表，找到 对应的段表项，段 表项的存放地址为 F+S*段表项长度。得到段基址b

④检查段内地址是否超过 段长。若W≥C，说明CPU正访问一个该段不存在的地址，产生越 界中断，否则继续执行。

⑤根据段基址b和段内偏移W计算得到物理地址。

⑥访问目标 内存单元。

分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。

- 分段和分页管理对比

1、从页和段的含义

分页的主要目的是为了实现进程在内存的离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。

分段的主要目的是更好地满足用户需求。一个段通常包含着一个逻辑模块的信息，分段对用户是可见的。

2、从页和段的长度

页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。

3、分段比分页更容易实现程序的共享和保护。

因为我们共享程序具体是共享一个独立的逻辑模块，而分段存储管理是对独立的逻辑模块分配连续内存空间，系统只需将共享的这段代码在内存中的地址添加到要引用这段代码的进程中的段表中即可。

而如果在分页存储管理中共享，一个逻辑模块的内容可能分在在不同的页面中。假如该逻辑模块横跨11个页，就需要将这些页面的页号块号映射都添加到共享进程们的页表中。而且一个页可能既有共享模块的内容也有非共享模块的内容，如果让共享进程们的页表指向这个页，就可能访问到不可共享的代码和数据。

简单来说：在分页系统中实现页的共享较为困难，因为分页是对连续的进程逻辑空间等分，被共享的程序不一定刚好分在一个或多个完整的页面。此时就会出现一个页面既有共享程序又有不能共享的该进程自己的私有数据，因此页式存储不利于共享。

PS：关于共享程序

不能被修改的代码称为纯代码或可重入代码，这样的代码是可以安全的被并行执行的，只有这样的代码可以被多进程或多线程共享，而可修改的代码是不能共享的。

以函数为例，如果一个函数是可重入的，则该函数不能含有全局变量，只能包含调用者提供的参数，和函数自己产生的局部变量，可重入函数也不能调用其他不可重入的函数；

如下所示：

int g_var = 1;
int f(){  g_var = g_var + 2;  return g_var;}
int g(){  return f() + 2;}

f() 和 g() 都是不可重入函数，因为他们包含了一个全局变量
g_var，如果多进程共享f()和g()会导致g_var变量因为多进程并发的异步性而被改乱。

int f(int i){  return i + 2;}
int g(int i){  return f(i) + 2;}

这两个函数才是可重入函数。多进程只能共享f() 和 g() 的代码段，但是不会共享f()和g()的数据段。f() 和
g()运行过程中产生的数据分别保存在各自进程自己在运行f()/g()时创建的数据段中。例如 进程A和进程B共享 f()
，进程A运行f()时系统会为其创建一个数据段A1用来保存f()产生的临时变量i，而且数据段A1和进程A运行自身其他逻辑模块产生的数据段是相互独立的，离散的。

- 段页式管理

段页式管理将进程按逻辑模块分段，再将各段分页 ，再将物理空间分为大小相同的内存块 ，把进程各页面分别装入各内存块中。

段页式存储同时继承了分页管理和分段管理的优点，分段方便用户进程按以逻辑模块为单位规划和运行，段内分页使一个段可以离散存储，提高了内存利用率，避免外部碎片。

段页式系统的逻辑地址结构由段号、页号、页内地址（页内偏移量）组成。

“分段”对用户是可见的，程序员知道程序中有多少个段，因为它亲手实现了这些逻辑模块。而将各段“分页”对用户是不可见的，系统会根据段内地址自动划分页号
和页内偏移量。段页式管理中，一个进程对应一个段表和多个页表，一个段对应一个页表。

每个段对应一个段表项，每个段表项由段号、段对应的页表长度、页表存放的块号（页表起始地址）组成。每个页面对应一个页表项，每个页表项由页号、块号组成。

段页式存储地址变换的过程

无论是段式存储、页式存储还是段页式存储，其地址变换都发生在进程运行时，即CPU执行指令时发生的。