2017-2018学年下学期期末

2017-2018学年下学期期末试卷（A）（含答案）

一、单项选择题（每小题 2 分，共 30 分）

1. 下列叙述中，正确的是（ ）。

   A. CPU 能直接读取硬盘上的数据 B. CPU 能直接存取内存储器 C. CPU 由存储器、运算器和控制器组成 D. CPU 主要用来存储程序和数据

   答案：

   B

   ---

2. 将十进制数 165 用十六进制表示的结果是（ ）。

   A. 0xB5 B. 0xA5 C. 0xB6 D. 0xA6

   答案：

   B

   ---

3. 位级运算 0x69 & 0x77 的结果是（ ）。

   A. 0x60 B. 0x61 C. 0x62 D. 0x63

   答案：

   B

   ---

4. 逻辑运算 !!0x77 的结果用十六进制表示为（ ）。

   A. 0x00 B. 0x77 C. 0x88 D. 0x01

   答案：

   D

   ---

5. 位移运算：对参数 $x=[10011101]_2$，则 x >> 4（算术右移）的结果是（ ）。

   A. $[11011001]_2$ B. $[00001001]_2$ C. $[11111001]_2$ D. $[10001001]_2$

   答案：

   C

   ---

6. 浮点运算 (3.14+1e20)-1e20 在计算机中的运算结果为（ ）。

   A. 3.14 B. 0.0 C. 1e20 D. 0

   答案：

   B

   ---

7. 假设寄存器 %eax 的值为 x，%ecx 的值为 y，则执行汇编指令 leal 9(%eax,%ecx,2),%edx 后，存储在寄存器 %edx 中的值为（ ）。

   A. 9*(x+2y) B. 9*(x+y+2) C. 9+x+y+2 D. 9+x+2y

   答案：

   D

   ---

8. 针对下列 C 代码片段，其输出是（ ）。

   unsigned int x = 0xDEADBEEF;
   unsigned short y = 0xFFFF;
   signed int z = -1;
   if (x > (signed short)y) printf("Hello");
   if (x > z) printf("World");

   A. 没有输出 B. "Hello" C. "World" D. "HelloWorld"

   答案：

   A

   ---

9. 假设一种 8 位浮点数定义为：1 sign, 3 exponent, 4 fraction。下列（ ）表示 $\infty$。

   A. 1 000 1111 B. 0 111 1111 C. 0 100 0000 D. 1 111 0000

   答案：

   D

   ---

10. 假设 %rsp 值为 0xd000b000d000d0d0。执行完指令 pushq %rbx 后，%rsp 的值为（ ）。

    A. 0xd000b000d000d0c8 B. 0xd000b000d000d0cc C. 0xd000b000d000d0d4 D. 0xd000b000d000d0d8

    答案：

    A

    ---

11. 有这样一个磁盘：有 2 个盘片，每个扇区 512 字节，20000 个磁道，每条磁道平均 400 个扇区，则这个磁盘容量是多少（GB）？

    A. 4.1 B. 8.2 C. 16.4 D. 32.8

    答案：

    C

    ---

12. RAM 代表的是（ ）。

    A. 只读存储器 B. 高速缓存器 C. 随机存储器 D. 软盘存储器

    答案：

    C

    ---

13. 对硬盘中某扇区的访问时间不包括（ ）。

    A. 寻道时间 B. CPU 发起磁盘读时间 C. 旋转时间 D. 传送时间

    答案：

    B

    ---

14. 关于程序的局部性原理，正确的是（ ）。

    A. 局部性包括时间局部性和空间局部性 B. 重复引用一个变量具有良好的空间局部性 C. 具有引用模式的程序，步长越大，空间局部性越好 D. CPU 取指令不存在局部性

    答案：

    A

    ---

15. 关于 fork 函数的调用和返回行为的描述，正确的是（ ）。

    A. 调用一次，返回两次 B. 调用一次，返回一次或多次 C. 调用一次，从不返回 D. 调用一次，返回一次

    答案：

    A

---

二、（12 分）

考虑下面基于 IEEE 浮点格式的 8 位浮点表示：1 位符号位、3 位阶码位和 4 位尾数位。请回答下列问题：

1. 偏置量是多少？
2. 请写出最小的正浮点数表示。
3. 请写出最大的正非规格化浮点数表示。
4. 请写出负无穷大的浮点数表示。
5. 请填写下表。

