计算机组成原理笔记（王道考研）第三章：存储系统

内容基于中国大学MOOC的2023考研计算机组成原理课程所做的笔记。

感谢LY，他帮我做了一部分笔记。由于听的时间不一样，第四章前的内容看起来可能稍显啰嗦，后面会记得简略一些。

西电的计算机组织与体系结构课讲法和王道考研的课不太一样，要应付校内考试建议还是跟着老师学比较好。以下是20年西电计科院车向泉老师这门课的录播下载链接（请勿将录像上传到B站等网站！！）：

链接：https://pan.baidu.com/s/1bFs3ajhy8ZcbHopS9izGsw

提取码：fdez

期中考试占20分，一般只考前两章内容，期末考试占60分，一般前两章内容不考，考察内容一般考前的复习课都会讲清楚，请务必认真听复习课。

其他各章节的链接如下：

计算机组成原理笔记（王道考研）第一章：计算机系统概述

计算机组成原理笔记（王道考研）第二章：数据的表示和运算1

计算机组成原理笔记（王道考研）第二章：数据的表示和运算2

计算机组成原理笔记（王道考研）第三章：存储系统

计算机组成原理笔记（王道考研）第四章：指令系统

计算机组成原理笔记（王道考研）第五章：中央处理器

计算机组成原理笔记（王道考研）第六章：总线

计算机组成原理笔记（王道考研）第七章：输入输出系统

其他各科笔记汇总

存储系统

存储系统基本概念

本章探讨二进制数据在电脑中如何存储。之前提过现代计算机的结构大致如下图所示，其中主机内部的主存储器（内存）和辅存都是存储器。这些存储器的容量是不一样的，主存更小而辅存更大

下图中的机身存储就是辅存

除了主存和辅存之外还有没有其他用于存储数据的存储器？为什么主存和辅存的存储容量差异这么大？除了存储容量之外，它们之间有没有速度差异？这就是在这一小节要探讨的第一个问题：存储器的层次结构。另外在这一小节当中也会介绍计算机内部存储器从不同角度进行的分类，最后会讲度量存储器的一些性能指标

存储器的层次化结构

直接见下图，后面是对下图的一些说明

手机里的辅存一般不是用磁盘实现的

平时手机里安装的app就存储在辅存内，由于辅存的读写速度比较慢，因此CPU不能直接和辅存进行数据交互

CPU的数据处理速度很快，如果让CPU直接去读写辅存的数据，CPU处理数据的速度会被辅存读写数据的速度拖累

平时要启动一个app就需要把该程序相关的数据先从辅存调入到主存。当app数据被放到主存之后，手机的CPU就会开始运行app的代码，我们就能使用app了。CPU可以向主存读数据也可以向主存写数据

老版微信打开时会有一个页面（一个人站在月球上看地球），手机会在这个页面停留几秒，这几秒就是把微信的数据从辅存读入主存所需要的时间

主存之上还有Cache，增加这一层的作用是什么？虽然主存读写速度已经很快了，但是依然远远跟不上CPU的运算速度，为了缓解这种速度矛盾通常计算机硬件会把当前有可能频繁被访问的代码和数据从主存复制一份到Cache当中。CPU可以直接读取Cache当中的副本数据。总之添加Cache层主要是为了缓解CPU和主存之间的速度矛盾

假设微信的数据现在被调入主存，要进行视频聊天。接下来一段时间内微信处理视频聊天的相关代码有可能会被频繁地访问，这时候就可以把处理视频相关的代码从主存复制一份到Cache当中。由于Cache是更靠近上层的存储层，因此Cache的读写速度会更快，CPU直接访问Cache里面存储的视频聊天相关的代码可以比直接访问主存快很多，这样就能让视频聊天更流畅

除了Cache之外还会看到更上面最接近CPU的一层叫做寄存器。什么是寄存器在之前的小节中已经讲过好多次（如ACC，MQ等），寄存器的读写速度又要比Cache快的多，所以CPU在进行加减乘除之类的运算时会把操作数先放到寄存器里面。CPU内部包含的寄存器数量很有限，有可能只有几十个

主存和辅存之间的数据交换由硬件+操作系统实现。主存和Cache之间的交换由硬件自动完成

操作系统需要实现页面置换算法，根据页面置换算法决定要把哪些数据从主存换出到外存。主存和辅存实现了虚拟存储系统（操作系统课会讲），虚拟存储系统解决了主存容量不够的问题。在实现了虚拟存储系统之后应用程序员看到的主存容量可以比它实际的容量要大得多，这就是“虚拟”的意思

接下来以一个实际的例子感受一下各层存储器的速度与价格间的差异

各层存储器的速度与价格

以京东的三星内存条介绍为例。Memory指的就是三星的内存条，大小为8GB，后面列出了其读（Read）、写（Write）、复制（Copy）的速度。当这个内存条与Intel的$i$5-9300H CPU进行配合工作的时候，内存的读速度可以达到37051MB/s，写速度可以达到37566MB/s（40GB/s左右），这就是内存也就是主存这一层的读写速度

除了内存之外还会有Cache层，各种CPU型号里面肯定会介绍其高速缓存也就是Cache的容量大小。从上图可以看出$i $5 的处理器受硬件开发成本限制的原因总容量只有 12 MB ，比内存的容量小得多。另外在现代 CP U 中 C a c h e 通常也是分层的，像上图$ i$5处理器就分为L1、L2、L3这几层，越靠近上层的容量越小，处理速度也更快，从图中也可以看出其访问/读写速度都比内存高得多

上面是主存层和Cache层，这两层都能直接被CPU访问，接下来再看靠近下层的辅存。从上图可以看到290+的价格机械硬盘的存储容量可以达到1TB，但实际读写速度100M/s左右，远小于内存。以蓝光光盘为例，外存制造成本又远小于辅存，但读写速度小于辅存

请无视SATA6Gb/s

在好几年前大多数的辅存都采取机械硬盘，但是近几年几乎所有的电脑都采用固态硬盘SSD来作为辅存，可以看到500+的价格能买到500GB大小，读写速度达到550MB/s的固态硬盘，比原来的机械硬盘要快的多。一些比较新的硬盘如果采用m.2接口读写速度甚至能达到4GB/s。由于固态硬盘的读写速度比机械硬盘快得多，电脑系统安装在固态硬盘里面会比安装在机械硬盘里面启动速度快得多，因为在开机时需要把系统相关的数据从辅存读入到主存，辅存读入的速度越快开机的速度越快

这就是存储器的层次结构，接下来探讨存储器的分类

存储器的分类

直接见下面的几张图即可，这里只做一些必要说明

1.按层次结构分类

我们需要重点关注的是高速缓存、主存、辅存这中间三层

高速缓存和主存可以直接被CPU读写，而辅存里的数据只有被调入到主存之后才能被CPU访问

2.按存储介质分类

半导体存储器的读写速度通常要快一些

好多年前的软盘、磁带、机械硬盘都以磁性材料作为存储介质。光盘/DVD之类则是光存储器

3.按存取方式分类

之前说过其实所有的存储器都是分为一个个存储单元，每个存储单元都有各自的地址编号。RAM读写速度与物理位置无关，像内存条就是一种RAM。复读机里面的磁带就是一种SAM，复读机/录音机会有一个磁头来读写磁带里面存放的数据，磁带中间的轴转动时磁条会划过读写磁头，此时就能读出其中的数据。机械硬盘/磁盘就是一种DAM，磁头臂会进行前后移动移到想读取的区域（随机存取），接下来中间的马达会带动磁盘旋转，想要读写的数据滑过磁头下方时磁头就能进行相应的读和写（顺序存取），DAM读写速度介于SAM和RAM之间

