Notes@Tsukino

存储管理

2分钟阅读

操作系统

存储管理负责管理计算机的内存资源，为程序运行提供地址空间支持。核心任务包括地址重定位、内存分配与回收、逻辑地址到物理地址的映射、虚拟内存扩展以及页面置换，目标是在有限的内存空间内高效、安全地支持多道程序的并发执行。

存储体系结构

存储体系结构

存储结构层次

  • 从上到下：访问速度递减、容量递增、成本递减
层次速度容量成本典型技术
寄存器最快（ns）最小（字）最高CPU 内寄存器
Cache（高速缓存）快（ns）较小（MB）高SRAM
主存（内存）中等（μs）中等（GB）中DRAM
辅存（磁盘）慢（ms）大（TB）低磁介质/SSD
磁带/archive最慢（s）最大（PB）最低磁带/光盘
  • 速度与成本矛盾：越快越贵，需通过分级存储实现性价比平衡
  • 局部性原理：程序执行时仅访问少数热点区域，可通过层次结构提供”大容量+高速度”的近似效果

为什么需要存储管理

  • 冯·诺依曼结构中，程序和数据必须在内存中才能被 CPU 执行
  • 存储器是珍贵资源，需合理使用
  • 程序的逻辑空间和物理空间不同，需映射

存储管理的主要任务

  • 内存分配和回收：进程创建时分配空间，撤销时回收
  • 地址映射（逻辑地址 → 物理地址）：由 MMU（Memory Management Unit）完成
    • 地址重定位方式：绝对装入（编译时）、静态重定位（加载时）、动态重定位（执行时）
  • 内存保护：防止进程间串扰，防止用户程序跨越到系统空间
  • 内存扩充（虚拟内存）：借助外存在逻辑上扩充内存
    • 覆盖技术（Overlay）：程序员手动安排互斥代码段
    • 交换技术（Swapping）：OS 自动将进程在内存和外存间换入换出
    • 虚拟存储：基于局部性原理，按需调入页面，缺页中断处理

地址重定位方式

方式时机特点典型应用
绝对装入编译时地址一一对应，简单但灵活性差单片机、早期 DOS
静态重定位加载时装入时修改地址值，执行期间不变需连续存储
动态重定位执行时逻辑地址不变，访问时映射（基址+偏移）现代 OS，支持页式/段式/虚拟存储
指向原始笔记的链接

连续存储管理

连续存储管理

单一连续分区

  • 内存分为两块：系统区（OS 内核）和 用户区（一个进程独占）
  • 通过界地址寄存器实现越界保护
  • 适用：单道批处理系统
  • 缺点：CPU 利用率低，内存浪费严重

固定分区

  • 内存预先划分为若干个大小固定的分区
  • 一个作业占用一个分区
  • 通过分区状态表（起始地址 + 分区大小 + 状态）管理
  • 进程排队方式：多队列（按大小排队，减少内部碎片）或单队列
  • 缺点：内部碎片（分区内未用完的空间），分区总数固定，限制并发进程数

重点 可变分区（动态分区）

  • 根据作业大小动态划分内存，需要多少切多少
  • 用空闲区链表管理（节点含：大小、起始地址、next 指针）
  • 外部碎片问题：经过多次分配释放，空闲分区总和够用但不成连续

分配算法

算法策略优点缺点
首次适应（First Fit）从低地址开始找第一个足够大的空闲分区简单，保留高端大空间产生外部碎片，查找次数多
循环首次适应（Next Fit）从上一次分配的位置继续找（循环链表）分配均匀，查找更快不易保留大分区
最佳适应（Best Fit）选最小的足够大的空闲分区剩余碎片最小产生许多小外部碎片
最差适应（Worst Fit）选最大的空闲分区无需查找，直接取首大分区被切碎

