计组高分笔记：【03】存储系统 「存储器的分类 | DRAM、SRAM | Cache | 位扩展 | 字扩展 | 双端口RAM和多模块存储器 | 写回法 | 全写法 | 虚拟存储系统」_cache sram

1. 存储器的基本概念

1.1 存储器的分类

1.1.1 按层次结构分

注意：

1. 主存---辅存（即虚拟存储器）：解决主存容量不够的问题。
2. cache---主存：解决主存与CPU速度不匹配的问题。
3. cache和主存都可以直接与CPU交换数据，而辅存必须先加载到主存后才能被CPU访问。
4. cache-主存是由硬件自动完成，所以其数据交换对任何程序员都是透明的。
   主存-辅存是由硬件+操作系统完成，所以其数据交换并不是对任何程序员都透明。

1.1.2 按存储介质分

• 按存储介质分类
  1. 半导体存储器（主存、cache）
  2. 磁表面存储器（磁盘、磁带）
  3. 光存储器（光盘）

1.1.3 按存取方式分

• 按存取方式分
  1. 按地址寻址
     1. 随机存储器(RAM): 读取任何一个存储单元所花时间相同，与存储单元所在物理位置无关。比如，内存
        1. 动态随机存储器（DRAM）：用做主存
        2. 静态随机存储器（SRAM）：用做Cache
           特别的，ROM也能随机存储
           
     2. 顺序存储器(SAM): 读取一个存储单元所需时间取决于其物理位置。比如，磁带, CD-ROM CD-ROM != ROM
     3. 直接存储器(DAM)：既有随机存储，又有顺序存储的特性。先直接选取信息所在区，然后顺序存取。比如，磁盘。
  2. 按地址或者内容寻址
     1. 相联存储器：可以按照地址，也可以按照内容检索到存储位置进行读写，比如，快表、相联Cache

1.1.4 按信息的可更改性分

• 按信息的可更改性分
  1. 只读存储器(ROM): 只能读，不能写。引导程序就存放在ROM中
  2. 读写存储器：即可读，又可写。

• 一个例题：
  

1.1.5 按信息的可保存性分

• 按信息的可保存性分
  1. 断电后
     1. 易失性存储器：信息丢失。
     2. 非易失性存储器：信息不丢失。 ROM
  2. 读取信息后
     1. 原存储信息被破坏，需要重写。比如DRAM芯片
     2. 原存储信息不被破坏，比如SRAM芯片、磁盘、光盘

1.2 存储系统的性能指标

• 性能指标
  1. 容量
  2. 价格
  3. 存储速度 = 存储字长/存储周期
     

注意：

1. 存取时间不等于存取周期，前者小于后者。
   存取时间：从存储器读出或者写入一次信息所需要的平均时间。
   存取周期：连续两次访问存储器之间所必须的最短时间间隔。
2. DRAM需要进行刷新操作，所以其恢复时间会比较长。
3. 恢复时间内CPU不可以对该存储体进行访问【如果有多个存储器，但是能对其他存储器进行访问】
4. 计算存储速度：
   

2. 半导体随机存储器

2.1 DRAM和SRAM

2.1.1 DRAM vs SRAM

注意：

1. 集成度：DRAM比较慢，需要集成。
2. 发热量：SRAM有六个触发器，所以功耗大。
3. 刷新：DRAM是电容，电荷会慢慢消失，所以需要刷新，保持电容电荷。
4. 地址复用：地址线引脚数目减半，先传行地址，再传列地址，需要两次。但是会增加行通线和列通线（并用片选线代替行通线）
   一般规则每一个SRAM或者DRAM: 地址线数 + 数据线数 + 1根片选 + 读写线数(1/2根)
   【做题时，默认DRAM使用地址复用，而SRAM没有，这是考点】
   
   
   

• 看清题目
  

2.1.2 DRAM的刷新

· 刷新的分类

1. 分散刷新
2. 集中刷新
3. 异步刷新

• 注意：

1. 刷新是由存储器独立完成的，并不需要CPU控制，即对CPU透明
2. 刷新是以行为单位，故刷新时只需要行地址
3. 一次完整的刷新过程占用一个存取周期。

注意：

