【计组 | Cache原理】讲透Cache的所有概念与题型方法

2024-09-01 03:44

本文主要是介绍【计组 | Cache原理】讲透Cache的所有概念与题型方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Cache

写在前面:高速缓存Cache一直408中的重点以及绝对的难点,前几天我在复习计组第三章的知识,Cache这一节把我困住了,我发现很多概念我都不记得了,一些综合性强的计算题根本无从下手,我深知Cache对于每个408的初学者来说,都是痛点、难点所在,因此花了一晚上狠狠学习Cache总结做了这个Cache“大观”,尝试用最精简且具有逻辑性的方式,只讲重难点和考点,给大家讲透Cache(我发现市面上很多课程讲解的都是比较零散且不好消化的,没有抓住主要矛盾),用最短的时间达到做出考研408题目的要求。

为什么要使用Cache?

为了引出Cache这个高速缓存的妙用,我们先来认识一个概念—时间局部性

所谓的时间局部性就是同一条指令在短时间内多次运行,比如循环结构,那么我们在循环体内重复更新的变量就是具有时间局部性的,而学过操作系统我们就知道程序是放在内存里运行的,由于时间局部性,程序运行时频繁访问的数据就集中在主存中的某几块区域内,于是我们只要把这几块区域的指令、数据全都复制到CPU的Cache里,这样CPU就可以先去Cache里看看有没有数据如果有直接取出,如果没有再取访存,提高了取数据的效率。由于命中率很高,平均访问是接近于Cache的访问时间的!!(小考点)

那么主存究竟是将数据复制到Cache内的呢?我们继续来看!

关于Cache的所有概念(重点)⭐

我们现在需要把主存中的部分高频访问内容复制到Cache中,最简单的思路就是把主存和Cache都划分出一个个的相同大小的区域,然后就可以直接把数据复制过去了对吧。实际上计算机也是这么做的。

  1. **“块”**的概念:我刚刚说的大小相同的区域,在主存中叫作主存块,在Cache中叫作Cache块或Cache行(注意这两是一个东西,题目中给出块或者行都是OK的)。主存块的大小就等于Cache块的大小!!这是第一点需要我们铭记于心的,原理我刚刚已经说过了,就是方便交换数据。

  2. Cache的数据结构模型(重点看,有个记忆能画出来是最好的)

    在这里插入图片描述

    从王道教材书这张图,我们可以看到Cache主要分为了tag标记位和存储数据两部分,数据部分是以“块”为单位与内存交换数据的,如果不够清晰,我们来看小林coding给出这张结构图:

    在这里插入图片描述

    我们可以清楚地看到每一个Cache行都分为了tag位和数据块,对应的主存也要划分成一个个一样大小的数据块,那么主存是怎么进行划分操作的呢?我们需要引出一个概念“主存地址”。

  3. 主存地址:将主存划分为多个主存块后,我们就需要一些数据位来标识块号,因此主存地址可以划分为两部分:高位地址(标识块号)+低位地址(块内地址)。请一定要记住这个划分它是我们后面做题的逻辑基点,同样的Cache以同样的划分方式:高位地址(标识块号)+低位地址(块内地址)

  4. 有效位:Cache中除了拥有上述的主要部分tag+数据块,还有一些特别的东西,我们先从有效位开始介绍。

    1. 工作原理:有效位用来标记对应的 Cache行中的数据是否是有效的,如果有效位是 0,无论Cache 中是否有数据,CPU 都会直接访问内存,重新加载数据。
    2. 作用:有了这个有效位,我们想要淘汰一个主存块数据就很容易了,只需要把有效位置0,装入一个新的主存块的时候,再把有效位置为1即可。
  5. CPU访问过程:我一开始的时候就说了,如果Cache中已经有了数据,我们就不要去访存了,但是如果在Cache中没有找到数据,我们就要去内存中读取并把数据块复制到Cache块中,这个过程也就是Cache的缺失处理。重点来了,到底是谁去完成这些判断、替换数据块工作的呢?为了保证速度当然只能由硬件来实现了,因此Cache对于程序员来说是透明的,所有过程都由硬件自动实现。硬件自动实现,硬件自动实现!!!重要的事情说三遍。

Cache和主存的映射方式(超级重点⭐⭐)

这一块请跟着我一起理解并记忆!!考察计算题!

我们一直再说交换数据,那么我们怎么把主存的数据块通过地址映射的方式,复制到Cache行中呢?先来了解一下三种映射方式:

