局部性通常有两种不同的形式:时间局部性和空间局部性。
时间局部性
在一个具有良好的时间局部性的程序中,被访问过一次的存储器位置很可能在不远的将来会被再次访问。
空间局部性
在一个具有良好空间局部性的程序中,如果一个存储器位置被访问了一次,那么程序很可能在不远的将来访问附近的一个存储器位置。
局部性原理的应用
局部性原理对硬件和软件的设计都有着极大的影响,从硬件到操作系统、再到应用程序,它们的设计都用到了局部性原理。
正是由于局部性原理的存在,在硬件层通过引入高速缓存存储器能够在很大程度上提升程序运行的速度。操作系统的虚拟地址空间的技术,以及缓存磁盘文件系统中最近被使用的磁盘块等都用到了局部性原理。在应用程序设计中应用到的缓存思想。
局部性的简单原则
- 重复引用同一个变量的程序有良好的时间局部性。
- 做顺序访问的程序具有良好的空间局部性。
- 循环结构具有良好的空间局部性和时间局部性。循环体越小,循环迭代次数越多,局部性越好。
网友评论