【总结】第三章:内存管理

考研提示:本章重点是分页地址转换计算、多级页表的地址结构、TLB命中的访存耗时计算、页面置换算法(LRU/FIFO/Clock)。段页式和连续分配了解即可。


一、内存管理概述

1.1 内存管理的四大功能

  1. 内存分配与回收:为进程分配空间,释放后回收
  2. 地址变换(重定位):逻辑地址 → 物理地址
  3. 内存保护:进程间互不干扰
  4. 内存扩充(虚拟内存):让进程的逻辑空间大于实际物理内存

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),多级页表将页表本身也分页存储,可按需加载。

二级页表地址结构:

地址转换过程:

  1. 用查页目录表(一级页表)→ 得到二级页表的页框号
  2. 用查二级页表 → 得到数据页的页框号
  3. 加上偏移量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算法步骤:

  1. 时钟指针扫描,访问位=0 → 直接淘汰,指针下移
  2. 访问位=1 → 清0,指针下移,给予第二次机会
  3. 若转一圈全为1,第二圈起始页访问位已为0,必定淘汰

5.3 缺页中断处理流程

  1. CPU访问逻辑地址 → 页表有效位=0 → 产生缺页中断
  2. 保存现场,进入内核
  3. 查磁盘,找到缺失页面
  4. 若内存有空闲页框,直接调入;否则运行置换算法选出淘汰页
  5. 若淘汰页被修改过(脏页),先写回磁盘
  6. 将新页调入,更新页表
  7. 恢复现场,重新执行发生缺页的指令

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没有
缺页中断时直接换入若内存满,先置换再换入;且置换的脏页要写回磁盘