2. 内存空间的分配与回收

1. 单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区常常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据

内存中只能有一道用户程序，用户程序独占整个用户区空间

优点：实现简单；无外部碎片；可以采用覆盖技能扩充内存；不一定需要采取内存保护（因为只有一道用户程序）

缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低

2. 固定分区分配

为了可以装入多道程序，且这些程序之间又不会互相干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式

分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合

分区大小不等：增加了灵活性，可以满足大小不同的进程需求，根据常在系统中运行的作业情况进行划分（划分多个小分区、适量中等分区、少量大分区）

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

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

缺点：

• 当用户程序太大，可能没有一个分区满足要求，不得不采用覆盖技术，会降低性能

• 会产生内部碎片，内存利用率低

3. 动态分区分配

动态分区分配（可变分区分配）：不会预先分配分区，而是进程装入内存时，根据进程的大小动态地建立分区

3.1 记录内存的数据结构

空闲分区表 and 空闲分区链

3.2 空闲分区的选择

把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区中选择一个分区分配给该作业。

可参考后面介绍的四种算法

3.3 分区的分配 & 回收

分配

• 情况一：当从空闲分区表中选择一个分区分配后，内存还有剩余，则修改表项

• 情况二：当从空闲分区表中选择一个分区分配后，刚刚好分配完，则删除该表项

回收

• 情况一：回收区后面有一个相邻的空闲分区，则合并

• 情况二：回收区前面有一个相邻的空闲分区，则合并

• 情况三：回收区前后各有一个相邻的空闲分区，则三个合并为一个

• 情况四：回收区前后无相邻的空闲分区，则新增一个表项

内部碎片：分配给某些进程的内存区域中，有些部分没有用上

外部碎片：内存中某些空闲的分区由于太小而难以利用

如果内存中零碎的空间太多，导致无法满足内存较大的进程，可采用拼凑技术来解决外部碎片

思考：动态分区分配应该使用动态重定位装入（绝对装入地址改变，需要重新编译；静态装入，不支持移动）

3.4 首次适应算法（First Fit）

算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区

实现方法：空闲分区以地址递增的次序开始排序。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到第一个满足大小的空闲分区

3.5 最佳适应算法（Best Fit）

算法思想：考虑大内存的进程有地可留，优先使用更小内存的空闲区

实现方法：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到第一个满足大小的空闲分区

缺点：每次都选小内存的分区进行分配，会留下越来越多很小的、难以利用的内存块。因此这种方法会产生很多外部碎片

3.6 最坏适应算法（Worst Fit）

又称最大适应算法（Largest Fit）

算法思想：避免留下越来越多的小内存块，优先使用更大内存的空闲块

实现方法：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到第一个满足大小的空闲分区

缺点：导致更快是使用完大内存的空闲块，使之后的大内存的进程无分区可用

3.7 邻近适应算法（Next Fit）

算法思想：首次适应算法，每次都从低地址开始遍历，导致低地址产生越来越多很小的空闲块。新来一个进程就重新从头开始遍历，会增加查找的开销。邻近适应算法就是接着从上一次查找结束的位置开始检索

实现方法：空闲分区按地址递增次序排列（可排成一个循环列表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到第一个满足大小的空闲分区

优点：无论低地址还是高地址都有相同的概率被使用

3.8 对比

算法	算法思想	分区排列顺序	优点	缺点
首次适应	从头开始找到第一个满足大小的内存空闲分区	按地址递增	综合性能最好 算法开销小 回收分区后一般不需要对空闲分区重新排序
最佳适应	优先使用更小的分区 以保留更多更大的分区	按容量递增	会有更多更大的内存空闲块保留 能满足更大进程的需求	会产生很多很小 难以利用的碎片 算法开销大（需要重新排序）
最坏适应	优先使用更大的分区 以防止产生太多的外部碎片	按容量递减	可以减少难以利用的小碎片（外部碎片）	大分区容易被用完 不利于大进程 算法开销大（需要重新排序）
邻近适应	每次从上次结束的位置开始查找	按地址递增	不用每次从头开始检索，算法开销小	会是高地址的大分区也被用完

4. 基本分页存储管理

4.1 什么是分页管理

