3.2存储器层次结构 -- 《深入理解计算机系统》☆☆☆☆☆

存储器系统，包括存储设备以及它们的组织结构。

存储设备包括：cache，内存，硬盘，磁带....

组织结构：层次结构。以CPU为记，越靠近CPU的存储，越快速，越小，成本越高。

编程时要做的就是：让数据在较高层，这样CPU能更快的访问。难处在于高层的存储空间较小。

（1）随机访问存储器（内存）

分两种SRAM和DRAM。即静态的和动态的。

dynamic 动态
static state 静态

i）SRAM（cache用 sram 价格贵，相比dram速度快）

6个晶体管一个单元（3组组合差分电路）

每个数据位存储于一个“双稳态的存储单元”。特点是：只要有电，就永远保存它的值，比较抗干扰。

ii）DRAM （常用的内存条 ddr3 动态随机访问存储器及 d-sdram 3代，相比sram便宜，相比sram速度慢）

一个晶体管，一个电容；

“每个位存储为对电容的充电”---书上这么说的。我想意思是：电容里有电就是1，没电就是0。

电容会漏电，因此必须周期性的用读出然后写回的方式刷新存储器每个位。

一个DRAM芯片中所有单元（一个单元是一位），被分成d个超单元，每个超单元由w个单元构成。

因此一个DRAM芯片能存储d*w位。这d个超单元组织成一个r行c列的矩阵。

因此每个超单元有一个地址（i，j），i是行号，j是列号。

CPU访问存储器中超单元(i,j)的方式：

先将地址i通过存储控制器发送到DRAM，DRAM取出第i行超单元内容，放入内部行缓冲区。再将地址j通过存储控制器发送到DRAM。DRAM从内部行缓存区中取出

第j个超单元，通过数据总线将数据返回。

好处：地址总线长度短。若有16个超单元，组成4*4的矩阵，则地址总线只需要两位。若组成线性数组，地址总线需要4根

坏处：地址需要分两次发送，增加访问时间。

存储器模块(内存条)

多个DRAM芯片包装在存储器模块中，然后插到主板的扩展槽里。有DIMM和SIMM接口。

内存条的两面都有金手指，或者叫pin，如果它们传输的是相同的信号，则是SIMM接口，如果传输的是不同的信号则是DIMM。貌似DIMM中也会有不同的分别，这个不细糾了。

一个64MB的内存，有8个64Mbit的DRAM芯片，每个DRAM芯片由8M*8构成。八个芯片编号为0-7. 每个超单元存储一个字节。

用(i,j)表示一个DRAM芯片中某个超单元的地址，当将这个地址发送给存储控制器时，存储控制器在8个芯片中的8个超单元取出，它们一起构成一个64位的数据。

DRAM又有其他改进的型号，叫什么SDRAM，DDR SDRAM等等.... 既然我也不清楚，那就不细说了。

CPU访问主存的过程：首先通过CPU内部的总线接口，经过系统总线，到达I/O桥接器，通过存储总线到达内存。 I/O桥接器上又接上其他I/O总线。

关于总线，我总不明白它们是个什么东西？我猜想它们就是一些导线，用来传输信号的。传地址的就是地址总线，传数据就是数据总线。

但为什么又有这么多不同的名称？与之相关的南北桥是什么作用？这里面有相应的标准规范吗？

（2）磁盘

磁盘由一些盘片构成，盘片的正反面都能存储数据，每个盘片分成许多的磁道，每个磁道分成一些扇区。

因此磁盘的容量 = 盘片数量 * 2 * 磁道数 * 每磁道扇区数 * 每扇区大小。

通常一个扇区为512B。

对扇区的访问时间包括：寻道时间，旋转时间和传送时间

寻道时间：即将读写磁头放在包含要访问的扇区的磁道上。T(seek)，取决于磁头以前的位置和传动臂移动的速度。通常为6-9ms（不知道对现在的磁盘该数据是否准确）。

旋转时间：定位到磁道后，转动盘片，直到指定的扇区到达磁头下。取决与盘片的转速。最大旋转时间就是盘片转一圈的时间了。平均旋转时间通常为最大旋转时间的一半。

传输时间：读扇区内容需花费的时间。

书中总结“将寻道时间乘2是估计磁盘访问时间的简单而合理的方法”

