计算机组成原理—

计算机组成原理——存储系统

存储器层次结构

存储器层次结构如下：

寄存器（CPU）
Cache（高速缓冲存储器）
主存
磁盘
磁带、光盘等

按照上述层次结构，自下而上速度依次增快、容量相对依次渐小、造价越来越高昂。

有的书上把计算机内部的磁盘统称为“辅存”，把U盘、光盘等成为外存。但是也有部分书籍将磁盘、U盘、光盘等统称为“辅村”或者“外存”。本文按照后者进行描述。

我们平常安装的应用程序一般是放在辅存中的，辅存容量大，但是读写较慢。如果CPU直接访问辅存的话，那么CPU就会被辅存的速度拖累，因此CPU想要运行应用程序，需要将辅存中的程序与数据放到内存中去才行。

主存中的数据被放到缓存中，CPU可以直接往缓存里写数据和读数据。虽然主存的速度已经很快了，但是相对于CPU来讲仍跟不上CPU的速度，为了解决主存与CPU之间速度的矛盾就在二者之间增加了缓存。

主存与辅存之间实现了虚拟存储系统以解决主存容量不够的方式。（参考OS）

存储器分类

按照存储介质分类：

半导体存储器：以半导体器件存储信息（主存、Cache等）
磁表面存储器：以磁性材料存储信息（磁盘、磁带等）
光存储器：以光介质存储信息（光盘等）

按存取方式分类：

随机存取存储器（Random Access Memory，RAM）：读写任何一个存储单元所需的时间都几乎相同，与存储单元所在的物理位置无关。
顺序存取存储器（Sequential Access Memory， SAM）：读写一个存储单元所需时间取决于存储单元所在的物理位置。
直接存取存储器（Direct Access Memory，DAM）：既有随机存取的特性，也有顺序存取的特性。先直接选取信息所在区域，然后按顺序方式存取。

其中SAM和DAM统称为串行访问存储器，即读写某个存储单元所需的时间与存储单元的物理位置有关。

还有一种叫做相联存储器（Associative Memory），即可以按照内容访问的存储器（Content Addressed Memory， CAM）。如硬件实现的快表（TLB）就是一种CAM。

按照信息可更改性分类：

读写存储器（Read/Write Memory）：可读也可写，如内存、磁盘等。
只读存储器（Read Only Memory）：只能读不能写，如实体音乐专辑使用的CD-ROM。BIOS通常写在ROM中。

按照信息等可保存性：

易失性存储器：断电后存储信息消失的存储器。（内存、Cache等）
非易失性存储器：断电后存储信息依然保持的存储器。（磁盘、光盘）

信息读出有两种：

破坏性读出：信息读出后，原来的存储信息被破坏（如DRAM芯片，读出数据后要重写）
非破坏性读出：信息读出后，原来等存储信息不被破坏（如SRAM芯片、磁盘、光盘等）

存储器性能指标

存储容量：存储字数*存储字长

单位成本：每位价格=总成本/总容量

存储速度：传输速率=数据的宽度/存储周期

数据的宽度即存储字长。

存储周期又称为读写周期读写周期或访问周期，它是存储器进行一次完整的读写操作所需的全部时间，即连续两次独立地访问存储器操作（读或写）之间所需的最小时间间隔，可以划分为存取时间和恢复时间。

存取时间是指从启动一次存储器操作到完成该操作所经历的时间，分为读出时间和写入时间。

主存带宽又称数据传输率，表示每秒从主存进出信息的最大数量，单位为字/秒、字节/秒、位/秒等。

主存储器的基本组成与原理

主存基本的半导体元件与原理

在前面我们提到过主存储器分为存储体、MAR、MDR，三者在时序控制逻辑电路的协调下配合工作。

存储体中包含若干个存储单元，每个存储单元的每一位实际上是由存储元这个电子元件来保存的。存储元包含一个电容和一个MOS管，每个存储元可以存放一个二进制位的0或1。

MOS管可以理解为是一种电控开关，输入电压达到某个阀值的时候，MOS管就可以接通。

存储器的读写的基本大小之所以是以存储字长为单位的，是因为MOS管的一端接在了同一条线上。

主存存储芯片的基本原理

MAR连接地址总线和译码器，给定n位地址对应 $2^{n}$ 个存储单元，译码器输出端就有 $2^{n}$ 个字选线。

若CPU给定的地址n位全为0到MAR中，译码器会将地址对应的第0根字选线一个高电平输出，由于该行存储元的MOS管同一级都连接到该线上，因此本行存储元都会被选通，与MOS相连的另一端，也就是每一列的数据线（位线）就可以输出该存储字的每一位二进制数据，每一列的位线与MDR相连接，MDR输出端与数据总线相连接，这样CPU就能够通过数据总线拿到MDR里寄存的数据了。

由此可见，数据总线的宽度与存储字长是相等的。

