存储器分类

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

存储系统的层次结构

image-20210702172352039

主存-辅存层次

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

cache-主存层次

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

虚拟存储系统

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

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

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

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

工作原理

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

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

image-20210702182720499

基本结构

image-20210702182733341

  • 假设主存储器的大小为2n个字节，共分成2m 个块，每个块的大小为2b 个字节，则： 2n = 2m×2b= 2(m+b)，即： n=m+b
  • 假设Cache中有2c个块，每个块的大小为2b个字节，则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 2c，j为Cache槽号，i为主存的块号，2c为Cache的槽数

image-20210702215713177

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

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

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

image-20210702215848787

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

image-20210702220511142

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

替换算法

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

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

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

多层次cache

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

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

虚拟存储器 【重点】

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

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

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

段式管理

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

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

image-20210702221954582

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

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

页式管理

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

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

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

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

image-20210702222628174

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

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

image-20210702222634186

页表的表项：

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

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

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

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

image-20210702223540444

段页式虚拟存储器

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

image-20210702224037755

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

其他概念

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

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

image-20210702225119386

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

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

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

虚拟存储系统两大特点：

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

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

image-20210702225513797

相联存储器

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

image-20210702225936832

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

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

image-20210702231224692

存储保护

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