当前位置：首页 > web >正文

2.虚拟内存：分页、分段、页面置换算法

web 2025/9/7 10:22:35

1. 为什么需要虚拟内存？

物理内存的局限性

2. 分页（Paging）机制

基本概念

页表结构

地址转换过程

多级页表

3. 分段（Segmentation）机制

基本概念

段表结构

地址转换过程

分页 vs 分段对比

4. 段页式存储管理

结合分段和分页的优点

5. 页面置换算法 (核心考点！)

为什么需要页面置换？

5.1 最佳置换算法（OPT）

5.2 先进先出算法（FIFO）

5.3 最近最少使用算法（LRU）

5.4 时钟算法（Clock/Second Chance）

5.5 最不经常使用算法（LFU）

6. 页面置换算法对比

7. 实际系统中的实现

Linux页面置换

Windows页面置换

8. 常见问题

Q1: 什么是虚拟内存？为什么需要它？

Q2: 分页和分段的主要区别是什么？

Q3: 什么是缺页中断（Page Fault）？

Q4: LRU算法为什么难以实现？

Q5: 什么是Belady异常？

9. 性能优化考虑

工作集模型

预取优化

总结

3.进程调度:常见算法

1. 为什么需要虚拟内存？

物理内存的局限性

// 传统物理内存访问的问题
void physical_memory_issues() {// 1. 内存碎片问题char* block1 = malloc(100);  // 分配100字节char* block2 = malloc(200);  // 分配200字节free(block1);               // 释放100字节// 现在有一个100字节的"空洞"，但无法分配250字节// 2. 内存大小限制// 程序只能使用有限的物理内存// 大程序无法完全加载到内存中// 3. 安全性问题// 程序可以直接访问物理内存，可能破坏其他程序数据
}

目的：让每个进程都以为自己拥有连续、完整的内存空间，简化编程。同时，通过磁盘扩展内存容量，实现“内存不够，磁盘来凑”。
核心思想：将程序使用的内存地址（虚拟地址）与硬件使用的内存地址（物理地址）分开。
好处：
- 安全性：进程无法直接访问物理内存，互相隔离。
- 简化管理：程序员无需关心物理内存的具体布局。
- 内存扩充：可以运行比物理内存更大的程序。

2. 分页（Paging）机制

基本概念

虚拟地址空间：每个进程看到的连续内存空间
物理地址空间：实际的物理内存+-------------------+      +-------------------+
|  虚拟地址空间       |      |  物理地址空间       |
|  0x0000 - 0xFFFF  |      |                   |
|                   |      |                   |
|  分为固定大小的页   |----->|  分为固定大小的帧   |
|  (通常4KB)        |      |  (通常4KB)        |
|                   |      |                   |
|  通过页表映射       |      |                   |
+-------------------+      +-------------------+

页表结构

// 页表项（Page Table Entry）的基本结构
struct page_table_entry {uint32_t present    : 1;   // 页是否在物理内存中uint32_t rw         : 1;   // 读写权限uint32_t user       : 1;   // 用户/内核模式uint32_t accessed   : 1;   // 是否被访问过uint32_t dirty      : 1;   // 是否被修改过uint32_t unused     : 7;   // 未使用位uint32_t frame      : 20;  // 物理帧号
};

地址转换过程

虚拟地址：| 页号 (20位) | 页内偏移 (12位) |↓页表查询 → 找到对应的页表项↓
物理地址：| 帧号 (20位) | 页内偏移 (12位) |

多级页表

// 二级页表示例（x86架构）
void address_translation(uint32_t virtual_addr) {// 虚拟地址分解uint32_t page_dir_index = (virtual_addr >> 22) & 0x3FF;  // 10位uint32_t page_table_index = (virtual_addr >> 12) & 0x3FF; // 10位uint32_t offset = virtual_addr & 0xFFF;                  // 12位// 页目录查询page_directory_entry* pde = &page_dir[page_dir_index];if (!pde->present) {handle_page_fault();  // 页错误处理}// 页表查询page_table_entry* pte = &page_table[pde->base_addr][page_table_index];if (!pte->present) {handle_page_fault();  // 页错误处理}// 生成物理地址uint32_t physical_addr = (pte->frame << 12) | offset;
}

3. 分段（Segmentation）机制

基本概念

虚拟地址空间按逻辑单元分段：
+-------------------+
|   代码段 (text)    |
+-------------------+
|   数据段 (data)    |
+-------------------+
|   堆段 (heap)      |
+-------------------+
|   栈段 (stack)     |
+-------------------+
|   共享库段         |
+-------------------+

段表结构

// 段描述符结构
struct segment_descriptor {uint32_t base_addr;    // 段基地址uint32_t limit;        // 段界限uint32_t type;         // 段类型（代码/数据）uint32_t privilege;    // 特权级uint32_t present;      // 段是否存在
};

地址转换过程

虚拟地址：| 段选择符 | 段内偏移 |↓段表查询 → 找到段描述符↓
检查权限和界限 → 如果违规则段错误↓
物理地址：基地址 + 段内偏移

分页 vs 分段对比

这是两种不同的内存管理方式。

