存储系统基本概念

  • 大端法为高位在低地址，小端法为低位在低地址
  • 小端模式 ：强制转换数据不需要调整字节内容

  • 大端模式 ：符号位的判定固定为第一个字节，容易判断正负。

    存储器的层次结构

    image.png
    高速缓存存储器和主存可被 CPU 直接读写，辅存中的数据必须先被调入主存才能被 CPU 访问。
    主存——辅存：实现 虚拟存储系统，解决了主存容量不够的问题
    cache——主存：解决了主存和 CPU 速度不匹配的问题

    存储器的分类

  • 按层次结构分类：高速缓存储器 (cache)、主存、辅存

  • 按存储介质分类：半导体存储器、磁表面存储器、光存储器
  • 按存取方式分类：
    • 随机存取存储器（RAM）：按地址访问数据，读写任何一个存储单元所需时间都相同，与存储单元所在的物理位置无关。比如：内存条。
    • 顺序存取存储器（SAM）：按地址访问数据，读写一个存储单元所需时间取决于存储单元所在的物理位置。比如：磁带。
    • 直接存取存储器（DAM）：按地址访问数据，既有随机存取特性，也有顺序存取特性。先直接选取信息所在区域，然后按顺序方式存取。比如：机械硬盘。
      • 串行访问存储器：读写某个存储单元所需时间与存储单元的物理位置有关
    • 相联存储器（CAM）：按内容检索到存储位置进行读写的存储器。比如：快表。
  • 按信息的可修改性分类：读写存储器、只读存储器（ROM）

  • 按信息的可保存性分类：

    • 断电后信息能否保存：易失性存储器（主存、cache)、非易失性存储器（磁盘、光盘）
    • 信息读出后原有信息是否被破坏：破坏性读出（DRAM 读出数据后要重写）、非破坏性读出（SRAM、磁盘、光盘）

      存储器的性能指标

  • 存储容量：存储字数 (存储单元个数)× 存储字长

  • 单位成本：每位价格 = 总成本 / 总容量

  • 存储速度：数据传输率 = 存储字长 / 存储周期

    • 存储周期：又叫读写周期或访问周期。是存储器进行一次完整的读写操作所需的时间，即两次访问存储器操作所需的最小时间间隔。
    • 存储周期 = 存取时间 (Ta) + 恢复时间 (Tm)
    • 存取时间：从启动存取到存取完成的时间
    • 恢复时间：从存取完成到下次存取的恢复时间
    • 主存带宽 (Bm)：主存带宽又称数据传输率，表示每秒从主存进出信息的最大数量。

      主存储器的基本组成

      基本元件

  • MOS 管，作为通电” 开关 “

  • 电容，用来存储电荷，表示二进制 0/1

    存储芯片的结构

    image.png

  • 译码驱动电路：译码器将地址信号转化成自选通线的高低电平

  • 存储矩阵 (存储体)：由多个存储单元构成，每个存储单元由多个存储元构成
  • 存储元：由 MOS 管和电容构成
  • 读写电路：每次读 / 写一个存储字
  • 地址线、数据线、片选线、读写控制线 (1/2 根)

寻址

image.png

  • 现代计算机通常按字节编址，即一个地址对应一个字节
  • 按字节寻找、按字寻址、按半字寻址、按双字寻址

    SRAM 和 DRAM

    | 类型特点 | SRAM | DRAM | | —- | —- | —- | | 存储信息 | 双稳态触发器 | 栅极电容 | | 破坏性读出 | 否 (读出后不用重写) | 是 (读出后需要重写) | | 运行速度 | 快 (不用刷新) | 慢 (需要刷新) | | 集成度 | 低 | 高 | | 发热量 | 大 | 小 | | 存储成本 | 高 | 低 | | 易失 / 非易失 (断电后信息是否消失) | 易失 | 易失 | | 送行列地址 | 同时送 | 分两次送 (地址线复用技术) | | 用途 | Cache | 主存 |

DRAM 刷新

  • 分散刷新、集中刷新、异步刷新
  • 由存储器独立完成，不需要 CPU 控制

DRAM 分两次送地址

  • 可使地址线、地址引脚减半

现在的主存常采用 SDRAM

ROM

  • MROM：掩膜式只读存储器，存储内容在出厂时写好，无法修改
  • PROM：一次可编程只读存储器，用户用编程器一次性写入，之后无法修改
  • EPROM：可擦除可编程只读存储器，修改次数有限，写入时间很长
    • UVEPROM：紫外线擦除
    • EEPROM：电擦除
  • FM：闪存存储器，如 U 盘等，写入速度比读出速度慢，因为要先擦除再写
  • SSD：固态硬盘，由 FM 和控制单元构成

ROM 虽然名字是只读存储器，但很多 ROM 也可以”写 “
ROM 是非易失性的 ，很多 ROM 也有” 随机存取 “的特性，常用作辅存，如硬盘等；RAM 是易失性的，常用作 Cache、主存。

CPU 与主存的连接

位扩展 - 增加主存的存储字长

image.png
上图实现了用 8 块 8K×1 位的存储芯片扩展为 1 块 8K×8 位的主存。地址总线一次可访问 8 块芯片，数据总线也一次可读 / 写出 8 位数据。
位扩展法：只加大字长（扩展数据线）
连接时：每个芯片具有相同的地址线，不同的数据线

字扩展 - 增加主存的存储字数

