半夜，滴滴司机问我会 LRU 吗？

落日映苍穹つ 2023-03-06 08:05 24阅读 0赞

点击上方“**五分钟学算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

##  ##

## **1**  ##

宫本走出公司的时候，已经将近半夜。此时天上的月亮仍旧散发着清冷的幽光，无情地审视着大地。

最近公司业务繁忙，大批技术人员都被迫加班到很晚。宫本正是这些技术人员中的一份子，从他开始写代码到如今，已经将近五年。

「需求根本做不完，这几天连续加班要吐了。」宫本小声嘟囔了一句，掏出手机准备叫个网约车。

宫本所在的公司是互联网行业，号称是行业内发展迅猛的独角兽。但是宫本在其中工作得并不顺心；一方面是由于技术工作的压力太大，二来也是因为公司规模比较大，个人的成就感无法得到充分的满足。

半夜的网约车基本不用排队，不到五分钟，一辆黑色的吉利帝豪便沿着定位开到了公司大门。一上车，宫本就从背包中掏出了笔记本电脑，打算利用路上的时间再补补技术基础。

打开笔记本，内嵌的键盘后背灯和屏幕同时亮了起来，照亮了宫本有点疲倦的脸庞。屏幕上开着一个网页，显示的是「CPU缓存」之类的字样，底下还配有长段的图文解析。

关于CPU 缓存的相关知识，宫本早在大学期间就已经学过。只不过年代久远加上也没有时常回顾，现在也忘得差不多了。这回是打算将计算机组成的基础知识再温习一遍，以应对之后可能的跳槽。

「CPU缓存相关的知识，重点应该在于计算机存储系统的层次结构、地址映像方法和缓存替换算法之类的吧。」宫本低头喃喃自语道，却没注意到前方的司机微微瞟了一眼后视镜。

说回来，宫本自上车起注意力就没落在司机上，心思还没从工作状态中缓过来。事实上，司机外形跟宫本倒有些相似，只不过看起来年纪更大一些，大概35左右。同时若隐若现的发际线都无意间展露出中年人的危机。

只不过宫本也无暇顾及前方这个与自己有些神似的男人了，一头扑进了学习中。

## **2**  ##

CPU 缓存「Cache」指的访问速度比一般内存快得多的高速存储器，主要是为了解决 CPU 运算速率与内存读写速率不匹配的问题。因为 CPU 的运算速率比内存读写速率快得多，当 CPU 需要向内存请求数据或者写入数据时，就需要一直等待内存缓慢的读写。在这个过程中，CPU 的高速运算能力就无法得到充分发挥。

「所以缓存的作用就像是 CPU 和内存之间进行数据缓冲的桥梁。」宫本若有所思。

缓存中的数据是内存中的一部分，这一部分数据被认为是 CPU 在短时间内会即将访问到的数据。当 CPU 在调用数据时，会先从缓存中调用，而不直接通过内存。当在缓存中找到想要的数据时，就会立即读取并返回给 CPU 处理；如果没有找到，就以相对较慢的速度从内存中读取，同时将这个数据所在的数据块都调入缓存中，方便下次对该数据块的读取。

「这样可行主要还是因为局部性原理吧。」宫本渐渐找回了上大学时的记忆。他记得程序在运行时对内存的访问会呈现出局部性的特征，这种特征表现在使用了某一个数据时，往往该数据附近的数据会有更高的概率在下次被使用。

「那缓存是如何发挥作用的呢？」宫本有些不太记得缓存的组成，埋头继续研究。前座的司机时不时通过后视镜瞥一瞥钻心学习的宫本，不经意间眼神里流露出一种夹杂着无奈和释然的复杂神情。

首先来讲讲计算机存储系统的层次结构。一般而言，通用计算机的存储层级分为四层，分别为 CPU 内部寄存器、高速缓存、主存储器和辅存储器。主存可以看作是一般而言的内存，而辅存又可根据是否与计算机相连分为联机和脱机两种类型。

![format_png 2][]

计算机存储系统的层次结构

从层次结构上可以看出，高速缓存处于第二层次，起到承上启下的作用。而为了能够与 CPU 进行高速交互，同时与主存进行数据的交换，高速缓存的结构也十分具有个人特色。

