连续存储器管理方式

固定分区方式（Fixed Partitioning）

固定分区方式是最早的内存管理方法之一。其核心思想是：

在系统启动时将内存划分为若干大小固定的分区，每个分区只装入一个作业。

特点

  • 实现简单：系统只需管理少量固定的分区表。
  • 分区大小固定：分区大小在系统启动时确定，运行时不能改变。

缺点

  1. 内部碎片（Internal Fragmentation）严重：

    进程大小小于分区大小 → 分区剩余空间无法利用。

  2. 灵活性差：不同作业大小不匹配时，可能导致大作业无法进入系统。

  3. 分区数量有限：可能造成 多道程序并发度低。

可变分区方式（Variable Partitioning）

可变分区方式按需分配内存：

每次装入作业时，根据作业大小动态划分分区，不预先固定分区数量与大小。

特点

  • 无内部碎片：分区大小和作业匹配。
  • 存在外部碎片（External Fragmentation）：随着进程装入与退出，不连续的空闲空间逐渐增多。
  • 可通过 内存紧凑（Compaction） 解决外部碎片，但代价高，需要移动进程。

可变分区分配算法

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

思想：从空闲区链表 头开始 查找，遇到第一个能满足作业大小的空闲块就分配。

优点：简单高效，查找速度快。空闲区链表通常按地址升序排列，易于维护。

缺点：低地址端容易变得零碎，产生大量小外部碎片。

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

思想：扫描所有空闲区，选择 大小最接近、但又能容纳作业 的分区进行分配。

优点：最大程度利用空间，减少大空闲块被切碎的可能性。

缺点：查找整个空闲区列表，开销大。容易产生 大量非常小的外部碎片，长期效果并不好。

3. 最坏适应算法（Worst Fit）

思想：选择 最大的空闲区 分配。

优点：避免产生很多小碎片，留下较大的剩余空间。

缺点：常常把最大内存块切得过碎，使内存缺乏大块空间。

回收算法

将被释放的分区插入空闲区链表中，并与相邻空闲区进行必要的合并。

假设释放区为 R，空闲区按地址升序排列。

需要检查四种情况：

  1. R 的前后都没有空闲区相邻

    → 单独作为一个新的空闲块插入链表。

  2. R 与前一个空闲区相邻（前合并）

    → 合并成一个更大的空闲块。

  3. R 与后一个空闲区相邻（后合并）

    → 合并成一个更大的空闲块。

  4. R 同时与前后两个空闲区相邻（前后合并）

    → 三者合并成一个大空闲块。

页式存储管理方式

基本思想

将 进程的逻辑地址空间 分成固定大小的 页（Page），将 物理内存 划分成大小相同的 页帧（Frame）。

进程运行时，将其页装入任意空闲页帧中，由 页表（Page Table） 实现逻辑地址到物理地址的转换。

特点

将外部碎片转化为内部碎片，允许 非连续分配，利于多道程序提高内存利用率

地址结构

逻辑地址通常分为两部分：

| 页号 (p) | 页内偏移 (d) |

地址转换过程：

物理地址 = 页表[p] + d

支持机制

  • 页表（Page Table）：程序内的逻辑页号通过页表得以得到实际物理地址进行读取。
  • 快表 TLB（Translation Lookaside Buffer）：增加页表的小型高速缓存，命中就直接用，不命中就读页表（页表的访问会明显慢于快表，但是页表的容量可以明显大于快表）
  • 多级页表：解决单级页表过大的问题，

分段存储管理方式

基本思想

依据 程序的逻辑结构（代码段、数据段、栈段），将进程划分为多个 长度不等的段（Segment），使用 段表（Segment Table） 做逻辑地址到物理地址的映射。

特点

  • 分段根据逻辑结构划分，长度不固定
  • 程序员可见，易于实现 共享、保护
  • 不存在内部碎片
  • 存在外部碎片（段大小可变）

地址结构

逻辑地址由两部分组成：

| 段号 (s) | 段内偏移 (d) |

地址转换：

物理地址 = 段表[s].base + d

段表项内容：

base：段的起始物理地址
limit：段长，用于越界检查

段式管理天然支持越界保护（检查 d < limit）。

段页式存储管理方式

基本思想

结合 段式的逻辑性 和 页式的物理管理优势：

  1. 先按逻辑结构划分为段
  2. 每段内部再分页
  3. 每段都有自己的 页表

地址结构

逻辑地址由三部分组成：

| 段号 (s) | 页号 (p) | 页内偏移 (d) |

地址转换过程：

段表[s] 得到段的页表基地址
段内页表[p] 得到物理页帧号
物理地址 = 页帧号 + d

