虚拟内存技术
请求分页管理方式
请求分页是基于基本分页系统基础之上，为了支持虚拟存储器功能增加了请求调页和页面置换功能。与普通分页系统不同之处主要在于：
- 当程序执行过程中，请求信息不在内存中，则由操作系统将信息从外存调入内存
- 将外存中页面调入内存时，若内存中空间足够，则直接调入，若内存不够，则由操作系统根据某些指标将内存中某些页面置换到外存中。
基于以上不同，请求分页系统的页表相对于基本分页系统，每个页表项增加了4个字段。
- 状态位，用于标识该页是否调入内存。
- 访问字段，用于记录该页面一段时间的访问次数，或者该页面多长时间未被访问。
- 修改位，标识该页面在内存中是否修改过，若修改过，则置换时需要重新写入外存。
- 外存地址，指出该页面在外存中的地址。
在请求分页系统中，当访问的页面不在内存中，则产生一个缺页中断。此时发生缺页的进程会被阻塞，然后操作系统将外存中页面调入内存，当内存没有空闲块时，使用页面置换算法，淘汰某个页面。调页完成，该进程被唤醒。
与一般中断相比，缺页中断的区别：
- 在指令执行期间而非一条指令执行完成后产生和处理中断信号，属于内部中断
- 一条指令执行期间可能产生不止一次缺页中断
页面置换算法
- 最佳置换算法
最佳置换算法选择的被淘汰页面是以后用不使用的页面，或者在最长时间内不再被访问的页面，保证获得最低的缺页率。但是由于无法预知进程中哪个页面是未来最长时间不在访问的，因此该算法无法实现。该算法可被用于评价其他算法。
- 先进先出页面置换算法
该算法优先淘汰最早进入内存的页面，即在内存中驻留时间最长的页面。实现简单，只需把调入内存的页面根据次序链接成队列。但是该算法与进程实际运行规律不符。在进程中有的页面经常被访问到。
同时该算法还会产生所分配物理块数增大而页故障数不减反增的异常。它是由Belady于1969年发现，故称为Belady异常。
image.png
- 最近最久未使用置换算法
选择最近最长时间未访问过的页面予以淘汰，他认为过去一段时间内未被访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，记录页面上次被访问以来所经历的时间。
最近最久未使用置换算法性能较好，但需要寄存器和栈的硬件支持。它属于堆栈类算法。理论证明堆栈类算法不可能出现Belady异常。
- 时钟置换算法
最近最久未使用置换算法性能较好，但实现较为困难，且开销大。先进先出页面置换算法，实现简单，但性能较差。因此操作系统的设计者尝试了许多算法，这些算法被称为CLOCK算法的变体，因为这类算法要循环扫描缓冲区，像时针转动，因此被称为CLOCK算法。
简单的CLOCK算法给每帧关联一个附加位，称为使用位。当某页首次装入内存时，将该页的使用位设置为1，当该页随后再被访问到时，其使用位也被置为1。对于置换算法，用于替换的候选帧集合可被视为一个循环缓冲区，并有一个指针与之关联。当某一页被替换时，该指针设置成指向缓冲区中的下一帧。当需要替换某一页时，操作系统扫描缓冲区，查找使用位被置为0的一帧。每当遇到使用位为1的帧，将其使用位置为0。这样的话，当缓冲区存在使用位为0的帧，则置换出第一个扫描到的使用位为0的帧，若所有页使用位都为1，扫描一轮后，所有使用位均为0，替换掉最初位置上的帧。
CLOCK算法性能接近最近最久未使用置换算法，通过在使用位基础上再添加一个修改位，可得到改进型CLOCK算法。
改进型算法中每一帧都处于一下四种情况之一：
- 最近未被访问，也未被修改（u=0,m=0）
- 最近被访问，但未被修改（u=1,m=0）
- 最近未被访问，但被修改（u=0,m=1）
- 最近被访问，被修改（u=1,m=1）
算法执行步骤如下：
- 从指针当前位置开始，扫描缓冲区，不对使用位做修改，选择遇到的第一个u=0,m=0的帧用于替换
- 若第一步失效，重新扫描，选择第一个u=0,m=1的帧。扫描过程将帧使用位置为0
- 若第二步失效，指针此时位于最初始位置，所有帧使用位均为0.重复第一步和第二步。
改进的地方在于替换时首选未被修改过的帧，这是因为修改过的页替换时需要写入外存。
