作为我操作系统作业的一部分,我被要求比较先进先出和最近最少使用的页面替换策略对给定页面访问顺序产生的页面错误数量。令人困惑的是,似乎FIFO产生的页面故障比LRU少。这是可能的,还是我犯了一个错误?FIFO页面替换策略可能超越LRU吗?
回答
是的,FIFO有可能击败LRU。我能想到的最小例子,
缓存大小:2页。
访问模式:A,B,A,C
在此之后,LRU缓存包含 “A,C”,而FIFO缓存包含 “B,C”。到目前为止,他们每个都错过了3次。所以如果下一页访问是“B”,那么FIFO会击败LRU。如果它是“A”,LRU会跳过FIFO。如果是其他任何东西,他们仍然束缚。
这必须是最小的可能的例子:当cachesize = 1时,当然没有cachesize = 1的例子是可能的,因为LRU = FIFO。并且没有cachesize = 2,totalnumaccesses = 4的例子是可能的,因为这样一个例子必须在第三次访问中包含驱逐,但是LRU和FIFO总是在第三次访问中驱逐相同的项目(如果有的话),所以在这里不会发生区分。 – 2016-04-06 02:30:38
不给你答案就很难给你一个提示。你为什么不尝试为自己设置问题?把自己放在你的老师的脑海里,一个扭曲的黑暗的地方,试着以这样一种方式来设置问题,使你的(同胞)学生深入思考这个问题。
理论上显然将取决于给定的序列。对于“扭曲的黑暗地点”+1,有一个非常好的建议可以想到它:D – 2012-03-05 16:11:59
- 1. 在这里LRU和FIFO页面替换是否正确完成?
- 2. Spark的当前驱逐策略是什么? FIFO还是LRU?
- 3. 实现LRU页面替换算法
- 4. MESI协议和LRU策略
- 5. Redis TTL vs“allkeys-lru”驱逐策略
- 6. FIFO缓存vs LRU缓存
- 7. windows页面文件策略
- 8. Redis 2.2.x文档是否可用? (特别是LRU策略)
- 9. 在C中的FIFO页面替换,得到错误的输出
- 10. 我们可以在O(1)中获得LRU(最近最少使用)页面替换算法吗?
- 11. vmalloc页面可以交换页面吗?
- 12. Excel/Access的替换或迁移策略
- 13. 超越服务器端请求的同源策略 - NodeJS/Express
- 14. 番石榴缓存/可配置逐出/缓存替换策略
- 15. 在Windows中替换程序可执行文件的策略
- 16. 元素扩展超越页面
- 17. 重定向到登录页面策略
- 18. 跨越跨域策略获取JavaScript
- 19. History.js和同源策略穿越到SSL
- 20. 使用LRU策略的默认内存缓存
- 21. Java策略模式 - 我可以在Context类中委托策略实例吗?
- 22. 多页表单的策略?
- 23. 超越比较忽略单方评论
- 24. 用RJS替换页面
- 25. 页面替换算法
- 26. VS2008开始页面替换
- 27. 忽略SVN忽略...可能吗?
- 28. 这是移动单页应用程序中页面管理的可行设计/策略吗?
- 29. 阅读交换策略
- 30. 蓝绿色转换策略
当然这是可能的。没有一种算法在页面替换中是最好的。 LRU在现实世界的使用情况下优于FIFO,但确实有可能建立一个相反的情况。 – 2012-03-05 16:03:03
为您自己的教诲推荐的扩展:给定_any_两个页面替换策略X和Y,证明存在一个访问序列,使得X具有的页面故障少于Y. – Nemo 2012-03-05 16:11:23