image.png
上图实现了用一块 2-4 译码器和 4 块 8K×8 位的存储芯片扩展为 1 块 32K×8 位的主存。片内地址 A0-A12 控制访问芯片中哪块存储单元，片选地址 A13-A14 控制访问哪块芯片。
图中芯片间连接线为片内地址 A0-A12，为了图例美观便直接让芯片相连接，实际并非是在芯片间传输地址数据。
字扩展法: 仅在字向扩充，而位数不变. 需由片选信号来区分各片地址。
芯片的地址总线和数据总线公用，控制总线中 R/W 公用，芯片使能端 CS(chip select) 不能公用，它由地址总线的高位段译码来决定片选信号。 R/W——/WE(write enable)，译码器输出端 Y0-Y3——芯片使能端 CS(chip select)， /MREQ(允许访存， 低电平有效)——译码器使能端。R/W(高电平为读命令，低电平为写命令)。
连接时：每个芯片具有不同的地址线 (片选信号不同)，相同的数据线。

字位扩展 - 增加主存容量

image.png
上图实现了将 8 块 16K×4 位的存储芯片分为 4 组，每组 2 块 16K×4 位芯片，实现位扩展为 16K×8 位；将 4 组用一块 2-4 译码器连接，实现字扩展为 1 块 64K×8 位的主存。片内地址 A0-A13 控制访问芯片中哪块存储单元，片选地址 A14-A15 控制访问哪块芯片。

在字向和位向同时进行扩展。字位扩展可以看成先位扩展，再字扩展。
连接时：每个芯片具有不同的地址线，不同的数据线。
组内是位扩展，地址线相同，数据线不同；组间是字扩展，地址线不同 (片选信号不同)，数据线相同

补充: 3-8 译码器

image.png
CPU 先送出地址信号，待电信号稳定后，才送出存储器请求信号控制译码器使能端，使片选信号开始生效。

并行存储器

存取周期 T = 存取时间 r + 恢复时间

双端口 RAM

image.png
支持两个 CPU 同时访问 RAM
可同时读 / 写不同的存储单元；可同时读同一个存储单元；不能同时写（或者一读一写）同一个单元
若发生” 冲突 “，则发出”BUSY“信号，其中一个 CPU 的访问端口暂时关闭

多模块交叉存储器

单体多字存储器

  • 每次并行读出 m 个连续的字
  • 总线宽度也要扩展为 m 个字

多体并行存储器
image.png

  • 高位交叉编址
    • 理论上多个存储体可以被并行访问，但是由于通常都是连续访问，因此实际效果相当于单纯的扩容，并没有提高速度。

  • 低位交叉编址

    • 当存储模块数 m ≥ T/r 时，可使流水线不间断
    • 每个存储周期可读写地址连续的 m 个字
    • 连续取 n 个存储字耗时 = T+(n-1)r
    • 微观上，m 个模块被串行访问；宏观上，每个存取周期内所有模块被并行访问

      高速缓存存储器 Cache

  • 双端口 RAM、多模块存储器提高了存储器的工作速度，但优化后速度与 CPU 差距依然很大

  • cache 工作原理：将主存中某些块复制到 cache 中，缓和 CPU 与主存之间的速度矛盾
  • 局部性原理
    • 时间局部性：现在访问的地址，不久之后也很有可能被再次访问
    • 空间局部性：现在访问的地址，其附近的地址也很有可能即将被访问
  • 性能分析
    • 命中率 H：CPU 欲访问的信息已在 Cache 中的比率
    • 缺失率 (未命中率)M=1-H
    • Cache——主存 系统的平均访问时间 t 为
      • 设 tb 为访问一次 Cache 所需时间，tm 为访问一次主存所需时间
      • 先访问 Cache，若 Cache 未命中再访问主存：t=Htc+(1-H)(tc+tm)
      • 同时访问 Cache 和主存，若 Cache 命中则立即停止访问主存：t=Htc+(1-H)(tm)
  • 其他概念image.png
    • 主存与 Cache 之间以” 块 “为单位进行数据交换，多个存储单元组成一个块
    • 主存的”块 “又叫” 页 / 页框 / 页面 “；Cache 的” 块“又叫”行“
    • 主存地址可拆分为 (主存块号，块内地址) 的形式
    • 每次被访问的主存块一定会被立即调入 Cache

      Cache - 主存映射方式

      image.png
      cache 组成：有效位 (0/1)+ 标记 + 整块数据
      其中 “标记” 用于指明对应的主存块。不同的映射方式 “标记” 的位数不同。

      全相联映射

      image.png
      主存块可以放到 cache 的任意位置
      主存地址结构：块号 + 块内地址
      优点：cache 存储空间利用充分，命中率高
      缺点：查找 “标记” 最慢，有可能需要对比所有行的标记

      直接映射

      image.png
      主存块只能放到特定的某个 cache 行，行号 = 主存块号 %cache 总行数
      主存地址结构：标记 + 行号 (主存块号后几位)+ 块内地址
      优点：对于任一主存地址，只需按主存地址后几位确定 cache 行，然后对比一个 “标记”，即可确定 cache 是否命中，速度最快。
      缺点：cache 存储空间利用不充分，命中率低

      组相联映射

      image.png
      主存块可以放到特定分组中的任意位置，所属组号 = 主存块号 % 总组数
      主存地址结构：标记 + 组号 + 块内地址
      优点：另外两种方式的折中，综合效果较好
      n 路组相联映射——每 n 个 cache 行为一组

Cache 替换算法

随机算法（RAND）

  • 随便选一个主存块替换
  • 过于自由，效果很差

先进先出算法 (FIFO)

  • 优先替换最先被调入 cache 的主存块
  • 未遵循局部性原理，是从主存全局考虑的，效果差

