408操作系统—3.内存管理

内存管理
- 内存管理的概念
  - 内存管理概述
    - 什么是内存管理
    - 内存管理的功能
  - 程序的链接与装入过程
    - 物理地址
    - 逻辑地址
    - 相对地址
    - 绝对地址
    - 编译
    - 链接
      - 静态链接
      - 装入时动态链接
      - 运行时动态链接
    - 装入
      - 绝对装入
      - 可重定位装入
      - 动态运行时装入
  - 进程的内存映像
  - 内存保护
  - 内存共享
  - 内存分配与回收
- 内存管理方法
  - 连续分配管理方式
  - 基本分页存储管理
  - 基本分段存储管理
  - 段页式存储管理
虚拟内存管理
- 虚拟内存基本概念
- 请求分页管理方式
- 页框分配
- 页面置换算法
- 抖动和工作集
- 内存映射文件
- 虚拟存储器性能影响因素

内存管理

内存管理的概念

内存管理概述

什么是内存管理

操作系统对内存的划分和动态分配
内存管理的功能
1. 内存空间的分配与回收
  
  由 OS 完成主存储器空间的分配和管理
2. 地址转换
  
  将程序的逻辑地址转换为内存种的物理地址
3. 内存空间的扩充
  
  利用虚拟存储技术从逻辑上扩充内存
4. 内存共享
  
  允许多个进程访问内存同一部分
5. 存储保护
  
  保证多道作业在各自存储空间运行，互不干扰

程序的链接与装入过程

物理地址：实际的硬件内存地址，由内存芯片直接访问
逻辑地址：程序员在编写程序时使用的地址，由 CPU 生成，并通过 MMU 转换为物理地址
相对地址：基于某个基准点的偏移量，需要与基准点结合来表示实际绝对地址
绝对地址：内存中的一个固定位置，是一个具体的固定数值，直接指向内存的一个存储单元

创建进程首先需要将程序和数据装入内存，将用户源程序变为可以在内存中执行的程序

编译

由编译程序将用户源代码编译成若干目标模块

目标模块：由源代码编译而来，还未被链接为最终可执行文件的**中间文件**，通常为机器代码的二进制表示
链接

由链接程序将目标模块和所需库函数链接，形成完整装入模块

装入模块：已经经过编译和链接处理，可以被操作系统装入内存并执行的**可执行文件**。装入模块通常包含了所有必要的代码、数据和资源，以便在运行时正确执行
1. 静态链接
  
  链接成完整装入模块后不再拆开
  
  由于编译后的目标模块都是相对地址，链接为装入模块时相对地址需要修改
  
  每个目标模块的外部调用符号也变化为相对地址
2. 装入时动态链接
  
  一组目标模块在装入内存时进行的链接操作，目标模块包含对动态链接库（DLL 或共享库）的引用，操作系统在加载程序时解析这些引用并加载相应的库
  
  便于修改和更新，可以实现目标模块（库文件）的共享，但增加加载时间
3. 运行时动态链接
  
  程序运行中需要用到某目标模块时再链接，未使用的目标模块都不会调入内存和形成装入模块
  
  能够加快程序装入过程，节省内存，需要额外代码管理库的加载和卸载
装入

装入程序将装入模块装入内存运行
1. 绝对装入
  
  只适用于单道程序环境
  
  编程时就将物理地址计算好，程序中的逻辑地址和实际内存地址完全相同
2. 可重定位装入
  
  也称为静态重定位装入，装入时根据实际情况调整程序的地址，将程序加载到合适的内存位置，把程序中的相对地址转换为物理地址
  
  必须一次分配所有所需内存，运行期间不能移动也不能再次申请内存空间，避免地址冲突
3. 动态运行时装入
  
  也称为动态重定位装入
  
  可以装入部分需要执行的代码分配相应内存地址，在程序运行期间根据动态需要申请内存，且申请的内存区可以不连续
  
  因此每分配一段内存地址都需要一个重定位寄存器，其中存放装入模块的起始位置
  
  通常与运行时动态链接结合发生

进程的内存映像

程序调入内存运行时，构成进程的内存映像

代码段

程序的二进制代码，只读，共享
数据段

包含全局变量和静态变量
bss 段

包含未初始化的全局变量和静态变量
进程控制块（见2️⃣进程与线程）
堆

动态内存分配，存放动态分配变量，通过调用 malloc 函数动态向高地址分配空间
栈

实现函数调用和存储局部变量，从用户空间最大地址往低地址方向增长

int global_var = 10;  // 数据段