逻辑磁盘块：在访问扇区时，通常只给出扇区的逻辑号，然后磁盘控制器会将逻辑号转换为相应的盘片上的相应磁道的相应扇区。

（3）局部性

随着CPU的发展，CPU与内存和磁盘的差距迅速拉大，为充分利用CPU性能，人们才采用了层次的存储结构。

而采用层次存储结构能提升性能的原因是：局部性，包括时间局部性和空间局部性。

（本以为局部性是程序局部性和数据局部性，仔细看书，原来是时间局部性和空间局部性）

时间局部性：被引用过的存储器位置，不久的将来很可能还会被引用。

空间局部性：一个存储器位置被引用了，那相邻的位置可能也会被很快被引用到。

书上示例：

int sumvec(int v[N])

{

int i, sum = 0;

for (i = 0; i < N; i++)

sum += v[i];

return sum;

}

由于sum会被多次引用，因此具有时间局部性。

由于数组v的被顺序访问，因此具有空间局部性。

这里是连续访问v的元素，称这种访问方式为具有步长为1的引用模式。

对于具有步长为k的引用模式，k越大，空间局部性越低，k越小，空间局部性越高。可以将步长看成是衡量空间局部性的一个因素。

（4）存储器层次结构

L0 寄存器

L1 芯片里L1高速缓存

L2 芯片外L2高速缓存

L3 主存

L4 本地磁盘

L5 远程二级存储

第k层是第k+1层的缓存，因为第k层的存储速度更块，当然空间也更小。这样便有一个统一的缓存模型。

第k+1层的存储器分成不同的块，每个块有唯一的地址，通常块的大小固定（也可以变化）

第k层的存储里缓存着k+1层里的部分块，在k和k+1之间传输数据时，都是以块为大小来传输。

i）缓存命中

若需要访问k+1层里的数据块d，如果d已经缓存在第k层，则称缓存命中。这样从第k层取块d要比k+1层更块。

ii）缓存不命中

若d不在第k层，则是缓存不命中，此时将k+1层存储中取出块d，放入k层。可能需要替换掉k层中已有的块。替换策略是：随机，最近最少使用等。

强制不命中

刚开始k层中没有缓存k+1中的数据，这时称为强制性不命中。

由于k层大小较小，因此k+1层中可能多个块会需要放入k层中相同位置，此时为冲突不命中，因为k层中可能还有多的空间没用。

若循环访问一个数组，当数组大小大于k层的大小时，就会发生容量不命中，即是因k层容量太小导致的。

需要有个东西对缓存进行管理，比如怎么进行块的划分，各层次间怎么传送块，判断是否命中，不命中该如何处理，写回数据的时候该如何处理。

都是需要考虑的问题，可用硬件管理如cache，也可用软件管理如虚拟内存。

（5）缓存的管理

i）相关假定

假定存储器的地址有m位，便有M=2^m 不同地址。

一个缓存被分成S=2^s个的高速缓存组（cache set），

每个组包含 E 个高速缓存行。

每个缓存行由一个B=2^b字节的数据块，一个有效位，t=m-(b+s)个标记位组成。

一个高速缓冲区的大小C = S * E * B。

ii）如何访问缓存

当要访问存储器中的一个字节时，给出的访问地址的m位中，前t位表示标记位，中间s位为组索引，最后b位为块偏移。

因此对这个访问地址，首先利用中间的s位组索引找到相应的组，

对组中的每一个缓存行，将缓存行的t位标记与访问地址中的前t位进行比较，若相等，则找到字节所在的块。若没找到，缓存不命中。

如果有效位为1，则利用b位块偏移，在缓存行中取出要访问的字节。

若有效位为0，则缓存不命中。

iii）缓存不命中时

当缓存不命中时，则若需要将存储器中的块放入缓存对应的组中。

若组中的行都有数据，则需要进行替换，替换策略是：LFU或这LRU（不想细说了）

iv）三种缓存方式的划分

分为直接映射高速缓存，组相联高速缓存，全相联高速缓存

若指定了S，E，B的值，则缓存的划分方式就已经确定了。

缓存块与存储块之间也就建立了一种映射关系。