以上三种类型的存储器都要指明一个要读写的地址然后进行读取，CAM的存取方式会不太一样。注意这种存储器和其他三种的区别，其他三种是指定数据的存储地址然后直接去那个地址当中读或者写这个数据。而CAM可以指明想要找的数据内容是什么，然后根据数据的内容去查找它的存储位置在哪儿。即下面三种按照地址来访问，上面这种是按照内容来访问

4.按信息的可更改性分类

BIOS通常写在ROM中，而这个ROM芯片通常集成在主板上

5.按信息的可保存性分类

手机没电关机之后需要开机，开机时会有开机画面并且过程很缓慢，这是因为之前手机在运行时操作系统，各自软件的数据本来是存在主存里的。然而在断电之后主存里的数据被清空，所以在开机时要把系统等各种各样的数据从辅存调入主存，因此开机的过程会比较慢。手机系统或者电脑系统安装在辅存里，显然这些数据电脑和手机没电之后依然是存在的，不然就不可能重新开机了

存储器的性能指标

之前说过存储器的MDR数据寄存器的位数反映了存储器的存储字长是多少，MAR地址寄存器的位数又反映了存储字数是多少。存储字数 $\times$ 存储字长=存储容量

单位成本指每一个比特位所需要付出的金钱成本是多少

注意 $T_a$ 和 $T_m$ 的区别

主存储器的基本组成

本节首先学习使用半导体元器件存储二进制0和1的基本原理，然后通过半导体元器件的组合可以构成存储芯片。由于存储芯片里面存储了很多个字的数据，因此存储芯片必须提供寻址功能。本节最后会探讨不同的寻址方式如何实现

首先来看组成主存储器的基本半导体元件和它的工作原理

基本的半导体元件及原理

第一章说过一个主存储器逻辑上可以分为存储体、地址寄存器MAR、数据寄存器MDR三大部分。这三部分会在时序控制逻辑电路的控制下相互配合工作。之前说过存储体就是用来存取实际的二进制数据0和1的，一个存储体由多个存储单元构成，而每个存储单元又由存储元也就是存储元件来构成

用一个存储元件也就能存储一位的二进制0或1，根据电容是否保存电荷两种状态信息来对应二进制的0和1

假设电容上现在保存着一些电荷，我们规定当它保留了一些电荷时表示二进制1，那接下来如何读取这个二进制的比特位呢？只需要给MOS管加一个高电平信号（也可以理解为输入了一个二进制1），当MOS管这一端输入电压达到一定阈值之后就会接通，相当于开关可以开始导电。由于MOS管接通，此时电容里保存的电荷就可以顺着导线往外流，当在另一端检测到输出电流时就意味着此时输出了二进制1。如果本来这个电容没有保存电荷，也就是这种状态表示二进制的0，当MOS接通时在另一端并不能检测到电荷的流出，因此在这种情况下就能判断电容保存的是二进制0

这就是读出一个二进制的原理，再来看写入一个二进制的原理

假设现在想让电容保存一个二进制的1，那可以在另一端加高电平同时给MOS也加高电平使其接通。导致电容存储一些电荷也就是存储了二进制的1，接下来再让MOS断开，这样电容里的电荷就无法跑出了

这就是存储元件存储二进制0和1的原理，需要用到一个MOS管和一个电容

将多个存储元进行科学合理的连接就能一次性读出或者写入多个二进制数据。比如下图上面这一排它们存储的二进制信息分别是这样一些值 101000011，红线连接了每一个存储元的MOS管，如果给这条红线加一个高电平就意味着所有存储元的MOS管都可以被导通。当MOS管被导通之后电容里存储的电荷就可以顺着绿色的线往外导出，只需要检测每一条绿线有没有产生电流就可以判断每一条线对应的是二进制0还是1，如果有电流意味着产生二进制1，如果没电流意味着产生二进制0。用这样的方式就能读出这一整行的存储元所存储的二进制比特信息

这样的一整行就是之前提到过的存储单元，也就是一个存储字，多个存储单元就构成了之前提到过的存储体（也可以叫做存储矩阵）。一次能读出的这些二进制位就是一个存储字，像下图中存储字长就是8bit，一行总共有8个存储元。如果让16个存储元构成一行，那么就意味着存储字长变成了16bit

这里就能理解为什么第一章说存储器每一次读或者每一次写的单位都是一个存储字。因为从属同一个存储字的存储元件的MOS管接的都是同一根线。如果要接通就是整个字的存储单元同时接通，也就可以同时被读出或者同时被写入

要注意字节和存储字的区别。1Byte=8bit，而一个存储字等于多少个比特具体要看存储体的结构是什么样的。像下图存储体就只包含了两个存储单元

接下来要研究的问题就是如何根据地址来决定要读或者要写哪个存储字，这就涉及到译码器的使用

存储器芯片的基本原理

译码器会根据地址寄存器MAR里边给出的这几位地址，把它转变成某一条选通线的高电平信号。每一个地址会对应译码器的一条输出线。经过译码器的处理，一个地址信号会被转换成译码器的某一条输出线的高电平信号，当这一条红色的字选线被接通之后就可以通过绿色的数据线把每一位的二进制信息传送到MDR当中，接下来CPU会根据数据总线从MDR当中取走这一整个字的数据。这就是给出地址之后通过译码器的处理选中其中某一个字的原理

数据总线的宽度和存储字长相同

接下来继续完善这个存储芯片的构成

还需要增加一个控制电路用于控制MAR、译码器和MDR。比如CPU会通过地址总线把地址送到MAR当中，但是由于是用电信号来传送这些二进制数据，而电信号难免会有不稳定的情况，因此当MAR里面的电信号稳定之前这个地址信息不能送到译码器当中的。这就是控制电路的一个作用，只有MAR稳定之后它才会打开这个译码器的开关让译码器来翻译这个地址然后给出相应的输出信号。同样的当数据输出时只有电信号稳定之后控制电路才会认为此时的输出是正确无误的，所以它也需要控制MDR在什么时候给数据总线送出数据

另一个方面存储芯片还需要对外提供一些线路。一个叫片选线，通常用 $\overline{CS}$ （chip select）和 $\overline{CE}$ （chip enable）来表示片选线的电信号。如果给出的 $\overline{CS}$ 芯片选择信号是一个低电平时就说明这个芯片的总开关是被接通的，可以正常工作

另外控制电路还需要对外提供一个读控制线和写控制线。当写控制线的信号 $\overline{WE}$ 是低电平时表示此时这个芯片正在进行的是写操作，也就是要把MDR里保存的数据输入到各个电容当中。当需要读出数据时需要把读控制线 $\overline{OE}$ 电信号变为低电平，当读控制线接收到一个低电平时控制电路就知道现在要进行的是读操作

还有一种常见的方法把两根控制线合二为一，用一根控制线来表示此时要进行写还是读。这种情况下输入低电平时表示要进行写操作，输入高电平表示要进行读操作

注意题目说的是采用两根读写线还是一根读写线，这两种方案芯片对外暴露的金属引脚数目是不一样的

