3 存储器层次结构

【随机存取】

随机存取就好像素数可以通过下标直接访问需要的元素。ROM 和 RAM 都是采用随机方式访问信息，ROM 只能进行取，RAM 可取可存

【存储器的分类】

关于此图，做如下几点注释：

1. CDROM 用户只能读出不能修改或写入新的内容，非常类似 ROM 的特性，故称只读型光盘为 CDROM，但其本质与 ROM 不同
2. Flash 从原理上讲仍属于 ROM，是 EEPROM 的改进产品

【闪存（Flash Memory）】

1. 信息可读可写，但是读写速度是不一样的：闪存必须在空白区域写，如果目标区域已经有数据，先擦除后写，而读不必如此
2. 存储单元为 MOS 管，是半导体存储器
3. 断点信息不丢失，是非易失性存储器
4. 随机访问，可替代外部存储器

【相联存储器】

根据存储内容（不需要地址）来进行存取的存储器称为相联存储器（即 TLB）

【RAM / ROM】

1）RAM

RAM 的缺点是断电信息丢失，分静态 RAM 和动态 RAM，静态 RAM 做 Cache，动态 RAM 做主存，都是易失性 RAM

2）ROM

断点后内容可保留，一般把一些固定的、不变的程序存放在这里，ROM 和 RAM 一起构成了主存

3）一些总结

1. 存放系统程序或各类常数使用 ROM 芯片，存放用户程序应该选用 RAM 芯片
2. SRAM 常用作 Cache，DRAM 和 ROM 用作主存

【存储容量】

记住这个公式，$存储容量=存储字数\times 字长$

【带宽的概念】

带宽衡量数据传输速度，表示单位时间内存取的信息量

△☼▽ （3 通道存储总线）

分析：B,总带宽为 3×8×1333MB/s ≈ 32GB/s

△☼▽

分析：每一个时钟周期为 $1/50MHz=20ns$

（1）一次读所花费的时间为 $(1+3+8)\times 20ns=240ns$，故存储器的带宽为 $$\frac{32B}{240ns}\approx 133.3MB/s$$（2）同理 $$\frac{32B}{(1+2+8+3)\times 20ns}\approx 114.3MB/s$$（3）$$\frac{32B}{0.65\times 240ns+0.35\times 280ns}\approx 126.0MB/s$$

【SRAM / DRAM】

1）半导体存储芯片的基本结构

考察芯片引出线：地址线 + 数据线 + 1 根读写控制线 + 1 根控制线

△☼▽

分析：D，数数据线 8 根，地址线 9 根，外加 1 根读写控制线和 1 根片选线，一共 19 根

2）半导体存储芯片的译码驱动方式

① 线选法（单译码）

一个编码结果选中一行

• （算地址线）假设该矩阵有 $N$ 行，然后就可以通过公式 $\lceil lo{g}_{2}N\rceil$ 算出地址线所需要的根数
• （算译码输出线）如果输入线有 $n$ 根，则译码需要 $2^n$ 根输出线
  

② 重合法（双译码）

需要行地址线和列地址线选中存储矩阵中的一个元素

• （算地址线）如果存储矩阵是 $N\times N$，则一共需要 $2\lceil lo{g}_{2}N\rceil$ 根地址线

③ 千万注意，DRAM 采用地址复用技术，行列地址分两次传送

△☼▽（2018年真题）

分析: C，DRAM 采用行列地址复用技术，我们应使得行列差值不可太大，排除 A、D 选项，看 C、D 选项，地址线仅需要 6 根（因为地址复用，只用取行或列所需地址线的最大值，都是 64）；其次，DRAM 的刷新按行进行，要求减小刷新开销，即行数尽量小

3）一些总结内容

1. RAM 是易失性 RAM，但不意味只要电源不断存储信息就不会丢失，DRAM 需要定期刷新
2. SRAM 的读出是非破坏性读出，DRAM 的读出是破坏式读出，因此读后需要再生

【刷新】

1）集中刷新

（认真分析下面的例子，即是考察集中刷新的一个角度）

假设电容上的电荷基本只能维持 2 ms，在 2ms 内必须要刷新一次。假设存储周期为 0.5us，那么在一个刷新周期里有 4000 个存储周期。假设该存储矩阵有 32 行，则对 32 行集中刷新需要 16us，刷新的时候是不能进行读/写操作的，于是可以计算出死区的占用比例为 32/4000=0.8%

2）分散刷新

扩展定义，

$$存储周期=读或写周期+刷新一行的时间$$

此时，存储周期为读或写周期的两倍，此处刷新一行的时间又看成是等于存储周期的

由上可知，分散刷新将存储器的存储周期人为地延长了，因此严重降低了系统的速度

3）异步刷新

对于 128x128 的存储芯片，如果要在 2ms 内刷新一遍，即每隔 15.6us（2000us/128≈15.6us）刷新一行，而每行刷新的时间仍然等于一个读/写周期

异步刷新的死时间为一个读/写周期

△☼▽

分析：刷新都是从单个芯片的存储矩阵入手（刷新按行进行，且整个存储器中的所有芯片的相同行同时进行刷新）

1）$2000us/64=31.25us$，可取相邻两行之间的刷新为 $31.25us$
2）采用集中刷新方式，存储器刷新一遍最少用 $64$ 个周期，死区时间为 $0.5us\times 64=32us$，死时间率为 $32us/2000us\times 100\%=1.6\%$

【再生和刷新】

• 再生： 随机的，某个存储单元只有在破坏性读出之后才需要再生，一般是按存储单元进行

• 刷新： 定时的，许多记忆单元长期未被访问而需要刷新，以存储体矩阵中的一行为单位进行

（注意以存储体矩阵中的一行为单位 ，如芯片内部采用 128×128 的存储阵列，问所有存储单元刷新一遍需要多少个存储周期，即 128 个存储周期）

【存储周期、存取时间和储存时间】

• 存储周期： 连续两次启动同一存储所需的最小时间间隔

• 存取时间： 从上一次启动存储器到完成读写操作为止，一般小于存储周期，包括读出时间和写入时间

• 存储时间： 即写入时间

【图形显示下的存储器容量计算】

下题的第一小问即为此类计算问题的理论所在

△☼▽