高速缓存并不是一中概念上的缓存，而是由特定 SRAM 组成的物理芯片。在现代 CPU 中，大量的空间都已经被 SRAM 占据。下图是一张Intel CPU的放大图片，红色框标出的就是其中一部分高速缓存。

> SRAM：SRAM是指静态随机存储器，它具有静止存取的功能，也就是可以不需要刷新电路就保存内部的数据。性能高，功耗小，速度快，价格高。

![format_png 3][]

Intel CPU， 图源网络，侵删

高速缓存一般由两部分组成，控制部分和存储器部分。控制部分是用来判断 CPU 所请求的数据是否保存在存储器中，如果在，则称为命中；若不在则没有命中。

![format_png 4][]

CPU高速缓存组成

当 CPU 命中缓存时，即可直接对高速缓存的存储器进行寻址；未命中时，则需要根据缓存替换算法将主存中的数据块替换到高速缓存的存储器中。

## **3**  ##

「接下来是地址映像方法了吧。」宫本还没从缓存的组成结构中缓过神来，就听见前座传来一声沧桑的话语。

「诶师傅，行家啊！」宫本惊讶的抬起头，正好对上后视镜中那双炯炯有神的目光。原来是宫本在学习时不自觉地自言自语起来，引起了司机师傅的注意。

「哈哈哈，早年学过，忘得差不多了。」司机师傅腼腆一笑。宫本心里一惊，没想到真是全民学编程的时代，高手无处不在。

「那您也太厉害了，我正准备了解下高速缓存中的地址映像方法呢。」宫本赞叹道。

「我之前还在当程序员的时候，就经常被拉去当面试官。关于地址映像方法啊，页面置换算法啊之类的问题基本上是必问的问题了。这也是对于计算机组成原理的基本考察。」司机师傅仿佛打开了话匣子。

「那您这功力很深厚呀，这么多年了还记得这么基础的东西。」宫本没想到这位师傅原来还是一位资深的程序员，时间过去这么久依然记得高速缓存的一些技术重点。

「其实也还好，这种基础的知识虽然实际工作中不会直接用到，但是对于理解代码还是有辅助作用的。只不过现在很多年轻人都比较忽视这方面的学习。」司机师傅略带惋惜的说道。宫本听完表示赞同的一笑，也没有接话，继续沉迷自己学习中去了。

的确也是，现在许多年轻人都是为了编程而编程，反而忽视了许多计算机基本的常识和基本思想。估计很多人可能都还不知道高速缓存中有哪些地址映像方法。

实际上地址映像方法就是为了将主存地址与高速缓存中存储器的地址对应起来，进行地址的映射，这样 CPU 在工作才能通过缓存正确地对主存数据进行快速读写。

地址映像方法有三种，直接映像，全相联映像和组相联映像。

#### 直接映像 ####

直接映像的图示如下，主存单元中的区块与缓存中内存块的关系是固定的，主存中的内存块只会存放在高速缓存存储器中的相同块号。因此，只要主存地址中的主存区号与缓存中的主存区号相同，则表明访问缓存命中。

这样一来，根据主存地址中的区内块号，就可以得到需要访问的高速缓存存储器中块号，从而即可从缓存中访问需要的数据。

直接映像带来的好处很明显， 地址变换很简单粗暴，主存的内存块与缓存直接映射，一整块进行对应。这样的方式虽然简单，但是灵活性很差。主存中不同区，但是块号相同的内存块不能同时被调入缓存存储器中。并且，当缓存存储器中有空着的块也无法被主存中其它的内存块替换。

![format_png 5][]

直接映像方式

#### 全相联映像 ####

为了解决直接映射造成灵活性差，缓存空间无法充分利用的问题，全相联映像的方式被提出来。全相联与直接映像就是两个极端，一个只能整个区块进行对应，一个就允许任意主存的块调入高速缓存存储器中任意的块。

![format_png 6][]

全相联映像方式

在进行地址变换时，当主存地址高位的主存块号与高速缓存中中主存块号相比时，有相同的块号即表示命中。一旦命中，CPU 即可通过缓存存储器中的块内地址访问到相应的数据。

全相联映像能够提供非常灵活的变换方式，不受主存所在块的限制。但是同样也是由于过于灵活，导致实际在变换的时候，无法从主存块号直接获得高速缓存存储器的块号，变换过程相对比较复杂，速度也比较慢。