到目前为止就给出了一块存储芯片的完整构造，把这些内部细节屏蔽掉进行封装，整体来看存储芯片由下图中所示的几个逻辑部分构成

存储矩阵就是一个个存储元

译码驱动电路分为译码器和驱动器。译码器的作用刚刚已经说过，会输出某一条线的高电平信号，这条线连了很多很多的存储元，需要控制这些存储元的开和关。为了让译码器输出的高电平稳定有效，通常还会在译码器后面加上驱动器，驱动器是把电信号放大的部件

读写电路包括下图那些红色，绿色的线还有控制电路

逻辑上我们可以把存储芯片的内部分为这样的三大部分

另外存储芯片需要接收来自外界的地址信息，这个地址信息通常是CPU通过地址总线传过来的，此外还需要数据线来控制数据的传输。除此之外还需要片选线的电信号来确定这块芯片此时是否可用。另外也需要提供读/写控制线（有可能有一条有可能有两条）

下图内存条中一块块黑色的小芯片就是存储器芯片，可见存储器有可能由多块存储芯片构成。如果只想读取某块芯片指定地址的数据就需要只让这块存储芯片的片选线信号有效（给低电平），这样就能保证读取指定芯片的数据，这就是片选线和片选信号的作用。每一块存储芯片都会对外暴露出一个个金属引脚，这些金属引脚就是用来接收地址信号、数据信号、片选信号、读/写信号的，每一条线都会对应一个金属引脚

除了实现功能所必须的金属引脚之外还会有供电引脚和接地引脚

有的题目会告知某一块存储芯片的参数信息，判断这块存储芯片至少有几个引脚

8 $\times 8$ 位的存储芯片，第一个8表示有8个存储单元，第二个8位表示存储字长是多少，即每一个存储单元包含多少位的信息。可以根据这两个信息来分别判断地址线和数据线有多少位，然后根据地址线和数据线的数量再加上片选线和读/写控制线就可以判断出这块存储芯片应该对外暴露出多少个金属引脚

寻址

按字节寻址、字寻址、半字寻址、双字寻址之前讲过。直接见下图即可，此处详细讲解略过不记

SRAM和DRAM

在上一小节讲了存储芯片的基本原理。如何存储二进制的0和1，如何根据一个地址来访问某一个存储字，这是上一小节学习的内容

这一小节会介绍两种特定类型的存储芯片SRAM（Static Random Access Memory，静态RAM）和DRAM（Dynamic Random Access Memory，动态RAM）。DRAM用于主存，SRAM用于Cache。DRAM和SRAM的对比是高频考点

之前提到过RAM（Random Access Memory），当指定某一个存储单元的地址时，这个存储单元的读取速度并不会因为存储单元的物理位置而改变

DRAM 芯片

上一小节介绍的这种芯片其实就是DRAM芯片，可以用于制造主存。DRAM和SRAM的核心区别在于存储元件不一样

来看一下这两种存储元存储元件的区别

栅极电容 V.S. 双稳态触发器

DRAM芯片的存储元栅极电容上节已经说明过，此处不再赘述，直接看图即可

再来看SRAM芯片，SRAM芯片的存储元是下图右边的双稳态触发器。这个双稳态触发器里面总共包含了6个MOS管，分别用 $M_1\sim M6$ 来标注。之所以叫双稳态触发器，是因为这种触发器可以呈现出两种稳定的状态，规定A为高电平，B为低电平的状态对应二进制1。A为低电平，B为低电平的状态对应二进制0。用触发器的这两种稳定状态就可以记录此时存储的是二进制1还是0

双稳态触发器需要用两根数据线来读出0和1的状态。如果原本里面存储的是二进制1，当给字选择线接通加高电平时，线BLX会输出低电平信号。如果原本里面存储的是二进制0，线BL会输出低电平信号，线BLX不会输出任何电信号。根据左边还是右边哪条线输出了低电平信号就可以判断这个触发器里面原本存储的是1还是0

如果要写入二进制0和1也很简单。以二进制0为例，要写入二进制0只需要给线BL加低电平，线BLX加高电平，这样就能使得触发器变为A低B高的状态，而这个状态对应的就是二进制0。要写入二进制1也是类似的原理

了解了这两种存储元的基本原理之后来看一下它们有什么区别。区别直接看下图即可，此处详细讲解略过不记

注意理解什么是“刷新”

DRAM 的刷新

简单模型中一个译码器要接的线太多了，如何解决这个问题呢？

把这些存储单元从一维的排列变成二维的排列，也就是把它们变成一个存储单元构成的矩阵。原本的n位地址会被拆分成行地址和列地址来分别送给行地址译码器和列地址译码器，这样每个译码器只需要处理 $\frac n2$ 位也就是一半的地址信息。随着存储器的发展和存储容量越来越大，现代存储器甚至会有三维的排列，但原理都是类似的

现在给右边的图示进行简单的连线，看下如何根据一个地址选中某一个存储单元。如果此时要访问的地址是全0，地址总共有8位，这个地址会被分为前后两半，前半部分作为行地址分给行地址译码器，后半部分作为列地址分给列地址译码器，4个全0的地址会导致行地址译码器的第0根选通线被选通，4个全0的送给列地址译码器也会导致它的第0根选通线被选通。一个存储单元只有行和列这两个选通信号都选通时才可以对它进行读和写。这样就完成了通过行地址和列地址来选中一个存储单元的操作

现在已经知道了什么叫一行存储单元，只要给出一个行地址，那么行地址译码器就会选中一行的存储单元，而刷新操作每次就会刷新一整行

怎么刷新呢？会有一个专门的刷新电路来支持，刷新电路会直接读出一整行的存储单元信息然后重新写入也就是重新给电容充电。由于刷新一整行本质上就是进行了一次读操作，所以它的耗时和一次读/写周期的耗时差不多。采用思路三来决定什么时刻刷新

刷新时CPU不能对存储器进行读和写

在实际应用当中可以利用CPU不需要访问存储器的时间进行刷新，比如CPU取得了一条指令，在指令译码阶段就可以进行刷新操作

DRAM 的地址线复用技术

之前已经知道了什么叫行地址什么叫列地址，同时送出行地址和列地址，地址有多少位就要有多少根地址线，而DRAM存储芯片通常存储容量会比较大（有可能需要32位地址）。为了地址线对应的电路更简单，DRAM通常会采用地址线复用技术，将行列地址分前后两次传输，先后把行列地址送到行列地址缓冲器里面，接下来在控制电路的控制下把行列地址再送给译码器进行处理

补充：现在的主存通常采用SDRAM，买电脑说的DDR3和DDR4都属于SDRAM

只读存储器ROM

在这一小节中会学习ROM芯片。上一小节中学习了两种具体的RAM芯片DRAM和SRAM，RAM芯片支持随机存取，读写速度较快，具有易失性，断电后数据消失。而ROM芯片具有非易失性，断电后数据不会丢失。本节会介绍几种ROM芯片

了解各种 ROM

比如买手机的时候看到文字宣传8GB RAM+256GB ROM，分别指的就是主存和辅存

计算机内的重要 ROM

通过之前的学习知道计算机的主存是用来存放一系列指令和数据的，CPU要做的就是从主存里取指令并执行指令。然而RAM具有易失性，断电后数据会全部丢失，也就说计算机关机之后主存里的数据就全部都没了，当再一次开机时需要把操作系统和各种应用程序相关的指令和数据重新调入主存，而操作系统安装在辅存里面。由于开机时主存里完全没有数据和指令，CPU就需要从主板上的一块ROM芯片上读取开机所需要的一些指令，这块芯片就是BIOS芯片

