江苏龙网

  1. 主页 > 生活百科 > >

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


3.3,2Q算法命中率高于LRU,切需要两个队列,但两个队列本身都比较简单,代价是FIFO和LRU代价之和; 2Q算法和LRU-2算法命中率类似,内存消耗也比较接近,但对于最后的缓存数据来说,2Q减少一次从原始储存读取数据或者计算数据的操作
4.0,Multi Queue (MQ) 算法根据访问频率将数据划分为多个队列,不同的队列具有不同的访问优先级,其核心思想是:优先缓存访问次数多的数据
4.1,MQ算法将缓存划分为多个LRU队列,每个队列对应不同的访问优先级,访问优先级是根据访问次数计算出来的,详情: 一,新插入的数据放入Q0; 二,每个队列按照LRU管理数据; 三,当数据访问次数达到一定次数需要提升优先级时将数据从当前队列删除,加入到高一级的队列头部; 四,为了防止高优先级数据永远不被淘汰,每个队列淘汰数据时,将数据从缓存中删除,将数据加入Q-history头部; 五,需要淘汰数据时,从最低一级队列开始按照LRU淘汰,每个队列淘汰数据时,将数据从缓存中删除,将数据索引加入Q-history头部; 六,如果数据在Q-history中被重新访问,则重新计算其优先级,移到目标队列的头部; 七,Q-history按照LRU淘汰数据的索引
4.2,MQ降低了"缓存污染"带来的问题,命中率比LRU高,但MQ需要维护多个队列,切需要维护每个数据的访问时间,复杂度比较高,并且MQ需要记录每个数据的访问时间,需要定时扫码所有队列,代价也比较高
4.3,虽然MQ的队列看起来数量比较多,但由于所有队列之和受限于缓存容量的大小,因此这里多个队列长度之和和一个LRU队列是一样的,因此队列扫码性能接近
小结: 命中率LRU-2 > MQ(2) > 2Q > LRU ; 复杂度 LRU-2 > MQ(2) > 2Q >LRU ; 代价 LRU-2 > MQ(2) > 2Q > LRU ; 需要注意的是,命中率并不是越高越好,实际中应该根据业务需求和对数据的访问情况进行分析选择,LRU虽然看起来命中率低一些,切存在"缓存污染"的问题,但其简单切代价小,实际中反而应用更多
拓展:基于 双链表的 LRU 实现: 一,传统意义的LRU算法是每一个Cache对象设置一个定时器,每次Cache命中则给定时器 +1,而Cache用完需要淘汰旧内容,放置新内容时就查看所有的计时器,并将使用的内容替换掉; 其弊端很明显,如果Cache的数量少,问题不大,但如果Cache的空间过大,达到10W或者100W以上,一旦需要淘汰,则需要遍历所有计时器,其性能与资源消耗巨大,效率也就非常的慢了; 二,双链表原理,将Cache的所有位置都用双链表连接起来,当一个位置被命中之后,就将通过调整链表的指向,将该位置调整到链表头的位置,新加入Cache直接加到链表头中,这样在多次进行Cache操作后,最近被命中的就会被向链表头方向移动,而没有命中的则向链表后部移动,链表尾则表示最近最少命中的Cache,当需要替换内容时我们只需要淘汰链表最后的部分即可!
如果错误或者建议,欢迎下方留言,谢谢!
Q6：FIFO算法（假定开始时先把1,2,3,4号页面装入内存）
FIFO：
页412512345
内存423413412512nono532534no
LRU：
页412512345
内存423413412512nono312342345
楼主 看一下这个
（缺页发生也就是需要进行 交换初始 装入内存的 三个页是不发生缺页的 所以 从4开始）
上面是 装入的 页面下面是装入后 内存的状态（no代表不缺页）
我 也是才看过 三级的教程大概算了一下
FIFO 是 先进 先出 ，也就是的 每次 总是 不 最早进来的 换出去和 页面值 无关（此算法是基于内存块的 顺序，最长未更新的内存块 ，先更新，明白这意思吧，可以对照前面的数据看下）
LRU 是 更新 最长为使用的 页面，也就是 这个算法 是根据页面值来交换的
也就是新装入的 页面值 如果 在内存快里面 有就会更新这个 页面的 某个标记状态（标记 其多久未使用，其实就是个 变量，很容易实现）
显然 一直到5都是和FIFO算法 是一样的 ，
为什么呢，因为前几页 都是 缺页的 并没有 改变 标记变量，所以 就 按照先装入，则 距今未使用时间最长，则 先交换的原则啦
开始需要1（5后面那个） 那么内存 目前状态时 512，1是在内存中的 不发生缺页，】
所以更新 标记变量（标明 1刚被使用过）
然后需要 2内存中依然 存在则 更新2的 标记变量，则现在内存中 任然是 512 但是 标记变量已经变了2最新，1次之 ，5最久 （最久未使用）所以下次 交换就先 换 5
内存 变为 321现在3最新，2次之，1最久下次缺页 就换1
思路 就是 这样 。
关于fifo算法和fifo算法模拟的介绍到此就结束了，不知道你从中找到你需要的信息了吗？如果你还想了解更多这方面的信息，记得收藏关注本站 。


推荐阅读


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

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