局部性原理的理解

局部性原理的理解

杜逸闲

本文首先介绍了局部性原理的定义，然后列举了一些局部性原理的应用，接着具体讨论了局部性原理在page coloring中的应用，最后分析了局部性原理的本质。

什么是局部性原理

在计算机学科的概念中，局部性原理是一个常用的术语，指处理器在访问某些数据时短时间内存在重复访问，某些数据或者位置访问的概率极大，大多数时间只访问局部的数据。主要可以分为时间局部性和空间局部性两种。

时间局部性

如果一个数据正在被访问，那么在近期它很可能还会被再次访问。任何编写过程序的人都知道，这个原理是正确的。我们在编写程序时，总是在一段时间内（比如一个循环或者一个函数内）对相同的地址进行反复的操作。

但为什么人们在编写程序的时候不会先计算出一个数据，将其存放在某个地方，然后在很长一段时间内都不使用呢？Locality Principle 一文提到这是因为人类解决问题的思维方式是分治（divide and conquer），将大事化小，小事化了。一个很庞大的问题会被分解成若干个子问题，在各自的模块分别解决，而某一个子问题涉及到的数据会在存放后不久被读取。

空间局部性

局部性原理的应用

局部性原理最先在操作系统领域被发现且应用，但慢慢延申至计算机科学的其他领域。最主要的应用就是在各种缓存的replacement algorithm中。下面列举一些其应用的例子：

1. 操作系统中，在将虚拟内存转换到物理内存的过程中，我们需要用到TLB。在交换页至硬盘时，内存可以看作是硬盘的一种缓存。在缓存的replacement algorithm中我们会应用到局部性原理。
2. CPU的多级缓存技术。
3. 数据库中的memcache。当使用关系型数据库（如mysql时），即使我们分库分表储存，高峰期单机的查询压力还是很大。由于查询的项同样有局部性，此时可以使用如redis一类的kv数据库做memchache。
4. 计算机网路中的CDN。由于同一个用户，甚至同一个地区的用户，在访问的数据上都存在局部性。大型的网站都引入了CDN来帮助分散主机的压力。CDN可以看作是服务器的一个cache。
5. CopyOnWrite. 在Linux的fork中，子进程应该拥有独立的地址空间，父进程拥有的数据也应该复制一份。但由于局部性原理的存在，只有一小部分的数据是会被修改的，而大部分数据是只需要读的，有的数据甚至不会被使用。因此只有当子进程写数据时，这块数据才会被真正的复制。

page coloring与局部性原理

缓存的架构

我们知道，在CPU的cache中会缓存一些内存，其中缓存的组织方式分别有三种，VIVT、VIPT和PIPT，见下图：
而在实际使用中，因为VIPT的效率比较高，我们会使用VIPT架构。VIPT架构使用虚拟地址做索引，物理地址做Tag。在利用虚拟地址索引cache同时，同时会利用TLB将虚拟地址转换为物理地址。然后将转换后的物理地址，与虚拟地址索引到的cache line中的Tag作比较，如果匹配则命中。

但这种方式由于仍然拿虚拟地址做索引，仍然会出现cache alias问题。

cache alias

cashe alias是指，当两个不同的虚拟地址都映射至同一个物理地址时，他们在cache中可能不存在于同一个cache line中。那么当其中一个地址中储存的值被修改时，另一个cache line就会有失效的问题，要解决这个问题会严重影响效率，因此应当避免cache alias出现。

下面我们将举例说明在VIPT架构下什么时候会出现cache alias。

假设页大小为4KB。对于不同的两个VA和他们映射的同一个PA，他们的offset即最低的12位bit[0…11]一定是相同的。在使用虚拟地址查找cache line的组时，若能保证用于索引的虚拟地址的位数在bit[0…11]中，就能确保两个虚拟地址查找到同一个cache line组内。而由于我们并行地在TLB中查询到了PA，并用这个PA作为tag在这个cache line组内查找，这两个VA最终会查找到同一个cache line内，不会出现cache alias.

假设cache大小为16KB，4路组相联，cache line大小为32（5个bit）。此时我们需要虚拟地址的7个bit作为索引，而由于cache line大小为32，占据了bit[0…4]，为了对齐我们只能用bit[5…11]作为索引。而由于两个VA的bit[0…11]都是相同的，他们都会被映射到同一个cache line组内，不会出现cache alias.

但假设现在cache大小为32KB，其余条件不变。此时我们就需要虚拟地址的7个bit作为索引，同理为了对其我们需要用bit[5…12]作为索引，而两个VA的bit[12]可能并不一样，这就导致他们被索引到不同的组内，占用了两个不同的cache line，导致了cache alias.

如何解决cache alias

其实方法的原理很简单。只要保证这两个VA用作映射的bit都是一样的，就可以保证他们映射到同一个组内。那么我们只要在建立VA到PA的映射时，强制让VA和PA的一定数量的低位保持一致即可。

如上一节的第一个例子，操作系统不需要做任何工作，VA和PA的最低12位必定一样，因此在mapping时不需要额外操作。

而第二个例子中，我们便需要保证VA和PA的bit[12]是一致的。比如VA的bit[12]是1，我们就只会将其分配到bit[12]为1的PA上，而不将其分配到bit[12]为0的PA上。用一种比喻的手法来说，PA和VA都拥有了0和1两种颜色，只有颜色一样的page才有可能建立虚拟地址到物理地址的映射。

这就是所谓的page coloring.

与局部性原理的关系

page coloring可能会导致一个问题。那就是内存和缓存的利用率可能下降。假设我们的page拥有四种颜色。此时cache line组实际上会被分成四种颜色。考虑下面一种情况，所有的VA的颜色均为0. 在这种情况下，分配的所有PA的颜色也为0. 这会导致更多的物理内存分配失败，需要更多的交换，从而带来更多的缺页，严重影响了效率。同时，由于只有颜色为0的cache line组被使用，缓存命中率会降低，效率又会大打折扣。

实际上，由于空间局部性原理，一段程序在一定时间内总是会使用相邻的一段内存，也就是说，VA和PA的颜色应该是在四种颜色中均匀分布的。上述问题在实际中并不会存在，或不会造成什么可观的影响。

局部性原理的本质

从物理的视角看，局部性原理的本质是熵的不均匀。不同事物的熵有高有低，熵低的事物组织性更强，这一组事物中的联系更紧密。而局部性原理认为在时间上或者空间上距离近的事物他们的联系更强，因此熵更低，暗示我们将他组织在一起。

认识局部性原理的本质的意义在于什么呢？如果意识到狭义上的局部性原理只是泊松分布的一个应用，那么当一些事情发生的概率并不符合泊松分布时，狭义上的局部性原理就需要修改。或者我们需要对其中的k做出一些变换，使得其服从泊松分布。具体到实际应用中，我们不能奉狭义上的局部性原理为真理，而在这个优化方向上蒙蔽了双眼，错过了可优化的空间。