近期最少使用算法（LRU）
image.png

  • 将最久没有被访问过的主存块替换。每个 Cache 行设置一个 “计数器”，用于记录多久没被访问
  • 基于 “局部性原理”，近期被访问过的主存块。在不久的将来也很有可能被再次访问，因此，淘汰最久没被访问过的块是合理的。
  • LRU 算法实际运行效果好，cache 命中率高
  • 硬件实现
    • 命中时，所命中行的计数器清零，比其低的计数器加 1，其余不变；
    • 未命中且还有空闲行时，新装入的行的计数器置 0，其余非空闲行全加 1；
    • 未命中且无空闲行时，计数器最大的行的信息块被淘汰，新装行的块的计数器置 0，其余全加 1。
    • 若 cache 块的总数为 2n，则计数器只需 n 位

最不经常使用算法（LFU）

  • 将被访问次数最少的主存块替换。每个 cache 行设置一个 “计数器”，用于记录被访问过多少次

  • 曾经被经常访问的主存块在未来不一定会用到，LFU 实际运行效果不好

    Cache 写策略

    写命中

  • 全写法 (写直通法)：当 CPU 对 Cache 写命中时，必须把数据同时写入 Cache 和主存，一般使用写缓冲 (write buffer)

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

写不命中

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

多级 Cache

  • 现代计算机通常采用多级 Cache 结构，各级 Cache 间常采用 “全写法 + 非写分配法”，Cache 和主存间常采用 “写回法 + 写分配法”

    页式存储器

  • 页式存储系统：一个程序在逻辑上被分为若干个大小相等的 “页面”，“页面”大小与 “块” 的大小相同。每个页面可以离散地放入不同地主存块中。

    • 操作系统将程序分 “页”
  • 逻辑地址（虚地址）：程序员视角看到的地址，也就是机器指令中的地址码（要操作的数据的逻辑地址）
    • 逻辑地址 = 逻辑页号 + 页内地址

若某程序为 4KB，主存中块大小为 1KB，则操作系统将程序分为 4 页。若要访问程序中某数据，则机器指令中地址码的前两位表示逻辑页号即数据在哪一页，后面的表示页内地址。

  • 物理地址（实地址）：数据实际在主存中的地址
    • 物理地址 = 主存块号 + 块内地址
  • CPU 访存过程：程序的逻辑地址——主存的物理地址
  • CPU 执行的机器指令中使用的是 “逻辑地址”，因此需要通过“页表” 将逻辑地址转为物理地址。
  • 页表的作用：记录了每个逻辑页面存放在哪个主存块中

image.png

  • 页表基地址是页表在主存中的物理地址，每次查页面都相当于一次访问主存，主存是 DRAM 访问速度不够快。因此增加快表，快表是一种 “相连存储器”，可以按内容寻访。
  • 快表与 Cache 区别：快表中存储的是页表项的副本；Cache 中存储的是主存块的副本

image.png

虚拟存储器

主存——辅存系统，主存中只调用辅存中一部分数据。实际并非是主存容量很大，而是利用主存——辅存系统解决了主存容量问题。所以叫做虚拟存储器
image.png
页式虚拟存储器：将程序拆分成大小相等的页面
段式虚拟存储器：按照功能模块拆分程序
段页式虚拟存储器：先分段 再分页，以页为基本传送单位，一个程序对应一个段表；一个段对应一个页表

习题

  1. 某计算机字长为 32 位，按字节编址，采用小端 (Little Endian) 方式存放数据。假定有一个 double 型变量 (8 个字节)，其机器数表示 1122 3344 5566 7788H，存放在 0000 8040H 开始的连续存储单元中，则存储单元 0000 8046H 中存放的是 ()
    A.22H
    B.33H
    C.66H
    D.77H
    解析：
    按字节编址，所以存储字长为 8 位。小端存储：低位在低地址，因为一个十六进制数为 4 位，存储字长为 8 位，一个存储单元存两个十六进制数，所以从后往前数第 13 个和第 14 个十六进制数，就是第 7 个存储单元 0000 8046H 中存储的数据。
    所以答案为 A
  1. 某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定 int 型和 short 型长度分别为 32 位和 16 位，并且数据按边界对齐存储，其 C 语言程序段如下：
    1. struct{
    2.  int a;32
    3.  char b;
    4.  short c;16
    5. }record;
    6. record.a=273;
    若 record 变量的首地址为 0xc008，则地址 0xc008 中的内容及 record.c 中的地址是（）
    A. 0x00, 0xc00d
    B. 0x00, 0xc00e
    C. 0x11, 0xc00d
    D. 0x11, 0xc00e
    解析：
    273=0001 0001 0001=111H，小端存储，所以地址 0Xc008 中内容为 11H
    按字节编址，存储字长为 8 位。a 变量为 int 型，长度为 32 位即 4 个字节，占 4 个存储单元；b 变量为 char 型，长度为 1 个字节，占 1 个存储单元； 边界对齐，即对于存放某长度为 m 字节的数据，存放地址需在 m 字节的整数倍存放，结构体整体的大小是最大成员长度的整数倍。 本题结构体最大成员为 4 字节
0xC008 0xC009 0xC00A 0xC00B
record.a(0x11) record.a(0x01) record.a(0x00) record.a(0x00)
0xC00C 0xC00D 0XC00E 0XC00F
record.b record.c record.c

