fifo页面淘汰算法总结第1篇
假设虚拟内存的地址是16位，页面大小为1K，则进程的大小为216=64KB2^{16}=64KB216=64KB
分页个数=进程的大小页面的大小=逻辑地址表示的大小页面的大小=216B1KB=26页分页个数=\frac{进程的大小}{页面的大小}=\frac{逻辑地址表示的大小}{页面的大小}=\frac{2^{16B}}{1KB}=2^{6}页分页个数=页面的大小进程的大小=页面的大小逻辑地址表示的大小=1KB216B=26页
因此页号p占用前6位，页内偏移量w=16-6=10位。每一个页表项占用2B,因此页表存储空间需要26∗2B=128B2^6*2B=128B26∗2B=128B
页面结构以及页表项设计如下：
算法流程如下：
具体实现如下：
算法流程如下：
具体实现如下：
算法流程如下：
其中调用了randBool()函数，随机的生成0或者1，其具体实现如下
算法规则：选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存。
假定系统为某进程分配了三个物理块，并考虑有以下页面访问序列：[7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1]进程运行时，先将7,0,1三个页面依次装入内存。进程要访问页面2时，产生缺页中断，根据最佳置换算法，选择第18次访问才需调入的页面7予以淘汰。然后，访问页面0时，因为已在内存中所以不必产生缺页中断。访问页面3时又会根据最佳置换算法将页面1淘汰……依此类推。
算法流程图如下：
opt算法具体实现如下：
算法规则：在发生页面替换时，被替换的对象应该是最早进入内存的。
仍然采用上述的例子，此时页面置换过程如下表所示
FiFo算法流程图如下所示：
FiFo页面置换算法具体实现如下：
初始化设置
m=8,e=8,s=10;页框数=3，访问序列长度=20；
选择算法2：先进先出淘汰算法
置换过程
算法规则：在发生页面替换时，被替换的页面应该满足，在之前的访问队列中，该对象截止目前未被访问的时间最长。
仍然采用上述的例子，此时页面置换过程如下表所示
初始化设置
m=8,e=8,s=10;页框数=3，访问序列长度=20；
选择算法3：先进先出淘汰算法
页面置换过程
算法规则：简单的CLoCK算法实现方法:为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLoCK算法选择一个淘汰页面最多会经过两轮扫描)
CLoCK_pro是CLoCK算法的入口参数，其中会传入参数choose。当choose=1时采用改进的clock算法，当choose=0时采用基本的clock算法。
然后replace_page_clock实现了基本CLoCK算法的置换策略，具体代码如下：
初始化设置
m=8,e=8,s=10;页框数=3，访问序列长度=20；
选择算法4：基本的CLoCK算法
页面置换过程
算法规则：简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行i/o操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免i/o操作。这就是改进型的时钟置换算法的思想。修改位=o，表示页面没有被修改过;修改位=1，表示页面被修改过。为方便讨论，用（访问位，修改位）的形式表示各页面状态。如(1，1）表示一个页面近期被访问过，且被修改过。
将所有可能被置换的页面排成一个循环队列
初始化设置
m=8,e=8,s=10;页框数=3，访问序列长度=20；
选择算法5：改进的CLoCK算法
页面置换过程
由于上述的生成访问随机序列较小，且只考虑了页框大小为3的情况。因此，需要改变页框数和增大访问序列来对比算法的命中率，并对不同的实验情况的置换率和系统开销求得平均值，统计如下表所示：
置换率比较
最佳置换算法<改进型clock置换算法
系统开销比较
先进先出置换算法<最近最久未使用算法 最开始页面号1进入主存，主存里面有空闲的帧，将其使用位记成1，由于主存中之前没有页面1，所以会发生缺页中断。 同理随后的页面2，3，4进入主存，将其使用位记成1，发生缺页中断。 当之后的页面1，2进入主存时，由于页面1,2已经在主存中，不做处理。 当之后的页面5进入主存时，主存内没有空余的帧，这时候随着指针循环移动整个缓冲区，将之前页面的使用位全部清0，即这时候页面1,2,3,4对应的使用位全部为0，指针回到最初的位置，将页面1替换出去，页面5换入主存，同时使用位标记成1。以此类推，可知CLoCK共发生10次缺页中断。 当数字不在框中，从当前向后找最后一个将要访问的数字进行替换当数字在框中，则不做改变，继续向后（3）特点缺点：最佳置换算法是一种理想化算法，具有较好的性能，但是实际上无法实现（无法预知一个进程中的若干页面哪一个最长时间不被访问）；优点：最佳置换算法可以保证获得最低的缺页率 由于FiFo算法性能较差，所以出现了LRU页面置换算法，该算法是根据页面调入内存后的使用情况来做决策的。无法预估页面将来的使用情况，利用过去的页面使用情况来进行置换的。 实现原理：可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问页面时，便将该页面的页面号从栈中移除，将它压入栈顶。因此，栈顶元素始终是最新被访问页面的编号，而栈底则是最近最久没有被使用的页面的编号。 参考实验所做的代码： 前三次访问依次将4,7，0放入栈中，4为栈底，0为栈顶；第四次是访问第7页，因此7变为栈顶；当第八次访问页面2时，栈满，在九、十次访问时，没有发生缺页；而在第十一次访问时，页面6发生了缺页，4为最久没有被访问的页面，被替换出去。 除此之外还有最佳（optimal）置换算法，所选择的页面是以后永不被使用的或者在最长（未来）时间内不再被访问的页面。此算法也有着最低的缺页率，但缺点是无法预知未来将调用那个页面。还有最少使用（LFU）置换算法，在使用该算法时在每个页面设置一个位移寄存器，来记录此页面被访问的频率，并选择最近时期使用频率最低的页面作为淘汰页。还有一些算法例如Clock置换算法、页面缓冲算法（pBa）等，由于没有过多去学习，故不过多赘述。 若文中有错误的地方，请批评指正，谢谢！ LRU算法是一种常见的缓存算法，它的思想是：最近最少使用的会被优先淘汰。如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被淘汰掉。 （1）实现：最简单的实现方法是用数组+时间戳的方式，不过这样做效率较低。因此，我们可以用双向链表（LinkedList）+哈希表（Hashmap）实现（链表用来表示位置，哈希表用来存储和查找），在Java里有对应的数据结构LinkedHashmap。 （2）缺点：它在需要淘汰时，只是随机选取有限的key进行对比，排除掉访问时间最久的元素，也就意味着它不能选择整个候选元素的最优解，只是局部最优。默认随机选取的key的数目为5，在配置文件中由maxmemory_samples属性的值决定，采样数量越大越接近于标准LRU算法，但也会带来性能的消耗。在Redis以后增加了LRU淘汰池，进一步提高了与标准LRU算法效果的相似度。淘汰池即维护的一个数组，数组大小等于抽样数量maxmemory_samples，在每一次淘汰时，新随机抽取的key和淘汰池中的key进行合并，然后淘汰掉最旧的key，将剩余较旧的前面5个key放入淘汰池中待下一次循环使用。假如maxmemory_samples=5，随机抽取5个元素，淘汰池中还有5个元素，相当于变相的maxmemory_samples=10了，所以进一步提高了与LRU算法的相似度。 LFU算法（Leastfrequentlyused：最不常使用） LFU算法的思想是：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。 实现：如果只为每个key维护了一个计数器，每次key被访问的时候，计数器增大，计数器越大，则认为访问越频繁。这样还是远远不够的，还会存在两个问题： （1）因为可能存在在开始一个小时内，某个key1有100万的访问量，但是在之后的一个小时内，这个key1的访问量为0了，而在这第二个小时内另外有个key2的访问量达到了20万，虽然这20万不如前面那个key1开始那个小时的100万访问量大，但是在第二个小时内这key2的访问量远大于key1的访问量，所以在第二个小时内key1依然会优先于key2被淘汰掉。 （2）当新加入的key，由于没有被访问过，所以初始的计数器为0，如果这时候触发淘汰机制的话，就会把最先添加到key最先淘汰掉。 所以在LFU算法中维护了这个24bit的字段，不过被分成了16bits与8bits两部分。第一部分：高16bits用来记录计数器的上次缩减时间，时间戳，单位精确到分钟。第二部分：低8bits用来记录计数器的当前数值，这个数值反映了访问频率，而不是次数。 在配置文件中还有2个属性可以调整LFU算法的执行参数：lfu-log-factor、lfu-decay-time。其中lfu-log-factor用来调整计数器counter的增长速度，lfu-log-factor越大，counter增长的越慢。lfu-decay-time是一个以分钟为单位的数值，用来调整counter的缩减速度。fifo页面淘汰算法总结第2篇
fifo页面淘汰算法总结第3篇
fifo页面淘汰算法总结第4篇
fifo页面淘汰算法总结第5篇