分析：（1）在图形方式中，每个屏幕上的像素都是由存储器中的存储单元的若干比特指定其颜色。每个像素所占用的内存位数决定于能用多少种颜色表示一个像素。每个像素的颜色数 $m$ 和每个像素所占用存储器的比特数 $n$ 之间的关系是：$$n=lo{g}_{2}m$$（2）由于显示缓冲存储器的容量应该按照最高灰度（65536色）计算，故容量为 $$\frac{640\times 480\times lo{g}_{2}65536bit}{8}=614400B$$

【芯片】

1）存储基元

（问一个 $a\times b$ 的芯片有多少存储基元）

对 $64K\times 8$ 位的芯片，该芯片的存储基元（同基本单元电路）总数为 $512K=2^{19}$

2）地址线和数据线

设地址线为 $a$，数据线为 $b$，则片容量为 $2^a\times b$，在片容量固定的情况下，片字数越少，片字长越长，引脚数越多（下面一道题会解释这句话）

△☼▽

分析：存储基元总数 = $64K\times 8位=512位=2^{19}位$

要求 $2^a\times b=2^{19}$，

$a=19,b=1,总和为20$
$a=18,b=2,总和为20$
$a=17,b=4,总和为21$
$a=16,b=8,总和为24$
$\cdots$

令 $F(a)=a+b=a+2^{19-a}$，$F^{\prime }(a)=1-2^{19-a}ln2$，当 $1⩽a⩽18$ 时，$F$ 单减，故 $F_{min}=F(19)=F(18)$

故，有两种方案：地址线 19 根，数据线 1 根；或地址线 18 根，数据线 2 根

【片选信号】

1）片选信号的产生

以一道题为例，地址线 A₁₅ ~ A₀，若用 16K × 1 位芯片构成 64KB 存储器，由地址码 A₁₅, A₁₄ 译码产生片选信号

为什么？

用 16K × 1 位芯片构成 64KB 存储器需要 4×8 片芯片，每 8 片芯片为一组，总共 4 组，需要两位做片选信号，64K = 2¹⁶，16 位地址，16K = 2¹⁴，A₁₃ ~ A₀ 为每个模块提供地址，A₁₅ ~ A₁₄ 通过 2-4 译码器产生片选信号

2）片选信号的确定

注意两个点，

1. 是先编址 ROM 还是先编址 RAM
2. 字扩展占据一个片选信号，位扩展一组占据一个片选信号

【芯片地址】

1）没有规定片选信号

以 8 片 2K × 4 位芯片组成一个 8K × 8 位存储器为例，分 4 组，每 2 片 2K × 4 构成 1 片 2K × 8，2K = 2¹¹，8K = 2¹³，选取第 12、13 位做片选信号，于是，

△☼▽（模拟题一）

分析：C，具体分析如下

2）规定片选信号

△☼▽

分析：
（1）每一组芯片的容量为 1K × 8 位，即 1KB，故需要 10 根地址线，地址范围为 000H ~ 3FFH
（2）存储器容量为 4KB，有 12 位，由图可知，规定各组芯片的片选端由 A₁₅ 和 A₁₄ 进行译码，芯片组内地址线为 A₉ ~ A₀，A₁₃ ~ A₁₀ 空闲，假设 A₁₃ ~ A₁₀ 全为 0，于是


第一组的寻址范围为 0000H ~ 03FFH
第二组的寻址范围为 4000H ~ 43FFH
第三组的寻址范围为 8000H ~ 83FFH
第四组的寻址范围为 C000H ~ C3FFH

3）由于 A₃ ~ A₁₀ 没有参与译码（部分译码），故会产生地址重叠现象

【全译码/部分译码】

1）全译码法

全译码法将除片内寻址外的全部高位地址线都作为地址译码器的输入，译码器的输出作为各芯片的片选信号，将它们分别接到存储芯片的片选端，以实现对存储芯片的选择

全译码法的优点是：每片芯片的地址范围是唯一确定的，而且是连续的，也便于扩展，不会产生地址重叠的存储区，但全译码法对译码电路要求较高

2）部分译码法

所谓部分译码法即用除片内寻址外的高位地址的一部分来译码产生片选信号，部分译码法会产生地址重叠

【寻址范围】

1） $寻址范围=\frac{存储器容量}{一地址大小}$，注意是按字节编址还是按字编址

2）若知地址反推存储器容量

△☼▽

分析：0CBFFFH + 1 - 0A4000H = 28000H = 0010 1000 0000 0000 0000 = 2¹⁷+2¹⁵ = 160KB

3）最高可用地址

在求最高可用地址的时候，需要注意存储地址起始单元（如下面一题）

△☼▽

分析：BFFFH，32KB = 2¹⁵B，若 32KB 的存储地址起始单元为 0000H，则其对应的范围为 7FFFH，现首地址为 4000H，最高可用地址为 7FFFH + 4000H = BFFFH

【地址寄存器、数据寄存器位数】

注意两个点：

1. 地址寄存器的位数只和主存空间大小联系
2. 按字/半字/字节编址，三者的寻址范围是不一样的

△☼▽ （2011年真题）

分析：D，MAR 应保证访问到整个主存地址空间，反过来，MAR 的位数决定了主存地址空间的大小，所以应该看主存地址空间大小 65MB，而不是 32MB

△☼▽

分析：
1）若按字节编址，1MB = 2²⁰ × 8bit，地址寄存器为 20 位，数据寄存器为 8 位，编址范围为 00000H～FFFFFH
2）若按半字编址，1MB = 2¹⁹ × 16bit，地址寄存器为 19 位，数据寄存器为 16 位，编址范围为 00000H～7FFFFH
3）若按字编址，1MB = 2¹⁸ × 32bit，地址寄存器为 18 位，数据寄存器为 32 位，编址范围为 00000H～3FFFFH

【连芯片】

△☼▽ （最简单的字扩展加位扩展）

分析：$\frac{64K\times 32}{16K\times 16}=4\times 2$，$16K=2^{14}$，$64K=2^{16}$

△☼▽ （规定地址空间）

分析：$\frac{32K\times 8}{16K\times 8}=2$，$16K=2^{14}$，故第一片 RAM 芯片的地址范围为 $8000H\sim BFFFH$（1000 0000 0000 0000 ~ 1011 1111 1111 1111），第二片 RAM 芯片的地址范围为 $C000H\sim FFFFH$（1100 0000 0000 0000 ~ 1111 1111 1111 1111），因此两片 RAM 的 $A_{15},A_{14}$ 分别为 10 和 11；另，ROM 芯片不要连接在 R/W 信号线上，RAM 芯片一定要连