特性	分页 (Paging)	分段 (Segmentation)
基本单位	页 (Page) - 固定大小的块（如4KB）	段 (Segment) - 逻辑单位（代码段、数据段、堆栈段），长度不固定
地址空间	一维线性地址空间	二维地址空间（段号 + 段内偏移）
碎片问题	产生内部碎片（页内未用完的空间）	产生外部碎片（段间难以利用的小空隙）
管理方式	由操作系统自动完成，对程序员透明	程序员（或编译器）需要感知段的划分
主要优势	简单高效，利于内存换入换出	符合程序的逻辑视图，易于共享和保护
现代应用	几乎所有现代通用操作系统（Linux, Windows）	常用于特定领域或与分页结合（段页式）

简单比喻：

分页：像一本练习本，每一页大小都固定。写作业时，如果一页没写满，剩下的格子就浪费了（内部碎片）。
分段：像一篇文章，有“开头”、“正文”、“结尾”等不同部分，每个部分长短不一。如果把很多文章的不同部分混在一起放，中间就会产生很多小空隙（外部碎片）。

现代操作系统（如x86 Linux）实际采用的都是【段页式内存管理】：先分段（出于历史兼容和权限控制），再分页。但对程序员来说，感受到的主要是分页机制。

4. 段页式存储管理

结合分段和分页的优点

虚拟地址：| 段号 | 段内页号 | 页内偏移 |↓段表查询 → 得到页表基地址↓页表查询 → 得到物理帧号↓
物理地址：| 帧号 | 页内偏移 |

5. 页面置换算法 (核心考点！)

为什么需要页面置换？

当物理内存不足时，需要将一些页面换出到磁盘，为新的页面腾出空间。

5.1 最佳置换算法（OPT）

// 理想算法，无法实际实现，作为性能比较基准
int opt_replace(struct page_table* pt, int new_page) {// 选择未来最长时间不会被访问的页面替换// 这需要知道未来的访问序列，实际中不可能return find_furthest_used_page();
}

特点：理论最优，但无法实际实现

5.2 先进先出算法（FIFO）

概念：换出最先进入内存的页面。

