章节一览

计算机组成原理知识点比较多,所以分多部分复习。本篇是第二部分,复习存储器的分层体系结构,主要是Cache—主存层次。

计算机系统概述

数据的表示和运算

指令系统

中央处理器(重点)

存储的分层体系结构(重点)

互联及输入输出设备


存储系统

存储器的分类?

  1. 按照存储器在计算机中的层次化结构(三级存储系统)分类:

    image-20220609101450639

    从下到上,分别是外存、辅存、主存、高速缓存和寄存器(在CPU中)。规律是速度越来越快,容量越来越小,成本越来越高。其中能和CPU直接交换信息的有Cache和主存。存储系统的两个主要层次:

    1. “Cache—主存”层次:主要解决CPU和主存速度不匹配的问题。
    2. “主存—辅存”层次:实现虚拟内存,主要解决主存容量不够的问题。

    image-20220609102401574

  2. 按照存储介质分类:

    • 半导体存储器:主存、Cache
    • 磁表面存储器:磁盘(机械硬盘)、磁带、磁条
    • 光存储器:光盘
  3. 按照信息的可保存性:根据断电后信息是否消失,分为易失性存储器和非易失性存储器;根据读出后信息是否被破坏,分为破坏性读出和非破坏性读出两种。

  4. 按照存取方式分类:

    • 随机存储器RAM:每个存储单元的存取时间与其物理位置无关
    • 串行访问存储器:包括顺序存取存储器(如磁带,从磁头开始按顺序访问)和直接存取存储器(如机械硬盘,磁头先移动到一个区,在这个区内顺序存取)
    • 只读存储器ROM:内容只能随机读出而不能写入,通常用于存储固化的信息,如存放BIOS启动程序。

存储器的性能指标?

  1. 容量:最大容量受MDR和MAR位数的限制。总容量=存储单元数$\times$每个存储单元的大小。
  2. 单位成本:总成本/存储器容量
  3. 存储速度:存储速度=数据宽度/存储周期。存储周期包括读写时间和恢复时间两部分,不能简单地把存储周期和读写时间划等号。比如破坏性存储器,它的恢复时间就很长。

主存储器的基本组成和原理?

第一章介绍过,存储器包括存储体、MDR和MAR。而存储体就是如下图的一个矩阵结构,所以也被称为存储矩阵。具体描述如下:

image-20220609112050743

  1. 存储矩阵的每一行就是一个存储单元(存储器读写的单位)。

  2. 地址线的数据存储在MDR中,由译码器翻译为地址,从而控制对应存储单元与MDR的通断

  3. 还需要控制电路对读写过程进行控制。一是指定是读数据还是写数据(数据流向不同),二是控制各元件等到电压稳定后才进行下一步操作。

  4. 需要理解片选信号,它控制这片存储器的开关。因为一个内存条往往由多个存储器并联或串联:

    image-20220609113655080

于是可以对整个存储器芯片进行封装:

image-20220609113759636

芯片向使用者提供的接口称为引脚。我们可以根据这些线的条数(还包括电源线和地线)来算出引脚的数目。如给出存储器的规格为8K$\times$8位,那么可以知道地址线有13条($8K=2^{13}$),数据线有8条,再加上其他控制线的条数,就可以求得引脚数了。

存储器的行地址与列地址?

在上面的模型中,译码器输出端的线为2的指数倍,需要连接的选通线太多,不易实现。所以,将存储器的存储单元在二维空间上排列,分为行地址和列地址。当行和列两根线都对这个存储单元选通时,才能对该存储单元进行读和写。

image-20220610173301380

分析这样可以减少一个译码器输出端选通线的数量:

假设对于一位排列的模型,地址线有N条,那么译码器输出端有$2^N$条,对应$2^N$个存储单元。

对于二维排列的模型,要得到N个存储单元,那么行列数都为$2^{\frac N2}$,分别对应$2^{\frac N2}$条选通线。

比如N=8时,一维模型需要接$2^8=256$根选通线;而二维模型每个译码器只需要接$2^4=16$条选通线,选通线的总数为32根,大大减少了。

存储器的寻址?

之前在”边界对齐”处复习过寻址方式,但是讲得并不深入。这里结合存储矩阵进一步理解。

image-20220609115050700

  1. 存储单元(每一行)一般都是字节的整数倍,所以可以把存储矩阵的每一行按字节分块。上图的一个存储单元的字长位4字节。
  2. 按字节寻址中,每一个字节都有一个编号,访问对应编号的字节即可。
  3. 按字寻址中,字依然是连续编号的。所以需要使用字地址和字节地址的关系进行转化:字节地址=字地址<<2
  4. 按半字寻址同理,字地址=半字地址<<1