【双口 RAM】

具有两组相互独立的地址线、数据线和读/写控制线。双口 RAM 存在的一个问题是很有可能在同一时间两个端口同时操作存储器的同一存储单元，这样就发生了冲突。为解决此问题，特地设置了 BUSY标志，当某存储单元被某端口访问时，就对另外一个端口设置 BUSY 延迟，另一个端口就无法访问该存储单元

双端口存储器可以同时对同一区间、同一单元进行读操作。但是，只要涉及写操作，就不能同时进行

【单字多体存储器】

要使单字多体存储器很好发挥作用，需要一个前提：指令和数据在主存内必须连续存放。一旦遇到转移指令，或者操作数不能连续存放，这种方法的效果就不明显了

单字多体存储器把存储器的存储字长增加 n 倍（下图中 n = 4），于是单字多体存储器的最大带宽比单子单体储存器的最大带宽提高 n 倍。但一般由于一次读取的 n 个字很有可能并不是最近需要的，所以不可能达到最大带宽

单字多体存储器的缺点是：单字多大提存储器必须是凑齐了 n 个数据字之后才能作为一个存储字一次写入存储器

【多体并行存储器】

1）高位交叉编址多体存储器

每个模块内的体内地址顺序是连续的（一个体存满后，再存入下一个体）

高位地址表示体号（带下划线的部分），低位地址来定位体内地址

高位交叉编址的优点：非常有利于存储器的扩张，只需将存储单元的编号往后加即可

高位交叉编址的缺点：由于各个模块一个接一个的串行工作，因此存储器的带宽受到了限制

2）低位交叉编址多体存储器

低位地址可用来表示体号，高位地址来定位体内地址。这样，连续地址分布在相邻的不同模块内，而同一个模块的地址都是不连续的

3）关于低位地址表示体号的考察

① 冲突的产生

△☼▽（2015年真题）

分析：4 体交叉编址，采用低 2 位表示体号，下图给出了每个地址所在的模块，显然 访问 8004 时对 0 号体进行访问，接着访问 8000 时还是对 0 号体进行访问，故发生访存冲突

② 从第几个芯片开始读数据

核心的一句话：从不同体开始读数据可能会影响完全读出某个数据所需要的存储周期数

△☼▽ （2017年真题）

分析：C，根据题意知，研究对象即一个 4 体交叉编址的存储器，低 2 位表示体号，主存 804 001AH 对应的体号为 2，故从 2 号体开始读出 8B 数据，第一个存储周期从 2、3 号读出 2B数据，第二个存储周期从 0 号到 3 号 4 个体中读出 4B，第 3 个周期从 0、1 号体读出 2B，故读出 x 一共需要 3 个存储周期

4）定性分析

模块的字长等于数据总线的宽度，假设模块存储周期为 $T$，总线传输周期为 $\tau$，且存储器由 $m$ 个模块组成，为了实现流水线方式存取，应当满足

$$T=m\tau$$

若采用低位交叉编址的多体存储器，连续读取 $n$ 个字所需要的时间 $t_1$ 为：

$$t_1=T+(n-1)\tau$$

若采用高位交叉编址的多体存储器，连续读取 $n$ 个字所需要的时间 $t_2$ 为：

$$t_2=nT$$

高位交叉编址中的并行性体现在不同的请求源并行地访问不同的体

低位交叉编址的并行性体现在同一请求源并行地访问不同的体

5）与其他知识点的综合

△☼▽（2013年真题）

分析：
（1）CPU 的时钟周期为 1/800MHz = 1.25ns，总线的时钟周期为 1/200MHz = 5ns，总线带宽 4B/5ns = 800 MB/s
（2）每次突发传送 32B，Cache 一块的大小恰好为 32B，故只需要一个度突发传送总线事务来完成一个主存块的读取
（3）（8 体交叉编址读出并传送 n 个字的时间）一次读突发传送总线事务包括一次地址传送和 32B 数据传送，用一个总线时钟周期传输地址，根据低位交叉存储器，数据全部取出需要 40ns+(8-1)×5ns = 75ns，又数据的读取与传输是可以重叠的，故完成一次读突发传送总线事务所需的时间为 = 5+75+5 = 85ns（最后一个 5ns 是最后一个体读出的数据的传输时间）
（4）（怎么算 CPU 执行时间，CPU 执行时间 = 执行所有指令的时间 + Cache 缺失导致的额外时间）BP 的 CPU 执行时间包括：Cache 命中的指令执行时间和 Cache 缺失时的额外开销，故 BP 的CPU执行时间为 100×4×1.25ns+100×1.2×5%×85ns = 1010ns

△☼▽

分析：
（1）1s 有 80M 个时钟周期，CPI = 4，故 MIPS = 8M/4×10^-6 = 20；每条指令访存 1.5 次，每秒共访存 20M×1.5 = 30M 次，Cache 的缺失率为 1%，故平均每秒 Cache 缺失 1%×30M = 0.3M 次；当 CPU 缺失时，CPU 访问主存，主存与 Cache 之间以块为单位传送数据，故每秒 CPU 与主存需要交换的数据大小为 0.3M×16B = 4.8MB，进一步可知，在不考虑 DMA 传送的情况下，主存带宽至少为 4.8MB/s 才能满足 CPU 的访存要求
（2）每秒产生的缺页次数为 300K×0.0005% = 1.5 次，由数据缓冲寄存器位数可知，每传送 4B 数据磁盘控制器就发出一次 DMA 请求，故磁盘 I/O 接口平均每秒发出的 DMA 请求次数至少是 1.5×4KB/4B = 1.5K 次 = 1536 次
（3）DMA 请求优先级更高，因为若 DMA 请求得不到及时响应，I/O 传输数据就可能会丢失
（4）每 1/4 个存储存储周期可以传送 4B 数据，若每个体的存储周期为 50ns，则最大带宽为 4B/(50ns/4) = 320MB/s （考虑一个体的存储字长等于数据寄存器的位数，即 4B，总线传输周期为 50ns/4，亦即每 50ns/4 传输 4B 数据）

【与 Cache 命中率相关的计算】

