操作系统内存管理

一、内存管理策略

1. 背景

基本硬件（基地址与界限地址）

地址绑定（编译时、加载时、运行时）

逻辑地址空间与物理地址空间

动态加载

动态链接与共享库（与静态库对比）

2. 交换（内存与磁盘间）

维护着一个可运行进程就绪队列，进行内存与磁盘间线程的载入与存出。

3. 连续内存分配

内存分区之 可变分区 的思想，将内存分成一个个孔（hole），使用一张表维护 hole 的使用情况。

存在碎片问题（分为外碎片与内碎片）

• 首次适应– 首个足够大的孔（50% 规则，描述碎片多）
• 最优适应– 最小合适的孔
• 最差适应– 最大孔

外部碎片大，解决思路有 紧缩 与 分页、分段（运行物理地址不连续的策略）

4. 分段

将内存分为不同长度的段，维护分段硬件支持段表

< 段名称 s，段偏移 d >

5. 分页

物理内存分为固定大小的块，称为帧。逻辑内存也分为同样大小的块，称为页。

< 页码 p，页偏移 > 与对应的页表

TLB 带 Hash 页表 – 转换表缓冲区

保护机制与共享页

6. 页表结构补充

分层页表

哈希页表（数组 + 链表）

倒置页表

二、虚拟内存管理

1. 背景

使用虚拟内存来逻辑内存容量 – 分配出去但未使用的内存空间，通过伪分配实现扩容。

2. 请求调页

概念：仅在需要时，才加载页面。

调页程序 – 惰性变换器实现

一般缺页错误的处理很简单：

1. 检查这个进程的内部表，以确认该引用是有效的还是无效的内存访问。
2. 如果引用无效，那么终止进程。如果引用有效但是没有调入内存，那么现在就调入。
3. 找到一个空闲帧。
4. 调度一个磁盘操作，以将所需页面读到刚分配的帧。
5. 磁盘读取完成，修改进程内部表和页表。以指示该页现在处于内存中。
6. 重新启动被陷入中断的指令。该进程能访问所需要的页面，就好像原来他就在内存中一样。

缺页处理的时间花费主要体现在：处理缺页中断、读入页面、重新启动进程

3. 写时复制（父子进程间）

4. 页面置换

​ 当用户进程在执行时，可能发生缺页错误。操作系统确定所需要页面的磁盘位置，但是却发现内存上没有空闲的帧。所有内存都在使用。此时，它会选择交换出一个进程，以释放它在所有帧并降低多道程序。

​ 在没有空闲帧的情况下，那么就要查找当前不在使用的一个帧，并释放它，牺牲帧 ，他被换出到交换空间，并修改它的页表。可以看到当没有空闲帧的情况下，需要两个页面传输（一个传入，一个传出）。这种情况世界加倍了缺页错误处理时间，并增加了有效的访问时间。为了减少置换的时间，系统提供了一个 修改位，两者的关联采用硬件。每当一个页面内的任何字节被写入时，它的页面修改位会由硬件来设置，以表示该页面被修改过。当要选择一个页面置换时，它会先看这个页面或者帧有没有被修改过，如果没有修改过就不用将它换出，直接进行换入，将它的空间覆盖。

页面置换算法

• FIFO 先进先出
• OPT/MIN 最优置换
• LRU 最近最少使用

• 近似 LRU

  1. 额外引用位算法（多位标志位）
  2. 第二次机会算法（1 位标志位）
  3. 增强型第二次机会算法 - 分类（元组分类出最近使用与需要写回）

• 基于计数

  1. LFU 最不经常使用
  2. MFU 最经常使用

     搭配上 页面缓冲算法– 最近被淘汰的页面被放置在高速磁盘区，减少淘汰错误页面下次换回的代价

5. 帧分配

分配算法 –平均与比例

全局分配与局部分配（区别，是否面向所有进程的内存暑假页）

6. 系统抖动

频繁发生页面置换

7. 内存映射文件与 IO