<!--
 * @Github: https://github.com/Certseeds/CS302_OS
 * @Organization: SUSTech
 * @Author: nanoseeds
 * @Date: 2020-05-10 18:42:40
 * @LastEditors: nanoseeds
 * @LastEditTime: 2020-07-04 17:48:25
 * @License: CC-BY-NC-SA_V4_0 or any later version 
 -->

1. FIFO  
FIFO算法,每次先查看是否在内存中,如果在内存中则不变;
若不在内存中,如果队列已满,就踢走队列头部的页面,将页面调入队尾
.只用列表等结构的话,每次查询需要复杂度O(n),每次替换时间复杂度O(1).
如果有hashmap辅助查询的话,查询的复杂度也能到O(1).

2. Min置换算法  
维护一个表,置换之后不再被访问,或者说,访问时间距离现在最长的页面.
由于每次都需要查找下一个这次出现的页面,所以时间复杂度是O(n).

3. LRU算法.  
置换最近一段时间来最长时间没有被访问的页面.根据局部性原则,被访问之间有关联,
所以越是长时间没有被访问,访问的可能性越低.
具体实现来看,每次至少需要遍历一遍页面,并且将页面从列表中提到头部.
所以需要O(n)的时间复杂度.

4. Clock算法的内容.  
首先,Clock算法是Second-chance算法的改进.
为了节约两个列表之间转换的成本,将列表置为循环列表,
将圆心指向下一个被置换的页面.置换前检查,
如果使用位是1,则将其置为0,但是只需要旋转,而不是在列表之间转换.
直到发现页为0,置换此页.节约了在两个列表之间转换的成本.
但是每次还是需要遍历,需要O(n)的时间复杂度.

5. second-chance算法:  
为了避免FIFO把经常使用的页面踢出的弊端,使用一个检查位,
给经常使用的,检查位为1的页面重新加入列表,给第二次机会.从而提升了效率.
换言之,使用了FIFO模式和LRU模式相结合.
从实现上来看,每次都要遍历需要O(n)的时间复杂度.

PS:由于不知名原因,这个report没有被评分,不知道具体情况.