• 关于命中率的计算，注意是 指令 Cache 命中率 还是 数据 Cache 命中率
• Cache-主存系统效率的计算$$Cache-主存系统效率e=\frac{t_c}{h{t}_c+(1-h)t_m}$$
• 平均访问时间的计算$$平均访问时间t_a=h{t}_c+(1-h)t_m$$

【Cache和主存之间的映射方式】

1）直接映射

$$i=jmodC$$

$i$ 为 Cache 中的组号，$j$ 为主存中的块号，$C$ 为 Cache 的块数

缺点是：

1. 不够灵活，因为每个主存块只能固定地对应某个 Cache 块，即使 Cache 内还空着许多位置也不能占用
2. 冲突概率高（抖动）

应用场合：适合大容量 Cache

2）全相联映射

如下图，主存有 256 块，Cache 需要 8 位（2⁸ = 256） 来做标记，这样才能识别每一个主存块。而在直接映射方式中只需要识别每个组号即可，8 个 Cache 块，256 个主存块，主存块分 32 组，故在 Cache 中只需 5 位来作为标记位，这样就足够识别该块属于哪一组

缺点：tag 的位数增加了，访问 Cache 主存字块标记需要和 Cache 的全部标记进行比较，才能判断所访问主存地址的内容是否已在 Cache 内。这种比较通常采用按内容寻址的相联存储器来完成

应用场合：适用于小容量的 Cache

3）组相联映射（块冲突概率最小）

$$i=jmodQ$$

$i$ 为 Cache 中的组号，$j$ 为主存中的块号，$Q$ 为 Cache 的组数

组相连映射中，主存地址从高位到低位分为 3 部分：Tag + 组号 + 块内字地址

$$\begin{gathered} 块内字地址=lo{g}_2(块大小) \\ 组号=lo{g}_2(Cache组数) \\ Tag=主存地址其余位 \end{gathered}$$

求主存块映射到 Cache 的组号，两种方法：

1. 告知块号，根据公式 $i=jmodQ$ ，注意块号、组号是从 0 开始
   （$mod{2}^k$，即取二进制序列的低 $k$ 位，基于这样的理解，我们可以知道从主存块号求得 Cache 组号，即取块号的低 $k$ 位，记 $Q=2^k$，于是，我们也可以将块号转二进制，但需要注意的是此时块号的二进制仅包含标记字段和组号字段，块号和单元号是不相同的内容，单元号包含主存块号和块内地址）
2. 告知单元号，转换成二进制，对应两个字段

下面以题来说明两种方法：

△☼▽（2009年真题）

分析：C

方法一：直接计算出 129 号单元在主存的位置。主存块大小 32B，按字节编址，因此主存 129 号单元（32×4+1）在主存的第 5 块，块号为 4；Cache 共 16 块，每组 2 块，共 8 组，故主存块号为 4 的块被映射到 Cache 的组号为 4（4 mod 8 = 4）

（我们考虑一下将块号转化为二进制的方法，块号为 4，即 0100B，组号取低 3 位，即 100B，组号为 4）

方法二：129 = 1000 0001B，块内地址占 5 位，组号占 3 位，即 100B = 4，故组号为 4

△☼▽（2016年真题）

分析：这是一道很好的题，把逻辑地址 → 物理地址 → Cache 地址全部整合在了一起

（1）虚拟地址 32 位，页大小 8KB，页内偏移占 13 位，故 A = 19；物理地址中的 D 也表示页内偏移，故 D = 13 位，物理地址24 位，故 C = 11 ；Cache 一块的大小等于主存块的大小，即 64B，故块内偏移占 6 位，即 G = 6 ，Cache 数据区 64KB，有 1K 块，按 2 路组相联方式，故有 2⁹ 组，组号占 9 位，即 F = 9，剩下 Tag 标记位占 24-9-6 = 9 位，即 E = 9

TLB 标记字段 B 中存放的是虚页号，表示该 TLB 项对应哪个虚页表的页表项

（2）4099 = 4096+3，即 1 0000 0000 0011B，故所映射的 Cache 组号为 0 0000 00011B = 3，对应 H 字段的内容为 0 0000 1000B

（3）Cache 缺失带来的开销小，处理缺页的开销大，因为处理缺页需要访问磁盘，而 Cache 缺失只需要访问主存

（4）因为采用直写策略时需要同时写快速存储器和慢速存储器，而写磁盘的速度比写主存慢很多很多，所以在 Cache-主存层次，Cache 可以采用直写策略，而在主存-外存层次，修改页面内容时总是采用回写策略

另外一种组相连方式：（该方式在真题中只出现够一次，系命题组老师采用的教材不同引起，搂一眼就行）

该方式先将主存按 Cache 大小分区，再将各个分区中的块进行分组，主存不同区的相同序号的组和 Cache 同序号的组采用直接映射

△☼▽（2012年真题）

分析：C
根据上面描述，先画出主存和 Cache 的映射如下：

（这里有一个可以学习的小技巧，在画表格研究替换的过程中，可以把块 1、块 3 作为两组分别的每次填入位置，这样可以很清楚地把哪一块挪出去）

4）三种映射方式下的主存地址

5）Cache 标记项问题

每一个 Cache 行对应一个标记项，对于组相连映射方式来说，每一组的标记项放在一起构成一行，将各组从上到下排列，成为一个标记项阵列，如下所示

对于全相联映射和直接映射来说，标记项一行就是一组

（其实标记阵列容量的计算对直接映射、全相联和组相联来说没有什么特别不一样之处，标记阵列的大小都是标记项位数乘以 Cache 的块数）

对于每个标记项来说，其结构如下所示

注意，题目如果说到采用写回方式，即一定有 1bit 的脏位（又称 一致性维护位）

△☼▽

分析：C
按字节编址，主存块大小 4×32/8=16B，字块内地址 4 位，4K字/4字=1K 块，Cache 字块地址 10 位，标记 32-10-4=18 位；4K字 数据有 4K×32=128K 位，标记项有 18+1+1=20 位，标记阵列有 1K×20=20K 位，故 Cache 的总容量为 148K 位

△☼▽

分析：
（1）标记项占 21 位，组号占 5 位，块内地址占 6 位
（2）标记阵列有 (21+1+1)×128 = 2994 位，Cache 的总位数为 2994+128×64×8=68480 位

【Cache 写操作策略】

1）写回法（Write Back）

