第四章 内存管理

存储器的层次结构

存储器的层级结构.png

局部性原理

在一段时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。

局部性原理的 分类：

1. 时间 局部性：某条指令一旦执行，不久后该指令可能再次执行；
2. 空间 局部性：一旦程序访问了某个单元，不久后附近的存储单元也将被访问；

程序的链接和装入

程序的链接

将编译后的目标模块装配成一个可执行程序。

可执行程序以 二进制可执行文件 的形式存储在磁盘上。

程序的链接.png

链接程序的 任务：

1. 对 逻辑地址 进行修改；
2. 变换外部 调用符号：将外部调用符号变换为逻辑地址；

链接程序的任务.png

程序的链接，可划分为：

1. 静态链接：程序运行前，用 链接程序 将目标模块链接成一个完成的装入模块；
   • 程序 运行前 完成；
   • 优点：运行速度快；
   • 缺点：系统开销大；
2. 动态链接：可将某些目标模块的链接推迟到这些模块中的函数被调用执行时才进行；
   • 程序 执行时 完成；
   • 优点：节省了空间；

程序的装入

程序的装入.png

重定位：将逻辑地址（相对地址）转换为物理地址（绝对地址）的过程。

物理地址 = 逻辑地址 + 程序在内存中的起始地址

重定位.png

程序的装入，可划分为：

1. 绝对装入方式：编译时产生 物理地址 的目标代码；
2. 可重定位装入方式（静态重定位）：编译时地址是逻辑地址，装入时 通过 重定位 转换为物理地址；
3. 动态运行时装入（动态重定位）：程序 执行时 通过 重定位 转换为物理地址；

连续分配存储管理方式

1. 单一连续分配；
2. 固定分区分配；
3. 动态分区分配；

单一连续分配

任何时刻主存储器 最多只有一个作业。

单一连续分配.png

固定分区分配

每个分区 大小固定不变：分区大小相等、分区大小不等。

大小固定不变：指的是在分区分配之后，大小不变

每个分区可以且 仅可以装入一个作业。

使用 下限寄存器 和 上限寄存器 来保存当前作业的起始位置和结束位置。

固定分区分配.png

使用 固定分区说明表 区分各分区的状态。

固定分区说明表.png

动态分区分配

分区 大小不是预先固定的，而是按作业（进程）的实际需求来划分的。

分区 个数也不是预先固定的，而是由装入的作业数决定的。

使用 空闲分区表 说明空闲分区的位置。

动态分区分配.png

使用 空闲分区链 说明空闲分区的位置。

空闲分区链.png

动态分区分配算法

1. 首次适应算法；
2. 循环首次适应算法；
3. 最佳适应算法；

首次适应算法

首次适应算法的 过程：

1. 空闲分区链从 地址递增 的顺序链接，从 链首 开始查找；
2. 直至找到 第一个满足要求 的空闲分区，从该分区中划出一块内存给进程；
3. 剩下的仍留在空闲区中；

外部碎片：空闲内存 没有在 分配的 进程 中。

内部碎片：空闲内存 在 分配的 进程 中。

首次适应算法.png

循环首次适应算法

从 上次找到的 空闲分区的 下一个 空闲分区开始查找。

优点：空闲区分布均匀、查找开销较小。

缺点：缺乏大空闲区。

循环首次适应算法.png

最佳适应算法

最佳适应算法的 过程：

1. 空闲分区链以 分区大小递增 的顺序链接从 链首 开始查找；
2. 直至找到第一个与进程请求的空间大小 最接近 的空闲分区；

优点：提高内存利用率。

注意点：每次在进行空闲区的修改前，需要先进行 分区大小递增 的排序。

最佳适应算法.png

动态分区分配的流程

1. 检索空闲分区链；
2. 分配空闲分区；
3. 将分配给进程的分区起始地址返回给内存分配程序的调用者；
4. 修改空闲分区链；

动态分区回收的流程

1. 释放一块连续的内存区域；
2. 如果被释放的区域与其他空闲区相邻，则合并空闲区；
3. 修改空闲分区链；

基本分页存储管理方式

分页存储管理的基本原理

页：将一个 进程 的 逻辑地址空间 分成若干个 大小相等 的 片。

页框：将 物理内存空间 分成与页大小相同的若干个 存储块。

分页存储：将进程的若干 页 分别装入多个 可以不相邻 的 页框 中。

页内碎片：进程 最后一页 一般装不满一个页框，形成 页内碎片。

页表：记录描述页的各种数据，实现从 页号 到 页框号 的映射。

分页地址结构

注意：页内偏移量 的单位是 字节。

分页地址结构.png

分页地址变换

分页地址变换指是：逻辑地址 通过 地址变换机构 变换为 物理地址。

分页地址变换的 过程：

