【操作系统-存储】存储的分配和管理方式

1 连续分配方式

• 内部碎片：分配给某进程的内存区域中，但有些部分没有用上
• 外部碎片：指内存中的某些空闲分区由于太小而难以利用，可以通过紧凑（拼凑，Compaction）技术来解决外部碎片

1.1 单一连续分配

如早期的 PC 操作系统 MS-DOS，内存中只能有一道用户程序，用户程序独占整个用户区空间。优缺点：

• 优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护
• 缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低

1.2 固定分区分配

将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。两种分配方案：

• 分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
• 分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分（比如：划分多个小分区、适量中等分区、少量大分区）

操作系统需要建立一个分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。

优缺点：

• 优点：实现简单，无外部碎片
• 缺点：a. 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；b. 会产生内部碎片，内存利用率低

1.3 动态分区分配

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。动态分区分配没有内部碎片，但是有外部碎片。

操作系统可使用两种方案记录空闲分区的情况：

• 空闲分区表：每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息
• 空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息

1.3.0 空闲分区的回收

空闲分区的回收分为四种情况：

• 回收区的后面有一个相邻的空闲分区：回收后，两个相邻的空闲分区合并为一个，空闲分区表需修改对应的表项
• 回收区的前面有一个相邻的空闲分区：回收后，两个相邻的空闲分区合并为一个，空闲分区表需修改对应的表项
• 回收区的前、后各有一个相邻的空闲分区：回收后，三个相邻的空闲分区合并为一个，空闲分区表需修改对应的表项
• 回收区的前、后都没有相邻的空闲分区：回收后，空闲分区多一个，空闲分区表需新增一个表项

把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业，不过这些算法的性能都非常差。

1.3.1 首次适应算法

首次：找到第一个能放得下的空闲分区

• 查找空闲分区的思路：每次都从低地址开始查找，找到第一个能满足大小的空闲分区
• 实现方法：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区
• 优点：算法开销小，综合四种算法来看，邻近适应算法性能最好

1.3.2 邻近适应算法

邻近：继续查找

• 查找空闲分区的思路：每次都从上次查找结束的位置开始检索
• 实现方法：空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区
• 优点：算法开销小，不用每次都从低地址的小分区开始检索
• 缺点：会使高地址的大分区也被用完

1.3.3 最佳适应算法

最佳：找到刚好放得下的空闲分区

• 查找空闲分区的思路：优先使用更小的空闲区
• 实现方法：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区
• 优点：会有更多的大分区被保留下来，更能满足大进程需求
• 缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片；需要排序，算法开销大

1.3.4 最坏（最大）适应算法

最坏：找到最大的空闲分区

• 查找空闲分区的思路：在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用
• 实现方法：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区
• 优点：可以减少难以利用的小碎片
• 缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了；需要排序，算法开销大

2 分页存储管理

2.1 一级基本分页存储管理

假设逻辑地址空间为 32 位（4GB），一页为 4KB，物理地址空间为 28 位（256MB），则：

2.1.1 物理地址空间

将内存空间分为一个个大小相等的分区（每个分区 4KB），每个分区就是一个“页框”。每个页框有一个编号，即“页框号”。页框号从 0 开始。

物理地址空间中页框和页框号的概念：

• 页框 = 页帧 = 内存块 = 物理块 = 物理页面
• 页框号 = 页帧号 = 内存块号 = 物理块号 = 物理页号

物理地址空间的分区如下（2²⁸/2¹² = 2¹⁶ 个页框）：

2.1.2 逻辑地址空间

将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个“页”或“页面” 。每个页面也有一个编号，即“页号”，页号也是从 0 开始。进程的页面与内存的页框有一一对应的关系。

如何理解“一一对应”这个字眼？一个页面可以对应（更准确来讲是“映射”）一个页框，但不可以对应多个页框；但一个页框可以对应多个页面（这里可引申出虚拟映射文件技术）。比如，页号 0 的页面可以对应页框号 6 的页框，页号 1 的页面可以对应页框号 5 的页框，页号 2 的页面可以对应页框号 4 的页框等等；框号 4 的页框可以同时对应页号 2 的页面和页号 8 的页面。

