3.1 内存管理概念

3.1.0 内存相关概念

程序执行前需要先放到内存中才能被CPU处理。内存是为了缓和CPU与外存之间的速度矛盾。

内存地址从0开始，每一个地址对应一个存储单元（用于存放数据的最小单元）。

• 若计算机按字节编址，则每个存储单元大小为一字节（1B），即8个二进制位；

• 若计算机按字编址，且字长为16位，则存储单元大小为一个字长，即16个二进制位。

• $2^{10}$个字节：1K

• $2^{20}$个字节：1M

• $2^{30}$个字节：1G

3.1.1 内存管理的基本原理和要求

1、逻辑地址与物理地址

逻辑地址：相对于进程的起始地址而言的地址

物理地址：实际在内存中的地址

在程序中，一般使用的是逻辑地址。

2、程序的装入和链接

创建进程时，通常需要将程序和数据装入内存，这一过程通常包含以下几个步骤：

• 编译：将高级语言翻译为机器语言，形成一组目标模块

• 链接：形成逻辑地址，将编译后的的目标模块与所需的静态库一起，形成一个完整的装入模块

  • 静态链接：在程序执行前将各目标模块及其所需库函数组成一个完整的装入模块

  • 装入时动态链接：在各目标模块装入时，一边装入一边链接

  • 运行时动态链接：在程序执行到相应目标模块时，才进行链接

    • 便于修改和更新

    • 便于实现对目标模块的共享

• 装入：将装入模块装入内存运行（逻辑地址→物理地址）

  • 绝对装入：若已经知道程序将在内存的哪个位置运行，则编译时就将逻辑地址转换为物理地址

    • 灵活性很差，只适用于单道程序环境

  • 静态重定位（可重定位装入）：对所有的逻辑单元进行重定位，将其转化为物理地址

    • 必须要一次全部装入内存（一次分配所需的全部内存）

    • 逻辑地址必须是连续的

    • 程序运行期间不能再次移动

  • 动态重定位（动态运行时装入）：设置一个重定位寄存器，里面存放程序的起始地址。程序执行时，会将逻辑地址与重定位寄存器中的值相加得到物理地址

    • 允许程序在内存中移动

    • 可以分配到不连续的区域中

    • 可以动态的分配内存

3、内存管理的功能

• 内存空间的分配与回收：主存储器空间的分配与管理

• 地址转换：逻辑地址到物理地址

• 内存空间的扩展：虚拟化

• 存储保护：保护各个作业只能访问自己的内存空间

4、内存保护

• 设置上、下限寄存器，进行越界检测

• 通过重定位寄存器和界地址寄存器，进行越界检测。其中重定位寄存器存放起始物理地址，界地址寄存器存放最大逻辑地址。

5、内存共享

• 可重入代码：允许多个进程同时访问，但不允许修改

• 为每个进程配备局部数据区，将可能改变的部分复制进去，修改进程自己的私有数据

3.1.2 覆盖与交换

1、覆盖技术

将用户空间分为一个固定区和若干覆盖区。

常用的部分放入固定区，不常用的段在需要时放入覆盖区，当需要使用时将相应的段从外存调入覆盖区。

• 内存中能够更新的地方只有覆盖区的部分

• 对用户不透明

2、交换技术

当内存空间紧张时，将内存中的某些进程暂时换出到外存，并将外存中某些已经具备运行条件的进程换入内存。

PCB是常驻内存的

中级调度（内存调度）就是决定将哪个处于挂起状态的进程重新换入内存。

• 在具有交换功能的操作系统中，磁盘空间通常分为文件区和对换区

  • 文件区存储文件，追求磁盘空间的利用率，对磁盘空间的管理采用离散分配方式

  • 对换区占用空间很小，追求换入换出速度，对磁盘空间的管理采用连续分配方式

• 交换通常发生在有较多进程在运行且内存吃紧的时刻

• 当系统负荷降低时停止交换

• 一般会优先换出阻塞进程以及底优先级的进程，同时为了防止出现饥饿现象，有时还要考选进程在内存的驻留时间

3.1.3 连续分配管理方式

连续分配：系统为用户进程分配的必须是一个连续的内存空间

1、单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。

• 系统区通常位于内存的低地址部分，用于存放操作系统相关数据；

• 用户区用于存放用户进程相关数据。

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

• 优点：

  • 实现简单；

  • 无外部碎片；

  • 可以采用覆盖技术扩充内存；

  • 不一定需要采取内存保护（eg: 早期的PC操作系统MS-DOS）

• 缺点：

  • 只能用于单用户、单任务的操作系统中；

  • 有内部碎片；

  • 存储器利用率极低。

内部碎片：系统分配给进程的内存空间中，没有被利用到的区域

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

2、固定分区分配

将整个用户空间划分为若千个固定大小的分区，在每个分区中只装入一道作业。

• 分区大小相等：

  • 缺乏灵活性

  • 适合用于用一台计算机控制多个相同对象的场合

• 分区大小不等：

  • 增加了灵活性，可以满足不同大小的进程需求；

  • 根据常在系统中运行的作业大小情况进行划分 （比如：划分多个小分区、适量中等分区+少量大分区）

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

• 优点：

  • 实现简单；

  • 无外部碎片

• 缺点：

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

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

3、动态分区分配（可变分区分配）

不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。