#### 组相连映像 ####

既然两者方法各有利弊，不妨我们就折中一下。因而有了中庸的组相连映像方式。

组相连方式就是将主存和高速缓存存储器中的块再分成组，组之间采用直接映像方式，而组内的块则采用全相联映像方式。具体的实现可以参考以下图示。

举例来说，主存任何区的0组只能存到高速缓存中的0组中，1组只能存到1组。这就是所谓组间的直接映像。而主存相同一组的任意一块可以存入高速缓存相同组中的任意一块。这就是所谓组内的全相联方式。

![format_png 7][]

组相连映像方式

在进行地址变换时，可通过直接映像方式来决定组号，在一组内再用全相联映像方式决定高速缓存中的块号。通过比较主存地址高位决定的主存区号与缓存中的区号，即可决定是否命中。

## **4**  ##

司机师傅见宫本专心思考去了，也没有强行打扰，稳稳地握着方向盘，眼光眺向远方。

「这地址映像方法还挺有意思，简单的地址映射也能根据具体的情况进行整体和局部的优化。」不一会，宫本抬起头，微微感叹了一声。

「哈哈哈，说的是啊。计算机领域很多看起来想当然的东西都是经过了不同程度的优化，才能真正运用在实际的系统中。」司机师傅听见宫本的感叹，接上了话茬。

「您想必之前是个很纯粹的技术人吧。」宫本对这个看起来普普通通的司机师傅充满了好奇，感觉像是个世外高人，大隐隐于市般。

「噗，这哪谈得上。不然也不会出来跑滴滴了。只是之前工作的时候比较看重基础吧。」司机师傅笑了一声。

「不过，如果我是你的面试官，我可能会更喜欢问你缓存替换算法。地址变换这些东西没啥技术含量，对程序员来说也并不是那么透明。相对来说替换算法的思想更值得你们学习哈。比方说 LRU」司机师傅话题一转，有了那么点面试官的味道。想必应该也是直男一个。

「哈是的，我正准备看呢。我大概记得应该有好几种吧，除了 LRU ，还有比如随机替换、FIFO之类的。」宫本之前也经过过几次面试，对司机师傅的说法表示赞同。

「那你好好看看。」司机师傅建议道，说完二人也都没有再说话了。

缓存替换算法的目的很明显，就是为了使得高速缓存获得尽可能高的命中率，当缓存的存储器满了的时候，将不用的数据块进行删除，替换新的数据。常用的替换算法有以下几种：

*  随机替换算法：顾名思义，就是通过随机获得一个需要被替换的块号，并用新的数据替换该块。
 *  先进先出算法：即FIFO，通过缓存中的块进入队列的先后顺序进行淘汰和替换，先进入缓存的数据块最先被替换。
 *  最近最少使用算法：即LRU，将近期最少使用的缓存块替换出去。这种算法在实现的时候将最近使用的的数据块放置到靠近缓存顶部的位置。每一次替换都从缓存尾部开始进行。
 *  最不经常使用算法：即LFU，这个算法需要记录每一个缓存块被访问的频率，每一次替换都从最低访问频率的数据块开始。
 *  最近最常使用算法，即MRU，这个算法会最先移除最近最常使用的数据块。

替换算法说白了，就是看采用怎么样的策略将缓存中的数据块替换出去。在实际的应用中，还会根据程序具体的情况对不同的算法进行优化选择。

## **5**  ##

看到这，宫本对 CPU 高速缓存的概念已经有了比较清晰的了解。再次抬起头，发现已经能够看到小区耸立的高楼。一栋栋楼盘，亮着灯的已经不多。

「师傅，我快到加了，这回感谢你哈。没想到打车也能遇到同行哈哈。」看完缓存，宫本松了口气，看来下班回家的时间还是能够利用起来的。

「不过我还是想问一下，您当初为啥不干这行了呢？」一直怀着这样的疑问，宫本还是忍不住问了出来。

「我啊，其实也没为啥吧。之前当程序员的时候，虽然赚得挺多的，但是累是真的累。很长一段时间也找不到自己成长的方向，在公司工作的时间越来越长，却感觉已经少了那股跟新人一样的活力和朝气。怎么说呢，就像是为了工作而工作。」

「所以您就不干啦？」