int main() {
    static int static_var = 20;  // 数据段
    int local_var = 30;  // 栈
    int *heap_var = (int *)malloc(sizeof(int));  // 堆
    *heap_var = 40;
}

内存保护

确保每个进程都拥有单独的内存空间，有以下两种方法：

在 CPU 中设置⼀对上下限存储器，存放用户进程在主存中的下限和上限地址，判断 CPU 访问的地址是否越界
重定位寄存器（基地址寄存器）和界地址寄存器（限长寄存器）进行越界检查

前者存放进程起始物理地址

后者存放进程最大逻辑地址，即进程的内存段的长度（或界限）。它定义了进程可以访问的内存范围的大小。
1. 逻辑地址生成：进程生成一个逻辑地址用于访问内存
2. 越界检查：在将逻辑地址转换为物理地址之前，系统会进行越界检查：
  - 检查逻辑地址是否小于界地址寄存器的值（即逻辑地址是否在合法范围内）
  - 如果逻辑地址大于或等于界地址寄存器的值，则发生越界访问，系统会触发异常或错误处理机制
3. 地址转换：如果逻辑地址通过了越界检查，系统会将逻辑地址加上重定位寄存器的值，生成实际的物理地址
4. 内存访问：使用生成的物理地址进行内存访问
仅操作系统可以加载以上两个寄存器，不允许用户更改

内存共享

只有只读区域才可以共享，

纯代码/可重入代码=不能修改的代码，不属于临界资源

实际执行时，每个进程配有局部数据区，可能改变的部分将复制到数据区，只对各自的私有数据区内存进行修改，共享代码不改变

内存分配与回收

连续分配
1. 单一连续分配
  
  单道发展到多道 OS↓
2. 固定分区分配
  
  为了适应大小不同的程序 ↓
3. 动态分区分配
  
  更好提高内存利用率 ↓
不连续分配
1. 分段存储管理
  
  为了满足用户在编程和使用方面的要求
2. 分页存储管理
3. 段页存储管理

内存管理方法

连续分配

为用户分配一个连续的内存空间

内部碎片：当程序小于固定分区大小时，也要占用一个完整的内存分区，这样分区内部就存在空间浪费

单一连续分配
- 定义
  
  内存分为系统区和用户区
  
  系统区仅 OS 使用，用户区由一道程序独占
- 优点
  1. 简单，无外部碎片
  2. 无需进行内存保护
- 缺点
  1. 只能用于单用户单任务系统
  2. 存在内部碎片，存储器利用率极低
固定分区分配
- 定义
  
  内存划分为若干固定大小分区，每个分区只有一道作业
- 优点
  - 简单
- 缺点
  1. 程序太大可能放不进任何分区，存在内部碎片
  2. 不能实现多进程共享一个主存区，存储空间利用率低
动态分区分配
- 概念
  
  也称可变分区分配，进程转入内存时，根据进程的实际需要，动态地分配内存；动态分区是在作业装入时动态建立的，装入时使用多少，分区大小就是多少
  
  随时间推移容易出现外部碎片
  
  外部碎片：存在于所有内存分区的外部，区别于内部碎片
- 内存回收方法
  1. 回收区与插入点的前一空闲分区相邻，此时将这两个分区合并，并修改前一分区表项的大小为两者之和
  2. 回收区与插入点的后一空闲分区相邻，此时将这两个分区合并，并修改后一分区表项的始址和大小
  3. 回收区同时与插入点的前、后两个分区相邻，此时将这三个分区合并，修改前一分区表项的大小为三者之和，并取消后一分区表项
  4. 回收区没有相邻的空闲分区，此时应该为回收区新建一个表项，填写始址和大小，并插入空闲分区链
- 基于顺序搜索的分配算法
  1. 首次适应算法
    
    按地址递增的次序排列，分配第一个能满足大小的空闲分区
    
    保留了高地址部分大空闲分区
    
    低地址部分产生大量碎片，增加查找开销
  2. 邻近适应算法(循环首次适应算法)
    
    与前者相比，从上次查找结束的位置继续开始查找
    
    导致高地址部分无大空闲分区，比前者适应性更差
  3. 最佳适应算法
    
    按**容量递增**次序排列，分配第一个能满足大小的空闲分区
    
    将留下越来越多难以利用的内存碎片，产生外部碎片最多
  4. 最坏适应算法
    
    按容量递减次序排列，分配当前最大的空闲分区
    
    将导致没有大分区可用，性能也很差