// 实现简单的队列
struct fifo_cache {int pages[MAX_FRAMES];int front, rear;int count;
};int fifo_replace(struct fifo_cache* cache, int new_page) {if (cache->count >= MAX_FRAMES) {// 替换最早进入的页面int victim = cache->pages[cache->front];cache->front = (cache->front + 1) % MAX_FRAMES;cache->count--;return victim;}// 还有空位，直接添加cache->pages[cache->rear] = new_page;cache->rear = (cache->rear + 1) % MAX_FRAMES;cache->count++;return -1;  // 没有需要替换的页面
}

特点：实现简单（用一个队列即可），但性能差。可能会出现 Belady异常：分配的物理页框增多，缺页率反而上升的异常现象。

5.3 最近最少使用算法（LRU）

概念：换出最长时间没有被访问的页面。

// 使用双向链表+哈希表实现O(1)复杂度的LRU
struct lru_node {int page;struct lru_node *prev, *next;
};struct lru_cache {struct lru_node* head;struct lru_node* tail;struct lru_node** hash;  // 快速查找int capacity;int count;
};void lru_access(struct lru_cache* cache, int page) {struct lru_node* node = cache->hash[page];if (node) {// 移动到链表头部（最近使用）move_to_head(cache, node);} else {if (cache->count >= cache->capacity) {// 替换链表尾部的页面（最久未使用）int victim = remove_tail(cache);// 从磁盘加载新页面...}// 添加到头部add_to_head(cache, create_node(page));}
}

特点：根据程序的局部性原理，过去一段时间没用的，未来一段时间也用到的概率较低。性能接近OPT，是最常用、最有效的算法。
面试重点：要求能手写LRU算法的实现。

5.4 时钟算法（Clock/Second Chance）

// 近似LRU的简单算法
struct clock_cache {int pages[MAX_FRAMES];int ref_bits[MAX_FRAMES];  // 引用位int hand;                  // 时钟指针
};int clock_replace(struct clock_cache* cache, int new_page) {while (true) {if (cache->ref_bits[cache->hand] == 0) {// 找到可替换的页面int victim = cache->pages[cache->hand];cache->pages[cache->hand] = new_page;cache->ref_bits[cache->hand] = 1;cache->hand = (cache->hand + 1) % MAX_FRAMES;return victim;} else {// 给第二次机会，清除引用位cache->ref_bits[cache->hand] = 0;cache->hand = (cache->hand + 1) % MAX_FRAMES;}}
}

特点：LRU的良好近似，实现相对简单

5.5 最不经常使用算法（LFU）

// 基于访问频率的置换
struct lfu_cache {int pages[MAX_FRAMES];int freq[MAX_FRAMES];     // 访问频率计数int time[MAX_FRAMES];     // 最近访问时间（解决频率相同的情况）
};int lfu_replace(struct lfu_cache* cache, int new_page, int current_time) {// 找到访问频率最低的页面int min_freq = INT_MAX;int victim = -1;for (int i = 0; i < MAX_FRAMES; i++) {if (cache->freq[i] < min_freq || (cache->freq[i] == min_freq && cache->time[i] < cache->time[victim])) {min_freq = cache->freq[i];victim = i;}}// 替换选中的页面int old_page = cache->pages[victim];cache->pages[victim] = new_page;cache->freq[victim] = 1;cache->time[victim] = current_time;return old_page;
}

特点：基于访问频率，适合某些特定场景

6. 页面置换算法对比

算法	优点	缺点	适用场景
OPT	理论最优	无法实现	性能基准
FIFO	实现简单	Belady异常，性能差	简单系统
LRU	性能好	实现复杂，需要硬件支持	通用系统
Clock	LRU近似，实现简单	不如LR精确	实际系统常用
LFU	基于访问频率	可能保留陈旧页面	特定工作负载

7. 实际系统中的实现

Linux页面置换

Linux使用改进的LRU算法，包含多个LRU链表：

活跃链表：最近被访问的页面
非活跃链表：可能被换出的页面
使用双链表和页面标志位实现

Windows页面置换

Windows使用工作集管理和时钟算法：

每个进程有工作集（working set）
使用时钟算法选择置换页面
支持页面优先级

8. 常见问题

Q1: 什么是虚拟内存？为什么需要它？

答：虚拟内存是一种内存管理技术，为每个进程提供独立的地址空间，使得程序可以使用比物理内存更大的地址空间，并提供内存保护和共享机制。

Q2: 分页和分段的主要区别是什么？

答：分页使用固定大小的内存单元，只有内部碎片；分段使用可变大小的内存单元，有外部和内部碎片。分页提供一维地址空间，分段提供二维地址空间。

Q3: 什么是缺页中断（Page Fault）？

答：当程序访问的页面不在物理内存中时，CPU产生缺页中断，操作系统需要从磁盘加载该页面到内存。

Q4: LRU算法为什么难以实现？

答：因为需要精确记录每个页面的访问时间顺序，这需要硬件支持（如引用位）和复杂的软件实现，开销较大。

Q5: 什么是Belady异常？

答：在FIFO算法中，增加物理帧数反而导致缺页率增加的反常现象。

9. 性能优化考虑

工作集模型

// 工作集：进程在一段时间内访问的页面集合
void working_set_management() {// 监控进程的页面访问模式// 保持工作集在物理内存中// 将非工作集页面换出
}

预取优化

// 根据访问模式预加载可能需要的页面
void prefetch_pages() {// 顺序访问模式：预取后续页面// 随机访问模式：基于历史记录预测
}

编程实现：手撕LRU算法

这是面试最高频的算法题之一，它完美结合了操作系统概念和数据结构能力。

要求：设计并实现一个满足LRU缓存约束的数据结构。
操作：

get(key)：如果关键字存在，则取其值，并将其更新为最新使用。
put(key, value)：如果关键字存在，则变更其值，并更新为最新使用；如果不存在，则插入。如果插入导致容量超标，则逐出最久未使用的项。

实现思路：

使用一个双向链表来维护访问顺序： recently used排在头部，least recently used排在尾部。
使用一个哈希表来提供O(1)时间复杂度的key查询，指向链表中的节点。

#include <iostream>
#include <unordered_map>
#include <list>class LRUCache {
private:int capacity;// 双向链表：存储实际的 (key, value) 对，顺序代表使用顺序std::list<std::pair<int, int>> cacheList;// 哈希表：映射 key 到链表中的迭代器std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap;public:LRUCache(int capacity) : capacity(capacity) {}int get(int key) {auto it = cacheMap.find(key);// 如果key不存在，返回-1if (it == cacheMap.end()) {return -1;}// key存在，将对应节点移到链表头部，并返回valuecacheList.splice(cacheList.begin(), cacheList, it->second);return it->second->second;}void put(int key, int value) {auto it = cacheMap.find(key);// key已存在，更新value，并移到头部if (it != cacheMap.end()) {it->second->second = value; // 更新值cacheList.splice(cacheList.begin(), cacheList, it->second); // 移到头部return;}// key不存在，需要插入// 如果容量已满，删除尾部节点（LRU项）if (cacheList.size() == capacity) {auto lruNode = cacheList.back(); // 获取尾部的节点cacheMap.erase(lruNode.first);   // 从哈希表中删除对应的keycacheList.pop_back();            // 从链表中删除节点}// 将新节点插入到链表头部cacheList.emplace_front(key, value);cacheMap[key] = cacheList.begin(); // 在哈希表中记录迭代器位置}
};// 测试用例
int main() {LRUCache cache(2); // 容量为2cache.put(1, 1);cache.put(2, 2);std::cout << cache.get(1) << std::endl; // 返回 1cache.put(3, 3); // 该操作会使得关键字 2 作废std::cout << cache.get(2) << std::endl; // 返回 -1 (未找到)cache.put(4, 4); // 该操作会使得关键字 1 作废std::cout << cache.get(1) << std::endl; // 返回 -1 (未找到)std::cout << cache.get(3) << std::endl; // 返回 3std::cout << cache.get(4) << std::endl; // 返回 4return 0;
}