重装电脑的时候就可能会见到BIOS界面

补充：虽然BIOS芯片通常被集成在主板上，但是逻辑上应该把它看作是主存的一部分。也就是说在计组中提到主存时，除了指我们熟悉的内存条之外，还应该加上BIOS芯片，二者结合才是一个完整的主存

统一编址的意思是如果这块ROM芯片的容量是1KB，那么CPU会把0到1023这几个地址分配给ROM芯片。然后RAM芯片也就是内存条的地址从1024开始往后编号

主存储器与CPU之间的连接

之前已经知道了单块存储芯片对外暴露出来的一些接口

首先会探讨单块存储芯片和CPU的连接如何实现，接下来会介绍多块存储芯片和CPU之间的连接，分别是位扩展、字扩展和字位同时扩展，这一小节的最后还会补充一些关于译码器的知识

单块存储芯片与CPU的连接

首先来回顾一下单块存储芯片的结构

需要对外暴露出这样的一些接口：绿线是用来传送数据的，通常会通过数据总线和CPU进行连接。红线是用来传送访问地址的，通常会通过地址总线和CPU进行连接。除此之外还需要暴露出片选线、读控制线和写控制线的接口，CPU通过控制总线来发送这些控制信号。下图给出的图示就是一个 $8\times8$ 位的存储芯片，因为总共只有8个字，每个字的字长是8位

字扩展和位扩展是这两个小节要解决的两个主要问题

这里只使用了单块存储芯片来存储数据，并且只能存储8B的数据。现在如果想要扩展主存字数该怎么办？这就是这一小节要学习的字扩展要解决的问题，我们可以连接多块存储芯片来扩展主存的字数

这里给出的存储芯片存储字长只有8位，也就是CPU一次只能存或者取8bit的数据，但是现代的CPU大多数可以同时存或者取64bit的数据，也就是说现代计算机数据总线的宽度通常都有64位宽。之前说过应该尽可能的保持数据总线的宽度和主存的存储字长一样，只有这样才能尽可能地发挥数据总线的性能。每一次多存或者多取一些数据可以让数据的读写速度更快。所以现在问题产生了，现在拥有的单块存储芯片如果芯片的字长比数据总线的宽度更小该怎么办呢？这一小节要学习的位扩展就是要解决这个问题，通过多块存储芯片的合理连接可以让整个主存的存储字长扩展为和数据总线宽度一致

这里还需要补充一点，之前在讲存储芯片的时候把MAR和MDR都画在了存储芯片里面，但是现在的计算机MAR、MDR通常集成在CPU内部。所以现在存储器当中的寄存器其实并不是MAR和MDR，只不过是一个普通的寄存器而已

因此现在使用的计算机一般来说是下图的结构。CPU里面集成了MAR和MDR，MDR里面存储的数据，即要读或者要写的数据，是通过数据总线和主存进行交换的。而MAR里存储的地址数据是通过地址总线送给主存的。另外CPU还需要通过控制总线向主存发送读/写这一类的控制信息。此外现在的主存当中一般会包含多块存储芯片

存储器芯片的输入输出信号

接下来为了描述方便，给一块存储芯片的各个输入信号和输出信号进行命名

有可能要输入多位的地址，地址通常用A（address）表示， $A_0$ 表示低位。地址通常用D（data）表示， $D_0$ 表示低位。片选信号通常用 $\overline{CS}$ （chip select）或 $\overline{CE}$ （chip enable）表示，上有横线表示低电平有效。读写控制线的信号通常用 $\overline{WE}$ （write enable）或 $\overline{WR}$ 表示，上有横线表示低电平信号时进行写操作，高电平信号进行读操作

也有的地方可能会把读信号和写信号分开用两个输入端输入，写信号用 $\overline{WE}$ 表示，读信号用 $\overline{OE}$ 表示，都是低电平有效

增加主存的存储字长 - 位扩展

如果此时已经买到了一块 $8K \times 1$ 位的存储芯片，这个单块的存储芯片应该如何和CPU进行连接？

8K对应二进制是 $2^{13}$ ，所以需要用13根地址线来表示这8K个地址，因此这块存储芯片对外暴露出的地址线引脚应该是 $A_0\sim A_{12}$ 总共13条，CPU会把它想要访问的地址通过地址总线送过来，这样就完成了地址线的连接

接下来看WE信号，CPU也会有一个金属引脚来发送这个读写控制信号，这个信号通过控制总线传给这个芯片

接下来看数据的传送，虽然CPU可以通过数据总线同时读或者写8bit的数据，然而由于存储芯片的限制，每一次只能通过数据总线来传送1bit，也就是说数据总线的传输能力利用不够充分

这里还有一个CS也就是片选信号没有接，由于只有这一块芯片工作，所以可以直接简单粗暴地给它接上一个高电平的信号

不管怎么说，这样就完成了单块存储芯片和CPU的连接。此时整个主存只有一块存储芯片，每一次只能读或者写一位的数据，所以此时主存的存储字长就是1bit，数据总线并没有被充分地利用

为了解决这个问题可以给主存再加上一块相同型号的存储芯片，同样也是 $8K \times 1$ 位。同样CPU通过地址总线把它想要访问的地址信息传给这块芯片，因为左边和右边都有8K个存储单元，所以如果把13位的地址信息同时送给这两块芯片，地址信息可以同时选中这两块芯片相同位置的存储单元。读写控制线也一样，只需要把CPU发出的读/写控制信号同时送给两块芯片就可以，要么同时读要么同时写。右边这块芯片读出的这一位数据可以作为CPU读入的 $D_1$ 这一位数据。接下来只需要给片选信号加一个高电平，这样这两块芯片就可以同时工作

进行了这个改造之后，整个主存储器就总共有两块存储芯片，总体来看现在存储器的存储字长扩展为了2位，可以同时读或者同时写两位的信息

接下来还可以使用同样的方法继续增加同类型的6块芯片，最终得到下图的连接。每一块芯片都有8K个存储单元，CPU发出的 $A_0\sim A_{12}$ 这13位的地址信息会同时送给8片存储芯片。由于每一块芯片的存储单元只有1bit的数据，所以会把这8块存储芯片的这1位数据分别送到数据总线的不同位上，接下来数据总线可以同时把这8位的信息送给CPU。这样的话就把整个主存的存储字长扩展为了8bit。这种连接方式称为位扩展的方式

接下来再来看第二种连接方式也就是字扩展的方式

增加主存的存储字数 - 字扩展

假设现在买了一片 $8K\times 8$ 位的存储芯片，CPU可以同时读或者写8位的信息。由于存储芯片字长已经有8位了，因此这块存储芯片的字长、数据的宽度和CPU能够处理的宽度可以完美匹配，对于这个场景数据总线的传输能力已经被使用到极致，不再需要像之前那样进行位扩展。同样的由于它有8K个存储单元，因此需要有13位的地址信息。接下来再给片选信号加一个高电平，这块存储芯片就能正常工作了

现在会发现CPU还有3个地址位的信息没有被利用到，这个CPU的MAR本来有16位，也就是这个CPU拥有 $2^{16}$ 的寻址能力，然而现在只利用了13位的地址信息，并没有完全发挥出CPU的寻址能力，那如何解决这个问题呢？

