存储分层加速源自局部性原理

下面就得引入必备的“程序的局部性原理”知识了。

　　程序的局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个存储区域。局部性原理又表现为：时间局部性（temporal locality）和空间局部性（spatial locality）。

 
程序的调用返回行为

　　时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执　行；如果某数据被访问，则不久之后该数据可能再次被访问。

空间局部性

　　空间局部性是指一旦程序访问了某个存储单元，则不久之后。其附近的存储单元也将被访问。

 　 空间局部性和时间局部性是有区别的。空间局部性指执行涉及很多簇聚的存储器单元的趋势，这反映了处理器顺序访问指令的倾向，同时，也反映了程序顺序访问数据单元的倾向，如处理数据表。时间局部性指处理器访问最近使用过的存储器单元的趋势，例如，当执行一个循环时，处理器重复执行相同的指令集合。

   传统上，时间局部性是通过将最近使用的指令和数据值保存到高速缓存中并使用高速缓存的层次结构实现的。空间局部性通常是使用较大的高速缓存并将预取机制集成到高速缓存控制逻辑中实现的。

　　举例：当硬盘受到CPU指令控制开始读取数据时，硬盘上的控制芯会控制磁头把正在读取的簇的下一个或者几个簇中的数据读到硬盘的缓存中（由于硬盘上数据存储时是比较连续的，所以读取命中率较高），当需要读取下一个或者几个簇中的数据的时候，硬盘则不需要再次读取数据，直接把缓存中的数据传输到内存中就可以了，由于速度远远高于磁头读写的速度，所以能够达到明显改善能的目的，即根据空间局部性原理，预测下一步所需要的数据，并将其提前写入内存。

　　为了保证CPU访问时有较高的命中率，内存储器（包括CPU缓存和内存）中的内容应该按一定的算法替换。较常用的算法是“最近最少使用算法”（LRU算法），它是将最近一段时间内最少被访问过的行淘汰出局。因此需要为每行设置一个计数器，LRU算法是把命中行的计数器清零，其他各行计数器加1。当需要替换时淘汰行计数器计数值最大的数据行出局。这是一种高效、科学的算法，其计数器清零过程可以把一些频繁调用后再不需要的数据淘汰出，提高利用率。这样内存储器中的数据在更新的时候则会根据时间局布性原理把读取频率高的及其周围的相关数据留下，把低导入虚拟内存或者淘汰掉（关于虚拟内存后面会有描述）。

　　在层次存储结构中的每一级都采用程序局部分布原理的原理来预读和更替数据。由于预读的命中率很高，故续约了时间，这也是采用层次存储结构的基础。