虚拟内存是一种允许进程部分装入内存就可以执行的技术。
局部性原理 : 时间局部性，空间局部性。
只有运行的部分程序需要在内存中。

程序的局部性原理

在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。

• 程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。
• 子程序调用将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。
• 程序中存在许多循环结构，循环体中的指令被多次执行。
• 程序中还包括许多对数据结构的处理，如对连续的存储空间——数组的访问，往往局限于很小的范围内。

时间局部性：

- 由于程序中存在着大量的循环操作
- 某条指令一旦执行，则不久该指令可能再次被执行；
- 某个存储单元被访问，则不久该存储单元可能再次被访问。

空间局部性：

- 由于程序的顺序执行
- 一旦程序访问了某个存储单元，则其附近的存储单元也最有可能被访问。 即程序在一段时间内所访问的地址，可能集中在一定的范围内

背景

逻辑地址空间能够比物理地址空间大。
必须允许页面能够被换入和换出
虚拟内存能够通过以下方法来实现：请求页式，请求段式。

虚拟存储器的特征

• 离散性:在内存分配时采用离散的分配方式，是虚拟存储器的最基本的特征。
• 多次性:一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。是虚拟存储器最重要的特征。
• 对换性:作业运行过程中信息在内存和外存的对换区之间换进、换出。
  虚拟性:从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

分页请求系统

在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的虚拟存储系统
需解决:
取页–将哪部分装入内存
置页–将调入的页放在什么地方
淘汰–内存不足时，将哪些页换出内存

页表机制

在分页的页表机制上形成
增加若干信息项，供程序(数据)在换进、换出时参考

• 状态位（存在位P）：指示该页是否已调入内存。
• 访问字段A：记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。
• 修改位M：表示该页在调入内存后是否被修改过。
• 外存地址：指出该页在外存上的地址，供调入该页时使用。

缺页中断机构

每当所要访问的页面不在内存时，便产生一缺页中断(page fault)，请求OS将所缺页调入内存。缺页中断作为中断，童颜需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。
与一般中断的主要区别在于：

• 缺页中断机构在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。
• 缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。
• 一条指令在执行期间，可能产生多次缺页中断。

地址变换机构

在分页系统地址变换机构的基础上，增加了:
产生和处理缺页中断
页面置换功能等

• 查找页表来确定此次地址访问是否合法
• 如果不合法,则中止该进程; 否则如果是发生了缺页,则需要将其调入内存
• 找到一个空闲物理块
• 启动磁盘,把该页读入内存
• 读磁盘结束后,修改页表以指出该页已在内存中
• 重新开始执行刚才发生缺页中断的指令,这时它可以访问刚才调入的页

页面调入策略

• 为能使进程运行，事先需将一部分要执行的程序和数据调入内存
• 调入页面的时机
  • 预调页策略：
    • 主动的页面调入策略，即把那些预计很快会被访问的程序或数据所在的页面，预先调入内存。
      • 预测的准确率不高（50%），主要用于进程的首次调入。也有的系统将预调页策略用于请求调页

缺页率

假定作业Ji共有m页，系统分配给它的主存块为n块，这里m>n。
如果作业Ji执行过程中总的内存访问次数为A, 成功访问的次数为S，不成功的访问次数为F(产生缺页中断的次数),则:
A=S+F
缺页率: f=F/A

页面置换算法

• 最佳算法(OPT: optimal)
• 先进先出算法(FIFO)
  BeLady现象
• 最近最久未使用算法(LRU: Least Recently Used)
• LRU的近似算法

计数器实现LRU

每一个页表项 有一个时间域，给CPU增加一个计数器，每次访问内存，该计数器值加1。如果某一页被访问，则把计数器值拷贝到该页的时间域中。
当需要进行页面置换时，查看页表中每一页的时间域，选择该值最小的页面换出去.

特点：
每次内存访问时需增加一次写内存（写页表中某一页的时间域）
页面替换时需检索页表以找到时间域最小的页面。

栈实现LRU

栈实现—用一个双向链表实现一个记录页号的栈。
被访问的页移到栈顶。
栈底的页是最近最少被访问的。
不用为置换进行查找。
每次把一个页号从栈中移动到栈顶，需修改几个指针