此外我们还需要一个控制电路来控制译码器、MAR、MDR。由于我们采用电信号传输方式，因此CPU给出的地址到MAR未稳定之前，其地址信息是不能够到译码器中的。当数据输出的时候，只有当数据到MDR稳定之后，才能从数据总线送出数据。这一系列的操作都是要通过控制电路来完成。

控制电路输入端分别是片选线、读控制线、写控制线。

片选线通常是低电平有效，此时说明该芯片可以工作。如果我们只想要存储器上某块芯片可以工作而其他芯片不工作，我们只需要给这个芯片的片选线加一个低电平，而其他芯片的片选线都是高电平就行了。

有的控制电路用读写线分为两根（如上图），当读控制线为低电平的时候允许读，当写控制线为低电平的时候允许写；当然有些电路采用一根读/写线，低电平表示写，高电平表示读。（读写线的个数会影响暴露的引脚数）

还有些存储器会在译码器后面添加一个驱动器，这个驱动器用于保证译码器输出的电信号是稳定可靠的。

我们经常会看到对于某个存储芯片的描述是8K*8位的，8K是指存储单元的个数，也就是有 $2^{13}$ 个存储单元，8位是指存储字长。

若存储器总容量为1KB，地址线总共有10根，则按照以下编址方式：

按字节寻址：总共 $2^{10}$ 个单元，每个单元1Byte
按字寻址：总共256个单元，每个单元4Byte
按半字寻址：512个单元，每个单元2Byte
按双字寻址：128个单元，每个单元8Byte

如果按字寻址，我们只需要把4个字节合并，只需要把字地址算术左移两位换成与之对应的字节地址。

DRAM和SRAM

动态RAM（Dynamic Random Access Memory，DRAM），用于主存。（当然，DRAM已经过时了，现在的主存通常使用SDRAM。）

静态RAM（Static Random Access Memory，SRAM），用于Cache。

DRAM使用栅极电容存储信息，SRAN使用双稳态触发器存储信息。

DRAM的栅极电容如果给字选择线相连的MOS管引脚添加一个5V的电压，MOS管就会被导通，如果此时MOS管另一端也就是连接数据线的那一侧同样有一个5V的电压，这样栅极电容一侧就会带5V的电压，另一侧由于接地带0V电压，这样就完成了一个二进制1的存储。如果数据线输入0V低电平信号，则MOS管被导通后，栅极电容金属板两侧的电压都是0V，电容内未储存电荷，这样就存储了一个二进制0。

若要读出栅极电容中的数据，只需要给字选择线加一个高电平，MOS管导通，若栅极电容存储电荷，数据线上就会产生电流，此时表示读出1；若栅极电容未存储电荷，则数据线上就无电流表示读出0。

SRAM的存储元是双稳态触发器。双稳态触发器中包含6个MOS管，分别用M1到M6标注。双稳态触发器可以存储两种稳定状态，第一种状态为1，A点高电平，B点低电平；如果A点低电平，B点高电平则存储0。

对于双稳态触发器，如果存储的是一个1，若给字选择线加一个5V的高电平，BLX这条线会输出一个低电平信号，读出1；如果存放的是0，左侧的BL线会输出一个低电平信号读出0。

我们来比较下两种元件。对于DRAM的栅极电容来说，电容放电信息被破坏，是破坏性读出。读出后应有重写操作，也称再生；对于SRAM的双稳态触发器，读出数据，触发器状态保持稳定，是非破坏性读出，无需重写。

DRAM存储元每个存储元件制造成本低，集成度高；而SRAM每个存储元成本更高，集成度低。

由于栅极电容内的电荷长期存放会流失，存放的信息也就有可能存在误差，因此只能维持2ms，2ms后即使不断电也会消失，2ms之后需要进行刷新。而对于双稳态触发器，如果一直给VDD维持一个5V的电压，只要不断电双稳态触发器的数据就不会丢失。

DRAM的刷新

DRAM刷新周期一般为2ms，以行为单位，每次刷新一行存储元。

如果DRAM不采用行列地址的方式，每一根选通线分别与一个存储单元相连，译码器输出端就会随着地址位数增加而以2的幂指数的方式递增。这种情况下，如果有n位地址，则译码器就要连接 $2^{n}$ 个选通线，这显然是不能接受的。

因此，DRAM采用行列编址方式，每次刷新以行为单位，刷新一行的存储单元。

DRAM的刷新方式有硬件支持，存储器独立完成，不需要CPU控制，读出一行信息后重新写入，占用一个读写周期。

假设DRAM内部结构排列为128*128，存取周期（读/写周期）0.5微秒：

