1、页面置换算法：FIFO 、LRU、LFU
腾讯面试时被问了，“怎么设计服务器缓存”，“你是指硬件上的吗？”，“都一样”！！！
Cache是个传统的课题，在处理机、操作系统和数据库等领域都有深入的研究.传统的cache替换算法有LFU(least frequency used)和LRU(least recently used)及LRU的变种LRFU和LRU-K等. LRU是将上一次使用时间最短的数据优先存放在cache中. LFU则是将过去使用频率高的数据优先保存在cache中.这两种算法代表了两个极端，LFU使用数据的访问频率，有利于数据的总体优化使用，但不利于数据访问方式的变化和猝发访问.LRU依据最近一次的访问时间，能较好地适应数据访问的变化，但只是在访问时间上的局部优化，没有考虑数据长期的访问特性.有一些算法试图在数据的访问时间和访问频率两方面达到平衡.如LRFU算法给近几次访问时间乘上一个与访问频率有关的权重，以加权值来取得两者之间的平衡.LRU-K算法则是使用最后第K次访问时间来扩展LRU算法，依靠K值的大小进行平衡.它们都是对访问时间的修正，是对LRU算法的改进.
LRU和LFU是不同的!
LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面!
LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页!
比如,第二种方法的时期T为10分钟,如果每分钟进行一次调页,主存块为3,若所需页面走向为2 1 2 1 2 3 4
注意,当调页面4时会发生缺页中断
若按LRU算法,应换页面1(1页面最久未被使用) 但按LFU算法应换页面3(十分钟内,页面3只使用了一次)
可见LRU关键是看页面最后一次被使用到发生调度的时间长短,
而LFU关键是看一定时间段内页面被使用的频率!
也就是说：
LRU算法适合：较大的文件比如游戏客户端（最近加载的地图文件）
LFU算法适合：较小的文件和教零碎的文件比如系统文件、应用程序文件
其中：LRU消耗CPU资源较少，LFU消耗CPU资源较多。