- 基于索引搜索的分配算法
  
  根据大小对空闲分区分类，每个分类设立一个空闲分区链，用一个索引表管理空闲分区链
  1. 快速适应算法
    
    找到能容纳的最小空闲分区链表，取出链表第一块空间
    
    查找效率高，不产生内部碎片
    
    回收分区需要有效合并分区，系统开销大，复杂
  2. 伙伴系统
    
    所有分区大小均为 $2^k$，需要分配大小为 n 的分区时 $(2^{i-1}<n\leqslant2^{i})$，在大小为 $2^i$ 的空闲分区链中分配
    
    耗尽则在 $2^{i+1}$ 中分配，若有，拆分该分区为两个 $2^i$ 大小分区，一个分配，另一个加入前一空闲分区连，称为一对伙伴
    
    以此类推，回收时，也可能需要对伙伴分区合并
  3. 哈希算法
    
    构建以空闲分区大小为关键字的哈希表，记录空闲分区链的头指针
    
    由所需分区大小，在哈希表中由哈希函数查找到头指针位置，得到空闲分区链表

连续分配方式中，不管如何分配，只要没有连续的足够大小的空间即无法分配

因此有非连续分配方式，由分区大小是否固定分为分页与分段

分页中由是否需要整个作业装入内存中分为基本分页和请求分页

基本分段存储管理

概念
1. 分段
  
  将用户进程分隔为若干个带有属性的逻辑分段，段内地址连续，段间地址不连续
2. 逻辑地址结构
  
  逻辑地址由 段号S 与 段内偏移量W 两部分构成，前 16 位表示段号，后 16 位表示偏移量，因此进程最多 $2^{16}$ 段，最大段长 64KB
  - 段号
    
    用于在段表中查找对应表项
  - 段内偏移量
    
    用于与基地址配合计算对应物理地址
3. 段表
  
  一张逻辑空间与内存空间的映射表，一个段对应一个段表项，一个进程通常只拥有一个段表
  
  段表记录段在内存中的 基地址b 和 段长C
  - 基地址
    
    用于与段内偏移量计算对应物理地址的基准地址
  - 段长
    
    防止偏移量越界的限制
  段号段长在主存的始址
  
  段表存储于段表寄存器中，段表寄存器存储了 段表始址F 与 段表长度M
4. 地址变换
  
  见下图 2，将逻辑地址 A 映射为物理地址 E
  1. 取出 逻辑地址A 的 段号S 和 偏移量W
  2. 判断段号是否越界，若 S>=M，则越界中断，否则执行
  3. 查询段号对应段表项，段表项地址=F + S * 段表项长度
  4. 取出 段长C，若 W>=C，则产生越界中断，否则继续执行
  5. 取出 始址b，计算物理地址 E=b+W
段的共享和保护
- 共享
  
  两个作业的段表中相应表项指向被共享段，共享段应只读
- 保护
  - 存储控制保护
    
    如地址变换过程 2
  - 地址越界保护
    
    如地址变换过程 4
优点
1. 有利于反映程序的逻辑结构，利于动态链接及编程
2. 分段保护，分段共享
3. 段的大小可以动态调整
缺点
1. 产生外部碎片
2. 内存交换效率低

基本分页存储管理

概念

分页

将整个虚拟和物理内存空间切成一段段固定尺寸的分区称为页框、页帧或物理块
页面

进程逻辑地址空间由与物理块大小相等的页面组成

也即页面和物理块是大小相等的

页大小为页的字节数，2的幂次方，通常4KB

页面大———内部碎片变多，降低利用率

页面小———页面数变大，页表长，增加地址转换开销
逻辑地址结构

地址结构包含 页号P 和 页内偏移量W
- 页号
  
  用于在页表中查找对应的物理块号
- 页内偏移量
  
  用于与页号结合在内存的一个物理块中查找实际的地址
  
  标识逻辑地址在特定页内的位置
  
  页内偏移量的位数等于页大小的对数$log_2(Page Size)$
以 2 的整数次幂划分页面大小时，物理块大小通常为4KB，$\log_2{4KB}=12位$，即一个页内偏移量需要用12位表示

假设逻辑地址由32位组成

则低12位 $0\sim11$ 为页内偏移量，高$31-12=19$位12~31 为页号，即一个进程最多可以分配 $2^{20}$ 页

以下为24位逻辑地址计算例子
```
逻辑地址: 0x1234AB
二进制表示: 0001 0010 0011 0100 1010 1011
逻辑地址由24位组成
+-------------------+--------------------+
|     页号 (高8位)   |  页内偏移量 (低16位) |
+-------------------+--------------------+
|    0001 0010      | 0011 0100 1010 1011|
+-------------------+--------------------+

页号: 0x12 (18)
页内偏移量: 0x34AB (13483)
```
页表