逻辑地址空间中页和页号的概念：

• 页 = 页面
• 页号 = 虚页号
• 虚拟内存的实际硬件是不存在的，实际上是由页表来描述页面和页框之间的映射关系

逻辑地址空间的分区如下（2³²/2¹² = 2²⁰ 个页）：

2.1.3 地址结构

逻辑地址结构：

• 页内地址（页内偏移量）：位数的多少指示每个页的大小；本身可指示页内偏移量
• 逻辑页号：位数的多少指示整个地址空间被划分为多少页

物理地址结构：

• 页内地址（页内偏移量）：位数的多少指示每个页的大小；本身可指示页内偏移量
• 物理页号：位数的多少指示整个地址空间被划分为多少页

2.1.4 页表和页表项

• 一个进程对应一张页表
• 进程的每个页面对应一个页表项
• 每个页表项由“页号”和“物理页号（页框号、块号）”组成，注意虚页号不属于页表结构，所以加括号
• 页表记录进程页面和实际存放的内存块之间的映射关系
• 每个页表项的长度是相同的

页表寄存器（PTR） 的结构：

一个页表项的结构（因为物理地址空间有 2¹⁶ 个页，所以页表项的物理页号占 16 位）：

页表的结构（因为逻辑地址空间有 2²⁰ 个页，所以页表有 2²⁰ 个页表项）（举个例子：页号 0 的页面映射页框号 6 的页框，页号 1 的页面映射页框号 5 的页框，页号 2 的页面映射页框号 3 的页框，页号 3 的页面映射页框号 3 的页框，则如下表所示）：

这个页表大小为 2²⁰*2B = 2²¹B = 2MB。因为一个页是 4KB，所以这样一个页表需要占据 2MB/4KB = 2¹¹KB/4KB = 2⁹ = 128 页。

2.1.5 TLB 结构

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

TLB 的结构跟页表差不多，只是 TLB 需要多存储“页号”即标记位。

2.1.6 地址变换过程

（1）根据逻辑地址计算出页号、页内偏移量：

• 逻辑地址为十进制：页号 = 逻辑地址 / 页面大小，页内偏移量 = 逻辑地址 % 页面大小
• 逻辑地址为二进制且页面大小是 2 的整数幂（假设逻辑地址空间的总页数为 2^x）：页号 = 逻辑地址高 x 位，页内偏移量 = 逻辑地址剩余位

（2）判断页号是否越界：

• 页表寄存器（PTR）：记录页表起始地址和页表长度
• 比较页号和页表长度：若页号 ≥ 页表长度，发生越界中断，立即终止；若页号 < 页表长度，则没有越界

（3）查询页表：通过 PTR 的页表访问内存，起始地址找到页号对应的页表项，确定页面存放的页框号（内存块号）

（4）用页框号（内存块号）和页内偏移量得到物理地址：

• 逻辑地址为十进制：物理地址 = 页框号 * 页面大小 + 页内偏移量
• 逻辑地址为二进制且页面大小是 2 的整数幂（假设逻辑地址空间的总页数为 2^x）：物理地址 = 页框号 拼接 页内偏移量（把逻辑地址的高 x 位地址换成页框号即可得到物理地址）

（5）访问目标内存单元

2.1.7 有 TLB 的地址变换过程

（1）根据逻辑地址计算出页号、页内偏移量：

• 逻辑地址为十进制：页号 = 逻辑地址 / 页面大小，页内偏移量 = 逻辑地址 % 页面大小
• 逻辑地址为二进制且页面大小是 2 的整数幂（假设逻辑地址空间的总页数为 2^x）：页号 = 逻辑地址高 x 位，页内偏移量 = 逻辑地址剩余位

（2）判断页号是否越界：

• 页表寄存器（PTR）：记录页表起始地址和页表长度
• 比较页号和页表长度：若页号 ≥ 页表长度，发生越界中断，立即终止；若页号 < 页表长度，则没有越界

（3）查询快表：若在 TLB 中找到页号对应的页表项，则可确定页面存放的页框号（内存块号），直接到第（5）步；若没有找到，则进行第（4）步

