江苏龙网

  1. 主页 > 生活百科 > >

FIFO fifo算法模拟?操作系统先进先出和先来先服务(FCFS)有什么区别?( 三 )


也不难，我把书桌上的10本书按照阅读时间先后堆放成一堆 。
这里的阅读时间，就是说我最近一次读这本书是几天之前 。
每次要看书的时候，我先在书桌上找，找到就直接可以读了 。
读完之后放在书堆的最上面 。
如果书桌上面没有我要读的书，就去地下室找 。
找来之后，我就把书桌上最久没有阅读的那本
（也就是书堆里面最下面的那本书）放回地下室 。
然后把我今天需要看的这本书放在书堆的最上面 。
上面这个比方，相信你可以看明白吧 。
这里的地下室对应内存，书桌对应缓存，书对应页面 。
Q5：FIFO和LRU小结
一:FIFO算法
1.0,FIFO (First in First out) 先进先出(核心原则:最先进来的,最先淘汰); 其实在操作系统的设计理念中很多地方都是利用到了先进先出的思想就是因为这个原则简单切符合人们的惯性思维,具备公平性实现起来也简单,直接使用数据结构中的队列即可实现
1.1,在FIFO 中应该支持这些操作: 一,get(key),如果Cache中存在该key,则返回对应的value值,否则返回 -1; 二,set(key,value),如果Cache中存在该key,则重置value值,如果不存在则将该key插入到Cache中,若Cache已满则淘汰最先进入Cache的数据
1.2,那么利用什么数据结构来实现呢?有这一种思路, 利用一个双向链表保存数据,当来了新数据之后便添加到链表末尾,如果Cache存满数据,则把链表头部数据删除,然后把次年数据添加到链表末尾,在访问数据的时候,如果在Cache中存在该数据的话,则返回对应的value值,否则返回 -1,如果想提高访问效率,可以利用hashmap来保存每个key在链表中的位置(参考下面拓展)
二:LRU算法
1.0,LRU (Least recently used) 最近最久未使用调度,其核心思想是"如果数据最近被访问过,那么将来被访问的几率也更高"; 最常见的实现是使用一个链表保存缓存数据,详细算法实现如下:
1,新数据插入到链表头部
2,每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
3,当链表满的时候,将链表尾部的数据丢弃
1.1,LRU的优缺点 1.命中率,当存在热点数据时,LRU的效率很好,但偶发性的,周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重 2,实现相对简单 3,命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部
2.0,LRU-K K代表最近使用的次数,因此LRU也可以认为是LRU-1,它主要是为了解决LRU算法"缓存污染"的问题,其核心思想是将"最近使用过1次"的判断标准扩展为"最近使用过K次"; 相比LRU要多维护一个队列,用于记录所有缓存数据被访问的历史,只有当数据的访问次数达到K次的时候,才将数据放入缓存.当需要淘汰数据时,LRU-k会淘汰第K次访问时间距离当前时间最大的数据.详细实现如下:
2.1,一,数据第一次被访问,加入到访问历史列表; 二,如果数据在访问历史列表里后达到K次访问,则按照一定(FIFO, LRU)淘汰; 三,当访问历史队列中的数据访问次数达到k次后,将数据l索引从历史队列删除,将数据移到缓存队列中,并缓存此数据,缓存队列重新按照时间排序; 四,缓存数据队列中被再次访问后,重新排序; 五,需要淘汰数据时,淘汰缓存队列中排在末尾的数据(即:淘汰倒数第K次访问离现在最久的数据)
2.2,LRU-K具有LRU的优点,同时能够避免LRU的缺点,实际应用中LRU-2是综合各种因素后最优的选择,LRU-3或者更大的K值命中率会高,但适应性差,需要大量的数据访问才能将历史记录缓存或者清除掉
2.3优缺,LRU-K降低了"缓存污染"带来的问题,命中率比LRU要高,但LRU-K队列是一个优先级队列,算法复杂度和代价相对LRU较高,并且LRU需要记录那些被访问过,但是没有达到K次也就是还没有放入缓存的对象,因此b内存消耗会比LRU要多,当然如果数据量很大的时候,内存消耗会比较可观
3.0,Two queues (2Q) 算法类似于LRU-2,不同点在于2Q将LRU-2算法中的访问历史队列(历史队列,还没有缓存数据)改为一个FIFO缓存队列,即: 2Q算法有两个缓存队列,一个是FIFO队列,一个是LRU队列.
3.1,当数据第一次访问时,2Q算法会将数据缓存在FIFO队列里面,当数据第二次被访问时,则将数据从FIFO队列移到LRU队列里面,两个队列各自按照自己的方法淘汰数据; 一,新访问的数据插入到FIFO队列, 二,如果数据在FIFO队列中一直没有被再次访问,则最终按照FOFO规则淘汰, 三,如果数据在FIFO队列中被再次访问,则将数据移到LRU队列头部, 四,如果数据在LRU队列再次被访问,则将数据移到LRU队列头部, 五,LRU队列淘汰末尾的数据
3.2,可能会感觉FIFO队列比LRU队列短,但并不代表这是算法的要求,实际应用中两者比例没有硬性要求


推荐阅读


上一篇：炒辣椒酱的家庭制作方法 炒辣椒酱的做法和配料

下一篇：以在文言文中的意思!文言文词语”辄”什么意思?