关于算法:计算机中的层次化存储是个什么鬼

33次阅读

共计 2514 个字符,预计需要花费 7 分钟才能阅读完成。

写在后面

撸代码只是程序员的一项最根本的技能,除此之外,还有很多常识须要程序员把握。【程序员进阶系列】专题,旨在分享程序员想要进一步晋升自我,冲破倒退瓶颈的一系列技术。明天,咱们来一起聊聊计算机中的层次化存储构造。

文章已收录到:

https://github.com/sunshinelyz/technology-binghe

https://gitee.com/binghe001/technology-binghe

层次化存储构造

首先,问小伙伴们一个问题: 计算机的存储构造为什么须要进行层次化的划分呢?

说的间接一点:就是为了缩小经济老本。如果说,CPU 的价格十分便宜的话,基本就不须要内存了。能够把所有的内存容量全副都做到 CPU 外面去,就能够了。然而,事实上,CPU 的内存是很精贵的,至今为止,CPU 中基本上还是一级缓存和二级缓存。三级缓存比拟少见。而且,CPU 中的存储容量是十分小的,根本都是 KB 级别的存储,CPU 的内存容量也就几 KB,MB 级别的 CPU 内存也是比拟少见的。所以,出于经济老本的思考,计算机中的存储构造是依照档次进行划分的。

为了可能让小伙伴们更加清晰的了解层次化存储构造,咱们先来看一张图。

由上图,能够看出:

(1)层次化的存储构造能够分为:CPU、Cache(高速缓存)、主存(内存)、外存(辅存)。

(2)从上往下,速度越来越慢,容量越来越大。

局部性原理是层次化存储构造的撑持。

局部性原理

一个编写良好的计算机程序经常具备良好的局部性。也就是说。它们偏向于援用邻近于其余最近援用过的数据项的数据项,或者最近援用过的数据项自身。这汇总倾向性,就被称为局部性原理,这是一个长久的概念,对硬件和软件系统的设计和性能都有着极大的影响。

之所以有这个法则,很多人认为起因是: 程序的指令大部分工夫是程序执行的 ,而且程序的汇合,如数组等各种数据结构是间断寄存的。

局部性原理讲的是:在一段时间内,整个程序的执行仅限于程序的某一部分,相应地,程序拜访的存储空间也局限于某个内存区域。次要分为两类:

  • 工夫局部性:如果程序中的某条指令一旦执行,则不久之后该指令可能再次被执行;如果某数据被拜访,则不久之后该数据可能再次被拜访。
  • 空间局部性:是指一旦程序拜访了某个存储单元,则不久之后,其左近的存储单元也将被拜访。

Cache

针对 Cache 相干的技术,咱们次要来聊聊 Cache 的概念和映像相干的技术。

Cache- 概念

这里的 Cache 示意的是高速缓冲,在计算机的存储体系零碎中,Cache 是除寄存器外访问速度最快的档次。 应用 Cache 改善零碎性能的根据是程序的局部性原理

如果以 h 代表对 Cache 的拜访命中率,t1 示意 Cache 的周期时间,t2 示意主存储器的周期时间,以读操作为例,应用“Cache+ 主存储器”的零碎的均匀周期为 t3,则能够得出如下运算公式。

t3 = h * t1 + (1 - h) * t2 

其中。(1 – h) 又称为失效率,也就是未命中率。

Cache- 映像

Cache 的映像分为三种,别离是:间接相联映像、全相联映像、组相联映像。

  • 间接相联映像:硬件电路比较简单,但抵触率最高。
  • 全相连映像:电路难于设计和实现,只实用于小容量的 Cache,抵触率比拟低。
  • 组相联映像:间接相联与全相联的折中。

地址映像是将主存与 Cache 的存储空间划分为若干大小雷同的页(或称为块)。

例如,一台计算机的主存容量为 1GB,划分为 2048 页,每页 512KB;Cache 的容量为 8MB,划分为 16 页,每页 512KB。接下来,咱们由此来具体图解间接相联映像、全相联映像和组相联映像。

间接相联映像

咱们能够画一组图来示意 Cache 的间接映像。首先,咱们先来简略画一个主存标记、Cache 页号和页内地址的示意图。如下所示。

如上图所示,主存标记为 7 位,Cache 页号为 4 位,页内地址为 19 位。

记录主存区号的示意图如下所示。

有了下面两张图的根底后,咱们再来看间接相联映像的示意图如下所示。

这里,咱们将容量为 1GB 的主存划分成 2048 页,总共 127 个区,每页的容量为 512KB。将容量为 8MB 的 Cache 划分为 16 页,每页容量为 512KB。

所谓间接相联映像是指 Cache 中的 0 页只能存储主存中 0 页的内容,这里主存中 0 页指的是每个区的 0 页,比方上图中的 0 区的 0 页,1 区的 16 页,127 区的 2032 页等。

在间接相联映像中,只须要记录主存标记、Cache 页号和页内地址就可能疾速的找到主存中的数据。

应用间接相联映像有个毛病:那就是如果 Cache 中的 0 页,存储了主存中 0 区 0 页的内容时,如果此时须要存储主存 1 区中的 16 页内容,就只能将主存 0 区中 0 页的内容从 Cache 的 0 页中革除,而后将主存 1 区中 16 页的内容存储到 Cache 中的 0 页内。抵触率比拟高。仔细的小伙伴会发现:这其实是违反局部性原理的。

间接相联映像访问速度最快,但抵触率最高。

全相连映像

咱们先来看下全相联映像的主存页标记和页内地址的示意图,如下所示。

此时,应用 11 位来标识主存页标记,应用 19 位来标识页内地址。

应用全相连映像须要记录主存与 Cache 的对应关系,如下图所示。

接下来,咱们来看看全相连映像的示意图,如下所示。

从图中能够看出,Cache 中的任何一个也,都能够存储主存中的任何一个页。

应用全相连映像访问速度最慢,抵触率最低。

组相联映像

组相联映像实质上是间接相联映像和全相联映像的折中。同样的,咱们先来看组相连映像的存储示意图。

此时,在组相连映像中,Cache 组号应用 3 位示意,组内页号应用 1 位示意,页内地址应用 19 位示意。其中,3 位的 Cache 组号,1 位的组内页号和后面的 7 位形成了主存页标记;3 位的 Cache 组号,1 位的组内页号和 19 号的页内地址形成了 Cache 地址。

接下来,咱们再来看看主存与 Cache 的对应关系,如下图所示。

组相连的映像示意图如下所示。

由上图可知,在组相连映像中,主存的组与 Cache 的组是组相联映像关系,而在组内则是通过间接相联映像来拜访和存储数据。

好了,我曾经肝不动了。明天就到这儿吧,我是冰河,大家有啥问题能够在下方留言,也能够加我微信:sun_shine_lyz,我拉你进群,一起交换技术,一起进阶,一起牛逼~~

正文完
 0