当 CPU 写命中时，只修改 Cache 的内容，而不立即写入主存，只有当此行被换出时才写回主存，这种方式可以减少访问主存的次数。为了实现这种方式，对 Cache 的每行都必须设置一个修改位（或者称为脏位）。当某行被换出时，根据此行的修改位来决定将该行内容写回主存还是简单舍去

千万注意，写不命中时，CPU 不会在主存中直接修改数据，而是在找到之后直接复制到 Cache 中进行修改，等从 Cache 中换出此块时，再复制到主存中

此知识点可设置综合题的细节题，如当使用写回算法时，求 Cache 的位数，此时，一些考生可能不会加上修改位（如上面习题所示）

2）全写法（Write Through）

当写 Cache 命中时，Cache 与主存同时发生写修改，因而较好地保持了 Cache 与主存内容的一致性。当写 Cache 未命中时，直接在主存中修改。至于在主存中修改后是否要复制到 Cache 中，视情况而定，可以复制也可以不复制

3）写一次

写一次是上面两种策略的一个折中，写命中和写未命中的处理方法都与写回法基本相同，仅仅是第一次写命中时要同时写入主存

【局部性原理】

△☼▽△

分析：C，对数组的遍历体现了空间局部性，对 i 和 sum 的访问体现了时间局部性

对数组遍历空间局部性的解释

对数组的遍历，一般而言，如果一个高速缓存的块大小为 $B$ 字节，那么一个步长为 $k$ 的引用模式（$k$ 的单位取决于数据类型，设占 $wordsize$ 字节）平均每次循环会有 $min(1,\frac{wordsize\times k}{B})$ 次缓存不命中，故而，当 $k=1$ 时，取得最小值，所以对步长为 $1$ 的引用的确具有良好的空间局部性

简而言之，for(int i=0;i<n;i++) tmp+=nums[i] 具有良好的空间局部性

【数组遍历中的缺失率问题（包括循环语句存在的情况）】

1. 按行遍历，还是按列遍历，这将决定换入的数据块是否有后续访问就被换出
2. 读数组元素之后是否又存回，如果又存回此时处理一个元素访问 Cache 两次

△☼▽ （采用组相联映射，且 Cache 足够大可以装下所有数组元素）

分析：
（1）按字寻址，主存块 16K 块，每块 16 字，16K×16=2¹⁸，主存地址 18 位，字块内地址 4 位，Cache 有 128 块，Cache 字块地址 7 位，标记 18-7-4=7 位
（2）（Cache 块数足够多，能一次将全部数组元素装下）210+1-16 = 195 = 16×12+3，故直接映射分别放入 1~13 号块，由于 Cache 初始状态为空，故第一次循环有 13 次未命中，剩下的 9 次循环均命中，故命中率 = 1-13/(195×10)≈99.3%
（3）（把第一次循环读取时间和后面 9 次循环的读取时间分开）CPU 平均每次循环读取时间为 $\frac{13\times 200+(195-13)\times 10+195\times 10\times 9}{10}=2197ns$

△☼▽ （采用组相联映射，且 Cache 足够大可以装下所有数组元素）

分析：
（1）块内地址 $5$ 位，$\frac{8KB}{8\times 4B}$=$2^8$ 块，$2^8/4=2^6$ 组，组号 $6$ 位，标记 $13$ 位
（2）（Cache 块数足够多，能一次将全部数组元素装下）$100=8\times 12+4$，故装入 $13$ 个 Cache 块，Cache 初始状态为空，故第一次循环有 $13$ 次未命中，之后的 $9$ 次循环均命中，故命中率为
$$\left(1-\frac{13}{100\times 10}\right)\times 100\%=98.7\%$$
（3）注意题目中问的是提高了多少倍，故设 Cache 的储存周期为 $t$，则提高倍数为
$$\frac{5t\times 1000}{t\times (1000-13)+5t\times 13}-1\approx 3.75$$
（4）系统效率为
$$\frac{t}{0.987\times t+(1-0.987)\times 5t}\times 100\%=95\%$$

△☼▽（2016年真题）（下面几题都是采用直接映射，Cache 装不下所有数组元素）

分析：C，第一次访问 a[k] 未命中，并将该字所在的主存块调入 Cache 对应的块中，对于该主存块中的 4 个 int 元素的两次访问中（先读后写）只在第一次的第一个元素时发生缺失，其他的 7 次访问中全部命中，故该程序段执行过程中访问数组 a 的 Cache 缺失率为 1/8

△☼▽（2010年真题）

分析：
（1）Cache 行大小 64B，块内地址 6 位，8 个 Cache 行，字块地址 3 位，主存地址空间大小为 256MB，总的地址 28 位，标记 28-6-3=19 位，标记项 1+19= 20 位，Cache 的总容量为 (20+64×8)×8/8B=532B
（2）每个 int 占 4B，a[0][31] 在主存的地址为 320+31×4 = 444 = 0001 1011 1100B，故对应 Cache 的行号为 6；a[1][1] 在主存的地址为 320+(256+1)×4 = 1348 = 0101 0100 0100B，故对应 Cache 的行号为 5
（3）（按行优先遍历和按列优先遍历的区别）Cache 的一行能存 16 个 int，对程序 A，数组每调一行是 2⁸ 次访问，2⁸/16 = 2⁴，即有 2⁴ 次未命中，故命中率为 1-2⁴/2⁸ = 93.75%（只需要按一行计算即可）。对程序B，注意数组 a 按行优先方式存放，由于 Cache 一次只能装入 16×8 = 128 个 int，所以每次数据块读入等不到下次使用就被换出，故命中率为 0

△☼▽

分析：
（1）Cache 总大小 16B，每行 8B，故只有 2 行。Cache 每一行能存下数组的一行（即两个 int 元素）。而 src 和 dst 的行 $i$ 都映射到 Cache 的同一行，所以对一个数组的引用总是驱逐另一个数组的


访问过程如下表描述，注意语句 dts[j][i] = src[i][j] 的意思是先访问 src[i][j] 再存回 dst[j][i]



（2）Cache 32B，有 4 行，此时映射关系如下


访问过程如下

△☼▽ （此题是缺页问题，与 Cache 缺失大同小异）

分析：B，每页刚好可以存储矩阵中一行的数据，因此按照行优先遍历时，每一行访问 200 个数据元素，仅缺失一次，总共缺失 100 次；而按照列优先遍历时，一页仅存放一行数据，在访问下一行时需要换出当前这一行的内容，故每次访问数据元素均发生缺页，缺页次数为 20000