所以答案为 D

  1. 存储容量：32M×16 位需要多少数据线？多少地址线？
    2G×32 位需要多少数据线？多少地址线？
    解析：
    32M×16b=2^25×2^4，所以需要 25 条地址线，4 条数据线
    2G×32b=2^31×2^5，所以需要 31 条地址线，5 条数据线
  1. 说明 1M×1 位 DRAM 片子的刷新方法，刷新周期定为 8ms，读写周期为定为 1 µs。(1M 芯片排列为 1024×1024)
    解析：
    如果行地址为 A9~A0，一行上有 1024 个存储元，在 8ms 内必须完成 1024 个行的刷新。
    刷新方式可采用集中刷新方式 ，用 8000-1024=6976µs 进行读写周期，用 1024µs 进行刷新。
    刷新方式还可采用异步刷新方式：8000µs/1024=7.8125µs，按 7.8µs 刷新一行的异步刷新方式
  1. 下列有关 RAM 和 ROM 得叙述中正确的是（）
    I. RAM 是易失性存储器，ROM 是非易失性存储器
    II. RAM 和 ROM 都是采用随机存取方式进行信息访问
    III. RAM 和 ROM 都可用做 Cache
    IV . RAM 和 ROM 都需要进行刷新
    A. 仅 I 和 II
    B. 仅 II 和 III
    C. 仅 I ，II， III
    D. 仅 II，III，IV
    解析：
    易失性：断电后信息是否保存，I 对；RAM 和 ROM 都是采用随机存取方式进行信息访问 ，II 对；ROM 是只读存储器不用作 cache，III 错；SRAM 不是破坏性读出，不需要刷新，IV 错
    所以答案为 A
  1. 下列各类存储器中，不采用随机存取方式的是（）
    A. EPROM
    B. CDROM
    C. DRAM
    D. SRAM
    解析：
    EPROM 是可擦除可编程只读存储器，采用随机存取方式；CDROM 是光盘只读存储器，不是随机存取方式；RAM 是随机存取存储器
    所以答案为 B
  1. 下列关于闪存（flash memory）的叙述中，错误的是（）
    A. 信息可读可写，并且读、写的速度一样
    B. 存储元由 MOS 管组成，是一种半导体存储器
    C. 掉电后信息不丢失，是一种非易失性存储器
    D. 采用随机访问方式，可替代计算机的外部存储器
    解析：
    闪存要先擦除才能写，所以写比读慢，A 错
    所以答案为 A
  1. 用 2114（1K×4）的存储芯片组成 8K×8 存储器，设计步骤如下（需要进行字扩展及位扩展）
    解析：
    1. 确定所需该芯片的个数：8K×8/(1K×4)=16(片)
    2. 字位扩展，确定地址线，数据线个数：位由 4 扩展到 8，一组 2 个芯片，共 8 组，数据线 8 根 (D0-D7)；单个芯片字长 1K，片内地址线 10 根 (A0-A9)；8 组，片选地址线 3 根 (A10-A12)。总计 16 根地址线，8 根数据线。
    3. 连线
    image.png

9.CPU 的地址总线 16 根 (A15—A0，A0 为低位)，双向数据总线 8 根 (D7— D0)，控制总线中与主存有关的信号有 / MREQ(允许访存， 低电平有效)， R/W(高电平为读命令，低电平为写命令)。主存地址空间分配如下：0—8191 为系统程序区，由只读存储芯片组成；8192—32767 为用户程序区；最后 (最大地址)2K 地址空间为系统程序工作区。上述地址为十进制，按字节编址。
现有如下存储器芯片：
EPROM：8K×8 位 (控制端仅有 / CS);
SRAM：16K×1 位，2K×8 位，4K×8 位，8K×8 位.
问 1： 请从上述芯片中选择适当芯片设计该计算机主存储器，
问 2 ： 画出主存储器逻辑框图，注意画出选片逻辑 (可选用门电路及 3∶8 译码器 74LS138) 与 CPU 的连接，说明选哪些存储器芯片，选多少片。
解析：
(1)
8192/1024=8K，因为是系统程序区，所以选 1 片 8K 的 EPROM；(32767-8192)/1024=24K，因为是用户程序区，所以选 3 片 8K 的 SRAM；因为是 2K 的系统程序工作区，所以选 1 片 2K 的 SRAM
(2)
CPU 提供地址线 16 根，数据线 8 根，控制总线 2 根。
此题属于位扩展。数据线 8 根 (D0-D7)；控制总线 2 根 (/MREQ，R/W)；最大单个芯片为 8K，片内地址线 13 根 (A0-A12)；片选地址线 3 根 (A13-A15)
image.png

  1. 设 CPU 有 16 根地址线，8 根数据线，并用 MREQ 作为访存控制信号（低电平有效），用 WR 作为读写控制信号（高电平为读、低电平为写）。现有下列存储芯片：
    1K×4 位 RAM、 4K×8 位 RAM、8K×8 位 RAM、2K×8 位 ROM、4K×8 位 ROM、8K×8 位 ROM
    74138 译码器和各种门电路。
    画出 CPU 与存储器的连接图，要求如下：
    ①主存地址空间分配： 6000H～67FFH 为系统程序区。 6800H～6BFFH 为用户程序区。
    ②合理选用上述存储芯片，说明各选几片。
    ③详细画出存储芯片的片选逻辑图
    解析：
    67FFH-6000H+1=7FFH=0111 1111 1111+1=1000 0000 0000=211=2K，因为是系统程序区，所以选 1 个 2K 的 ROM
    6BFFH-6800H+1=210，因为是用户程序区，所以选 2 个 1K×4 位的 RAM 为一组将位扩展位 8 位
    数据线 8 根 (D0-D7)；最大单个芯片是 2K，片内地址线 11 根 (A0-A10)；因为只有 3-8 译码器，所以片选地址线 3 根 (A11-A13)；使能端 3 根 (A14-A15、MREQ)；读写控制线 1 根 (WR)
    image.png
  1. 某计算机字长 32 位，存储容量 256MB，若按字编址，它的寻址范围是（）
    A. 1M
    B. 512KB
    C. 64M
    D. 256KB
    解析：
    按字编址，字长 32 位，存储容量 256MB，则存储字数为 256MB/32b=228B/22B=226B=64MB
    所以答案为 C
  1. 某计算机字长 32 位，存储容量 4GB，若按双字编址，它的寻址范围是（）
    A. 4G
    B. 0.5G
    C. 8G
    D. 2G
    解析：
    按双字编址，单字长 32 位，双字 64 位，则存储字数为 4GB/64b=232B/8B=229B=0.5GB
    所以答案为 B
  1. 某 DRAM 芯片，其存储容量为 512K×8bit，则该芯片的地址线和数据线数目为（）
    A. 8,512
    B. 512,8
    C. 18,8
    D. 19,8
    解析：
    512K=219,19 根地址线
    所以答案为 D
  1. 假定用若干个 2K×4 位芯片组成一个 8K×8 为存储器, 则 0B1FH 所在芯片的最小地址是（）
    A. 0000H
    B. 0600H
    C. 0700H
    D. 0800H
    解析：
    位扩展 4 位到 8 位，每组 2 个 2K×4 位；字扩展 2K 到 8K，4 组；2 位片选信号，11 位片内信号。
    0B1FH=0000 1011 0001 1111，片选信号为 01，即第二组芯片，每组芯片寻址范围为 2K=211，所以第二组芯片寻址范围最小为 211=0000 1000 0000 0000 = 0800H
    所以答案为 D
  1. 某一 RAM 芯片，其容量为 128K×16 位。除电源和接地端外，该芯片引出线最小数目为 ()
    A.33
    B.35
    C.17
    D.12
    解析：
    128K=217，片内地址 17 根，16 位，数据线 16 根
    所以答案为 A
  1. 设存储器容量为 32 字，字长 64 位，模块数 m=4，分别用顺序方式和交叉方式进行组织。存储周期 T=200ns，数据总线宽度为 64 位，总线传送周期τ=50ns。问顺序存储器和交叉存储器的带宽各是多少?
    解析：
    模块数为 4，假设访问 4 个字，字长 64 位，共 256b
    1ns=10-9s
    顺序存储器所需时间：4T=800ns=8×10-7s，带宽：256b/(8×10-7s)=3.2×108b/s
    交叉存储器所需时间：T+(4-1)τ=350ns=3.5×10-7s，带宽：256b/(3.5×10-7s)≈7.3×108b/s

