页面着色和局部性原理
页面着色
原理
页面着色的出现,是为了解决虚拟内存中相邻的页表,因为在物理地址上不相邻,(可能)导致出现 cache 出现大量缺页,从而造成抖动。

cache 的设计采用中间一段地址作为 Set 的寻址。采用 Set 作为索引不仅保证了相邻的物理内存可以整块出现在 cache 中,是局部性原理的体现,而且保证了物理内存中相邻的块不会出现在同一个 cache set 中产生冲突。但是从虚拟内存到物理内存中,可能导致相邻虚拟地址的内存块被影射到不相邻的内存块中,而更加致命的是,可能会映射到 Set 相同的物理地址,从而导致相邻的虚拟地址对相同的 cache set 进行竞争。这显然和局部性原理以及 cache 的设计初衷相违背的。
而页面着色的设计,正是为了解决虚拟内存的出现给 cache 带来的问题。通过竞争产生机制的分析,可以发现关键在于虚拟内存映射到物理内存的映射。如果能够保证相邻的虚拟内存不会映射到相同 Set index 的物理内存上,就不会产生这种竞争。因此会从 Set index 中选择一些 bits 作为 color bits,在操作系统为虚拟内存分配页表的时候,可以进行优化,选择将相邻的虚拟地址映射到不同 color bits 的页表中。虚拟地址由操作系统来维护,将这个操作交给操作系统再合适不过了。
应用
page coloring 技术被应用在 Solaris,FreeBSD,NetBSD,WindowsNT等操作系统中,虽然大大增加了操作系统的复杂性,但是对于性能的优化也是可观的。
局部性原理
局部性原理是计算机中广泛出现的一个现象。局部性原理表明了资源在时间和空间上的聚集性,不仅仅在操作系统中,也在硬件设计,网络,软件等方面有着广泛的应用。
局部性原理可以分为两个方面:
-
时间层面的局部性,即对于同一个资源的引用会在一段时间内大量出现。
-
空间层面的局部性,即相邻的资源很有可能被同时引用。
通过对局部性原理的运用,有以下好处:
-
进行计算时只需要加载当前所用到的部分资源而非所有资源,这对于缓存器(比如 cache)的容量要求大大降低。
-
同一工作集中的资源可以被同时加载,加速后面的计算。
-
如果不知道接下来运用的资源,就保持已经加载的资源不变。
可以看到,局部性原理对于计算整个流程的资源加载都有着指导意义,帮助操作系统选择最优的行动。
不仅仅对现代操作系统,局部性原理在很多其他系统上也有着重要作用,

如上图所示,局部性原理可以通过数据的来源和使用方向分成四类。
-
内部数据内部使用。比如网购网站可以通过用户购买或浏览的记录,预测后来的用户可能感兴趣的物品。
-
内部数据外部使用。比如链接器找到源代码引用的库文件作为源程序的工作集。
-
外部数据内部使用。比如搜索引擎通过对网页数据的整理为用户的请求提供相关的信息。
-
外部数据外部使用。比如虚拟内存系统计算工作集保证为程序提供足够的空间。
局部性原理从操作系统的应用到更多系统的应用,展示了这个原理的广泛性,不仅仅是在计算机的资源加载中,在人类的行为等等方面也具有重要意义。相信未来局部性原理能够在更多领域获得运用。