碎片处理

  • 外部碎片：空闲分区总和够用但不成连续，无法分配
  • 紧凑（Compaction）：移动已分配分区聚到一端，合并空闲空间
    • 需要动态重定位（基址寄存器）支撑
  • 释放时合并规则：空闲块相邻时需合并（前邻空闲、后邻空闲、前后皆空闲、前后皆占用四种情形）

内部碎片 vs 外部碎片

类型定义产生场景
内部碎片已分配给进程的分区中未被使用的空间固定分区（进程需求 < 分区大小）
外部碎片空闲分区总和够用但不成连续可变分区（多次分配释放后）
指向原始笔记的链接

页式存储管理

页式存储管理

基本思想

  • 将程序的逻辑地址空间划分为等长的页（Page）
  • 将物理内存划分为同样大小的页帧（Page Frame）
  • 逻辑上连续的空间在物理内存中可以分散存放在不同页帧
  • 页大小定为 2 的 k 次幂：地址转换中的除法/乘法可转化为移位操作，提高效率

重点 页表（Page Table）

  • 每个进程一张独立页表，PCB 中有指针指向其页表
  • 页表为数组结构：数组下标 = 逻辑页号（自然映射，无需额外存储页号），节省内存
  • 页表项内容：物理页帧号 + 权限位（读/写/执行）+ 状态位等
  • 存储于系统空间

地址转换

  • 逻辑地址 = 页号（高位）+ 页内偏移（低位）
  • 物理地址 = 帧号（高位拼接）+ 页内偏移（低位）—— 位拼接，区别于段式的加法拼接
  • 由 MMU（内存管理单元）硬件完成
  • 转换流程：
    1. 从 PCB 获取该进程页表起始地址
    2. 线性逻辑地址拆分为页号 P 和页内偏移 W
    3. 以 P 为下标查页表，得到物理页帧号 F
    4. 物理地址 = F（高位拼接）+ W（低位）

TLB（快表，Translation Lookaside Buffer）

  • 两次访存问题：查页表（1 次）+ 取数据（1 次），共 2 次内存访问
  • TLB：一组高速联想寄存器，存放近期访问的页表项，容量有限（通常 8~12 项）
  • 利用程序局部性提高命中率
  • 命中率计算实例（一次访存 750ns，查 TLB 50ns）：
    • 命中率 80%：平均访问时间 = 80% × (50+750) + 20% × (50+750+750) = 950ns
    • 无 TLB：2 × 750 = 1500ns
  • 进程切换时，TLB 需刷新并装入新进程的页表项

空闲页帧管理：Bitmap（位图）

  • 每个物理页帧对应位图中的一位（0 = 空闲，1 = 占用）
  • 相比链表极大节约存储空间
  • 计算实例：256MB 内存 / 4KB 页大小 = 65536 页帧 → 65536 bit = 8192 字节

共享与保护

  • 共享：不同进程的页表项指向同一物理页帧（如多进程执行同一程序，共享代码段）
  • 保护：
    • 页表长度寄存器：检查逻辑页号是否越界
    • 权限位：页表项中增加访问权限字段（只读/读写/执行）

优缺点

  • 优点：无外部碎片，物理内存不要求连续，内存利用率高
  • 缺点：页表占用额外空间，页内可能有少量内部碎片（平均半页），需一次性装入全部逻辑页，对用户不自然（与程序逻辑结构无关）

相关概念

指向原始笔记的链接

段式存储管理

段式存储管理

基本思想

  • 按程序的逻辑结构划分为若干段（Segment）
  • 每段有独立的名称和长度（主程序段、数据段、堆栈段等）
  • 每段独立编址（从 0 开始），段长可变
  • 物理内存采用可变分区管理
  • 通过段表实现段到物理内存的映射

重点 段表

  • 每个进程一张段表
  • 包含：段号、段基址、段长度、状态位等
  • 段号由数组下标自然表示
  • PCB 中有指针指向段表

