计算机组成知识点 - 存储系统

存储器分类

• 存储器：主存储器（主存或内存，半导体存储器） 辅助存储器（外存或辅存，磁盘、磁带、光盘）
• 串行存储器分成顺序存取存储器和直接存取存储器

存储系统的层次结构

主存-辅存层次

• 操作系统和硬件结合，把主存和辅存统一成了一个整体，形成了一个存储层次。
• 速度接近于主存的速度，容量与每位价格接近于辅存的容量。

cache-主存层次

• 在CPU和主存中间设置高速缓冲存储器（cache），构成cache-主存层次。
• 解决了速度与成本之间的矛盾：速度接近于cache，容量与每位价格则接近于主存。
• 完全由硬件来实现

虚拟存储系统

• 可用机器指令地址码对整个程序统一编址
• 由软、硬件结合实现

cache-主存-辅存三级存储层次

cache容量最小，辅存容量最大，各层次中存放的内容在下一层次中找到。

高速缓冲存储器(cache) 【重点】

工作原理

• 在一个较短的时间间隔内，地址往往集中在存储器逻辑地址空间的很小范围内
• 程序访问的局部性：对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象

cache一般由SRAM组成，介于CPU和主存之间，它的工作速度数倍于主存，全部功能由硬件实现，并且对程序员是透明的。

基本结构

• 假设主存储器的大小为2ⁿ个字节，共分成2^m 个块，每个块的大小为2^b 个字节，则： 2ⁿ = 2^m×2^b= 2^(m+b)，即： n=m+b
• 假设Cache中有2^c个块，每个块的大小为2^b个字节，则Cache的大小为2^(c+b)个字节。每个块的标记信息t=m-c位。

cache的效率

重要因素：cache的容量，块的大小

• 命中率：CPU所要访问的信息在cache中的比率
• 失效率：所要访问的信息不在cache中的比率

具有cache的存储器的平均存取时间=h·tc + (1 - h)·(tc + tm)
cache的存取时间为tc，命中率为h，主存的存取时间为tm

---

例题 设某流水线计算机有一个指令和数据合一的cache，已知cache的读/写时间为10ns，主存的读/写时间为100ns，取指的命中率为98%，数据的命中率为95%，在执行程序时，约有1/5指令需要存/取一个操作数，为简化起见，假设指令流水线在任何时候都不阻塞。问设置cache后，与无cache比较，计算机的运算速度可提高多少倍?

解答：有cache的情况：
平均访存时间=平均取指时间+平均取数时间
= (98%*10ns+(1-98%)*(10ns+100ns)) + (95%*10ns+(1-95%)*(10ns+100ns))/5
=12ns+3ns =15ns

无cache的情况：
平均访存时间=平均取指时间+平均取数时间 = 100*1+100*1/5 = 120ns

速度提高倍数 = 120ns/15ns = 8倍

---

写策略

• 标志交换(flag-swap)或写回法：暂时只向cache存储器写入，并用标志加以注明，直到经过修改的字块被从cache中替换出来时才一次写入主存。【速度快】
• 通过式写(write-through)或写通法：每次写入cache存储器时也同时写入主存，使cache和主存保持一致。【开销大、速度慢】

地址映像

地址变换：执行程序时，应将主存地址变换成cache地址。

1、直接映像：把主存的每一块映射到一个固定的Cache槽中。 j = i mod 2^c，j为Cache槽号，i为主存的块号，2^c为Cache的槽数

• 优点：实现简单、花费少；缺点：Cache利用率不高。

2、全相联映像：允许每个主存块装入到Cache的任何一槽中。

• 优点：灵活，克服了主存；缺点：寻找某一主存块的成本过高。

3、 组相联映像：把Cache分成2^c组，每组有2^r个槽，组间为直接映像；组内为全相联映像。

折衷方案。r=0时是直接映像；r=c时是全相联映像。

替换算法

使用时机：新的主存字块需要调入cache存储器而可用位置又已被占满。

1. FIFO算法：一组中最先调入cache的字块最先替换出去。不需要随时记录各个字块的使用情况，所以实现容易，开销小。
2. LRU算法（最近最少使用）：把一组中近期最少使用的字块替换出去。需随时记录cache中各个字块的使用情况，以便确定那个字块是近期最少使用的字块。

LRU的平均命中率比FIFO要高，当分组容量加大时，能提高LRU的命中率。

多层次cache

哈佛结构：将指令cache和数据cache分开，成为两个相互独立的cache。解决存取数据的操作与取指令的操作发生冲突，从而延迟了指令的读取的问题。

多层次cache：片内cache、片外cache；一级、二级、三级。

虚拟存储器 【重点】

主存—辅存层次与cache—主存层次的比较：

	主存—辅存层次	cache—主存层次
区别	访问“时间比”较小 基本信息单元(字块)也比较小	访问“时间比”大得多 基本信息单元(字块)也很大
联系	原理相同：程序访问的局部性原理	地址变换及映像方法和替换策略，从原理上是相同的

主存—辅存层次的信息传送单位可采用几种不同的方案： 段、页或段页

