1. 内存管理的发展历程
无内存管理（单道程序） → 静态分区 → 动态分区 →
分页 → 分段 → 段页式 → 虚拟内存
2. 连续分配方式
2.1 固定分区 vs 动态分区
| 方式 | 原理 | 问题 |
|---|---|---|
| 固定分区 | 内存分成等大/不等大的固定区域 | 内部碎片，利用率低 |
| 动态分区 | 按需求分配连续内存块 | 外部碎片，需紧凑整理 |
2.2 动态分区的分配算法
首次适应（First Fit）：从头找第一个足够大的空闲块
优点：速度快
缺点：低地址碎片多
最佳适应（Best Fit）：找最小的足够大的空闲块
优点：减少浪费
缺点：产生大量小碎片
最坏适应（Worst Fit）：找最大的空闲块
优点：碎片较大可利用
缺点：大进程无法分配
下次适应（Next Fit）：从上次分配位置继续搜索
优点：分布更均匀
缺点：尾部碎片可能累积
3. 分页（Paging）
3.1 基本思想
将物理内存和逻辑内存划分为固定大小的页框（Page Frame）和页面（Page），大小通常为 4KB。
逻辑地址 → [页号 (p) | 页内偏移 (d)]
↓
页表查询
↓
物理地址 → [页框号 | 页内偏移]
3.2 页表结构
页表项（PTE）:
┌─────────┬─────┬─────┬─────┬─────┬─────┬──────┐
│ 页框号 │ 存在位│ 修改位│引用位│保护位│缓存位│ 脏位 │
└─────────┴─────┴─────┴─────┴─────┴─────┴──────┘
存在位（Present）: 页面是否在内存中
修改位（Dirty）: 页面是否被写过
引用位（Accessed）: 页面是否被访问过（用于 LRU 近似）
保护位（Protection）: 读/写/执行权限
3.3 多级页表
32 位系统单级页表的问题：4GB / 4KB = 1M 个页表项 × 4B = 4MB 页表。
二级页表（32位，4KB页）：
逻辑地址 = [ 目录索引(10) | 页表索引(10) | 偏移(12) ]
↓ ↓
页目录表(PDE) 页表(PTE)
│ │
└────→ 页框号 + 偏移 = 物理地址
// x86 二级页表地址转换示意
uint32_t translate(uint32_t logical_addr, uint32_t *page_directory) {
uint32_t dir_idx = (logical_addr >> 22) & 0x3FF;
uint32_t table_idx = (logical_addr >> 12) & 0x3FF;
uint32_t offset = logical_addr & 0xFFF;
uint32_t pde = page_directory[dir_idx];
uint32_t *page_table = (uint32_t*)(pde & 0xFFFFF000);
uint32_t pte = page_table[table_idx];
uint32_t frame = pte & 0xFFFFF000;
return frame | offset;
}
4. 分段（Segmentation）
4.1 基本思想
按程序逻辑结构划分段：代码段、数据段、栈段、堆段。
逻辑地址 → [段号 (s) | 段内偏移 (d)]
↓
段表查询（段基址 + 段限长）
↓
段基址 + 偏移 = 物理地址
↓
段限长检查（越界保护）
4.2 段页式管理
结合两者优点：
逻辑地址 → [段号 | 页号 | 页内偏移]
↓
段表 → 页表基址
↓
页表 → 页框号
↓
页框号 + 偏移 = 物理地址
Linux 实际采用页式管理为主，x86-64 架构使用四级/五级页表。
5. 虚拟内存（Virtual Memory）
5.1 核心思想
每个进程拥有独立的虚拟地址空间（如 64 位 Linux 的用户空间 128TB），物理内存只存放活跃页面，不活跃的页面换出到磁盘（交换空间/Swap）。
进程虚拟地址空间（128TB）：
高地址 → ┌──────────────────┐
│ 栈（向下增长） │
│ （映射到物理页） │
├──────────────────┤
│ 内存映射区 │ ← mmap 区域
│ （按需分配） │
├──────────────────┤
│ 堆（向上增长） │
├──────────────────┤
│ BSS / 数据段 │
│ 代码段 │
低地址 → └──────────────────┘
↑
未分配区域 → 不占物理内存
↑
已分配但未被访问 → 分配页表但无物理页
↑
已访问 → 页表指向物理页框
5.2 页错误（Page Fault）
1. 合法访问，页面不在内存 → 请求调页（Demand Paging）
→ 从磁盘加载页面 → 继续执行
2. 合法访问，页面在 Swap
→ 从交换区读入 → 更新页表 → 继续执行
3. 非法访问（越界/权限不足）
→ 触发段错误（Segmentation Fault）→ 进程终止
6. 页面置换算法
6.1 最优置换（OPT）
置换未来最久不被访问的页面。
理论最优但不可实现（需要预知未来），用于评估其他算法。
6.2 FIFO（先进先出）
from collections import deque
def fifo(pages, capacity):
"""Belady 异常：增加页框数可能缺页更多"""
memory = deque(maxlen=capacity)
faults = 0
for page in pages:
if page not in memory:
faults += 1
memory.append(page)
return faults
6.3 LRU（最近最少使用）
def lru(pages, capacity):
"""最近最少使用，性能接近 OPT"""
from collections import OrderedDict
memory = OrderedDict()
faults = 0
for page in pages:
if page in memory:
memory.move_to_end(page)
else:
faults += 1
if len(memory) >= capacity:
memory.popitem(last=False)
memory[page] = True
return faults
LRU 实现方式：哈希表 + 双向链表（O(1)）或计数器法。
6.4 Clock（时钟/第二次机会）算法
def clock_algorithm(pages, capacity):
"""
环形链表 + 引用位
每个页面有一个引用位 R
指针遍历：R=1 则清 0 并跳过；R=0 则置换
"""
clock = [None] * capacity # [(page, R), ...]
hand = 0
faults = 0
for page in pages:
# 检查是否已在内存中
found = False
for i, entry in enumerate(clock):
if entry and entry[0] == page:
clock[i] = (page, 1)
found = True
break
if found:
continue
# 需要置换
faults += 1
while True:
if clock[hand] is None or clock[hand][1] == 0:
clock[hand] = (page, 1)
hand = (hand + 1) % capacity
break
else:
clock[hand] = (clock[hand][0], 0)
hand = (hand + 1) % capacity
return faults
6.5 算法对比
| 算法 | 缺页率 | 实现复杂度 | 特点 |
|---|---|---|---|
| OPT | 最优 | — | 理论基准 |
| FIFO | 较差 | O(1) | 可能 Belady 异常 |
| LRU | 接近最优 | O(1) | 需要维护访问顺序 |
| Clock | 接近 LRU | O(1) | 近似 LRU，开销更小 |
| LFU | 视访问模式 | O(log n) | 保留频繁访问页面 |
7. Linux 内存查看与调优
# 查看内存使用情况
free -h
# 查看进程内存
cat /proc/[pid]/status | grep VmRSS
cat /proc/[pid]/maps # 完整地址空间映射
# Swap 使用情况
swapon -s
cat /proc/swaps
# 调整 Swappiness（0-100，越大越倾向用 Swap）
cat /proc/sys/vm/swappiness
sudo sysctl vm.swappiness=10
# 查看缺页统计
ps -o min_flt,maj_flt -p [pid]
# min_flt: 轻微缺页（无需磁盘 I/O）
# maj_flt: 严重缺页（需要磁盘 I/O）
# 清除页缓存（谨慎使用）
sync; echo 3 | sudo tee /proc/sys/vm/drop_caches
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。