同样地，买一块同型号的芯片，不能简单的用之前位扩展的方式解决问题。关键在于片选信号的使用，现在把 $A_{13}$ 连到左边这块芯片， $A_{14}$ 连到右边这块芯片。由于片选信号高电平有效，当 $A_{13}$ 和 $A_{14}$ 分别为1和0时，左边的这块芯片片选信号有效被选中，右边则不会工作，这种情况下只会读取出左边这块芯片对应存储单元的8bit数据。联系数电里译码器扩展的内容，易得 $A_{13}$ 和 $A_{14}$ 输入的都是两个1的信号时，这两块芯片都会被选中，这样两边会同时读或者同时写数据，出现冲突

所以如果采用这样的连线方式，想要让存储器正常地工作只能允许 $A_{14}$ 和 $A_{13}$ 这两位要么为01要么为10，不可以是11和00。此时如果把它们看作是一整个存储器会发现在这个存储器当中00和11开头的地址都不能用，所以这种连线方法有待改进

这种连线方法我们称之为线选法，会用一根专门的地址线作为片选信号来选中某一片芯片。如果CPU有n条多余的地址线，采用这种方法就只能有n个选片信号

这里结合数电的经验应该很容易理解，就不赘述了

接下来对线选法进行优化，采用下图的连线方式。自行结合数电理解这个非门的作用，此处详细讲解略过不记

显然这样连线之后整个主存的地址空间就是连续的。这里可以把设计的小电路看成是1-2译码器，什么叫1-2呢？就是输入1位的地址信息，这一位的地址信息有可能呈现出 $2^1=2$ 种不同的状态，这两种不同的状态会被译码器翻译为要么是上面那条线高电平要么是下面这条线高电平，这就是1-2译码器的意思。之前其实接触过如3-8译码器等更复杂的译码器，因此可以顺着这个思路往下优化，使用一个译码器来处理CPU的高位地址部分，这种方法称为译码器片选法，如果CPU能够给出n位的地址信息，那么通过译码器的翻译可以得到 $2^n$ 个片选信号

后面紧跟着介绍了一下3-8译码器的工作原理，这里略过不记

主存容量扩展 - 字扩展

现在有了译码器之后再来看如何更好的进行字扩展，以2-4译码器为例。此处的具体工作原理分析略过不记

注意译码器输出端的小圆圈（进行取反）和CS信号上加的横线和小圆圈的（低电平有效）含义不同

$A_{15}$ 这一位还没有使用，想要再使用这一位，只需要换成3-8译码器，然后再增加4片 $8K\times8$ 位的存储芯片

考试也有可能考察下面的连法，这种连法下 $A_{14}$ 就是没用的

这种设计在实际应用中是不可能采用的

总结一下字扩展，实际应用中都是采用片选法

线选法	译码片选法
n条线 $\to$ n个选片信号	n条线 $\to2^n$ 个选片信号
电路简单	电路复杂
地址空间不连续	地址空间可连续

目前学习了位扩展和字扩展，位扩展可以使存储器的字长变得更长，从而更好地发挥数据总线的数据传输能力，而字扩展可以增加存储器的字数，可以更好地利用CPU的寻址能力。这两种方法可以在不同维度上扩展主存的总容量

主存容量扩展 - 字位同时扩展

还可以把字扩展和位扩展两种方法进行结合，二者的结合就是字位同时扩展法，其实原理都是类似的

图里总共画出了8块芯片，因为每一块芯片是 $16K\times 4$ 位，而CPU可以同时读写8位，所以可以让每2块芯片为一组实现位扩展。上面这块芯片可以把它连接上 $D_0\sim D_3$ 这4根数据线，而后面这块芯片可以把它连接上 $D_4\sim D_7$ 这4根数据线。下图中画的空心箭头其实指的就是数据总线，数据总线总共有8位，其中低4位可以由上面这块芯片传输，高4位可以由下面这块芯片传输

再看字扩展。每一块芯片的字数是16K= $2^{14}$ ，所以芯片内的地址总共要用14位表示，可以把CPU的 $A_0\sim A_{13}$ 这14位的地址信息作为片内地址。CPU还有两个高位地址没有使用，可以给它接上一个2-4译码器，总共有4个片选信号，所以可以接上4组，每一组的芯片总共有16K这么多个存储单元，每一个单元可以存8位的数据，得到一个 $64K\times 8$ 位的存储器。再看每一组芯片所对应的合法地址，显然分别由00、01、10、11开头，整个主存的地址空间从全0到全1并且中间是连续不中断的，同时这个主存的字长也可以完美地匹配CPU的读写能力，这就是字位同时扩展法

补充：译码器

此处详细讲解略过不记

双口RAM & 多模块存储器

先回顾一个概念叫做存取周期，存取周期就是可以连续读/写的最短时间间隔。之前说过对于DRAM芯片，由于DRAM芯片采用了电容这种存储元，因此对于DRAM芯片的读操作是破坏性的读出，所以这种芯片进行一次读写操作之后所需要的恢复时间比较长，一般是存取时间的好几倍。相比之下，SRAM的恢复时间就会短很多。存取时间意味着CPU从内存里读出一个字的数据实际上只需要 $t_2-t_1$ 的时间，然而虽然存取的时间很快，CPU又必须等这么一段恢复时间才可以读取下一个存储字，所以这就引出了一系列问题

下图提出的问题中第一个问题可以用双端口RAM这种方式来解决，而第二个问题可以用多模块存储器这样的方式来解决。多模块存储器又可以进一步地分为单体多字、多体多字（高位交叉编址、低位交叉编址）

很多打游戏的同学应该听说过“双通道内存”这个名词。把电脑改造成双通道内存可以很大地提升电脑的性能

首先来看第一个技术，双端口RAM。该技术可以用来优化多核CPU访问一根内存条的速度

双端口 RAM

比如我们的电脑是双核CPU但只有一根内存条，该内存条使用双端口RAM技术，这样两个CPU的核心就可以通过它的两个端口来对内存进行访问。如果要支持双端口RAM，就必须拥有两组完全独立的数据总线、地址总线和控制总线，也就是总线设计会变得更复杂（如果用大家熟悉的东西来说，就是电脑主板要设计的更复杂一些），需要有两组完全独立的各种各样的线，另外CPU里的内存控制单元和内存里的读写控制电路也需要更复杂的设计

现在来分析一下这两个CPU对双端口RAM的访问有可能出现的情况，4种情况直接见下图即可，此处详细讲解略过不记。当发生3和4这两种情况时，RAM里的控制电路应该向CPU发送一个“忙”信号，同时会有一些逻辑电路来决定暂时关闭其中某一个端口，等一个CPU完成操作之后另一个CPU再继续访问

可以把这部分内容和操作系统中的“读者-写者问题”进行对比。可以同时读但不能同时写，这其实和“读者-写者问题”一模一样

多体并行存储器

之前说过即便是对于一个单核CPU，CPU的读写速度也比内存快得多，而内存每次读写之后又需要一段恢复时间，当CPU想要连续读取一些数据时，就必须等待它的恢复时间。可以使用多体并行存储器解决这个问题

可以把下图理解成是在电脑上插了4根内存条，并且每一根内存条的大小都一致。可以有两种编址方案，第一种是高位交叉编址，第二种是低位交叉编址。CPU在对内存进行访问时必须要提供一个内存地址，高位交叉编址会采用内存地址的更高几个bit位来区分要访问哪一个存储体，相应的低位交叉编址采用内存地址的更低几个bit位来区分