17.CPU 执行一段程序时，cache 完成存取的次数为 1900 次，主存完成存取的次数为 100 次，已知 cache 存取周期为 50ns， 主存存取周期为 250ns，求 cache / 主存系统的效率和平均访问时间
解析：
cache 命中率 h=1900/(1900+100)=0.95
cache / 主存系统的平均访问时间 t=0.95×50ns+0.05×250ns=60ns
cache / 主存系统的效率 e=50ns/60ns≈0.833

  1. 设有一个 cache 的容量为 2k 字，每行为 16 字，求：
    1. 该 cache 可容纳多少个行?
    2. 如果主存容量为 256k 字，则有多少个块?
    3. 主存的地址有多少位？Cache 的地址有多少位？
    4. 在直接映射方式下，主存中的第 i 块映射到 Cache 中的哪一个行中？
    5. 进行直接地址映射时，存储器的地址分成哪几段？各段分别有多少位?
    解析：
    (1)2K/16=27，该 cache 可容纳 27 个行
    (2)256K/16=214 个块
    (3)256K=218，主存地址 18 位；2K=211，cache 地址 11 位
    (4)i%27，
    (5)由 (2) 知主存块数 214 个块，所以块号 14 位；由 (1) 知 cache 行数 27 个行，所以块号可细分为前 7 位是标记号，后 7 位是行号；主存的地址共 256K=218，即 18 位，所以块内地址 4 位。综上，存储器地址可分成 3 段：标记 7 位，行号 7 位，块内地址 4 位。
  1. 一个容量为 4 个行的全相联 cache，设访问的主存地址块号序列为 2，11，2，9，7，6，4，3 在先进先出替换方式下， cache 中的内容变化情况为
    解析：
访问主存块 2 11 2 9 7 6 4 3
cache #0 2 2 2 2 2 6 6 6
cache #1 11 11 11 11 11 4 4
cache #2 9 9 9 9 3
cache #3 7 7 7 7
  1. 一个容量为 4 个块的全相联 cache，设访问的主存地址块号序列为 2， 11，2，9，7，6，4，3 在近期最少使用法替换方式下，cache 中的内容变化情况为：
    解析：
