OS-Chapter2-内存管理

# 存储管理基础

# 基本目标

• 地址独立：程序发出的地址与物理地址无关
• 地址保护：一个程序不能访问另一个程序的地址空间

# 功能

• 存储分配和回收：是存储管理的主要内容。讨论其算法和相应的数据结构。

• 地址变换：可执行文件生成中的链接技术、程序加载时的重定位技术，进程运行时硬件和软件的地址变换技术和机构。

• 存储共享和保护：代码和数据共享，对地址空间的访问权限（读、写、执行）。

• 存储器扩充：涉及存储器的逻辑组织和物理组织；

# 几个概念

• 地址空间：源程序经过编译后得到的目标程序，存在于它所限定的地址范围内，这个范围称为地址空间。简言之，地址空间是 逻辑地址的集合
• 存储空间：指主存中一系列存储信息的物理单元的集合，这些单元的编号称为物理地址或绝对地址。简言之，存储空间是 物理地址的集合
• 碎片：内存中无法被利用的存储空间
  • 内碎片：分配给作业的存储空间中未被利用的部分。无法被整理，但作业完成后会得到释放
  • 外碎片：系统中无法利用的小的空闲分区。外碎片才是造成内存系统性能下降的主要原因。外部碎片可以被整理后清除（紧凑技术）

# 存储分配和回收

# 单一连续分配

在 单道程序 环境下，整个内存里只有两个程序：一个用户程序 和 操作系统

• 操作系统所占的空间是固定的，用户程序永远从同一个地方开始运行

• 静态地址翻译：即在程序运行之前就计算出所有物理地址

• 优点：实现简单；无需地址翻译，程序运行速度快

• 缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低 ；比物理内存大的程序无法加载运行

# 固定（静态）分区分配

最简单的一种 多道程序 存储管理方式。它将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。当有空闲分区时，便可从外存的后备作业队列中选择适当大小的作业装入该分区，如此循环。

• 划分分区有两种方法：

  • 分区大小相等。只适合于多个相同程序的并发执行（处理多个类型相同的对象）

  • 分区大小不等。划分为多个较小的分区、适量的中等分区和少量大分区。增加了灵活性

• 优点：易于实现，开销小，无外部碎片。

• 缺点：内碎片造成浪费，分区总数固定，限制了并发执行的程序数目。

• 采用的数据结构：分区表 —— 记录分区的大小和使用情况

# 可变（动态）分区分配

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

数据结构

在管理内存的时候，OS 需要知道内存空间有多少空闲，这就必须跟踪内存的使用，有两种常用的数据结构：

• 位图表示法（分区表）：给每个分配单元赋予一个字位，用来记录该分配单元是否闲置。例如，字位取值为 0 表示单元闲置，取值为 1 则表示已被占用。

  • 空间成本固定：不依赖于内存中的程序数量。
  • 时间成本低：操作简单，直接修改其位图值即可。
  • 没有容错能力：如果一个分配单元为 1，不能肯定应该为 1 还是因错误变成 1

• 将分配单元按照是否闲置链接起来，这种方法称为链表表示法。如上图所示的的位图所表示的内存分配状态，使用链表来表示的话则会如下图所示

  • 空间成本：取决于程序的数量。

  • 时间成本：链表扫描通常速度较慢，还要进行链表项的插入、删除和修改。

  • 有一定容错能力：因为链表有被占空间和闲置空间的表项，可以相互验证

分区分配流程

• 事先规定 size 是不再切割的剩余分区的大小。

• 设请求的分区大小为 u.size ，空闲分区的大小为 m.size 。

• 若 m.size - u.size ≤ size ，将整个分区分配给请求者。

• 否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区表 / 链中。

分区回收方式

将相邻的空闲区域合并为一个

基于顺序搜索的分配算法

基于索引搜索的分配算法

快速适应算法

又称为分类搜索法，把空闲分区按容量大小进行分类，经常用到长度的空闲区设立单独的空闲区链表。系统为多个空闲链表设立一张管理索引表

• 优点：查找效率高，不会对任何分区产生分割，所以能保留大的分区，不会产生内碎片
• 缺点：在分区归还主存时算法复杂，系统开销较大。在分配空闲分区时是以进程为单位，一个分区只属于一个进程，存在一定的浪费

可重定位分区分配

紧凑技术，定时的或在内存紧张时，移动某些已分配区中的信息，把存储空间中所有的空白区合并为一个大的连续区