Bits	Decimal Value
0 000 0000	0
1 010 0000	（1）
（2）	-13
（3）	$1/16$
（4）	$15/256$

答案：

1. 偏置量为 3。
2. 最小的正浮点数表示为 0 000 0001，值为 $1/64$。
3. 最大的正非规格化数表示为 0 000 1111，值为 $15/64$。
4. 负无穷大的浮点数表示为 1 111 0000。
5. 表格答案：

空格	答案
（1）	$-1/2$
（2）	1 110 1010
（3）	0 000 0100
（4）	0 000 0100

---

三、（10 分）

某 C 程序中定义了结构类型 st1_t 和 st2_t。

struct st1_t {
    char a;
    char b;
    char c;
};

struct st2_t {
    st1_t d;
    st1_t e;
    st1_t *f;
    short g;
    char h;
    double i;
};

1. 请标出在 X86-64 机型 Linux 系统上 st1_t 结构类型的存储分配（每小格为 1 个字节。用结构成员的名称标记属于各个成员的字节，并用 end 标记结构的结尾，使用 X 标记在结构中用于对齐的字节）。（4 分）

   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

2. 请标出在 X86-64 机型 Linux 系统上 st2_t 结构类型的存储分配（每小格为 1 个字节。用结构成员的名称标记属于各个成员的字节，并 end 标记结构的结尾，使用 X 标记在结构中用于对齐的字节）。（6 分）

   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

答案：

1. st1_t：

+---+---+---+---+
| a | b | c |end|
+---+---+---+---+

2. st2_t：

+---+---+---+---+---+---+---+---+
| d | d | d | e | e | e | X | X |
+---+---+---+---+---+---+---+---+
| f | f | f | f | f | f | f | f |
+---+---+---+---+---+---+---+---+
| g | g | h | X | X | X | X | X |
+---+---+---+---+---+---+---+---+
| i | i | i | i | i | i | i | i |end
+---+---+---+---+---+---+---+---+

---

四、（8 分）

请分析 foo() 函数的汇编代码，并填写其中的缺失部分。

int foo(unsigned int x)
x in %edi
00000000004004f8 <foo>:
4004f8: 53                    push %rbx
4004f9: 89 f8                 mov %edi,%eax
4004fb: 83 ff 01              cmp $0x1,%edi
4004fe: 76 21                 jbe 400521 <foo+0x29>
400500: b8 01 00 00 00        mov $0x1,%eax
400505: b9 00 00 00 00        mov $0x0,%ecx
40050a: ba 02 00 00 00        mov $0x2,%edx
40050f: 39 fa                 cmp %edi,%edx
400511: 77 0e                 ja 400521 <foo+0x29>
400513: 01 c8                 add %ecx,%eax
400515: 89 c3                 mov %eax,%ebx
400517: 29 cb                 sub %ecx,%ebx
400519: 89 d9                 mov %ebx,%ecx
40051b: ff c2                 inc %edx
40051d: 39 fa                 cmp %edi,%edx
40051f: 76 f2                 jbe 400513 <foo+0x1b>
400521: 5b                    pop %rbx
400522: c3                    retq

int foo(unsigned int x)
{
    int a, b, i;
    if (____(1)____)
        ____(2)____;
    a = 1;
    b = 0;
    for (____(3)____; ____(4)____; ____(5)____)
    {
        a = ____(6)____;
        b = ____(7)____;
    }
    return ____(8)____;
}

答案：

1. x <= 1
2. return x
3. i = 2
4. i <= x
5. i++
6. a + b
7. a - b
8. a

---

五、（共 8 分）

a 和 b 表示当前路径中的目标模块或静态库，而 a -> b 表示 a 依赖于 b，也就是说 a 引用了 b 中定义的符号。对于下面三种场景，分别给出使得静态链接器能够解析所有符号引用的最小的命令行（即含有最少数目的目标文件和库参数的命令）。

1. p.o -> libx.a -> p.o
2. p.o -> libx.a -> liby.a 和 liby.a -> libx.a
3. p.o -> libx.a -> liby.a -> libz.a 和 liby.a -> libx.a -> libz.a

答案：

1. gcc p.o libx.a（2 分）
2. gcc p.o libx.a liby.a libx.a（3 分）
3. gcc p.o libx.a liby.a libx.a libz.a（3 分）

---

六、（7 分）