特点

  • 结合两种方式优势
    • 分段：逻辑清晰、易于共享与保护
    • 分页：无外部碎片、支持离散分配
  • 段间独立，段内分页，使得段大小灵活，不受页大小限制
  • 地址转换开销较大
    • 可使用 TLB + 段表缓存加速

虚拟存储系统

用页表机制把部分不在内存的数据暂存在磁盘，并在需要时自动加载，使得外部存储能作为内存的补充。

抖动（系统颠簸）：频繁将页面换出换入（加载卸载），导致执行受到严重影响

页面置换算法

内存的大小是有限的，使用磁盘去拓展，当反复访问同一个页面时，将页面存储到内存之后反复读取，会比反复从磁盘中加载快很多。

可以理解为：主存作为CPU交互外存的缓存，访问一个页面时先查看是否在主存中缓存，如果没有再读取外存。

页面置换有以下概念：

  • 缺页：访问的页面不在内存中，需要从磁盘加载
  • 淘汰：选择某个已在内存的页面替换出去

主存通常都只有一定的大小，需要找到一个算法能让淘汰合理运行，使得缺页的次数越少越好。

理论最优：最佳置换算法（OPT）（*）

最佳置换算法的前提是：操作系统提前知道将来所有页面的访问序列。

因此最佳置换算法一般无法用于系统设计，通常用于比较其他置换算法的性能如何，作为参考答案的最优解。

工作原理

当发生缺页中断，需要淘汰某个页面时，选择将来最长时间内不会被访问的页面进行替换。

淘汰行为

（拥有访问序列LIST）

  • 当需要淘汰一个页面时，对主存里的每个页面都进行检查起下次在未来访问序列中的位置。
  • 谁的位置最靠后，就淘汰谁。

先入先出置换算法（FIFO）

工作原理

FIFO 是最简单的页面置换算法之一，当发生缺页中断且内存已满时，淘汰最早进入内存的页面

淘汰行为

系统通过一个队列维护页面进入内存的顺序：

  • 页面进入内存时加入队尾。
  • 内存满时，从队头取出页面进行淘汰。

Least Recently Used 算法 (LRU)

工作原理

LRU 根据 页面最近访问时间 来判断淘汰对象。每次页面被访问时，更新其最近使用时间或移动到链表/栈顶。当发生缺页且内存满时，淘汰 最久未被访问的页面。

淘汰行为

  • 系统维护一个访问顺序或时间戳（栈或链表）。
  • 内存满时，从末尾或时间最早的页面中选择淘汰。

优点：比 FIFO 更符合实际访问规律，缺页率通常更低。

缺点：实现稍复杂，需要维护访问记录。

Least Frequently Used 算法（LFU）

工作原理

LFU 根据 页面被访问的次数 来判断淘汰对象。每次页面被访问时，对其访问计数器加 1。当发生缺页且内存满时，淘汰 访问次数最少的页面。

淘汰行为

  • 系统为每个页面维护访问计数。
  • 内存满时，选择计数最小的页面进行淘汰。

优点：对经常访问的页面友好。

缺点：长期不再访问的老页面可能长期占用内存，需要额外机制（如计数衰减）。

时钟置换算法（CLOCK）

工作原理

CLOCK 是对 FIFO 的改进，模拟一个 循环队列/时钟。每个页面有一个 使用位（use bit），表示是否被访问过。页面访问时，将使用位置为 1。

淘汰行为

  • 内存满时，指针顺时针扫描页面。
  • 遇到 使用位为 0 的页面，将其淘汰。
  • 遇到 使用位为 1 的页面，将其清零并继续扫描下一个页面。

优点：实现简单，近似 LRU 的性能，开销比 LRU 小。

改进的 CLOCK 算法（Enhanced CLOCK / 二次机会）

背景

  • 普通 CLOCK 只使用 使用位（use bit），不能区分页面是否被修改。
  • 如果淘汰一个脏页（被修改过的页面），需要先写回磁盘，开销大。
  • 改进算法同时考虑 使用位和修改位，减少磁盘写入次数。

工作原理

  • 每个页面有两个标志位：
    1. 使用位（U bit / R bit）：表示页面最近是否被访问过。
    2. 修改位（M bit / dirty bit）：表示页面内容是否被修改。
  • 优先淘汰既 不常用又干净 的页面。

淘汰行为

  • 当需要淘汰页面时，按以下顺序扫描（优先级低到高淘汰）：
    1. U=0, M=0 → 未被使用且未修改，直接淘汰（最佳选择）。
    2. U=0, M=1 → 未被使用但已修改，淘汰前写回磁盘。
    3. U=1, M=0 → 最近被访问过但未修改，将 U 清零，给它“二次机会”。
    4. U=1, M=1 → 最近被访问过且已修改，将 U 清零，继续扫描。
  • 指针顺时针移动，直到找到符合淘汰条件的页面。