参考教材：
Operating Systems: Three Easy Pieces
Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
在线阅读：
http://pages.cs.wisc.edu/~remzi/OSTEP/
University of Wisconsin Madison 教授 Remzi Arpaci-Dusseau 认为课本应该是免费的。
————————————————————————————————————————
这是专业必修课《操作系统原理》的复习指引。
在本文的最后附有复习指导的高清截图。需要掌握的概念在文档截图中以蓝色标识，并用可读性更好的字体显示 Linux 命令和代码。代码部分语法高亮。

六 内存管理（三）：交换

1、当内存不足以放置所有进程的地址空间时，需要将一部分页面移动到硬盘上。早期的系统中，程序员需要手动移动暂时不需要的页面。也就是说每次调用函数或访问数据时，都要手工检查被访问的内容是否在内存中。现代操作系统会自动帮我们完成这项工作。硬盘上的一部分空间被保留下来，专门用于暂存不太紧要的内存页，这部分空间称为交换区（swap space）。

2、页表中有一位present bit，用于刻画该页是否正位于内存中。如果试图访问一个不在内存中的页，就会发生页错误（page fault），也称页缺失。OS会运行页错误处理程序进行处理。一般地，OS会把位于交换区的页移回内存。为了确保顺利进行页交换，OS就需要记录处于交换区的页的磁盘地址（disk address）。页从磁盘回到内存时，OS就更新页表中相应虚拟地址的物理页号，然后重试指令。这次重试可能会引发TLB未命中，于是TLB中的相应内容也被更新。再一次重试时，就能直接从TLB中取得回到内存中的页的物理地址了。IO的开销相比内存内的操作大得多，因此OS一般会将进程IO和进程切换尽量同时处理，以充分利用硬件。

3、硬件一般不处理页错误。虽然硬件工程师对操作系统包揽大部分事务这一点不信任，但页错误仍被交由操作系统处理。这是因为：（1）磁盘相比内存是非常慢的。就算OS执行处理页错误的其它命令花费很长时间，一般也远远少于比将请求的页从磁盘调回到内存花费的时间，所以对总体的运行性能影响十分小，无需通过硬件进行专门的加速。（2）如果要通过硬件来处理，那么硬件工程师势必要弄清楚交换区的具体实现原理，搞清楚磁盘IO怎么处理并实现，以及许多他们一般不知道的细节。总的来说，为了平衡性能和开发的难易程度，就由OS处理页错误。

4、内存已满的时候，必须进行交换；但是内存未满的时候也可能会交换。许多操作系统一般有两个阈值：High watermark（HW）和Low watermark（LW）。当可用的页数小于LW时，就会有一个后台（background）进程启动，将部分页面移动到交换区，直到可用页数达到HW。这个程序叫做交换守护进程（swap daemon），又称页面守护进程（page daemon）。

5、Cache miss分为三种：
（1）冷启动缺失（cold-start miss），也称强制缺失（compulsory miss），是指系统刚启动、缓存为空时必定发生的未命中现象。对一个从未放入缓存的对象进行访问，在缓存中肯定是找不到这个对象的。
（2）容量缺失（capacity miss），是指缓存容量已满时又遇到未访问过的内容造成的未命中。此时必须将缓存中已有的一项移除。
（3）冲突缺失（conflict miss）只在组相联映射和直接映射的cache中存在。其出现原因是由于一些内容只能被写入特定的缓存区域，当被指定同一个写入区域的不同内容写入缓存时，先写入的会被移除。下一次访问原来先写入的内容时，记一次冲突缺失。

6、当需要把内存页交换到交换区时，应该正确选择交换的页面，否则内存的速率就会被拖慢成磁盘的速率。最理想的状况自然是交换在未来被使用的次数最少的页（Bélády算法），但是我们没有办法预测未来，所以这个思路虽然简单但难以实现。这里介绍常见的选择交换页面的几个算法：
（1）先进先出（FIFO）。此方法十分容易实现，但最坏情况的表现显著差于均值。
（2）随机（Random）。这类算法亦属于较容易实现的一类。
（3）最少频率使用（LFU）。该算法尽可能去解决FIFO和随机算法可能把常用的页踢出去的问题。根据局部性原理，一般认为最近访问的页比较早访问的页被再次访问的可能性更大；如果数据在最近一段时间内使用次数很少，那么将来被使用的次数也大概率很少。最近最少使用（LRU）与其类似，不过LRU淘汰的是最长时间没有被使用的页面，而LFU淘汰的是一段时间内使用次数最少的页面。

