# 虚拟存储

# 虚拟内存

在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理主存大得多的、可寻址的 “主存储器”

一般用于分页存储管理

虚拟地址空间虚拟页面通常分为未分配、分配且在内存、分配但不在内存三种

# 程序执行的局部性

程序执行的局部性是指在程序运行期间，对内存的访问呈现出一定的局部特性，即对某些地址范围或数据集合的频繁访问。局部性主要分为两种类型：时间局部性（Temporal Locality）和空间局部性（Spatial Locality）。

1. 时间局部性（Temporal Locality）：
   • 时间局部性指的是在一段时间内，如果某个地址被访问，那么在不久的将来它很可能会再次被访问。
   • 典型的例子是循环结构，其中的变量在每次迭代中都被重复使用。
2. 空间局部性（Spatial Locality）：
   • 空间局部性指的是在一段时间内，如果某个地址被访问，那么附近的地址很可能也会被访问。
   • 典型的例子是数组访问，数组中相邻的元素通常在内存中也是相邻的，因此很可能在短时间内被连续访问。

# 请求分页存储管理

# 页面装入策略

通常使用请页式，仅当需要访问程序和数据时，通过缺页中断并由缺页中断处理分配页框，并将所需页面装入主存

• 页表中的页面不在内存中的后果
  • 若进程的生命周期都不访问该页面，则无影响
  • 若进程在执行过程中访问不在内存中的页面，则产生缺页中断 / 异常，从而陷入操作系统，执行相应的缺页中断处理程序。

操作系统对缺页异常的处理:

• 若为非法地址访问，则终止程序；
• 若是合法地址访问，但页面不在内存，则：
  • 获得空闲页框
  • 若不存在空闲页框，则需进行页面替换
  • 启动 I/O 操作，将页面从磁盘载入内存中的空闲页框；
  • 修改页表中的对应表项，填入页框号，将 valid-invalid 位置 1.
  • 重启由于缺页异常而被中断的指令

# 请求分页的性能

缺页率$0\leq p\leq1$

有效访问时间$EAT$

$\lambda$ 为访问快表的时间 / 更新快表的时间

$t$ 为访问内存的时间

$\epsilon$ 为缺页中断处理时间

1. 页在内存且快表命中 $EAT=\lambda+t$
2. 页在内存但不在快表$EAT=快表检索时间+访问页表+修改更新页表+访问内存=2*(\lambda+t)$
3. 页面不在内存$EAT=快表检索时间+访问页表时间+缺页中断处理时间+修改更新快表时间+访问页面物理内存时间=2*(\lambda+t)+\epsilon$

考虑快表命中率和缺页率的公式为 (a 为快表命中率)

$$EAT=\lambda+at+(1-a)\{t+p*(\lambda+t+\epsilon)+(1-p)*(\lambda+t)\}$$

# 请求分页虚实地址转换过程

# 页面分配

# 固定分配

进程的生命周期中，保持页框数固定不变

# 可变分配

进程的生命周期中，分配的页框数可以随着进程的执行而变化

页面替换算法的目标是最小化缺页异常的次数

# 页面替换算法

全局替换

• 页面替换算法的作用范围是整个系统，不考虑进程属主

局部替换

• 页面替换算法的作用范围局限于进程自身

# 最佳页面替换算法 (OPT)

淘汰以后不再访问的页，或距离现在最长时间后要访问的页面

# 先进先出页面替换算法 (FIFO)

淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面

# 最近最少用页面替换算法 (LRU)

淘汰的页面是最近一段时间内最久未被访问的那一页

# 时钟页面替换算法 (CLOCK)

• 进入主存的页面构造成循环队列
• 指针给出了下一个可能被淘汰的候选对象
• 主存中的任何一个页面被访问时，其引用位置 1
• 淘汰页面时，指针从当前位置指向的页面开始扫描循环队列，把遇到的引用位为 1 的页面的引用位清 0，并继续向前扫描，如遇到引用位为 0 的页面，则淘汰该页面，指针指向下一个页面

# 工作集理论

工作集是指在某个时间间隔内访问的页面集，随着时间的变化而变化

记$W(t,\Delta)$ 表示时刻$t-\Delta$ 到时刻$t$ 之间所访问的页面集合

为保证程序正常运行，需要将程序的工作集调入内存，当内存不能容纳所有进程的工作集时，会发生抖动现象

# 请求分段存储管理

• 当作业调度运行时，首先把当前需要的段装入内存，在执行过程中访问到不在内存的段时再将其动态装入
• 当所需段不在主存，发生缺段中断

# 请求段页式存储管理

• 虚地址以程序的逻辑结构划分成段
• 实地址划分成固定长度的页框
• 将每一段的线性地址空间划分成页框大小一样的页面
• 逻辑地址分为三部分：段号、段内页号、页内偏移
• 地址转换过程与段页式存储管理类似，加入了缺段中断和缺页中断处理