【虚拟存储器】

1. 虚拟存储器必须建立在主存-辅存结构基础上，但两者是有差别的：虚拟存储器允许使用比主存容量大得很多的地址空间，并不是虚拟存储器最多只允许使用主存空间，且在虚拟存储器中主存的内容只是辅存的一部分，遇到问虚拟存储器的容量由什么决定，都应统一回答由计算机地址总线的数量来决定；虚拟存储器每次访问时，必须进行虚实地址的转换
2. 虚拟存储器和 Cache 都基于程序的局部性原理

【Cache 和虚拟储存器的区别】

1. 当 Cache 缺失时，CPU 使当前指令阻塞，并根据主存地址继续到主存中去访问主存块，从主存中取到信息后继续执行指令；当虚拟存储器失效时（如缺页），处理区将会切换进程，以便更新主存中的内容
2. Cache 缺失的处理是由硬件实现的，页面缺失处理是由软件实现的

【页式虚拟存储器】

1）关于页面大小的设定：

如果页面很小，虚拟存储器中包含的页面个数就会过多，使得页表体积过大，页表本身占据的存储空间过大，操作速度将变慢

如果页面很大，虚拟储存器中的页面个数会变少。另外，主存的容量比虚拟存储器的容量更少，主存中的页面个数就会更少，缺页率自然就很大，就会不断地调入/调出页面，降低操作速度

2）地址转换

△☼▽ （2013年真题）

分析：A，页面下大小 4KB，页内地址 12 位，虚拟地址为 03FF F180H，其中页号标记为 03FFFH，页内地址为 180H，根据题目中给出的页表项可知页标记为 03FFFH 所对应的页框号为 0153H，页框号与页内地址之和即为物理地址 015 3180 H

△☼▽（模拟题一）

分析：（注意，物理地址是十进制表示，不是十六进制表示）C，32773 = 1024×32+5，1000 0000 0000 0101B，页大小 2¹² B，页内地址占 12 位，即 0000 0000 0101，物理页号为 8，查表可知虚页号为 3 = 0011，故逻辑地址为 0011 0000 0000 0101 = 2¹³+2¹²+5 = 12293

3）页表大小的计算

$页表大小=\frac{虚存容量}{页大小}\times 页表项大小$

△☼▽

分析：虚地址 36 位，虚存容量 $2^{36}=64$ GB，$\frac{64GB}{8KB}=8$M 个页表项，故页表的总容量为 $8M\times 4B=32$ MB

4）综合题目

△☼▽（2011年真题）

分析：

（1）虚拟地址空间大小 16MB = 2²⁴B，故虚拟地址 24 位；页面大小 4KB = 2¹²B，虚地址中的高 12 位表示虚页号；物理地址空间 1MB = 2²⁰B，故物理地址 20 位；物理地址中高 8 位表示页框号

（2）根据直接映射方式可知，物理地址应该划分为 3 个字段，块内偏移 5 位， 字块地址 3 位，标记 12 位

（3）（虚拟地址 → 物理地址 → Cache 地址）虚地址 001C600H 的高 12 位为 001H，页号为 1，有效为 1，故对应页面在主存中；页框号为 04H，故对应的物理地址为 04C600H；04C600H = 0000 0100 1100 0110 0000B，字块地址为 011 = 3，行号 3 的有效位为 1，但标记 105H ≠ 04CH，故不命中

（4）采用 4 路组相联，TLB 有 8 个页表项，分 2 组，页内地址 12 位，组号 1 位，标记 11 位；虚地址 024BACH = 0000 0010 0100 1011 1010 1100B，组号为 0，标记为 0000 0010 010B = 012H，根据 TLB 的部分内容可知有效位为 1，故对应页面在主存中，对应的页框号为 1FH

（从此题可以看出一点：对于 TLB 具体实现的处理可以类同 Cache）

△☼▽（2018年真题）

分析：
（1）主存物理地址 28 位

（2）TLB 采用全相联映射方式，可以把页表内容调入任一块空闲的 TLB 中，TLB 中每项都有一个比较器，没有映射规则，只要空闲就好；TLB 使用 SRAM

（3）（考虑标记项中的替换算法控制位）Cache 采用二路组相联映射方式，还应该有 1 位的替换控制位和 1 位的脏位；于是，标记项一共有 1+1+1+20 = 23 位（1B），组地址占 3 位，故有 8 组，每组两行，共 16 行，Cache 一行 2⁵ = 32B，故 Cache 的总容量为 16×(23+32×8)/8B = 558B；Cache 中的有效位用来指出所在 Cache 行中的信息是否有效

（4）（虚拟地址 → 物理地址 → Cache 地址）虚页号为 0008CH 对应页框 0040H，故其对应的物理地址为 0040040H；标记为 00400H，其有效位为 0，故 Cache 缺失；物理地址的低 12 位与虚拟地址的低 12 位相同，即 260H，其低 8 位 60H = 0110 0000B，组号为 3，故该地址所在主存块映射到 Cache 的组号为 3

（接上题）

分析：此题为操作系统考题，当主要知识仍是页式虚拟存储器，故在这里紧接给出

（1）由图可知，虚页号的高 10 位为页目录号，低 10 位为页号，故虚页号为 00 0000 0110 00 0000 0110，故虚拟地址为 0000 0001 1000 0000 0110 0000 0000 1000B = 0180 6008H

（2）（页目录基址地址寄存器）PDBR 为页目录基址地址寄存器，其存储页目录表物理内存地址；进程切换时，PDBR 的内容会变化，理由：进程切换时，地址空间发生了变化，对应的页目录及其起始地址也相应变化，因此需要用进程切换后当前进程的页目录启示地址刷新 PDBR；同一进程的线程切换时，PDBR 的内容不会变化，理由：同一进程中的线程共享该进程的地址空间，其线程发生切换时，地址空间不变，线程使用的页目录不变，故 PDBR 的内容也不变

（3）改进型 CLOCK 置换算法需要用到使用位和修改位，故需要设置访问字段（使用位）和修改字段（脏位）

△☼▽（2019年真题）

分析：仅对 46 题

