精华内容
下载资源
问答
  • 2020-09-21 21:01:12

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

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

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

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

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

    更多相关内容
  • 这是一份计算机体系结构课堂展示的ppt,有关于缓存cache以及多种优化的核心思想:局部性原理,制作精美 内容详实覆盖面广,有需要的同学可以下载一下~
  • 局部性原理的理解

    千次阅读 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做出一些变换,使得其服从泊松分布。具体到实际应用中,我们不能奉狭义上的局部性原理为真理,而在这个优化方向上蒙蔽了双眼,错过了可优化的空间。

    展开全文
  • 计算机体系结构资源
  • 局部性原理——各类优化的基石

    千次阅读 多人点赞 2019-07-28 16:38:21
    学过计算机底层原理、了解过很多架构设计或者是做过优化的同学,应该很熟悉局部性原理。即便是非计算机行业的人,在做各种调优、提效时也不得不考虑到局部性,只不过他们不常用局部性一词。如果抽象程度再高一些,...

    学过计算机底层原理、了解过很多架构设计或者是做过优化的同学,应该很熟悉局部性原理。即便是非计算机行业的人,在做各种调优、提效时也不得不考虑到局部性,只不过他们不常用局部性一词。如果抽象程度再高一些,甚至可以说地球、生命、万事万物都是局部性的产物,因为这些都是宇宙中熵分布布局、局部的熵低导致的,如果宇宙中处处熵一致,有的只有一篇混沌。

    所以什么是 局部性 ?这是一个常用的计算机术语,是指处理器在访问某些数据时短时间内存在重复访问,某些数据或者位置访问的概率极大,大多数时间只访问_局部_的数据。基于局部性原理,计算机处理器在设计时做了各种优化,比如现代CPU的多级Cache、分支预测…… 有良好局部性的程序比局部性差的程序运行得更快。虽然局部性一词源于计算机设计,但在当今分布式系统、互联网技术里也不乏局部性,比如像用redis这种memcache来减轻后端的压力,CDN做素材分发减少带宽占用率……

    局部性的本质是什么?其实就是概率的不均等,这个宇宙中,很多东西都不是平均分布的,平均分布是概率论中几何分布的一种特殊形式,非常简单,但世界就是没这么简单。我们更长听到的发布叫做高斯发布,同时也被称为正态分布,因为它就是正常状态下的概率发布,起概率图如下,但这个也不是今天要说的。
    在这里插入图片描述
    其实有很多情况,很多事物有很强的头部集中现象,可以用概率论中的泊松分布来刻画,这就是局部性在概率学中的刻画形式。
    在这里插入图片描述
    在这里插入图片描述
    上面分别是泊松分布的示意图和概率计算公式, λ \lambda λ 表示单位时间(或单位面积)内随机事件的平均发生次数, e e e表示自然常数2.71828…,k表示事件发生的次数。要注意在刻画局部性时 λ \lambda λ表示不命中高频数据的频度, λ \lambda λ越小,头部集中现象越明显。

    局部性分类

    局部性有两种基本的分类, 时间局部性空间局部性 ,按Wikipedia的资料,可以分为以下五类,其实有些就是时间局部性和空间局部性的特殊情况。

    时间局部性(Temporal locality):

    如果某个信息这次被访问,那它有可能在不久的未来被多次访问。时间局部性是空间局部性访问地址一样时的一种特殊情况。这种情况下,可以把常用的数据加cache来优化访存。

    空间局部性(Spatial locality):

    如果某个位置的信息被访问,那和它相邻的信息也很有可能被访问到。 这个也很好理解,我们大部分情况下代码都是顺序执行,数据也是顺序访问的。

    内存局部性(Memory locality):

    访问内存时,大概率会访问连续的块,而不是单一的内存地址,其实就是空间局部性在内存上的体现。目前计算机设计中,都是以块/页为单位管理调度存储,其实就是在利用空间局部性来优化性能。

    分支局部性(Branch locality)

    这个又被称为顺序局部性,计算机中大部分指令是顺序执行,顺序执行和非顺序执行的比例大致是5:1,即便有if这种选择分支,其实大多数情况下某个分支都是被大概率选中的,于是就有了CPU的分支预测优化。

    等距局部性(Equidistant locality)

    等距局部性是指如果某个位置被访问,那和它相邻等距离的连续地址极有可能会被访问到,它位于空间局部性和分支局部性之间。 举个例子,比如多个相同格式的数据数组,你只取其中每个数据的一部分字段,那么他们可能在内存中地址距离是等距的,这个可以通过简单的线性预测就预测是未来访问的位置。

    实际应用

    计算机领域关于局部性非常多的利用,有很多你每天都会用到,但可能并没有察觉,另外一些可能离你会稍微远一些,接下来我们举几个例子来深入了解下局部性的应用。

    计算机存储层级结构

    极客时间
    上图来自极客时间徐文浩的《深入浅出计算机组成原理》,我们以目前常见的普通家用电脑为例 ,分别说下上图各级存储的大小和访问速度,数据来源于https://people.eecs.berkeley.edu/~rcs/research/interactive_latency.html
    在这里插入图片描述
    从最快的L1 Cache到最慢的HDD,其两者的访存时间差距达到了6个数量级,即便是和内存比较,也有几百倍的差距。举个例子,如果CPU在运算是直接从内存中读取指令和数据,执行一条指令0.3ns,然后从内存读下一条指令,等120ns,这样CPU 99%计算时间都会被浪费掉。但就是因为有局部性的存在,每一层都只有少部分数据会被频繁访问,我们可以把这部分数据从底层存储挪到高层存储,可以降低大部分的数据读取时间。
      
    可能有些人好奇,为什么不把L1 缓存做的大点,像内存那么大,直接替代掉内存,不是性能更好吗?虽然是这样,但是L1 Cache单位价格要比内存单位的价格贵好多(大概差200倍),有兴趣可以了解下DRAM和SRAM。

    我们可以通过编写高速缓存友好的代码逻辑来提升我们的代码性能,有两个基本方法 。

    1. 让最常见的情况运行的快,程序大部分的运行实际都花在少了核心函数上,而这些函数把大部分时间都花在少量循环上,把注意力放在这些代码上。
    2. 让每个循环内缓存不命中率最小。比如尽量不要列遍历二维数组。

    MemCache

    在这里插入图片描述
    MemCache在大型网站架构中经常看到。DB一般公司都会用mysql,即便是做了分库分表,数据数据库单机的压力还是非常大的,这时候因为局部性的存在,可能很多数据会被频繁访问,这些数据就可以被cache到像redis这种memcache中,当redis查不到数据,再去查db,并写入redis。
      
    因为redis的水平扩展能力和简单查询能力要比mysql强多了,查起来也快。所以这种架构设计有几个好处:

    1. 加快了数据查询的平均速度。
    2. 大幅度减少DB的压力。

    CDN

    CDN的全称是Content Delivery Network,即内容分发网络(图片来自百度百科) 。CDN常用于大的素材下发,比如图片和视频,你在淘宝上打开一个图片,这个图片其实会就近从CDN机房拉去数据,而不是到阿里的机房拉数据,可以减少阿里机房的出口带宽占用,也可以减少用户加载素材的等待时间。
    在这里插入图片描述
    CDN在互联网中被大规模使用,像视频、直播网站,电商网站,甚至是12306都在使用,这种设计对公司可以节省带宽成本,对用户可以减少素材加载时间,提升用户体验。看到这,有没有发现,CDN的逻辑和Memcache的使用很类似,你可以直接当他是一个互联网版的cache优化。

    Java JIT

    JIT全称是Just-in-time Compiler,中文名为即时编译器,是一种Java运行时的优化。Java的运行方式和C++不太一样,因为为了实现write once, run anywhere的跨平台需求,Java实现了一套字节码机制,所有的平台都可以执行同样的字节码,执行时有该平台的JVM将字节码实时翻译成该平台的机器码再执行。问题在于字节码每次执行都要翻译一次,会很耗时。
      在这里插入图片描述
    图片来自郑雨迪Introduction to Graal ,Java 7引入了tiered compilation的概念,综合了C1的高启动性能及C2的高峰值性能。这两个JIT compiler以及interpreter将HotSpot的执行方式划分为五个级别:

    • level 0:interpreter解释执行
    • level 1:C1编译,无profiling
    • level 2:C1编译,仅方法及循环back-edge执行次数的profiling
    • level 3:C1编译,除level 2中的profiling外还包括branch(针对分支跳转字节码)及receiver type(针对成员方法调用或类检测,如checkcast,instnaceof,aastore字节码)的profiling
    • level 4:C2编译

    通常情况下,一个方法先被解释执行(level 0),然后被C1编译(level 3),再然后被得到profile数据的C2编译(level 4)。如果编译对象非常简单,虚拟机认为通过C1编译或通过C2编译并无区别,便会直接由C1编译且不插入profiling代码(level 1)。在C1忙碌的情况下,interpreter会触发profiling,而后方法会直接被C2编译;在C2忙碌的情况下,方法则会先由C1编译并保持较少的profiling(level 2),以获取较高的执行效率(与3级相比高30%)。

    这里将少部分字节码实时编译成机器码的方式,可以提升java的运行效率。可能有人会问,为什么不预先将所有的字节码编译成机器码,执行的时候不是更快更省事吗?首先机器码是和平台强相关的,linux和unix就可能有很大的不同,何况是windows,预编译会让java失去夸平台这种优势。 其次,即时编译可以让jvm拿到更多的运行时数据,根据这些数据可以对字节码做更深层次的优化,这些是C++这种预编译语言做不到的,所以有时候你写出的java代码执行效率会比C++的高。

    CopyOnWrite

    CopyOnWrite写时复制,最早应该是源自linux系统,linux中在调用fork() 生成子进程时,子进程应该拥有和父进程一样的指令和数据,可能子进程会修改一些数据,为了避免污染父进程的数据,所以要给子进程单独拷贝一份。出于效率考虑,fork时并不会直接复制,而是等到子进程的各段数据需要写入才会复制一份给子进程,故此得名 写时复制
      
    在计算机的世界里,读写的分布也是有很大的局部性的,大多数情况下读远大于写, 写时复制 的方式,可以减少大量不必要的复制,提升性能。 另外这种方式也不仅仅是用在linux内核中,java的concurrent包中也提供了CopyOnWriteArrayList CopyOnWriteArraySet。像Spark中的RDD也是用CopyOnWrite来减少不必要的RDD生成。

    处理

    上面列举了那么多局部性的应用,其实还有很多很多,我只是列举出了几个我所熟知的应用,虽然上面这些例子,我们都利用局部性得到了能效、成本上的提升。但有些时候它也会给我们带来一些不好的体验,更多的时候它其实就是一把双刃剑,我们如何识别局部性,利用它好的一面,避免它坏的一面?

    识别

    文章开头也说过,局部性其实就是一种概率的不均等性,所以只要概率不均等就一定存在局部性,因为很多时候这种概率不均太明显了,非常好识别出来,然后我们对大头做相应的优化就行了。但可能有些时候这种概率不均需要做很详细的计算才能发现,最后还得核对成本才能考虑是否值得去做,这种需要具体问题具体分析了。

    如何识别局部性,很简单,看概率分布曲线,只要不是一条水平的直线,就一定存在局部性。

    利用

    发现局部性之后对我们而言是如何利用好这些局部性,用得好提升性能、节约资源,用不好局部性就会变成阻碍。而且不光是在计算机领域,局部性在非计算机领域也可以利用。

    性能优化

    上面列举到的很多应用其实就是通过局部性做一些优化,虽然这些都是别人已经做好的,但是我们也可以参考其设计思路。

    恰巧最近我也在做我们一个java服务的性能优化,利用jstack、jmap这些java自带的分析工具,找出其中最吃cpu的线程,找出最占内存的对象。我发现有个redis数据查询有问题,因为每次需要将一个大字符串解析很多个键值对,中间会产生上千个临时字符串,还需要将字符串parse成long和double。redis数据太多,不可能完全放的内存里,但是这里的key有明显的局部性,大量的查询只会集中在头部的一些key上,我用一个LRU Cache缓存头部数据的解析结果,就可以减少大量的查redis+解析字符串的过程了。

    另外也发现有个代码逻辑,每次请求会被重复执行几千次,耗费大量cpu,这种热点代码,简单几行改动减少了不必要的调用,最终减少了近50%的CPU使用。

    非计算机领域

    《高能人士的七个习惯》里提到了一种工作方式,将任务划分为重要紧急、不重要但紧急、重要但不紧急、不重要不紧急四种,这种划分方式其实就是按单位时间的重要度排序的,按单位时间的重要度越高收益越大。《The Effective Engineer》里直接用leverage(杠杆率)来衡量每个任务的重要性。这两种方法差不多是类似的,都是优先做高收益率的事情,可以明显提升你的工作效率。

    这就是工作中收益率的局部性导致的,只要少数事情有比较大的收益,才值得去做。还有一个很著名的法则__82法则__,在很多行业、很多领域都可以套用,80%的xxx来源于20%的xxx ,80%的工作收益来源于20%的工作任务,局部性给我们的启示“永远关注最重要的20%” 。

    避免

    上面我们一直在讲如何通过局部性来提升性能,但有时候我们需要避免局部性的产生。 比如在大数据运算时,时常会遇到数据倾斜、数据热点的问题,这就是数据分布的局部性导致的,数据倾斜往往会导致我们的数据计算任务耗时非常长,数据热点会导致某些单节点成为整个集群的性能瓶颈,但大部分节点却很闲,这些都是我们需要极力避免的。

    一般我们解决热点和数据切斜的方式都是提供过重新hash打乱整个数据让数据达到均匀分布,当然有些业务逻辑可能不会让你随意打乱数据,这时候就得具体问题具体分析了。感觉在大数据领域,局部性极力避免,当然如果没法避免你就得通过其他方式来解决了,比如HDFS中小文件单节点读的热点,可以通过减少加副本缓解。其本质上没有避免局部性,只增加资源缓解热点了,据说微博为应对明星出轨Redis集群也是采取这种加资源的方式。

    参考资料

    1. 维基百科局部性原理
    2. 《计算机组成与设计》 David A.Patterson / John L.Hennessy
    3. 《深入浅出计算机组成原理》 极客时间 徐文浩
    4. 《深入理解计算机系统》 Randal E.Bryant / David O’Hallaron 龚奕利 / 雷迎春(译)
    5. interactive latencies
    6. Introduction to Graal 郑雨迪
    展开全文
  • 计算机体系结构——局部性原理研究学习一、引言与局部性原理宏观理解二、存储系统角度理解局部性原理2.1 了解计算机的存储结构:2.2 CPU与内存之间的速度匹配2.3 数组访问角度理解空间局部性三、局部性原理的细化...

    一、引言与局部性原理宏观理解

    • 经过一个多月跟随余老师学习计算机体系结构的过程,有一个词汇频繁出现在课堂上,那就是大名鼎鼎的“局部性原理”。从存储系统到指令系统再到操作系统的方方面面好像都有局部性原理的影子。这一点引起了我的好奇心,想要深入了解局部性原理在计算机体系结构方面的众多应用,从而诞生了这篇研究报告。
    • 我们从局部性原理在计算机领域具体应用跳出,从更宏观的角度去理解局部性原理。
       无论是计算机行业还是非计算机行业,在做各种调优、提效时也不得不考虑到局部性原理,只不过他们不常用局部性一词。如果抽象程度再高一些,甚至可以说地球、生命、万事万物都是局部性的产物,因为这些都是宇宙中熵分布不均、局部熵低导致的,如果宇宙中处处熵一致只会是一片混沌。  
       局部性其实就是一种概率的不均等性,所以只要概率不均等就一定存在局部性。局部性原理正是我们人为地抓住了概率分布的不均等性,利用这条性质来优化生活中地方方面面。
       如果说我们不考虑局部性原理,那就是在默认概率均等,与事实存在的概率不均等性相违背当然会影响效率。比如说在选择数据存入缓存时,如果我们随机选择那就是在默认CPU将来利用的数据的概率是均等分布的,而通过我们的经验与数据分析,CPU将来要使用的数据确实存在时间与空间上的聚集性。所以说我们利用局部性原理实际上是顺应了事务发展的客观规律

    二、存储系统角度理解局部性原理

    • 第一次接触“局部性原理”这个词是在上学期的操作系统课上,缓存优化存储系统效率的原理便是我们今天的主角:局部性原理。

    2.1 了解计算机的存储结构:

    在这里插入图片描述
      计算机的存储结构从上到下依次为:寄存器、L1级缓存、L2级缓存、L3级缓存、内存、硬盘。可以看出从上到下空间越来越大速度越来越慢成本越来越低
      存储结构最顶层的寄存器,是与CPU直接数据交换也是存放计算数据的地方。CPU要工作时所需要的数据或者地址从哪里来?先从一级缓存里面找,找不到就从二级缓存里面找,依次类推直至最底层硬盘。找到数据之后需要将数据一层层向上返回,假如CPU到磁盘才有,那么这个数据就会存入内存,再存入三级缓存、二级缓存、一级缓存,最后存入寄存器,CPU才能用它来计算。
      其实我们可以拓宽缓存的定义,缓存其实就相当于抽取部分数据以提高访问效率的含义。抽象层次上CPU要与内存之间进行数据交换,所有数据当然最终存储在物理介质——硬盘上,但硬盘较慢的存取速度无法匹配CPU的高处理速度,因此我们才把数据层层向上抽取形成各层“缓存”来匹配速度差异。我们可以将寄存器当作L1的缓存,L1当作L2的缓存…L3当作内存的缓存,内存当作硬盘的缓存。

    2.2 CPU与内存之间的速度匹配

      CPU的工作要求高速,我们希望CPU需要的数据更多的就在L1里面,一找就找到,即便不在L1里面也尽可能在更高的层次里,避免每次都要深入到硬盘层次才能找到想要的数据。所以当CPU使用一个数据之后,计算机会存入CPU可能会再次用到的数据到三级缓存,用到的可能性越大,就能存到越接近寄存器的层次。

    • 总结来说计算机可以通过向缓存中存入数据地方式极大优化CPU运行效率。那么问题来了,计算机该向缓存中存入哪些数据呢?
    • 心心念念的“局部性原理”终于登场!计算机就是根据局部性原理选择最合适的数据存入三级缓存。局部性原理可以大体分为时间局部性与空间局部性:
        时间局部性:如果一个信息项正在被访问,那么在近期它很可能还会被再次访问。一旦一个数据费很大劲从k+1层调入了k层,就希望他多次被引用,这样能节省很大的方寸开支。
        空间局部性:在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。比如说读取数组第一个元素时,由于数组是连续存放的,会把第一个元素后面的n个元素一起拷贝到缓存中等待访问。

    2.3 数组访问角度理解空间局部性

    • 有关空间局部性的内容我们可以通过数组的不同访问方式进一步理解。数组有按行访问按列访问两种形式。
        举例子来说,我们有一个数组a[4][4]。按行访问的顺序为:a[0][0]、a[0][1]、a[0][2]…按列访问的顺序为:a[0][0]、a[1][0]、a[2][0]…看似差别不大的访问方式,其访问效率却有成倍的差异。
        按行访问时,访问a[0][0]直接从内存中读取,然后将a[0][0]以及其后的两个数据存入缓存中。下一步读取a[0][1]直接从缓存读取并不需要再一次访问内存;按列访问时,访问a[0][0]直接从内存中读取,t同样将a[0][0]以及其后的两个数据存入缓存中。但下一步要访问的却是a[1][0]这个数据在缓存中找不到只好再去访问内存,即增大了访问时间也浪费了缓存中存储的数据。

    三、局部性原理的细化分类

    • 我们可以针对局部性原理做进一步细致的划分,其实根本上还是时间局部性与空间局部性的进一步具体化拓展。

    3.1 时间局部性(Temporal locality):

      如果某个信息这次被访问,那它有可能在不久的未来被多次访问。时间局部性是空间局部性访问地址一样时的一种特殊情况。这种情况下,可以把常用的数据加cache来优化访存。

    3.2 空间局部性(Spatial locality):

      如果某个位置的信息被访问,那和它相邻的信息也很有可能被访问到。 这个也很好理解,我们大部分情况下代码都是顺序执行,数据也是顺序访问的。

    3.3 内存局部性(Memory locality):

      访问内存时,大概率会访问连续的块,而不是单一的内存地址,其实就是空间局部性在内存上的体现。目前计算机设计中,都是以块/页为单位管理调度存储,其实就是在利用空间局部性来优化性能。

    3.4 分支局部性(Branch locality):

      这个又被称为顺序局部性,计算机中大部分指令是顺序执行,顺序执行和非顺序执行的比例大致是5:1,即便有if这种选择分支,其实大多数情况下某个分支都是被大概率选中的,于是就有了CPU的分支预测优化。

    3.5 等距局部性(Equidistant locality):

      等距局部性是指如果某个位置被访问,那和它相邻等距离的连续地址极有可能会被访问到,它位于空间局部性和分支局部性之间。 举个例子,比如多个相同格式的数据数组,你只取其中每个数据的一部分字段,那么他们可能在内存中地址距离是等距的,这个可以通过简单的线性预测就预测是未来访问的位置。

    四、局部性原理的其他应用

    • 上面我们通过缓存在存储系统中的优化作用理解了局部性原理。其实局部性原理在当今计算机领域的其他实际应用中也常常发挥作用。

    4.1 数据库缓存中局部性原理的应用

      MemCache在大型网站架构中经常看到。一般公司的数据库架构都会用mysql,即便是做了分库分表,数据库单机处理的压力还是非常大的,这时候因为局部性的存在,可能很多数据会被频繁访问,这些数据就可以被缓存到像redis这种memcache中。当有数据请求到达时,首先快速查询redis,当redis查不到数据,再去查数据库,并根据局部性原理写入redis。
      因为redis的水平扩展能力和简单查询能力要比mysql强多了,查询速度也更快。所以这种架构设计有几个好处:1.加快了数据查询的平均速度。2.大幅度减少数据库的存取压力
      在实际WEB开发中我也曾学习并使用过redis数据库。redis是NoSQL的一种,通过键值对的方式来存储数据,数据存储量小但存取速度快。在网站开发中常常把用户名、密码、登录状态等信息数据存储在redis中来应对用户对于登入登出的频繁请求。
    在这里插入图片描述

    4.2 网络架构中局部性原理的应用

      CDN常用于较大素材下发,比如图片和视频,你在淘宝上打开一个图片,这个图片其实会就近从CDN机房读取数据,而不是到阿里的数据中心读取数据。当数据中心处理一次数据请求后会根据局部性原理,将部分数据分发到边缘服务器上,以便于就近用户的再次访问。局部性原理应用于网络架构中可以减少数据中心的出口带宽占用,也可以减少用户加载素材的等待时间。
      这一点应用让我联想到了最近很火热的技术话题——边缘计算。众所周知目前我们的网络架构计算方式还是中心云端计算,也就是将网络边缘收集到的请求与数据传输汇聚到中心云端服务器上,凭借云端服务器极强的算力来处理数据再分发到各个边缘服务器。该策略在过去有明显的优势,可以将算力集中,极大地节约了计算成本,但同时也存在一些弊端,比如数据地上传与下载存在很大的传输代价,如果数据量很大还会造成拥塞。
      近些年来,随着移动设备、物联网IOT设备数量的飞速增长,网络中的数据量发生了爆炸式的增长。之前适合于中小型数据量的中心云端计算网络架构越来越不堪重负,随着而来的是边缘计算模式的兴起。边缘计算顾名思义,将部分计算能力还有数据处理能力分配到边缘服务器,这样就近收集数据大部分数据都可以在边缘服务器上处理,只有少部分数据需要传输到数据中心处理。这样极大程度上减轻了数据中心的处理压力也缓和了数据传输的拥塞压力,唯一缺点就是边缘服务器的部署带来了更高的成本
    在这里插入图片描述

    展开全文
  • 要想更好地理解虚拟内存技术,必须要了解计算机中著名的局部性原理。 早在1968年的时候,就有人指出我们的程序在执行的时候往往呈现局部性规律,也就是说在某个较短的时间段内,程序执行局限于某一小部分,程序访问...
  • 什么是程序的局部性原理

    千次阅读 2019-12-02 11:38:14
    01、前言 作为有追求的程序员,我们日常在写代码的时候往往都会运用很多奇技淫巧,不单单是为了炫耀我们的技术,更是为了追求更高的效率。...说到局部性原理,那我们首先要知道什么是局部性原理局部性原理...
  •   基于局部性原理,计算机处理器在设计时做了各种优化,比如现代CPU的多级Cache、分支预测…… 有良好局部性的程序比局部性差的程序运行得更快。虽然局部性一词源于计算机设计,但在当今分布式系统、互联网技术里...
  • 什么是局部性原理

    2021-03-02 10:36:19
    什么是局部性原理局部性原理的逻辑是这样的: 内存读写块,磁盘读写慢,而且慢很多; 磁盘预读:磁盘读写并不是按需读取,而是按页预读,一次会读一页的数据,每次加载更多的数据,如果未来要读取的数据就在这一...
  • 程序访问的局部性原理

    千次阅读 2021-03-18 18:02:08
    程序访问的局部性原理 程序访问的局部性原理包括时间局部性和空间局部性。时间局部性是指在最近的未来要用到的信息,很可能是现在正在使用的信息,因为程序中存在循环。空间局部性是指在最近的未来要用到的信息,很...
  • 以前我们仅了解cache比内存速度快,但是这个仅在于说他可以方便CPU和内存交换数据,其实它另一个作用是局部性原理,而这在程序运行中也起到很关键的作用。 2. 局部性原理是什么? 局部性原理指的是将程序中最活跃...
  • Linux内存介绍(局部性原理,段页)

    千次阅读 2020-07-27 19:10:29
    文章目录内存1虚拟储存区2局部性原理3 虚拟地址 和 虚拟地址空间4内存管理方式5 页(了解)6 段页※(掌握)定义段页纠错小案例代码:说明各个变量存储的地方答案 内存 每一个要运行的程序,必须先进入内存然而,每...
  • 局部性原理(Locality of Reference)
  • 操作系统的局部性原理

    千次阅读 2019-11-05 18:47:23
    局部性原理:一个良好的计算机程序 常常具有良好的局部性,也就是说,它们倾向于引用邻近于其他最近引用过的数据项的数据项,或者最近引用过的数据项本身。 局部性的两种不同的形式:时间局部性和空间局部性 时间...
  • 文章目录目录基于局部性原理实现的内-外存交换技术局部性原理Swap 交换分区 基于局部性原理实现的内-外存交换技术 虚拟存储器的实现思想就是将内存作为辅存的缓存,使得计算机系统拥有了 主存+辅存(交换空间) 大小...
  • 什么是缓存的局部性原理

    千次阅读 2019-10-18 20:05:56
    存储结构 了解计算机的存储结构,对我们编写优秀的程序很有帮助,虽然计算机的内部对我们来说是透明的,但是如果我们能多了解一些计算机...在程序中注意利用缓存的局部性原理,能大大提高程序的运行效率哦。  
  • Cache —— 局部性原理和工作原理

    千次阅读 多人点赞 2019-07-26 14:48:36
    一、程序访问的局部性原理 程序访问的局部性原理包括时间局部性和空间局部性。 空间局部性:在最近的未来要用到的信息(指令和数据),很可能与现在正在使用的信息在存储空间上是邻近的 时间局部性:在最近的未来要...
  • 局部性原理 局部性原理不仅适用于程序结构,也适用于数据结构 正是由于局部性原理的存在,才可以实现只装入部分程序到内存就开始运行 局部性原理的表现: 时间局部性:如果程序中的某条指令一旦执行,不久之后该...
  • CPU访问中的局部性原理 主要两点:时间与空间 时间局部性:理解的关键点在于“访问的时间间隔”,比如for循环实现sum求和,sum就是这次访问了,下次还被访问,体现的就是时间局部性。 空间局部性:理解的关键点...
  • #资源达人分享计划#
  • 首先我们需要先明白程序的局部性原理是什么? 局部性原理是指CPU访问存储器时,无论是存取指令还是存取数据,所访问的存储单元都趋于聚集在一个较小的连续区域中。 当访问的存储单元都聚集在一个较小的连续区域中时...
  • 虚拟内存和局部性原理

    千次阅读 2019-11-10 15:19:13
  • 局部性原理与磁盘预读原理来了解索引机制

    千次阅读 多人点赞 2019-11-26 16:52:44
    参考文章,链接如下: https://blog.csdn.net/coolwriter/article/details/80346454 https://blog.csdn.net/u010727189/article/details/79399384 ... 目录 局部性原理...
  • 说到局部性原理,那我们首先要知道什么是局部性原理局部性原理分为两部分: 时间局部性:指的是在程序运行过程中最近被引用到的存储器位置在程序执行后期还会被多次引用到的可能性很大。 空间局部性:指的是程序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 211,880
精华内容 84,752
关键字:

局部性原理