# 内存管理

## 💡 核心结论

1. **虚拟内存是现代操作系统的基石，提供进程隔离和内存抽象**
2. **分页比分段更灵活，段页式结合两者优点**
3. **多级页表减少内存占用，TLB加速地址转换**
4. **LRU是最优页面置换算法的近似，Clock算法是LRU的高效实现**
5. **写时复制(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 ─┘  (映射到不同物理页)
```

**虚拟地址的优势**：
1. 进程隔离（安全）
2. 内存碎片整理（灵活）
3. 程序重定位（简单）
4. 共享内存（高效）

### 2.2 内存布局

```text
// 典型的进程内存布局（32位）

0xFFFFFFFF  ┌─────────────┐
            │   内核空间   │ 1GB
0xC0000000  ├─────────────┤
            │     栈       │ ↓ 向下增长
            ├─────────────┤
            │      ↕      │
            ├─────────────┤
            │     堆       │ ↑ 向上增长
            ├─────────────┤
            │   BSS段     │ 未初始化数据
            ├─────────────┤
            │   数据段     │ 已初始化数据
            ├─────────────┤
            │   代码段     │ 只读
0x08048000  ├─────────────┤
            │   保留区     │
0x00000000  └─────────────┘
```

**查看进程内存布局**：
```c
#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地址空间
```

**地址转换**：
```c
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（按需分配）

节省：只需一级页表 + 实际使用的二级页表
```

**地址转换**：
```c
// 两级页表转换
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缓存最近的地址转换

```c
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 基本分段

**原理**：按逻辑单元（代码、数据、栈）分段

```c
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）

**原理**：替换未来最长时间不用的页（理论最优）

```c
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）

**原理**：替换最早进入的页

```c
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）

**原理**：替换最长时间未使用的页

```c
// 方案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）

**原理**：循环扫描，给第二次机会

```c
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-改进算法**
```c
// 考虑访问位和修改位
// (reference, dirty)
// (0, 0) - 最佳替换
// (0, 1) - 需要写回
// (1, 0) - 最近访问
// (1, 1) - 最近访问且修改
```

### 5.5 工作集算法

**工作集**：最近Δ个时间单位内访问的页面集合

```c
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时不复制内存，只有写入时才复制

```c
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的幂次分配，相邻块可合并

```c
#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分配器

**原理**：为常用大小预分配对象缓存

```c
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 测量缺页率

```c
#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内存映射

```c
#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）

```bash
# 配置大页面（2MB）
echo 100 > /proc/sys/vm/nr_hugepages

# 查看大页面使用情况
cat /proc/meminfo | grep Huge
```

```c
// 使用大页面
void *ptr = mmap(NULL, size,
                PROT_READ | PROT_WRITE,
                MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
                -1, 0);
```

**优势**：
- 减少TLB未命中
- 减少页表大小
- 适合大内存应用

---

## 9. 常见问题

### Q1: 为什么需要虚拟内存？
**A**:
1. 进程隔离和保护
2. 简化内存管理
3. 支持进程间共享
4. 允许使用比物理内存更大的地址空间

### Q2: 页面大小如何选择？
**A**:
- 小页面：减少内部碎片，但页表大
- 大页面：减少页表大小和TLB未命中，但内部碎片多
- 常用：4KB（通用），2MB（大页面）

### Q3: 如何减少缺页中断？
**A**:
1. 增加物理内存
2. 优化页面置换算法
3. 使用局部性原理
4. 预取策略
5. 使用大页面

### Q4: 为什么fork那么快？
**A**: 写时复制！只复制页表，不复制实际数据

---

## 参考资源

- 《深入理解计算机系统》(CSAPP) - 第9章
- 《Operating Systems: Three Easy Pieces》
- Linux源码：`mm/memory.c`, `mm/page_alloc.c`
- Intel手册：《Intel 64 and IA-32 Architectures Software Developer's Manual》