精华内容
下载资源
问答
  • 局部性原理

    2020-09-21 21:01:12
    想要更好的理解虚拟内存技术,必须要知道计算机中著名的局部性原理局部性原理是虚拟内存技术的基础,正是因为程序运行具有局部性原理,才可以只装入部分程序到内存就开始运行。局部性原理主要表现在以下两个方面...

    想要更好的理解虚拟内存技术,必须要知道计算机中著名的局部性原理。

    局部性原理是虚拟内存技术的基础,正是因为程序运行具有局部性原理,才可以只装入部分程序到内存就开始运行。局部性原理主要表现在以下两个方面:

    1. 时间局部性:如果程序中的某条指令一旦执行,不久以后该指令可能再次执行;如果某数据被访问过,不久以后该数据可能被再次访问。产生时间局部性的典型原因,是由于在程序中存在着大量的循环操作。

    2. 空间局部性:一旦程序访问了某个存储单元,在不久以后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围之内,这是因为指令通常是顺序存放、顺序执行的,数据也一般是以向量、数组等形式聚集存储的。

    时间局部性是通过将近来使用的指令和数据保存到高速缓冲存储器中,并使用高速缓存的层次结构实现;空间局部性通常是使用较大的高速缓存,并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了“内存—外存”的两级存储器的结构,利用局部性原理实现高速缓存。

    展开全文
  • 局部性原理的理解

    2021-03-08 23:07:54
    本文首先介绍了局部性原理的定义,然后列举了一些局部性原理的应用,接着具体讨论了局部性原理在page coloring中的应用,最后分析了局部性原理的本质。 什么是局部性原理 在计算机学科的概念中,局部性原理是一个...

    局部性原理的理解

    17300240036 杜逸闲

    本文首先介绍了局部性原理的定义,然后列举了一些局部性原理的应用,接着具体讨论了局部性原理在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的颜色应该是在四种颜色中均匀分布的。上述问题在实际中并不会存在,或不会造成什么可观的影响。

    局部性原理的本质

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

    从数学的角度上考虑,局部性原理的本质,就是一部分事情发生的概率与另一些事情发生的概率不相等。比如空间局部性指的是,与当前正在使用的内存在空间中相邻的部分,接下来被使用的概率比离得远得更大。
    在自然界中,不存在完美的平均分布。实际上自然界中大量事物发生的概率都遵循泊松分布。局部性原理其实就是对泊松分布的一个应用。
    在这里插入图片描述
    如果定义x=k为距离当前被访问资源距离为k的资源被访问。那么当k越小时,p(x=k)越大,我们就应该将距离尽可能近的资源提前加载。

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

    展开全文
  • Cache —— 局部性原理和工作原理

    千次阅读 2019-07-26 14:48:36
    一、程序访问的局部性原理 程序访问的局部性原理包括时间局部性和空间局部性。 空间局部性:在最近的未来要用到的信息(指令和数据),很可能与现在正在使用的信息在存储空间上是邻近的 时间局部性:在最近的未来要...

    一、程序访问的局部性原理

    程序访问的局部性原理包括时间局部性和空间局部性。

    • 空间局部性:在最近的未来要用到的信息(指令和数据),很可能与现在正在使用的信息在存储空间上是邻近的
    • 时间局部性:在最近的未来要用到的信息,很可能是现在正在使用的信息

    高速缓冲技术是利用程序访问的局部性原理,把程序中正在使用的部分存放在一个高速的、容量较小的Cache中,使CPU的访存操作大多数针对Cache进行,从而大大提高程序的执行速度。


    二、Cache的基本工作原理

    在这里插入图片描述

    Cache位于存储器层次结构的顶层,通常由SRAM构成。

    Cache和主存都被分成若干大小相等的块(Cache块又称为Cache行),每块由若干字节组成,块的长度称为块长(Cache行长)。所以Cache中的块数要远少于主存中的块数,它仅保存主存中最活跃的若干块的副本。

    CPU与Cache之间的数据交换以字为单位,而Cache与主存之间的数据交换则以Cahce块为单位。

    • 当CPU发出读请求时,若访存地址在Cache中命中,就将此地址转换成Cache地址,直接对Cahce进行读操作,与主存无关;若访存地址在Cache中未命中,则需访问主存,并把此字所在的块一次性地从主存调入Cache,若此时Cache已满,则需根据某种 替换算法,用这个块替换Cache中原来的某块信息。

    • 当CPU发出写请求时,若Cache命中,有可能会遇到Cache与主存中的内容不一致的问题,此时需要根据某种 写策略 解决这个问题。


    三、Cahce的性能指标

    与Cahce有关的性能指标主要有:命中率,缺失率和平均访问时间。

    1. 命中率H:

    • CPU欲访问的信息已在Cache中的比率

    设一个程序执行期间,Cache的总命中次数为 NcN_c,访问主存的总次 NmN_m。则 H=Nc/(Nc+Nm)H=N_c/(N_c+N_m)

    2. 缺失率M:

    • CPU欲访问的信息不在Cache中的比率

    M=1HM=1-H

    3. 平均访问时间 TaT_a

    tct_c 为命中时的Cache访问时间,tmt_m为未命中时的访问时间,则 Ta=Htc+1HtmT_a=H*t_c+(1-H)t_m

    在这里插入图片描述

    展开全文
  • 空间局部性原理: 当程序访问一个空间立即又访问其临近的空间。 依次访问空间顺序空间。(例如对数组进行初始化,初始化完A0 接着初始化临近的空间A1) 时间局部性原理: 也就是刚刚访问完的指令再次访问。 比如说一...

    空间局部性原理:
    当程序访问一个空间立即又访问其临近的空间。
    依次访问空间顺序空间。(例如对数组进行初始化,初始化完A0 接着初始化临近的空间A1)

    时间局部性原理:
    也就是刚刚访问完的指令再次访问。
    比如说一段循环代码(例如i++被循环100次),被放到了高速缓冲区,那么CPU 直接通过读取高速缓冲区而不是与内存交互达到一个高效的状态。

    工作集原理:
    把要被频繁访问的页面集合打包起来,并放到CACHE使之短时间不被替换,达到高效的目的。

    展开全文
  • 程序的局部性原理

    2021-05-22 15:49:44
    程序的局部性原理是指程序在执行时呈现出局部性规律,即在一段时间内,整个程序的执行仅限于程序中的某一部分。相应地,执行所访问的存储空间也局限于某个内存区域。 局部性原理又表现为:时间局部性和空间局部性。 ...
  • 1.7局部性原理

    2020-03-15 22:45:27
    两类型 程序执行时间的90%都是在执行程序中的10%的代码 时间局部性 如果一个信息项正在被...主要的三部分 处理,存储,时间 其中最能体现局部性原理的是存储器部分 for (i = 0;i<n;i++){ sum+=v[i] sum---...
  • 局部性原理学习笔记

    2020-12-27 23:20:00
    局部性原理启发的一点思考 我觉得有必要在最前面进行一下声明,这个学期学完了计算机系统基础,刚开始学的时候没感觉与所学的内容有联系,直到后面学习了内存,链接,进程等内容联系学完的java才发现代码与这门课...
  • 局部性原理及性能分析 1.概述 2.局部性原理 3.性能分析
  • 缓存局部性原理

    2020-05-01 15:35:33
    这篇主要是利用局部性原理优化程序性能, 另外主要是结合perf工具分析量化比较缓存命中率情况。一 存储体系1.1 存储层组成计算机的存储是由多级存储组成的存储体系,原因是越快的存储成本...
  • 程序访问的局部性原理 程序访问的局部性原理包括时间局部性和空间局部性。时间局部性是指在最近的未来要用到的信息,很可能是现在正在使用的信息,因为程序中存在循环。空间局部性是指在最近的未来要用到的信息,很...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,219
精华内容 1,287
关键字:

局部性原理