DRAM和SRAM?二者的区别?

  1. DRAM(Dynamic)即动态RAM,用于制作主存。上面讲的存储器的结构是主存的结构,也就是DRAM的结构。

    由于DRAM使用栅极电容来存储信息,每次从DRAM读取时会放电,原信息被破坏,所以读取结束后还需要充电进行再生。

  2. SRAM(Static)即静态RAM,用于制作Cache

    由于SRAM使用双稳态触发器来存储信息,能保持电压不变,所以读取后信息不会改变,无需进行恢复操作。但是它的电路较DRAM更复杂。

二者的区别总结如下:

image-20220610172147884

需要注意表中的刷新和再生不是一个概念,再生是破坏性读出导致,刷新见下。

DRAM的刷新?

由于DRAM电容上的电荷,由于空气等原因,会逐渐减少。为了保持电容上的电压,所以每隔一段时间需要刷新。关于刷新,我们需要知道下面几点:

  1. 隔多久刷新?

    一般间隔2ms,这个间隔就是刷新周期。在这个周期内,我们需要把每个存储单元都刷新一遍。

  2. 每次刷新多少存储单元?

    对于存储器的二维结构,每次刷新一行的存储单元。

  3. 如何刷新?

    由专门的刷新电路实现。原理是读出该行存储单元的数据再重新写入,因此占用一个读写周期。

  4. 在什么时候刷新?

    根据刷新的时机,分为:

    1. 集中刷新:在一个刷新周期内,利用一段固定的时间来对所有存储单元进行刷新。在这段刷新的固定时间内是不能对存储器进行读写的,称为死区
    2. 分散刷新:分散刷新为了避免死区,把对每行的刷新分散到各个工作周期中。但是它分散的方式比较无脑:每隔一个读写周期就进行一段刷新。这样的刷新过于频繁,一个刷新周期内每个存储单元一般都会刷新多次。表现为系统的读写周期为存储器读写周期的两倍,效率过低。
    3. 异步刷新:异步刷新也是一种分散式的刷新,但它通过计算,保证一个刷新周期内每行只会被刷新一次。具体的计算公式为:每行的刷新时间间隔=刷新周期/行数。

此外,存储器的刷新由存储器自己完成,不需要CPU控制。

ROM的类型?

ROM即Read Only Memory,只读存储器。由于它是只读的,所以它上面的存储的信息一般都是非易失的。它可以分为如下几种:

  1. 掩膜式只读存储器MROM:真正意义上的只读。它里面的信息一般是由商家写入的,用户不能修改,所以可靠性高。
  2. 一次可编程只读存储器PROM:也是只读的。和掩膜式只读存储器的区别是它第一次数据的写入由用户利用专门的设备完成。此后不能进行更改。
  3. 可擦除可编程只读存储器EPROM:和一次可编程只读存储器的区别是写入数据后还可以使用特殊的方式擦除本来的数据重新写入,如紫外线,电擦除等。
  4. 闪存Flash Memory:在电擦除EPROM的基础上发展而来,如U盘、SD卡都是闪存。因为写的时候需要擦除,所以闪存的读速度一般比写速度要快
  5. 固态硬盘SSDSSD由控制器+多块闪存组成,速度快、位密度高、功耗低,是当今辅存的发展方向,单目前成本较高。而手机为了在体积小的同时也具有较大的容量,辅存一般使用的都是SSD。

上面分的ROM差不多都是外存或辅存。实际上,主板的BIOS芯片也是ROM。它存储了“自举装入程序”,负责在开机时引导CPU将操作系统装入内存。BIOS一般和主存统一编址,它应该看成内存的一部分。

存储芯片的扩展?

CPU与主存的连接如下所示:

image-20220613100254636

由于主存一般包含多块存储芯片,且可由多个内存条组成,所以将MAR和MDR设计在CPU内部是合理的。CPU通过地址总线找到主存中的存储单元,通过数据总线与主存进行数据传输,通过读写等信号来控制主存的行为。

但是,存储芯片可能和CPU出现不匹配的问题,如数据总线有8位,但芯片只有1位;CPU的寻址能力为64K,但或芯片的存储单元数只有8K。这时就要对存储芯片进行位扩展和字扩展