地址转换

  • 二维逻辑地址：段号（S）+ 段内偏移（D）
  • 转换过程：
    1. 查段号 S 是否超过段表长度寄存器（越界保护）
    2. 查段表获取该段物理起始地址
    3. 检查段内偏移 D 是否越界（D < 段长度）
    4. 物理地址 = 基址 + 段内偏移（加法拼接，区别于页式的位拼接）

共享与保护

  • 共享：不同进程段表的段表项指向同一物理起始地址（共享代码段、共享库）
  • 保护：每段可独立设置访问权限（只读代码段、可读写数据段）

优缺点

  • 优点：对用户自然（按逻辑划分），便于共享和保护，无内部碎片
  • 缺点：外部碎片（需内存紧致 Complex），内存分配复杂，编程需在汇编中加段号

重点 页式 vs 段式

方面页式段式
划分依据固定大小（系统决定）逻辑结构（用户/程序员）
地址结构一维线性二维（段号 + 偏移）
段/页大小固定（2^k）可变
表页表（较长）段表（较短）
物理地址形成帧号|偏移（位拼接）基址 + 偏移（加法）
对用户不自然自然
碎片内部碎片（平均半页）外部碎片
共享保护困难容易
内存扩充不支持不支持
指向原始笔记的链接

段页式存储管理

段页式存储管理

基本思想

  • 结合 段式存储管理 和 页式存储管理
  • 按段划分逻辑结构（段式思想）—— 用户视角自然
  • 每段内再分页（页式思想）—— 内存管理高效
  • 内存按页帧分配，无外部碎片

地址转换

  • 逻辑地址 = 段号 + 段内页号 + 页内偏移
  • 转换过程：段表 → 页表 → 物理地址
    • 先查段表（得页表始址），对段内偏移做越界检查
    • 再查页表（得物理页帧号）
    • 最后拼接页内偏移 → 物理地址
  • 三次访存：段表访存 + 页表访存 + 取数据
  • 可配合 TLB 降低等效访问时间

结构

逻辑地址: | 段号 | 页号 | 页内偏移 |
            ↓
          段表  →  页表  →  物理页帧

优缺点

  • 优点：兼具段的逻辑性（用户视角自然、便于共享保护）和页的高效利用（无外部碎片、离散存储）
  • 缺点：地址转换复杂（三级查表），需要更多硬件支持

相关概念

指向原始笔记的链接

虚拟内存管理

虚拟内存管理

定义

  • 虚拟存储器：将主存和辅存统一管理，给用户提供比实际内存大得多的地址空间
  • 程序运行时只将当前需要的部分装入内存，其余在辅存
  • 虚拟空间大小由地址宽度决定（32 位→4GB，64 位→16EB）
  • 以时间换空间：利用外存扩展内存逻辑容量

理论基础：局部性原理（Locality Principle）

  • 时间局部性：刚被访问的数据近期很可能再次被访问（如循环体）
  • 空间局部性：刚被访问的数据附近的地址很可能被访问（如数组遍历）
  • 程序执行时有热点区域（循环、子程序调用），一段时间内仅访问少数页
  • 基于此，无需一次性装入全部程序

实现方式

虚拟页式存储的页表结构

较普通页表更复杂，页表项包含：

字段说明
合法位（Valid）1=在内存，0=在外存
修改位（Modified）是否被修改（决定淘汰时是否回写）
页类型零页/swap 区/文件映射（决定缺页处理方式）
保护码读写执行权限
外存块号页在外存的位置
物理页帧号在内存时的页帧号

Swap 分区（交换区）

  • 硬盘上专门划分的交换区空间
  • 代码页：从程序文件读入（只读，无需回写）
  • 数据页：运行中可能修改，需回写到 swap 区
  • 零页（未初始化数据）：在内存中直接清零，不从外存读