思路一：每次读写完后都刷新一行，系统的存取周期变1微秒，前0.5微秒用于读，后0.5微秒用于写。2ms内可以刷新2000次，足以刷新128行。这种刷新方式叫做分散刷新。
思路二：2ms内集中安排某段时间进行刷新，这种方式叫做集中刷新。由于有一段时间是刷新专用的，这段时间无法访问存储器，称为访存死区。此时系统存取周期与存储器一致为0.5微秒，其中2ms尾部有128周期（64微秒）用于刷新，其他时间（3872个周期，1936微秒）用于读写。
思路三：2ms被128行分成128段时间，每个时间间隔2ms/128=15.6微秒，由于存取周期0.5微秒，也就是说每个15.6微秒内有0.5微秒的死时间用于刷新不能访存，这种刷新方式叫做异步刷新。这些死时间往往是在CPU不需要访存（译码）阶段。

DRAM地址线复用技术

对于DRAM，正常情况下有n位地址，就需要n位地址线。为了节省成本，我们可以使用地址线复用技术，将地址拆分成行地址和列地址。这样在使用的时候，我们只需要将行地址和列地址分两次进行传输。

第一次发送行地址，行地址会被送往行地址缓冲器里；第二次发送列地址，列地址会被送往列地址缓冲器中。然后会分别送往行地址译码器和列地址译码器。此时最少只需要 $\frac{n}{2}$ 条地址线即可（芯片引脚数量也相对减少了）。

DRAM地址线复用技术

ROM种类

掩模式只读存储器（Mask Read-Only Memory，MROM），厂家按照客户需求，在新品生产过程中直接写入信息，之后任何人都不可以重写，只能被读出。可靠性高、灵活性差、生产周期长，只适合批量定制。

可编程只读存储器（Programmable Read-Only Memory，PROM），用户可用专门的PROM写入器写入信息，写一次后就不可以更改。灵活性相对MROM增加，写一次后就不可更改。

可擦除可编程只读存储器（Erasable Programmable Read-Only Memory，EPROM），允许用户写入信息，之后某种方法擦除数据，可进行多次重写。

此外还有UVEPROM，这种ROM通常用紫外线照射8到20分钟就可以擦除所有信息。EEPROM，使用电擦除的方式擦除特定的字。

**闪存（Flash Memory）**在EEPROM的基础上发展而来，断电后也可以保存信息，而且可以进行多次快速擦除重写。闪存需要先删除再重写，因此闪存写的速度比读要慢。（部分U盘、SD卡就是闪存）

固态硬盘（Solid State Drives，SSD），由控制单元和存储单元组成，存储单元主要是Flash芯片，与闪速存储器的核心区别在于控制单元不一样，但存储介质都类似，可进行多次快速擦除重写。SSD速度快功耗低，但是价格相对较高（然而按照现在的行情某些SSD价格已经近乎机械硬盘甚至低于机械硬盘了）。

在现在的智能手机中经常会看到ROM，通常是指手机的辅存，使用Flash芯片但是相比SSD的芯片集成度更高、功耗低而且价格贵。

计算机中的重要ROM

对于计算机，其操作系统是安装在辅存或者说外存中的。

计算机开机时主存中是没有指令的，CPU需要到主板上的一块ROM芯片中获取BIOS程序。BIOS中包含ROM引导程序即自举程序。

自举程序会把磁盘主引导记录分区MBR中的主引导记录读如到RAM里，主引导记录包含分区表和磁盘引导程序，分区表用于判断活动分区也就是安装了OS的分区，读如这个分区头部的引导记录PBR到RAM中，PBR负责找到根目录的启动管理程序，这个启动管理程序会负责初始化系统完成开机动作。

（注意，计算机主存严格的说法应该是RAM加上这块ROM）

主存速度提升

DRAM芯片恢复时间比较长，有可能是存取时间的好几倍，CPU读写速度比主存快很多，主存恢复时间太长。此外，还有如果CPU为多核，多核都要放存等问题。

解决多核CPU放存等问题可以用双口RAM，主存恢复时间太长可以用多模块存储器。

多模块存储器可以分为多体并行存储器和单体并行存储器。

双端口RAM

使用双端口RAM可以优化多核CPU访问一根内存条的速度。使用双端口RAM意味着需要有两组完全独立的数据线、地址线、控制线。CPU、RAM中也需要有更复杂的控制电路。

两个端口对同一主存操作有以下四种情况：

两个端口同时对不同的地址单元存取数据
两个端口同时对同一地址单元读出数据
两个端口同时对同一地址单元写入数据
两个端口同时对同一地址单元，一个写入数据，一个读出数据

前两种情况不会发生冲突，但是对于两个端口同时写同一个地址单元或者一读一写，就会发生竞争，后两种情况应当被禁止。

当发生后两种情况的时候，RAM里的控制电路应向两个CPU发送忙信号，同时CPU应当有逻辑电路来根据忙信号决定暂时关闭一个端口（即被延时），未被关闭的端口正常访问，被关闭的端口延长一个很短的时间再访问。

实际上就是在硬件层面解决读写者问题，了解过操作系统的应该很熟悉。