image-20220613104523182

  1. 位扩展

    CPU的数据线位数与存储芯片的数据位数不一定相等,必须对存储芯片进行位扩展,使其数据位数与数据线数相等。位扩展的思路很像图形学中的位面法:

    image-20220613104728556

    位扩展的方法是将多个存储芯片的地址端、片选段和读写控制端并联数据端单独引出。8个8K×1bit的存储芯片进行位扩展后可以视为一个8K×8bit的芯片。

  2. 字扩展

    字扩展是指增加存储器中字的数量,即可以寻址到的存储单元的数量。它的方式是将芯片的地址线、数据线和读写控制线并联,通过片选信号来区分不同芯片的地址范围。

    image-20220613110219374

    如上图,$A_{15}A_{14}$两个片选信号通过一个二四译码器后分别连接到不同的存储芯片,每次选中一个芯片。实际上,因为$\bar {CS}$代表低电平有效,所以译码器的输出端应该经过了反相器:

    • $A_{15}A_{14}$为00选中了第1号芯片,所以第1号芯片的地址范围为0000000000000000-0011111111111111。
    • $A_{15}A_{14}$为01选中了第2号芯片,所以第2号芯片的地址范围为0100000000000000-0111111111111111。
    • $A_{15}A_{14}$为10选中了第3号芯片,所以第3号芯片的地址范围为1000000000000000-1011111111111111。
    • $A_{15}A_{14}$为11选中了第4号芯片,所以第4号芯片的地址范围为1100000000000000-1111111111111111。

    这样就构成了从0000000000000000到1111111111111111一系列连续的内存单元,实现了字扩展。

  3. 字位同时扩展

    还有一种情况是芯片位数和存储单元数都不足,这时就要对字、位同时进行扩展:

    image-20220613112050375

    字位同时扩展的方式是各芯片的地址线和读写控制线并联;进行位扩展的一组芯片译码器输出端并联,数据线单独引出;进行字扩展的一组芯片,数据线并联,$\bar{CS}$端分别接到不同的译码器输出端上。

    可以理解为先进行位扩展后再进行字扩展,也可以理解为先进行字扩展再进行位扩展。

存储芯片的地址分配?

上面的例子进行字扩展的时候使用的是译码器,这就是片选法。片选法是比较常用的方法,此外还有线选法

线选法的方式是一根线选中一个存储芯片,这样的连接比较简单。但是从下图可以看出,线选法的地址空间是不连续的,会造成CPU地址资源的浪费。

image-20220613113241544

并行存储器结构技术有哪些?

内存和CPU的频率(速度相差很大),要提高CPU访问内存的速度,可以从下面几个方式入手:

  1. 提高内存本身的速度,如采用比DRAM更先进的SDRAM
  2. 在CPU和内存之间增加高速缓冲存储器Cache
  3. 采用并行结构技术,使CPU能同时访问内存的存储单元。

