Lab 3：虚拟内存管理

计算机系统时常出现内存空间不够用，为了解决此问题，可以使用以下办法：

• 覆盖（overlay）：应用程序手动把需要的指令和数据保存在内存中
• 交换（swapping）：操作系统自动把暂时不能执行的程序保存到外存中
• 虚拟存储：在有限容量的内存中，以页为单位自动装入更多更大的程序

局部性原理（principle of locality）：程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。具体来说，体现在以下方面：

• 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内。
• 空间局部性：当前指令和临近的几条指令，当前访问的数据和临近的几个数据都集中在一个较小区域内。
• 分支局部性：一条跳转指令的两次执行，很可能跳到相同的内存位置。

局部性原理的意义在于：从理论上来说，虚拟存储技术是能够实现的，而且可取得满意的效果。

虚拟存储的思路是将不常用的部分内存块暂存到外存。具体来说：

• 装载程序时：只将当前指令执行需要的部分 页面 或 段 装入内存
• 指令执行中需要的指令或数据不在内存（称为缺页或缺段）时：处理器通知操作系统将相应的 页面 或 段 调入内存。
• 操作系统将内存中暂时不用的页面或段保存到外存：通过页面置换算法。

具体实现方式包括：

• 虚拟页式存储：在页式存储管理的基础上，增加请求调页和页面置换
• 虚拟段式存储

页面置换算法

当出现缺页异常时，需调入新页面而内存已满时，页面置换算法选择被置换的物理页面。页面置换算法大致分为两类：

• 局部页面置换算法：置换页面的选择范围仅限于当前进程占用的物理页面内
  • 最优算法
  • 先进先出算法
  • 最近最久未使用算法
  • 时钟算法
  • 最不常用算法
• 全局页面置换算法：置换页面的选择范围是所有可换出的物理页面
  • 工作集算法
  • 缺页率算法

最优页面置换算法（OPT，optimal）是指置换在未来最长时间不访问的页面。

先进先出算法（First-In First-Out，FIFO）是指选择在内存驻留时间最长的页面进行置换。

最近最久未使用算法（Least Recently Used，LRU）是指选择最长时间没有被引用的页面进行置换。如果某些页面长时间未被访问，则它们在将来还可能会长时间不会访问。

LRU 算法的可能实现方式：

• 页面链表：系统维护一个按最近一次访问时间排序的页面链表，链表首节点是最近刚刚使用过的页面，链表尾节点是最久未使用的页面，访问内存时，找到相应页面，并把它移到链表之首，缺页时，置换链表尾节点的页面。
• 活动页面栈：访问页面时，将此页号压入栈顶，并将栈内相同的页号抽出；缺页时，置换栈底的页面。

时钟置换算法（Clock）是 FIFO 和 LRU 的折中，其仅对页面的访问情况进行大致统计。具体来说，各页面组织成环形链表，指针指向最先调入的页面，访问页面时，在页表项记录页面访问情况，缺页时，从指针处开始顺序查找未被访问的页面进行置换。

实验

实现基于分页机制的虚拟内存管理，要建立缺页异常处理机制，实现先进先出页面置换算法（First-In First-Out）。