下图假设每个存储体有8个存储单元，由这4个存储体构成的一整个主存地址空间大小就是 $4\times 8=32=2^5$ ，所以可以用5bit来表示主存地址。如果采用高位交叉编址，就意味着对于第一个存储体的第一个存储单元，给它的地址应该是00 000。高位的00表示这是 $M_0$ 存储体，后面的000表示在这个存储体内部的第几个单元，所以把它称为体内地址，类似地下一个存储单元就应该是00 001，再往后都是类似的。采用低位交叉编址时原理差不多，直接见下图即可

现在尝试着把这些地址信息翻译为十进制，会发现地址编号一个是竖着编一个是横着编，这两种特性会导致一定的区别。现在假设每个存储体存取周期为 $T$ ，存取时间为 $r$ ，假设 $T = 4 r$ ，也就是说CPU从一个存储体里取走一个字的数据总共需要 $r$ 的时间，但是CPU想要再次访问这个存储体就需要再等 $3 r$ 的恢复时间

对于高位交叉编址，如果要连续访问00000、00001、00010、00011、00100这样一些地址，那么根据体号和体内地址就可以知道第一个地址00000应该对应 $M_0$ 的哪个存储单元。接下来画一个甘特图，CPU对 $M_0$ 存储体进行一次读操作，每一次读的存取周期是 $T$ ，实际上CPU只花了 $r$ 的时间就完成了读操作，但是后面还必须等待 $3 r$ 的时间让这个存储体恢复。由于接下来要访问的这个存储单元同样属于 $M_0$ 存储体，所以必须等 $T$ 的时间才可以访问1号存储单元，接下来再过一个周期再访问2号存储单元，然后是3号、4号。总之由于连续访问的地址都属于 $M_0$ 存储体，所以每一次访问完之后都必须等待它恢复，也就是总共要过 $T$ 的时间之后才可以进行下一次读写。整个过程读了5个存储字，耗时 $5 T$ ，这是高位交叉编址

由于过程比较简单，下图就直接展示甘特图结果了

接下来再来看低位交叉编址。根据00000的末两位可以知道这个地址从属于 $M_0$ 存储体，所以CPU会从 $M_0$ 这读出一个字

刚才说过其实CPU从存储器里面读或者写一个字实际只需要 $r$ 的时间，因此过了 $r$ 的时间之后，对 $M_0$ 这个存储单元的读取工作就已经完成，后面 $3 r$ 的时间CPU不用管这个存储体，只需要让它自己恢复。所以过了 $r$ 的时间后，由于第二个要访问的这个存储单元所属的 $M_1$ 存储体此时已经准备好被读写，因此CPU可以直接从 $M_1$ 这读取数据

之后都是类似的，再往后要访问的2号存储单元属于 $M_2$ ， $M_2$ 此时已经准备好被读写，所以经过 $r$ 时间的读 $M_1$ 操作之后CPU就可以紧接着读 $M_2$ 的这个单元

再往后读 $M_3$ 的过程也是类似的，此处详细讲解略过不记

读取 $M_3$ 也需要r的时间，读完 $M_3$ 之后从刚开始算起总共已经过了 $4 r$ 的时间，也就是刚好过了一个存取周期。因此读取完 $M_3$ 的这个地址之后， $M_0$ 存储体又准备好被读取了，而刚好接下来要读取的地址又回到了 $M_0$ ，因此到 $T$ 这个时刻CPU又可以紧接着从 $M_0$ 读出下一个字的数据

对于这个例子，读出地址连续的4个单元总共的时间开销是 $T + 4 r$ ，也就是刚好等于 $2 T$ 。其实CPU在 $5 r$ 这个时刻就已经取得了这5个字，只不过这里计算总耗时考虑了最后这 $3 r$ 的恢复时间。进一步推广不难得出结论，当连续取 $n$ 个存储字，采用低位交叉编址，那么总耗时应该是 $T + (n - 1) r$ 。因为对各个存储字的读取刚好是可以无缝衔接的，所以读取 $n$ 个存储字总共需要 $n r$ 长的时间，而最后一个存储字读取完之后还需要给它留 $3 r$ 的时间进行恢复，所以整体来看耗时就应该是 $T + (n - 1) r, (T = 4 r)$ 。这是一种考题，考察对微观层面的时间开销的计算

如果连续读取的字数 $n\to \infty$ ，使用这种策略读写一个字的平均只需要 $r$ 的时间。所以在访问一系列地址连续的存储单元时，低位交叉编址的方案效率要比高位交叉编址高得多

这就是多体并行存储器

为什么要探讨“连续访问”的情况？

因为在实际应用当中很多数据其实就存放在一些地址连续的空间，比如数组。我们平时写的程序代码，或者说程序的指令也是连续地存放在主存当中的，除非遇到if-else之类需要发生跳转的地方，否则程序指令肯定是顺着地址一条一条往下执行的

应该取几个“体”？

既然这种低位交叉编址的方案能让存取效率变得更高，那应该取多少个“体”呢？

直接见下图说明即可，此处详细讲解略过不记

总之最好的方案还是 $m = t / r$ 。这种方案可以让存取流水线的效率达到顶峰，同时存储体的数量最少成本最低

存取时间 $r$ 指的是存储体的性能瓶颈，存取字至少也需要r这么长的时间。而总线传输周期 $r$ 指的是通过数据总线把一个数据传给CPU至少需要 $r$ 的时间。所以虽然这两种表述方式背后的含义是不一样的，但是都意味着CPU存取一次时间不可能低于 $r$ ，因此不管题目给的是哪种条件，都可以按同样的算法来处理

多模块存储器

目前为止介绍了多体并行存储器，这种存储方案的特点是每一个体，每一模块之间是相互独立的，与这种方案相对应的另一种方案是单体多字存储器

上面这种实现方式可以让每一个存储体独立地工作，CPU可以自由地选择每一次要从哪个存储体读出哪个字，它们之间都是相互独立的。而下面这种方案相当于把这几个存储体进行了一个合并，整个存储器只有一套读写电路，地址寄存器和数据寄存器。本来每次只能读写一个存储字，但是经过这样的合体之后每次读取的就是一整行也就是4个字。为了配合这种单体多字存储器，需要把数据总线的宽度改为m个字，每次可以并行地读出m个字。显然这种单体多字存储器灵活性要比多体并行存储器差一些，我们并不能单独地选择要读取其中的某个字，只能一次读一整行也就是4个字的内容。不过如果从整体读写速度的提升来看，上面这种方案和下面这种方案都差不多，无论是哪种方案，都能很大地提升主存的读写速度

以上就是这一小节理论部分的内容，接下来我们尝试把这个理论应用到现实生活当中

以内存条为例，之前说过双通道内存可以提升整体性能，事实上所谓双通道内存就是低位交叉的二体存储器，给电脑插了2根内存条之后，CPU给这2个内存条编址采用低位交叉编址方案，虽然内存的读写速度跟不上CPU，然而CPU可以交替地访问这两个内存，这样就可以让内存的整体吞吐量几乎翻倍

当然这里所谓的翻倍指的是连续访问的情况，经过之前的讲解应该不难理解

