内存管理

内存分配

连续分配

方式	说明	问题
单一连续	整个内存给一个进程	利用率低
固定分区	内存分成固定大小分区	内部碎片
动态分区	按需分配	外部碎片

分配算法

• 首次适应：从头找第一个满足的
• 最佳适应：找最小满足的
• 最坏适应：找最大的
• 邻近适应：从上次位置开始找

虚拟内存

概念

虚拟内存使程序可以使用比物理内存更大的地址空间。

┌─────────────────────────────────────────────────────────┐
│                    虚拟内存                             │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  ┌─────────────┐        ┌─────────────┐                │
│  │  虚拟地址   │        │  物理地址   │                │
│  │   空间      │  MMU   │   空间      │                │
│  │  ┌─────┐   │ ────>  │  ┌─────┐   │                │
│  │  │Page │   │        │  │Frame│   │                │
│  │  └─────┘   │        │  └─────┘   │                │
│  └─────────────┘        └─────────────┘                │
│                              │                          │
│                              ▼                          │
│                         ┌─────────┐                    │
│                         │  磁盘   │                    │
│                         └─────────┘                    │
│                                                         │
└─────────────────────────────────────────────────────────┘

分页

┌─────────────────────────────────────────────────────────┐
│                    分页机制                             │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  虚拟地址: [页号 | 页内偏移]                            │
│                │                                        │
│                ▼                                        │
│           ┌─────────┐                                  │
│           │  页表   │                                  │
│           │ ┌─────┐ │                                  │
│           │ │ 0→3 │ │  页号 → 帧号                     │
│           │ │ 1→7 │ │                                  │
│           │ │ 2→5 │ │                                  │
│           │ └─────┘ │                                  │
│           └─────────┘                                  │
│                │                                        │
│                ▼                                        │
│  物理地址: [帧号 | 页内偏移]                            │
│                                                         │
└─────────────────────────────────────────────────────────┘

多级页表

┌─────────────────────────────────────────────────────────┐
│                   二级页表                              │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  虚拟地址: [一级页号 | 二级页号 | 页内偏移]              │
│                │          │                             │
│                ▼          │                             │
│           ┌─────────┐     │                             │
│           │一级页表 │     │                             │
│           │ ┌─────┐ │     │                             │
│           │ │  →  │─┼─────┘                             │
│           │ └─────┘ │                                   │
│           └─────────┘                                   │
│                │                                        │
│                ▼                                        │
│           ┌─────────┐                                  │
│           │二级页表 │                                  │
│           │ ┌─────┐ │                                  │
│           │ │ →帧 │ │                                  │
│           │ └─────┘ │                                  │
│           └─────────┘                                  │
│                                                         │
└─────────────────────────────────────────────────────────┘

TLB（快表）

TLB 是页表的高速缓存，加速地址转换。

地址转换流程：
1. 查 TLB
2. TLB 命中 → 直接得到帧号
3. TLB 未命中 → 查页表 → 更新 TLB

页面置换算法

常见算法

算法	说明	特点
OPT	置换最长时间不用的	理想，无法实现
FIFO	先进先出	简单，Belady 异常
LRU	最近最少使用	性能好，开销大
Clock	时钟算法	LRU 近似，开销小
LFU	最不经常使用	考虑频率

LRU 实现

// 使用 LinkedHashMap
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // accessOrder=true
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

Clock 算法

┌─────────────────────────────────────────────────────────┐
│                   Clock 算法                            │
├─────────────────────────────────────────────────────────┤
│                                                         │
│           ┌───┐                                        │
│      ┌────│ 1 │────┐                                   │
│      │    └───┘    │                                   │
│    ┌───┐         ┌───┐                                 │
│    │ 0 │         │ 1 │  ← 指针                         │
│    └───┘         └───┘                                 │
│      │    ┌───┐    │                                   │
│      └────│ 0 │────┘                                   │
│           └───┘                                        │
│                                                         │
│  访问位=1：清零，指针后移                               │
│  访问位=0：置换该页                                     │
│                                                         │
└─────────────────────────────────────────────────────────┘

分段

分段 vs 分页

特性	分页	分段
目的	内存管理	逻辑划分
大小	固定	可变
地址	一维	二维（段号+偏移）
碎片	内部碎片	外部碎片

段页式

结合分段和分页的优点：

1. 先按逻辑分段
2. 每段再分页
3. 地址：段号 + 页号 + 页内偏移