「倒也没有那么果断吧，纠结了挺长时间的。你别看我现在在开滴滴，其实这只不过是我目前的副业。」

「那你现在还敲代码吗？」

「现在还是天天敲键盘，只不过不是敲代码啦。我开滴滴也就在你们公司这附近接单，主要是为了找找以前的感觉，同样也是找找灵感吧。」

「哇，那您应该财富自由了吧哈哈。」

「哈哈哈，还行～」

小区到了，宫本轻松的走下了车，并再次跟司机师傅道了声谢谢。短短的几十分钟的车程，让他收获满满。

不仅对 CPU 缓存原理进行了快速的复习，还有幸遇到了别样的人生。他也不清楚自己是否能够迈过35岁这道坎，但至少情况可能没那么糟糕。就像那位司机师傅一样，大胆的尝试加上勇敢的付出，或许也能够成就别样的人生。

--------------------

### **推荐阅读** ###

• [吴师兄实名吐槽 LeetCode 上的一道题目。。。][LeetCode]• [面试字节跳动时，我竟然遇到了原题……][Link 1]• [Leetcode 惊现马化腾每天刷题 ？为啥大佬都这么努力！][Leetcode _]• [为什么 MySQL 使用 B+ 树][MySQL _ B_]• [一道简简单单的字节跳动算法面试题][Link 2]• [新手使用 GitHub 必备的两个神器][GitHub]• [卧槽！红警代码竟然开源了！！！][Link 3]

--------------------

欢迎关注我的公众号“**五分钟学算法**”，如果喜欢，麻烦点一下“**在看**”~

![format_png 8][]

[format_png]: /images/20230208/8bc206d248d64afb942da929364bf59d.png
[format_png 1]: /images/20230208/9495f542ea2f4f1fa3b813f777e37f38.png
[format_png 2]: /images/20230208/4e013b5272d74205888b5cc8fa181ffc.png
[format_png 3]: /images/20230208/7522d80db4254bc193189d122bdb901a.png
[format_png 4]: /images/20230208/012d2af7044641fcb65fa5c9460fd54d.png
[format_png 5]: /images/20230208/73db036aa7004ae2b0dad23c3fd53e58.png
[format_png 6]: /images/20230208/a65c05210c85476eb34fa39fa037e12e.png
[format_png 7]: /images/20230208/a419b563e6b14377b7b8e0585aa8eab1.png
[LeetCode]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75efcd79fcf9c65ebb5070122b9705e18cb1c46b06c5eb3e299520ed4a25e327bc07bb4b&idx=2&mid=2247490158&scene=21&sn=12e587a361f0df072d2dc164c219a61e#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75aecd79fcb8b5f932c7ba5ed7a9e34a6c99f20bc129cef33774167d668e8745755d02ad&idx=1&mid=2247490095&scene=21&sn=baa0379b1ca62db17327a2cb825a1b24#wechat_redirect
[Leetcode _]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e759ccd79fc8a8cf663e3650128f0efffbc3c785eada46c1ad390e839133dd8c4ef34b31b&idx=1&mid=2247490077&scene=21&sn=2e7151b3bc56ea2cfdf262510c49d298#wechat_redirect
[MySQL _ B_]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e759ccd79fc8a73c77eacfd7c8b1391b08864e2e13fdf5a6e41e218a499d5a87ee12e4e6a&idx=2&mid=2247490077&scene=21&sn=56c52b385c98c7f0ad33c2621da101eb#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e767dcd79ff6b2733dd8905f188afb19eb400d5e644f5b5127f909ee7c3583786031f9c20&idx=2&mid=2247490044&scene=21&sn=bb3610dfedbb2e0c017c3ff3d5e4684b#wechat_redirect
[GitHub]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e764acd79ff5c90eccffd8a5abcd999c07fd91fa60993778073da57b337ea2809f5bc87ff&idx=2&mid=2247489995&scene=21&sn=767d0abd5c038665e1ad4618cab359fc#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e7712cd79fe040e2f6ee2fefac2d203cb42a352026668e55807564462bc5de0d9a7704e45&idx=1&mid=2247489683&scene=21&sn=e58e18a5db229e8e8e3bfed94970b7bb#wechat_redirect
[format_png 8]: /images/20230208/d642bac154f94b1588faaa6310425553.png