存储器层次结构¶
概述¶
存储器层次结构是计算机系统为了解决存储器速度、容量和成本之间的矛盾而采用的一种组织方式。通过将不同性能的存储器按层次组织,形成Cache-主存-辅存的三级结构。
存储器层次结构的基本原理¶
程序局部性原理
存储器层次结构有效的基础是程序局部性原理。
时间局部性¶
时间局部性: 如果一个存储单元被访问,那么不久后它可能再次被访问。
示例:
- 循环体中的指令
- 循环计数器
- 累加变量
空间局部性¶
空间局部性: 如果一个存储单元被访问,那么它附近的单元也可能被访问。
示例:
- 数组元素
- 顺序执行的指令
- 结构体字段
三级存储器结构¶
graph TB
A[CPU] --> B[Cache<br/>高速缓冲存储器]
B --> C[主存储器<br/>RAM]
C --> D[辅助存储器<br/>磁盘/SSD]
style A fill:#ff9999
style B fill:#99ff99
style C fill:#9999ff
style D fill:#ffff99各级存储器的特点¶
| 存储器 | 速度 | 容量 | 成本 | 介质 |
|---|---|---|---|---|
| Cache | 最快 | 最小 | 最高 | SRAM |
| 主存 | 中等 | 中等 | 中等 | DRAM |
| 辅存 | 最慢 | 最大 | 最低 | 磁盘/SSD |
Cache存储器¶
Cache的基本原理¶
Cache的作用
Cache是位于CPU和主存之间的高速小容量存储器,用于存放当前最活跃的程序和数据。
工作原理:
- CPU访问存储器时,先访问Cache
- 如果命中,直接从Cache读取
- 如果未命中,从主存读取,并调入Cache
Cache的映射方式¶
1. 直接映射¶
直接映射: 每个主存块只能映射到Cache的一个特定行。
映射公式:
| Text Only | |
|---|---|
优点:
- 硬件实现简单
- 成本低
缺点:
- 灵活性差
- 冲突率高
2. 全相联映射¶
全相联映射: 每个主存块可以映射到Cache的任意一行。
优点:
- 灵活性好
- 冲突率低
缺点:
- 硬件复杂
- 成本高
3. 组相联映射¶
组相联映射: 每个主存块可以映射到Cache的一个特定组中的任意一行。
映射公式:
| Text Only | |
|---|---|
优点:
- 兼顾灵活性和成本
- 应用最广泛
Cache的替换算法¶
替换算法
当Cache满时,需要替换已有的块。
1. 随机替换 (RAND)¶
- 随机选择一行替换
- 实现简单
- 性能不稳定
2. 先进先出 (FIFO)¶
- 替换最早进入的块
- 实现简单
- 不考虑使用情况
3. 最近最少使用 (LRU)¶
LRU算法: 替换最近最少使用的块,性能最好。
实现方法:
- 计数器法
- 堆栈法
- 对位矩阵法
4. 最不经常使用 (LFU)¶
- 替换使用次数最少的块
- 需要计数器
- 考虑长期使用情况
Cache的写策略¶
1. 写回法 (Write Back)¶
写回法: 只写Cache,替换时才写回主存。
特点:
- 写速度快
- 需要修改位
- 一致性问题
2. 写直达法 (Write Through)¶
写直达法: 同时写Cache和主存。
特点:
- 一致性好
- 写速度慢
- 实现简单
Cache的性能指标¶
1. 命中率 (Hit Rate)¶
| Text Only | |
|---|---|
2. 平均访问时间¶
| Text Only | |
|---|---|
虚拟存储器¶
虚拟存储器的概念¶
虚拟存储器
虚拟存储器是主存和辅存的结合,为用户提供一个比实际主存大得多的存储空间。
特点:
- 逻辑地址空间 > 物理地址空间
- 按需调入
- 对用户透明
虚拟存储器的实现方式¶
1. 页式虚拟存储器¶
页式管理: 将程序和主存划分为大小相等的页。
地址结构:
页表:
- 页号 → 页框号
- 有效位、修改位、访问位等
2. 段式虚拟存储器¶
段式管理: 按程序的逻辑结构分段。
特点:
- 段长可变
- 便于共享和保护
- 产生碎片
3. 段页式虚拟存储器¶
段页式管理: 先分段,再分页。
特点:
- 兼顾段式和页式的优点
- 地址变换复杂
- 应用广泛
页面置换算法¶
页面置换
当缺页时,如果主存已满,需要置换页面。
1. 最佳置换 (OPT)¶
- 置换将来最长时间不用的页面
- 理论最优,无法实现
- 用于性能评估
2. 先进先出 (FIFO)¶
- 置换最早进入的页面
- 实现简单
- 可能出现Belady异常
3. 最近最少使用 (LRU)¶
LRU算法: 置换最近最少使用的页面,性能接近OPT。
实现方法:
- 计数器法
- 堆栈法
- 近似LRU
4. 时钟置换 (Clock)¶
- 循环检查各页的访问位
- 访问位为0则置换
- 实现简单,性能较好