扫码获取 VIP 码
添加管理员微信获取 VIP 码
程序局部性原理在计算机体系结构领域具有基础性和支柱性的地位，由计算机科学先驱彼得·丹宁于二十世纪六十年代系统化地提出和论证。丹宁通过对大量实际程序运行时的内存访问地址序列进行统计分析，发现了一个具有普遍性的现象：在任意一段足够短的时间窗口内，程序倾向于只访问整个地址空间中一个很小的子集，而非均匀随机地散布在整个地址空间中。他将这一现象抽象为程序局部性原理，并进一步将其细分为时间局部性和空间局部性两个维度。这一发现不仅具有理论上的优美性，更对整个计算机工业产生了深远的影响——可以说，没有对局部性原理的深刻理解，就没有现代计算机存储层次体系的设计，也就没有今天我们习以为常的高性能计算能力。
程序局部性原理之所以被冠以"原理"而非"假设"或"猜想"，是因为它不仅是经由海量实证数据反复验证的统计规律，更有着深刻的程序结构和编程语言层面的解释基础。绝大多数程序都包含循环结构和顺序执行的代码段——循环体会使同一组指令和数据被反复访问，这是时间局部性的最直接来源；顺序执行会使指令指针沿代码段地址连续递增，数组遍历会使数据访问地址连续递增，这些顺序模式是空间局部性的主要来源。此外，程序运行时的栈空间使用模式天然地表现出强局部性——函数调用时栈指针向下增长分配新的栈帧，函数返回时栈指针向上收缩释放栈帧，最近分配的栈帧数据往往就是当前最活跃的数据，这在行为上同时满足时间局部性和空间局部性的特征。这些根植于程序结构和编程语言实现层面的深层原因，使得局部性不是一个偶然现象或特例现象，而是横跨几乎所有编程语言和所有应用领域的普适性程序行为特征。
在软考系统架构设计师、系统分析师和软件设计师等科目中，程序局部性原理通常在计算机组成与体系结构或操作系统板块中出现，考查形式涵盖概念辨析、原理应用和与高速缓存工作机制的结合分析。
程序局部性原理的最重要工程应用，是它为现代计算机存储层次体系的设计提供了理论基础。存储层次体系的基本思想是利用时间局部性将最近访问过的数据保留在靠近CPU的高速小容量存储器中以提高重复访问的命中率，利用空间局部性以块为单位将数据从低速大容量存储器预取到高速小容量存储器中以捕捉邻近数据的后续访问。这个简单而深刻的工程思想，使得一个配备了几KB一级缓存和几MB二级缓存的CPU，能够在对数GB主存空间的访问中获得超过百分之九十甚至百分之九十五以上的缓存命中率。如果没有局部性原理作为理论基础，缓存将无法有效地工作——因为如果程序的内存访问模式是均匀随机的，任何缓存策略都无法提升命中率，高速缓存的引入将变成纯粹的硬件成本浪费。
时间局部性指导了高速缓存的替换策略设计。当CPU需要访问一个内存地址时，硬件首先检查该地址的数据是否已经存在于高速缓存中。如果存在（即缓存命中），直接从高速缓存读取，延迟极低；如果不存在（即缓存未命中），则需要从主存甚至更低层级的存储器中加载包含该地址的数据块到高速缓存中。当高速缓存已满而需要腾出空间加载新的数据块时，就需要依据某种替换策略选择一个现存的数据块从缓存中驱逐。替换策略的设计直接建立在对时间局部性的理解之上——最近最少使用策略（LRU策略）优先驱逐最长时间未被访问的数据块，其理论假设是时间局部性意味着最近被访问的数据在未来最可能被再次访问，而久未访问的数据块在未来被访问的概率最低，是LRU替换策略直接建立在时间局部性的理论假设之上——最近被访问的数据在未来最可能被再次访问，而久未访问的数据在未来被访问的概率最低，因此后者是当前最优的驱逐候选。LRU策略的工程实现需要在每次缓存访问时更新被访问数据块的时间戳信息，在发生缓存未命中需要驱逐时扫描所有缓存行找到时间戳最旧的那个进行替换。在硬件实现中维护精确的全局时间戳代价较高，因此实际CPU缓存通常采用伪LRU策略——例如使用一棵二叉树来近似跟踪每个缓存组的访问历史，每次驱逐时选择在二叉树中位于"久未访问"一侧的缓存行。CLOCK算法则是操作系统虚拟内存页面置换中广泛使用的另一种LRU近似实现——通过一个访问位和一个循环移动的指针来模拟LRU的行为，当需要驱逐页面时指针扫描页面直到找到一个访问位为零的页面，在扫描过程中将遇到的所有访问位为一的页面清零。CLOCK算法的精妙之处在于用极低的硬件开销（每个页面一个比特的访问位和一个指针）近似实现了LRU的大部分性能优势，是计算机系统工程中"用最小的工程代价换取接近最优的理论效果"这一设计哲学的经典案例。
空间局部性指导了高速缓存的行大小和预取策略的设计。高速缓存并非以单个字节为单位从主存加载数据，而是以固定大小的缓存行为单位。常见的缓存行大小为六十四字节，这意味着当CPU访问某个内存地址时，硬件会将包含该地址的整个六十四字节对齐块一次性地从主存加载到高速缓存中。这样做的假设是：CPU在访问了当前地址后，很可能接下来会访问该地址附近的其他地址——这正是空间局部性的精确应用。预取技术则将空间局部性的利用推向了一个更前瞻的层次——硬件预取器通过监测CPU的内存访问模式，在CPU尚未实际请求某些地址的数据之前就主动将这些数据提前加载到高速缓存中，试图在指令或数据被实际需要时能够命中缓存，从而隐藏主存访问的高延迟。
现代计算机的存储层次从离CPU最近到最远通常分为四个层级，每一级比上一级容量更大但访问速度更慢一个数量级左右，程序局部性原理使得绝大多数内存访问都能在较快的层级中命中。寄存器位于最内层，数量通常只有几十个，由编译器在寄存器分配阶段显式管理，访问延迟为零到一个时钟周期。一级缓存（L1）通常分为独立的指令缓存和数据缓存，容量在数十KB级别，访问延迟约为一到四个时钟周期。二级缓存（L2）通常是指令和数据统一的缓存，容量在数百KB到数MB级别，访问延迟约为十到二十个时钟周期。三级缓存（L3）在所有CPU核心之间共享，容量在数MB到数十MB级别，访问延迟约为三十到五十个时钟周期。主存（DRAM）位于CPU芯片外部，容量在数GB到数百GB，访问延迟约为一百到三百个时钟周期。现代CPU的大多数内存访问都能在一级缓存中命中（命中率通常超过百分之九十），在二级缓存中进一步捕获大部分一级缓存未命中的访问，最终只有极少数访问需要穿透到主存。这种金字塔式的命中率分布，正是程序局部性原理在硬件层面最直接、最有力的实证。
指令访问的局部性是程序局部性原理最直观也最强有力的体现。程序执行过程中指令指针在绝大多数时间内沿着代码段的字节地址顺序逐条递增，仅在遇到条件分支指令、无条件跳转指令、函数调用指令和函数返回指令时才发生跳跃。这种以顺序执行为绝对主体、跳跃执行为例外的指令访问模式，天然地同时表现出空间局部性（相邻指令地址被连续依次访问）和时间局部性（循环体内的指令序列被反复执行多次）。指令访问的局部性强度通常显著高于数据访问的局部性——因为指令流的顺序性比数据流的顺序性更为稳定和可预测，程序中的分支指令占比通常不超过百分之二十，意味着超过百分之八十的指令是顺序执行的。这也是为什么指令高速缓存通常可以使用比数据高速缓存更简单的预
本篇完！