这段时间在学习操作系统，看的是清华向勇，陈渝老师的视频，老师讲的很好很细致。
昨天看到局部置换算法，今天主要想说说自己的思考，如果看到这篇文章的你是想系统的学习局部置换算法，那暂且不要继续往下看了，去网上搜这两位老师的网课吧，你会收获更多。
如果你正在学习这部分知识并有了一定的了解，那不妨花个一两分钟看看下文，我们可以一起思考，一起讨论，如果文中有错误或不合理的地方，麻烦看到文章的你一定告诉我，谢谢啦。
最优算法：OPT (optimal)
optimal是最理想的情况，发生缺页时选择置换未来最长时间不被访问的页面，嗯理想很丰满现实很骨感，事实上我们是没法预测未来的，所以并不能准确知道每个页面下次会在什么时间访问，所以说optimal是没法实现的。
那么问题来了，都没法实现要它有啥用？它当然是有用的，它存在的意义就是给其他置换算法树立标杆，因为它是最理想的情况，把其他置换算法的置换结果和它作比较，就能分出好坏。小时候家长嘴里总有个“别人家的孩子”，没错，最优算法就是那个“别人家的孩子”。
先进先出算法：FIFO (First in, first out)
先进先出算法是比较笨拙也比较容易实现的，只需要用一个链表来记录在内存中的页面。看下面这个画的有点糙的图，假设运行一个程序时CPU只分配给这个程序能保存3个页面的内存空间，也就是说我们可以创建一个长度为3的链表来记录存在物理内存中的页面，下图棕色的线就是链表，图中描述了每次访问页面时链表的维护过程。
使用先进先出算法完成页面置换很简单，发生缺页时找链表末端的页面置换就可以。这么看来置换的开销是不大的，但是从图中我们可以看出，这种算法日常访问时开销是极大的，每次访问都要修改链表。
最可怕的还不是持续不断的对链表的修改，可怕的是有可能刚把页面A置换到外村，下一个就要访问A，如果一个程序执行过程中这种情况比较多，还有可能造成belady现象，也就是说分配给程序的物理内存大了，发生缺页的次数反而增加了。
最近最久未使用算法： LRU(Least Recently Used)
最近最久未使用算法在一定程度上实现了最优算法，最优是想替换未来最不可能使用的，最近最久未使用是根据历史来预判未来。每次缺页时，都要去物理内存中统计每个页面上次访问的时间，最久未访问的，就要被拉到屠宰场干掉了，统计的过程是及其复杂的，因此这种算法置换时候的开销就很大了。
上述提到的三种算法，最优算法是不能实现的；先进先出算法置换开销小，但是访问开销大；最近最久未使用算法访问开销小，但是置换开销大，那么有没有比较折中的置换算法呢？
答案是：有的。我就不卖关子了，反正你google上随便一搜也能搜到的，时钟置换算法和最不常用算法就是更折中的算法，所以呢，未完待续......
时钟置换算法：CLOCK
前面提到对LRU和FIFO的折中，今天就来聊聊时钟置换算法，时钟置换算法的思想是置换最近未被访问的，但不像LRU一样在置换页面时做详细的统计，因此置换开销会降低。使用访问位标识每个页面，每次遇到访问位为0的就将其置换，这点和FIFO类似，但不像FIFO那么无脑。
具体的做法是，在页表中增加访问位，用来标识当前页面是否被访问过，当一个页面第一次被加载到内存中时，将其访问位初始化为0；当一个页面第一次被访问时，将其访问位置1。所有页表项构成一个环形链表，发生缺页中断时，从当前指针位置开始查找，如果访问位为1，将其置0，指针后移；如果访问位为0，置换该页面。
我们可以看一个例子，如下图，初始状态下，页面a, b, c, d 保存在内存中，均未被访问过，接下来页面的访问顺序是c, a, d, b, e, b, a, b, c, d,下图每个两行四列的表格中，第一行表示存在内存中的页面，第二行表示相应页面的访问位，红色箭头表示当前指针所处的位置。
- 上述过程我们只考虑了页面的访问，实际情况下我们不仅有读操作，也有写操作，我们在对内存中的页面进行置换时，如果该页面在内存中被修改过，那我们应该在置换的同时，将修改同步到外存中。针对这一现象，就出现了改进的时钟置换算法，旨在每次置换时跳过别修改的页面。
- 改进的时钟置换算法在页表项中增加修改位，用来表示该页面是否被修改。当我们对内存中的页面进行写操作时，将该页面的修改位和访问位置1，如果是读操作，只将访问位置1。进行页面置换时，如果修改位为1，跳过该页面，只有当存在内存中所有页面的修改位都为1时，再进行将修改同步到外存的操作，这样就不需要频繁同步数据到外存。
最不常用算法：LFU(Least Frequently Used)
最不常用算法也是LRU的一种简化，只不过LRU关心的是时间，而LFU关心的是次数，LFU为每个页面设置一个计数器，用来统计该页面被访问的次数，发成缺页时，选择被访问次数最少的页面进行置换。