（4）查询页表：通过 PTR 的页表起始地址访问内存，找到页号对应的页表项，确定页面存放的页框号（内存块号）

（5）用页框号（内存块号）和页内偏移量得到物理地址：

• 逻辑地址为十进制：物理地址 = 页框号 * 页面大小 + 页内偏移量
• 逻辑地址为二进制且页面大小是 2 的整数幂（假设逻辑地址空间的总页数为 2^x）：物理地址 = 页框号 拼接 页内偏移量（把逻辑地址的高 x 位地址换成页框号即可得到物理地址）

（6）访问目标内存单元

2.2 二级基本分页存储管理

假设逻辑地址空间为 32 位（4GB），一页为 4KB，物理地址空间为 28 位（256MB），所以逻辑地址空间被分为 2³²/2¹² = 2²⁰ 个页，物理地址空间被分为 2²⁸/2¹² = 2¹⁶ 个页框。

现继续假设规定页表项长度为 16b = 2B（不同级页表的页表项长度都是固定的），所以一个页能存储 4KB/2B = 2K = 2¹¹ 个页表项。而又因为逻辑地址空间被分为 2²⁰ 个页，即总共需要 2²⁰ 个页表项，从而进一步计算 20/11 = 2（向上取整），分页系统需要分两级。

需要怎么分呢？通常规定：一个页目录表只能占据一个页面，所以一个页目录表可以映射 2¹¹ 个二级页表，那么每个二级页表就存储 2⁹ 个页表项。

2.2.1 地址结构

逻辑地址结构：

• 页内地址（页内偏移量）：位数的多少指示每个页的大小；本身可指示页内偏移量
• 顶级 + 二级逻辑页号：位数的多少指示整个地址空间被划分为多少页

物理地址结构：

• 页内地址（页内偏移量）：位数的多少指示每个页的大小；本身可指示页内偏移量
• 物理页号：位数的多少指示整个地址空间被划分为多少页

2.2.2 页目录表（顶级页表）和页目录表项

页目录表寄存器（PDBR） 的结构：

一个页目录表项的结构：

页目录表的结构：

2.2.3 页表（二级页表）和页表项

由以上页目录表可以看出，二级页表一共有 2¹¹ 个。

页表基地址的组成：

一个页表项的结构：

页表的结构：

这个页表大小为 2⁹*2B = 1KB。因为一共有 2¹¹ 个页表，所以这些二级页表总共占据 2¹¹*1KB = 2MB。

2.2.4 地址变换过程

（1）按照地址结构将逻辑地址拆分成三部分

（2）从 PDBR 中读出页目录表始址，再根据顶级页号查页目录表（访存 1 次），找到对应二级页表在内存中的存放位置

（3）根据二级页号查二级页表（访存 2 次），找到最终想访问的内存块号

（4）结合页内偏移量得到物理地址

（5）访问目标内存单元（访存 3 次）

2.3 请求分页虚拟存储管理

2.3.1 页表和页表项

一个页表项的结构：

页表的结构：

2.3.2 TLB 结构

TLB 的结构跟页表差不多，只是 TLB 需要多存储“页号”即标记位。

2.3.3 地址变换过程 + 缺页中断过程

（1）根据逻辑地址计算出页号、页内偏移量

（2）判断页号是否越界：若判断越界，则发生越界中断，立即终止

（3）查询快表：若在 TLB 中找到页号对应的页表项，则可确定页面存放的页框号（内存块号），直接到第（5）步；若没有找到，则进行第（4）步

（4）查询页表：通过 PTR 的页表起始地址访问内存，若找到页号对应的页表项，则确定页面存放的页框号（内存块号），直接到第（6）步；若没有找到，则进行第（5）步

（5）缺页中断处理：

（5-1）在外存中找到该缺页

（5-2）判断内存是否已满：若是，选择一页换出（还需判断该页是否被修改过，若是，先将其写入外存）；若不是，直接进行（5-3）步

（5-3）将该缺页从外存读入内存

（5-4）修改页表，修改 TLB

（6）修改访问位和修改位

（7）用页框号（内存块号）和页内偏移量得到物理地址

（8）访问目标内存单元

2.4 基本分页与请求分页的区别