当E = 1时，一个组中只有一个行，明显这个时候不需要使用替换策略，比较简单。查找块也很块，但容易发生冲突不命中。直接映射高速缓存

当E < C/B时，一个组中有多个行，这时需要考虑使用什么替换策略了。而且在查找块时，需要将地址中的标记与组中全部缓存行的标记进行比较。组相联高速缓存

当E=C/B时，仅有一个组，这时不会出现冲突不命中的情况，但容易发生容量不命中。而且查找块时，需要比较全部缓存行中的标记。全相联高速缓存

未完待续....

这只是看书的时候做的记录，没有什么含金量，而且书中有图，看着更明了。写在这里更多是表示我看了这部分内容，总结下好些，也许以后能再看看。

第三章存储器的层次结构

3.1 存储器分类

按存储介质分类
（1）半导体存储器：
        TTL，MOS，SSD。
        易失
（2）磁表面存储器：
        磁头，载磁体
        非易失
（3）磁芯存储器：
        硬磁材料，环状元件
        非易失
（4）光盘存储器：
        激光，慈光
        非易失
按存取方式
（1）存取时间与物理地址无关（随机存取）
        类比于数据结构中的线性表数组(取数组某个元素的时间和物理地址无关，只和index有关)
        （a）随机存储器：程序执行过程中可读可写
        （b）只读存储器：程序执行过程中只读
（2）存取时间与物理地址有关（串行访问）
        类比于数据结构中的链表
        （a）顺序存取存储器：磁带
        （b）直接存取存储器：磁盘（根据物理地址，直接移动磁头）
按在计算机中的作用分类
（1）主存
        （a）RAM：操作系统被加载到RAM
                SRAM：（Static Random Access Memory）静态随机存储器。常用制作二级缓存。
                                不必刷新电路就能保存数据。但体积大，集成度低
                DRAM：（Dynamic Random Access Memory）动态随机存取存储器。常用语制作系统内存
                                DRAM用电容存储数据，需要定时充电，刷新电路，否则出处的数据丢失。集成度高
        （b）ROM：存储机器自检和引导程序，BIOS等程序
                MROM：（Mask Read-Only Memory）掩模式只读存储器。MROM的内容在出厂前一次写入，之后不能更改
                PROM：（Programmable Read-Only Memory）－可编程只读存储器。只能写入一次数据的只读存储器，写入错误只能更换存储芯片
                EPROM：（Erasable Programmable Read Only Memory）可擦除可编程只读寄存器
                EEPROM： (Electrically Erasable Programmable Read-Only Memory)，电可擦可编程只读存储器。SSD
（2）辅存
        磁盘，磁带，光盘

3.2 存储器的存储结构

存储结构综述
（1）cpu只能和主存，cache进行数据交互，而不能直接获得辅存的数据
（2）辅存的数据只能调入主存，不能直接进入缓存中。
（3）辅存到主存的映射是由OS操作系统管理的。但是主存和辅存之间的一个映射关系被放到TLB中，TLB在cache中。
（4）虚拟存储中的页表，段表，段页表被放到了主存中。cpu通过页表访问辅存时，发现缺页中断，就会先暂停程序的执行，先把数据调到内存
主存
（1）主存的基本结构

（2）主存和CPU的联系
主存中存储单元地址的分配
（1）寻址的个数有2个因素：
（a）地址线的个数：这是内存中总的可寻址字节数
（b）一个地址所占用的字节数：表明了一个内存单元，占用多少个字节
（2）
主存的指标
（1）存储容量：存放二进制代码的总位数
（2）存取速度：
存取时间：存储器的访问时间（读出时间，写入时间）
存取周期：连续两次独立的读写存储器操作之间，最小的时间间隔。用于读电路，写电路，地址电路清空一次
（3）存储器带宽（位/秒）
半导体存储片的基本结构

（1）地址线单向，数据线双向。
（2）半导体芯片的容量由地址线和数据线一起决定。
地址线和数据线的根数表示了内存实际的大小，而cpu理论上的最大寻址范围，由MAR和MDR的大小决定，为
半导体存储芯片的译码方式：
（1）线选法：每个小存储单元占用一行，构成多行的线性结构
       每个小存储单元占用一行，构成多行的线性结构
       eg：161 bit的存储矩阵，占16行，因为要选择16行，所以要有4位片选线，链接所有的16个存储单元。
       这种设计导致电路设计异常复杂。