1和2已经是当今的标配了,第3点的应用我们也并不陌生:两根内存条组成双通道。如两个8G的内存条组成双通道往往比单根16G的内存条快很多。接下来研究内存的并行技术。(需要注意的是并行结构技术涉及到的是多根内存条之间的关系,而之前研究的是一根内存条上多个存储芯片的关系

  1. 双端口存储器

    双端口RAM提供了两组独立的读写控制电路和两个读写端口。对于双核以上的CPU,可以对该存储器的不同内存单元同时进行读写;但同时访问同一个内存单元时,就需要注意了:

    • 同时读同一个内存单元,没有问题
    • 同时写同一个内存单元,可能发生丢失更新的问题
    • 对同一内存单元一读一写,可能发生读脏数据的问题

    这和数据库的事务的并发控制很相似,可以用“加锁”,即增加一个“忙”信号的方式来解决:

    image-20220613132116223

  2. 低位交叉编址多模块存储器

    这种方式用到了多根内存条,所以首先能扩大内存的容量。如果是连续编址(或称为高位交叉编址)的话,并不能实现存储器并行工作,只能简单地扩大容量;但是使用低位交叉编址,在扩大内存的同时又能实现并行,可以较大的提升性能。下面对这两种编址方式进行研究。

    1. 高位交叉编址

      高位交叉编址如下图,体号是在地址的最前面,用于定位不同的存储器。由于体号在最前面,所以单个内存条上的存储单元编号是连续的。

      如果需要访问多个连续的存储单元(程序的局部性),那么只能每读出一个内存单元的数据后等待一段时间(等待的原因是多方面的,如存储元信息的恢复、各种信号的稳定等)再继续读取下一个内存单元,而此时其他存储器都是空闲的。

      image-20220613133546555

      前面讲过,存储周期T包括读写时间r和恢复时间s。这样每读一个存储单元的数据都花费一个存储周期T的时间。

    2. 低位交叉编址

      低位交叉编制的示意图如下,体号在地址的最后面。

      image-20220613135135922

      按照低位交叉编址的方式,连续的地址编号就不在同一个存储体上了,而是按顺序分布在不同的存储体上。这样要访问一段连续的地址,直接访问多个存储器即可,无需等待上一个内存单元恢复再读取下一个。

      但需要注意的是,我们读取存储单元时依然要按照顺序,即先读0,再读1,而不是同时读。所以读取一个内存单元的时间缩短到了r,减少了s的时间。($T=r+s$)

    低位交叉编制有这样一个问题:如果读取时间为r,恢复时间为4r,我们要读取编号为0~4的内存单元,时序图如下:

    image-20220613140512400

    访问完3号存储单元再访问4号时,仍然需要等待一个r的时间。如果恢复时间为3r,那么访问的时序图如下:

    image-20220613140810166

    这时就无需等待了。所以要保证流水下不间断地访问一段连续的内存单元,需要满足的条件:存储体个数≥存储周期T/读取时间r。

Cache的原理?

首先要知道局部性原理的两点:

  1. 空间局部性:最近的未来要用到的信息,很可能与当前正在使用的信息在存储空间上是临近的,如数组。
  2. 时间局部性:最近的未来要用到的信息,很可能就是当前正在使用的信息,如循环。

Cache正是利用局部性原理,把程序中正在使用的部分存放在高速缓存中,CPU每次访问数据时先去Cache中找。这时可能有命中和没命中两种情况:

image-20220613142254739

Cache行?主存块?

我们知道了Cache会存储与当前使用的数据所在存储单元临近的数据。如何定义这里的“临近”?

采用的方式是将主存分块(也称页),每次将数据所在的块送入Cache中,Cache中存储的块称为行(应该是为了区别主存的块)。

进一步地有以下问题:

  1. 主存块怎么和Cache行建立映射关系?
  2. 当Cache满了,主存的块应该替换那个Cache行?
  3. Cache实际上是主存的副本,如果进行写操作,如何保证Cache数据和主存同步?

Cache行和主存之间的映射方式?

我们先来研究第一个问题:主存块怎么和Cache行建立映射关系?

  1. 全相联映射

    在全相联映射的方式下,主存中的每个块都可以对应Cache中的任意行。只要有空位就可以放,没有空位了就替换。

    而Cache的行要与主存的块建立映射关系,需要储存相应的主存块号。主存块号的计算如下:

    假设Cache行的大小为512B,主存中存储单元数为1MB,按字节编址,那么主存的地址总共有$2^{20}$位。由于主存块和Cache行大小相等,均为$512B=2^{9}$,所以主存分为$2^{20-9}=2^{11}$个块。主存的20位地址可以拆分为如下的形式:

    image-20220613160638035

    Cache除了存储主存块号外,还需要存储一个有效位来表示该存储单元是否有效。


    现在假设我们有了一个20位的地址,使用全相联映射访问数据的步骤如下:

    1. 将该地址的高11位与Cache的标记进行对比(这个步骤是顺序访问的,查找比较耗时)
    2. 如果查命中且对应Cache行的有效位为1,那么直接通过地址低9位在行(块)内寻址即可。
    3. 如果查不命中或有效位为0,直接去内存中访问。
  2. 直接映射

    直接映射通过取模的方式建立主存块和Cache行之间的映射关系,一个块只能放到Cache的某个行,而不能放到其他行

    这里取模的除数就是Cache的行数,如Cache有8行,$0 \%8=0\rightarrow $放到第0行;$2 \%8=2\rightarrow $放到第2行;$8 \%8=0\rightarrow $放到第0行。

    image-20220613161645932

    这时Cache行与主存块是一对多的关系,要区分映射在同一个Cache行不同主存块,依然要存储标记,但这时的标记不必存储整个主存块号

    image-20220613162449850

    可以发现,当Cache行数为8时,映射到同一Cache行的主存块号的后三位相等,因此Cache标记不必包含这三位,这三位代表了Cache的行号。一般地,使用直接映射,主存地址划分如下:

    image-20220613163149073


    现在假设我们有了一个20位的地址,使用直接映射访问数据的步骤如下:

    1. 使用块地址(高11位)的低3位得到Cache行(可以直接找到)
    2. 对比块地址的高8位和当前Cache行的标记
    3. 如果对比相等,且有效位为1,那么直接行内寻址。
    4. 如果不相等或有效位为0,访问内存。
  3. 组相联映射

    全相联映射比较灵活,Cache的空间利用率高,但查找标记比较慢;直接映射可以直接找到Cache行,查找标记快,但是空间利用率低。

    组相联映射在二者之间折中:给Cache行分组,组间直接映射,组内全相联映射。

    假设Cache总共有8行,每组两行,分4组,那么20位的地址就划分为:

    image-20220613165001669


    现在假设我们有了一个20位的地址,使用组相联映射访问数据的步骤如下:

    1. 使用块地址(高11位)的低2位得到Cache组(可以直接找到)
    2. 在组内使用块地址的高9位进行查找
    3. 如果查命中,且有效位为1,那么直接行内寻址。
    4. 如果查不命中或有效位为0,访问内存。

    特殊地,当组相联映射分组为1,就变成了全相联映射;当分组为Cache行数,就变成了直接映射。

Cache的替换算法?

现在来解决第二个问题:当Cache满了,主存的块应该替换哪个Cache行?

Cache的替换算法是针对全相联映射和组相联映射的,直接映射替换对应的内存单元即可。常用的替换算法有:

  1. 随机算法RAND:随机替换一个Cache块,实现简单

  2. 先进先出算法FIFO:替换最早调入的行,实现容易,按照行号顺序调入即可。

  3. 近期最少使用法LRU:(需要重点掌握)

    使用一个计数器来记录Cache行对应的主存块的使用情况。这个计数器的值称为LRU位,它的位数和组的大小有关(全相联映射组大小为n)。计数器的变化规则如下:

    1. 命中时,被访问行的计数器清零,比其低的计数器值+1,其余不变
    2. 未命中且还有空闲时,新装入行的计数器置为0,其他行计数器+1
    3. 未命中且没有空闲时,淘汰计数值为3那一行的主存块,装入新块后置为0,其余行的计数器+1

    使用这个规则进行替换的一个例子:设Cache采用4路组相联,五个主存块{1,2,3,4,5}映射到同一个组,访问序列为${1,2,3,4,1,2,5,1,2,3,4,5}$,则替换的过程用表表示:

    image-20220613191533125

  4. 最不经常使用算法LRU:替换Cache中引用次数最少的块。

Cache的一致性问题(写策略)?

会导致Cache和内存出现不一致情况的操作只有写操作,所以Cache的一致性问题研究的就是Cache的写策略

  1. 命中“写回法”+不命中“写分配法”

    当CPU对Cache写命中时,只修改Cache的内容,且将脏位置1;当该Cache行对应的主存块被替换,且脏位为1时,再写回主存。使用脏位的目的是当没有对某个Cache行进行写操作时,对应脏位为0,无需写回,以节约时间。

    当CPU对Cache写未命中时,先将对应主存块加载到Cache中,再使用写回法。

  2. 命中“全写法”+不命中“非写分配法”

    当CPU对Cache写命中时,同时对Cache和主存进行写操作。但是这样就失去使用Cache的意义了,所以在CPU和内存之间增加了一个写缓冲

    image-20220613192855225

    当CPU对Cache写未命中时,只写入主存块,不将其载入Cache。

虚拟存储器?

前面研究的都是“Cache—主存”层次,解决的是内存和CPU速度不匹配的问题;虚拟存储器属于“主存—辅存”层次,解决的是内存容量不够的问题。

虚拟存储器将主存和辅存的地址空间同一编址,形成一个庞大的地址空间,这个地址空间中的地址就是虚地址,或称为逻辑地址;实际主存单元的地址称为实地址,或称为物理地址。虚拟存储器要做的就是实现虚地址到实地址的转化。

页式虚拟存储器以固定大小的页为基本储存单位,类似于“Cache—主存”层次的行和块。这样虚地址分为虚页号+页内地址,实地址分为实页号+页内地址,二者的页内地址是一样的,所以虚地址到实地址的转换就是虚页号到实页号的转换,借助的是页表:

image-20220613201506183

每个进程都有一个页表基地址,存放该进程的页表首地址;虚拟页号相当于偏移地址,根据虚拟页号找到页表的对应表项。虚拟页表详细的表项如下:

image-20220613201809758

  1. 有效位(装入位):1表示页面在主存中,0表示不在,需要从辅存中读取。
  2. 脏位(修改位):目的是解决主存和辅存之间的一致性问题(写策略)。
  3. 引用位:解决的辅存中的数据调入主存时的替换问题(实现替换算法)。
  4. 物理页地址就是内存中的实地址,磁盘地址就是页面在磁盘中的地址。