（1）push 指令和 ret 指令的虚拟地址相差 74 个地址单位（0040104A-00401000 = 4A），故其大小为 74B（< 4KB），故在同一页中

（2）主存块大小 64 B（2⁶），故在主存地址中的低 6 位地址表示块内地址；Cache 有 64 行，采用 4 路组相联，故有 16 组，中间 4 为表示 Cache 组号；高 22 为表示标记信息

（3）因为页大小为 4KB（2¹²），于是虚拟地址的低 12 位和物理地址低 12 位完全相同，call 指令的虚拟地址为 0040 1025，低 12 位为 0000 0010 0101，取中间 4 位为 0000，故对应 Cache 的组号为 0

【段式虚拟存储器】

段式虚拟存储器中，段具有逻辑独立性，易于实现程序的编译、管理和保护，也便于多道程序共享

【段页式虚拟存储器】

在这种方式中，把程序按逻辑单位分段以后，再把每个段分成固定大小的页。程序对主存的调入/调出是按页面进行的，但它又可以按段实现共享和保护

【命中一致性】

下面四句话每句话都是重点

• TLB 命中，页表必然命中，且该页面一定在内存中，至于此页是否在 Cache 中，这个不能确定
• Cache 命中，主存必命中
• Cache 命中与否与页表命中没有必然联系，因为 Cache 和页表是两种独立的机制
• 如果 TLB 和页表都不命中，则代表该数据就不在主存中，所以必定会导致 Cache 访问不命中

【包括关于访问时间（次数）花销的计算】（此处同操作系统）

1）关于 TLB

1. 每访问一个内存数据就会访问 TLB 一次
2. 若发生缺页异常时，处理完缺页异常，重新执行该指令，仍会再访问 TLB 一次

△☼▽

分析：仅讨论 52 题

（1）R₂ 装的是 i 值，循环结束的条件为 i < N，N 存放在 R₆ 中，故 i<1000，P 执行结束时，i = 1000，故 (R₂) = 1000

（2）（注意这里讨论的是指令 Cache）Cache 共有 16 行，每块 32B，故 Cache 的数据区容量为 16×32B = 512B；P 有 6 条指令，每条指令占 4B，一共占 24 B（< 32B），读第一条指令时发生缺失，之后所有指令均在指令 Cache 中，故指令 Cache 的命中率为 1-1/(1000×6) ≈ 99.8%

（3）指令 4 为加法指令，当数组 A 中元素值过大时，则会导致加法指令发生溢出异常；虽然指令 2、5 也是加法指令，但它们分别为数组地址计算指令和存储变量 i 的寄存器进行自增的指令，而 i 最大达到 1000，故这两条指令不会产生溢出异常；指令 3 需要访存，会发生缺页异常

（接 3 小问）数组 A 的所有元素在同一页，故一次全部调入主存，于是，共访盘 1 次；每访问一次内存数据就会查 TLB 一次，共访问数组元素 1000 次，所以此时又访问 TLB 1000次，还要考虑到第一次访问数组 A，即访问 A[0] 时，会多访问一次 TLB（第一次访问 A[0] 会先查一次 TLB，然后产生缺页，处理完缺页中断后，会重新访问 A[0]，此时又查 TLB），所以访问 TLB 的次数一共是 1001 次

△☼▽（2009年真题）

分析：
（1）页面大小 4KB（2¹²B），故页内偏移占虚地址的低 12 位，其余为页号

2362H：页号 P=2，访问快表，快表初始为空，再访问页表，页表命中，最后访问内存，故需要 10ns+100ns+100ns

1565H：页号 P=1，访问快表，未命中，再访问页表，有效为0，发生缺页，缺页处理完之后再次访问快表命中，最后访问内存，故需要 10ns+100ns+10⁸ns+10ns+100ns

25A5H：页号 P=2，访问快表命中（访问 2362 H时，将 2 号页填入 TLB），访问内存，故需要 10ns+100ns

（2）访问虚地址 1565H 时发生缺页，进程的驻留集大小为 2， 故需要淘汰一个页面，根据 LRU 算法淘汰 0 号页面，替换后，虚地址 1565H 对应的物理地址为 101565H

2）关于 Cache

Cache 未命中时，会从主存调入缺失数据，调入数据后仍需读取，所以对缺失数据要算两部分的时间：调入数据时间 + 读取时间

对于总时间即是，所有次数执行的时间 + 缺失时的额外开销

△☼▽

分析：
（1）主存地址 16 位，块内地址 3 位，标记 13 位，故 Cache 地址中标记位数 13 位
（2）45-20+1 = 26 = 8×3+2，需要映射到 4 个 Cache 块，第一次访问有 4 次未命中，其余访问均命中，四次循环全部命中，故命中率 = 1-4/(26+18×4) ≈ 96%
（3）总的存取时间 = 98 次 Cache 读数据 + 4 次 Cache 缺失 = 98×40ns+4×1us = 7920ns

【试问 CPU 执行指令进行一次存储访问最少访问主存几次？】

第一步： 根据虚页号查找 TLB，若 TLB 命中，有对应虚页的页表项，则取出页框号形成物理地址，转第二步；若 TLB 缺失，转第三步

第二步： 判断物理地址中的标记是否和 Cache 中的标记相同并且有效为是否为 1，若为 1，则 Cache 命中，从 Cache 中读取数据或者写数据到 Cache （全写方式下，同时也写主存）；若不为 1，则发生 Cache 缺失，转第四步

第三步： 当 TLB 缺失时，根据页表基址寄存器的值和虚页号找到主存中的页表项，判断有效位是否为 1，若是，则说明该虚页在主存中，此时把该页表项转入 TLB 中，并取出页框号形成物理地址，转第二步；若不是，则说明该虚页不在主存中，即发生了缺页异常。此时，需要调出操作系统中的缺页异常处理程序，实现从磁盘读入一个页面的功能。缺页处理结束后，重新执行指令，这次一定能在主存中找到

第四步： Cache 缺失时，CPU 根据物理地址到主存读一块信息到 Cache，然后读入到 CPU 或 CPU 写信息到Cache 中

从上述过程来看，CPU 进行一次存储访问操作，最好情况下无需访问主存；最坏情况下，不仅要多次访问主存，还要读写磁盘

△☼▽ （2015年真题）

分析：B，取数时，如果 Cache 命中则不需要访问主存，但是采用直写方式，写回的过程除了在 Cache 中修改数据，也会在主存中修改数据，故至少需要访问主存 1 次