1. 分散刷新 = 透明刷新，机器的存取周期中的存取时间用来读写，恢复时间用来刷新，因此不存在死时间。
2. 集中刷新和异步刷新都存在死时间，异步刷新缩短了死时间。
3. 在工作中DRAM的内容会产生变化。-----错误，可以通过刷新机制解决。
4. 刷新周期通常是下取整
   

2.2 ROM

注意：

• 随机存取与随机存储器(RAM)不同，只读存储器(ROM)也是随机存取的。因此，支持随机存取的存储器不一定是RAM
  
  

3. 主存与CPU的连接

3.1 存储芯片与CPU的连接

3.1.1 位扩展

why: 如果数据总线的位数大于单块存储芯片的位数，则需要进行位扩展，从而充分利用总线位数，提高系统效率。

注意：位扩展的各芯片，地址线并联相同(A, CS, WE)，只有数据线不同。

3.1.2 字扩展

3.1.2.1 线选法

注意：线选法是一个地址线中多出的A，每个A对应一个字扩展芯片的CS，用做片选。其余相同

3.1.2.2 片选法

注意：线选法是一个地址线中多出的A，用门电路连接字扩展芯片。能够连接更多的芯片

3.1.2.3 小结

习题：

1. 给出容量算芯片数
   
   
2. 算地址所在芯片
   
3. 判断扩展方式
   

3.2 关于译码器知识的补充

综合例题：

4. 双端口RAM和多模块存储器

• 双端口RAM、多模块存储器都是提高CPU访存的速度。

4.1 双端口/双通道RAM（多核–单存）

• 双通道：RAM是指同一个存储器有左右两个独立编址，分别具有两组相互独立的地址线、数据线和读写控制线，允许两个独立的控制器同时异步的访问存储单元。

注意：

1. 若发生冲突，则对一个CPU发送“忙=0”信号，使得该CPU暂停访存
2. 速度 * n
   

4.2 多模块存储器（多存）

4.2.1 单体多字存储器（空间并行）

• 单体多字存储器：若有m个存储器，则存储单元m个字，总线宽度也扩展为m个字。
• 缺点：灵活性不高。只有一系列访问地址存放在一个存储单元内，否则效果不明显。如下图，访问这四个连续的字，CPU需要读取两次，而低位交叉比较灵活，可以克服这个缺点。
  

4.2.1 多体并行存储器（时间并行）

• 多体并行存储器：总线宽度不会扩展，为单个存储器长度。
  1. 高位交叉编址 = 顺序方式
     1. 优点：当一系列访问地址不连续访问，并且在不同的存储模块内时，则可以并行访问，加快CPU访存速度
     2. 缺点：当一系列访问地址连续，会在一个或两个存储体内，不能被并行访问
  2. 低位交叉编址 = 交叉方式
     1. 优点：当一系列访问地址连续，或不连续当时在不同的存储模块中时，都可以并行访问
     2. 缺点：当一系列访问地址恰好在一个存储模块中时，不能并行访问
• 注意：一系列访问地址可能是连续的也可能是不连续的;
  不连续时，也可能在不同的存储模块中, 从而并行访问
  

• 注意：

1. 低位交叉编址的存储体个数 >= T/r，最好是相等
   
   
2. 低位交叉编址的时间计算，画流水线图
   
3. 低位交叉编址存储次数的判断
   
4. 交叉方式中地址访问的冲突问题：连续m个中相同则冲突。
   
   
5. 综合例题
   

5. Cache（cache—主存）

5.1 Cache概述

5.1.1 程序访问的局部性原理

1. 时间局部性：正在使用的信息等会可能还需要用到。 比如for循环
2. 空间局部性原理：与正在使用的信息在物理位置上相邻的信息等会可能用到。比如数组

注意：for循环访问数组，则同时满足时间局部性和空间局部性原理

5.1.2 cache

1. 作用：解决CPU与主存速度不匹配的问题, 即加速CPU对主存的访存操作。
2. 组成：cache由SRAM（静态随机存储器）组成，通常放在CPU内部。
3. 工作原理：根据CPU所访问的主存物理地址【CPU只发送主存物理地址】，查找地址映射表判断改地址所在块是否被调入cache。若调入，则直接从cache中存取数据；若不在，则直接访问主存，并且同时将改主存物理地址所在块的数据复制一份到cache中。
   【而块内数据是连续的，且被调入内存的块在cache中，故能满足时间局部性和空间局部性原理】

