This post was writteen in Chinese，Original Post.
Since this post had not been translate to English，Please use the tool provided to translate.
因为快要上课了, 这个系列的笔记可能做不下去了； 而且我借的参考书快要到期了。这后面的概念也十分复杂。如果要讲清楚的话需要大量的文字，至少也要做几个gif动画配图才能阐述明白。本来计划一个月内能将整本书讲完，现在看看可能没那么简单呢。( °௰° υ )
虚拟内存原理
按需调页
虚拟内存是一个或多个逻辑地址空间的集合。其中每个逻辑地址空间的大小可以超过物理空间。这样的逻辑地址空间被称为虚拟地址。通常来说，每个程序都有自己的虚拟内存，这些虚拟内存的页要通过加载到物理内存中才能被使用。由于虚拟内存要比物理内存大得多，操作系统要有一套完善的调度体系来维持内存的合理利用。 按需调页(demand paging)是加载页的一个原则，它规定了只有在需要的时候，内存才会加载页；而不是一次性将所有页加载进物理内存。这就需要到一个标记符号了。有效-无效位(valid-invalid bit)，有时候也叫存在位（present bit）， 被用于表示一个页是在自盘还是内存中。当一个页在物理内存中的时候，它是1， 否则是0。当一个进程试图访问那些在内存中不存在的页的时候，页错误(page fault)就会产生。
我们要在常规页表的基础上加上有效-无效位，用于表示一个页是否在物理内存中。如果进程执行到了某个存在位是0的页，页错误就会产生。这时，这个没有被加载的页就会从虚拟内存中被加载到物理内存中，页表的存在位也会相应的变成1。这样，这个页就能被访问了。
如上图所示，在页表上加入了一个存在位。存在位表示该页是否加载到了内存中。比如p3的存在位是0，这表示该页没有被加载到内存中。这个时候系统就要将这个没有被加载到物理内存中的页加载进来。
需要注意的是，页表的任务只是将页和帧对应起来。一个程序被分配到的逻辑内存是固定的，但是它占用的页不是整个逻辑内存空间。所以加载哪一个页不是由页表决定的，反而是系统决定加载了哪一个页之后更新这个页表的存在位(见下图)。
页置换
虚拟内存比物理内存要大得多。当所有的帧都被使用，且新的页错误产生的时候，其中一个在物理内存的页一定要被移出内存以释放空间给新的帧。页置换（page replacement）的概念便是更换一个在内存中的页到另一个页的过程。
在内存和磁盘之间移动这些页十分的耗费时间，必须要有一个方法来减少这样的损失。如果一个页被移出内存，而且它在内存的过程中没有被修改过，那么就不需要将它复制回磁盘中。这个方法好用，不过我们需要一个修改位(modified-bit, m-bit)来记录一个页是否被修改过。如果修改位为1，则修改位对应的页被修改过，否则没有。
多层页表
我们说过一个虚拟内存可以是很大的，它甚至可以比物理内存的大小还要大出许多。并不是所有的程序都需要很大的地址空间的，这样一来虚拟内存的页表就浪费了。为了能够节省这种浪费，我们要在之前的页表前加上一级页表。如此一来，段页式储存管理的(s, p, w)就变成了(s,p1,p2,w)。
这也就是说，当需要将物理内存某个帧置换的时候。首先要找到该帧所对应的页表p2，然后再根据页表p2找到p1,依此类推找到完整的(s, p1, p2, w)并且核验过大小一致之后才能将内容写入虚拟内存。
固定帧的页置换
内存有固定帧数，一个给多个进程分享帧的方法是分配一段固定的帧给这些进程。当出现页错误，并且没有空闲的帧出现的时候，操作系统要将其中一个在内存中的页换掉。引用串(reference string)是某个时刻，正在运行的程序调用的一组页码。通过比较页错误，引用串被用于比较不同页置换算法。比如上面我们说页表的那张图，里面有两个程序。程序1的引用串是p1,p3；程序2的引用串是p1,p2,p5。这只是在某一个时刻它们页调用的情况。下面我们利用引用页来说明几个置换算法。
最优置换
最优置换算法(optimal page replacement algorithm)会选择替换掉最长时间内不会被调用的页。这个算法是所有置换算法中产生页错误最少的。
先进先出置换
先进先出置换(FIFO page replacement algorithm)会选择替换掉在内存停留最长时间的页。不要混淆了，最优置换是换掉未来最不可能用到的页，而这个算法是换掉停留时间最长的页。
最近最少使用算法
最近最少使用算法， 或者LRU算法，(Least-recently-used page replacement algorithm, LRU)会替换掉最长时间没有被引用的页。这个算法需要一个长度为n的队列，其中n是内存中帧的长度。这个队列包含了所有在内存中的页。
当一个驻在内存中的页被引用， 它会被挪到队列头，这保证了队列永远都让最近被使用的页排在最前面。当一个没有驻在内存中的页被引用，它会被放在队列的最前头，如果此时队列的长度已经为n，那么队列中最后一页需要被挪出队列。
近似LRU算法
LRU算法要求每次内存中出现调用的时候就更新队列，这样的算法复杂度十分高，通常来说这不是一个好的实践。一些其他算法被用来趋近LRU的效果。
老化页置换算法
引用位(referenced bit, r-bit)被用于记录页面的调用，这个引用位是在硬件层面实现的。
老化寄存器(aging register)被用于和页连接。除非最高有效位被设为1
， 否则它会周期性地向右位移1个比特。页会随着寄存器向右位移逐渐老化。
老化置换算法不需要维护一个排序方式和LRU一致的队列，它只将那些在一个周期内引用位标记为1的页组起来。老化寄存器移动一位即为一个周期。
这个算法的步骤如下，它会在每次有d个页被引用的时候执行。
- 所有的老化寄存器向右移动一位，丢掉最低有效位。
- 复制引用位到最高有效位位
- 重制引用位为0
当一个页错误出现的时候
- 选择持最小老化寄存器的页，并替换它
- 如果多个页都是最小的值，那么就随机选择一个。
做gif很麻烦，将就着看吧
二次机会算法
二次机会算法(second-chance page replacement algorithm)是另一个近似LRU算法，它使用r-bit将页分为两类：最近被调度， 最近没有被调用。这个算法会从最近没有被调用的页中找一个并替换掉它。
和FIFO算法类似，这个算法需要维护一个指针循环遍历所有页来寻找适当的页并取代它。因为这样的一种循环，这个算法也被称为计时器算法。
``
当一个页错误出现的时候，这个算法会重复下面的步骤直到一页被选择并被取代。
- 如果指针指在一页p上，并且该页的r-bit是0, 那么就置换p并将该指针移动到到下一页
- 否则就重置r-bit为0, 并将指针继续往前搜索。
三次机会算法
在二次机会的算法上加多了一次机会，所以这次需要计数的是两位($2^2 = 4$)引用位。三次机会算法(third-chance page replacement algorithm)也被称为非最近使用页置换算法(NRU)。他将页分为四种状态，由两个1比特的位来表示。
当一个页错误出现的时候，该算法重复以下步骤直到有某页被选择并被替换为止。
如果指针指向了一页，并且该页的引用位r, m都为0，那么就选择该页并向前挪动指针
否则，根据如下状态表设置r,m。
状态转移 类型 11 -> 01 被引用过的页 01 -> 00 被引用过的页 10 -> 00 未被引用的页
工作集合模型
某个程序总是需要调用固定的几个驻内存页来运行。当没有足够的帧，就会出现页错误。如果频繁的将这些页替换，效率将会大大减小。
一个进程得最优工作集(optimal working set)指的是那些它需要马上调用的页，这些页要提前被挪进物理内存中。一个进程的最优工作集大小根据进程的需要而不同。想要知道一个进程的最优工作集在时间t的时候是什么，一个大小为d的窗口(working-set window)将会被插入到引用串中。那些出现在该行的页就是这个集合的元素。集合的大小和它的元素随着时间的推移而改变。一个窗口的大小是由其对应的程序决定的，在程序第一次被加载的时候，它的行为决定了窗口的大小。
工作集置换算法
最优工作集在现实生活中是无法预测的，我们永远都不知道下一个进来的页是什么。所以我们要用次优方案。虽然不能知道未来有什么页输入进来，但是我们知道过去引用了哪些页。进程的工作集（working set, WS）是指这个进程过去d个内存操作所用到的页。工作集置换算法(working set page replacement algorithm)，或者叫WS算法，用一个大小为d的窗口，一边监测引用串，一边改变工作集合的大小及其元素。
随着时间t的推移，工作集合算法的工作如下：
- 挪动1单位的窗口来概括目前的引用串
- 只将该窗口包含的页留在内存中
和最优工作集不同，工作集算法看的是过去用过哪些页。在上面的例子中，在t为-1和0的时候，工作集算法还不会启动，待窗口能装满所需的页之后才会开始记录。
页错误率置换算法
工作集合算法能很好地将页错误率保持在一个很低的水平，但仍旧不够高效。想想看，每次窗口移动都伴随着对集合的更新。一个更好的方法去解决这个问题是使用错误率置换算法（page-fault-frequency replacement algorithm）。它通过调整常驻页集，直接控制页错误率（page fault frequency, PFF)。这个算法只在出现页错误的时候被激活。
在页错误出现的时候，这个算法做如下操作：
- 将需要的页添加到常驻集中
- 如果距上次页错误的时间大于d(一个提前预设的数字)，将所有自上次页错误以来没有被引用的的页，从常驻集中移除。
这里有必要说明一下常驻集(resident set)，它指的是在某个时刻t，被加载到物理内存中的页。
我们来看一个例子
上图中，红色的柱状体表示该引用发生了页错误。在时间为1和2的时候都发生了页错误，但是由于它们距离上一次发生页错误的时间都小于2,所以页错误率置换算法不被激活。到时间4的时候，调用P3导致了页错误，并且距离上一次发生页错误的时间大于2。页错误率置换算法被激活，但是由于在这个区间所有页P1, P2都有被使用过，所以保留它们。在时间7的时候，调用P4触发页错误和页错误率算法。距离上一次页错误到现在（时间4到时间7）只有P3被引用，所以P1, P2被挪出常驻集。剩下的两个时间（8, 9)都因为距离上一次页错误的时间不超过2没有激活算法。
这个算法比工作集算法好的地方是它只有在出现页错误的时候才会发生，而且每次发生的时候都会移除最长时间没有被调用的页，从而保证了每次都清理出理想的内存空间给将来加载的页使用。
虚拟内存的时间和空间复杂度
按需调页的代价
虚拟内存要在时间和空间复杂度中取舍。让虚拟内存比物理内存大的代价是其出现的页错误。一个页错误的出现伴随着对内存和磁盘的读写。磁盘的读写要比内存的读写慢得多，所以将页错误率降得越低越好。
局部控制
当我们说局部控制(local control)的时候，我们在说在某个时刻对“应该有多少进程应该被同时执行”的定夺。当我们需要频繁地进行页调度，颠簸就出现了。试想一下，如果没有做好局部控制，某个进程在执行到一定程度的时候需要更多帧，页错误因此发生，如果内存的利用率是满的，系统就要调度其它进程的帧来解决页错误。其他进程在执行的阶段也需要更多帧，所以它们互相抢夺内存的帧，这样的页错误数量就会居高不下。
如上图，当只有一个进程在运行，页调用引起I/O操作导致了低CPU利用率。随着越来越多的程序被加载到内存运行，CPU的利用率就会稳定增长，但是这个增长不是一直持续的，因为物理内存有限。CPU的利用率跟着进程的数量一起上到一定的高度后会急剧下降。这是因为进程越多，等待I/O操作的进程也越多。CPU的利用率趋近于0。
要执行的程序变多，页错误率就上涨。系统需要在页错误的数量和CPU利用率之间取舍。当页错误的间隔时间L等于它解决页错误的时间S的时候，CPU的利用率最高。 操作系统可以利用这一原理来决定多少个程序可以在内存中。当L < S的时候，操作系统无法及时处理页错误，必然需要相应地减少内存中的程序；当L > S的时候， 页错误之间的时间很长，操作系统可以增加同时运行在内存中的程序来提高CPU的利用率。
页大小的确定
页的大小对时间和空间有着很大的影响。有些进程需要大一点的页，另一些需要小的页。确定不好这个大小会对页错误产生很大的影响。最常见的页大小是512到4096，但是近些年这个数正在逐渐变大。为了满足不同程序的需求，有的操作系统甚至支持多种页大小。
页的大小对空间有什么影响？
假设本来每页的大小是4个字(8字节)，本来一个页表刚好装得下这4个字(1页)。现在我们重新设置一页的大小为2个字，那么页表也要相应的加大一倍来装住现在的两页了。所以页越小需要的空间越大。
页的大小对时间有什么影响？
假设从磁盘中读取1页的时间为m，现在我们将页的数量翻一倍。由于页的数量增加，它要对磁盘的读取时间也会增加。所以页越小，总体需要的I/O时间越长。