607 lines
20 KiB
Markdown
607 lines
20 KiB
Markdown
# 16. 虚拟存储器
|
||
|
||
> **课程**: 操作系统 - 存储器管理
|
||
> **核心内容**: 虚拟存储器思想、局部性原理、请求分页、页面置换算法、内存分配策略、抖动与工作集
|
||
|
||
---
|
||
|
||
## 前置知识
|
||
|
||
- [[14_分页存储管理]] — 分页思想、页表、地址变换、缺页中断
|
||
- [[15_段式存储管理]] — 分段思想、段页式
|
||
- [[11_处理机调度]] — 进程调度基本概念
|
||
|
||
---
|
||
|
||
## 一、虚拟存储器的基本思想
|
||
|
||
### 问题的提出
|
||
|
||
在传统的存储管理中，作业必须**全部装入内存**才能运行。这带来两个问题：
|
||
1. 作业大小超过物理内存时，无法运行
|
||
2. 内存中同时驻留多个大程序时，内存不够用
|
||
|
||
### 虚拟存储器思想
|
||
|
||
**核心**: 程序员在比实际物理内存**大得多**的虚拟地址空间中编写程序，运行时只需将**部分页面**调入内存，其余留在外存。当访问到不在内存的页面时，再从外存调入。
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph VA["虚拟地址空间 (很大)"]
|
||
direction TB
|
||
V0["页面0 ✓ 在内存"]
|
||
V1["页面1 ✓ 在内存"]
|
||
V2["页面2 ✗ 在外存"]
|
||
V3["页面3 ✓ 在内存"]
|
||
V4["页面4 ✗ 在外存"]
|
||
V5["..."]
|
||
end
|
||
|
||
subgraph MEM["物理内存 (较小)"]
|
||
direction TB
|
||
M0["页框0"]
|
||
M1["页框1"]
|
||
M2["页框2"]
|
||
M3["页框3"]
|
||
end
|
||
|
||
subgraph DISK["外存 (磁盘)"]
|
||
direction TB
|
||
D0["页面2"]
|
||
D1["页面4"]
|
||
D2["..."]
|
||
end
|
||
|
||
V0 --> M0
|
||
V1 --> M1
|
||
V3 --> M3
|
||
V2 -.->|"缺页时调入"| DISK
|
||
V4 -.->|"缺页时调入"| DISK
|
||
|
||
style VA fill:#e3f2fd,stroke:#1976d2
|
||
style MEM fill:#fff8e1,stroke:#f9a825
|
||
style DISK fill:#fce4ec,stroke:#c62828
|
||
```
|
||
|
||
### 实现基础
|
||
|
||
虚拟存储器的实现依赖两个关键技术：
|
||
1. **[[14_分页存储管理|分页]]或[[15_段式存储管理|分段]]**: 将程序划分为小块，可以部分装入
|
||
2. **[[14_分页存储管理#五、地址变换过程|缺页中断]]**: 访问不在内存的页面时，由OS负责调入
|
||
|
||
---
|
||
|
||
## 二、局部性原理
|
||
|
||
虚拟存储器之所以可行，是因为程序运行时具有**局部性**——程序不会均匀地访问所有地址空间。
|
||
|
||
### 时间局部性 (Temporal Locality)
|
||
|
||
> **含义**: 如果一条指令/数据被访问，那么在不久的将来它很可能**再次被访问**。
|
||
|
||
**典型场景**:
|
||
- 循环中的指令反复执行
|
||
- 频繁访问的变量
|
||
- 栈顶数据的反复操作
|
||
|
||
### 空间局部性 (Spatial Locality)
|
||
|
||
> **含义**: 如果一个存储单元被访问，那么它**附近的单元**也很可能很快被访问。
|
||
|
||
**典型场景**:
|
||
- 顺序执行的指令
|
||
- 数组的顺序遍历
|
||
- 结构体成员的连续访问
|
||
|
||
### 局部性的实际影响：行优先 vs 列优先
|
||
|
||
以二维数组遍历为例，行优先和列优先的性能差异可达 **21.5 倍**：
|
||
|
||
```c
|
||
// 二维数组: int a[1024][1024];
|
||
|
||
// 行优先遍历 (空间局部性好)
|
||
for (int i = 0; i < 1024; i++)
|
||
for (int j = 0; j < 1024; j++)
|
||
sum += a[i][j]; // 访问顺序: a[0][0], a[0][1], a[0][2], ...
|
||
// 连续内存访问，充分利用缓存行
|
||
|
||
// 列优先遍历 (空间局部性差)
|
||
for (int j = 0; j < 1024; j++)
|
||
for (int i = 0; i < 1024; i++)
|
||
sum += a[i][j]; // 访问顺序: a[0][0], a[1][0], a[2][0], ...
|
||
// 每次跳过一整行，频繁缺页/缓存失效
|
||
```
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph RowMajor["行优先遍历"]
|
||
direction LR
|
||
R1["a[0][0]"] --> R2["a[0][1]"] --> R3["a[0][2]"] --> R4["..."]
|
||
style R1 fill:#c8e6c9
|
||
style R2 fill:#c8e6c9
|
||
style R3 fill:#c8e6c9
|
||
end
|
||
|
||
subgraph ColMajor["列优先遍历"]
|
||
direction LR
|
||
C1["a[0][0]"] --> C2["a[1][0]"] --> C3["a[2][0]"] --> C4["..."]
|
||
style C1 fill:#ffcdd2
|
||
style C2 fill:#ffcdd2
|
||
style C3 fill:#ffcdd2
|
||
end
|
||
|
||
RowMajor ---|"性能差异约 21.5 倍"| ColMajor
|
||
```
|
||
|
||
---
|
||
|
||
## 三、请求分页
|
||
|
||
### 基本思想
|
||
|
||
**请求分页 (Demand Paging)** 是最常用的虚拟存储器实现方式：
|
||
- 页面只在**被访问时**才调入内存（而非预装入）
|
||
- 内存不足时，将某些页面**换出**到外存，腾出空间
|
||
|
||
### 页表项扩展
|
||
|
||
在[[14_分页存储管理#四、页表|基本分页]]的基础上，请求分页的页表项增加了**状态位**：
|
||
|
||
| 字段 | 含义 | 说明 |
|
||
|------|------|------|
|
||
| **状态位 (Present/Valid)** | 页面是否在内存 | 1=在内存，0=不在内存 |
|
||
| **访问位 (Reference/Access)** | 页面是否被访问过 | 用于置换算法判断 |
|
||
| **修改位 (Dirty)** | 页面是否被写过 | Dirty=1 时换出需写回外存 |
|
||
| **外存地址** | 页面在外存中的位置 | 用于缺页时调入 |
|
||
|
||
### 缺页中断处理
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A["CPU访问虚拟地址"] --> B{"页面在内存中?<br/>(检查状态位)"}
|
||
B -->|"在内存"| C["正常地址变换，访问数据"]
|
||
B -->|"不在内存"| D["触发**缺页中断**"]
|
||
D --> E["保存CPU现场"]
|
||
E --> F{"外存中存在该页?"}
|
||
F -->|"不存在"| G["终止进程<br/>Segmentation Fault"]
|
||
F -->|"存在"| H{"内存有空闲页框?"}
|
||
H -->|"有空闲"| I["从外存读入该页"]
|
||
H -->|"无空闲"| J["执行**页面置换算法**<br/>选择牺牲页"]
|
||
J --> K{"牺牲页Dirty=1?"}
|
||
K -->|"是"| L["将牺牲页写回外存"]
|
||
K -->|"否"| M["直接覆盖"]
|
||
L --> I
|
||
M --> I
|
||
I --> N["更新页表:<br/>状态位=1, PPN"]
|
||
N --> O["刷新TLB"]
|
||
O --> P["重新执行被中断的指令"]
|
||
|
||
style D fill:#ffcdd2,stroke:#c62828
|
||
style J fill:#fff3e0,stroke:#e65100
|
||
style G fill:#ffcdd2,stroke:#c62828
|
||
```
|
||
|
||
---
|
||
|
||
## 四、页面置换算法
|
||
|
||
当内存中没有空闲页框时，需要选择一个页面换出到外存，为新页面腾出空间。不同的选择策略就是**页面置换算法**。
|
||
|
||
> **示例参数**: 物理内存有 **3 个页框**，页面引用串为：
|
||
> **7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1**
|
||
|
||
### 1. OPT (Optimal) 最佳置换算法
|
||
|
||
**策略**: 换出**将来最长时间不会被使用**的页面。
|
||
|
||
> OPT 是理论算法，因为无法预知未来的页面访问序列。它用于衡量其他算法的上限。
|
||
|
||
**执行过程**:
|
||
|
||
| 访问序列 | 页框0 | 页框1 | 页框2 | 缺页? | 说明 |
|
||
|---------|-------|-------|-------|-------|------|
|
||
| **7** | 7 | - | - | 缺页 | 空闲页框，直接装入 |
|
||
| **0** | 7 | 0 | - | 缺页 | 空闲页框，直接装入 |
|
||
| **1** | 7 | 0 | 1 | 缺页 | 空闲页框，直接装入 |
|
||
| **2** | 7 | 0 | **2** | 缺页 | 换出1（最久后才用） |
|
||
| **0** | 7 | 0 | 2 | 命中 | 0已在内存 |
|
||
| **3** | **3** | 0 | 2 | 缺页 | 换出7（最久后才用） |
|
||
| **0** | 3 | 0 | 2 | 命中 | |
|
||
| **4** | 3 | 0 | **4** | 缺页 | 换出2（最久后才用） |
|
||
| **2** | 3 | **2** | 4 | 缺页 | 换出0（最久后才用） |
|
||
| **3** | 3 | 2 | 4 | 命中 | |
|
||
| **0** | 3 | 2 | **0** | 缺页 | 换出4（最久后才用） |
|
||
| **3** | 3 | 2 | 0 | 命中 | |
|
||
| **2** | 3 | 2 | 0 | 命中 | |
|
||
| **1** | **1** | 2 | 0 | 缺页 | 换出3（最久后才用） |
|
||
| **2** | 1 | 2 | 0 | 命中 | |
|
||
| **0** | 1 | 2 | 0 | 命中 | |
|
||
| **1** | 1 | 2 | 0 | 命中 | |
|
||
| **7** | 1 | **7** | 0 | 缺页 | 换出2（最久后才用） |
|
||
| **0** | 1 | 7 | 0 | 命中 | |
|
||
| **1** | 1 | 7 | 0 | 命中 | |
|
||
|
||
**缺页次数: 9**，缺页率 = 9/20 = **45%**
|
||
|
||
### 2. FIFO (First-In First-Out) 先进先出
|
||
|
||
**策略**: 换出**最早进入内存**的页面。
|
||
|
||
**执行过程**:
|
||
|
||
| 访问序列 | 页框0 | 页框1 | 页框2 | 缺页? | 淘汰队列 |
|
||
|---------|-------|-------|-------|-------|---------|
|
||
| **7** | 7 | - | - | 缺页 | [7] |
|
||
| **0** | 7 | 0 | - | 缺页 | [7,0] |
|
||
| **1** | 7 | 0 | 1 | 缺页 | [7,0,1] |
|
||
| **2** | **2** | 0 | 1 | 缺页 | [0,1,2] 淘汰7 |
|
||
| **0** | 2 | 0 | 1 | 命中 | [0,1,2] |
|
||
| **3** | 2 | **3** | 1 | 缺页 | [1,2,3] 淘汰0 |
|
||
| **0** | 2 | 3 | **0** | 缺页 | [2,3,0] 淘汰1 |
|
||
| **4** | **4** | 3 | 0 | 缺页 | [3,0,4] 淘汰2 |
|
||
| **2** | 4 | **2** | 0 | 缺页 | [0,4,2] 淘汰3 |
|
||
| **3** | 4 | 2 | **3** | 缺页 | [4,2,3] 淘汰0 |
|
||
| **0** | **0** | 2 | 3 | 缺页 | [2,3,0] 淘汰4 |
|
||
| **3** | 0 | 2 | 3 | 命中 | [2,3,0] |
|
||
| **2** | 0 | 2 | 3 | 命中 | [2,3,0] |
|
||
| **1** | 0 | **1** | 3 | 缺页 | [3,0,1] 淘汰2 |
|
||
| **2** | 0 | 1 | **2** | 缺页 | [0,1,2] 淘汰3 |
|
||
| **0** | 0 | 1 | 2 | 命中 | [0,1,2] |
|
||
| **1** | 0 | 1 | 2 | 命中 | [0,1,2] |
|
||
| **7** | **7** | 1 | 2 | 缺页 | [1,2,7] 淘汰0 |
|
||
| **0** | 7 | **0** | 2 | 缺页 | [2,7,0] 淘汰1 |
|
||
| **1** | 7 | 0 | **1** | 缺页 | [7,0,1] 淘汰2 |
|
||
|
||
**缺页次数: 15**，缺页率 = 15/20 = **75%**
|
||
|
||
> **Belady 异常**: FIFO 算法在某些情况下，增加物理页框数反而会导致缺页率**上升**。例如本例中 4 个页框时缺页次数可能比 3 个页框时更多。这是 FIFO 算法的独特缺陷。
|
||
|
||
### 3. LRU (Least Recently Used) 最近最久未使用
|
||
|
||
**策略**: 换出**最近最长时间没有被访问**的页面。
|
||
|
||
**实现方式**:
|
||
- **栈法**: 用一个栈保存页面号，访问某页时将其移到栈顶。栈底就是最久未使用的页面
|
||
- **计数器法**: 每个页面记录最后一次访问的时间，淘汰时间值最小的页面
|
||
|
||
**执行过程**:
|
||
|
||
| 访问序列 | 页框0 | 页框1 | 页框2 | 缺页? | 说明 |
|
||
|---------|-------|-------|-------|-------|------|
|
||
| **7** | 7 | - | - | 缺页 | |
|
||
| **0** | 7 | 0 | - | 缺页 | |
|
||
| **1** | 7 | 0 | 1 | 缺页 | |
|
||
| **2** | 2 | 0 | 1 | 缺页 | 淘汰7(最久未用) |
|
||
| **0** | 2 | 0 | 1 | 命中 | 0被访问，更新时间戳 |
|
||
| **3** | 2 | 0 | 3 | 缺页 | 淘汰1(最久未用) |
|
||
| **0** | 2 | 0 | 3 | 命中 | |
|
||
| **4** | 4 | 0 | 3 | 缺页 | 淘汰2(最久未用) |
|
||
| **2** | 4 | 0 | 2 | 缺页 | 淘汰3(最久未用) |
|
||
| **3** | 4 | 3 | 2 | 缺页 | 淘汰0(最久未用) |
|
||
| **0** | 0 | 3 | 2 | 缺页 | 淘汰4(最久未用) |
|
||
| **3** | 0 | 3 | 2 | 命中 | |
|
||
| **2** | 0 | 3 | 2 | 命中 | |
|
||
| **1** | 0 | 3 | 1 | 缺页 | 淘汰2(最久未用) |
|
||
| **2** | 0 | 2 | 1 | 缺页 | 淘汰3(最久未用) |
|
||
| **0** | 0 | 2 | 1 | 命中 | |
|
||
| **1** | 0 | 2 | 1 | 命中 | |
|
||
| **7** | 0 | 2 | 7 | 缺页 | 淘汰1(最久未用) |
|
||
| **0** | 0 | 2 | 7 | 命中 | |
|
||
| **1** | 1 | 2 | 7 | 缺页 | 淘汰0(最久未用) |
|
||
|
||
**缺页次数: 12**，缺页率 = 12/20 = **60%**
|
||
|
||
### 4. Clock (时钟 / 近似LRU)
|
||
|
||
**策略**: 将所有页面组成一个**循环链表**，每页有一个**访问位 R**。淘汰指针从当前位置开始扫描：
|
||
- R=1：将 R 置 0，指针前移（给第二次机会）
|
||
- R=0：淘汰该页
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph Clock["时钟置换算法 (循环链表)"]
|
||
direction LR
|
||
P0["页0<br/>R=1"]
|
||
P1["页1<br/>R=0"]
|
||
P2["页2<br/>R=1"]
|
||
P3["页3<br/>R=0"]
|
||
end
|
||
|
||
PTR["淘汰指针"] --> P1
|
||
|
||
P0 --> P1
|
||
P1 --> P2
|
||
P2 --> P3
|
||
P3 --> P0
|
||
|
||
style P1 fill:#ffcdd2,stroke:#c62828
|
||
style PTR fill:#fff3e0,stroke:#e65100
|
||
```
|
||
|
||
**执行示例**（简化）:
|
||
- 指针指向页1 (R=0) → 淘汰页1，装入新页，指针前移
|
||
- 指针指向页2 (R=1) → R置0，指针前移
|
||
- 指针指向页3 (R=0) → 淘汰页3
|
||
|
||
**改进型Clock**: 同时考虑 R 和 D (修改位)，优先淘汰 R=0 且 D=0 的页面（不需要写回外存）。
|
||
|
||
| 优先级 | R | D | 淘汰代价 |
|
||
|--------|---|---|---------|
|
||
| 最高 | 0 | 0 | 未访问未修改，直接覆盖 |
|
||
| | 0 | 1 | 未访问但已修改，需写回 |
|
||
| | 1 | 0 | 已访问未修改，再给机会 |
|
||
| 最低 | 1 | 1 | 已访问已修改，最不想淘汰 |
|
||
|
||
### 5. LFU (Least Frequently Used) 最少使用
|
||
|
||
**策略**: 换出**访问次数最少**的页面。
|
||
|
||
- 用计数器记录每个页面的访问次数
|
||
- 淘汰计数器值最小的页面
|
||
- **缺点**: 某页面过去被频繁访问但现在不再使用，仍难以被淘汰
|
||
- **实现开销**: 需要为每个页面维护计数器
|
||
|
||
### 算法对比
|
||
|
||
| 算法 | 策略 | 优点 | 缺点 | 是否有Belady异常 |
|
||
|------|------|------|------|----------------|
|
||
| **OPT** | 淘汰将来最久不用的 | 缺页率最低（理论最优） | 无法实现 | 无 |
|
||
| **FIFO** | 淘汰最早进入的 | 实现简单 | 缺页率高，有Belady异常 | **有** |
|
||
| **LRU** | 淘汰最近最久未用的 | 接近OPT，效果好 | 实现开销大（需时间戳或栈） | 无 |
|
||
| **Clock** | 给访问位R=0的淘汰 | LRU的近似，开销小 | 效果略逊于LRU | 无 |
|
||
| **LFU** | 淘汰访问次数最少的 | 考虑历史频率 | 对访问模式变化响应慢 | 无 |
|
||
|
||
### 算法效果对比（本例）
|
||
|
||
```
|
||
页面引用串: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 (3个物理块)
|
||
|
||
┌──────────┬──────────┬──────────┐
|
||
│ 算法 │ 缺页次数 │ 缺页率 │
|
||
├──────────┼──────────┼──────────┤
|
||
│ OPT │ 9 │ 45% │ ← 理论最优
|
||
│ LRU │ 12 │ 60% │
|
||
│ FIFO │ 15 │ 75% │ ← 效果最差
|
||
└──────────┴──────────┴──────────┘
|
||
```
|
||
|
||
---
|
||
|
||
## 五、内存分配策略
|
||
|
||
### 物理页框分配方式
|
||
|
||
| 方式 | 说明 |
|
||
|------|------|
|
||
| **平均分配** | 将可用页框平均分配给所有进程 |
|
||
| **按比例分配** | 按进程大小占总需求的比例分配 |
|
||
| **考虑优先权** | 高优先级进程分配更多页框 |
|
||
|
||
**按比例分配公式**:
|
||
|
||
$$a_i = \frac{s_i}{\sum s_j} \times m$$
|
||
|
||
其中 $s_i$ 是进程 $i$ 的页面数，$m$ 是可用页框总数。
|
||
|
||
### 置换策略
|
||
|
||
| 策略 | 说明 | 特点 |
|
||
|------|------|------|
|
||
| **固定分配局部置换** | 每个进程固定页框数，只能在自己的页面中置换 | 公平，但可能浪费 |
|
||
| **可变分配全局置换** | 从全局空闲页框池中分配，可换出任何进程的页面 | 灵活，但可能影响其他进程 |
|
||
| **可变分配局部置换** | 进程页框数可调，但只能在自己的页面中置换 | 折中方案 |
|
||
|
||
---
|
||
|
||
## 六、抖动与工作集
|
||
|
||
### 抖动 (Thrashing)
|
||
|
||
当进程分配到的页框数**不足以**容纳其工作集时，会频繁发生缺页，CPU 大量时间花在页面置换上，利用率急剧下降——这种现象称为**抖动**。
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A["进程增多"] --> B["每个进程分到的页框减少"]
|
||
B --> C["缺页率上升"]
|
||
C --> D["CPU利用率下降"]
|
||
D --> E["调度器增加进程数<br/>(以为CPU空闲)"]
|
||
E --> B
|
||
|
||
style C fill:#ffcdd2,stroke:#c62828
|
||
style D fill:#ffcdd2,stroke:#c62828
|
||
```
|
||
|
||
CPU 利用率随进程数的变化：
|
||
|
||
```
|
||
CPU利用率
|
||
↑
|
||
100%│ ╱‾‾‾‾╲
|
||
│ ╱ ╲
|
||
│ ╱ ╲ ← 抖动区域
|
||
│ ╱ ╲
|
||
│ ╱ ╲
|
||
│╱ ╲
|
||
└──────────────────────────→ 进程数
|
||
↑
|
||
最佳点
|
||
```
|
||
|
||
### 工作集 (Working Set)
|
||
|
||
**工作集**的定义：在最近 $\Delta$ 时间内，进程实际访问的页面集合。
|
||
|
||
$$W(t, \Delta) = \text{在时刻 } t-\Delta \text{ 到 } t \text{ 之间访问的页面集合}$$
|
||
|
||
**示例**:
|
||
|
||
页面访问序列: ... 2, 6, 1, 5, 7, 7, 7, 2, ...
|
||
|
||
设 $\Delta = 5$（最近 5 次访问），当前访问页面 2：
|
||
- 最近 5 次访问: {5, 7, 7, 7, 2}
|
||
- 工作集 = {2, 5, 7}，大小 = 3
|
||
|
||
**工作集策略**: 为每个进程分配**不少于其工作集大小**的页框数，就可以避免抖动。
|
||
|
||
### 工作集模型的应用
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A["监控每个进程的工作集"] --> B{"总工作集 ≤ 物理页框数?"}
|
||
B -->|"是"| C["正常运行，不会抖动"]
|
||
B -->|"否"| D["可能发生抖动"]
|
||
D --> E["挂起某些进程<br/>释放页框"]
|
||
E --> B
|
||
|
||
style D fill:#ffcdd2,stroke:#c62828
|
||
style C fill:#c8e6c9,stroke:#2e7d32
|
||
```
|
||
|
||
---
|
||
|
||
## 七、请求分段
|
||
|
||
### 基本思想
|
||
|
||
**请求分段**是虚拟存储器在[[15_段式存储管理|分段]]基础上的实现：
|
||
- 段不需要全部装入内存
|
||
- 访问到不在内存的段时，触发**缺段中断**，从外存调入
|
||
|
||
### 与请求分页的对比
|
||
|
||
| 对比项 | 请求分页 | 请求分段 |
|
||
|--------|---------|---------|
|
||
| 调入/调出单位 | 页面（固定大小） | 段（可变大小） |
|
||
| 碎片 | 内碎片 | 外碎片 |
|
||
| 共享 | 以页为粒度 | 以段为粒度 |
|
||
| 中断类型 | 缺页中断 | 缺段中断 |
|
||
| 实现复杂度 | 较简单 | 较复杂 |
|
||
|
||
---
|
||
|
||
## 八、完整计算示例
|
||
|
||
### 综合例题
|
||
|
||
> 某系统采用请求分页存储管理，页面大小为 4KB，物理内存有 4 个页框。某进程的页面访问序列为：**0, 1, 4, 2, 0, 2, 6, 5, 1, 2, 3, 2, 1, 2, 6, 5, 2, 1, 3, 6**。分别用 FIFO 和 LRU 算法计算缺页次数。
|
||
|
||
**FIFO 算法**:
|
||
|
||
| 访问 | 页框0 | 页框1 | 页框2 | 页框3 | 缺页? |
|
||
|------|-------|-------|-------|-------|-------|
|
||
| 0 | 0 | - | - | - | 缺页 |
|
||
| 1 | 0 | 1 | - | - | 缺页 |
|
||
| 4 | 0 | 1 | 4 | - | 缺页 |
|
||
| 2 | 0 | 1 | 4 | 2 | 缺页 |
|
||
| 0 | 0 | 1 | 4 | 2 | 命中 |
|
||
| 2 | 0 | 1 | 4 | 2 | 命中 |
|
||
| 6 | 6 | 1 | 4 | 2 | 缺页(淘汰0) |
|
||
| 5 | 6 | 5 | 4 | 2 | 缺页(淘汰1) |
|
||
| 1 | 6 | 5 | 1 | 2 | 缺页(淘汰4) |
|
||
| 2 | 6 | 5 | 1 | 2 | 命中 |
|
||
| 3 | 6 | 5 | 1 | 3 | 缺页(淘汰2) |
|
||
| 2 | 2 | 5 | 1 | 3 | 缺页(淘汰6) |
|
||
| 1 | 2 | 5 | 1 | 3 | 命中 |
|
||
| 2 | 2 | 5 | 1 | 3 | 命中 |
|
||
| 6 | 2 | 6 | 1 | 3 | 缺页(淘汰5) |
|
||
| 5 | 2 | 6 | 5 | 3 | 缺页(淘汰1) |
|
||
| 2 | 2 | 6 | 5 | 3 | 命中 |
|
||
| 1 | 2 | 6 | 5 | 1 | 缺页(淘汰3) |
|
||
| 3 | 3 | 6 | 5 | 1 | 缺页(淘汰2) |
|
||
| 6 | 3 | 6 | 5 | 1 | 命中 |
|
||
|
||
**FIFO 缺页次数: 14**
|
||
|
||
**LRU 算法**:
|
||
|
||
| 访问 | 页框0 | 页框1 | 页框2 | 页框3 | 缺页? |
|
||
|------|-------|-------|-------|-------|-------|
|
||
| 0 | 0 | - | - | - | 缺页 |
|
||
| 1 | 0 | 1 | - | - | 缺页 |
|
||
| 4 | 0 | 1 | 4 | - | 缺页 |
|
||
| 2 | 0 | 1 | 4 | 2 | 缺页 |
|
||
| 0 | 0 | 1 | 4 | 2 | 命中 |
|
||
| 2 | 0 | 1 | 4 | 2 | 命中 |
|
||
| 6 | 0 | 1 | 6 | 2 | 缺页(淘汰4) |
|
||
| 5 | 0 | 5 | 6 | 2 | 缺页(淘汰1) |
|
||
| 1 | 1 | 5 | 6 | 2 | 缺页(淘汰0) |
|
||
| 2 | 1 | 5 | 6 | 2 | 命中 |
|
||
| 3 | 1 | 5 | 3 | 2 | 缺页(淘汰6) |
|
||
| 2 | 1 | 5 | 3 | 2 | 命中 |
|
||
| 1 | 1 | 5 | 3 | 2 | 命中 |
|
||
| 2 | 1 | 5 | 3 | 2 | 命中 |
|
||
| 6 | 1 | 5 | 3 | 6 | 缺页(淘汰2) |
|
||
| 5 | 1 | 5 | 3 | 6 | 命中 |
|
||
| 2 | 2 | 5 | 3 | 6 | 缺页(淘汰1) |
|
||
| 1 | 2 | 1 | 3 | 6 | 缺页(淘汰5) |
|
||
| 3 | 2 | 1 | 3 | 6 | 命中 |
|
||
| 6 | 2 | 1 | 3 | 6 | 命中 |
|
||
|
||
**LRU 缺页次数: 12**
|
||
|
||
---
|
||
|
||
## 九、小结
|
||
|
||
```mermaid
|
||
mindmap
|
||
root((虚拟存储器))
|
||
基本思想
|
||
虚拟空间>物理内存
|
||
部分装入
|
||
按需调入调出
|
||
局部性原理
|
||
时间局部性
|
||
空间局部性
|
||
行优先vs列优先
|
||
请求分页
|
||
页表扩展状态位
|
||
缺页中断处理
|
||
页面置换
|
||
置换算法
|
||
OPT理论最优
|
||
FIFO简单但有Belady异常
|
||
LRU效果好但开销大
|
||
Clock近似LRU
|
||
LFU最少使用
|
||
内存分配
|
||
平均/按比例/优先权
|
||
固定/可变分配
|
||
局部/全局置换
|
||
抖动与工作集
|
||
频繁缺页=抖动
|
||
工作集=近期访问页面集
|
||
帧数≥工作集大小
|
||
```
|
||
|
||
---
|
||
|
||
## 思考题
|
||
|
||
1. **概念理解**: 为什么说虚拟存储器的基础是局部性原理？如果没有局部性，虚拟存储器还能工作吗？
|
||
|
||
2. **算法对比**: 对于页面引用串 1,2,3,4,1,2,5,1,2,3,4,5（3个物理块），分别计算 OPT、FIFO、LRU 的缺页次数。是否存在Belady异常？
|
||
|
||
3. **工作集**: 某进程页面访问序列为 2,6,1,5,7,7,7,2,5,1,3,1,5,7,2,5，设 $\Delta=5$，求各时刻的工作集大小。
|
||
|
||
4. **抖动分析**: 某系统物理内存可容纳 10 个工作集页面。目前有 5 个进程，工作集大小分别为 {3,2,2,1,3}。此时再增加一个工作集大小为 3 的进程，系统是否会发生抖动？
|
||
|
||
5. **综合题**: 在请求分页系统中，页面大小 4KB，页表项 4 字节，虚拟地址 32 位，物理地址 32 位。
|
||
- 一级页表有多大？
|
||
- 如果采用二级页表，页目录和页表各多大？
|
||
- 如果 TLB 命中率 95%，TLB 访问 10ns，内存访问 100ns，有效访问时间是多少？
|
||
|
||
---
|
||
|
||
## 关联笔记
|
||
|
||
- [[14_分页存储管理]] — 分页基础、页表结构、地址变换
|
||
- [[15_段式存储管理]] — 分段思想、段页式
|
||
- [[11_处理机调度]] — 进程调度与抖动的关系
|
||
|
||
---
|
||
|
||
**上一讲**: [[15_段式存储管理]]
|
||
**目录**: [[00_课程导航]]
|