访问主存块 2 11 2 9 7 6 4 3
cache #0 2 2 2 2 2 2 4 4
cache #1 11 11 11 11 6 6 6
cache #2 9 9 9 9 3
cache #3 7 7 7 7
  1. 设主存容量 512KB，Cache 容量 4KB，每个块 16 个字， 字长 32 位。
    （1）Cache 地址多少位？Cache 共有多少行？
    （2）主存地址多少位？可容纳多少个块？
    （3）在直接地址映射方式下，主存的第几个块映射到 Cache 中的第 5 块？
    （4）画出直接映射方式下主存地址地段中各段的位数？
    解析：
    (1)cache 容量 4K×8 位，4K=212cache 地址 12 位；4KB/(16×32b)=26，共 26 个行
    (2) 主存容量 512K×8 位，512K=219，主存地址 19 位；512KB/(16×32b)=213，共 213 个块
    (3)i%26=5，则 i=n64+5(n=0,1,2,3,……)
    (4) 块号 13 位 (标号 7 位，行号 6 位)，块内地址 6 位
  1. 设主存容量 512K×16 位，Cache 容量 4096×16 位，块长 4 个 16 位的字，访存地址为字地址。
    （1）直接映射方式下，设计主存的地址格式。
    （2）全相联映射方式下，设计主存的地址格式。
    （3）二路组相联映射方式下，设计主存的地址格式。
    （4）四路组相联映射方式下，设计主存的地址格式
    解析：
    (1)512K=219，主存地址共 19 位；512K×16b/(4×16b)=217，主存可容纳 217 个块，块号 17 位；4096×16b/(4×16b)=210，cache 共有 210 个行；标号 7 位，行号 10 位，块内地址 2 位
    (2)由 (1) 知，块号 17 位，块内地址 2 位
    (3)由 (1) 知，cache 共 10 行，2 行 1 组，可分为 29 个组；标号 8 位，组号 9 位，块内地址 2 位
    (4)由 (1) 知，cache 共 10 行，4 行 1 组，可分为 28 个组；标号 9 位，组号 8 位，块内地址 2 位
  1. 某计算机 Cache 共有 16 块，采用 2 路组相联映射方式 (即每组 2 块)。每个主存块大小为 32 字节，按字节编址。主存 129 号单元所在的主存块应装入到 Cache 的组号是：()
    A、0
    B、2
    C、4
    D、6
    解析：
    16/2=8，8 个组。每个主存块大小为 32 字节，按字节编址，则 1 块 32 个存储单元；128/32=4，所以主存 129 号存储单元在第 5 块；5%8=5，所以应装入第五组，也就是 cache #4
    所以答案为 C
  1. 假设计算机的存储系统由 Cache 和主存构成。某执行过程访存 1000 次，其中 Cache 访问缺失（未命中）50 次，则 Cache 的命中率是（）
    A. 5%
    B. 9.5%
    C. 50%
    D. 95%
    解析：
    1-50/1000=0.95
    所以答案为 D
  1. 假设某计算机按字编址，Cache 有四个行， Cache 与主存之间交换的块为 1 个存储字。若 Cache 的内容初始为空，采用 2 路组相联的映射方式和 LRU 替换策略。访问的主存地址是 0,4,8,2,0,6,8,6,4,8 时，命中 Cache 的次数是（）
    A. 1
    B. 2
    C. 3
    D. 4
    解析：
    2 路组相联，#0#1 一组，#2#3 一组，LRU 近期最少使用算法
访问的主存地址 0 4 8 2 0 6 8 6 4 8
cache #0 0 0 8 8 0 0 8 4 4
cache #1 4 4 2 2 6 6 6 8
cache #2
cache #3
是否命中 命中

所以答案为 A
补充：本题为 2012 年考研题，标准答案给的 C。因为当时教材中组相联映射方法与如今有些许区别，本题我以如今统一的组相联映射方法作答。
相关链接：
关于该问题的讨论 1
关于该问题的讨论 2
关于该问题的讨论 3

  1. 假定主存地址为 32 位，按字节编址，主存和 Cache 之间采用直接映射方式，主存块大小为 4 个字，每字 32 位，采用回写（Write Back）方式，则能存放 4K 字数据的 Cache 的总容量的位数至少是（）
    A．146k
    B．147K
    C．148K
    D．158K
    解析：
    主存容量 232×8 位，主存地址共 32 位；232×8b/4×32b=228，块号 28 位；4K 字 / 4 字 = 210，cache 共 210 行，标记 18 位，行号 10 位；
    cache 总容量 = 存储容量 + 标记阵列容量，标记阵列容量包括 4 种标记：标记位、有效位、一致性维护位 / 脏位、替换算法控制位。有效位和标记位是一定有的，而一致性维护位（脏位）和替换算法控制位的取舍标准是看题眼，题目中，明确说明了采用写回法，则一定包含一致性维护位，而关于替换算法的词眼题目中未提及，所以不予考虑。
    cache 存储容量：4K 字 = 4K×32b=27Kb
    每行标记阵列：标记 18 位，有效位 1 位，脏位 1 位，共 20 位
    cache 共 210 行，所以标记阵列容量为：210×20=20Kb
    故 cache 总容量 = 27Kb+20Kb=148Kb
    所以答案为 C
  1. 有如下 C 语言程序段：
    for (k=0; k<1000; k++)
    a[k]=a[k]+32;
    若数组 a 及变量 k 均为 int 型，int 型数据占 4B，数据 cache 采用直接映射方式，数据区大小为 1KB、块大小为 16B， 该程序段执行前 cache 为空，则该程序段执行过程中访问数组 a 的 cache 缺失率约为
    A.1.25%
    B.2.5%
    C.12.5%
    D.25%
    解析：
    a[k] 的访问步骤是：先访问 cache，cache 缺失，之后从主存中取出一个块调入 cache，由于数组在内存中是连续存放，所以这个块中的后几个数据都是命中的。本题中一个 int 数据占 4B，一个块大小是 16B，这说明一个块中有 4 个 int 数据，关键是后面还有一次写操作，这说明一次循环要八次访问 cache，其中只有第一次是缺失的，后面七次都是命中的，所以缺失率是 1/8=12.5%；
    所以答案为 C
  1. 假定主存地址位数为 32 位，按字节编址，主存和 cache 之间采用直接映射，主存块大小为一个字，每字 32 位，写操作时采用直写法（write through）, 则能存放 32K 字数据的 cache 的总容量至少应为（ ）位。
    A.1504K
    B.1536K
    C.1568K
    D.1600K
    解析：
    cache 存储容量：32K×32b=210Kb=1024Kb
    主存块大小为一个字，每字 32 位，按字节编址，一块 4 个字节，块内地址 2 位；32K 字 / 1 字 = 32K=215，行号 15 位；主存地址为 32 位，所以标号 32-15-2=15 位；有效位 1 位，直写法无脏位，无替换算法控制位；
    cache 标记阵列容量 215×16b=512Kb；
    cache 总容量：：1024Kb+512Kb=1536Kb
    所以答案为 B
  1. 假定主存地址位数为 32 位，按字节编址，主存和 cache 之间采用直接映射，主存块大小为一个字，每字 32 位写操作 时采用回写法（write back）, 则能存放 32K 字数据的 cache 的总容量至少应为（ ）位。
    A.1504K
    B.1536K
    C.1568K
    D.1600K
    解析：
    与上题不同点在于使用了回写法，故多了脏位 1 位
    cache 标记阵列容量 215×17b=544Kb；
    cache 总容量：1024Kb+544Kb=1568Kb
    所以答案为 C
  1. 假定主存按字节编址，cache 共有 64 行，采用 4 路组向量映射方式，主存块大小为 32B, 所有编号从 0 开始。主存第 2593 号单元所在的主存块会映射到 cache 的第（ ）组。
    A.1
    B.17
    C.34
    D.81
    解析：
    cache 可分为 16 组，每组 4 行；主存按字节编址，即一个存储单元存储一个字节；一块 32B，32 个字节，即一块是 32 个存储单元。2592/32=81，所以 2593 单元在第 82 块，编号为 81；81%16=1
    所以答案为 A