1)三种映射方式

  1. 直接映射:每个主存块映射到Cache的特定行中,CPU访问某个特定行即可
  2. 全相联映射:主存块可以映射到Cache的任意行中,需要把Cache所有行都扫一遍
  3. 组相联映射:把Cache分成多个组,每个组又有多个行,主存块可以放到特定组的任意行中,访问的时候只需要看看那特定组的所有行

2)直接映射的理解

  1. 我们先来看这张图:

    在这里插入图片描述

  2. 我们需要把主存块映射到特定的Cache行中,因此就需要一个转化的方式,我们把它提炼成一个公式:

    cache 行号 = 主存块号 % Cache行数

    我们来解释一下:假设我们一个主存块的大小为4B,给出一个主存地址x(还记得主存地址是什么吗,上面已经讲过高位标识块号低位为快内地址),我们就可以通过x/4去找到我们的主存块号(假设是从0标号的),我们也可以通过转成二进制然后通过右移操作(比如/4就是右移两位)来得到块号,再用块号去%Cache行数(同样的模运算也可以用二进制取后n位得到,等会会演示)。

    Cache行数如果题目中没有给出,就是用Cache的总容量去 / cache块的大小(和主存块是一样大的)来得到。

    好好理解一下这个公式,后面我会用综合性很强的计算题带着大家来做练习加深理解。

  3. 主存地址划分:

    三部分组成:标记Tag+Cache行号(也有叫索引的)+块内地址(也有叫块内偏移的)

    其中主存块号就是去除块内地址的部分,即标记+Cache行号。我们刚刚一直没有介绍tag位是用来干嘛的,只是引出了这个概念,实际上它是作为主存块和Cache块是否匹配的验证信息,如上图用一个比较器进行匹配的操作,同时还要去看有效位是否为1,不过这一块内容不是考察的重点,我们就算不太能理解也没有关系,能把各部分的位数计算出来就行了。

  4. 内存映射表:很多教材上都不讲这一点,所以对同学们造成了概念上的迷惑,到底什么是地址映射表?一句话,地址映射表就是Cache中除了装数据部分的大小,要用标记位+特殊位得到,等会看一道题。

3)全相联和组相联

理解了上面的直接映射后,这两种就好理解多了。

  1. 全相联映射:给每一个行都设置一个比较器 ,根据tag字段按内容访问Cache中的主存块,对于硬件开销比较大,但是能解决直接映射的冲突问题。

    在这里插入图片描述

    我们需要记住的是主存地址结构:标记+块内地址 (最简单的一种,只有两部分)

  2. 组相联映射:组间采用直接映射,组内采用全相联映射。

    在这里插入图片描述

    1. Cache行数 = 组数 * 路数(每一组的大小是相等的,路数是指每一组有多少个Cache行,题目一般给出的也是k路组相联的信息,不要搞混了)
    2. 地址结构:标记+组号+块内
    3. 组号的计算方法和直接映射中Cache行号的计算思想是一样的,先求出主存块号,再对组数取模,后面直接来看例题就更清晰了。
    4. 当路数为1时,就变成一块一组,也就退化成直接映射方式,当路数为Cache行数时,所有块都变成了一组,也就变成了全相联映射。

以上内容,请好好理解吃透,特别是对于主存地址的三种划分映射结构,Cache的模型与概念,及计算公式,下面我们进入好题精析部分。

好题赏析

题目

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

讲解笔记

在这里插入图片描述
在这里插入图片描述
讲解视频跳转:30min带你狠狠拿捏Cache所有知识与题型方法

这篇关于【计组 | Cache原理】讲透Cache的所有概念与题型方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1125847

相关文章

SQL中redo log 刷⼊磁盘的常见方法

《SQL中redolog刷⼊磁盘的常见方法》本文主要介绍了SQL中redolog刷⼊磁盘的常见方法,将redolog刷入磁盘的方法确保了数据的持久性和一致性,下面就来具体介绍一下,感兴趣的可以了解... 目录Redo Log 刷入磁盘的方法Redo Log 刷入磁盘的过程代码示例(伪代码)在数据库系统中,r

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

Spring 基于XML配置 bean管理 Bean-IOC的方法

《Spring基于XML配置bean管理Bean-IOC的方法》:本文主要介绍Spring基于XML配置bean管理Bean-IOC的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录一. spring学习的核心内容二. 基于 XML 配置 bean1. 通过类型来获取 bean2. 通过

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil

Python处理函数调用超时的四种方法

《Python处理函数调用超时的四种方法》在实际开发过程中,我们可能会遇到一些场景,需要对函数的执行时间进行限制,例如,当一个函数执行时间过长时,可能会导致程序卡顿、资源占用过高,因此,在某些情况下,... 目录前言func-timeout1. 安装 func-timeout2. 基本用法自定义进程subp

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4:

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三