2006-07-15

缓存在计算机中的使用

Views: 9048 | Add Comments

如果计算机中或者计算机间通信的两个实体的速度之比为1:100或者更悬殊时,那么它们之间就有使用缓存(Cache)的必要了。例如CPU/主存与磁盘,CPU/主存与键盘,CPU/主存与打印机等。缓存最先被使用在硬件上,然后在软件中也被应用。最著名的应该是CPU与内存(主存)之间的缓存了。

缓存的速度比被缓存者的速度快很多。缓存是被缓存者的一个相联的副本,更重要的,它是被缓存者的访问接口。要想访问被缓存者,必须先访问缓存。缓存的改变将导致被缓存者的改变,这就是缓存的一致性问题。主要有两种方法保持缓存的一致性。一种是全写法,另一种是写回法。前一种是在缓存发生改变的同时改变被缓存者;后一种是在缓存改变达到一定程序时才改变被缓存者。前一种安全性更好,但效率受影响;后一种相反。

缓存的性能指标除了速度之外,最重要的就是合命中率h。命中率等于访问缓存就能找到数据的次数除以总的访问次数,命中率与算法有关。注意,如果数据不在缓存中,那么将浪费一次访问缓存的时间。所以缓存系统的平均访问时间为h*nc+(1-h)*(nc+n)(全概率公式),其中nc为缓存的访问每一次时间,n为被缓存者的每一次访问时间。

由于缓存容量小,所以需要替换缓存中的某些数据。相关的算法有:FIFO算法,LRU算法,RAND算法。

  • FIFO算法:也就是先进先出算法,最先被缓存的数据将被替换。
  • LRU算法:最近最少使用算法,在软件中一般使用链表来实现。数据每被使用一次,它将被放到表头,被替换的是表尾的数据。这种算法效率很好,所以最常用。
  • RAND算法:随机算法,随机替换数据。

缓存系统的一个重要问题是缓存与被缓存者的映射(映像)问题,即如何识别缓存中的数据就是被缓存者中的数据。这里使用关键字,如果是内存,使用内存的地址,在软件中使用实体的标识(id)。即缓存中必须有一个字段用来保存数据的标识。相关的算法有

  • 全相联映射:缓存中有一个字段用来保存被缓存者数据的关键字。访问的时候迭代搜索,或者使用HASH法保存和搜索。HASH法浪费缓存的容量,一般在软件中使用,硬件中不使用。
  • 直接映射:如果关键字是有规律的,如内存地址。那么抽取关键字的一部分,另一部分被隐含在缓存和被缓存者的物理空间关系或者其它关系中。一个例子是,如果内存中有0,1,2,3,4,5,6,7号一共8个数据,缓存中有0,1共2个数据。规定0号缓存只能缓存内存中的0,2,4,6号数据中的一个,1号缓存只能缓存1,3,5,7号数据中的一个。当需要访问内存数据n时,先计算出CID = n MOD 2,所以只查找缓存CID,而不需要迭代整个缓存。如果你将上面的关键字转换为二进制,取模运算可以省略,因为模的值已经被隐含在二进制数中,所以关键字的保存也可以只保存二进制数中不包含模值的那部分。
  • 组相联映射:是上面两种的组合。将缓存分成多个组,组的查找使用直接映射,组内数据的查找使用全相联映射。

因为速度总是与价格联系的,所以缓存永远不会消失。提高缓存性能可以从缓存的硬件性能,替换算法,映射算法3方面着手,还有就是系统的分析,即哪些数据适合被缓存。

Related posts:

  1. GUI 的架构设计
  2. 软件体系结构模式-层
  3. 技术的本质 – 围观不会设置User-Agent的美国菜鸟
  4. 上海交大关于“汉芯”系列芯片涉嫌造假的调查结论与处理意见的通报
  5. 应该写一个Debian Linux的详细教程了
Posted by ideawu at 2006-07-15 07:52:08

Leave a Comment