将内存分为一个个相等的分区，每个分区就是一个页框（页框 = 页帧 = 内存块 = 物理块 = 物理页面）

每个页框都有一个编号，即页框号（页框号 = 页帧号 = 内存块号 = 物理块号 = 物理页号），页框号从 0 开始

将进程的逻辑地址空间分为与页框相等的一个个部分，每个部分称为一个页或页面。每个页面也有一个编号，即页号，页号也从 0 开始

操作系统以页框为单位为各个进程分配内存空间，进程的每个页面分别放入一个页框中（进程的页面与内存的页框有一一对应的关系）

4.2 页表

页表存放在物理内存中，页表起始地址和页表长度存在 PCB 中，记录了进程的每个页面在内存中的位置信息

问题一：页表项占多少个字节

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

内存块大小 = 页面大小 = 4 KB = $2 ^{12} B$

• 内存块数量 = $2 ^{32} / 2 ^{12} = 2 ^{20}$
• 内存块的范围是 $0 \backsim 2 ^ {20} - 1$ ，至少需要 20 bit 来表示
• 至少用 3B 来表示块号（3 * 8 = 24 bit）

• 由于页号是隐含的，因此每个页表项占 3B，存储整个页表至少需要 3 * (n + 1) B

  • 因为可以通过目标逻辑地址和页面大小推算出页号，故可以隐含

• 注意：通常我们设置的页表项最好可以使每个页面恰好装下整个页表项

问题二：如何实现地址转换

逻辑地址 A 对应的物理地址 = P 号页面在内存中的起始地址 + 页内偏移量 W

• 可以利用二进制的特点巧妙计算，即：物理地址 = （页框号，页内偏移量）-> 二进制

4.3 基本地址变换机构

基本地址变换机构可以借助进程的页表实现将逻辑地址转换为物理地址

通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址 F 和页表长度 M

进程未执行时，页表的始址 和 页表长度 放在进程控制块（PCB）中，当进程被调度是，操作系统内核会把它们放到页表寄存器中

假设页面大小为 L

1. 计算页号和页内偏移量：页号 $p = A / L$ ，页内偏移量 $W = A \% L$ （计算机可以根据逻辑地址的结构快速计算出）
2. 判断页号是否越界：查询页表寄存器中的页表长度 M，若 $p \ge W$ ，则越界；反之继续下一步
3. 查询页表，找到页号对应的页表项，确定页面存放的内存块号

4. $E = b * L + W$

4.4 快表

快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓存，用来存放最近访问的页表项的副本，可以加快地址变换的速度

引入快表后，改变的地方：

1. 会现在快表里查询，看看是否存在，如果不存在再去页表里查询

2. 在页表里查询到后，会把该表项存一份到快表中

快表依据的是局部性原理

• 空间局部性

  • 一旦访问了某个存储单元，在不久后，其附近的存储单元也有可能被访问（因为很多数据在内存中都是连续存放的）

• 时间局部性

  • 如果执行了程序中的某条指令，那么不久后很有可能再次执行到这条指令（因为程序中存在大量的循环）

4.5 两级页表

单级页表存在的问题

• 有时页表的长度可能会很大，同时页号隐含导致页表必须在内存中连续存放

• 根据局部性原理，很多时候，一段时间内只需要访问几个页面就可以正常运行，没必要让整个页表常驻内存

两级页表的原理 & 地址结构

1. 按照地址结构将逻辑地址拆分为三部分

2. 从 PCB 中读取页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存的存放位置

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

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

在表项中增加一个标志位，即可实现部分页表存放在内存中

5. 基本分段存储管理

5.1 什么是分段管理

分页存储管理，每个页面的大小都是固定相同的，这样可能导致某些程序的逻辑被拆分，不利于信息的共享和保护

分段：按照程序的自身逻辑关系划分为若干个段，每个段都有一个段名，每段从 0 开始编址

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

分段系统的逻辑地址结构：

5.2 段表

1. 每个段都对应一个段表项，其中记录了该段在内存中的起始位置（基址）和段的长度

2. 各个段表项的长度都是相同的，段号可以隐含，不占存储空间

5.3 地址变化

6. 段页式存储管理

6.1 段氏 & 页式 优缺点

6.2 段页式管理

先分段，再为每一段分页

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

每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的

6.3 地址变化