针对下列 C 语言程序，试分析其输出是什么？

#include "caspp.h"
int counter = 1;

int main()
{
    if (fork() == 0) {
        counter--;
        exit(0);
    }
    else {
        wait(NULL);
        printf("counter = %d\n", ++counter);
    }
    exit(0);
}

答案：

counter = 2

---

七、（每小题 3 分，共 15 分）

我们考虑一个大小为 128 字节的数据 Cache，采用 2 路组相联，Cache 块大小为 32 字节。对于下面的代码，我们假设初始时 Cache 为空，除数组 A 外其他所有变量都保存在寄存器中。代码中变量 m 和 n 满足 m * n = 32（m 和 n 正整数）。

double A[32], t = 0;
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        t += A[j*m + i];

请回答下列问题：

1. Cache 中最多可以保存多少数组 A 元素？
2. 该 Cache 有多少组？
3. 当 m 为 1 时：
   1. 试计算 Cache 的不命中率。
   2. 该代码中访问数组 A 是否具有时间局部性特性？
4. 当 m 为 2 时，试计算 Cache 的不命中率。
5. 当 m 为 16 时：
   1. 试计算 Cache 的不命中率。
   2. 该代码中访问数组 A 是否具有空间局部性特性？

答案：

1. 16
2. 2
3. 当 m = 1 时：
   1. Cache 不命中率为 $1/4$。
   2. No
4. 当 m = 2 时，Cache 不命中率为 $1/2$。
5. 当 m = 16 时：
   1. Cache 不命中率为 $1/4$。
   2. Yes

---

八、（10 分）

有一个利用 TLB 加速虚-实地址变换速度的 Cache。有如下假设：

• 虚地址为 32 位。
• 虚页号（VPN）为 24 位。
• 实页号（PPN）为 32 位。
• TLB 采用 2 路组相联，总共有 512 个条目。

与问题 2，3 有关的 TLB 的部分内容如下：

Index	Valid?	Tag	Entry	Valid?	Tag	Entry
3D	1	0x083F	0x0913ABDE	1	0x083E	0xAB18ED24
3E	0	0xF3E9	0x0913ABDE	1	0x083F	0xAB18ED24
3F	1	0x409A	0x0913ABDE	1	0x083F	0xAB18ED24
40	0	0x083E	0x0913ABDE	1	0x3E40	0xAB18ED24

1. 请给出各部分的地址位范围（采用形式如 0-15 表示地址第 0 位至第 15 位）。

   1. 虚地址 VA 中（1）表示 VPO。
   2. 虚地址 VA 中（2）表示 VPN。
   3. 物理地址 PA 中（3）表示 PPO。
   4. 物理地址 PA 中（4）表示 PPN。
   5. VPN 中（5）表示 TLB 索引（TLBI）。
   6. VPN 中（6）表示 TLB 标识（TLBT）。

2. 假设有虚拟地址为 0x083F3E9A，请采用十六进制形式数据填写下表，如果其值无法确定则填写 U。

   Parameter	Value	Parameter	Value
   VPN	（1）	VPO	（2）
   TLBI	（3）	TLBT	（4）
   命中 Cache?（Y/N/U）	（5）	PPN	（6）
   PA	（7）

3. 假设有虚拟地址为 0x083E409B，请采用十六进制形式数据填写下表，如果其值无法确定则填写 U。

   Parameter	Value	Parameter	Value
   VPN	（1）	VPO	（2）
   TLBI	（3）	TLBT	（4）
   命中 Cache?（Y/N/U）	（5）	PPN	（6）
   PA	（7）

答案：

1. 地址位范围：

   1. VPO：0-7
   2. VPN：8-31
   3. PPO：0-7
   4. PPN：8-39
   5. TLBI：0-7
   6. TLBT：8-23

2. 虚拟地址 0x083F3E9A：

   Parameter	Value	Parameter	Value
   VPN	0x083F3E	VPO	0x9A
   TLBI	0x3E	TLBT	0x083F
   命中 Cache?（Y/N/U）	Y	PPN	0xAB18ED24
   PA	0xAB18ED249A

3. 虚拟地址 0x083E409B：

   Parameter	Value	Parameter	Value
   VPN	0x083E40	VPO	0x9B
   TLBI	0x40	TLBT	0x083E
   命中 Cache?（Y/N/U）	N	PPN	U
   PA	U