【分析解答】
第 3 版 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【分析解答】
（1）系统 A 使用 RAID 1 技术，采用避盘镜像方式存储，所以，所用避盘容量为 $10\mathrm{TB} + 10\mathrm{TB} = 20\mathrm{TB}$。系统 B 使用 RAID 5 技术，采用一个奇偶校验盘，假设使用 5 个避盘阵列，那么 10TB 的数据需要 2.5TB 来存放冗余的奇偶校验数据，所以系统 A 比系统 B 多用 7.5TB 存储容量。
（2）系统 A 的写入速度取决于两个避盘中速度慢的那个，因为所有盘写一块数据的时间都是 30ms，故系统 A 写入一块数据的时间是 30ms。对于系统 B，最坏的情况下，写一块数据的时间为 2 次读和 2 次写，即所用时间为 $4 \times 30\mathrm{ms} = 120\mathrm{ms}$。
（3）系统 A 更可靠，因为系统对整个避盘都进行了备份，所以即使所有的数据都损坏了也可以恢复，而系统 B 只是记录了部分冗余信息，如果两个避盘的相同位都损坏了就恢复不出来了。
11. 假定在一个使用 RAID 5 的系统中，采用先更新数据块、再更新校验块的信息更新方式。如果在更新数据块和更新校验块的操作之间发生了掉电现象，那么会出现什么问题？采用什么样的信息更新方式可避免这个问题？
## 【分析解答】
对于 RAID 5 来说，如果在写完数据块但未写入校验块时发生断电，则写入的数据和对应的校验信息不匹配，无法正确恢复数据。这种情况可以避免，因为 RAID 5 是大数据块交叉方式，每个盘独立进行操作，所以，只要同时写数据块所在盘和校验块所在盘即可。
12. 已知字符编码 $A = 1000001, a = 1100001, 0 = 0110000$，求 D,d,6 的 7 位 ASCII 码和第一位前加入奇校验位后的 8 位编码。
## 【分析解答】
D 的 ASCII 码为 $1000001 + 011 = 1000100$，前面加奇校验位后的编码是 11000100。
d 的 ASCII 码为 $1100001 + 011 = 1100100$，前面加奇校验位后的编码是 01100100。
6 的 ASCII 码为 $0110000 + 110 = 0110110$，前面加奇校验位后的编码是 10110110。
13. 某数据为 $11100101\mathrm{B}$，采用奇校验和 CRC 校验（生成多项式为 $x^{4} + x + 1$）对应的校验码各是什么？
## 【分析解答】
采用奇校验时，因为数据中有奇数个 1，故校验位为 0；采用 CRC 校验时，生成多项式为 $x^{4} + x + 1$，故有 4 个校验位。首先在数据后面添 4 个 0，得到 $111001010000\mathrm{B}$，再将它和 10011 进行模 2 除法，得到余数为 $1100\mathrm{B}$，所以校验码为 $1100\mathrm{B}$。
<!-- page: 222 -->
14. 假定某计算机的总线采用偶校验，每8位数据有一位校验位，若在32位数据线上传输的信息是 1234 5678H，则对应的4个校验位应为什么？若接收方收到的数据信息和校验位分别为 1235 5678H 和 0100B，则说明发生了什么情况，给出验证过程。
## 【分析解答】
总线上传输的4字节分别为0001 0010、0011 0100、0101 0110、0111 1000B，因此对应的4个偶校验位 $\mathrm{P_0\sim P_3}$ 分别为 $0,1,0,0$。当接收方收到数据信息1235 5678H和校验位0100B后，进行如下验证。
第1字节：数据为 $12\mathrm{H} = 00010010\mathrm{B}$，故偶校验位 $\mathrm{P_0^{\prime} = 0,0\oplus 0 = 0}$，说明传输正确。
第2字节：数据为 $35\mathrm{H} = 00110101\mathrm{B}$，故偶校验位 $\mathrm{P_0^{\prime} = 0,0\oplus 1 = 1}$，说明传输错误。
第3字节：数据为 $56\mathrm{H} = 01010110\mathrm{B}$，故偶校验位 $\mathrm{P_0^{\prime} = 0,0\oplus 0 = 0}$，说明传输正确。
第4字节：数据为 $78\mathrm{H} = 01111000\mathrm{B}$，故偶校验位 $\mathrm{P_0^{\prime} = 0,0\oplus 0 = 0}$，说明传输正确。
15. 假定一个 16 位数据 $M_{16}M_{15}M_{14}M_{13}M_{12}M_{11}M_{10}M_{9}M_{8}M_{7}M_{6}M_{5}M_{4}M_{3}M_{2}M_{1}$ 为 0111 1000 1101 0010B，要求写出该 16 位数据的 SEC 码（单检错码），并说明 SEC 码如何正确检测数据位 $M_{5}$ 的错误。
## 【分析解答】
对于16位数据的单检错码，其校验位 $P$ 和故障字 $S$ 都是5位。假定故障字 $S = S_{3}S_{4}S_{3}S_{2}S_{1}$ 的值反映出错数据位或校验位的位置信息，则得到码字排列和故障字的取值如下。
[tbl-41.md](tbl-41.md)
根据上表，得到各个校验位的计算公式如下。
$$
P _ {1} = M _ {1} \oplus M _ {2} \oplus M _ {4} \oplus M _ {5} \oplus M _ {7} \oplus M _ {9} \oplus M _ {1 1} \oplus M _ {1 2} \oplus M _ {1 4} \oplus M _ {1 6}
$$
$$
P _ {2} = M _ {1} \oplus M _ {3} \oplus M _ {4} \oplus M _ {6} \oplus M _ {7} \oplus M _ {1 0} \oplus M _ {1 1} \oplus M _ {1 3} \oplus M _ {1 4}
$$
$$
P _ {3} = M _ {2} \oplus M _ {3} \oplus M _ {4} \oplus M _ {8} \oplus M _ {9} \oplus M _ {1 0} \oplus M _ {1 1} \oplus M _ {1 5} \oplus M _ {1 6}
$$
$$
P _ {4} = M _ {5} \oplus M _ {6} \oplus M _ {7} \oplus M _ {8} \oplus M _ {9} \oplus M _ {1 0} \oplus M _ {1 1}
$$
$$
P _ {5} = M _ {1 2} \oplus M _ {1 3} \oplus M _ {1 4} \oplus M _ {1 5} \oplus M _ {1 6}
$$
当数据字为0111 1000 1101 0010B时，代入上述公式，得到校验位 $P = P_{5}P_{4}P_{3}P_{2}P_{1} = 01111\mathrm{B}$。若第5位数据 $M_{5}$ 出错时，数据字变为0111 1000 1100 0010B，代入上述公式，得到 $P^{\prime} = P_{5}^{\prime}P_{4}^{\prime}P_{3}^{\prime}P_{2}^{\prime}P_{1}^{\prime} = 00110\mathrm{B}$，因而，故障字 $S = S_{5}S_{4}S_{3}S_{2}S_{1} = 01111\oplus 00110 = 01001\mathrm{B},M_{5}$ 排在码字的第9位，因此 $M_{5}$ 出错。
16. 假设要传送的数据信息为 1110001B，若约定的生成多项式为： $G(x) = x^{3} + 1$ ，则校验码为多少？假定在接收端接收到的数据信息为 1110011B，说明如何正确检测其错误，写出检测过程。
## 【分析解答】
原数据信息为1110001B，对应的报文多项式为 $M(x) = x^{6} + x^{5} + x^{4} + 1$ ，生成多项式
<!-- page: 223 -->
的位数为 4 位，因此，校验码的位数为 3 位。在原数据信息后面添加 3 个 0，得到 $M'(x) = x^3 M(x) = x^5 + x^8 + x^7 + x^3$，用 $M'(x)$ 去模 2 除 $G(x)$，得到余数 110B，因此，在发送端要传送的 CRC 码为 111 0001 110B。在接收端收到的数据位为 111 0011B，假定 CRC 码中的校验位在传送过程中没有出错，在接收端还是 110B，则在接收端对数据校验时，将接收端的 CRC 码 111 0011 110B 用生成多项式 $G(x)$ 进行模 2 除，得到的余数为 010B，余数不为 0 表明传输时发生了错误。
17. 现代计算机中，SRAM 一般用于实现快速小容量的 cache，而 DRAM 用于实现慢速大容量的主存。以前超级计算机通常不提供 cache，而是用 SRAM 来实现主存（如 Cray 巨型机），请问：如果不考虑成本，你还这样设计高性能计算机吗？为什么？
【分析解答】
不会。其理由主要有以下两个方面。
（1）主存越大越好，主存大，缺页率降低，因而减少了访问磁盘所需的时间。DRAM 芯片的集成度比 SRAM 芯片的高得多，因而用 DRAM 芯片比用 SRAM 芯片构成的主存容量大得多。
（2）程序访问的局部性特点使得 cache 的命中率很高，因而 CPU 访问的主要是 cache，对主存的访问不多，而且现代 DRAM 芯片中也有 SRAM 构成的行缓冲。因此，即使主存没有用快速的 SRAM 芯片而是用 DRAM 芯片，也不会对存储访问速度有多大影响。
18. 某计算机主存地址空间大小有 8MB，分成 32768 个主存块，按字节编址；cache 可存放 8KB 数据（不包括有效位、标记等附加信息），采用直接映射方式，问 cache 共有多少行？主存地址如何划分？要求说明每个字段的含义、位数和在主存地址中的位置。
【分析解答】
每个主存块大小为 $8\mathrm{MB} / 32768 = 256\mathrm{B}$，故 cache 共有 $8\mathrm{KB} / 256\mathrm{B} = 32$ 行。直接映射方式下，cache 行号（即行索引）有 5 位；由于每个主存块大小为 256B，按字节编址，故块内地址为 8 位；主存地址空间大小为 8MB，所以地址位数为 23 位，故主存地址中标记有 $23 - 5 - 8 = 10$ 位。综上所述，主存地址共有以下三个字段：高 10 位为标记字段，中间 5 位为行索引，低 8 位为块内地址。
19. 某计算机主存地址空间大小为 1GB，按字节编址。cache 可存放 64KB 数据，主存块大小为 128B，采用直接映射和直写（write through）方式。请回答下列问题：
（1）主存地址如何划分？要求说明每个字段的含义、位数和在主存地址中的位置。
（2）cache 的总容量为多少位？
【分析解答】
（1）cache 共有 $64\mathrm{KB} / 128\mathrm{B} = 512$ 行，直接映射方式下，cache 行号占 9 位；由于每个主存块大小为 128B，按字节编址，故块内地址为 7 位；主存地址空间大小为 1GB，所以主存地址位数为 30 位。主存地址中标记有 $30 - 9 - 7 = 14$ 位。综上所述，主存地址共有以下三个字段：高 14 位为标记，中间 9 位为行索引，低 7 位为块内地址。
（2）因为直接映射不考虑替换算法，所以 cache 行中没有用于替换的控制位；因为采用直写方式，所以，cache 行中也没有修改位。每个 cache 行中包含 1 位有效位、14 位标记位和 128B 的数据，因此，cache 总容量为 $512 \times (1 + 14 + 128 \times 8)b = 519.5\mathrm{Kb}$。
20. 对于数据的访问，分别给出具有下列要求的程序或程序段的示例。
<!-- page: 224 -->
(1) 空间局部性和时间局部性都好。
(2) 时间局部性好，空间局部性差。
(3) 空间局部性好，时间局部性差。
(4) 时间局部性和空间局部性都差。
【分析解答】
对于按行优先存放在内存的多维数组，如果按列优先访问数组元素，则空间局部性就差；如果在一个循环体中某个数组元素只被访问一次，则时间局部性就差。假定二维数组 $a[1000][1000]$ 按行优先存放在内存，以下给出的4个程序片段用于对数组 $a$ 进行相应的处理，它们具有相同的功能，但数组访问的时间局部性和空间局部性截然不同（不考虑编译器的优化）。
(1) 时间局部性和空间局部性都好的程序片段。
for(i=0; i&lt;1000; i++)
for(j=0; j&lt;1000; j++) {
sum=sum+a[i][j];
product=product*a[i][j];
square=square+a[i][j]*a[i][j];
}
for(j=0; j&lt;1000; j++)
for(i=0; i&lt;1000; i++) {
sum=sum+a[i][j];
product=product*a[i][j];
square=square+a[i][j]*a[i][j];
}
for(i=0; i&lt;1000; i++)
for(j=0; j&lt;1000; j++)
sum=sum+a[i][j];
for(i=0; i&lt;1000; i++)
for(j=0; j&lt;1000; j++)
product=product*a[i][j];
for(i=0; i&lt;1000; i++)
for(j=0; j&lt;1000; j++)
square=square+a[i][j]*a[i][j];
for(j=0; j&lt;1000; j++)
for(i=0; i&lt;1000; i++) {
sum=sum+a[i][j];
for(j=0; j&lt;1000; j++)
for(i=0; i&lt;1000; i++) {
product=product*a[i][j];
}
for(j=0; j&lt;1000; j++)
for(i=0; i&lt;1000; i++) {
square=square+a[i][j]*a[i][j];
int sum_array(int a[N][N])
{
int i, j, k, sum = 0;
for (i = 0; i &lt; N; i++)
for (j = 0; j &lt; N; j++)
for (k = 0; k &lt; N; k++)
sum += a[k][i][j];
return sum;
}
int sum_array(int a[N][N])
{
int i, j, k, sum = 0;
for (k = 0; k &lt; N; k++)
for (i = 0; i &lt; N; i++)
for (j = 0; j &lt; N; j++)
sum += a[k][i][j];
return sum;
}