• 优点：把存储空间中所有的空白区合并为一个大的连续区
• 缺点：性能开销、设备依赖（DMA）、间接寻址

# 伙伴系统

在分配存储块时将一个大的存储块分裂成两个大小相等的小块，这两个小块就称为 “伙伴”

• 核心思想

  所有分区大小为 2^k ，通过递归分裂与合并管理内存。

• 分配过程：

  • 向上取整到最近的 2^k（如 50KB → 64KB）。
  • 若没有匹配块，则分裂更大的块（如 128KB → 2×64KB），直到满足需求。

• 回收过程：

  • 检查释放块的 “伙伴” 是否空闲，若空闲则合并为更大的块，递归直到无法合并。

• 优点

  • 快速合并：利用二进制地址特性，合并操作高效（仅需检查伙伴块）。

  • 基本无外部碎片：合并机制确保大块内存可重用。

• 缺点

  • 可能会产生严重内部碎片：请求大小与 2k 不匹配时浪费严重（如 257KB 占用 512KB）。

# 程序段

一个程序本质上都是由 bss 段、data 段、text 段三个组成的

• bss 段：用来存放程序中未初始化的全局变量的一块内存区域。属于静态内存分配
• data 段：用来存放程序中已初始化的全局变量的一块内存区域。属于静态内存分配
• text 段：用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读

text 和 data 段都在可执行文件中，由系统从可执行文件中加载，而 bss 段不在可执行文件中，由系统初始化 。

一个装入内存的可执行程序，除了 bss、data 和 text 段外，还需构建一个栈（stack）和一个堆（heap）。

• 栈 (stack)：用户存放程序 局部变量 的内存区域，也用于保存 / 恢复调用现场
• 堆（heap）：存放进程运行中动态分配的内存段。它的大小并不固定，可动态扩张或缩减。 malloc 、 free 就是通过堆实现的

# 程序的执行过程

一个用户源程序要变为在内存中可执行的程序，通常要进行以下处理：

• 编译 (compile)：由编译程序将用户源程序编译成若干个目标模块。
• 链接 (linking)：由链接程序将目标模块和相应的库函数链接成可装载模块（通常是单一可执行文件）。
• 装入 (loading)：由装载程序将可装载入模块装入内存。

# 程序的链接

• 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开
• 动态链接：用于链接共享库代码。当程序运行中需要某些目标模块时，才对它们进行链接，具有高效且节省内存空间的优点。但相比静态链接，使用动态链接库的程序相对慢

# 程序的装入

采用 动态运行时 装入的方式

装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到 程序运行时 才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。

特点：可以将程序分配到不连续的存储区中；在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间；采用动态重定位时允许程序在内存中发生移动

# 程序、进程和作业

• 程序是静止的，是存放在磁盘上的可执行文件
• 进程是动态的。进程包括程序和程序处理对象（数据集），是一个程序对某个数据集的执行过程，是分配资源的基本单位。通常把进程分为系统进程和用户进程两大类。进程是竞争计算机系统有限资源的基本单位
• 作业是用户需要计算机完成的某项任务，是要求计算机所做工作的集合。一个作业可由多个进程组成，且必须至少由一个进程组成

一个作业可划分为若干个进程来完成，而每一个进程由其实体 —— 程序和数据集合

# 分页内存管理

# 基本思想

把一个 逻辑地址连续 的的程序分散存放到 若干不连续的内存区域 内，并保证程序的正确执行，则既可充分利用内存空间，又可减少移动带来的开销

# 概念

• 页：在分页存储管理系统中，把每个作业的 地址空间 分成一些大小相等的片，称之为页面或页。
• 存储块：在分页存储管理系统中，把 主存的 存储空间 也分成与页面相同大小的片，这些片称为存储块，或称为页框、内存块、物理页面。
• 页表：每个进程都有一张页表，储存在 PCB（进程控制块）中。记录进程 页 和实际存放的 内存块 之间的 地址映射关系

# 纯分页系统

不具备页面置换功能，必须把它的所有页一次装到主存的页框内；如果当时页框数不足，则该作业必须等待，系统再调度另外作业

• 优点：
  • 没有外碎片，每个内碎片不超过页大小。
  • 程序不必连续存放。便于改变程序占用空间的大小（主要指随着程序运行而动态生成的数据增多，要求地址空间相
    应增长，通常由系统调用完成而不是操作系统自动完成）。
