Cache内容为什么要经常替换?常用替换算法有几种?

Cache内容为什么要经常替换?常用替换算法有几种?
这是一个存储系统的题目,

二级缓存
CPU缓存（Cache Memory）位于CPU与内存之间的临时存储器,它的容量比内存小但交换速度快.在缓存中的数据是内存中的一小部分,但这一小部分是短时间内CPU即将访问的,当CPU调用大量数据时,就可避开内存直接从缓存中调用,从而加快读取速度.由此可见,在CPU中加入缓存是一种高效的解决方案,这样整个内存储器（缓存+内存）就变成了既有缓存的高速度,又有内存的大容量的存储系统了.缓存对CPU的性能影响很大,主要是因为CPU的数据交换顺序和CPU与缓存间的带宽引起的.
缓存的工作原理是当CPU要读取一个数据时,首先从缓存中查找,如果找到就立即读取并送给CPU处理；如果没有找到,就用相对慢的速度从内存中读取并送给CPU处理,同时把这个数据所在的数据块调入缓存中,可以使得以后对整块数据的读取都从缓存中进行,不必再调用内存.
正是这样的读取机制使CPU读取缓存的命中率非常高（大多数CPU可达90%左右）,也就是说CPU下一次要读取的数据90%都在缓存中,只有大约10%需要从内存读取.这大大节省了CPU直接读取内存的时间,也使CPU读取数据时基本无需等待.总的来说,CPU读取数据的顺序是先缓存后内存.
最早先的CPU缓存是个整体的,而且容量很低,英特尔公司从Pentium时代开始把缓存进行了分类.当时集成在CPU内核中的缓存已不足以满足CPU的需求,而制造工艺上的限制又不能大幅度提高缓存的容量.因此出现了集成在与CPU同一块电路板上或主板上的缓存,此时就把 CPU内核集成的缓存称为一级缓存,而外部的称为二级缓存.一级缓存中还分数据缓存（Data Cache,D-Cache）和指令缓存（Instruction Cache,I-Cache）.二者分别用来存放数据和执行这些数据的指令,而且两者可以同时被CPU访问,减少了争用Cache所造成的冲突,提高了处理器效能.英特尔公司在推出Pentium 4处理器时,用新增的一种一级追踪缓存替代指令缓存,容量为12KμOps,表示能存储12K条微指令.
随着CPU制造工艺的发展,二级缓存也能轻易的集成在CPU内核中,容量也在逐年提升.现在再用集成在CPU内部与否来定义一、二级缓存,已不确切.而且随着二级缓存被集成入CPU内核中,以往二级缓存与CPU大差距分频的情况也被改变,此时其以相同于主频的速度工作,可以为CPU提供更高的传输速度.
二级缓存是CPU性能表现的关键之一,在CPU核心不变化的情况下,增加二级缓存容量能使性能大幅度提高.而同一核心的CPU高低端之分往往也是在二级缓存上有差异,由此可见二级缓存对于CPU的重要性.
CPU在缓存中找到有用的数据被称为命中,当缓存中没有CPU所需的数据时（这时称为未命中）,CPU才访问内存.从理论上讲,在一颗拥有二级缓存的CPU中,读取一级缓存的命中率为80%.也就是说CPU一级缓存中找到的有用数据占数据总量的80%,剩下的20%从二级缓存中读取.由于不能准确预测将要执行的数据,读取二级缓存的命中率也在80%左右（从二级缓存读到有用的数据占总数据的16%）.那么还有的数据就不得不从内存调用,但这已经是一个相当小的比例了.目前的较高端的CPU中,还会带有三级缓存,它是为读取二级缓存后未命中的数据设计的—种缓存,在拥有三级缓存的CPU中,只有约 5%的数据需要从内存中调用,这进一步提高了CPU的效率.
为了保证CPU访问时有较高的命中率,缓存中的内容应该按一定的算法替换.一种较常用的算法是“最近最少使用算法”（LRU算法）,它是将最近一段时间内最少被访问过的行淘汰出局.因此需要为每行设置一个计数器,LRU算法是把命中行的计数器清零,其他各行计数器加1.当需要替换时淘汰行计数器计数值最大的数据行出局.这是一种高效、科学的算法,其计数器清零过程可以把一些频繁调用后再不需要的数据淘汰出缓存,提高缓存的利用率.
CPU产品中,一级缓存的容量基本在4KB到64KB之间,二级缓存的容量则分为128KB、256KB、512KB、1MB、2MB等.一级缓存容量各产品之间相差不大,而二级缓存容量则是提高CPU性能的关键.二级缓存容量的提升是由CPU制造工艺所决定的,容量增大必然导致CPU内部晶体管数的增加,要在有限的CPU面积上集成更大的缓存,对制造工艺的要求也就越高.
双核心CPU的二级缓存比较特殊,和以前的单核心CPU相比,最重要的就是两个内核的缓存所保存的数据要保持一致,否则就会出现错误,为了解决这个问题不同的CPU使用了不同的办法：
Intel双核心处理器的二级缓存
目前Intel的双核心CPU主要有Pentium D、Pentium EE、Core Duo三种,其中Pentium D、Pentium EE的二级缓存方式完全相同.Pentium D和Pentium EE的二级缓存都是CPU内部两个内核具有互相独立的二级缓存,其中,8xx系列的Smithfield核心CPU为每核心1MB,而9xx系列的 Presler核心CPU为每核心2MB.这种CPU内部的两个内核之间的缓存数据同步是依靠位于主板北桥芯片上的仲裁单元通过前端总线在两个核心之间传输来实现的,所以其数据延迟问题比较严重,性能并不尽如人意.
Core Duo使用的核心为Yonah,它的二级缓存则是两个核心共享2MB的二级缓存,共享式的二级缓存配合Intel的“Smart cache”共享缓存技术,实现了真正意义上的缓存数据同步,大幅度降低了数据延迟,减少了对前端总线的占用,性能表现不错,是目前双核心处理器上最先进的二级缓存架构.今后Intel的双核心处理器的二级缓存都会采用这种两个内核共享二级缓存的“Smart cache”共享缓存技术.
AMD双核心处理器的二级缓存
Athlon 64 X2 CPU的核心主要有Manchester和Toledo两种,他们的二级缓存都是CPU内部两个内核具有互相独立的二级缓存,其中,Manchester 核心为每核心512KB,而Toledo核心为每核心1MB.处理器内部的两个内核之间的缓存数据同步是依靠CPU内置的System Request Interface(系统请求接口,SRI)控制,传输在CPU内部即可实现.这样一来,不但CPU资源占用很小,而且不必占用内存总线资源,数据延迟也比Intel的Smithfield核心和Presler核心大为减少,协作效率明显胜过这两种核心.不过,由于这种方式仍然是两个内核的缓存相互独立,从架构上来看也明显不如以Yonah核心为代表的Intel的共享缓存技术Smart Cache.
___________________________________
前端总线
总线是将信息以一个或多个源部件传送到一个或多个目的部件的一组传输线.通俗的说,就是多个部件间的公共连线,用于在各个部件之间传输信息.人们常常以MHz表示的速度来描述总线频率.总线的种类很多,前端总线的英文名字是Front Side Bus,通常用FSB表示,是将CPU连接到北桥芯片的总线.选购主板和CPU时,要注意两者搭配问题,一般来说,如果CPU不超频,那么前端总线是由 CPU决定的,如果主板不支持CPU所需要的前端总线,系统就无法工作.也就是说,需要主板和CPU都支持某个前端总线,系统才能工作,只不过一个CPU 默认的前端总线是唯一的,因此看一个系统的前端总线主要看CPU就可以.
北桥芯片负责联系内存、显卡等数据吞吐量最大的部件,并和南桥芯片连接.CPU就是通过前端总线（FSB）连接到北桥芯片,进而通过北桥芯片和内存、显卡交换数据.前端总线是CPU和外界交换数据的最主要通道,因此前端总线的数据传输能力对计算机整体性能作用很大,如果没足够快的前端总线,再强的CPU也不能明显提高计算机整体速度.数据传输最大带宽取决于所有同时传输的数据的宽度和传输频率,即数据带宽＝（总线频率×数据位宽）÷8.目前PC机上所能达到的前端总线频率有266MHz、333MHz、400MHz、533MHz、800MHz几种,前端总线频率越大,代表着CPU与北桥芯片之间的数据传输能力越大,更能充分发挥出CPU的功能.现在的CPU技术发展很快,运算速度提高很快,而足够大的前端总线可以保障有足够的数据供给给CPU,较低的前端总线将无法供给足够的数据给CPU,这样就限制了CPU性能得发挥,成为系统瓶颈.显然同等条件下,前端总线越快,系统性能越好.
外频与前端总线频率的区别：前端总线的速度指的是CPU和北桥芯片间总线的速度,更实质性的表示了CPU和外界数据传输的速度.而外频的概念是建立在数字脉冲信号震荡速度基础之上的,也就是说,100MHz外频特指数字脉冲信号在每秒钟震荡一万万次,它更多的影响了PCI及其他总线的频率.之所以前端总线与外频这两个概念容易混淆,主要的原因是在以前的很长一段时间里（主要是在Pentium 4出现之前和刚出现Pentium 4时）,前端总线频率与外频是相同的,因此往往直接称前端总线为外频,最终造成这样的误会.随着计算机技术的发展,人们发现前端总线频率需要高于外频,因此采用了QDR（Quad Date Rate）技术,或者其他类似的技术实现这个目的.这些技术的原理类似于AGP的2X或者4X,它们使得前端总线的频率成为外频的2倍、4倍甚至更高,从此之后前端总线和外频的区别才开始被人们重视起来.此外,在前端总线中比较特殊的是AMD64的HyperTransport.