重点 缺页中断处理流程

  1. CPU 发出逻辑地址，MMU 查页表
  2. 合法位 = 0（页不在内存）→ 产生缺页中断（硬件 trap）
  3. 进入缺页中断处理子程序
  4. 申请空闲页帧：
  5. 检查页类型：
    • 零页 → 物理页帧清零
    • 非零页 → 从外存读入数据到页帧
  6. 填写页表项（页帧号、合法位置 1）
  7. 恢复执行访存指令

页淘汰流程

  1. 检查淘汰页的修改位：
    • 未修改 → 合法位清零，页帧回收（无需 I/O）
    • 已修改 → 需回写到外存（分配 swap 空间，调用 I/O 子系统）
  2. 页帧回收，更新页表项（合法位清零，更新外存块号）

关键问题

  • 调入策略：何时调入（请求调页 vs 预调页）、调入多少
  • 放置策略：放在内存何处
  • 置换策略：内存满时选择哪个页/段调出 → 见 页面置换策略

重点 虚存访问过程

  1. CPU 发出逻辑地址
  2. MMU 查询页表
  3. 页在内存中 → 形成物理地址访问
  4. 页不在内存中 → 缺页中断 → 从磁盘调入 → 更新页表 → 重新执行

抖动（Thrashing）

  • 定义：页面频繁在内存和外存间调入调出，系统效率急剧下降
  • 原因：置换算法不合理 / 驻留集太小（工作集 > 物理内存）
  • 解决：动态调整进程驻留集大小（工作集模型、缺页频率控制 PFF）

相关概念

指向原始笔记的链接

页面置换策略

页面置换策略

评价标准

  • 缺页发生频率少，防止系统发生抖动（Thrashing）
  • 算法本身的复杂度小

驻留集（Resident Set）

  • 进程当前在内存中的物理页帧集合
  • 固定驻留集 + 局部置换：每个进程分配固定页帧数，只在本进程内置换
  • 可变驻留集 + 全局置换：动态调整驻留集大小，系统范围内置换

重点 固定驻留集算法

FIFO（先进先出）

  • 淘汰最早进入内存的页面（队列实现：队首淘汰，队尾插入）
  • 实现简单，无需额外硬件支持，但效果差
  • Belady 异常：分配更多页帧反而缺页更多
  • 演算示例（访问串 7,0,1,2,0,3,0,4,2,3,0,3,2，驻留集=3）：
    • 7→0→1 依次入内存；访问 2 时缺页，淘汰最早进入的 7
    • 访问 3 时缺页，淘汰当前最早的 0 … 依次类推

OPT（最佳置换）

  • 淘汰未来最长时间内不再访问的页面（或永不访问的页面）
  • 理论上缺页中断次数最少
  • 不可实现（未来访问串未知）
  • 价值：作为理论参照标准（性能下界标尺）

重点 LRU（最近最久未使用）

  • 淘汰过去最长时间未被访问的页面（” 往后看未知，往前看已知 ”）
  • 栈式算法：驻留集大小为 M 时的页帧集合 ⊆ 驻留集为 M+1 时的页帧集合
  • 无 Belady 异常（栈式算法可证明，驻留集增大时缺页次数一定不增）
  • 实现：每页帧配计数器，访问时清零、其余加一，淘汰计数值最大的页
  • 性能好，但实现代价高（需额外硬件支持）

Clock（时钟算法 / 第二次机会）

  • 物理页帧组成循环链表（钟面），指针（钟针）在其中旋转
  • 页表增加访问位，循环检查：
    • 访问位 = 1 → 置 0，指针下移（给第二次机会）
    • 访问位 = 0 → 淘汰
  • 若全部访问位均为 1，转一圈后全部变 0，回到原点淘汰
  • 性能接近 LRU，实现简单（仅需一位访问位）

NRU（最近未使用算法）

  • 结合 FIFO 和 LRU 思想：页表项增加使用位，定时清零
  • 淘汰优先级（同时考虑使用位和修改位）：
    1. 使用位=0，修改位=0（最优先，无需回写外存）
    2. 使用位=0，修改位=1（需回写）
    3. 使用位=1，修改位=0
    4. 使用位=1，修改位=1（最后）
  • 优先淘汰修改位=0 的页面：避免回写开销