• 缺点：程序全部装入内存。（时间连续性）

# 地址结构

给定一个逻辑地址空间中的地址为 A，页面的大小为 L，则：

• 页号 P = [ A / L ]
• 页内地址 d = A % L

# 基本地址变换（一级页表）

访存次数：2 次

# 二级页表

一级页表的不足：若逻辑地址空间很大，则划分的页面就很多，页表就很大，占用的存储空间大 **（连续）**。

为解决此问题，将页表再进行分页，离散地将各个子页表存放在不同的物理块中

访存次数：3 次

# 快表（TLB）

快表是一种特殊的高速缓冲存储器（Cache） ，内容是页表中的一部分或全部内容。
CPU 产生逻辑地址的页号，首先在快表中寻找：

• 若命中就找出其对应的物理块；
• 若未命中，再到页表中找其对应的物理块，并将之复制到快表。

若快表中内容满，则按某种算法淘汰某些页

TLB 的其它特性

• 有的 TLB 在每个 TLB 条目中还保存地址空间标识码（address-space identifier，ASID）。ASID 可用来唯一标识进程，并为进程提供地址空间保护。当 TLB 试图解析虚拟页号时，它确保当前运行进程的 ASID 与虚拟页相关的 ASID 相匹配。如果不匹配，那么就作为 TLB 失效。
• 除了提供地址空间保护外，ASID 允许 TLB 同时包含多个进程的条目。如果 TLB 不支持独立的 ASID，每次选择一个页表时（例如，上下文切换时），TLB 就必须被冲刷（flushed）或删除，以确保下一个进程不会使用错误的地址转换。

# 分段内存管理

# 基本思想

进程的地址空间，按照 程序自身的逻辑关系 关系划分为若干个段，每个段都有一个段名（翻译为段号），每个段是连续的，从 0 开始编址。例如下图：

# 地址结构

# 地址变换

与页表的地址变换相似，每个进程都有一张 段表，储存在 PCB（进程控制块）中。记录进程的 段 和实际存放的 物理地址 之间的 地址映射关系

访存次数：2 次

# 分页与分段的比较

# 段页式内存管理

# 基本思想

先分段，再分页。用分段方法来分配和管理虚拟存储器，而用分页方法来分配和管理实存储器。

# 地址结构

# 段表和页表

# 地址变换

访存次数：3 次

若使用 TLB 且命中，则只需访存一次

# 虚拟内存管理

# 覆盖与交换

# 覆盖技术

将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。

内存中分为一个 “固定区” 和若干个 “覆盖区”。需要常驻内存的段放在 “固定区” 中，调入后就不再调出（除非运行结束) 不常用的段放在 “覆盖区”，需要用到时调入内存，用不到时调出内存。

缺点：

• 编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。
• 从外存装入覆盖文件，以时间延长来换取空间节省。

# 交换技术

广义的说，所谓交换就是 把暂时不用的某个（或某些）程序及其数据的部分或全部从主存移到辅存中 去，以便腾出必要的存储空间；接着 把指定程序或数据从辅存读到相应的主存中，并将控制转给它，让其在系统上运行。

• 优点：

  • 增加并发运行的程序数目，并且给用户提
  • 供适当的响应时间；编写程序时不影响程序结构

• 缺点：

  • 对换入和换出的控制增加处理机开销；
  • 程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。

# 虚拟内存的基本概念

# 传统存储管理的问题

• 一次性：作业必须一次性全部装入内存后，才能开始运行。这会导致两种情况：

  • ①当作业很大而不能全部被装入内存时，将使该作业无法运行；
  • ②当大量作业要求运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序度的下降。

• 驻留性：作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。运行中的进程会因等待 IO 而被阻塞，可能处于长期等待状态。

# 局部性原理

快表、页高速缓存及虚拟内存技术都属于高速缓存技术，这个技术所依赖的原理就是局部性原理。

• 时间局部性。

  程序中的某条指令一且执行，不久后该指令可能再次执行；某数据被访问过，不久后该数据可能再次被访问。产生的原因是程序中存在着大量的循环操作。

• 空间局部性。

  一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式聚存储的。

# 虚拟存储的基本原理

• 按需装载：在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。
• 缺页调入：在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。
• 不用调出：另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段――具有请求调入和置换功能，只需程序的一部分在内存就可执行，对于动态链接库也可以请求调入

# 虚拟存储的基本特征