1. 程序执行时，PCB中 页表起始地址 和 页表长度 送CPU的 页表寄存器；
2. CPU访问某个逻辑地址A；
3. 由分页 地址变换硬件 自动将A分为 页号 和 页内偏移量 两部分；
4. 由硬件检索 页表，得到A所在的页对应的 页框号；
5. 页框号 和 页内偏移量 送 物理地址寄存器，计算 物理地址；

物理地址 = 页框大小 × 页框号 + 页内偏移量

操作系统在修改或装入页表寄存器的值时，使用的是 特权级 指令。

分页地址变换.png

页内地址变换-例题.png

分页大小的选择

页大小：512B ~ 4KB，目前的计算机系统中，大多选择 4KB 大小的页。

页大小的 选择因素：

1. 管理内存开销；
2. 内存的利用率；

快表

快表也称为“转换后援缓冲”，是为了提高CPU访问速度而采用的专用缓存，用来存放 最近被访问过的页表项。

英文缩写：TLB。

组成：键和值。

快表.png

引入快表后的地址变换过程

1. CPU产生分页的逻辑地址页号和页内偏移地址后，将页号提交给快表；
2. 查找快表，如果找到页号，得到该页所对应的页框号；否则，继续查找 内存页表，得到页框号；
3. 如果查找的页表项不在快表中，访问完内存页表后，把 该页表项写到快表中；

引入快表后的性能分析

在TLB中找到某一个页号对应的页表项的百分比称为 TLB命中率。

当 能 在TLB中找到所需要的页表项时：

有效访问时间 = 一次访问TLB 的时间 + 一次访问内存 的时间（访问内存读写数据或指令）

当 不能 在TLB中找到所需要的页表项时：

有效访问时间 = 一次访问TLB 的时间 + 两次访问内存 的时间（一次访问内存页表，一次访问内存读写数据或指令）

系统的有效访问时间.png

两级和多级页表

将页表再分页，形成两级或多级页表，将页表离散地存放在物理内存中。

在进程切换时，要运行的进程的页目录表歧视地址被写入 页表寄存器。

在二级分页系统中，为页表再建立一个页目录表的目的是为了能在地址映射时得到页表在物理内存中的地址，在页目录表的表项中存放了每一个 页表 在物理内存中所在的 页框号。

两级页表.png

基于分页的虚拟存储系统

虚拟存储器：是指具有 请求调入功能 和 置换功能，能 从逻辑上对内存容量进行扩充 的一种存储系统。

请求调入：就是说，先将进程一部分装入内存，其余的部分什么时候需要，什么时候请求系统装入。

置换：如果请求调入时，没有足够的内存，则由操作系统选择一部分内存中的进程内容移到外存，以腾出空间把当前需要装入的内存调入。

虚拟存储系统的优点

1. 提高内存利用率；
2. 提高多道程序度；
3. 把逻辑地址空间和物理地址空间分开；

虚拟存储系统的特征

1. 离散性：实现虚拟存储管理的 基础；
2. 多次性；
3. 对换性；
4. 虚拟性：实现虚拟存储系统的 最重要目标；

请求分页中的硬件支持

为了实现请求分页，需要：

1. 特殊的页表；
2. 缺页异常机构：在访问内存过程中发现缺页时产生缺页异常信号；
3. 支持请求分页的 地址变换机构，具体过程：
   • 分页地址变换机构计算出页号和页内偏移地址；
   • 查找快表，如果找到页号，读出页框号，计算物理地址；
   • 若快表无该页信息，转到内存页表中查找 页表，如果该页已调入，读出页框号，计算物理地址；
   • 如果该页尚未调入内存，则产生 缺页异常，请求调入该页，修改页表，重新执行因缺页被中断的指令；

当系统拥有足够的对换空间时，若发生缺页请求，则从对换区调入页。对换区中的页是进程运行前从文件区复制到对换区的。

特殊的页表.png

最小页框数

保证进程正常运行的所需要的最小页框数。

最小页框数与进程的大小没有关系，它与计算机的 硬件结构 有关，取决于 指令的格式、功能和寻址方式。

内存不够时，从进程本身选择淘汰页，还是从系统中所有进程中选择？：

1. 固定分配局部变换：分配固定内存，由进程本身置换；
2. 可变分配全部变换：在分配固定内存的基础上，再额外保留多余的内存，提供进程运行内存不足时使用；
3. 可变分配局部变换：分配固定内存，由进程本身置换，当操作系统发现置换频率大时，再分配额外的内存给进程；

采用什么样的算法为不同进程分配页框？：

1. 平均分配算法；
2. 按比例分配算法；
3. 考虑优先权的分配算法；

页分配策略

常用的两种 置换策略：局部置换 和 全局置换。

从分配给进程的页框数量上看，常使用的两种 分配策略：固定分配 和 可变分配。

页置换算法