段式管理

段：利用程序的模块化性质，按照程序的逻辑结构划分成的多个相对独立部分。

段表：指明各段在主存中的位置。

段式管理：主存按段分配的存储管理方式。

• 优点：段的分界与程序的自然分界相对应，段的逻辑独立性使它易于编译、管理、修改和保护，也便于多道程序共享。
• 缺点：容易在段间留下许多空余的零碎存储空间不好利用，造成浪费

页式管理

页面：主存的物理空间被划分为等长的固定区域。

页式管理系统的信息传送单位是定长的页。

• 优点：新页调入主存也很容易掌握，只要有空白页面就可；可能造成浪费的是程序最后一页的零头，它比段式管理系统的空间浪费要小得多。
• 缺点：正好和段式管理系统相反，由于页不是逻辑上独立的实体，所以处理、保护和共享都不及段式来得方便。

页式虚拟存储器：把虚拟空间分成虚页（逻辑页），主存空间也分成同样大小的实页（物理页）。

虚拟地址两个字段：高位字段为虚页号，低位字段为页内字地址。

页表：虚拟地址到主存实地址的变换。虚地址中每一个虚存页地址有一个表目，包含该虚页所在的主存页面号，用它作为实存地址的高字段。

页表的表项：

• 装入位(有效位)：如装入位为“1”，表示该虚页已从辅存调入主存；如装入位为“0”，则表示对应的虚页尚未调入主存，如访问该页就要产生页面失效中断
• 修改位：指出主存页面中的内容是否被修改过，替换时是否要写回辅存
• 替换控制位：指出需替换的页
• 其他保护位

快表（TLB）：把页表的最活动部分存放在快速存储器中组成快表。减少时间开销。

若不存在TLB，访存时先查页表：

• 页面命中：先访问主存查页表，再访问主存取得数据，相当于主存速度降低一倍
• 页面失效：要进行页面替换，页面修改，访问主存次数就更多了

段页式虚拟存储器

把程序按逻辑结构分段，每段分成固定大小的页。

• 优点：（兼取页式和段式系统的优点）调入调出主存按页面进行，亦可按段实现共享和保护。
• 缺点：在地址映像过程中需要多次查表。虚拟地址 -> 物理地址，通过一个段表和一组页表来定位。
  • 段表：每个表目对应一个段，每个表目有一个指向该段的页表的起始地址(页号)及该段的控制保护信息
  • 页表：该段各页在主存中的位置以及是否已装入、已修改等标志

其他概念

多道程序：有多个用户在机器上运行（道：用户）。每一道(每个用户)需要一个基号(用户标志号)，指明该道程序的段表起点(存放在基址寄存器中)。虚拟地址格式：

虚地址：按虚存储空间编制程序，在直接寻址方式下由机器指令的地址码给出地址。由虚页号及页内地址组成。不是辅存的实地址，而是辅存的逻辑地址。

地址变换：虚拟存储器中还有虚拟地址到辅存实地址的变换。
辅存一般按信息块编址，而不是按字编址。若使一个块的大小等于一个虚页面的大小，这样就只需把虚页号变换到Nvd即可完成虚地址到辅存实地址的变换。采用页表的方式：外页表 Nv -> Nvd；内页表 Nv -> 主存页号。

存储管理部件(MMU)：整个虚拟存储器的管理是由MMU部件与操作系统共同完成的。

现代计算机一般都有辅助存储器，但具有辅存的存储系统不一定是虚拟存储系统。

虚拟存储系统两大特点：

1. 允许用户用比主存空间大得多的空间来访问主存。
2. 每次访存都要进行虚实地址的转换。

多用户虚拟存储器工作过程

相联存储器

相联存储器：不按地址访问存储器，而按所存数据字的全部内容或部分内容进行查找(或检索)。

• 比较操作并行进行（CR中的关键字段与存储器的所有W个字的相应字段同时进行比较）。
• 检索某一单元仅需要进行一次检索操作。

---

例子 列出“总分”在560分～600分范围内的考生名单：（可用二次查找完成）

---

存储保护

1. 存储区域保护：界限寄存器，为每个程序划定存储区域，禁止越界访问。
   1. 页表保护：在没形成主存地址前的保护。段表和页表本身都有自己的保护功能。无论地址如何出错，也只能影响到相应的几个主存页面。
   2. 键保护：为主存的每一页配一个键，称为存储键，由操作系统赋予，相当于一把“锁”。为了打开这个锁，必须有钥匙，称为访问键，保存在每道程序的状态寄存器中。数据要写入主存的某一页时，访问键要与存储键相比较，相符则允许访问该页，否则拒绝访问。
   3. 环保护：按照程序重要性以及对系统正常运行的影响进行分层，一层为一环，用环号表示，环号越小级别越高。可以对正在执行的程序本身进行保护。
2. 访问方式保护：读®、写(W)和执行(E)。
3. 管理状态和用户状态：
   1. 管理状态：执行操作系统或管理程序时所处的状态。
      用户状态：执行用户程序时所处的状态。
   2. 特权指令：只有操作系统等系统程序才能使用。