多体并行存储器

为了解决CPU与主存之间速度不一致的问题，我们可以采用多体并行存储器，即每个存储器它们都是独立工作的（可以想像主板上插了多个内存条）。多体并行存储器有两种编址方式：

高位交叉编址的多体存储器
低位交叉编址的多体存储器

高位交叉编址的多体存储器在高位设置几个比特位来标志访问哪一个存储器，而采用低位交叉编址的多体存储器在低位设置几个比特位来标志访问哪一个存储器。

我们假设每个存储器有8个存储单元，存取周期为T，存取时间为r，假设T=4r，也就是说CPU存取一个数据要r时间，但是要再次存取同一存储器，恢复时间为3r。现在我们来连续访问00000到00100五个地址。

先来看采用高位交叉编址的情况：CPU读取M0存储器的一个地址后花费时间为r，假设该地址为00000，读取下一个地址00001，由于采用高位编址，前两个比特位表示存储器，也就是说00001这个地址仍在M0存储器内，CPU需要再等待3r的时间才存取这个地址。按照这种方式分析，连续访问00000到00100五个地址要经历5T时间。

然后再来看低位交叉编址到情况：CPU读取00000地址花费时间为r，下一个地址为00001，但是采用低位编址的方式，00001在存储器M1，于是就不必再等待M0恢复后进行读取了，CPU可以立刻访问M1存储器。同理，访问完00011之后，已经经过了4r的时间，此时要访问的最后一个地址00100在存储器M0中，而M0已经恢复完毕，可以立即访问。由此可见采用这种编址方式，所花费的时间相对较短。

细心可以发现，上面给出的数据特别巧妙，因为采用低位编址，T=4r可以使CPU访问一轮过后正好可以访问M0存储器。现在我们来讨论一般情况，若存取周期为T，存取时间为r，为了能够不间断访问，存储器的数目m应该遵循以下规律：

$m\ge{\frac{T}{r}}$

单体多字存储器

与多体并行存储器相对的是单体多字存储器。

在前面我们提到过多体并行存储器每个模块都有独立的控制电路、地址寄存器、数据寄存器。

而单体多字存储器则相反，它把多个模块集成到了一块，用一套控制电路进行控制，每个存储单元存储m个字，总线宽度也是m个字，一次并行读出m个字，不能单独读取其中的某个字，指令和数据在主存内必须是连续存放的。

也就是说在读取的时候可能会伴随着与当前操作无关的数据。这就导致了单体多字存储器的灵活性相对变差了许多，但是性能并不一定比多体并行存储器好。

单体多字存储器

我们假设多体并行存储器遵循低位交叉编址，而且存储器的数目足够可以使CPU能够不间断地进行访问，假设存取周期T=4r，r为存取时间，对于多体并行存储器（有4个独立模块）平均读取时间为r，而对于单体多字存储器，一次也就读取4个字，平均读取时间也是r。

但是无论是单体多字存储器还是多体并行存储器都可以极大提升CPU访问内存的效率。

双通道内存

在平时使用计算机的时候，我们购买主办和内存条经常会提到双通道内存，如果有4个内存条插槽，两个内存条插入的方式通常为1，3或2，4。这种实际上就是实现了低位交叉编址多体存储器，相比于1，2插法，可以让内存吞吐量几乎翻倍（连续访问的情况）。而1，2这种插入顺序是高位交叉编址。

X670e Hero

（图片中的主板是X670e Hero）

主存储器与CPU的连接

现代计算机连接方式

现在的计算机MAR与MDR通常是集成在CPU内，而不是存储器内部。MDR的数据是通过数据总线与内存交换，而MAR是通过地址总线发送给内存。

主存扩展

在某些条件下我们需要增加存储字长，可以有以下几种方式。在此之前我们来约定下表示：

WE或WR表示读/写线，上面有横线表示低电平有效没有则高电平有效下同理
$A_i$ 表示地址总线的i号线
$D_i$ 表示数据总线的i号线
CS表示片选线

位扩展

我们假设主存规格为8K*1位，也就是存储字长1bit，一共 $2^{13}$ 个存储单元。现在我们的地址总线为16位，而数据总线为8位，数据总线的利用是不够充分的。为了解决这个问题，我们可以多增加几块规格的芯片，将存储字长扩展到8bit。

字扩展

字扩展用于有多余的地址线未利用。

扩展多个芯片将多余的地址线连接到存储芯片的片选线引脚上，多个芯片的数据线引脚都连接到数据总线上。这种方式多个存储芯片不能同时工作，连接片选线引脚的地址线（假设高电平有效）不能同时为1，否则会冲突。这种字扩展的方法叫做线选法。

如上图 $A_{13}$ 与 $A_{14}$ 不能同时为1，第一个存储芯片地址最高两位都是01，第二块都是10。

