1. 计算机组成原理中的局部性原理是什么
时间局部性就是，最近被访问的存储单元，在之后很有可能会被再次访问到；
空间局部性就是，对于正在被访问的存储单元附近的位置，在之后很有可能会被访问到。
这个很容易理解，以一段常见的代码为例：
for(i = 0; i <= 100; i++) {
sum += array[i];
}
其中i、sum 这些元素现在正被访问，在之后也一定会被重复访问，这就是时间局部性；
而array这个数组，现在访问了array[0]的位置，那之后紧接着就会访问它附近的位置，比如array[1]、array[2]等等，这就是空间局部性。
根据局部性原理，可以做一些相关设计。比如cache就是利用局部性原理设计出来的。
2. 空间局部性和时间局部性的策略是什么
进程运行时，在一段时间里，程序的执行往往呈现高度的局部性，包括时间局部性和空间局部性。时间局部性是一旦一个指令被执行了，则在不久的将来，它可能再被执行。空间局部性是一旦一个指令一个存储单元被访问，那么它附近的单元也将很快被访问。
程序的局部性原理是虚拟存储技术引入的前提。虚拟存储的实现原理是，当进程要求运行时，不是将它全部装入内存，而是将其一部分装入内存，另一部分暂时不装入内存。
(2)存储程序结构利用了时间局部性扩展阅读:
时间局部性
如果在某一点时访问了存储器的特定位置，则很可能在不久的将来将再次访问相同的位置。在对相同存储器位置的相邻访问之间存在时间接近性。
在这种情况下，通常努力将访问过的数据的副本存储在可以被更快访问的特殊存储器中。时间局部性是空间局部性的特殊情况，即当预期位置与当前位置相同时。
空间局部性
如果特定存储位置在特定时间被访问，则很可能在不久的将来访问附近的存储位置。在这种情况下，通常尝试猜测当前访问周围的区域的大小和形状，对于该区域，值得准备更快的访问。
局部性的原因
局部性有几个原因。这些原因是某些方面要实现的目标或接受的情况。以下原因不是不相交的；事实上，下面的列表从最一般的情况到特殊情况：
可预测性:事实上，局部性只是计算机系统中一种可预测的行为。
程序结构
局部性通常因为创建计算机程序的方式而发生，用于处理可决定的问题。通常，相关数据存储在存储器中的附近位置。计算中常见的一种模式涉及几个项目的处理，一次一个。这意味着如果进行大量处理，则将访问单个项目多次，从而导致时间局部性。
此外，移动到下一项意味着将读取下一项，导致空间局部性，因为存储器位置通常被批量地读取。
线性数据结构
局部性通常因为代码包含循环，倾向于通过索引访问数组或其他数据结构。当相关数据元素被线性地排列和访问时，发生顺序局部性，即空间局部性的特殊情况。例如，从基地址到最高元素的一维数组中的元素的简单遍历将利用存储器中数组的顺序局部性。
当线性遍历在具有相同结构和大小的相邻数据结构的较长区域上，访问每个结构的相互对应的元素而不是整个结构时，发生更一般的等距局部性。这是当矩阵被表示为行的顺序矩阵并且需要访问矩阵的单个列时的情况。
内存层次结构的效率
虽然随机存取存储器使程序员能够在任何时间在任何地方读取或写入，但在实践中，等待时间和吞吐量会受到高速缓存的效率的影响，这通过增加访问局部性来改进。访问局部性差导致缓存抖动和缓存污染，为了避免它，具有弱局部性的数据元素可以从缓存旁路。
参考资料：网络-访问局部性
3. 什么是存储访问的局部性原理,它分别成哪两个方面的局部性
程序局部性原理:虚拟存储管理的效率与程序局部性程序有很大关系。根据统计，进程运行时，在-
段时间内，其程序的执行往往呈现岀高度的局限性，包括时间局部性和空间局部性
1、时间局部性:是指若一条指令被执行，则在不久的将来，它可能再被执行
2、空间局部性:是指一旦一个存储单元被访问，那它附近的单元也将很快被访问
4. 局部性原理
局部性通常有两种形式：
时间局部性（temporal locality）：在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次引用。
空间局部性（spatial locality）在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。
程序员应该理解局部性原理，一般而言，有良好局部性的程序比局部性差的程序运行得更快。
现代计算机系统的各个层次，从硬件到操作系统，再到应用程序，它们的设计都利用了局部性。
在硬件层，局部性原理允许计算机设计者通过引入小而快速的高速缓存存储器来保存最近被引用的指令和数据项，从而提高对主存的访问速度。
在操作系统级，局部性原理允许系统使用主存作为虚拟地址空间最近被引用块的高速缓存。类似的，操作系统用主存来缓存磁盘文件系统中最近被使用的磁盘块。
在应用程序的设计中，局部性原理也扮演者重要角色。如Web浏览器将最近被引用的文档放在本地磁盘上，利用的就是时间局部性。大容量的Web服务器将最近被请求的文档放在前端磁盘高速缓存中，这些缓存能满足对这些文档的请求，而不需要服务器的干预。
5. 存储器层次结构中的缓存
《深入理解计算机系统》p422
6.1 存储器层次结构中的缓存
一般而言,高速缓存( cache ,读作“ cash ”)是一个小而快速的存储设备,它作为存储在更大、也更慢的设备中的数据对象的缓冲区域。使用高速缓存的过程称为缓存( caching ,读作“ cashing ”)。存储器层次结构的中心思想是,对于每个 k ,位于 k 层的更快更小的存储设备作为位于 k 十1层的更大更慢的存储设备的缓存。换句话说,层次结构中的每一层都缓存来自较低一层的数据对象。例如,本地磁盘作为通过网络从远程磁盘取出的文件(例如 Web 页面)的缓存,主存作为本地磁盘上数据的缓存,依此类推,直到最小的缓存—— CPU 寄存器组。图6-22展示了存储器层次结构中缓存的一般性概念。第 k 十1层的存储器被划分成连续的数据对象组块( chunk ),称为块( block )。每个块都有一个唯一的地址或名字,使之区别于其他的块。块可以是固定大小的(通常是这样的),也可以是可变大小的(例如存储在 Web 服务器上的远程 HTML 文件)。例如,图6-22中第 k 十1层存储器被划分成16个大小固定的块,编号为0~15。
类似地,第 k 层的存储器被划分成较少的块的集合,每个块的大小与 k 十1层的块的大小一样。在任何时刻,第 k 层的缓存包含第 k 十1层块的一个子集的副本。例如,在图6-22中,第 k 层的缓存有4个块的空间,当前包含块4、9、14和3的副本。
数据总是以块大小为传送单元( transfer unit )在第 k 层和第 k +1层之间来回复制的。虽然在层次结构中任何一对相邻的层次之间块大小是固定的,但是其他的层次对之间可以有不同的块大小。例如,在图6-21中,L1和 LO 之间的传送通常使用的是1个字大小的块。L2和L1之间(以及I3和I2之间、L4和I3之间)的传送通常使用的是几十个字节的
块。而L5和L4之间的传送用的是大小为几百或几千字节的块。一般而言,层次结构中较低层(离 CPU 较远)的设备的访问时间较长,因此为了补偿这些较长的访问时间,倾向于使用较大的块。
1. 缓存命中
当程序需要第 k 十1层的某个数据对象 d 时,它首先在当前存储在第 k 层的一个块中查找 d 。如果 d 刚好缓存在第 k 层中,那么就是我们所说的缓存命中( cache hit )。该程序直接从第 k 层读取 d ,根据存储器层次结构的性质,这要比从第 k +1层读取 d 更快。例如,一个有良好时间局部性的程序可以从块14中读出一个数据对象,得到一个对第 k 层的缓存命中。
2. 缓存不命中
另一方面,如果第 k 层中没有缓存数据对象 d ,那么就是我们所说的缓存不命中( cache miss )。当发生缓存不命中时,第 k 层的缓存从第 k 十1层缓存中取出包含 d 的那个块,如果第 k 层的缓存已经满了,可能就会覆盖现存的一个块。
覆盖一个现存的块的过程称为替换( replacing )或驱逐( evicting )这个块。被驱逐的这个块有时也称为牺牲块( victim block )。决定该替换哪个块是由缓存的替换策略( replace — ment policy )来控制的。例如,一个具有随机替换策略的缓存会随机选择一个牺牲块。一个具有最近最少被使用 LRU )替换策略的缓存会选择那个最后被访问的时间距现在最远的块。
在第 k 层缓存从第 k 十1层取出那个块之后,程序就能像前面一样从第 k 层读出 d 了。例如,在图6-22中,在第 k 层中读块12中的一个数据对象,会导致一个缓存不命中,因为块12当前不在第 k 层缓存中。一旦把块12从第 k 十1层复制到第 k 层之后,它就会保持在那里,等待稍后的访问。
3. 缓存不命中的种类
区分不同种类的缓存不命中有时候是很有帮助的。如果第 k 层的缓存是空的,那么对
任何数据对象的访问都会不命中。一个空的缓存有时被称为冷缓存( cold cache ),此类不命中称为强制性不命中( compulsory miss )或冷不命中( cold miss )。冷不命中很重要,因为它们通常是短暂的事件,不会在反复访问存储器使得缓存暖身( warmed up )之后的稳定状态中出现。
只要发生了不命中,第 k 层的缓存就必须执行某个放置策略( placement policy ),确定把它从第 k 十1层中取出的块放在哪里。最灵活的替换策略是允许来自第 k +1层的任何块放在第 k 层的任何块中。对于存储器层次结构中高层的缓存(靠近 CPU ),它们是用硬件来实现的,而且速度是最优的,这个策略实现起来通常很昂贵,因为随机地放置块,定位起来代价很高。
因此,硬件缓存通常使用的是更严格的放置策略,这个策略将第 k 十1层的某个块限制放置在第 k 层块的一个小的子集中(有时只是一个块)。例如,在图6-22中,我们可以确定第 k 十1层的块 i 必须放置在第 k 层的块( i mod 4)中。例如,第 k 十1层的块0、4、8和12会映射到第 k 层的块0;块1、5、9和13会映射到块1;依此类推。注意,图6-22中的示例缓存使用的就是这个策略。
这种限制性的放置策略会引起一种不命中,称为冲突不命中( conflict miss ),在这种情况中,缓存足够大,能够保存被引用的数据对象,但是因为这些对象会映射到同一个缓存块,缓存会一直不命中。例如,在图6-22中,如果程序请求块0,然后块8,然后块0,然后块8,依此类推,在第 k 层的缓存中,对这两个块的每次引用都会不命中,即使这个缓存总共可以容纳4个块。
程序通常是按照一系列阶段(如循环)来运行的,每个阶段访问缓存块的某个相对稳定不变的集合。例如,一个嵌套循环可能会反复地访问同一个数组的元素。这个块的集合称为这个阶段的工作集( working set )。当工作集的大小超过缓存的大小时,缓存会经历容量不命中( capacity miss )。换句话说就是,缓存太小了,不能处理这个工作集。
4. 缓存管理
正如我们提到过的,存储器层次结构的本质是,每一层存储设备都是较低一层的缓存。在每一层上,某种形式的逻辑必须管理缓存。这里,我们的意思是指某个东西要将缓存划分成块,在不同的层之间传送块,判定是命中还是不命中,并处理它们。管理缓存的逻辑可以是硬件、软件,或是两者的结合。
例如,编译器管理寄存器文件,缓存层次结构的最高层。它决定当发生不命中时何时发射加载,以及确定哪个寄存器来存放数据。L1、L2和L3层的缓存完全是由内置在缓存中的硬件逻辑来管理的。在一个有虚拟内存的系统中, DRAM 主存作为存储在磁盘上的数据块的缓存,是由操作系统软件和 CPU 上的地址翻译硬件共同管理的。对于一个具有像 AFS 这样的分布式文件系统的机器来说,本地磁盘作为缓存,它是由运行在本地机器上的 AFS 客户端进程管理的。在大多数时候,缓存都是自动运行的,不需要程序采取特殊的或显式的行动。
6.3.2 存储器层次结构概念小结
概括来说,基于缓存的存储器层次结构行之有效,是因为较慢的存储设备比较快的存储设备更便宜,还因为程序倾向于展示局部性:
1）利用时间局部性: 由于时间局部性,同一数据对象可能会被多次使用。一旦一个数据对象在第一次不命中时被复制到缓存中,我们就会期望后面对该目标有一系列的访问命中。因为缓存比低一层的存储设备更快,对后面的命中的服务会比最开始的不命中快很多。
2）利用空间局部性: 块通常包含有多个数据对象。由于空间局部性,我们会期望后面对该块中其他对象的访问能够补偿不命中后复制该块的花费。现代系统中到处都使用了缓存。正如从图6-23中能够看到的那样, CPU 芯片、操作系统、分布式文件系统中和万维网上都使用了缓存。各种各样硬件和软件的组合构成和管理着缓存。注意,图6-23中有大量我们还未涉及的术语和缩写。在此我们包括这些术语和缩写是为了说明缓存是多么的普遍。
6. 什么是程序访问的局部性存储系统中哪一级采用了程序访问的局部性原理
程序访问的局部性是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。它们倾向于引用的数据项邻近于其他最近引用过的数据项，或者邻近于最近自我引用过的数据项。局部性通常有两种形式：时间局部性和空间局部性
存储系统中Cache-主存层次和主存-辅存层次均采用了程序访问的局部性原理。