可以拆开主板看一下，很多主板给的内存条卡槽颜色不一样（如下图，虽然该主板支持的DDR2内存已经过时了，但是现在的主板其实也都差不多）。以后如果有2根内存条应该插到颜色相同的卡槽里面，只有这样才是低位交叉编址。如果其中一条插到了黄色这，另一条插到了绿色这，这种插法相当于给这两个内存条进行高位交叉编址，只是单纯地扩充了内存的容量，并没有提升访存速度

当买内存条时可挑选相同主频和容量的两根内存条来组成双通道。当然可以买一根16GB的内存直接插到主板上，但是更好的方式是选择两根8GB的内存然后分别插到黄色的卡槽上，这样内存性能能更高。所以这也是为什么去搜内存条时会发现有的商家卖内存条是按 $16G\times 2$ 这样来卖的，因为两根一起就意味着可以组成一个双通道

下图中内存条的主频是3200MHz，这反映了它的读写周期有多快。主频越高，相应的读写周期 $T$ 就越短，读写时间 $r$ 也越短。如果买的是两根主频不一样的内存条，那主频更高的内存条就会进行降频处理，也就发挥不出它所有的功效，因为CPU在处理多体存储器的各个体时只有 $T$ 和 $r$ 都相等才比较方便，这就是为什么要选相同主频的原因

想要将两个内存条组成双通道时如果容量不同，则只有低地址部分这两个内存可以组成双通道，高地址部分依然是单通道的性能，而这有可能会导致电脑性能不太稳定。如果打游戏时游戏刚好被装到了低地址部分，那游戏可能会运行的更流畅一些，画面帧数什么都会更好，但是如果游戏被装到了高地址部分，那运行起来就会更卡。所以如果组成双通道的两根内存容量不一样，电脑性能有可能会更不稳定

再以下面两张笔记本电脑配置截图为例。左图说明的是整个电脑的概况，为内存16GB的MacBook Pro。但查看内存的详细页面会看到电脑里面其实是插了两根8GB的内存条，第一根内存条插在0号卡槽里，第二根内存条插在2号卡槽里。有可能该电脑的主板也有4个卡槽，编号分别是0~3，插在0号和2号时就可以组成一个双通道，所以这台电脑在出厂时或许就已经考虑到了双通道的问题

外存储器磁盘存储器

外存储器

磁表面存储器每次读写都以1bit为单位，读和写不能同时进行

磁盘存储器