为了解决这种问题我们对线选法进行优化：将两块芯片的片选线引脚都接到 $A_{13}$ 上去，然后给其中一个分支接一个非门。

经过这种改造后整个存储器的地址空间就连续了。

还有一种方式叫做译码片选法，我们有 $A_{13}$ 到 $A_{15}$ 三根地址线未被利用，可以连接一个3-8译码器，译码器输出端有8个引脚，于是就可以输出 $2^8$ 个片选信号。

使用译码片选法，若有n条线，可以输出 $2^n$ 个片选信号。如下图所示，我们使用了2根地址线，接了一个2-4译码器。

字位同时扩展

字扩展和位扩展可以同时使用。

外部存储器

外部存储器又称为辅助存储器，既可以作为输入设备又可以作为输出设备。

磁表面存储器

概念与原理

磁表面存储，是在金属铝或者塑料表面上涂装一层磁性材料薄层作为磁载体来存储信息。

磁表面存储器通常使用一个围绕着线圈的U型铁芯作为磁头，很显然磁头是一个电磁铁，通过给线圈所通电流方向不同来改变磁头产生的磁场的方向。磁载体上的磁层会由于磁场方向不同而产生一定的移动和变化。

我们可以根据发生变化的部分磁层南北极来规定0还是1。

磁盘存储器、磁带存储器和磁鼓存储器均属于磁表面存储器。

磁表面存储器有如下优点：

存储容量大，价格低
记录介质可以重复使用
记录信息可以长期保存不丢失，甚至可以脱机存档
非破坏性读出，读出不需要再生

磁表面存储器缺点：

存取速度慢
机械结构复杂
对工作环境要求较高

磁盘存储器

目前主流的磁表面存储器是磁盘存储器，也就是平时提到的机械硬盘。

一块磁盘通常由外壳、磁头、磁臂、盘片、驱动轴以及电路板组成。（或者说由磁盘驱动器、磁盘控制器和盘片组成）

磁盘驱动器：核心部件是磁头和盘片组件，温彻斯特盘是一种可移动头固定盘片的存储器。

磁盘控制器：是硬盘存储器和主机的接口，主流标准有IDE、SCSI、SATA。（IDE在现代硬件设备上已经不常见了，SCSI现在在一些服务器上可能会见到，目前家用设备磁盘的接口通常是SATA）

一块硬盘有若干个记录面（盘面），通常情况下盘片有两面（两个盘面）被涂满磁性材质可以用于存储，每个记录面可以划分为多个磁道，每条磁道又划分为多个扇区（也称块），扇区是磁盘读写的最小单位，也就是说磁盘按块存取。驱动轴会带动盘片旋转以实现访问不同扇区。

磁头分为两种：一种是固定磁头，即每个磁道上都有一个对应的磁头，磁臂不能移动。另一种经常见到的是每个盘面只有一个磁头，磁臂带动磁头伸缩以切换不同的磁道，这种情况下磁头数等于盘面数。

在一个盘组中，不同记录面的相同位置的磁道构成的圆柱面叫做柱面。柱面数表示了一个盘面有多少磁道。

衡量磁盘性能的指标通常为以下几种：

磁盘容量：一个磁盘所能存储的总字节数。磁盘容量有格式化容量和和非格式化容量之分。非格式化容量是指磁记录表面可以利用的磁化单元的总数；格式化容量是按照某种特定的记录格式所能存储信息的总量（格式化后某些扇区会设为备用或者其他用途）。
记录密度：即盘片单位面积记录的二进制信息量，通常以道密度、位密度和面密度表示。**磁盘所有磁道记录信息量是相同的，并不是圆越大越多，每个磁道的位密度不一样。**面密度是道密度与位密度的乘积。
平均存取时间：寻道时间（磁头移动到目的磁道）+旋转延迟时间（磁头定位所在扇区）+传输时间（传输数据花费的时间）

主机向磁盘控制器发送寻址信息，磁盘的地址一般如图所示：

一台电脑可能有多个硬盘，驱动器号用于选择磁盘。
柱面号用于移动磁臂寻道
盘面号用于选择激活哪个磁头
扇区号用于旋转将特定扇区划过磁头下方

磁盘的主要操作是寻址、读盘、写盘。每个操作都对应一个控制字，硬盘工作时，第一步是取控制字，第二步是执行控制字。

磁盘属于机械式部件，其读写操作是串行的，不可能在同一时刻即读又写，也不可能在同一时刻读两组数据或写两组数据。读和写是一比特一比特地进行，主机给磁盘发送的数据可能是并行发送的，对于磁盘需要一个并-串变换电路。

固态硬盘

SSD结构

固态硬盘（Solid State Disk，SSD）基于闪存技术，属于EEPROM。

SSD由闪存翻译层和存储介质组成。闪存翻译层负责翻译逻辑块号，找到对应页。存储介质包含多个闪存芯片，每个芯片包含多个块，每个块包含多个页。

