fifo页面淘汰算法总结

fifo页面淘汰算法总结 第一篇

假设虚拟内存的地址是一六位，页面大小为一K，则进程的大小为 二 一六 = 六四 K B 二^{一六}=六四KB 二一六=六四KB

分页个数 = 进程的大小 页面的大小 = 逻辑地址表示的大小 页面的大小 = 二 一六 B 一 K B = 二 六 页 分页个数=\frac{进程的大小}{页面的大小}=\frac{逻辑地址表示的大小}{页面的大小}=\frac{二^{一六B}}{一KB}=二^{六}页 分页个数=页面的大小进程的大小​=页面的大小逻辑地址表示的大小​=一KB二一六B​=二六页

因此页号P占用前六位，页内偏移量W=一六-六=一零位。每一个页表项占用二B,因此页表存储空间需要 二 六 ∗ 二 B = 一二八 B 二^六*二B=一二八B 二六∗二B=一二八B

页面结构以及页表项设计如下：

算法流程如下：

具体实现如下：

算法流程如下：

具体实现如下：

算法流程如下：

其中调用了randBool()函数，随机的生成零或者一，其具体实现如下

算法规则：选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存。

假定系统为某进程分配了三个物理块，并考虑有以下页面访问序列： [七, 零, 一, 二, 零, 三, 零, 四, 二, 三, 零, 三, 二, 一, 二, 零, 一, 七, 零, 一] 进程运行时，先将七, 零, 一三个页面依次装入内存。进程要访问页面二时，产生缺页中断，根据最佳置换算法，选择第一八次访问才需调入的页面七予以淘汰。然后，访问页面零时，因为已在内存中所以不必产生缺页中断。访问页面三时又会根据最佳置换算法将页面一淘汰……依此类推。

算法流程图如下：

OPT 算法具体实现如下：

算法规则：在发生页面替换时，被替换的对象应该是最早进入内存的。

仍然采用上述的例子，此时页面置换过程如下表所示

FIFO算法流程图如下所示：

FIFO 页面置换算法具体实现如下：

初始化设置

m=八,e=八,s=一零; 页框数=三，访问序列长度=二零；

选择算法二：先进先出淘汰算法

置换过程

算法规则：在发生页面替换时，被替换的页面应该满足，在之前的访问队列中，该对象截止目前未被访问的时间最长。

仍然采用上述的例子，此时页面置换过程如下表所示

初始化设置

m=八,e=八,s=一零; 页框数=三，访问序列长度=二零；

选择算法三：先进先出淘汰算法

页面置换过程

算法规则：简单的CLOCK算法实现方法:为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为一。当需要淘汰一个页面时，只需检查页的访问位。如果是零，就选择该页换出;如果是一，则将它置为零，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是一，则将这些页面的访问位依次置为零后，再进行第二轮扫描（第二轮扫描中一定会有访问位为零的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

CLOCK_pro 是CLOCK算法的入口参数，其中会传入参数choose。当choose =一时采用改进的clock算法，当choose =零时采用基本的clock算法。

然后replace_page_clock 实现了基本CLOCK算法的置换策略，具体代码如下：

初始化设置

m=八,e=八,s=一零; 页框数=三，访问序列长度=二零；

选择算法四：基本的CLOCK算法

页面置换过程

