虚拟内存
虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。
页面置换算法
1. 最优页面置换算法
此算法不可能实现。在发生缺页中断的时候，在内存中的页面有的很快就会被访问，而有的页面可能要到10、100、1000条指令后才会被访问。此时要置换最迟被访问的页面，把因调用被替换的页面而引起的中断推迟到将来，越久越好。当缺页中断发生时，操作系统无法知道各个页面下一次将在什么时候被访问，因此这个算法是无法被实现的。
这个算法可以用来对其他可实现算法的性能进行比较。
2. 最近未使用页面置换算法（NRU）(Not Recently Used)
当页面被访问（读或写）时设置R位，页面被写入（修改）时设置M位。
当启动一个进程时，它的所有页面的两个位都由操作系统设为0，R位被定期地（比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面。
当发生缺页中断时，操作系统检查所有的页面并根据它们当前的R位和M位的值，把它们分为4类：
第0类：没有被访问，没有被修改。
第1类：没有被访问，已被修改（M）。
第2类：已被访问，没有被修改（R）。
第3类：已被访问，已被修改（RM）。
当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。
NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。
3. 先进先出页面置换算法（FIFO）
开销同样较小的FIFO算法，最新进入的页面放在表尾，最早进入的页面放在表头。当缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。这种算法的缺点是可能会把有用的页面淘汰掉。
4. 第二次机会页面置换算法（SC）（Second Chance）
FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：
当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。
5. 时钟页面置换算法（CLOCK）
第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。
6. 最近最少使用页面置换算法（LRU）（Least Recently Used）
在缺页中断发生时，置换未使用时间最长的页面。
LRU理论上是可以实现的，但是代价很高。维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。困难的是在每次访问内存时都必须要更新整个链表。
假设用硬件实现：硬件有一个64位计数器C，它在每条指令执行完后自动加1，每个页表项必须有一个足够容纳这个计数器值的域。在每次访问完内存后，将当前的C值保存到被访问页面的页表项中。一旦发生缺页中断，操作系统就检查所有页表项中计数器的值，找到值最小的一个页面，这个页面就是最近最少使用的页面。
但是只有非常少的计算机拥有这样的硬件。
7. 最不常用页面置换算法（NFU）（Not Frequently Used）
用一个软件模拟LRU，该算法将每个页面与一个软件计数器相关联。计数器的初值为0。每次时钟中断时，由操作系统扫描内存中所有的页面，将每个页面的R位（它是0或1）加到它的计数器上。这个计数器大体上跟踪了各个页面被访问的频繁程度。发生缺页中断时，则置换计数器值最小的页面。
NFU的缺点是它不从不忘记任何事，比如一个页面之前频繁被访问，导致这个它的计数器很大，但是后来它不被访问了，而它的计数器的值还是很大，所以它一直不会被置换出去。
分段
虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。
下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。
分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。
段页式
程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。
分页与分段的比较
- 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
- 地址空间的维度：分页是一维地址空间，分段是二维的。
- 大小是否可以改变：页的大小不可变，段的大小可以动态改变。
- 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。
