内存管理
💡 核心结论
虚拟内存是现代操作系统的基石，提供进程隔离和内存抽象
分页比分段更灵活，段页式结合两者优点
多级页表减少内存占用，TLB加速地址转换
LRU是最优页面置换算法的近似，Clock算法是LRU的高效实现
写时复制(COW)是fork和内存优化的关键技术
1. 内存层次结构
寄存器 <1ns KB级 最快
L1缓存 ~1ns 32-64KB
L2缓存 ~4ns 256KB-1MB
L3缓存 ~10ns 8-32MB
内存 ~100ns GB级
SSD ~10μs TB级
HDD ~10ms TB级 最慢
局部性原理：
时间局部性：最近访问的数据很可能再次访问
空间局部性：相邻地址的数据很可能被访问
2. 地址空间
2.1 物理地址 vs 虚拟地址
物理地址：实际内存地址
虚拟地址：程序使用的地址
进程A: 0x1000 ─┐
├─> 物理地址: 0x5000
进程B: 0x1000 ─┘ (映射到不同物理页)
虚拟地址的优势：
进程隔离（安全）
内存碎片整理（灵活）
程序重定位（简单）
共享内存（高效）
2.2 内存布局
// 典型的进程内存布局（32位）
0xFFFFFFFF ┌─────────────┐
│ 内核空间 │ 1GB
0xC0000000 ├─────────────┤
│ 栈 │ ↓ 向下增长
├─────────────┤
│ ↕ │
├─────────────┤
│ 堆 │ ↑ 向上增长
├─────────────┤
│ BSS段 │ 未初始化数据
├─────────────┤
│ 数据段 │ 已初始化数据
├─────────────┤
│ 代码段 │ 只读
0x08048000 ├─────────────┤
│ 保留区 │
0x00000000 └─────────────┘
查看进程内存布局：
#include <stdio.h>
int global_init = 10; // 数据段
int global_uninit; // BSS段
const int readonly = 5; // 代码段（只读）
int main() {
int stack_var = 20; // 栈
int *heap_var = malloc(sizeof(int)); // 堆
printf("代码段: %p\n", main);
printf("数据段: %p\n", &global_init);
printf("BSS段: %p\n", &global_uninit);
printf("堆: %p\n", heap_var);
printf("栈: %p\n", &stack_var);
return 0;
}
3. 分页机制
3.1 基本分页
原理：将虚拟地址空间和物理内存都分成固定大小的页
页大小：通常4KB
虚拟地址 = [页号 | 页内偏移]
例如（32位，4KB页）：
20位页号 + 12位偏移
支持：2^20 = 1M个页 = 4GB地址空间
地址转换：
struct page_table_entry {
unsigned int present : 1; // 在内存中
unsigned int writable : 1; // 可写
unsigned int user : 1; // 用户可访问
unsigned int accessed : 1; // 已访问
unsigned int dirty : 1; // 已修改
unsigned int reserved : 7;
unsigned int pfn : 20; // 物理页框号 (Page Frame Number)
};
// 地址转换函数
unsigned int translate(unsigned int virtual_addr) {
unsigned int page_num = virtual_addr >> 12; // 高20位
unsigned int offset = virtual_addr & 0xFFF; // 低12位
page_table_entry pte = page_table[page_num];
if (!pte.present) {
page_fault(); // 缺页中断
return 0;
}
unsigned int physical_addr = (pte.pfn << 12) | offset;
return physical_addr;
}
3.2 多级页表
问题：32位系统，4KB页，页表大小 = 2^20 * 4B = 4MB（每个进程！）
解决：多级页表
两级页表（32位）：
虚拟地址 = [10位一级页号 | 10位二级页号 | 12位偏移]
一级页表：1024项 = 4KB
二级页表：1024项 = 4KB（按需分配）
节省：只需一级页表 + 实际使用的二级页表
地址转换：
// 两级页表转换
unsigned int translate_2level(unsigned int va) {
unsigned int pde_index = (va >> 22) & 0x3FF; // 一级索引
unsigned int pte_index = (va >> 12) & 0x3FF; // 二级索引
unsigned int offset = va & 0xFFF; // 偏移
// 1. 查一级页表
pde_t pde = page_directory[pde_index];
if (!pde.present) {
page_fault();
return 0;
}
// 2. 查二级页表
pte_t *page_table = (pte_t*)pde.pt_base;
pte_t pte = page_table[pte_index];
if (!pte.present) {
page_fault();
return 0;
}
// 3. 组合物理地址
return (pte.pfn << 12) | offset;
}
Linux x86-64 四级页表：
PGD (Page Global Directory) -> 全局页目录
PUD (Page Upper Directory) -> 上层页目录
PMD (Page Middle Directory) -> 中间页目录
PTE (Page Table Entry) -> 页表项
虚拟地址（48位）：
[9位PGD | 9位PUD | 9位PMD | 9位PTE | 12位偏移]
3.3 TLB（Translation Lookaside Buffer）
问题：每次内存访问需要多次页表查询
解决：TLB缓存最近的地址转换
struct tlb_entry {
unsigned int vpn; // 虚拟页号
unsigned int pfn; // 物理页框号
bool valid;
};
tlb_entry tlb[TLB_SIZE];
unsigned int translate_with_tlb(unsigned int va) {
unsigned int vpn = va >> 12;
unsigned int offset = va & 0xFFF;
// 1. 查TLB
for (int i = 0; i < TLB_SIZE; i++) {
if (tlb[i].valid && tlb[i].vpn == vpn) {
// TLB命中
return (tlb[i].pfn << 12) | offset;
}
}
// 2. TLB未命中，查页表
unsigned int pfn = page_table_walk(vpn);
// 3. 更新TLB
tlb_insert(vpn, pfn);
return (pfn << 12) | offset;
}
TLB性能：
TLB大小：64-1024项
命中率：>95%
命中时间：~1ns
未命中时间：~100ns
TLB刷新：
进程切换时需要刷新TLB（开销大！）
解决：ASID（Address Space ID）标记进程
4. 分段机制
4.1 基本分段
原理：按逻辑单元（代码、数据、栈）分段
struct segment {
unsigned int base; // 段基址
unsigned int limit; // 段长度
unsigned char type; // 段类型（代码/数据）
unsigned char privilege; // 特权级
};
segment segment_table[MAX_SEGMENTS];
// 地址转换
unsigned int translate_segment(unsigned int seg, unsigned int offset) {
if (offset > segment_table[seg].limit) {
segmentation_fault();
return 0;
}
return segment_table[seg].base + offset;
}
优点：
符合程序逻辑结构
保护粒度灵活
共享方便
缺点：
外部碎片（不同大小的段）
段表管理复杂
4.2 段页式
结合分段和分页的优点：
虚拟地址 = [段号 | 页号 | 页内偏移]
1. 先用段号查段表，得到页表基址
2. 用页号查页表，得到物理页框号
3. 组合物理地址
Intel x86的段页式：
段选择子：13位索引 + 1位TI + 2位RPL
段描述符：基址 + 限长 + 属性
5. 页面置换算法
5.1 最优算法（OPT）
原理：替换未来最长时间不用的页（理论最优）
int opt_replace(int pages[], int n, int capacity) {
// 对每个页面，计算下次使用时间
int farthest = -1;
int victim = -1;
for (int i = 0; i < capacity; i++) {
int next_use = find_next_use(pages, n, frames[i]);
if (next_use > farthest) {
farthest = next_use;
victim = i;
}
}
return victim;
}
问题：无法预知未来，仅用于性能对比
5.2 先进先出（FIFO）
原理：替换最早进入的页
int fifo_replace() {
static int pointer = 0;
int victim = pointer;
pointer = (pointer + 1) % capacity;
return victim;
}
Belady异常：增加页框数反而增加缺页率！
页面引用序列：1 2 3 4 1 2 5 1 2 3 4 5
3个页框：缺页9次
1 2 3 4 1 2 5 1 2 3 4 5
1 1 1 4 4 4 5 5 5 3 3 3
2 2 2 1 1 1 1 1 1 4 4
3 3 3 2 2 2 2 2 2 2 5
* * * * * * * *
4个页框：缺页10次（更多！）
5.3 最近最少使用（LRU）
原理：替换最长时间未使用的页
// 方案1：时间戳
struct page {
int frame_num;
int last_use_time;
};
int lru_replace_timestamp() {
int oldest_time = INT_MAX;
int victim = -1;
for (int i = 0; i < capacity; i++) {
if (pages[i].last_use_time < oldest_time) {
oldest_time = pages[i].last_use_time;
victim = i;
}
}
return victim;
}
// 方案2：链表
// 最近使用的放链表头，替换时选链表尾
struct lru_list {
struct list_head head;
};
void lru_access(int page_num) {
// 移到链表头
list_move(&pages[page_num].list, &lru_list.head);
}
int lru_replace_list() {
// 返回链表尾
return list_last_entry(&lru_list.head, struct page, list);
}
性能：
理论上接近OPT
实现开销大（每次访问都要更新）
5.4 Clock算法（近似LRU）
原理：循环扫描，给第二次机会
struct page_frame {
int page_num;
int reference_bit; // 访问位
};
page_frame frames[CAPACITY];
int clock_hand = 0;
int clock_replace() {
while (1) {
if (frames[clock_hand].reference_bit == 0) {
// 找到受害页
int victim = clock_hand;
clock_hand = (clock_hand + 1) % CAPACITY;
return victim;
} else {
// 给第二次机会
frames[clock_hand].reference_bit = 0;
clock_hand = (clock_hand + 1) % CAPACITY;
}
}
}
// 页面访问时设置访问位
void page_access(int page_num) {
for (int i = 0; i < CAPACITY; i++) {
if (frames[i].page_num == page_num) {
frames[i].reference_bit = 1;
break;
}
}
}
改进：Clock-改进算法
// 考虑访问位和修改位
// (reference, dirty)
// (0, 0) - 最佳替换
// (0, 1) - 需要写回
// (1, 0) - 最近访问
// (1, 1) - 最近访问且修改
5.5 工作集算法
工作集：最近Δ个时间单位内访问的页面集合
struct working_set {
int pages[MAX_PAGES];
int access_time[MAX_PAGES];
int size;
};
void update_working_set(int page, int current_time) {
// 移除时间窗口外的页面
for (int i = 0; i < ws.size; i++) {
if (current_time - ws.access_time[i] > DELTA) {
remove_page(i);
}
}
// 添加新页面
add_page(page, current_time);
}
6. 写时复制（Copy-On-Write）
原理：fork时不复制内存，只有写入时才复制
void fork_cow() {
// 1. 复制页表
child->page_table = copy_page_table(parent->page_table);
// 2. 标记所有页为只读
for (int i = 0; i < NUM_PAGES; i++) {
parent->page_table[i].writable = 0;
child->page_table[i].writable = 0;
}
// 3. 引用计数+1
for (int i = 0; i < NUM_PAGES; i++) {
page_ref_count[i]++;
}
}
void page_fault_handler(unsigned int addr) {
int page_num = addr >> 12;
if (page_ref_count[page_num] > 1) {
// 写时复制
void *new_page = alloc_page();
memcpy(new_page, frames[page_num], PAGE_SIZE);
page_table[page_num].pfn = get_pfn(new_page);
page_table[page_num].writable = 1;
page_ref_count[page_num]--;
} else {
// 只有一个引用，直接改为可写
page_table[page_num].writable = 1;
}
}
优势：
fork速度快
节省内存
fork后立即exec的场景效率极高
7. 内存分配
7.1 伙伴系统（Buddy System）
原理：2的幂次分配，相邻块可合并
#define MAX_ORDER 11 // 支持2^0到2^10页
struct free_area {
struct list_head free_list;
int nr_free;
};
struct free_area free_area[MAX_ORDER];
void* buddy_alloc(int order) {
// 1. 找到满足大小的块
for (int i = order; i < MAX_ORDER; i++) {
if (!list_empty(&free_area[i].free_list)) {
void *block = list_first_entry(&free_area[i].free_list);
list_del(&block->list);
// 2. 分裂大块
while (i > order) {
i--;
void *buddy = block + (1 << i) * PAGE_SIZE;
list_add(&buddy->list, &free_area[i].free_list);
}
return block;
}
}
return NULL; // 内存不足
}
void buddy_free(void *block, int order) {
// 尝试合并伙伴
while (order < MAX_ORDER - 1) {
void *buddy = get_buddy(block, order);
if (!is_free(buddy, order)) {
break; // 伙伴不空闲
}
// 合并
list_del(&buddy->list);
if (buddy < block) {
block = buddy;
}
order++;
}
// 加入空闲链表
list_add(&block->list, &free_area[order].free_list);
}
7.2 Slab分配器
原理：为常用大小预分配对象缓存
struct kmem_cache {
char *name;
size_t size;
void (*ctor)(void*); // 构造函数
struct list_head slabs_full;
struct list_head slabs_partial;
struct list_head slabs_free;
};
void* kmem_cache_alloc(struct kmem_cache *cache) {
// 1. 优先从partial slab分配
if (!list_empty(&cache->slabs_partial)) {
struct slab *slab = list_first_entry(&cache->slabs_partial);
void *obj = slab_alloc(slab);
if (slab_full(slab)) {
list_move(&slab->list, &cache->slabs_full);
}
return obj;
}
// 2. 从free slab分配
if (!list_empty(&cache->slabs_free)) {
struct slab *slab = list_first_entry(&cache->slabs_free);
void *obj = slab_alloc(slab);
list_move(&slab->list, &cache->slabs_partial);
return obj;
}
// 3. 分配新slab
struct slab *new_slab = alloc_slab(cache);
return slab_alloc(new_slab);
}
8. 实战案例
8.1 测量缺页率
#include <sys/time.h>
#include <sys/resource.h>
void measure_page_faults() {
struct rusage usage;
getrusage(RUSAGE_SELF, &usage);
printf("主缺页: %ld\n", usage.ru_majflt); // 需要磁盘I/O
printf("次缺页: %ld\n", usage.ru_minflt); // 只需分配物理页
}
8.2 mmap内存映射
#include <sys/mman.h>
void* ptr = mmap(NULL, size,
PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS,
-1, 0);
// 使用内存...
munmap(ptr, size);
8.3 大页面（Huge Pages）
# 配置大页面（2MB）
echo 100 > /proc/sys/vm/nr_hugepages
# 查看大页面使用情况
cat /proc/meminfo | grep Huge
// 使用大页面
void *ptr = mmap(NULL, size,
PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
-1, 0);
优势：
减少TLB未命中
减少页表大小
适合大内存应用
9. 常见问题
Q1: 为什么需要虚拟内存？
A:
进程隔离和保护
简化内存管理
支持进程间共享
允许使用比物理内存更大的地址空间
Q2: 页面大小如何选择？
A:
小页面：减少内部碎片，但页表大
大页面：减少页表大小和TLB未命中，但内部碎片多
常用：4KB（通用），2MB（大页面）
Q3: 如何减少缺页中断？
A:
增加物理内存
优化页面置换算法
使用局部性原理
预取策略
使用大页面
Q4: 为什么fork那么快？
A: 写时复制！只复制页表，不复制实际数据
参考资源
《深入理解计算机系统》(CSAPP) - 第9章
《Operating Systems: Three Easy Pieces》
Linux源码：
mm/memory.c,mm/page_alloc.cIntel手册：《Intel 64 and IA-32 Architectures Software Developer’s Manual》