image.png
31. 某计算机的主存地址空间大小为 256M，按字节编址。 指令 cache 和数据 cache 分离，均有 8 个 Cache 行，每个 Cache 行大小为 64B，数据 Cache 采用直接映射方式，现有两个功能相同的程序 A 和 B，其伪代码如下：
假定 int 类型数据用 32 位补码表示，程序编译时 i，j，sum 均分配在寄存器中，数组 a 按行优先方式存放，其地址为 320(十进制)。请回答，要求说明理由或给出计算过程。
(1)、若不考虑用于 Cache 一致维护和替换算法的控制位， 则数据 Cache 的总容量为多少?
(2)、数组元素 a[0] [31] 和 a[1] [1] 各自所在的主存块对应的 Cache 行号分别是多少 (Cache 行号从 0 开始)
(3)、程序 A 和 B 的数据访问命中率各是多少？哪个程序的执行时间短?
解析：
(1)
cache 存储容量：64B×16=210B
主存地址 28 位；256M×8b/64×8b=222, 块号 22 位；标号 18 位；行号 4 位；块内地址 6 位
标号 18 位，有效位 1 位，cache 标记阵列容量：16×19b=38B
cache 总容量：210B+38B=1062B
数据 cache 总容量：1062/2=531B
(2)
数组 a 按行优先方式存放，其地址为 320(十进制)。按字节编制，一个存储单元存储 1 个字节，a[0] [31] 所在存储单元：320+31×4=444；一块 64B，即一块 64 个存储单元；444/64=7 块，即 a[0] [31] 在第 7 块，块号为 6，6%8=6，即 a[0] [31] 所在主存块对应的 cache 行号是 6
a[1] [1] 所在存储单元：320+257×4=1348，1348/64=22 块，块号 21，21%8=5，即 a[0] [31] 所在主存块对应的 cache 行号是 5
(3)
每块 16 个 int，每次不命中时调入 16 个元素，后面连续 15 个都命中，程序 A 的命中率为：15/16×100%=93.75%
程序 B 列优先计算 a[0] [0]，a[1] [0]，a[2] [0]，……… 每次连 续计算的元素肯定不在同一个调入 cache 的块，每次都不命中， 命中率为 0%

  1. 假设有三道程序 (用户标志号为 A，B，C)，其基址寄存器内容分别 为 SA，SB，SC ，在主存中，每道程序都有一张段表，A 程序有 4 段，C 程序有 3 段。每段应有一张页表，段表的每行就表示相应页表的起始位置， 而页表内的每行即为相应的物理页号。请说明虚实地址变换过程。
    解析：
    image.png
    ①根据基号 C 执行 SC 加 1（段号）操作，得到段表相应行地址， 其内容为页表的起始地址ｂ。
    ②执行 b+2（页号），得到物理页号的地址，其内容即为物理页 10。
    ③物理页号与页内地址拼接即得物理地址。
    如计算机只有一个基址寄存器，基号可不要，多道程序切换时，操作系统修改基址寄存器内容。 可以看出，段页式虚拟存储系统由虚拟地址向主存地址的变换至少需要查两次表。
  1. 假设主存只有 a,b,c 三个页框，组成 a 进 c 出的 FIFO 队列，进程访问页面的序列是 0，1，2，4，2，3，0，2，1，3，2 号。若采用①FIFO 算法， ②FIFO 算法 + LRU 算法，用列表法分别求两种替换策略情况下的命中率
    解析
    FIFO 算法，先进先出
访问页面的序列 0 1 2 4 2 3 0 2 1 3 2
a 0 0 0 4 4 4 2 2 2
b 1 1 1 3 3 3 1 1
c 2 2 2 0 0 0 3
是否命中 命中 命中

命中率：2/11≈0.182
LRU 算法，近期最少使用

访问页面的序列 0 1 2 4 2 3 0 2 1 3 2
a 0 0 0 4 4 0 0 3
b 1 1 1 3 3 1 1
c 2 2 2 2 2 2
是否命中 命中 命中 命中

命中率：3/11≈0.273