动态驻留集算法

程序形态

  • 局部性形态：程序在一段时间内工作于某个局部热点（工作集）
  • 阶段转换形态：执行热点从工作集 A 跳转到工作集 B

工作集模型（Working Set, WS）

  • 设置 δ 间隔（delta window），每经过 δ 次页面访问，淘汰在该间隔内未被访问的页面
  • 驻留集大小随工作集动态变化
  • 实现：每页配计数器，访问时清零、其余加一；淘汰计数器值 = δ 的页
  • 开销大（每页一个计数器）

SWS（Sampled Working Set）

  • 改进 WS：页表项中记录当前时间戳（访问时写入时钟值）
  • 操作系统定时检查：当前时钟值 - 页表项时间戳 > δ → 淘汰
  • 无需额外计数器，硬件消耗仍较大

实用 OS 策略：SWS + 延迟清除

  • 自由列表（Free List）：修改位=0，页面内容无需回写
  • 修改列表（Modified List）：修改位=1，待回写
  • 修改链过长或自由链过短时，将修改链页面回写外存后移至自由链
  • 缺页中断时，从自由链直接分配物理页帧（数据可覆盖）
  • 关键优化：若自由链/修改链中的页面被再次访问，只需将合法位置 1，无需从外存重新加载

缺页频率控制（PFF）

  • 动态调整进程的驻留集大小，防止抖动
  • 驻留集 < 工作集 → 频繁抖动
  • 驻留集 >> 工作集 → 内存浪费

多级页表

  • 为什么需要：32 位系统，页大小 4K（2¹²），页表项 4B → 页表需 2²² = 4MB 连续物理空间。页表本身也可分页存储，避免大块连续分配
  • 二级页表结构（10+10+12）：
    • 页内偏移：12 位
    • 二级页号（内层页表）：10 位
    • 页目录号（一级页表）：10 位
  • 地址转换：先查页目录 → 获二级页表地址 → 查二级页表 → 获物理帧号 → 拼接偏移
  • 计算示例：逻辑地址空间 2¹⁶ 个页（64MB），页大小 1K（10 位偏移），页表项 2B：
    • 每页可存放页表项数：1K / 2B = 2⁹ = 512 项（9 位索引）
    • 页目录号位数：26 - 10 - 9 = 7 位 → 128 项
  • 64 位系统使用哈希页表（逻辑页号作哈希值，链表解决冲突）

最佳页面大小推导

假设进程平均大小 S 字节，页面大小 P 字节，页表项 1B：

  • 页表开销：S/P
  • 内部碎片：P/2（每页平均浪费半页）
  • 总开销：C(P) = S/P + P/2
  • 求导得最优：P = sqrt(2S)
  • 实际系统据此选择页大小（如 4K）

比较

算法性能实现开销Belady 异常类别
OPT最优（理论）不可实现—局部
LRU好高无（栈式算法）局部
Clock较好低—局部
NRU较好低—局部
FIFO一般最低有局部
WS好高—全局
SWS好较高—全局
指向原始笔记的链接

Linux 内存管理

Linux内存管理

物理内存分区（32 位）

Linux 将物理内存分为三个 Zone：

Zone范围用途
ZONE_DMA<16MBDMA 方式数据缓冲
ZONE_NORMAL16MB~896MB内核虚拟地址映射（系统空间）
ZONE_HIGHMEM>896MB用户空间（进程映像）

分配优先级：首选 HIGHMEM → 满时用 NORMAL → DMA 专用

重点 伙伴系统（Buddy System）

  • 基于 2 的幂次分配内存块（1, 2, 4, 8, 16 页…）
  • 分配：将大块拆分为两个 ” 伙伴 “，从大到小剖分
  • 回收：相邻伙伴合并为更大块，逐级向上合并
  • 伙伴定义：大小相同 + 物理地址连续 + 第一个页帧编号为 2 的倍数