注意：

1. 通常主存的“块”又叫页/页面/页框，cache的块又叫行
2. 将主存块复制到cache时，要标记主存块的信息，即标记位【标记位数与映射方式有关】。然后再用1位来表示有效位，
   每一个行都有一个标记位，这与映射方式无关
   如下图所示：
   
   注意：标记项 = 标记Tag + 有效位 [ + 脏位 + 替换算法位]
3. cache总位数或容量的计算
   
   

4. 求cache地址：cache地址 = 所在块 + 块内地址
   
5. Cache只是副本，用来加速。存储系统指主存和辅存，故存储系统容量 = 主存+辅存
   
6. 主存中指令和数据一起存放在内存中，而cache中指令和数据是分离----->为了减少指令流水线资源冲突

5.1.3 性能分析

通常使用平均访问时间来衡量cache的性能：

注意：

1. cache的平均访问时间有两种公式，注意看清题目给的是同时还是非同时。
   
2. 根据程序求缺失率【关键：a = a +1 是两次访问存，一次读，一次写、a = 3一次写】
   
   注意：若给定一段程序，求cache命中率，只算访问数组，其他变量不看
   

5.2 cache与主存的映射方式

1. 全相联映射：指主存块可以放在cache块的任意地方
2. 直接映射：每个主存块只能映射到一个特点的位置 cache块号 = 主存块号 % cache块总数
3. 组相联映射：几个cache块组合，变成cache组，每个主存块只能放在cache的特定组，而组内位置是任意的。 组号 = 主存块号 % 分组数。

注意：没说按字寻址时，都默认按字节寻址。

5.2.1 全相联映射（任意放）

注意：全相联映射中，cache的标记信息为对应主存块号。

CPU访问想访问主存信息时：

1. CPU会遍历所有cache块的标记位，看是否等于主存地址高22位
2. 若标记匹配且有效位=1，则cache命中。
3. 若未命中或者有效位=0，则正常访问主存。

优点：cache空间利用充分，命中率高
缺点：查找标记最慢。

注意：全相联映射的任意放，指的不是随机放，而是某个主存块在不同的时间可能对应不同的cache块。做题时，其是顺序扫描，第一个空cache则存放数据。

5.2.2 组相联映射（组特定，组内任意）

注意：和直接映射类似，只有当cache的组数为2^n时，才可以优化cache的标记位数。

CPU访问想访问主存信息时（拿上图举例）：