• 离散性：物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间）
• 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
• 对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
• 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

虚拟性以多次性和对换性为基础，多次性和对换性必须以离散分配为基础。

# 代价和限制

• 代价：虚拟存储量的扩大是以牺牲 CPU 工作时间以及内外存交换时间为代价
• 限制：
  • 虚拟内存的 ** 最大容量 ** 是由计算机的地址结构（ CPU 寻址范围）确定的
  • 虚拟内存的 ** 实际容量 **= min (内存和外存容量之和，CPU 寻址范围)

# 请求分页系统

在运行作业之前，只要求把当前需要的一部分页面装入主存。当需要其它的页时，可自动的选择一些页交换倒辅存去，同时把所需的页调入主存。

虚拟存储系统：控制自动页面交换而用户作业意识不到的那个机构，成为虚拟存储系统。

# 页表机制

# 调入问题

# 缺页中断机制

属于 故障

# 地址变换

# 页面置换算法

# 最佳置换算法

是所有页置换算法中页错误率最低的，但它需要引用先验知识，因此无法被实现。

• 它会将内存中的页 P 置换掉，页 P 满足：从现在开始到未来某刻再次需要页 P，这段时间最长。也就是 OPT 算法会置换掉未来最久不被使用的页 。
• OPT 算法通常用于比较研究，衡量其他页置换算法的效果。

# 先进先出算法（FIFO）

每次选择淘汰的页面是最早进入内存的页面

把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。

性能较差：较早调入的页往往是经常被访问的页，这些页在 FIFO 算法下被反复调入和调出。并且有 Belady 现象。

Belady 现象：在使用 FIFO 算法作为缺页置换算法时，分配的页面增多，但缺页率反而提高。

# 改进的 FIFO —— Second Chance 算法

如果被淘汰的数据之前被访问过，则给其第二次机会（Second Chance）

• 每个页面会增加一个访问标志位，用于标识此数据放入缓存队列后是否被再次访问过。
• A 是 FIFO 队列中最旧的页面，且其放入队列后没有被再次访问，则 A 被立刻淘汰；否则如果放入队列后被访问过，则将 A 移到 FIFO 队列头，并且将访问标志位清除。
• 如果所有的页面都被访问过，则经过一次循环后就会按照 FIFO 的原则淘汰。

# 改进的 FIFO —— Clock 算法（NRU）

Clock 是 Second Chance 的改进版，也称最近未使用算法 (NRU, Not Recently Used)。

通过一个环形队列，避免将数据在 FIFO 队列中移动。

产生缺页错误时，当前指针指向 C：

• 如果 C 被访问过，则清除 C 的访问标志，并将指针指向 D；

• 如果 C 没有被访问过，则将新页面放入到 C 的位置，置访问标志，并将指针指向 D。

由于 FIFO 类算法命中率相比其他算法要低不少，因此实际应用中很少使用此类算法。

# 最近最少使用算法（LRU）

LRU 算法根据数据的历史访问记录来进行淘汰数据，其核心思想是 “如果数据最近被访问过，那么将来被访问的几率也更高”。

• 这是局部性原理的合理近似，性能接近最优算法。
• 但由于需要记录页面使用时间的先后关系，硬件开销太大。
• 实现方法之一：
  • 设置一个特殊的栈，保存当前使用的各个页面的页面号。
  • 每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。栈底始终是最近最久未使用页面的页面号。

# 页面分配策略

# 驻留集

指请求分页存储管理中给进程分配的物理块的集合

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。

若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际上用于进程推进的时间很少。

驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

• 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间大小不变。即，驻留集大小不变。
• 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变
• 局部置换：发生缺页时只能选进程自己的物理块进行置换。
• 全局置换: 可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

# 分配与置换策略

• 固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。

  这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。

• 可变分配全局置换：刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页都将获的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是进程中任意一个进程的页，因此被选中的这个进程物理块会减少，缺页率会增加。

• 可变分配局部置换：刚开始会为每个进程分配一定数量的物理块，当某进程发生缺页时，只允许从该进程自己的物理块中选出一个换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当，反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

# 抖动问题

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。

产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够)。

• 为进程分配的物理块太少，会使进程发生抖动现象。
• 为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率

预防与消除：

• 局部置换策略

• 引入工作集算法

• 预留部分页面

• 挂起若干进程

# 工作集

指在某段时间间隔里，进程实际访问页面的集合。

一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。