（2）重合法 : 组合多个存储单元为一行：
       通过组合多个存储单元为一行，来减少行数，达到减少片选线位数的目的，简化电路设计。但此时的存储矩阵，每行有多列存储单元，因此，用X地址译码器（确定行），用Y地址译码器(确定列)，来选到具体的某个存储单元。
       eg：256 1bit重合片选法：把8个bit存储单元作为一行，设计32行即可。
              因为有32行，因此X地址译码器有5位，因为有8列，因此Y地址译码器有3位

3.3 半导体随机存储器

SRAM
（1）SRAM：静态随机存储器，不用刷新电路，使用双稳态管存储数据，不掉电情况下数据存在。
（2）SRAM基本电路
DRAM
（1）DRAM：动态随机存储器，定时刷新电路，使用电容存储数据，不掉电情况下也需要定时对电容充电。
（2）DRAM的存储矩阵是二维的，有行有列。所以要对行和列进行片选。行列片选的片选片进行复用，即同一个针脚，先选择行，后选择列。
（3）动态RAM刷新（刷新与行地址有关：默认数据能保持2ms）

（a）集中刷新(存取周期0.5

3.4 主存与CPU的连接

存储容量的扩展
（1）位扩展
用2片1K4位存储芯片组成1K8位存储器
位扩展没有增加房间号，只是房间里面多住人了。即地址线不变，增加数据线，其他没变化
（2）字扩展（增加存储字的数量）
用1K8位存储芯片组成2K8位的存储器：原来的1K字即10根地址线，变成现在的2K即11根地址线，多出来的1根地址线用来进行片选。

（3）字位扩展
用8片1K4位的存储芯片组成4K8位的存储器。即地址线先扩展4位成
存储器与CPU的连接
（1）地址线的连接：先连接芯片固有的
（2）数据线的连接：先连接芯片固有的
（3）读写控制线的连接：每个芯片都要连接，包括增加的
（4）片选线的连接：用增加的地址线进行片选线
（5）芯片选择：选择芯片数量组少的解决方案
eg：设CPU有16根地址线，8根数据线。现有以下几种存储芯片：1K4位RAM，4K8位RAM，8K8位RAM，
2K8位ROM，4K8位ROM，8K8位ROM，和74138译码器。请画出CPU和存储器的连接图。要求：
主存地质分配如下：6000H~67FFH为系统程序区。6800H~6BFFH为用户程序区。
（1）写出地址对应的二进制码

所谓系统存储区，指的是单片机中存储系统程序的那部分芯片，通常被烧制在ROM里，而用户程序是单片机中跑的程序，运行在RAM中。如上图所示，应该选择1片2K8位ROM，和2片1K4位RAM。
（2）分配地址线：

3.5 双口RAM和多模块存储器 -- 提高访存速度的手段

单体多字系统
（1）把原来的单字长寄存器改变为多字长的寄存器，使得内存一次可以读出多个字。从而增加访存速度
（2）这种设计实际上不存在，因为多字长在跳转指令时会产生顺序读取的数据无效，降低效率
双口RAM
（1）双口RAM是含有两套相互独立的读写控制电路而得名。同时进行2次独立的读写操作，所以会增加存储器
（2）当两套读写电路同时操作同一块内存地址时，会产生写冲突。因此，增加一个busy标志(低电平)
多体并行 - 高位交叉，顺序编址
（1）多体并行是编址方式的一种转变。存储矩阵有多个行，每个行成为一个体。
（2）高位交叉编址的意思是：用地址的高位表示是哪个体。所以4体高位交叉编址就变成了高位分别为00,01,10,11$,低位作为体内地址。因此形成顺序编址。
多体并行 - 低位交叉编址，各体轮流编址
（1）低位为体号，高位为体内地址。正好使得连续地址分布在不同的体

（2）低位交叉编制，使得读取连续地址的数据时，采用流水线方式：
     流水线为2步，分为通知体传输和体传输时间。
     通知体的时间为cpu发出信号到体的时间，即总线传输时间。体传输时间为体读取数据的时间。
     为了使流水线可以对齐，要求1个存取周期内，正好通知到所有体，所以存取周期为体数的整数倍。
     eg：设4体交叉存储器，存取周期为T，总线传输周期为
高性能存储芯片
（1）SDRAM（同步DRAM）：系统时钟控制下进行读出和写入，CPU无需等待
（2）RDRAM：由Rambus开发，解决存储器带宽问题
（3）带cache的DRAM：在DRAM的芯片中集成了一个由SRAM组成的cache

3.6 高速缓冲存储器Cache

cache工作原理
（1）主存单位称为块，cache称为行，实质是一个东西
（2）CPU读主存时，把地址同时送给cache和主存，cache通过地址查看此字是否在cache中，若在则立即传送给cpu。
若不在，则用主存读周期把此字从主存中读出送到cpu，与此同时，把含有此字的整个数据块从主存读出送到cache的行中
cache与内存的映射关系(读方式)
（1）全关联：full associative cache
     将内存也看成line的方式存储，全关联是指，内存的任意一个line可以映射到cache中的任意一个line。
     全相连映射的主存地址分为2部分：主存块号|字块内地址；cache标记位为主存地址除了字块内地址的全部高位。
     这就需要一个表，记录主存块号到cache行号的映射
     这种方式，在查找内存是否在cache中时，要查找所有的tag。而且查表的比较器很难实现
（2）直接映射：Direct Associated Cache
     将内存按照cache大小划分为n个Page，内存中Page的line0对应cache的line0。因此直接映射下，cache标志位标志的是内存的page号。
     另一种理解方式：主存中的几个特定行，映射到cache的一个特定行。多对一的关系。这种关系满足公式 i = j mod c
     其中，i：cache行的行号。j：主存块的块号。c：cache的行数。标志位=j/c向下取整
     直接映射相当于多体高位交叉顺序编址。体相当于整个cache，主存包含多个体。采用顺序编址，使得主存地质分成三部分：体号(第几个cache)|cache块号|块内地质。所以cache把主存中的最高几位(cache体号)作为标记位
     当恰好访问的几个主存地质，映射到了相同的cache行，就会产生抖动
（3）组相联：Set Associated Cache
     i. 组相联映射把cache划分为过个way，每个way的结构一样。内存按照way的大小划分Page，page间采用直接映射方式，page内采用全相联映射方式。
即：page号到组号的映射关系是多对一且固定的。
u为cache的way个数，v为way中的行数。 v路组相联：把几行作为一个way
这种方式，把主存地址分为3部分：主存自块标记|组内地址（不用有way号，因为是映射出来的）|字内地址。分别对应cache的标记位，way内的行号
     ii. c64+DSP的配置中，L1P使用1个way，L1D使用2个way，L2不区分程序和数据，使用4个cache way

eg:假设主存的容量为512K16位，cache容量为409616位，块长为4个16位字，访存地址为字地址。
（1）直接映射下，设计主存地址格式：
解：直接映射是主存的每块映射到cache的固定块。所以，主存地址应包含cache块号的标记。
因为按字编址，每个字为16位，所以主存地址容量为

3.7 虚拟存储器

一. 页式虚拟存储

概念
（1）程序员在比实际主存大得多的逻辑地址空间中编写程序
（2）程序执行时，把当前需要的程序段和数据块掉入主存，其他暂不使用的放在磁盘上
（3）执行指令时，通过硬件将逻辑地址转化为物理地址。虚拟地址高位为虚页号，低位为页内偏移地址
（4）当程序发生数据访问或程序访问失效(缺页时)，由操作系统把信息从磁盘调入主存中
分页
（1）基本思想：
内存被分成固定长度且长度较小的存储块（页框，实页，物理页）
每个进程也被划分为固定长度的程序块（页，虚页，逻辑页）
通过页表，实现逻辑地址想物理地址的转化
（2）逻辑地址
程序中指令所使用的地址（进程所在地址空间）
（3）物理地址
存放指令或数据的实际内存地址
“主存-磁盘”层次
（1）与“cache-主存”层次相比，页大小远比cache的行大小要大（windows中的页位4k）
（2）采用全相联映射方式：磁盘中的任意一个页能用射到内存中的任意一个页
因为缺页导致中断时，操作系统从磁盘拿数据通常要耗费几百万个时钟周期。增大页大小，可以减少缺页中断
（3）为什么让软件处理“缺页”
因为访问磁盘需要好粉几百万个时钟周期，硬件即使能立刻把地址打给磁盘，磁盘也不能立即响应
（4）为什么地址转换用硬件实现
硬件实现地址转换可以加快指令的执行速度
（5）为什么页写会策略采用write back
避免频繁的慢速磁盘访问
页表结构
页表的首地址放在基址寄存器。采用基址寻址方式
每个页表项前面有一个虚页号：从0开始递增的序号。页表项又分为几个结构：
（1）装入位：该页是否在内存中
（2）修改位：该也在内存中是否被修改
（3）替换控制位：用于clock算法
（4）其他
（5）实页号（8进制）
TLB
（1）一次磁盘引用需要访问几次主存？2次，一次查页表，一次查物理地址。于是，把经常查的页表放到cache中。这种在cache页表项组成的页表称为TLB（Translation Lookside Buffer）
（2）TLB的页表结构：tag + 主存中的页表项
当采用全相连映射时，tag为页表项前面的虚页号。需要把tag和虚页号一一比较
当采用组相联映射时，tag被分为tag+index，虚页号的高位为tag，虚页号的低位为index，做组内索引(属于组内第几行)

二. 段式虚拟存储

段式存储是根据程序逻辑，给程序分段。使得每段大小不同。这种虚拟地址划分方法适合程序设计
段式存储的虚拟地址由段号和段内偏移地址组成。段式虚拟存储器到物理地址的映射通过段表实现
段式虚拟存储会造成空页

三. 段页式虚拟存储

段页式虚拟存储，先把程序按照逻辑分成段，再把每段分成固定大小的页。
程序对主存的调入调出是按照页面进行的；但他有可以根据段实现共享和保护
缺点是段页式虚拟地址转换成物理地址需要查询2个表：段表和页表。段表找到相应页表的位置，页表找到想也页的位置
段页式细腻地址的结构可以为以下形式：
程序地址：用户号(进程pid) | 段号 | 页号 | 页内偏移地址

eg：
（1）某计算机的cache块工16块，采用二路组相联映射方式，每个主存块大小为32字节，按照字节编制。则主存129号单元的主存块硬装如刀cache的组号是：（C）A、0       B、2       C、4       D、6
解：二路组相联，所以每组2块，共有16/2=8组，所以组号占3位。
      每块32字节，所以块内地址占5位。
      129转化为二进制：1000 0001：前3位为组号，100：=4

（2）假设用若干个2K4位的芯片组成一个8K8位的存储器，则地址0B1FH所在芯片的最小地址为：
解：用2片组成一行，共4行，所以片选地址占2位。片内地址有2k=

（3）某计算机的主存地址空间大小为256MB，按字节编址，指令cache和数据cache分离，均有8个cache行，每行大小为64B，数据cache采用直接映射方式，现有两个程序A，B对数组int a[256][256]进行遍历，程序A按行遍历，程序B按列遍历。假定int类型数据用32位补码表示，数组a按行优先方式存储，其地址为320（十进制）。
问：(1) 若不考虑cache一致性维护和替换算法所需的控制位，则数据cache的总容量占多少？
      (2) 数组元素a[0][31]和a[1][1]各自所在主存块对应的cache行号分别为多少（cache从0行开始）？
      (3)程序A和B的数据访问命中率各自为多少？哪个程序的执行时间更短？
解：(1) 因为cache的总容量是cache每行的数据存储大小+tag位+数据是否有效位+其他一致性控制位。
          主存地址空间256MB，占28位。直接映射方式，8行，行号占3位。每行64B，所以块内地址占6位，因此，tag占28-3-6=19位
          每行有一个数据有效位。因此，cache共（19+1+648）8 = 532字节
      (2) 因为int类型占32位，所以一个int占4B。a[0][31] = 320 + 314 = 444 a1 = 320 + 4(256+1) = 1348。
          块内地址占6位，直接映射下行号占3位，因此444 = 110 | 111100，所以行号为6
          1348 = 10 | 101 | 000100，所以行号为5
      (3) 因为1行cache占64B，每个int数占4B，所以一行有16个数。第一个数会因cache缺失而不命中，然后调入cache。，使得后面的15个int访问全部命中。所以命中率为