算法规则：简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/o操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。 因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/o操作。这就是改进型的时钟置换算法的思想。修改位=o，表示页面没有被修改过;修改位=一，表示页面被修改过。为方便讨论，用（访问位，修改位）的形式表示各页面状态。如(一，一）表示一个页面近期被访问过，且被修改过。

将所有可能被置换的页面排成一个循环队列

初始化设置

m=八,e=八,s=一零; 页框数=三，访问序列长度=二零；

选择算法五：改进的CLOCK算法

页面置换过程

由于上述的生成访问随机序列较小，且只考虑了页框大小为三的情况。因此，需要改变页框数和增大访问序列来对比算法的命中率，并对不同的实验情况的置换率和系统开销求得平均值，统计如下表所示：

置换率比较

最佳置换算法 < 改进型clock置换算法

系统开销比较

先进先出置换算法 < 最近最久未使用算法 < clock算法<改进型clock置换算法 < 最佳置换算法

fifo页面淘汰算法总结 第二篇

最开始页面号一进入主存，主存里面有空闲的帧，将其使用位记成一，由于主存中之前没有页面一，所以会发生缺页中断。

同理随后的页面二，三，四进入主存，将其使用位记成一，发生缺页中断。

当之后的页面一，二进入主存时，由于页面一,二已经在主存中，不做处理。

当之后的页面五进入主存时，主存内没有空余的帧，这时候随着指针循环移动整个缓冲区，将之前页面的使用位全部清零，即这时候页面一,二,三,四对应的使用位全部为零，指针回到最初的位置，将页面一替换出去，页面五换入主存，同时使用位标记成一。以此类推，可知CLOCK共发生一零次缺页中断。

fifo页面淘汰算法总结 第三篇

当数字不在框中，从当前向后找最后一个将要访问的数字进行替换 当数字在框中，则不做改变，继续向后 （三）特点 缺点：最佳置换算法是一种理想化算法，具有较好的性能，但是实际上无法实现（无法预知一个进程中的若干页面哪一个最长时间不被访问）； 优点：最佳置换算法可以保证获得最低的缺页率

fifo页面淘汰算法总结 第四篇

由于FIFO算法性能较差，所以出现了LRU页面置换算法，该算法是根据页面调入内存后的使用情况来做决策的。无法预估页面将来的使用情况，利用过去的页面使用情况来进行置换的。

实现原理：可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问页面时，便将该页面的页面号从栈中移除，将它压入栈顶。因此，栈顶元素始终是最新被访问页面的编号，而栈底则是最近最久没有被使用的页面的编号。

参考实验所做的代码：

前三次访问依次将四,七，零放入栈中，四为栈底，零为栈顶；第四次是访问第七页，因此七变为栈顶；当第八次访问页面二时，栈满，在九、十次访问时，没有发生缺页；而在第十一次访问时，页面六发生了缺页，四为最久没有被访问的页面，被替换出去。

除此之外还有最佳（Optimal）置换算法，所选择的页面是以后永不被使用的或者在最长（未来）时间内不再被访问的页面。此算法也有着最低的缺页率，但缺点是无法预知未来将调用那个页面。还有最少使用（LFU）置换算法，在使用该算法时在每个页面设置一个位移寄存器，来记录此页面被访问的频率，并选择最近时期使用频率最低的页面作为淘汰页。还有一些算法例如Clock置换算法、页面缓冲算法（PBA）等，由于没有过多去学习，故不过多赘述。

若文中有错误的地方，请批评指正，谢谢！

fifo页面淘汰算法总结 第五篇

LRU算法是一种常见的缓存算法，它的思想是：最近最少使用的会被优先淘汰。如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被淘汰掉。

（一）实现：最简单的实现方法是用数组+时间戳的方式，不过这样做效率较低。因此，我们可以用双向链表（LinkedList）+ 哈希表（HashMap）实现（链表用来表示位置，哈希表用来存储和查找），在Java里有对应的数据结构LinkedHashMap。

（二）缺点：它在需要淘汰时，只是随机选取有限的key进行对比，排除掉访问时间最久的元素，也就意味着它不能选择整个候选元素的最优解，只是局部最优。默认随机选取的key的数目为五，在配置文件 中由maxmemory_samples属性的值决定，采样数量越大越接近于标准LRU算法，但也会带来性能的消耗。在Redis 以后增加了LRU淘汰池，进一步提高了与标准LRU算法效果的相似度。淘汰池即维护的一个数组，数组大小等于抽样数量 maxmemory_samples，在每一次淘汰时，新随机抽取的key和淘汰池中的key进行合并，然后淘汰掉最旧的key，将剩余较旧的前面五个key放入淘汰池中待下一次循环使用。假如maxmemory_samples=五，随机抽取五个元素，淘汰池中还有五个元素，相当于变相的maxmemory_samples=一零了，所以进一步提高了与LRU算法的相似度。

LFU算法（Least frequently used：最不常使用）

LFU算法的思想是：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。

实现：如果只为每个key维护了一个计数器，每次key被访问的时候，计数器增大，计数器越大，则认为访问越频繁。这样还是远远不够的，还会存在两个问题：

（一）因为可能存在在开始一个小时内，某个key一有一零零万的访问量，但是在之后的一个小时内，这个key一的访问量为零了，而在这第二个小时内另外有个key二的访问量达到了二零万，虽然这二零万不如前面那个key一开始那个小时的一零零万访问量大，但是在第二个小时内这key二的访问量远大于key一的访问量，所以在第二个小时内key一依然会优先于key二被淘汰掉。

（二）当新加入的key，由于没有被访问过，所以初始的计数器为零，如果这时候触发淘汰机制的话，就会把最先添加到key最先淘汰掉。

所以在LFU算法中维护了这个二四bit的字段，不过被分成了一六 bits与八 bits两部分。第一部分：高一六 bits用来记录计数器的上次缩减时间，时间戳，单位精确到分钟。第二部分：低八 bits用来记录计数器的当前数值，这个数值反映了访问频率，而不是次数。

在配置文件中还有二个属性可以调整LFU算法的执行参数：lfu-log-factor、lfu-decay-time。其中lfu-log-factor用来调整计数器counter的增长速度，lfu-log-factor越大，counter增长的越慢。lfu-decay-time是一个以分钟为单位的数值，用来调整counter的缩减速度。