1 背景
在物理内存分配方法中，要求执行指令必须在物理内存中，满足这一要求的方法是将整个进程放在内存中。这使得程序的大小被限制在物理内存的大小以内，然而在许多情况下，并不需要将整个程序放到内存中。能够执行只有部分在内存中的程序可以带来许多好处：
- 程序不再受现有的物理内存空间限制。
- 更多的程序可以同时执行，CPU的利用率也相应增加 。
- 由于载入或交换每个用户程序到内存所需的I/O更少，用户程序会运行得更快。
虚拟内存（virtual memory）将用户逻辑内存与物理内存分开，为程序员提供了巨大的虚拟内存，这使得编程更加容易。使程序员不再需要担心可用的有限物理内存空间，只需要关注所要解决的问题。进程的虚拟地址空间就是进程如何在内存中存放的逻辑视图，如下图所示。除了将逻辑内存与物理内存分开，虚拟内存也允许文件和内存通过共享页尾两个或多个进程所共享。
2 按需调页
一个执行程序从磁盘载入内存，一种选择是在程序执行时，将整个程序载入；另一种选择是在需要时才调入相应的页。这种技术称为按需调页(demand paging)，常为虚拟内存系统所采用。按需调页技术类似于使用交换的分页系统，不过不是将整个进程换入内存，而是在需要页时才将它调入内存。
当换入进程时，调页程序推测在该进程再次换出之前会用到哪些页，这种方案需要一定形式的硬件支持来区分哪些页在内存里，哪些页在磁盘上。当该位设置为“有效”时，该值表示相关的页既合法且也在内存中；当该位设置为“无效”时，该值表示相关的页为无效或者有效但是在磁盘上。当进程试图访问无效页时，会产生缺页异常，处理这种错误的程序比较简单，如下图所示。
3 局部页面置换
页面置换采用如下办法：如果没有空闲帧，就查找当前没有使用的帧，并将其释放。释放一个帧的方法是：将其内容写到交换空间，并改变页表以表示该页不在内存中。修改缺页异常的处理程序如下：
- 1 查找所需页咋磁盘上的位置
- 2 查找一个空闲帧：a 如果有空闲帧就使用该帧；b 如果没有空闲帧，就使用页面置换算法选择一个牺牲帧；c 将牺牲帧的内容写到磁盘上
- 3 将所需页读入空闲帧，改变页表和帧表
- 4 重启用户进程
页面置换过程如下图所示。
页面置换是按需调页的基础，它分开了逻辑内存和物理内存，对于按需调页，逻辑空间的大小不再受物理内存所限制。为了实现按需调页，必须解决两个主要问题：必须开发帧分配算法（frame-allocation algorithm）和页面置换算法（page-replacement algorithm）。如果在内存中有多个进程，那么必须决定为每个进程分配多少帧。当需要页面置换时，必须选择要置换的帧。
衡量页面置换算法的指标是缺页率：针对特定内存引用序列，运行某个置换算法，并计算出也错误的数量。为了知道页错误的数量，还需要知道可用帧的数量，因为随着可用帧数量的增加，页错误的数量一般会相应地减少。如下图所示。
在说明各种页面置换算法之前，这里先介绍Belady异常（Belady’s anomaly）。该现象是指：对有的页面置换算法，缺页率可能会随着所分配的帧数增加而增加，而原期望为增加内存会改善其性能。造成这种现象的原因在于：置换算法的特征与进程访问内存的特征相矛盾，被置换出的页面并不一定是进程近期不会访问的。
| 置换算法 | 思路 | 实现 | 特征 |
|---|---|---|---|
| 最优页面置换算法（OPT） | 置换在未来最长时间不访问的页面 | 计算内存中每个逻辑页面的下次访问时间，选择未来最长时间不访问的页面 | 缺页最少，理想情况，无法实现，可作为性能评价依据 |
| 先进先出算法（FIFO） | 选择在内存驻留时间最长的页面进行置换 | 维护记录逻辑页面的链表，按驻留时间排序，链首最长链尾最短，缺页时置换链首，新页面加到链尾 | 实现简单，性能较差，Belady现象 |
| 最近最久未使用算法（LRU） | 选择最长时间没有被引用的页面进行置换 | 计算内存中每个逻辑页面上的上次访问时间，选择上次使用到当前时间最长的页面 | 需要硬件支持，反向OPT |
| 时钟置换算法（Clock） | 对页面访问次数进行大致统计 | 在页表项记录页面访问情况，缺页时从指针处开始顺序查找未被访问的页面进行置换 | LRU和FIFO算法的妥协 |
| 最不常用算法（LFU） | 置换访问次数最少的页面 | 每个页面设置一个访问计数，访问页面时计数加一，缺页时置换计数最小的页面 | 开销大，开始频繁使用后来不使用的页面很难置换 |
4 帧分配
帧分配策略收到多方面的限制，所分配的帧不能超过可用帧的数量，也必须分配至少最少数量的帧。最少数量帧会影响性能，随着分配给每个进程的帧数量的减少，缺页率会增加，从而减慢进程的执行。如果指令完成之前出现缺页异常，那么该指令必须重新执行。帧的最少数量是由给定的计算机结构定义的。
帧分配算法有平均分配（equal allocation）和比例分配（proportional allocation）。对于给n个进程分配给m个帧，平均分配算法会给每个进程分配m/n个帧，但是该算法没有考虑到不同进程需要不同数量的帧。所以可以根据进程大小或者进程优先级，将不同数量的帧分配给每个进程。
当有多个进程竞争帧时，可将页面置换算法分为两大类：全局置换（global replacement）和局部置换（local replacement）。全局置换允许一个进程从所有帧集合中选择一个置换帧，不管是否分配给其他进程。局部置换要求每个进程仅从其自己的分配帧中进行选择。全局置换算法的一个问题是进程不能控制进程缺页率，局部置换算法没有这个问题，但是由于不能使用其他进程的不常用内存，会阻碍进程执行，所以全局置换通常会有更好的系统吞吐量，而且更为常用。
5 全局页面置换
进程在不同阶段的内存需求是变化的，所以分配给进程的内存也需要在不同阶段有所变化，全局置换算法就是要确定分配给进程的物理页面数量。CPU利用率与并发进程数存在相互促进和制约的关系，当进程数少时，提高并发进程数可以提高CPU利用率，而并发进程的内存访问会降低访问的局部性特征，导致缺页率上升和CPU利用率下降，即抖动问题（thrashing），如下图所示。局部性特征包括时间局部性（程序即将用到的信息可能就是目前正在使用的信息）和空间局部性（程序即将用到的信息可能与目前正在使用的信息在空间上相邻或者临近）。
为了避免抖动问题，可以采用工作集合模型（working-set model），该模型定义了进程执行的局部模型，即一个进程实际正在使用多少帧。如果分配的帧数少于现有局部的大小，那么进程会抖动。该模型使用参数\Delta 定义工作集合窗口，其思想是检查最近\Delta个页的引用，成为工作集合。工作集合的精度与\Delta的选择有关，如果太小不能包含整个局部，如果太大可能包含多个局部。所以工作模型的困难之处在于如何跟踪工作集合。
由于工作集合模型对于控制抖动问题的处理不是很灵活，一种更为直接的方法是缺页率模型（page-fault frequency model）。思路是为进程期望的缺页率设置上限和下限，如果缺页率超过上限，那么分配更多的帧；如果缺页率低于下限，那么移走帧。如果缺页率增加且没有空闲帧，那么必须选择暂定一个进程。如下图所示。
进程的工作集合和缺页率有着直接的关系，随着进程对代码和数据的引用从一个局部切换到另一个局部，进程的工作集合也在随之改变。如果有足够的内存来存放进程的工作集合，即没有发生抖动现象，那么进程的缺页率会随着时间在波峰和波谷之间交替。如下图所示。
全局页面置换和局部页面置换的最大区别在于分配给进程的帧是否是固定的
