【计组 | 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

相关文章

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

CentOS 7部署主域名服务器 DNS的方法

《CentOS7部署主域名服务器DNS的方法》文章详细介绍了在CentOS7上部署主域名服务器DNS的步骤,包括安装BIND服务、配置DNS服务、添加域名区域、创建区域文件、配置反向解析、检查配置... 目录1. 安装 BIND 服务和工具2.  配置 BIND 服务3 . 添加你的域名区域配置4.创建区域

mss32.dll文件丢失怎么办? 电脑提示mss32.dll丢失的多种修复方法

《mss32.dll文件丢失怎么办?电脑提示mss32.dll丢失的多种修复方法》最近,很多电脑用户可能遇到了mss32.dll文件丢失的问题,导致一些应用程序无法正常启动,那么,如何修复这个问题呢... 在电脑常年累月的使用过程中,偶尔会遇到一些问题令人头疼。像是某个程序尝试运行时,系统突然弹出一个错误提