SSD读写以页为单位，相当于磁盘的扇区。另外，SSD以块为单位擦除，擦干净的块中每一页都可以写一次，读无限次。并且SSD支持随机访问，系统给定一个逻辑地址，闪存翻译层可通过电路迅速定位到对应的物理地址。

SSD通常读速度快、写速度慢，随机访问性能高，用电路控制访问位置。相比于机械硬盘通关旋转磁盘和移动磁臂，SSD没有寻道时间和旋转延迟，并且SSD安静无噪音、抗震耐摔，造价相对较贵。

SSD多次擦除同一个块（重复写同一个块）可能会坏掉，而机械硬盘不会如此。

磨损均衡技术

磨损均衡技术通过将擦除平均分布在各个块上以提升使用寿命。

磨损均衡技术通常分为两种：

动态磨损均衡：写入数据时，优先选择累计擦除次数少的闪存块。
静态磨损均衡：SSD检测并自动进行数据分配、迁移，让老旧的块承担以读为主的存储任务，让较新的块承担更多写任务。

磁盘冗余阵列

**廉价冗余磁盘阵列（Redundant Array of Inexpensive Disks）**是将多个独立的物理磁盘组成一个独立的逻辑盘，数据在多个物理盘上分割交叉存储、并行访问，具有更好的存储性能、可靠性和安全性。

RAID分级如下所示：

RAID0:无冗余和无校验磁盘阵列
RAID1:镜像磁盘阵列
RAID2:采用纠错的海明码的磁盘阵列
RAID3:位交叉奇偶校验的磁盘阵列
RAID4:块交叉奇偶校验的磁盘阵列
RAID5:无独立校验的奇偶校验磁盘阵列

Cache的基本组成与基本原理

存储系统存在的问题

即使双端RAM和多模块存储器可以提高存储器工作速度，但是CPU与主存速度差距仍然很大，于是需要在二者之间设计一层缓存来缓解二者的速度矛盾。

Cache工作原理

应用程序的某些功能模块的指令会首先加载到内存中，CPU可能会频繁地执行某些指令，这些指令就可以被复制到Cache中来提高效率。

在现在的计算机中，Cache被集成在CPU内部使用SRAM实现，成本高但速度快。

局部性原理与分块数据交换

空间局部性原理：在最近的未来要用到的信息（数据和指令）很可能与现在正在使用的信息在存储空间上是邻近的。

时间局部性原理：在最近未来要用的某些信息，很可能是现在正在使用的信息。

基于局部性原理，可以把CPU目前访问地址周围的部分数据和指令放到Cache中。为了界定周围这个概念，我们可以将主存分块，如每1KB为一块，主存与Cache之间以块为单位进行数据交换。

在OS中，通常采用分页存储管理，主存中的一个块也被称为页框，Cache中的块被称为行。

如果CPU访问的数据在Cache，我们就称这为缓存命中，如果不在则称缺失。

设 $t_c$ 访问Cache一次所需时间， $t_m$ 是访问主存一次所需的时间。

命中率 $H$ 为CPU想要访问的信息在Cache中的比率。缺失率 $M = 1 - H$ 。

那么Cache-主存系统的平均访问时间t为：
$t = Ht_c+(1-H)(t_c+t_m) = Ht_c+(1-H)t_m$

很显然当缓存命中的时候直接从Cache取即可，当没有命中时还需要额外访问内存获取信息。

Cache与主存映射方式

前提

Cache与主存有三种映射方式：

全相联映射
直接映射
组相联映射

为了区分Cache中是存放的哪个主存块，我们可以设置标记来记录对应的主存块号。此外光有记录还不够，因为记录初始值全为0，这就意味着没有保存主存信息的行与保存主存块号为0的行是一样的，因此我们还需要设置一个有效位。

假设某个计算机主存地址空间大小为256MB，按字节编址，其数据Cache有8个Cache行，行长64B（也就是说Cache大小为512B，每个Cache行与主存块相等）。

主存的地址共28位，主存块号占22位，块内地址占6位。

全相联映射

若采用全相联映射，存放相对随意，只需要将主存块复制到Cache行中，并记录主存块号和设置有效位为1即可。

全相联映射

CPU想要访问，首先会根据主存地址的前22位与所有记录条目的标记对比，若匹配有效且有效位为1，则缓存命中，访问块内地址（即主存地址的后六位，就是一个便宜量，缓存命中时直接从当前缓存行的起始位置偏移）。

若未命中或有效位为0，则正常访问主存。

直接映射

直接映射存放的位置相对固定，设主存块在Cache中的位置为 $P$ ，主存块号为 $n_M$ ，Cache总块数为 $N_c$ ，则由如下关系：

$n_M \bmod N_c$

但是采用直接映射有一个缺点：可能存在两个相同的主存块放到同一个Cache行中，这时候后来者就必须覆盖前者，即使有其他空闲的Cache行。