实现从页号到物理块号的映射

页表项由页号和块号组成

页表的起始地址和页表长度放在页表寄存器 PTR 中
进程未执行时，存放于PCB中，进程调度时，存入PTR中

页表存储于内存中，内存管理单元 MMU 负责将虚拟地址转换为实际物理地址
- 页号
  
  不存储于页表中，页表项连续存放，页号可以隐含，不占存储空间
- 页表项
  - 物理块号
    
    指示逻辑页在物理内存中的位置
  - 额外信息
    
    通常占用4位
1B = 8位，逻辑地址空间大小$=2^{逻辑地址位数}B$

假设一个逻辑地址空间32位表示，一页面4KB，1B表示一个地址

则逻辑地址空间大小为：$2^{32}B=4GB$

逻辑地址空间内页数：$\frac{2^{32}B}{4KB}=\frac{2^{32}}{2^{12}}=2^{20}=1048576页$，也即该系统内一个进程最多$2^{20}$页，页面号需要20位表示

则页表项大小至少为$20+4=24位=3B$

页表大小：$页数\times页表项大小=1048576\times3=3145728B=4GB$

地址转换

基本地址转换

由逻辑地址A转换物理地址E

由A计算出页号P和页内偏移量W
在页表中查找P对应的物理块号F，若P>页表长度M则越界中断
将F与W组合生成物理地址

页号: 0x12 (18)
页内偏移量: 0x34AB (13483)

页号 18 对应的物理块号: 7

物理地址计算:
物理页框号起始地址: 7 * 4KB = 28672 (0x7000)
物理地址: 28672 + 13483 = 42155 (0xA4AB)

两级页表地址变换

单级页表处理大地址空间时，需要占用大量连续的内存地址空间来保存页表，解决办法如下：

页表所需内存空间，离散分配，用一个新的页表记录离散分配的页表位置
需要页表的部分存入内存，其余驻留硬盘

新的页表称为**外层页表（页目录）：**记录二级页表的基地址

**外层页表寄存器（页目录基址寄存器）：**存放外层页表起始地址

32位的虚拟地址可以分解为三个部分：

一级页表索引：用于索引一级页表（页目录表）
二级页表索引：用于索引二级页表（页表）
页内偏移

通常将原页表按照每一部分刚好能用一物理块存储拆分为二级页表，此时每个二级页表都为4KB，页表项1024个，需要10位表示二级页表索引

32位地址需要12位表示偏移，一二级页表索引都为10位

虚拟地址: 0x12345678(0001 0010 0011 0100 0101 0110 0111 1000)

虚拟地址一级页表索引 (10位) 二级页表索引 (10位) 页内偏移 (12位)

0x12345678 0001 0010 00 11 0100 0101 0110 0111 1000

一级页表索引查找一级页表，得到二级页表的基地址，例如 0x2000

二级页表索引查找二级页表，得到物理页框的基地址，例如 0x3000

页内偏移0110 0111 1000 0x678

计算得物理地址 = 0x3000 + 0x678 = 0x3678

虚拟地址	一级页表索引 (10位)	二级页表索引 (10位)	页内偏移 (12位)
0x12345678	0001 0010 00	11 0100 0101	0110 0111 1000

对于64位地址空间，两级分页时，页面大小设为4kb，页表项大小4B

则逻辑地址空间内页数为$64-12页内偏移-10二级页表索引=42$

则外层页表需要占用16384GB连续内存空间

因此更大的逻辑地址空间必须使用多级页表

具有快表的地址变换

地址变换机构中增设能够并行查找的高速缓冲存储器——快表（TLB,相联存储器）

TLB存储最近使用的虚拟地址到物理地址的映射

存在TLB时，首先查找TLB，有则使用，无则查找页表并将映射添加进TLB

段页式存储管理

如何划分空间

结合分段与分页
1. 程序划分为多个有逻辑意义的段
2. 分段出来的连续空间再分页
组成
- 段表
  
  每个进程都有一张段表，段表包含段号、页表长度、页表始址
  
  每个段表项都用于找到一个页表
- 页表
  
  页表中包含页号和块号
- 段表寄存器
  
  指出进程的段表始址和段表长度，兼具判断逻辑地址段号是否越界的功能
- 逻辑地址
  
  逻辑地址由段号、页号、页内偏移量组成
地址变换
1. 逻辑地址段号S，配合段表寄存器中的段表始址，确定段表项，同时判断段号是否越界
2. 通过段表得到对应页表始址，配合逻辑地址页号，得到物理块号
3. 物理块号，配合逻辑地址页内偏移量，得到具体物理地址