分配示例（16 页初始 → 分配 2 页）：

  1. 初始：空闲链表仅 16 页块 [0-15]
  2. 请求 2 页 → 剖分 16→[0-7]+[8-15]，[8-15] 入 8 页链表
  3. [0-7] 剖分 → [0-3]+[4-7]，[4-7] 入 4 页链表
  4. [0-3] 剖分 → [0-1]+[2-3]，[0-1] 分配出去，[2-3] 入 2 页链表

回收：释放 [0-1] → 检查伙伴 [2-3] 是否空闲 → 合并为 [0-3] → 继续向上合并。

优点：保留大的连续空间，分配的内存尽量连续（提高 TLB 命中率），减少外部碎片。

Slab 分配器

  • 在伙伴系统之上用于小对象分配（Buddy 以页为单位，4K 以下会造成内部碎片）
  • 为常用的小对象预分配缓存（Cache），将多个同类型小对象打包成一个大的页面
  • 充当 Buddy 与内核之间的中间代理
  • 每种对象类型有自己的 Slab 缓存（如 int cache、inode cache 等）
  • 通用预分配大小：32B、64B、128B、4K、128K 等
  • 优点：减小内部碎片，管理局部化，减少与 Buddy 系统的直接交互
  • 相关系统调用：kmem_cache_create、kmalloc、kfree

进程虚拟地址空间（32 位）

+------------------+ 0xFFFFFFFF (4G-1)
|    内核空间      |
+------------------+ 0xC0000000 (3G)
|    用户空间      |
+------------------+ 0x00000000
  • 用户虚空间通过页表映射到物理内存
  • 内核空间通常对应固定物理内存区域

重点 两级页表（32 位 Linux）

32 位 Linux 虚拟地址：页目录 (10 位) + 页表项 (10 位) + 页内偏移 (12 位=4K)

线性地址 → 物理地址转换：

  1. CR3 寄存器指向进程的页目录
  2. 逻辑地址高 10 位索引页目录 → 获取页表
  3. 中间 10 位索引页表 → 获取物理页帧号
  4. 低 12 位页内偏移拼接 → 物理地址

页表项标志位：存在位、读写位、访问位、脏位

关键数据结构

mm_struct

  • 每个进程的 task_struct 中包含指向 mm_struct 的指针
  • 描述进程的完整内存映像：
    • 指向页目录的指针（PGD）
    • 指向 vm_area_struct 链表的指针
    • 代码段/数据段/堆/栈的地址范围等

vm_area_struct

  • 描述进程虚拟地址空间中的一个连续区域（如代码段、堆、栈、mmap 区域等）
  • 组织成链表/红黑树

mem_map[]

  • 数组大小为页帧数
  • 页描述符：管理每个物理页的状态

Copy-on-Write（写时拷贝，COW）

  • fork() 创建子进程时，父进程与子进程共享同一物理页面（页表项指向相同页帧，标记为只读），不立即复制
  • 写触发：子进程或父进程要写入共享页面时 → 触发缺页异常 → OS 分配新物理页帧 → 复制原内容 → 修改页表为可写 → 分别映射各自的副本
  • 优点（Lazy 策略）：
    • 避免一次性拷贝所有数据，开销分散
    • 只被写入的页面才真正复制，共享页面保留
    • 提高进程创建效率
  • 缺页异常处理：do_page_fault 函数 → 判断地址是否在有效区域 → 区分写缺失/页不在内存 → 执行对应处理

用户态与核心态系统调用

  • brk — 改变堆大小
  • exit — 结束进程，释放空间
  • mmap / munmap — 映射/取消映射文件或匿名内存
  • shmget — 创建共享存储区
指向原始笔记的链接

重点 页式 vs 段式对比

参考 重点 页式 vs 段式

重点 页面置换算法对比

参考 比较

关系图谱

反向链接