我们仍以前提中的条件为例，块号为0的主存块按照上述公式进行直接映射，存放的缓存行号为0，此时标记记录主存块的地址，有效位设为1。但是对于8号主存块来讲，按照上述公式存放的缓存行号仍为0。

若Cache总块数为 $2^{n}$ 相当于留下最后的n位二进制数，则主存块号末尾n位直接反应它在Cache中的位置，也就是说我们的标记只需要存这n位以外的二进制位即可。

例如Cache总块数为 $2^3$ 个，主存块号22位，则记录只需要存22-3=19位。

于是优化后的直接映射CPU访问步骤就变成了：

CPU根据主存块号的后三位确定Cache行
若主存块号前19位与Cache标记匹配且有效位为1则缓存命中
若未命中则访问内存

组相联映射

设所属分组为 $G$ ，主存块号 $n_M$ ，分组数为 $M$ ，则组相联映射有如下关系

$n_M \bmod M$

我们采用2路组相联映射，按照前提中提到的条件，2块为一组，总共可以分4组。

那么以1号主存块为例，则可以放到第一组，第一组内任何一个空闲的位置都可以放入。

组相联映射

组相联映射同样可以像直接映射那样优化，我们假设分组数为 $2^{n}$ ，那么模上这个数相当于右移n位，也就是说我们只需要在记录里存放这n位以外的二进制位即可。

以组数为4为例，主存块号22位，则记录只保存主存块号的高20位即可。

CPU访问步骤就成了：

根据地址的主存块号后两位判断分组
在这个分组中对比前20位，若记录匹配且有效位为1则缓存命中
若未命中则访问内存

Cache替换算法

分析

Cache容量对比主存来讲比较小，也就是说Cache容易被装满，在某些情况下需要将Cache某行的内容替换掉，因此需要设计Cache替换算法来完成这一操作。

对于全相联映射，只需要Cache满了之后才需要决定替换哪一块；而直接映射，如果对应位置非空，则毫无选择地直接替换；对于组相连映射，只有分组内满了，才需要判断分组内替换哪一块。

因此替换算法会用在组相联映射和全相联映射，直接映射无需考虑替换算法。

我们下面以全相联映射为例，因为组相联可以视为一种受到限制的全相联映射。

随机算法（RAND）

随机算法RAND很简单，若Cache已经满了，则随机选取一块替换。

这种算法实现简单，但完全没考虑局部性原理，实际运行不稳定，命中率低。

先进先出算法（FIFO）

学过OS的应该很熟悉，FIFO原则就是若Cache已满，则替换最先被调入的Cache块。

FIFO算法

实际上就是一个队列，实现很简单，但依然没考虑局部性原理，最先被掉入的块也有可能是被频繁访问的。

近期最少使用算法（LRU）

LRU为每个Cache行设置一个计数器，用于记录每个Cache行多久没有被访问了，当Cache满后替换计数器最大的。

命中时，所命中的行的计数器清零，比其低的计数器加1，其余不变
未命中且还有空闲，新装入的行计数器置为0，其余非空闲行全加1
未命中时且无空闲行，计数值最大的行信息块被淘汰，新装入的行计数器置为0，其他全加1

LRU算法

LRU基于局部性原理，近期访问过的主存块将来也很有可能被访问，而且实际运行效果很优秀，Cache命中率高。但是当频繁被访问的主存块大于Cache行数的时候，容易发生抖动现象。

抖动又被叫做颠簸，是指块来回被换入、换出。

最不经常使用算法（LFU）

LFU为每一个Cache行设置一个几乎起，用于记录每个Cache行被访问过几次，当Cache满后替换计数器最小的行。

新调入的块计数器为0，每次被访问计数器加1，需要替换的时候选择计数器最小的一行。

若有多个计数器最小的行，则可按行号递增或者FIFO策略进行选择。

LFU算法

对于LFU算法，曾经被访问的块在未来未必会用到（如微信视频聊天相关的块），并没有很好的遵循局部性原理，实际运行效果不如LRU。

Cache写策略

、

分析

在前面我们提到过Cache保存的只是主存的副本，若CPU修改了Cache的信息，如何确保主存与Cache的一致性？

这就需要Cache的写策略。因为对于读来讲，无论是否命中都不会影响信息的一致性。

Cache写策略分两种情况，一种是写命中，另一种是写不命中。其中，写命中分为全写法和写回法；写不命中分为写分配法和非写分配法。

写命中

写回法(write-back)

当CPU对Cache写命中时，只修改Cache内容，而不立即写入主存，只有此块被换出的时候才写回主存。

为了让硬件能够区分哪些Cache行被修改过，需要增加一个脏位来标志，若为1则被修改过，若为0则未被修改。

当Cache行的信息被写回主存时，可以根据标记中的信息来定位写回的位置。

写回法