image.png
34. 某计算机的页式虚存管理中，采用长度为 32 字的页，页表内容如下， 求当 cpu 程序按下列 2 进制虚拟字地址访问存储器时产生的实地址为多少？
（1）00001101
（2）10000000
（3）00101000
解析：
由表知虚页号 3 位；由选项知，页内地址 8-3=5 位。
逻辑地址：虚页号 3 位 + 页内地址 5 位；物理地址：实页号 3 位 + 页内地址 5 位
(1)00001101——0101101
(2)10000000——1000000
(3)00101000——缺页，需要从虚拟存储器调入主存

  1. 下列命令组合情况，一次访存过程中，不可能发生的是（）
    A. TLB 未命中，Cache 未命中，Page 未命中
    B. TLB 未命中，Cache 命中，Page 命中
    C. TLB 命中，Cache 未命中，Page 命中
    D. TLB 命中，Cache 命中，Page 未命
    解析：
    TLB 中数据由 Page 项复制调入，若 TLB 命中则 Page 一定会命中
    所以答案为 D

image.png
36. 某计算机主存地址空间大小为 256MB，按字节编址。虚拟地址空间大小为 4GB，采用页式存储管理，页面大小为 4KB， TLB（快表）采用全相联映射，有 4 个页表项，内容如下表所示：
则对虚拟地址 03FF F180H 进行虚实地址变换的结果是（）
A. 015 3180H
B. 008 5180H
C. TLB 缺页
D. 缺页
解析：
03FFFH——015 3180H
所以答案为 A

  1. 假定编译器将赋值语句 “x=x+3;” 转换为指令”add xaddt, 3”，其中 xaddt 是 x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的 TLB，且 Cache 使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（）
    A．0
    B．1
    C．2
    D．3
    通过查 TLB 获得实页号拼接页内地址获得主存物理地址，访问 cache 命中，用直写法直接写入 cache 和主存
    所以答案为 B

image.pngimage.png
38. 某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为 16MB，主存（物理）地址空间大小为 1 MB，页面大小为 4 KB；Cache 采用直接映射方式，共 8 行；主存与 Cache 之间交换的块大小为 32 B。 系统运行到某一时刻时，页表的部分内容和 Cache 的部分内容分别下两图所示，图中页框号及标记字段的内容为十六进制形式。
请回答下列问题。
（1）虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位， 哪几位表示页框号（物理页号）？
（2）使用物理地址访问 Cache 时，物理地址应划分成哪几个字段？ 要求说明每个字段的位数及在物理地址中的位置。
（3）虚拟地址 001C60H 所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否 Cache 命中？ 要求说明理由。
（4）假定为该机配置一个 4 路组相联的 TLB，该 TLB 共可存放 8 个页项，若其当前内容（十六进制）如下图所示，则此时虚拟地址 024BACH 所在的页面是否在主存中？要求说明理由。
解析：
(1) 因为虚拟（逻辑）地址空间大小为 16MB，按字节编址，所以虚拟地址共有 24 位；因为页面大小为 4 KB，16MB/4KB=212 个页，所以虚页号是虚拟地址前 12 位，页内地址是虚拟地址后 12 位；
按字节编址，主存 1MB=220B，物理地址共 20 位，前 8 位是物理页号，后 12 位是页内地址
(2)Cache 采用直接映射方式，共 8 行；主存与 Cache 之间交换的块大小为 32 B，块内地址 5 位，行号 3 位，标号 12 位
综上，划分三个字段，最前面 12 位标号，中间 3 位行号，最后 5 位块内地址
(3)001C60H——04C60H，虚页号为前 12 位，即 001H=1。查表可知，有效位为 1，在主存中；物理地址为 04C60H；0000 0100 1100 0110 0000，行号 011=3，标记位 04CH≠105H，未命中
(4)4 路组相联，共 8 个页项，可分为 2 组，组号 1 位；0000 0010 0100 1011 1010 1101，组号为 0，标号 012H；由图可得有效位为 1，故虚拟地址 024BACH 所在的页面在主存中。

image.png
39. 某计算机采用页式虚拟存储管理方式， 按字节编址。CPU 进行存储访问过程如图所示
回答下列问题。
（1）主存物理地址占多少位？
（2）TLB 采用什么映射方式？TLB 用 SRAM 还是 DRAM 实现？
（3）cache 采用什么映射方式？若 cache 采用 LRU 替换算法和回写（Write Back）策略，则 cache 每行中除数据（Data）、Tag 和有效位外，还应有哪些附加位？ Cache 总容量是多少？Cache 中有效位的作用是什么？
（4）若 CPU 给出的虚拟地址是 0008 C040H，则对应的物理地址是多少？是否在 cache 中命中？说明理由。 若 CPU 给出的虚拟地址是 0007 C260H，则该地址所在的主存块映射到 Cache 的组号是多少？
解析：
(1) 由图知，主存物理地址占 28 位
(2) 由图知，TLB 中每项都有一个比较器，故 TLB 采用全相联映射方式。TLB 采用 SRAM 实现。
(3)Cache 中每组有两行，故采用 2 路组相联映射方式。 因为 2 路组相联并采用 LRU 替换算法，所以每行（或每组） 需要 1 位 LRU 位；因为采用回写策略，所以每行有 1 位修改位（脏位）
组号 3 位，2 路组相联映射，所以 cache 共 16 行；块内地址 5 位，按字节编址，所以 cache 存储容量 16×25B=29B
cache 标号阵列容量 =(20+1+1+1)b×16=46B
cache 总容量 = 29B+46B=558B
有效位用来指出所在 Cache 行中的信息是否有效
(4) 虚页号 20 位 = 0008CH，对应物理地址为 0040040H；0000 0000 0100 0000 0000 0100 0000，组号 010=2，标号 00400H，有效位为 0，cache 未命中。
虚拟地址 0007 C260H=0000 0000 0000 0111 1100 0010 0110 0000，组号 011=3