1. 根据主存块号的后2位确定cache组。
2. 遍历该组内的所有标记，若主存块的前20位与组内某个标记匹配且有效位=1，则cache`命中。
3. 若未命中或者有效位=0，则正常访问主存。

组相联映射是全相联映射与直接映射的结合，所以其综合效果最好。

• 注意：n路组相联指一组有n个行，而不是n组
• 例题：

1. 求组号
   
2. 给出地址序列，求命中率
   
3. 求标记位
   
4. 综合应用
   

5.2.3 直接映射（1路组相联）

注意：只有当cache的块数为2^n时，才可以优化cache的标记位数。

CPU访问想访问主存信息时（拿上图举例）：

1. 根据主存块号的后3位确定cache块。
2. 若主存块的前19位与cache行中的标记位相等且有效位=1，则cache命中。
3. 若未命中或者有效位=0，则正常访问主存。

优点：查找标记快
缺点：cache空间利用率低，命中率低

• 例题：

1. 标记位 = 主存位 - 组位 - 块内位
   标记位 = 主存容量 / cache容量 【因为其是1路组相联，2^组位*2^块内位 = cache容量】
   
   
   

5.3 Cache块的替换算法

Cache很小，主存很大。如果Cache满了怎么办？这就需要相应的块被替换，具体有RAND、FIFO、LRU、LFU。

注意：由于直接映射的位置是固定的，所以直接映射不需要考虑替换算法，只有全相联映射和组相联映射才考虑替换算法【在cache块满的情况下才考虑】。

5.3.1 随机算法（RAND）

5.3.2 先进先出算法（FIFO）

5.3.3 近期最少使用算法（LRU）

上图是手算结果。

注意：

1. 其符合程序的局部性原理，所以其效果是最好的。
2. 标记位 + 有效位 + 记数位
   【记数位位数 = n，cache块数 = 2^n】
3. 采用计数器，计数器标记的是未被访问次数，故取最大替换
   

5.3.4 最不经常使用算法（LFU）

不可以手算，得采用计数器

注意：

1. count标记的是被访问次数。
2. count可能会不断增大，变为一个很大的数，故计数位不能确定

5.3.5 小结

注意：

1. 以上都可能发生抖动现象：频繁的换入换出现象。
2. 只有LRU用到了程序的局部性原理，其他的都没有，所以其效果最好。
3. 若Cache块的总数为2^n，则LRU的计算器的位数 = n

5.4 写策略

CPU修改了cache中数据副本，如何确保主存中数据母本的一致性？这就需要用到写策略：

1. 写命中: CPU对某个地址要进行写，且该地址的数据已经被复制到cache中。
2. 写不命中: CPU对某个地址要进行写，而该地址的数据没有被复制到cache中。

5.4.1 写命中

5.4.1.1 写回法

• 写回法：当CPU对cache写命中时，只修改cache的内容，而不修改内存的内容，只有当此块被换出的时候才写回主存。

1. 优点：减少了CPU访问主存的次数，适用于写操作密集的情况
2. 缺点：存在数据不一致的问题

• 注意: 写回法的cache还需要增加一个标记位，即脏位，为1表示要写回。

5.4.1.2 全写法

• 全写法：当CPU对cache写命中时，将数据同时写入cache和主存

1. 缺点：增加了CPU访问主存的次数
2. 优点：能保证数据的一致性，适用于安全性高，不允许由数据不一致的情况

• 注意：全写法通常搭配写缓冲使用。

注意：

• 如果使用写缓冲，则CPU是将数据直接写入cache和写缓冲区，在CPU做其他事情的时候，由一个专门的电路将写缓冲中的数据写入到主存中。
• 使用写缓冲有一个缺点，就是在CPU频繁写的时候，回使得写缓冲饱和，使得CPU阻塞，不得不停下手中的事情，来立即写回数据。

5.4.2 写不命中

5.4.2.1 写分配法

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

缺点：每次不命中，CPU都需要从主存中读取一块

5.4.2.2 非写分配法

当CPU对Cache写不命中时只写入主存，不将主存中的数据调入Cache。通常搭配全写法使用。

注意：非写分配法，只有读未命中才调入Cache

5.5 多级Cache

5.6 cache与总线结合的例题

注意：

1. 总线带宽 = 位数 / 实际的时间开销而不是总线周期
2. 总线的突发传送：没给数据，则默认送首地址即可连续传送一个块
3. 记住突发传送的过程，分三步。
4. 主存采用交叉方式，关于时间的计算是流水线模式。

6. 虚拟存储系统（磁盘—主存）

虚拟二字的含义：传统的存储系统有一次性 和 驻留性两个问题，虚拟存储器就是解决这两个问题，变为多次性 和 对换性，从而从逻辑上扩充了主存容量。

而虚拟存储器一定采用页式、段式、段页式管理方式，因为只有这样才能满足多次性和对换性。因此，其能够很好的满足程序的空间局部性原理
（页式、段式、段页式管理方式又叫请求页式、请求段式、请求段页式，区别是一般页式存放所有的块，故其页表要比虚拟的大且不会发生缺页情况，因为前者一次装入全部程序）

注意：

1. 一次性：作业必须一次性全部装入内存后才能运行
2. 驻留性：一旦作业被装入内存，则会一直占据内存，直至运行结束。
3. 多次性和对换性需要解决2个问题：
   1. 进：如何判断缺页
   2. 出：若内存空间不够，OS如何将暂时不用的信息换出到外存。

6.1 虚拟页式存储

虚拟页式存储：以分页式管理方式的虚拟存储器。
页式管理方式：一个进程在逻辑上被分为若干个大小相等的页面，页面大小与主存块的大小相同。每个页面可以离散的放入不同的主存块中。

1. 优点：不会产生外部碎片
2. 缺点：
   1. 最后一页可能产生内部碎片
   2. 不用拥有逻辑独立性，处理、保护、共享 不及段式
      

注意：

1. 页表的标记项和cache地址映射表的3个字段一样。
2. 虚拟存储器采用的写回法。
3. 页表存放在主存中。
4. 页表核心字段逻辑页号 + 主存块号
5. 页表不可很大—>缺页率高，也不可很小—>页表占的空间大，都会使得速度变慢
6. 执行某条程序，缺页引起中断，中断处理完后，返回到缺页的指令执行，而不是缺页指令的下一条指令
7. 缺页处理后，页表的修改
   

6.1.1 地址转换

每次将程序加载到主存的位置是不一样的，我们不可能提前预知进程被放在哪里，所以指令的地址码使用的是逻辑地址。

注意：

1. 页表寄存器
2. 逻辑地址--->物理地址--->cache/主存
3. 页表缺失，则TLB和cache一定缺失
   

注意：

1. 快表是类似于cache的存在，故其也有三种映射方式。但是，映射方式只会影响标记字段位数(即逻辑块号)，不会影响页框号字段。
2. 快表中逻辑块号字段是隐藏表示，但是页表是直接表示。

6.1.2 快表（TLB）

页式方式只是满足了程序空间局部性原理，创建快表满足程序时间局部性原理。

注意：

1. 访问快表比慢表（即页表）更快的原因：
   1. 快表是放在一个SRAM存储器中
   2. 快表是一种“相联寄存器”，可以按内容和地址寻址，而根据内容逻辑号查找对应的主存号会更快。
2. 若快表没命中，会访问页表，并将信息复制到快表中。

6.2 虚拟段式存储器

1. 优点：
   1. 不会产生内部碎片
   2. 拥有逻辑独立性，易于处理、保护、共享
2. 缺点：会产生外部碎片

注意：

1. 段表是段基址 + 段长
2. 段表核心字段：逻辑段号 + 段基址 + 段长

6.2.1 地址转换

注意：段表存放在段表寄存器

6.3 虚拟段页式存储器

缺点：地址变换过程中需要两次查表，系统开销较大。

程序先分段，再分块：虚拟地址 = 段号 + 段内页号 + 页内地址

注意：

1. 段表的字段变为了标识页表，即段表字段充当页表寄存器的作用。若假设程序被分为n段，则该程序总共存在1个页表，n个页表
2. 段页式先分段后分页，类似于多级页表，故次级页表一个占一个块，段号中用页表存放块号来代替页表基址。

6.3.1 地址转换

6.4 替换算法

注意：只有FIFO算法会产生Belady异常。（Belady异常：所分配的物理块数增大，但是缺页故障数不减反而增加的异常。）

例题：

6.5 虚拟存储器 vs cache

6.5.1 区别与联系

1. 相同：
   1. 都把数据划分为小的信息块，并作为基本的传递单位（只是对象不同，cache划分对象为主存，而虚存划分对象为磁盘程序，故一般虚存的块更大）
   2. 都有地址映射、替换算法、更新策略等。
   3. 都应用了程序的局部性原理.。虚存的页式，段式，段页式都满足空间局部性，若增加快表，则满足时间局部性。
2. 不同
   1. 虚存主要解决主存容量，cache解决CPU与主存速度不匹配
   2. cache全部由硬件组成，对所有程序员透明。
      虚存由os和硬件组成，故其对系统程序员不透明，对应用程序员透明
   3. 对不命中的影响。CPU速度是主存的10倍，主存速度是辅存的100倍，故不命中时，对虚存的影响更大。
   4. CPU可以和主存直接相连，不命中时，CPU可以直接访问主存；但是，CPU不与辅存相连，虚存不命中时，只能从辅存中读数据到主存。

6.5.2 相结合考点

注意：a = a + 1是一次读 + 一次写

注意：换出的页框即换入的页框，记得都要修改

注意：虽然不知道虚拟页号所映射的主存块号，但是虚拟地址中的页内地址包括了cahce的组号，依旧可以求解。