请求分页存储管理与基本分页存储管理的主要区别：

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

【注】虚拟内存需要满足两个条件：

• 虚拟内存的实际容量 ≤ 内存容量 + 外存容量
• 虚拟内存的最大容量 ≤ 计算机的地址位数能容纳的最大容量

3 分段存储管理

段：进程的地址空间按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从 0 开始编址。每个段在内存中占据连续空间，但各段之间可以不相邻。

3.1 逻辑地址空间

以实际例子说明分段存储管理的结构，某个进程的地址空间划分段如下：

3.2 物理地址空间

物理内存存放各个段的位置如下：

3.3 段表和段表项

段表寄存器的结构：

一个段表项的结构：

段表的结构（可对照物理地址空间）：

3.4 地址结构

逻辑地址结构：

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

（若要访问程序段的地址 8B 处，假设逻辑地址是 13 位，给出例子如下）

物理地址结构：

• 段的首地址：该段在内存中的实际起始位置
• 段内偏移量：在段内的位置

（继续上面的例子，则通过查段表，可得到物理地址如下）

3.5 地址变换过程

（1）根据逻辑地址得到段号、段内偏移量：高位为段号，低位为段内偏移量

（2）判断段号是否越界：

• 段表寄存器：记录段表起始地址和段表长度
• 比较段号和段表长度：若段号 ≥ 段表长度，发生越界中断，立即终止；若段号 < 段表长度，则没有越界

（3）查询段表：通过段表寄存器访问所指向的段表，找到段号对应的段表项，确定段基址

（4）用段基址和段内偏移量得到物理地址：

• 逻辑地址为十进制：物理地址 = 段基址 + 段内偏移量
• 逻辑地址为二进制：物理地址 = 段基址 拼接 段内偏移量（把逻辑地址的高 x 位地址换成段基址即可得到物理地址）

（5）访问目标内存单元

3.6 分段与分页的区别

4 段页式存储管理

假设某进程最多可以分 256 个段，页面大小为 4KB，页表有 2¹⁰ 个页表项。

4.1 逻辑地址空间

将进程按逻辑模块分段，再将各段分页（各段均从 0 页开始），再将内存空间分为大小相同的内存块，将各页面分别装入各内存块中。假设逻辑地址空间如下：

4.2 物理地址空间

假设各个段及其页表映射到物理地址空间的位置如下：

4.3 段表和页表

每个进程只有一张段表，根据上面的映射情况，段表中存储如下：

每个段都有自己的页表，根据上面的映射情况，这三个段的页表中存储如下：

• 段号 0（程序段 10KB）的页表：

• 段号 1（数据段 6KB）的页表：

• 段号 2（堆栈段 2KB）的页表：

4.4 地址结构

（假设某进程最多可以分 256 个段，页面大小为 4KB，页表有 2¹⁰ 个页表项）

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

• 段号：段号的位数决定了每个进程最多可以分几个段
• 页号：页号位数决定了每个段最大有多少页
• 页内偏移量：页内偏移量决定了页面大小是多少

物理地址结构：

• 物理页号：实际在哪个物理页号/内存块号。
• 页内偏移量：在段内的位置

（假设访问程序段的 9KB 处，则对应 2 号页，2 号页框）

4.5 地址变换过程

（1）根据逻辑地址得到段号、页号、页内偏移量

【注】也可引入快表机构，用段号和页号作为查询快表的关键字。若快表命中则仅需一次访存

（2）判断段号是否越界：若段号 ≥ 段表长度，发生越界中断，立即终止；若段号 < 段表长度，则没有越界

（3）查询段表：通过段表寄存器，找到段表，找到对应的段表项，得到页表存放块号（即存放页表的起始页号）（第一次访存）

（4）检查页号是否越界：若页号 ≥ 页表长度，发生越界中断，立即终止；若页号 < 页表长度，则没有越界

（5）根据页表存放块号、页号查询页表，找到对应页表项：页表项地址 = 存放页表的起始页号*页面大小 + 页号*页表项长度（第二次访存）

（6）根据内存块号、页内偏移量得到最终的物理地址：内存块号 拼接 页内偏移量

（7）访问目标内存单元（第三次访存）