【快表缺失、Cache 缺失和页面缺失的处理有什么异同点？】

• 快表的缺失可以用软件也可以用硬件来处理。 首先根据虚页号和页表基址寄存器的内容到主存中找到对应的页表项，若有效为 1，则把该项取到快表中即可；若有效位为 0，发生缺页异常
• 页面缺失处理是由软件实现的。 缺页时，需要调出操作系统中的缺页异常处理程序进行处理，实现从一个磁盘读入一个页面的功能。缺页处理结束后，重新执行当前指令
• Cache 缺失的处理是由硬件实现的。 当 Cache 发生缺失时，CPU 使当前指令阻塞，并根据主存地址继续到主存中去访问主存块，从主存中取到信息后指令继续执行

【磁盘问题】

1）磁盘地址格式

对盘面号做出一点说明：一个磁盘组共有 $n$ 片，那么就有 $2n-2$ 个记录面，盘面号取 $k$ 位（$2^k⩾2n-2$）

2）诸多关于磁盘的计算公式

$$\begin{gathered} 数据传输率=每一条磁道的容量\times 磁盘转速 \\ 传输时间=\frac{b字节}{r\times 一个磁道上的字节数} \end{gathered}$$

$$访问时间=寻道时间+旋转延迟+传输时间$$

$$寻道时间=启动磁臂的时间+n\times 每移动一个磁道所花的时间$$

$$旋转延迟=\frac{1}{2r}（注意r的单位为r/s）$$

△☼▽ （考虑扇区间隙）

分析：D，每个磁道容量为 60MB/200 = 0.3MB，读一个磁道数据的时间等于磁盘旋转一周的时间减去经过所有扇区间隙的时间，故0.3MB/(25-1.25ms×8) = 20MB/s

△☼▽ （读取时间的计算）

分析：B，$10000r/min$，即一转 $6ms$，故平均等待时间为 $3ms$，$4KB/(20MB/s)=0.2ms$，于是读取一个扇区所需要的平均时间为 $平均等待时间+寻道时间+读取时间+控制器延迟时间=3ms+6ms+0.2ms+0.2ms=9.4ms$

△☼▽

分析：B，平均等待时间为 (60s/7200)/2 = 4.17ms，传输时间为 (60s/7200)/1000 = 0.01ms，故访问一个扇区的平均存取时间约为 4.17ms+8ms+0.01ms = 12.18ms

△☼▽

分析：注意 r 的单位是秒/转，而不是转/秒，在随机寻道的情况下，读写一个磁道的时间要包括平均寻找时间（包括了寻道时间和旋转延时）和读写时间，即 (T+r) 秒，b 字节数据占用 b/N 个磁道，故总时间为 (T+r)b/N

△☼▽

分析：
（1）每块的数据传输时间为 3000B/(500B/ms) = 6ms，更新全部数据所需时间为 4ms×1000+2×1000×(30ms+10ms+6ms) = 96s
（2）磁盘机旋转速度提高一倍后，平均等待时间为 5ms，数据传输速率提高一倍后，每块的数据传输时间为 3ms，更新全部数据所需时间为 4ms×1000+2×1000×(30ms+5ms+3ms) = 80ms

△☼▽ （位密度的计算，磁盘地址格式）

分析：
（1）磁盘存储器的容量为 $4\times 275\times 12288B=13516800B$

（2）假设最高位密度为 $D_1$（即最内圈磁道的位密度），$${D}_1=\frac{每道信息量}{内圈周长}=\frac{12288B}{\pi \times 230mm}\approx 17B/mm$$ 假设最低位密度为 $D_2$（即最外圈磁道的位密度），$$D_2=\frac{12288B}{(230mm/2+275/5mm)\times 2\times \pi }\approx 11.4B/mm$$
（3）磁盘数据传输率 $C=转速\times 每道信息容量=50r/s\times 12288B=614400B/s$

（4）平均等待时间 $=(1/50s)/2=10ms$

（5）假定每个扇区记录 $1024B$，则有 $12288B/1024B=12$ 个扇区，于是磁盘地址格式为：

△☼▽（2019年真题，在扇区的基础上还考虑了簇）

分析：
（1）磁盘的容量为 300×10×200×512B = 3×10⁵KB
（2）（结合着磁盘的计算靠磁盘调度算法）一个磁道有 100 个簇，一个柱面有 1000 个簇，则簇号 100260 在柱面 100，簇号 60005 在柱面 60， 101660 在柱面 101，110560 在柱面 110；按照 SSTF 调度算法，访问的先后次序为 100260 → 101660 → 110560 → 60005
（3）（簇号转换为磁盘地址格式）由（2）可知，簇号 100530 在柱面 100，磁道 5 ，扇区 60（530 = 500 + 30）；将簇号转换成磁盘物理地址的过程是由 I/O 系统的磁盘（设备）驱动程序完成

3）磁盘记录方式

如果某文件长度超过了一个磁道的容量，应将它记录在同一个柱面上，而不是同一个盘面上，因为记录在同一个柱面上不需要重新寻道

【磁盘阵列】

RAID 指由多个小容量磁盘代替一个大容量的磁盘。由于目前的技术可以将数据进行分块并且能并行处理，因此可以将数据交错存放在多个磁盘上，使之并行存取。此外，RAID 专门划分出了一块区域用来记录多余或重复的资料，一旦系统中某一磁盘失效，就可以利用重复的资料重建用户信息

1）RAID 0

交错存放数据。缺点是，如果某一次磁盘的数据损坏，将会导致整个资料因不完整而无法读出

2）RAID 2

镜像备份

3）提高 RAID 可靠性

可以提高 RAID 可靠性的方法

• 磁盘镜像就是将磁盘的数据复制到其他磁盘，如果某个磁盘出现问题，可以通过赋值的数据来恢复，以此达到提高可靠性的目的
• 奇偶校验很明显可以提高 RAID 的可靠性

不可以提高 RAID 可靠性的方法

• 条带化技术主要是用来解决磁盘冲突问题，因为条带化技术可以将一块连续的数据分成很多小部分并把它们分别存储到不同的磁盘上去。这就能使多个进程同时访问数据的多个不同部分不会造成磁盘冲突，而且在需要对这种数进行顺序访问的时候可以获得最大程度上的 I/O 并行能力