主机每次对磁盘进行读写操作都以扇区为单位

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LGF91Us5-1663675480178)( https://xdu-cslee-blog.oss-cn-hangzhou.aliyuncs.com/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E7%AC%94%E8%AE%B0%E5%9B%BE%E7%89%87/image-20220911231846759.png)]

磁盘阵列

固态硬盘SSD

U盘也使用闪存技术

机械硬盘与固态硬盘

固态硬盘的结构

块大小：16KB$\sim$512KB

页大小：512B$\sim$4KB

系统对SSD的读写以页为单位，一个逻辑块对应一个SSD里面的一个页

如果数据存放在机械硬盘里面，一个逻辑块对应着一个磁盘块/扇区，磁盘的读写以块为单位

对于SSD，一个逻辑地址对应的实际物理位置可能会变，闪存翻译层会把映射关系修改正确

想要再次往已经写入数据的页写入数据必须先把一整块擦除，SSD会把同块的其他数据复制到另一块的对应位置，然后再把新数据写到另一块，接着把原来的块擦除，同时闪存翻译层会重新进行映射

理想情况下，固态硬盘的寿命

Cache的基本概念和原理

从这一小节开始会进入这章的重点，大题和小题的高频考点Cache

之前学习了存储系统的一些优化策略。可以用双端口RAM、多模块存储器的方式来提高主存的工作速度，但是无论主存的速度再怎么提高，相比CPU的读写运算速度依然很大。为了解决这个问题，一个比较容易想到的方法是设计更高速的存储单元，比如把DRAM芯片改成SRAM芯片，但是这又意味着存储器价格会更高，或者从另一个角度来想当成本相同时容量肯定要下降

基于程序的局部性原理，可以再增加一个Cache层来缓和CPU和主存之间的矛盾

来看一下Cache的工作原理

Cache 的工作原理

先看没有Cache的情况。假设下图是一个手机，辅存空间上安装了各种各样的软件

现在要启动微信，过程其实就是把微信相关的程序代码还有数据调入内存。比如微信里面可能会有一个模块用来处理文字聊天，还有一个模块用来处理视频聊天，还有一个模块的代码指令专门用来实现朋友圈的相关功能。当然除了应用软件的代码指令之外，也会有一些相关的数据被调入内存，比如微信的聊天数据还有朋友圈里的图片之类的缓存数据也需要放到内存里

把这些数据调入内存之后微信就可以开始正常运行了。微信运行的过程其实就是CPU从内存一条一条地取指令并执行指令。不过之前说过CPU和内存的速度差异很大，所以快速的CPU每一次都从内存里读取数据就会导致CPU的执行效率被内存的读写速度所拖累

假设现在正在视频聊天，在视频聊天的这段时间内，只有视频聊天的相关指令代码在这段时间内会被频繁地访问

所以如果能够把视频聊天相关的代码复制一份到更高速，读写速度更快的Cache当中。那么CPU就可以直接从Cache当中读取视频聊天相关的指令和数据。而Cache的读写速度比内存快多了，这样CPU和内存之间的速度矛盾就能被缓和，可以更好地配合高速的CPU工作

这就是Cache的工作原理

上图左下角图中最右边的Latency列表示CPU访问主存的某一个存储单元和访问Cache的某一个存储单元所需要付出的时间代价

在上图中Cache和CPU画成了两个框，但是现在的计算机通常Cache高速缓冲存储器被集成在CPU内部

Cache用SRAM芯片实现.之前说过SRAM速度要比DRAM快得多，但是成本也会更高。另外SRAM的集成度会更低，这就意味着如果想要把Cache高速缓冲存储器塞进一个很小的手机里面，注定了Cache的存储容量不可能做的特别大，这并不是有钱就能解决的问题，得考虑集成度和体积。Intel $i 5$ 系列CPU的Cache大小可能也就是12MB

局部性原理

大家可能会觉得刚才说的视频聊天的场景比较特殊，其他的程序运行也会存在描述的这么理想的场景吗？就是说在某一段时间内CPU是否只会访问到某一部分的数据？这个问题可以用程序的局部性原理解释，局部性原理是Cache能有效工作的理论依据

下图中程序A是个遍历二维数组的过程，这个程序运行时需要把代码翻译成二进制机器指令再放到内存里面，另外像数组还有各种各样的变量也需要被放到内存里面

假如现在访问了 $a [0] [0]$ 这个元素，那么在接下来一段时间内和 $a [0] [0]$ 这个元素相邻的元素很有可能紧接着被访问，这就是所谓的空间局部性

刚才看的是数组的数据，其实除了数据之外，指令的访问也存在空间局部性。因为这些程序最终肯定会被翻译成一条一条的机器指令，而这些机器指令在内存里也是顺序存放的，因此当访问某一条机器指令时，在不久的将来与这条机器指令相邻的其他机器指令也有可能紧接着被使用到

再看时间局部性，要理解时间局部性最典型的例子就是程序A里的这种循环结构。比如程序A中加法所对应的指令可能被存放在内存里的某一位置，当访问了这条加法指令之后，由于有这种循环结构的存在，在未来很短的时间内有可能会再次使用到加法所对应的指令

这就是空间局部性和时间局部性。空间局部性是因为指令和数据在内存里通常是顺序存储的，访问这些指令和数据时很多时候都是需要顺序地访问，这就导致了空间局部性。而时间局部性主要是因为程序里面会存在大量的循环结构，这就导致了时间局部性。除了对指令的访问具有时间局部性之外，对某一些数据的访问也具有时间局部性，比如对于变量 $i, j ， s u m$ ，这些变量因为循环结构的存在也很有可能在短时间内被重复地访问

基于程序执行的局部性原理，不难想到这样的策略，由于CPU当前访问的主存地址周围的那些数据很有可能在不久的未来就被使用，另外CPU当前访问的地址也有可能在未来被重复地访问，所以可以把CPU当前访问地址周围的部分数据复制一份放到Cache中，接下来CPU就可以直接从Cache里读取相应的数据

比如当访问这个数组时，如果此时CPU访问了 $a [0] [0]$ 这个元素，那完全可以制定一定的策略把 $a [0] [0]$ 之后的多个数组元素复制一份到Cache当中。这样接下来CPU想要访问这些数据时去Cache里面找就可以了，这样就可以大幅度提升CPU的运行速度

在实际当中可能程序B的实际运行时间要比程序A慢得多

接下来看一下增加了Cache之后整个系统的程序运行效率会提升多少

性能分析

还是以刚才微信的运行为例。直接见下图即可，此处详细讲解略过不记

有待解决的问题

对于Cache依然还有很多有待解决的问题

第一个问题直接见下图即可，此处详细讲解略过不记

此外还有一些问题留待接下来几节探讨。CPU会优先从Cache里面找数据，但如果Cache当中找不到，CPU又会到主存里面找数据，那么当CPU访问了主存的某一个存储单元之后一定会把这个存储单元所从属的一整块立即调入到Cache当中，注意这个过程只会把数据复制一份，并不会删除主存里的数据

现在问题产生了，访问的这些主存块有可能被放到Cache的每一个位置，那么应该如何记录主存块和Cache块之间的对应关系？CPU如何区分Cache数据和主存数据的对应关系？这个问题是下一小节学习的Cache和主存的映射方式要探讨和解决的问题

第二个问题，之前说过Cache的容量很小，而主存的容量一般要比Cache大得多，这就意味着只能把主存中的一小部分数据放到Cache当中。那么Cache满了之后应该怎么办？这个问题是下下小节当中替换算法要解决的问题

最后一个问题，主存里保存的数据被复制了一份到Cache当中，比如用美图秀秀P图时，图片数据有可能会被放到Cache当中，图片的数据是被复制了一份到Cache里面。当进行P图时CPU其实会优先更改Cache里面保存的数据，而Cache里的数据只是一个数据副本，真正的数据母本被保存在主存当中。那应该如何保证数据副本和数据母本之间的一致性？这也是后面的小节要解决的问题，也就是Cache的写策略所要探讨的问题

Cache和主存的映射方式

上一小节的末尾留下了几个问题，由于Cache保存的是主存里某些数据块的副本，那么如何区分Cache数据块与主存数据块之间的映射关系？这一小节要学习的Cache和主存的映射方式探讨的就是这个问题

本节内容直接见图即可，详细讲解略过不记

全相联映射（随意放）

“全相联映射“如何访存？

直接映射（只能放固定位置）

映射到相同位置会把之前存放的数据覆盖掉

可以进一步对标记进行优化

“直接映射”如何访存

组相联映射（可放到特定分组）

仿造直接映射的思路，同样可以对标记进行优化

“组相联映射”如何访存

Cache替换算法

本节学习Cache的替换算法，在之前的小节中留下了三个问题。上一个小节解决了第一个问题。第二个问题就是Cache很小，主存很大，但是每次被访问的主存块一定会被立即调入Cache，这就意味着Cache很容易被装满，当Cache装满之后应该怎么办？这就是替换算法要解决的问题

结合上一小节学习的这些地址映射方式，可知替换算法只会被用到全相联映射和组相联映射这两种方式。直接映射时不需要考虑替换算法。这一小节以全相联映射为例学习四种替换算法

随机算法（ RAND ）

假设总共有4个Cache块，并且刚开始所有的Cache块都是空的。所以刚开始访问1、2、3、4这几个主存块时都需要把这些主存块依次调入到Cache当中。1号主存块放到0号位置，2号主存块放到1号位置，接下来3、4号主存块也是类似地被放到Cache的相应位置。刚开始访问的这几个主存块都没有命中，每访问一个主存块就需要把这块的数据从主存调入到Cache。由于前边的这几次访问Cache都没有装满，所以不需要进行Cache替换

接下来要访问1号主存块，由于此时1号主存块已经被存放到Cache当中，所以这次的访问可以命中。接下来2号主存块也一样可以命中

要访问5号主存块时，由于此时4个Cache块当中存放的主存块分别是1、2、3、4号，5号主存块没有被调入Cache，而之前说过每访问一个主存块就一定要把这个主存块立即调入Cache，所以此时就需要根据Cache块的替换算法决定要替换哪一块。根据随机算法的规则可以随便选一个块进行替换，比如把3号主存块换出去换入5号主存块

对下表中后面步骤的详细讲解略过不记。接下来的几种方法也会记得简略些

先进先出算法（ FIFO ）

最先被调入Cache的块也有可能在之后会被频繁地访问到。比如C语言程序很有可能在刚开始就调用了printf函数，而这并不意味着往后就用不到这个函数了

近期最少使用算法（ LRU ）

做题时可以采取一种比较快的方法，当要替换一个Cache块时，从当前访问的这个主存块号位置往前看，看哪些主存块最近被访问过，从后往前看最后一个出现的主存块号就是应该被替换的主存块

如何用硬件实现近期最少使用算法的？上一小节说过每一个Cache行需要有一个标记用来记录这个Cache行里所存储的主存块号，另外还需要增加一个有效位，除了这些信息之外，如果要使用LRU算法，那么还必须给每一个Cache行添加一个计数器属性。刚开始所有的Cache行都是空的，计数器也会被全部置为0。计数器的编号规则见下图所示

后面步骤的具体说明略过不记

当然也可以同样地把3加1变成4，但是这样毫无意义，让它的值保留原本的3也可以达到同样的效果。因为设置计数器的目的是想通过计数器值的大小判断应该替换哪一个主存块，我们想要选择的是计数器值最大的一个Cache块并把它替换掉，3这个值本来就已经是最大的了，所以再让3加1没有意义。这种处理策略的好处是当只有4个Cache行时，4个计数器的值可能是0、1、2、3这几种情况

模拟机器执行要比手算麻烦一点，但是机器这样处理计数器是有好处的，刚才说过采用这样的策略可以保证所有这些计数器的值只有可能出现0、1、2、3这几种情况

当Cache块的总数为 $2^n$ 时，只需要 $n$ 个比特位作为计数器。比如这个例子当中只有4个Cache块，那么就只需要2bit的信息来表示计数器，2bit刚好可以表示0、1、2、3这几种数字。这样的策略保证了当用硬件实现替换算法时硬件电路的设计会更简单，只需要增加2bit的冗余信息

该算法的特点如下

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SYGKQyLX-1663675480182)( https://xdu-cslee-blog.oss-cn-hangzhou.aliyuncs.com/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86%E7%AC%94%E8%AE%B0%E5%9B%BE%E7%89%87/image-20210303122900238.png)]