1. 使用什么数据结构存储内存的使用情况

   • 空闲分区表：每一个空闲分区对应一个表项，其内容包括空闲分区的起始地址、大小、分区号、状态等信息

   • 空闲分区链：每一个空闲分区的起始部分和末尾部分分别设置前向指针和后向指针，指向前（后）一个空闲分区，同时在起始部分存储分区大小等信息

2. 当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配

   • 使用动态分区分配算法

3. 如何进行空间的分配与删除

   • 使用空闲分区表

     • 分配：修改或直接删除相应的空闲分区

     • 回收：修改或直接新增空闲分区，若存在合并，则删除掉其中一个

4. 优缺点

   • 优点

     • 系统分区的大小和数目是可变的

     • 不会产生内部碎片

   • 缺点

     • 可能产生外部碎片

可以采用“拼凑”（紧凑）技术来解决外部碎片，即操作系统不断地移动各个分区，使之相邻，拼出更大的空闲分区。

紧凑技术需要重定位寄存器的支持

4、动态分区分配算法

在存在多个可用的空闲分区时，通过动态分区分配算法来决定使用哪个空闲分区

（1）首次适应算法（First Fit）

每次都从低地址开始查找，找到第一个能满足大小的空闲分区。相应的，空闲分区以地址递增的方式进行排列。

（2）最佳适应算法（Best Fit）

尽可能优先使用小的空闲分区，找到第一个能满足大小的空闲分区。相应的，空闲分区按照容量递增的方式进行排列。

可能会产生很多外部碎片。

（3）最坏适应（Worst Fit）

也称为最大适应算法。优先使用大分区，找到第一个能满足大小的空闲分区。相应的，空闲分区按照容量递减的方式进行排列。

大的空闲分区不断变小，可能导致后到来的大进程无内存可用。

（4）邻近适应（Next Fit）

相当于对首次适应算法的改良，每一次从上次查找结束的地方开始继续查找，找到第一个能满足大小的空闲分区。相应的空闲分区在按照地址递增存储的同时，可以使用循环链表等类似数据结构。

• 首次适应算法相比于临近适应算法开销较大（每次都要从头开始检索）

• 首次适应每次都从头开始检索，会优先利用低地址部分的小分区，能够给大进程留下更多的大空闲分区

四种算法中，首次适应一般效果是最好的

3.1.4 非连续分配管理方式

1、基本分页存储方式

将内存空间分为一个个大小相等的分区，每个分区就是一个页框（页帧、内存块、物理块、物理页面）。每个页框有一个编号，即页框号（页帧号、内存块号、物理块号、物理页号），页框号从0开始。

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

• 操作系统以页框为单位为各个进程分配内存空间；

• 进程的页面与内存的页框有一一对应的关系；

• 各个页面不必连续存放，可以放到不相邻的各个页框中。

2、基本分段存储管理

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

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

分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）所组成，其中：

• 段号的位数决定了每个进程最多可以分几个段

• 段内地址位数决定了每个段的最大长度是多少

引入段式存储主要是为了满足以下的需求：

• 方便编程

• 分段共享

• 分段保护

• 动态链接

• 动态增长

（1）段表

作用与页表类似，结构包括段号、段长、基址，每个段表项的长度是相同的：

• 段号：由于段表项长度相同，可以是隐含的

• 段长：该段的长度

• 基址：该段在内存中的起始地址

（2）地址变换

1. 根据逻辑地址得到段号、段内地址

2. 判断段号是否越界（段号应当小于段表长度M）

3. 查询段表，得到对应的段表项（段表项地址 = 段表始址 + 段号 * 段表项长度）

4. 判断段内地址是否超过段长

5. 计算得到物理地址（物理地址 = 段基址 + 段内地址）

6. 访问目标内存单元

（3）分段和分页管理的区别

• 分页管理

  • 页是信息的物理单位

  • 分页的主要目的是为了实现离散分配，提高内存利用率，不会产生外部碎片，只有少量的内部碎片

  • 分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的

  • 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址

• 分段管理

  • 段是信息的逻辑单位

  • 分段的主要目的是更好地满足用户需求，会产生外部碎片

  • 一个段通常包含着一组属于一个逻辑模块的信息

  • 分段对用户是可见的，用户编程时需要显式地给出段名

  • 分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址

  • 分段更容易实现信息的共享和保护

3、段页式管理方式

• 将进程按逻辑模块分段

• 再将各段分页（如每个页面4KB）

• 再将内存空间分为天小相同的内存块

• 运行进程前将各页面分别装入各内存块中

段页式管理方式的逻辑地址由段号、页号和页内偏移量组成，其中

• 段号的位数决定了每个进程最多可以分几段

• 页号的位数决定了每个段最大由多少页

• 页内偏移量决定了页面的大小和内存块的大小

数据结构

段表：段表项包括段号（隐含）、页表长度、页表存放块号（页表起始地址）

页表：页表项包含页号（隐含）、页面存放的内存块号

地址转化过程

1. 根据逻辑地址得到段号S、页号P和页内偏移量W

2. 判断段号是否越界（段号S应当小于段表长度M）

3. 查询段表，找到相应的段表项（段表项地址 = 段表始址F + 段号S * 段表项长度）

4. 检查页号是否越界（页号应当小于页表长度）

5. 根据页表存放块号和页号找到对应的页表项

6. 根据内存块号和页内偏移量得到物理地址

总计三次访问内存

同样可以引入快表，并以段号和页号作为查询关键字，若快表命中，则可以直接得到物理地址，仅需一次访存。