【总结】第三章:内存管理
考研提示:本章重点是分页地址转换计算、多级页表的地址结构、TLB命中的访存耗时计算、页面置换算法(LRU/FIFO/Clock)。段页式和连续分配了解即可。
一、内存管理概述
1.1 内存管理的四大功能
- 内存分配与回收:为进程分配空间,释放后回收
- 地址变换(重定位):逻辑地址 → 物理地址
- 内存保护:进程间互不干扰
- 内存扩充(虚拟内存):让进程的逻辑空间大于实际物理内存
1.2 地址类型
- 逻辑地址(虚地址):程序编译后看到的地址,从0开始
- 物理地址(实地址):内存条上的真实地址
- 地址变换:MMU(内存管理单元)负责在硬件层完成
二、连续分配管理(了解)
| 方式 | 分配规则 | 缺点 |
|---|---|---|
| 单一连续分配 | 内存只给一个进程 | 利用率极低 |
| 固定分区分配 | 内存分固定大小的区 | 内部碎片 |
| 动态分区分配 | 按需分配,大小不固定 | 外部碎片 |
动态分区常用算法:
- 首次适应(First Fit):从头找第一个能装下的空闲区(通常最好)
- 最佳适应(Best Fit):找最小的刚好够的空闲区(产生大量小碎片)
- 最坏适应(Worst Fit):找最大的空闲区(大区很快被分完)
碎片解决:紧凑/拼凑(Compaction)——移动所有已分配区,合并外部碎片(开销极大)
三、分页存储管理(核心!)
3.1 基本原理
- 逻辑空间划分为等大的页(Page)
- 物理内存划分为等大的页框/物理块(Page Frame)
- 页表记录逻辑页号→物理页框号的映射
关键公式:
3.2 页表项与页表大小
例:页内偏移12位(页面4KB),页号20位,PTE=4B → 最大页表大小 =
3.3 多级页表(解决大页表占用连续内存的问题)
动机:单级页表可能占用巨大连续空间(如4MB),多级页表将页表本身也分页存储,可按需加载。
二级页表地址结构:
地址转换过程:
- 用查页目录表(一级页表)→ 得到二级页表的页框号
- 用查二级页表 → 得到数据页的页框号
- 加上偏移量d → 物理地址
⚠️ 重点:n级页表需要访问内存 n+1 次(n次查表+1次访问数据)
3.4 快表(TLB,Translation Lookaside Buffer)
作用:硬件高速缓存,缓存最近使用的页表项,加快地址变换
访存耗时三种情况:
| 情况 | 流程 | 公式 |
|---|---|---|
| TLB命中 | 查TLB→访存数据 | |
| TLB未命中,页在内存 | 查TLB(失败)→查页表→访存数据 | (二级页表则+2次) |
| TLB未命中,缺页 | 查TLB→查页表(缺页)→缺页中断→页面置换→重新执行 |
其中:
- :访问TLB(快表)一次的时间(约10ns)
- :访问主存一次的时间(约100ns)
- :访问磁盘(缺页处理)时间(约10ms,远大于内存)
有效访问时间(EAT)(设TLB命中率为h):
其中:
- :TLB命中率(Hit Rate),即在TLB中找到页表项的概率
- :TLB查找时间
- :主存访问时间
- 命中:只需访问TLB + 访问数据()
- 未命中:TLB + 主存查页表 + 主存访数据()
四、分段与段页式(了解)
分段:按程序逻辑模块划分,段长不固定
- 地址 = 段号S + 段内偏移d
- 优点:逻辑清晰,便于共享和保护
- 缺点:外部碎片,不易实现虚拟内存
段页式:先分段,段内再分页
- 地址 = 段号S + 页号P + 页内偏移d
- 两个表:段表 + 页表;地址转换需3次内存访问
五、虚拟内存
5.1 概念
虚拟内存允许程序的逻辑空间大于物理内存。进程运行时只把部分页面装入内存,其余放在磁盘;访问不在内存的页时触发缺页中断,按需调入。
实现方式:请求分页、请求分段、请求段页式
5.2 页面置换算法
| 算法 | 淘汰依据 | Belady异常 | 特点 |
|---|---|---|---|
| OPT(最优) | 未来最长时间不用的页 | 无 | 理论最优,实际无法实现 |
| FIFO | 最早进入内存的页 | 有 | 实现简单,性能差 |
| LRU(最近最少使用) | 最久未被访问的页 | 无 | 接近最优,实现开销大 |
| Clock(时钟算法) | 访问位为0的页(二次机会) | 无 | FIFO+LRU折中,实际系统常用 |
Belady异常:分配页框越多,缺页次数反而增加(仅FIFO会出现,LRU/OPT不会)
Clock算法步骤:
- 时钟指针扫描,访问位=0 → 直接淘汰,指针下移
- 访问位=1 → 清0,指针下移,给予第二次机会
- 若转一圈全为1,第二圈起始页访问位已为0,必定淘汰
5.3 缺页中断处理流程
- CPU访问逻辑地址 → 页表有效位=0 → 产生缺页中断
- 保存现场,进入内核
- 查磁盘,找到缺失页面
- 若内存有空闲页框,直接调入;否则运行置换算法选出淘汰页
- 若淘汰页被修改过(脏页),先写回磁盘
- 将新页调入,更新页表
- 恢复现场,重新执行发生缺页的指令
5.4 抖动(Thrashing)
定义:进程不断发生缺页,花大量时间在换页上而非执行程序
原因:分配给进程的物理页框数太少,无法满足工作集
解决:
- 工作集策略(保证工作集所有页面都在内存)
- 降低多道程序度(减少并发进程数)
六、多维数组与Cache(补充)
6.1 二维数组的内存存储
C语言中,二维数组int A[m][n]按行优先存储:
A[i][j]的地址 = 基地址 +(i×n + j) × sizeof(int)
6.2 Cache命中率
其中:
- :Cache命中率
- :Cache访问时间
- :内存访问时间
- :缺失率,缺失时需同时访问Cache和内存
局部性原理:
- 时间局部性:最近访问过的数据很快还会再被访问(循环变量)
- 空间局部性:被访问数据附近的数据很快也会被访问(数组顺序遍历)
陷阱:二维数组按列遍历会破坏空间局部性,命中率极低!
七、高频易错汇总
| 易错点 | 正确理解 |
|---|---|
| 页号位数决定页面大小 | 偏移量位数决定页面大小: |
| 页面大小决定页号位数 | 页号位数 = 逻辑地址总位数 - 偏移量位数 |
| 多级页表减少内存访问次数 | 多级页表增加访问次数,减少的是连续内存占用 |
| TLB命中不需要访主存 | TLB命中仍需访主存一次(取数据) |
| FIFO缺页次数随页框增多而减少 | FIFO存在Belady异常,可能反而增多 |
| LRU有Belady异常 | 只有FIFO有Belady异常,LRU没有 |
| 缺页中断时直接换入 | 若内存满,先置换再换入;且置换的脏页要写回磁盘 |