249 KiB
存储系统习题
存储器概念
存储器层次化结构
例题 下列关于多级存储系统的说法中，正确的有()。
Ⅰ.多级存储系统是为了降低存储成本
Ⅱ.虚拟存储器中主存和辅存之间的数据调动对任何程序员是透明的
Ⅲ.$CPU$只能与$Cache$直接交换信息，$CPU$与主存交换信息也需要经过Cache
$A.$仅Ⅰ
$B.$仅Ⅰ和Ⅱ
$C.$Ⅰ、Ⅱ和Ⅲ
$D.$仅Ⅱ
解：$A$。主存和辅存之间的数据调动是由硬件和操作系统共同完成的，仅对应用级程序员透明。$CPU$与主存可直接交换信息。
半导体随机存储器
SRAM和DRAM
DRAM的刷新
例题 一个$1K\times4$位的动态$RAM$芯片，刷新周期为$2ms$，若其内部结构排列成$64\times64$形式，且存取周期为$0.1\mu s$。
1）若采用分散刷新和集中刷新（即异步刷新）相结合的方式，刷新信号周期应取多少？
2）若采用集中刷新，则对该存储芯片刷新一遍需多少时间？死时间率是多少？
解：
1）采用分散和集中刷新相结合的方式，对排列成$64\times64$的存储芯片，需在$2ms$内将$64$行各刷新一遍，刷新信号的时间间隔为$2m\div64=31.25\mu s$，因此可取刷新周期为$\lfloor31.25\rfloor=31us$。
2）采用集中刷新，对$64\times64$的芯片，需在$2ms$内集中$64$个存取周期刷新$64$行。题中给出的存取周期为$0.1\mu s$，即在$2ms$内集中$6.4\mu s$刷新，则死时间率为$(6.4\div2000)\times100%=0.32%$。
ROM
例题 下列关于闪存的叙述中，错误的是()。
$A.$信息可读可写，并且读、写速度一样快
$B.$存储元由$MOS$管组成，是一种半导体存储器
$C.$掉电后信息不丢失，是一种非易失性存储器
$D.$采用随机访问方式，可替代计算机外部存储器
解：$A$。闪存是$EEPROM$的进一步发展，可读可写，用$MOS$管的浮栅上有无电荷来存储信息。闪存依然是$ROM$的一种，写入时必须先擦除原有数据，因此写速度比读速度要慢不少（硬件常识）。闪存是一种非易失性存储器，它采用随机访问方式。现在常见的$SSD$固态硬盘，它由$Flash$芯片组成。
例题 $U$盘属于()类型的存储器。
$A.$高速缓存
$B.$主存
$C.$只读存储器
$D.$随机存取存储器
解：$C$。$U$盘采用$Flash,Memory$技术，它是在$EEPROM$的基础上发展起来的，属于$ROM$的一种。由于擦写速度和性价比均很可观，因此其常用作辅存。随机存取与随机存取存储器$RAM$不同，只读存储器$ROM$也是随机存取的。因此，支持随机存取的存储器并不一定是$RAM$。
主存结构
即问一块芯片需要多少根控制线。一般不包括电源与接地端。
例题 某容量为$256MB$的存储器由若干$4M\times8$位的$DRAM$芯片构成，该$DRAM$芯片的地址引脚和数据引脚总数是()。
A.19
B.22
C.30
D.36
解：$A$。$256MB$是一个迷惑性条件，问题问的是该芯片的引脚而不是总的引脚。$4MB=2^{22}B$，又$DRAM$使用地址复用技术，所以只需要一半的地址引脚，为$11$。而$8$位，所以需要$8$根数据引脚。一共需要$19$根。
主存与CPU连接
主存容量扩展
芯片需要数
注意单位转换，一般给出的容量为$B$，而芯片规格为位。
例题 某计算机主存容量为$64KB$，其中$ROM$区为$4KB$，其余为$RAM$区，按字节编址。现要用$2K\times8$位的$ROM$芯片和$4K\times4$位的$RAM$芯片来设计该存储器，需要上述规格的$ROM$芯片数和$RAM$芯片数分别是()。
A.1,15
B.2,15
C.1,30
D.2,30
解：$D$。因为$ROM$为$4KB$，所以需要$(4K\times8)\div(2K\times8)=2$片，需要字扩展。$RAM$为$64-4=60KB$。$(60K\times8)\div(4K\times4)=30$片。所以需要字位同时扩展。
存储芯片片选
地址总线低位连接具体的地址端，高位连接片选线。
例题 地址总线$A_0$（高位）到$A_{15}$（低位），用$4K\times4$位的存储芯片组成$8$位的$16KB$存储器，则产生片选信号的译码器的输入地址线应该是()。
A.A_2A_3
B.A_0A_1
C.A_{12}A_{13}
D.A_{14}A_{15}
解：$A$。因为芯片规格$4K\times4$，所以每个芯片需要地址$4K=2^{12}$个。所以低位的$A_4\sim A_{15}$一共$12$个总线作为地址线，$A_0\sim A_3$作为片选线进行接入。因为芯片规格$4K\times4$，组成$16KB$存储器，所以需要$(16K\times8)\div(4K\times4)=8$个芯片，且存储器需要$8$位，所以需要字位扩展，从而芯片为$4$行$2$列，$2$个芯片一组，一共$4$组。所以片选线选两位就能表示$2^2=4$组，直接连接在靠近地址线的高位，即$A_2A_3$。（如果$A_0A_1$中间就缺两位）
例题 若片选地址为$111$时，选定某一$32K\times16$位的存储芯片工作，则该芯片在存储器中的首地址和末地址分别为()。
A.00000H,01000H
B.38000H,3FFFFH
C.3800H,3FFFH
D.0000H,0100H
解：$B$。$32K\times16$的存储芯片有地址线$15$根（片内地址），片选地址为$3$位，因此地址总位数为$18$位，现高$3$位为$111$，则首地址为$11,1000,0000,0000,0000=38000H$，末地址为$11,1111,1111,1111,1111=3FFFFH$。
如下图所示，若低位地址（$A_0\sim A_{11}$）接在内存芯片地址引脚上，高位地址（$A_{12}\sim A_{19}$）进行片选译码（其中$A_{14}$和$A_{16}$未参加译码），且片选信号低电平有效，则对图中所示的译码电路，不属于此译码空间的地址是()。
A.AB000H\sim ABFFFH
B.BB000H\sim BBFFFH
C.EF000H\sim EFFFFH
D.FE000H\sim FEFFFH
解：$D$。首先要看懂这个片选信号译码图，并明白译码原理。这是一个部分译码的片选信号，高$8$位地址中有$2$位（$A_{14}$和$A_{16}$）未参与译码，所以最后表达式中没有这两位。最右边的里面写的是与符号，代表其他几位最后都需要与操作。然后$A_{18}$和$A_{17}$中间还有一个$\geqslant1$，这是什么意思？电路逻辑操作是与或非，不是与，也不是非，那就是或，可以用加号表示，即$A_{18}+A_{17}\geqslant1$，即里面有一个为$1$就可以了。
最后译码输出的逻辑表达式应为$\overline{CS}=\overline{A_{19}(A_{18}+A_{17})A_{15}A_{13}A_{12}}$。
因此不属于此译码空间的是这几位不合该逻辑表达式的，$A$选项为$AB$，即$1010,1011$，去掉$14$位和$16$位为$101111$；$B$选项为$101111$；$C$选项为$111111$；$D$选项为$111110$。由逻辑表达式可知$A_{17}$与$A_{18}$至少有一个为$1$，$A_{19}A_{15}A_{13}A_{12}$应全为$1$，仅$D$无法满足。
连接图
例题 设$CPU$有$16$根地址线，$8$根数据线，并用$\overline{MREQ}$作为访存控制信号（低电平有效），用$\overline{WR}$作为读/写控制信号（高电平为读，低电平为写）。现有下列存储芯片：$1K\times4$位$RAM$，$4K\times8$位$RAM$，$8K\times8$位$RAM$，$2K\times8$位$ROM$，$4K\times8$位$ROM$，$8K\times8$位$ROM$及$74LS138$译码器和各种门电路。画出$CPU$与存储器的连接图，要求：
1）主存地址空间分配：$6000H\sim67FFH$为系统程序区；$6800H\sim6BFFH$为用户程序区。
2）合理选用上述存储芯片，说明各选几片？
3）详细画出存储芯片的片选逻辑图。
解：系统程序区需要使用$ROM$，用户程序区需用$RAM$。
第一步根据地址线、数据线，选择存储芯片。
对于系统程序区，$CPU$数据线有八根，所以存储器的位数应该为八位。$CPU$从$6000H$到$67FFH$之间一共有$800H$个地址，即为$2K$个地址。所以就应该选择$2K\times8$位的$ROM$。对于用户程序区，$6800H$到$6BFFH$一共有$400H$，即$1K$，需要使用$1K\times8$位的$RAM$，但是这时候没有，为了不造成浪费使用两块$1K\times4$位的$RAM$进行位扩展。
然后是地址分配，$2K$的$ROM$的地址线应该是11根地址线，$1K$的$RAM$地址线应该是10根地址线。而$CPU$一共有$16$根地址线，所以可以分配给$RAM$和$ROM$。$ROM$地址$6000H$到$67FFH$是二进制$0110,0000,0000,0000到0110,0111,1111,1111$，所以选择最低$11$位进行连接。$RAM$地址$6800H$到$6BFFH$是二进制$0110,1000,0000,0000到0110,1011,1111,1111$，所以选择最低$10$位进行连接。
然后进行选片信号，即什么时候用$RAM$什么时候用$ROM$，其中$74LS138$译码器是用三位选八位，所以对于$ROM$和$RAM$地址，选择低位占用更多的地址的从低位开始的能区分$ROM$和$RAM$地址的三位，即第三位到第六位的$100$和$101$。即地址是$100$就是$ROM$，$101$就是$RAM$。所以$CBA$为$100$时选择$Y_4$，为$101$时选择$Y_5$。
$74LS138$还有三个使能端，一个高电平有效$G_1$，两个低电平有效$\overline{G_{2A}}$、$\overline{G_{2B}}$。这时地址前面还有两位$01$，可以作为译码器的使能端，第一位$0$代表低电平有效的使能端，第二位的$1$代表高电平有效的使能端$\overline{G_1}$。余下的一个低电平有效的使能端正好对应低电平有效的$\overline{MREQ}$作为访存控制信号决定译码器是否工作。
其中为什么两个$RAM$还需要一个$&$操作，是因为RAM的地址不仅仅需要第三位到第六位是$101$，还需要第七位是$0$，所以必须同时保证$A_{10}=0$和$\overline{Y_5}=0$，然后从$&$这个操作传回两个$RAM$得到选片信号。
同时只有$RAM$需要直接连接读写控制线$\overline{WR}$，而$ROM$读写控制线是静态的，所以可以直接连接到地面就可以了。
另外还有一个问题，就是$ROM$和$CPU$之间的箭头的问题，如果$ROM$是在此无法写入的，就是单向的箭头，从$ROM$到$CPU$，但是这里是双向的，说明这里指可以写入$ROM$。
双端口RAM和多模块存储器
例题 下列说法中，正确的是（).
Ⅰ.高位多体交叉存储器能很好地满足程序的局部性原理
Ⅱ.高位四体交叉存储器可能在一个存储周期内连续访问$4$个模块
Ⅲ.双端口存储器可以同时访问同一区间、同一单元
$A.$Ⅰ、Ⅲ
$B.$Ⅱ、Ⅲ
$C.$只有Ⅲ
$D.$只有Ⅰ
解：$B$。Ⅰ：高位多体交叉存储器由于在单个存储器中的字是连续存放的，所以不能保证程序的局部性原理；而低位多体交叉存储器由于是交叉存放，所以能很好地满足程序的局部性原理，因此Ⅰ错误。Ⅱ：高位四体交叉存储器虽然不能满足程序的连续读取，但仍有可能一次连续读出彼此地址相差一个存储体容量的$4$个字，虽然概率较小，但也非不可能，因此Ⅱ正确。Ⅲ中：双端口存储器具有两套独立读/写口，具有各自的地址寄存器和译码电路，所以可以同时访问同一区间、同一单元，因此Ⅲ正确。综上，Ⅱ、Ⅲ正确。
例题 某计算机主存按字节编址，由$4$个$64M×8$位的$DRAM$芯片采用交叉编址方式构成，并与宽度为$32$位的存储器总线相连，主存每次最多读写$32$位数据。若$double$型变量$x$的主存地址为$804,001AH$，则读取$x$需要的存储周期数是()。
A.1
B.2
C.3
D.4
解：$C$。由$4$个$DRAM$芯片采用交叉编址方式构成主存可知，主存地址最低两位表示该字节存储的芯片编号。$double$型变量占$64$位（$8B$）。其主存地址$804,001AH$的最低两位是$10$，说明它从编号为$2$的芯片开始存储（编号从$0$开始）。一个存储周期可对所有芯片各读取$1$字节，一轮可以取$4$字节，因此需要$3$轮（最开始两个和最后面两个各占一轮）。
例题 假定一个存储器系统支持四体交叉存取，某程序执行过程中访问地址序列为$3,9,17,2,51,37,13,4,8,41,67,10$，哪些地址访问会发生体冲突？
解：
首先将对应的地址分类：
B0:4,8
B1:9,17,37,13,41
B2:2,10
B3:3,51,67
若给定访存地址在相邻$4$次访问中出现在同一$B$中就会访存冲突：$4,8$，$9,17,37$，$37,13,41$。
高速缓冲存储器
$Cache$总容量=标记阵列+$Cache$的存储容量
标记阵列就是标记项集合，包括标志位（地址总长度减去块内地址长度与$Cache$组号长度等）和有效位控制位等。
高速缓冲存储器基本概念
某C语言程序段如下：
for(i-0;i<-9;i++) {
temp=1;
for(j-0;j<=i;j++)temp*=a[i];
sum+=temp;
下列关于数组$a$的访问局部性的描述中，正确的是()。
$A.$时间局部性和空间局部性皆有
$B.$无时间局部性，有空间局部性
$C.$有时间局部性，无空间局部性
$D.$时间局部性和空间局部性皆无
解：$A$。提问数组$a$的访问局部性即考虑关于存储数组单元的访问情况。涉及到访存的语句只有temp*=a[i]一条，$C$语言中temp和sum都是临时变量放到寄存器栈中。访存顺序为$a[0]$；$a[0]$、$a[1]$；$a[0]$、$a[1]$、$a[2]$……，所以访存都是同一块存储空间的周围存储空间，所以空间局部性好。每一轮都要访问相同的位置，所以时间局部性也好。
局部性原理
存储结构
例题 对于由高速缓存、主存、硬盘构成的三级存储体系，$CPU$访问该存储系统时发送的地址为()。
$A.$高速缓存地址
$B.$虚拟地址
$C.$主存物理地址
$D.$磁盘地址
解：$C$。当$CPU$访存时，先要到$Cache$中查看该主存地址是否在$Cache$中，所以发送的是主存物理地址。只有在虚拟存储器中，$CPU$发出的才是虚拟地址，这里并未指出是虚拟存储系统。磁盘地址是外存地址，外存中的程序由操作系统调入主存中，然后在主存中执行，因此$CPU$不可能直接访问磁盘。
例题 采用指令$Cache$与数据$Cache$分离的主要目的是()。
$A.$降低$Cache$的缺失损失
$B.$提高$Cache$的命中率
$C.$降低$CPU$平均访存时间
$D.$减少指令流水线资源冲突
解：$A$。把指令$Cache$与数据$Cache$分离后，取指和取数分别到不同的$Cache$中寻找，则指令流水线中取指部分和取数部分就可以很好地避免冲突，即减少了指令流水线的冲突。
注意：如果指令$Cache$与数据$Cache$分离，要注意其组号是分别计算的，不能加在一起分组，如两个都是$4$行，则二路组相联后，其各自两个组，组号长度为$2$，而不是一共四个组，组号长度为$3$。
高速缓冲存储器的效率
例题 假设$Cache$的速度是主存的$5$倍，且$Cache$的命中率为$95%$，则采用$Cache$后，存储器性能提高多少（同时考虑：同时被访问$Cache$，命中则中断访问主存；先访问$Cache$，若不命中再访问主存）？
解：设$Cache$的存取周期为$t$，则主存存储周期为$5t$。
若$Cache$和主存同时访问，命中时的访问时间就是$t$，则不命中时的访问时间就是访问主存的时间，也就是$5t$。
所以系统的平均访问时间为$t_a=0.95\times t+0.05\times5t=1.2t$。
所每个周期可存取的数据量为$D$，则存储系统的带宽就是$\dfrac{D}{1.2t}$，不采用$Cache$的带宽为$\dfrac{D}{5t}$，所以性能为原来的$\dfrac{D\div1.2t}{D\div5t}=\dfrac{5}{1.2}\approx4.17$，即提高了$3.17$倍。
若先访问$Cache$再访问主存，则命中时的访问时间就是$t$，则不命中时的访问时间就是访问主存的时间加上之前访问$Cache$消耗的$t$时间，总共为$6t$。
所以系统的平均访问时间为$t_a=0.95\times t+0.05\times6=1.25t$。
所以性能为原来的$\dfrac{5}{1.25}=4$倍，即提高了$3$倍。
地址映射
主存地址=主存块号+块内地址，$Cache$地址=$Cache$块号+块内地址。
直接映射
例题 某$32$位计算机的$Cache$容量为$16KB$，$Cache$行的大小为$16B$，若主存与$Cache$地址映像采用直接映像方式，则主存地址为$0x1234E8F8$的单元装入$Cache$的地址是()。
A.00010001001101
B.01000100011010
C.10100011111000
D.11010011101000
解：$C$。因为$Cache$容量为$16KB=2^{14}B$，所以$Cache$地址长$14$位。主存与$Cache$地址映像采用直接映像方式，将$32$位的主存地址$0x1234E8F8$写成二进制，根据直接映射的地址结构可知，取低$14$位就是$Cache$地址。
例题 某存储系统中，主存容量是$Cache$容量的$4096$倍，$Cache$被分为$64$个块，当主存地址和$Cache$地址采用直接映像方式时，地址映射表的大小应为()。（假设不考虑一致维护和替换算法位）
A.6\times4097bit
B.64\times12bit
C.6\times4096bit
D.64\times13bit
解：$D$。地址映射表也就是标记阵列，由于$Cache$被分为$64$个块，则$Cache$有$64$行，采用直接映射，一行相当于一组。因此该标记阵列每行存储$1$个标记项，其中主存标记项为$12$位（$2^{12}=4096$，是$Cache$容量的$4096$倍，即地址长度比$Cache$长$12$位)，加上$1$位有效位，因此为$64\times13$位。
组相联映射
例题 某计算机的$Cache$共有$16$块，采用二路组相联映射方式（即每组$2$块）。每个主存块大小为$32B$，按字节编址，主存$129$号单元所在主存块应装入的$Cache$组号是()。
A.0
B.2
C.4
D.6
解：$C$。由于每个主存块大小为$32B$，主存$129$在$129\div32=4...1$，即在第五块$Cache$中，即$4$号内存块的$1$号地址。$Cache$共有$16$块，采用二路组相联映射方式，所以$4%8=4$，即在第四组中。
例题 某计算机的主存地址位数为$32$位，按字节编址。假定数据$Cache$中最多存放$128$个主存块，采用四路组相联方式，块大小为$64B$，每块设置了$1$位有效位。采用一次性写回策略，为此每块设置了$1$位“脏”位。要求：
1)）分别指出主存地址中标记（$Tag$）、组号（$Index$）和块内地址（$Offset$）三部分的位置与位数。
2）计算该数据$Cache$的总位数。
解：因为块大小为$64B$，所以块内地址字段为$\log_264=6$位;因为$Cache$中有$128$个主存块，采用四路组相联，$Cache$分为$128\div4=32=2^5$组，所以组号字段为$5$位；标记字段为剩余的$32-5-6=21$位。数据$Cache$的总位数应包括标记项的总位数和数据块的位数。每个$Cache$块对应一个标记项，标记项中应包括标记字段、有效位和“脏”位（仅适用于写回法)。
1）主存地址中$Tag$为$21$位，位于主存地址前部；组号$Index$为$5$位，位于主存地址中部；块内地址$Offset$为$6$位，位于主存地址后部。
2）标记项的总位数$=128\times(21+1+1)=128\times23=2944$位，数据块位数$=128\times64\times8=65536$位，所以数据$Cache$的总位数$=2944+65536=68480$位。
替换算法
例题 有如下$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\%
解：$C$。分析语句a[k]=a[k]+32，首先读取a[k]需要访问一次a[k]，之后将结果赋值给a[k]需要访问一次，共访问两次。第一次访问a[k]未命中，并将该字所在的主存块调入$Cache$对应的块中，对该主存块中的$16\div4=4$个整数的两次访问中，只在访问第一次的第一个元素时发生缺失，其他的$4\times2-1=7$次访问中全部命中，因此该程序段执行过程中访问数组$a$的$Cache$缺失率约为$1/8$（即$12.5%$）。
例题 设$Cache$由$8$个块构成，$CPU$依次访问的主存地址块号为：$4$，$6$，$12$，$4$，$8$，$14$，$22$，$6$，$4$，$11$，$5$，$2$（十进制），求：
1）假设地址映射方式为全相联映射，在采用$FIFO$、$LRU$、$LFU$替换算法时，分别求$Cache$命中次数。
2）假设地址映射方式为直接映射，求$Cache$命中次数。
3）假设地址映射方式为二路组相联映射，在采用$FIFO$、$LRU$、$LFU$替换算法时，分别求$Cache$命中次数。
解：
1）使用全相连映射可以随机存放，为了方便按照顺序存放。
| Cache号\CPU访问主存序列 | 4 | 6 | 12 | 4 | 8 | 14 | 22 | 6 | 4 | 11 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 是否命中 | 否 | 否 | 否 | 是 | 否 | 否 | 否 | 是 | 是 | 否 | 否 | |
| 0 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | |
| 1 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | ||
| 2 | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 12 | |||
| 3 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | |||||
| 4 | 14 | 14 | 14 | 14 | 14 | 14 | ||||||
| 5 | 22 | 22 | 22 | 22 | 22 | |||||||
| 6 | 11 | 11 | ||||||||||
| 7 | 5 |
这时候还差一个$2$需要调入，但是没有多余的空间了。
$FIFO$：由于最先进入的是$4$，所以替换$0$号，将$4$变为$2$。
$LRU$：选择最近最久未使用的块，从第一位开始算，$4$目前来看出现了$3$次，$6$目前来看出现了$2$次，而后面的$12$、$8$、$14$、$22$、$11$、$5$都出现了$1$次，所以选最远的，是$12$号块，替换$2$号，将$12$变为$2$。
$LFU$：选择最不经常使用的，从全局来看，$4$出现了$3$次，$6$出现了$2$次，而$12$、$8$、$14$、$22$、$11$、$5$都出现了$1$次，又$12$最先进入，所以替换$2$号，将$12$变为$2$。
2）由于直接映射，所以直接对$8$取模，然后将对应相同余数的块替换掉就可以了。余数代表调入的$Cache$块号，商代表区分同一个$Cache$存储的不同主存块的标记。
| CPU访问主存序列 | 4 | 6 | 12 | 4 | 8 | 14 | 22 | 6 | 4 | 11 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 余数 | 4 | 6 | 4 | 4 | 0 | 6 | 6 | 6 | 4 | 3 | 5 | 2 |
| 商 | 0 | 0 | 1 | 0 | 1 | 2 | 2 | 0 | 0 | 1 | 0 | 0 |
根据余数和商计算得到对应处理结果：
| $Cache$号\CPU访问主存序列 | 4 | 6 | 12 | 4 | 8 | 14 | 22 | 6 | 4 | 11 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 是否命中 | 否 | 否 | 否 | 否 | 否 | 否 | 否 | 否 | 是 | 否 | 否 | 否 |
| 0 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | ||||
| 1 | ||||||||||||
| 2 | 2 | |||||||||||
| 3 | 11 | 11 | 11 | |||||||||
| 4 | 4 | 4 | 12 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 5 | 5 | 5 | ||||||||||
| 6 | 6 | 6 | 6 | 6 | 14 | 22 | 6 | 6 | 6 | 6 | 6 | |
| 7 |
3）二路组相联即两块为一组，所以一共四个组。这时候需要将块对$4$取模。余数代表调入的$Cache$组号，商代表区分同一个$Cache$组存储的不同主存块的标记。
| CPU访问主存序列 | 4 | 6 | 12 | 4 | 8 | 14 | 22 | 6 | 4 | 11 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 余数 | 0 | 2 | 0 | 0 | 0 | 2 | 2 | 2 | 0 | 3 | 1 | 2 |
| 商 | 1 | 1 | 3 | 1 | 2 | 3 | 5 | 1 | 1 | 2 | 1 | 0 |
若使用$FIFO$，每一组上面是队头，下面是队尾：
| 组号 | $Cache$号\CPU访问主存序列 | 4 | 6 | 12 | 4 | 8 | 14 | 22 | 6 | 4 | 11 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 是否命中 | 否 | 否 | 否 | 是 | 否 | 否 | 否 | 否 | 否 | 否 | 否 | 否 | |
| 0 | 0 | 4 | 4 | 12 | 12 | 12 | 12 | 8 | 8 | 8 | 8 | ||
| 1 | 4 | 4 | 12 | 12 | 8 | 8 | 8 | 8 | 4 | 4 | 4 | 4 | |
| 1 | 2 | ||||||||||||
| 3 | 5 | 5 | |||||||||||
| 2 | 4 | 6 | 14 | 22 | 22 | 22 | 22 | 6 | |||||
| 5 | 6 | 6 | 6 | 6 | 14 | 22 | 6 | 6 | 6 | 6 | 2 | ||
| 3 | 6 | ||||||||||||
| 7 | 11 | 11 | 11 |
命中一次。
若使用$LRU$，每一组上面是将要替换（最近不怎么用）的，下面是最近换入或替换的：
| 组号 | Cache号\CPU访问主存序列 | 4 | 6 | 12 | 4 | 8 | 14 | 22 | 6 | 4 | 11 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 是否命中 | 否 | 否 | 否 | 是 | 否 | 否 | 否 | 否 | 是 | 否 | 否 | 否 | |
| 0 | 0 | 4 | 12 | 4 | 4 | 4 | 4 | 8 | 8 | 8 | 8 | ||
| 1 | 4 | 4 | 12 | 4 | 8 | 8 | 8 | 8 | 4 | 4 | 4 | 4 | |
| 1 | 2 | ||||||||||||
| 3 | 5 | 5 | |||||||||||
| 2 | 4 | 6 | 14 | 22 | 22 | 22 | 22 | 6 | |||||
| 5 | 6 | 6 | 6 | 6 | 14 | 22 | 6 | 6 | 6 | 6 | 2 | ||
| 3 | 6 | ||||||||||||
| 7 | 11 | 11 | 11 |
命中两次。
若使用$LFU$，则需要考虑置换出的块后面是否还需要使用，将最近要用的保留下来：
| 组号 | $Cache$号\CPU访问主存序列 | 4 | 6 | 12 | 4 | 8 | 14 | 22 | 6 | 4 | 11 | 5 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 是否命中 | 否 | 否 | 否 | 是 | 否 | 否 | 否 | 是 | 是 | 否 | 否 | 否 | |
| 0 | 0 | 4 | 12 | 4 | 4 | 4 | 4 | 8 | 8 | 8 | 8 | ||
| 1 | 4 | 4 | 12 | 4 | 8 | 8 | 8 | 8 | 4 | 4 | 4 | 4 | |
| 1 | 2 | ||||||||||||
| 3 | 5 | 5 | |||||||||||
| 2 | 4 | 14 | 6 | 6 | 6 | 6 | 6 | 6 | |||||
| 5 | 6 | 6 | 6 | 6 | 6 | 22 | 22 | 22 | 22 | 22 | 2 | ||
| 3 | 6 | ||||||||||||
| 7 | 11 | 11 | 11 |
命中三次。
写策略
例题 设主存地址空间大小为$1KB$，按字节编址，$Cache$由$8$个块构成，每个$Cache$块大小为$16B$，$CPU$依次访问以下地址：$0001001110$、$1001110010$、$0001001111$、$0011000010$、$0101001000$、$1011110010$、$1111010000$、$0011001001（十进制为78$、$626$、$79$、$194$、$328$、$754$、$976$、$201$），求：
1）假设地址映射方式为全相联映射，在采用$FIFO$、$LRU$、$LFU$替换算法时，分别求$Cache$命中次数。
2）假设地址映射方式为直接映射，求$Cache$命中次数。
3）假设地址映射方式为二路组相联映射，在采用$FIFO$、$LRU$、$LFU$替换算法时，分别求$Cache$命中次数。
4）假设其它配置同3），采用写回法和直写法时，$Cache$的总容量分别为多少？
解：
1）由于使用全相联映射，所以地址分为主存字块标记和字块内地址两个部分。
因为主存地址空间大小为$1KB$，且按字节编址，即一共可以标识$1K$个数据，则主存地址一共有$10$位二进制位。
又每个$Cache$块大小位$16B$，所以需要$4$位标识块，即$4$位的字块内地址。所以需要$10-4=6$位主存字块标记来区分主存块。
所以开始访问地址，按$6+4$分开，并设置$8$个有效位。并注意，如果调入一个地址，则回调入这个主存字块标记所标识的全部地址到$Cache$中，即若$CPU$访问$xx\cdots xxx$，则会全部调入$xx\cdots000$到$xx\cdots111$的全部数据。
按题目所说，前面主存字块标记为$4$位（每个$Cache$块$16$位），所以$16$就进$1$，即按十进制来理解，十进制地址$0$到$15$在$Cache$的0中，$16$到$31$在$Cache$的$1$中等等。
第一个是$000100,1110$，所以$Cache$的$0$号块调入$000100,0000$到$000100,1111$的数据，并将有效位设置为$1$，标记为$00100$。同样下面也都要如此处理，按顺序存储，表格中代表该$Cache$所保存的地址的标记：
| Cache号\访问地址 | 000100 1110 | 100111 0010 | 000100 1111 | 001100 0010 | 010100 1000 | 101111 0010 | 111101 0000 | 001100 1001 |
|---|---|---|---|---|---|---|---|---|
| 是否命中 | 否 | 否 | 是 | 否 | 否 | 否 | 否 | 是 |
| 0 | 000100 | 000100 | 000100 | 000100 | 000100 | 000100 | 000100 | 000100 |
| 1 | 100111 | 100111 | 100111 | 100111 | 100111 | 100111 | 100111 | |
| 2 | 001100 | 001100 | 001100 | 001100 | 001100 | |||
| 3 | 010100 | 010100 | 010100 | 010100 | ||||
| 4 | 101111 | 101111 | 101111 | |||||
| 5 | 111101 | 111101 | ||||||
| 6 | ||||||||
| 7 |
因为$Cache$还有剩余，没有替换问题，所以使用三种替换算法时，$Cache$都是命中$2$次。
2）由于使用直接映射，所以地址分为主存字块标记、$Cache$字块地址和字块内地址三个部分。
因为每个$Cache$块大小是$16B$，所以字块内地址还是$4$位。而$Cache$字块地址需要映射到$8$个$Cache$块，所以$Cache$字块地址需要三位，从而主存字块地址为$10-3-4=3$位。
因为直接映射法是按序存入的，所以对于同一个$Cache$的存储的数据的地址的$Cache$字块地址是固定的，所以$Cache$字块地址和字块内地址都不用标记，所以也只用标记主存字块标记就可以了。然后需要按照$Cache$字块地址来放，而不能像全映射的按$0$、$1$、$2$这样放。
第一个是$000,100,1110$，所以要将$000,100,0000$到$000,100,1111$的数据全部放入$100$即$4$号中，将$4$的有效位设置为$1$，标记$000$：
| Cache号\访问地址 | 000 100 1110 | 100 111 0010 | 000 100 1111 | 001 100 0010 | 010 100 1000 | 101 111 0010 | 111 101 0000 | 001 100 1001 |
|---|---|---|---|---|---|---|---|---|
| 是否命中 | 否 | 否 | 是 | 否 | 否 | 否 | 否 | 否 |
| 0 | ||||||||
| 1 | ||||||||
| 2 | ||||||||
| 3 | ||||||||
| 4 | 000 | 000 | 000 | 001 | 010 | 010 | 010 | 001 |
| 5 | 111 | 111 | ||||||
| 6 | ||||||||
| 7 | 100 | 100 | 100 | 100 | 100 | 100 | 100 |
因为使用直接映射，所以要替换一定是使用先进先出算法。
3）因为使用二路组相联映射，所以使用两位来标识组，即分为$4$个组，每个组两个$Cache$块。
所以字块内地址还是$4$位，组地址是$2$位，主存字块标记位$10-4-2=4$位。
第一个是$0001,00,1110$，所以是第$0$组，将$0001,00,0000$到$0001,00,1111$放到第$0$组中，标记$0001$，并将$0$号$Cache$块有效位改为$1$，下一个是队尾，上一个是队头，$FIFO$算法：
| 组号 | Cache号\访问地址 | 0001 00 1110 | 1001 11 0010 | 0001 00 1111 | 0011 00 0010 | 0101 00 1000 | 1011 11 0010 | 1111 01 0000 | 0011 00 1001 |
|---|---|---|---|---|---|---|---|---|---|
| 是否命中 | 否 | 否 | 是 | 否 | 否 | 否 | 否 | 是 | |
| 0 | 0 | 0001 | 0011 | 0011 | 0011 | 0011 | |||
| 1 | 0001 | 0001 | 0001 | 0011 | 0101 | 0101 | 0101 | 0101 | |
| 1 | 2 | ||||||||
| 3 | 1111 | 1111 | |||||||
| 2 | 4 | ||||||||
| 5 | |||||||||
| 3 | 6 | 1001 | 1001 | 1001 | |||||
| 7 | 1001 | 1001 | 1001 | 1001 | 1011 | 1011 | 1011 |
由于替换只出现在$0101,00,1000$处，所以不同的替换策略结果相同，命中次数均为$2$次。
4）
数据大小为$8\times16B=128B=1024bit$。
而标记项分为有效位、标记位（地址映射）、一致性维护位（脏位，写策略）、替换算法位（替换策略）。
而按照3）的配置，地址映射的主存字块标记就是标记位内存，为$4$位。
而对于写策略，写回法需要脏位$1$位，而直写法不需要，则$0$位。
替换策略暂时不考虑。
所以写回法需要$1024+(1+4+1)\times8=1072bit$，而直写法需要$1024+(1+4)\times8=1064bit$。
例题 假定主存地址为$32$位，按字节编址，指令$Cache$和数据$Cache$与主存之间均采用$8$路组相联映射方式，直写写策略和$LRU$替换算法，主存块大小为$64B$，数据区容量各为$32KB$。开始时$Cache$均为空。请回答下列问题。
1）$Cache$每一行中标记、$LRU$位各占几位？是否有修改位？
2）有如下$C$语言程序段：
for(k=0;k<1024;k++)
s[k]=2*s[k];
若数组$s$及其变量$k$均为$int$型，$int$型数据占$4B$，变量$k$分配在寄存器中，数组$s$在主存中的起始地址为$0080,00C0H$，则在该程序段执行过程中，访问数组$s$的数据$Cache$缺失次数为多少？
3）若$CPU$最先开始的访问操作是读取主存单元$0001,003H$中的指令，简要说明从$Cache$中访问该指令的过程，包括$Cache$缺失处理过程。
解：
1）主存块大小为$64B=2^6$字节，故主存地址低$6$位为块内地址，$Cache$组数为$32KB\div(64B\times8)=64=2^6$，故主存地址中间$6$位为$Cache$组号，主存地址中高$32–6-6=20$位为标记，采用$8$路组相联映射，故每行中的$LRU$位占$3$位，采用直写方式，故没有修改位。
2）$0080,00C0H,=,0000,0000,1000,0000,0000,0000,1100,0000B$，主存地址的低$6$位为块内地址，为全$0$，故$s$位于一个主存块的开始处，这个数组一共$1024$个元素，占$1024\times4B/64B=64$个主存块。在执行程序段的过程中，每个主存块中的$64B\div4B=16$个数组元素依次读、写一次，因而对每个主存块，总是第一次访问缺失，此时会将整个主存块调入$Cache$，之后每次都命中。综上，数组$s$的数据$Cache$访问缺失次数为占用块数$64$次。
3）$0001,0003H=0000,0000,o000,0001,0000,000000,000011B$，根据主存地址划分可知，组索引为$0$，故该地址所在主存块被映射到指令$Cache$的第$0$组。因为$Cache$初始为空，所有$Cache$行的有效位均为$0$，所以$Cache访$问缺失。此时，将该主存块取出后存入指令Cache的第$0$组的任意一行，并将主存地址高$20$位$00010H$填入该行标记字段，设置有效位，修改$LRU$位，最后根据块内地址$000011B$从该行中取出相应的内容。
虚拟存储器
快表
例题 下列命令组合的一次访存过程中，不可能发生的是( )。
$A.TLB$未命中，$Cache$未命中，$Page$未命中
$B.TLB$未命中，$Cache$命中，$Page$命中
$C.TLB$命中，$Cache$未命中，$Page$命中
$D.TLB$命中，$Cache$命中，$Page$未命中
解：$D$。首先要明白，$Cache$中存放的是主存的一部分副本，$TLB$（快表）中存放的是$Page$（页表）的一部分副本。在同时具有虚拟页式存储器（有$TLB$）和$Cache$的系统中，$CPU$发出访存命令，先查找对应的$Cache$块看看最靠近$CPU$的存储系统中有没有副本。如果没有再去看$TLB$，如果$TLB$再没有，再去$Page$。
- 若$Cache$命中，则说明所需内容在$Cache$内，其所在页面必然已调入主存，因此$Page$必然命中（如果没有命中就找不到对应页面，页面也不可能已经放入$Cache$中），但$TLB$不一定命中。
- 若$Cache$未命中，则并不能说明所需内容未调入主存，和$TLB$、$Page$命中与否没有联系，要再去看看$TLB$。若$TLB$命中，$Page$也必然命中（因为$TLB$只是一部分的$Page$），反之当$Page$命中，$TLB$则未必命中，因此选项$D$不可能发生。
例题 虚拟存储器中的页表有快表和慢表之分，下面关于页表的叙述中正确的是()。
$A.$快表与慢表都存储在主存中，但快表比慢表容量小
$B.$快表采用了优化的搜索算法，因此查找速度快
$C.$快表比慢表的命中率高，因此快表可以得到更多的搜索结果
$D.$快表采用相联存储器件组成，按照查找内容访问，因此比慢表查找速度快
解：$D$。快表由组相联存储器组成，因此查表速度很快，而慢表存储在主存中，因此选项$A$、$B$错误。快表仅是慢表的一个小副本，所以不能得到更多结果，因此选项$C$错误。
例题 下列关于$TLB$和$Cache$的叙述中，错误的是()。
$A.$命中率都与程序局部性有关
$B.$缺失后都需要去访问主存
$C.$缺失处理都可以由硬件实现
$D.$都由$DRAM$存储器组成
解：$D$。$Cache$由$SRAM$组成；$TLB$通常由相联存储器组成，也可由$SRAM$组成。$DRAM$需要不断刷新，性能偏低，不适合组成$TLB$和$Cache$。其他选项都是$TLB$和$Cache$的特点。
例题 假定编译器将赋值语句x=x+3;转换为指令add xaddr，3，其中$xaddr$是$x$对应的存储单元地址。若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的$TLB$，且$Cache$使用直写方式，则完成该指令功能需要访问主存的次数至少是()。
A.0
B.1
C.2
D.3
解：$B$。该指令可分为取数、运算、写回的过程，取数可能从主存中取，也可能从$Cache$中取数，所以不用访问主存，而写直通方式要把数据同时写入$Cache$和主存，所以至少访问一次。
地址转换
例题 某计算机主存地址空间大小为$256MB$，按字节编址。虚拟地址空间大小为$4GB$，采用页式存储管理，页面大小为$4KB$，$TLB$（快表）采用全相联映射，有$4$个页表项，内容如下表所示。
| 有效位 | 标记 | 页框号 |
|---|---|---|
| 0 | FF180H | 0002H |
| 1 | 3FFF1H | 0035H |
| 0 | 02FF3H | 0351H |
| 1 | 03FFFH | 0153H |
则对虚拟地址$03FF,F180H$进行虚实地址变换的结果是？对虚拟地址$FF18,0180H$进行虚实地址变换的结果是?
解：因为主存地址空间大小为$256MB$，若按字节编址，则有$256M$个地址，即$28$位地址。
因为虚拟地址空间大小位$4GB$，则同样按字节编址，则有$4G$个地址，即$32$位地址。
页面大小为$4KB$，则页表地址一共$12$位。
所以主存地址=实页号$16$位+页内地址$12$位，虚拟地址=虚页号$20$位＋页内地址$12$位。
表格的标记就是指虚页号，页框号就是指实页号。
根据虚地址组成划分所求虚拟地址为$03FFF,180H$和$FF180,180H$，根据表格对应的$03FFFH$指向$0153H$，而页内地址不变所以可以直接拼接上去得到实页地址$0153180H$。
同理$FF180$指向$0002H$，但是此时注意到这个快表项的有效位是$0$，代表$TLB$没有命中，所以这个地址指向不一定对，所以要去找页表，如果页表没有就再去找辅存调入主存。