-
存储系统 编辑
局部性原理
所谓局部性原理, 是指CPU访问存储器时, 无论是存取指令还是存取数据, 所访问的存储单元都聚集在一个较小的连续区域中。
局部性通常有两种形式:
时间局部性(temporal locality):如果一个信息项正在被访问, 那么在近期它很可能还会被再次访问。程序循环、堆栈等是产生时间局部性的原因。
空间局部性(spatial locality):在最近将要用到的信息很可能与现在正在使用的信息在空间地址上是临近的。
现代计算机系统的各个层次,从硬件到操作系统,再到应用程序,它们的设计都利用了局部性原理。在硬件层,局部性原理允许计算机设计者通过引入小而快速的高速缓冲存储器来保存最近被引用的指令和数据项,从而提高对主存的访问速度。在操作系统级,局部性原理允许系统使用主存作为虚拟地址空间最近被引用的高速缓存,局部性原理也允许系统利用主存来缓存磁盘文件系统中最近被使用的磁盘块等。局部性原理在应用程序的设计中也扮演着重要的角色, 例如, Web浏览器将最近被引用的文档放在本地磁盘上, 利用的就是时间局部性。大量的Web服务器将最近被请求的文档放在前端磁盘高速缓存中, 这些缓存能满足用户对这些文档的请求,而不需要服务器的任何干涉。
下面用三个例子来说明程序对数据引用的局部性。
例1:
int sumvec(int v)
{
int i=0,sum=0;
for(int i=0; i
{
sum+=v;
}
return sum;
}
上述代码中,变量sum在每次循环迭代中被引用一次,具有时间局部性。对于数组v的元素,按照它们存储在存储器中的顺序,被依次读取,因此具有空间局部性,但是每个数组元素只被访问一次, 所以不具有时间局部性。可见, sumvec函数对数据的访问既有空间局部性,也有时间局部性。
例2:
int sumarrayros(int v)
{
int i=0;j=0;sum=0;
for(i=0;i
for(j=0;j
{
sum+=v ;
}
return sum;
}
上述代码中,数组v的元素都是按照步长1来访问的,因此具有很好的空间局部性(数组元素是按照行顺序存储的)。
例3:
int sum array ros(int v)
{
inti=0;j=0;sum=0;
for(j=0;j
for(i=0;i
{
sum+=v;
}
return sum;
}
上述代码中,数组v的元素都是按照步长N来访问的,因此其空间局部性很差。 综上,可以得到如下结论:
1)重复引用同一个变量的程序有良好的时间局部性;
2)对于具有步长为k的引用模式的程序,步长越小,空间局部性越好。在存储器中以大步长跳来跳去的程序,空间局部性会很差;
3)对于取指令来说,循环有好的时间和空间局部性。循环体越小,循环迭代次数越多,局部性越好。