这种方法减少了访存的次数，但仍存在数据不一致的隐患。

全写法（写直通法，write-through）

当CPU对Cache写命中时，必须把数据同时写入Cache和主存，一般使用写缓冲（write buffer）

CPU在修改信息后，会把当前块写入的写缓冲里，写缓冲用SRAM实现FIFO队列，在CPU干其他事情的时间，会有一个专门的控制电路逐一将缓冲区的信息写回主存。

使用写缓冲，CPU写速度很快，若写操作不频繁则效果很好，但是若写操作频繁，可能会因为写缓冲饱和而发生阻塞。

全写法

写不命中

写分配法（write-allocate）

当CPU对Cache写不命中时，把主存的块调入Cache，在Cache中修改，通常搭配写回法使用。

非写分配法（not-write-allocate）

当CPU对Cache写不命中时，只写入主存，不掉入Cache。搭配全写法使用。

多级Cache

现代计算机常采用多级Cache，离CPU越近速度越快，容量越小，离CPU越远速度越慢，容量越大。

常见的CPU通常有L1缓存和L2缓存，某些CPU可能有L3等缓存。（例如AMD 5800x与5800x3d，后者就有较大的L3缓存对游戏比较友好）

低级的缓存通常是高级缓存的副本，最高级缓存是主存的副本。

缓存一致性问题

总线嗅探

现在的CPU都是多核的，由于L1/L2 Cache是多个核心各自独有的，那么会带来多核心缓存一致性问题。

必然我们对同一个变量进行加1，如果使用写回法，先修改缓存行，再标记脏位，由于内存是没有被同步数据的，只有当这个行被替换的时候才会写入主存。

此时如果另一个核心尝试从内存读取变量的值，读到的将会是错误的值，毕竟上面所说的核心还没有把块写回到主存。

解决这一问题有两种方法：

写传播（Write Propagation）：某个CPU核心Cache数据更新的时候，必须要传播到其他核心的Cache
事务的串行化（Transaction Serialization）：某个CPU核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的

写传播最常见的实现方式就是总线嗅探（Bus Snooping），每个CPU核心都要时刻监听总线的广播事件，并检查是否有相同的数据在自己的L1缓存里，如果其他核心缓存有而本核心没有，则需要将缓存的数据更新到本核心的缓存中。

CPU需要监听总线上的一切活动，但是不管别的核心的Cache是否缓存了相同的数据，都要发出一个广播事件，存在一定的开销，而且不能保证事务事件的串行化。

于是有了MESI协议。

MESI

MESI协议使用了状态机降低总线带宽压力，其名称就是4个状态的首字母缩写：

Modified——已修改
Exclusive——独占
Shared——共享
Invalidated——已失效

Modified实际上就是脏标记，表示Cache中更新过但未被写回内存。

Invalidated表示当前缓存行的信息已经失效了，不可以读取该状态的数据。

Shared表示信息与主存是一致的，并且此信息在多个CPU核心里都有，请求更新的时候不能直接修改，要先在事件总线上广播一个请求，要求其他核心将存放该信息的缓存行标记为Invalidated。

Exclusive表示信息尽在当前核心缓存中，并且与主存保持一致。

以下内容来自维基百科

处理器对缓存的请求:

PrRd: 处理器请求读一个缓存块
PrWr: 处理器请求写一个缓存块

总线对缓存的请求:

BusRd: 窥探器请求指出其他处理器请求读一个缓存块
BusRdX: 窥探器请求指出其他处理器请求写一个该处理器不拥有的缓存块
BusUpgr: 窥探器请求指出其他处理器请求写一个该处理器拥有的缓存块
Flush: 窥探器请求指出请求回写整个缓存到主存
FlushOpt: 窥探器请求指出整个缓存块被发到总线以发送给另外一个处理器（缓存到缓存的复制）

下图为处理器操作带来的状态变化：

处理器操作带来的状态变化

下图为不同总线操作带来的状态变化：

不同总线操作带来的状态变化

写操作仅在缓存行是已修改或独占状态时可自由执行。如果在共享状态，其他缓存都要先把该缓存行置为无效，这种广播操作称作Request For Ownership (RFO).

缓存对已修改状态的缓存行，要监听各处理器对其的读请求并插入其数据到总线。

缓存对共享状态的缓存行，要监听使其无效或请求拥有的广播，当匹配时把该缓存行置为无效。

已修改状态、独占状态是精确的，匹配于该缓存行在系统中的实际情况。共享状态可以是不精确的: 如果别的缓存抛弃了该行，只有当前缓存拥有该行，但其状态没有变为独占。其他缓存不需要广播通知其抛弃操作。

独占状态是一个优化机会：处理器修改共享状态的缓存行必须要先发出一个总线事务使得其他缓存中的该行失效；而独占状态下修改一行不需要总线事务。

上图中红色为总线初始化事务，蓝色为处理器初始化事务。