1. 最佳置换算法 ORA：主要用于 理论研究；
2. 先进先出置换算法 FIFO：最简单 的页置换算法；
3. 最近最久未使用置换算法 LRU：实现最佳算法的近似算法；
4. 附加引用位算法：选择附加引用值最小的换出；
5. 简单Clock置换算法：选择最近没有被访问的淘汰；
6. 改进型Clock算法：选择即没有被访问过也没有被修改过的淘汰；
7. 最少使用算法：选择最近时期内使用次数最少的淘汰；
8. 页缓冲算法：将换出页移到空闲页链表中；

先进先出置换算法

先进先出置换算法-例题.png

先进先出置换算法-答案.png

最近最久未使用置换算法

用新调入的页替换 最长时间没有访问 的页面。

最近最久未使用LRU置换算法.png

最佳置换算法

找到 未来最晚被访问 的那个页换出。

最佳置换算法ORA.png

请求分页系统的性能

，P为缺页率。

有效访问时间与缺页率成 正比，缺页率越高，有效访问时间越长，访问效率越低。

工作集：某段时间间隔里，进程实际要访问的页的集合。

引入工作集的 目的：降低缺页率，提高访问内存效率。

抖动：运行进程的大部分时间都用于页的换入换出，几乎不能完成任何有效果工作的状态。

抖动的 产生原因：

1. 进程数量太多；
2. 分配页框太小；

抖动的 预防方法：

1. 采用局部置换策略；
2. 引入工作集；
3. 挂起若干进程；

分段存储管理

分段机制的引入

在分段存储管理的系统中，程序使用 二维 的逻辑地址，一个数用来表示 段，另一个数用来表示 段内偏移量。

引入分段的 目的：

1. 部分存储空间动态增长；
2. 信息共享；
3. 信息保护的问题；

引入分段的 优点：

1. 方便编程；
2. 分段共享；
3. 分段保护；
4. 动态链接；
5. 动态空间的增长；

比分页机制更容易实现 信息的共享。

分段系统的基本原理

分段

进程的地址空间被划分成 若干个段。

每个段定义了一组逻辑信息，每个段的大小由相应的逻辑信息组的长度确定，段的大小不一样，每个段的逻辑地址从0开始，采用一段 连续的地址空间。

系统为每个段分配一个 连续的物理内存区域，各个 不同的段可以离散 地放入物理内存不同的区域。

系统为 每个进程建立一张段表，段表的每一个表项记录的信息包括：段号、段长和该段的基址，段表存放在内存中。

分段的 逻辑地址结构：

1. 段号；
2. 段内偏移；

段表

段表是由操作系统维护的用于支持分段存储管理 地址映射 的数据结构。

每个进程有一个段表，段表由段表项构成。每个段表项包括：段号、段长（段的大小）和该段的基址（段的起始地址）。

段表.png

分段系统的地址变换

若已知逻辑单元的地址为 S:D（段号:段内偏移量），求相应物理地址的步骤如下：

1. 以段号为索引，从段表中找到段号为S的段表项；
2. 从找到的段表项中读出S段的基地址和段大小；
3. 如果D<=段大小，则将段基址与段内偏移D相加，得到与逻辑单元S:D相应的物理地址单元；

分段系统的地址变换.png

分页和分段的主要区别

相同点：分页和分段都属于 离散 分配方式，都要通过数据结构与硬件的配合来实现 逻辑地址到物理地址 的映射。

不同点：

1. 页是按 物理 单位划分的，分页的引入是为了提高内存的利用率和支持虚拟存储；而段是按 逻辑 单位划分的，一个段含有一组意义相对完整的信息，引入分段的目的是为了方便程序员编程；
2. 页的大小是 固定 的，而段的大小 不固定；
3. 分页的地址空间是 一维 的，分段的地址空间是 二维 的；

段的大小取决于 用户编写的程序 和 编译器。

段页式存储管理

段页式存储管理的基本原理

将用户进程的逻辑空间 先划分为若干个段，每个段再划分成若干个页。

进程以页为单位在物理内存中 离散 存放，每个段中被离散存放的页具有 逻辑相关性。

为了实现地址映射，操作系统为 每个进程建立一个段表，再为 每个段建立一个页表。

进程段表的段表项组成：

1. 段号；
2. 段长；
3. 页表起始地址；
4. 页表长度；

段页式存储管理.png

地址变换过程

1. 以段号s做索引，找到段s的 段表项，得到该段的 页表起始地址；
2. 通过分页机制从段内偏移d中分离出 页号P和页内偏移W；
3. 以段内页号P作为索引，从段s的页表中搜索页号P对应的 页表项；
4. 从页表项得到页所在的 页框号；
5. 由 页框号与页内偏移W 得到对应的物理地址；（物理地址 = 页框号 * 页框大小 + 页内偏移）

段页式存储管理的地址变化成程.png

Linux的伙伴系统

满足以下条件的两个块称为 伙伴：

1. 两个块具有 相同的大小，记作b；
2. 它们的 物理地址 是连续的，起始地址是 2b的整倍数；