7、在完全随机的访问请求下，这几种常见算法的命中率几乎没有区别。但是如果我们将“二八定律”套用过来，即描述一种更接近实际使用的情况：绝大多数（约80%）的访问只访问少数（约20%）的数据；少数（约20%）的访问访问绝大多数（约80%）的数据。这时候，情况就变得不一样了：

由图可知，LRU算法的命中率表现优于FIFO和随机算法。但是这样的命中率在实际使用中会反映多少提升？答案是：看情况。如果一次未命中带来的重新查找并访问的开销十分大，提升就会更明显。反之，提升就不太大。
但有一种极端情形，LRU和FIFO的表现都很差：循环访问。例如交换区能记录49页，且当前内存接近耗尽，必须进行交换。如果需要循环访问50页的内容，前49页都在交换区（任意49页都在交换区的情况也是一样差），那么程序每访问一页就要把这一页从交换区移至内存，然后在后续的访问中总是把先进内存的移到交换区（或把先到交换区的先移入内存，这里先进内存或先进交换区的正好与最长时间没有被使用的页是同一页），于是命中率就是0 %。这种情况下，随机算法的反而具有大于0的命中率。当然如果内存空间剩余比较多，那么就无需进行交换，所有需要访问的页都在内存中，命中率就达到100 %。

8、如果想要实现LRU等需要通过历史记录来选定移动哪一页到交换区的算法，那么每次内存访问都要做额外的工作，这是十分影响性能的。为了加速，一般需要硬件支持。另外，我们不一定总是要获得最优解，如果能用更少的时间获得次优解，那么不失为一个很好的解决方案。
用一个使用位（use bit）（亦称引用位（reference bit）），来标记一个页是否被访问过。硬件不会将这个位置零，OS才可以。一种选择次优解的实现方式是时钟算法（clock algorithm）。一个指针开始时指向任意的页。当需要将部分页面移到交换区时，检查当前指向的页的是因为是否为0。如果为1，则继续查找其它页，直到找到一个使用位为0的页位置。如果所有的页都被使用过，那么把使用位全部清零。
在80-20工作负载中，一种时钟算法的变体表现不错：

这种变体算法在发现一个使用位为1的位时，就将其使用位清零；如果发现一个使用位为0的位，就将其移到交换区。可以看出它和LRU算法的表现十分接近。

9、也可以根据一个页面是否已修改来决定是否将其移至交换区。修改位（modified bit）也称dirty bit，用于描述一个页面是否被修改过。如果否，则优先移至交换区。因为将一个未修改的页面移至交换区实际上可以优化成：不写入硬盘，而是直接用于其它事务（当以后需要此页面时再重新读入内存）。引入修改位后，时钟算法就可以改进为：先交换未修改且未访问的页面，当无未修改的页面可交换时再交换已修改但（后来）未访问的页面。

10、多数情况下，一般在一个页被访问时，如果此页在交换区，OS就把它移入内存。但是OS也可以猜测哪些页在接下来更可能被访问，并将它们一起读入内存，这个机制称为预读（prefetching）。例如当交换区中的某一页被访问时，将其附近的页一并读入内存。同理，在写入交换区的时候，OS一般不会将少数的页立刻写入，而是将写入延迟，直到凑齐一定数量后，才统一写入硬盘。这样就可以大幅改善写入速率。这是因为磁盘写入小文件的速率远远慢于写入大文件。很多情况下，请求将数据写入硬盘时，写入也会被延迟，直到要求存盘的数据足够多再写入。对某些情况，例如刚刚请求存盘的文件被删除了，那么就可以直接在快得多的内存中操作，而无需访问硬盘。

11、当请求建立一组新进程时，如果可用的内存（包括交换区）不足，OS应该拒绝一部分进程的运行。这个机制称为接纳控制（admission control）。无论是在现代操作系统还是在实际生活中，把少量的事情做好，远远好于同时做大量的事情但做得不好。新的系统对内存不足的预防更为严苛。例如一些Linux版本在内存不足时还会杀掉占用内存较高的进程。当然这个方法并不是没有问题的：有时候X Window System会被干掉，于是所有需要显示位图的进程都无法继续显示。Android系统也是基于Linux的，相信大家常常发现在运行较多程序后，有许多后台进程被杀，需要重新运行，或者进程的一部分内容需要重新载入（例如浏览器的部分网页）。