2020 年春《计算机系统基础》期末试卷

考试日期为 2020 年 6 月 23 日。这是一份同时覆盖计算机组成与操作系统的线上考试卷。源 DOCX 没有答案区，我只整理原题，不补写解析；试卷中的代码、流水线和目录树均转录为文本，不使用整页截图。

一、选择题（每题 2 分，共 10 分）

1. 无条件跳转

无条件转移指令 j 的功能是将指令中的地址码（立即数）送入（　）。

A. PC

B. ALU

C. 累加器

D. 地址寄存器

2. 定点减法

计算机进行定点二进制运算时，减法一般通过（　）实现。

A. 原码运算的二进制减法器

B. 补码运算的二进制减法器

C. 补码运算的十进制加法器

D. 补码运算的二进制加法器

3. RAM 扩展

用 $1\mathrm{K}\times4$ 位 RAM 芯片构造 $16\mathrm{K}\times8$ 位存储器，需要的芯片数和新增高位地址线数分别为（　）。

A. 16 片和 3 条

B. 32 片和 4 条

C. 64 片和 5 条

D. 128 片和 6 条

4. 分支后的 PC

下列代码起始地址为 0x00001234，$t0 初值为 -1。分支指令执行完后，PC 的值为（　）。

Label: addi $t0, $t0, 1
       bgtz $t0, Label

A. 0x00001234

B. 0x00001238

C. 0x0000123C

D. 0x00001240

5. 虚存与 Cache

假设虚存系统先把虚拟地址转换为物理地址，再访问 Cache。对于可被 Cache 缓存的某个物理页面，以下判断错误的是（　）。

A. 若页表项已建立，则 TLB 可能缺失。

B. 若 Cache 命中，则物理页面必然已经装载。

C. 若 TLB 命中，则页表项必然已建立。

D. 若 TLB 缺失，则 Cache 必然命中。

二、简答题（每题 5 分，共 15 分）

1. 逻辑函数化简

将下列逻辑函数化为最简与或式：

F=\overline{AB+BC}+\overline{A}C.

2. MIPS 指令格式

给定以下 C 代码及其 MIPS 汇编代码：

while (A[i] == k)
    i++;

Loop: sll  $9, $19, 2
      add  $9, $9, $22
      lw   $8, 0($9)
      bne  $8, $21, Exit
      addi $19, $19, 1
      j    Loop
Exit:

列出代码片段中所有 R 型指令，并任选一条，以二进制写出它的第 31 到 6 位。（2 分）
列出代码片段中所有 I 型指令，并任选一条，以二进制写出它的第 25 到 0 位。（3 分）

原卷为两类指令分别给出的字段框如下：

R 型第 31—6 位：31—26 | 25—21 | 20—16 | 15—11 | 10—6
I 型第 25—0 位：25—21 | 20—16 | 15—0

3. 页式虚拟存储

一个按字节编址的页式虚存系统，虚存空间为 16 GB，物理内存为 256 MB，页大小为 16 KB。每个页表项还包含 1 位有效位和 1 位修改位，假设所有虚拟页都在使用。

虚地址中的虚页号和页内偏移各有多少位？（1 分）
实地址中的实页号和页内偏移各有多少位？（1 分）
每个进程的虚拟空间最多有多少页？（1 分）
每个页表项共有多少位？（1 分）
每个进程的页表大小是多少？（1 分）

三、MIPS 汇编语言（共 10 分）

计算机系统中的功能既可由硬件实现，也可由软件实现，例如溢出检测。有符号加法中，如果两个加数同号，而结果与加数异号，就发生了溢出。

1. 补全溢出检测程序（6 分）

在 add $s0, $s1, $s2 之后执行检测；发生溢出时跳到 overflow 标签。补全下面程序。

xor $t0, __________, __________
slt $t1, $t0, $zero
bne $t1, $zero, no_overflow

xor $t0, __________, __________
slt $t1, $t0, $zero
bne $t1, $zero, overflow

no_overflow:
    j nextins

overflow:
    # 溢出处理

nextins:
    # ...

2. 分支偏移量（4 分）

如果不用标签，而直接用十进制数表示，两条 bne 的跳转偏移量分别是多少？

no_overflow = __________
overflow    = __________

四、Cache（共 6 分）

某机主存容量为 64 KB。Cache 采用 4 路组相联结构，容量为 1 KB，数据块大小为 16 B；每块需要 1 位有效位和 1 位修改位，替换策略为 LRU。假设 Cache 初始为空。程序依次访问以下 10 个主存单元：

A70FH, B608H, A30DH, D302H, E200H,
A30BH, F104H, B708H, F114H, B738H

计算 Cache 块数、Cache 组数，并给出主存地址格式，包括字段名称和位数。（5 分）
Cache 的实际总容量是多少字节？（1 分）

五、CPU（共 9 分）

一条五级流水线只支持 W 级到 E 级的一条转发，而且寄存器堆没有内部转发。原图还表明：取指后依次经过 D、E、M、W 流水寄存器；D 段读寄存器；E 段执行 ALU；M 段访问数据存储器；W 段选择存储器读数或 ALU 结果回写；唯一转发路径从 W 段回到 E 段的 ALU 输入。

给定代码：

I1: lw  $1, 0($2)
I2: add $3, $1, $2
I3: sw  $1, 4($2)
I4: or  $5, $6, $7
I5: sub $8, $6, $7

指出这些指令在上述流水线中执行时存在的所有数据相关。（4 分）
调整指令顺序，在保持程序语义的前提下尽可能减少暂停。（5 分）

六、内存管理（共 15 分）

一个 32 位虚拟存储系统采用两级页表，每页 4096 字节。逻辑地址第 22 到 31 位是第一级页表（页目录）索引，第 12 到 21 位是第二级页表索引，第 0 到 11 位是页内偏移。每个页表或页目录项包含 20 位物理页框号和 12 位标志位。

逻辑地址空间共有多少字节？第一级页表占多大空间？第二级页表共有多少页表项？（3 分）
假设第一级页表的起始逻辑地址为 0xC0300000，给出逻辑地址 0x01234567 对应页目录项的逻辑地址，并写出计算过程。（4 分）
假设系统从逻辑地址 0x8C000000 开始映射整个页表，给出第一级页表的起始逻辑地址，并写出计算过程。（4 分）
假设逻辑地址 0x89ABCDEF 对应的第二级页表物理地址为 0x00008000，给出该逻辑地址对应页表项的物理地址，以及对应页目录项中包含的物理页框号，并写出计算过程。（4 分）

七、进程同步（共 15 分）

有 $n$ 个旅客和一辆汽车，旅客在汽车停靠的站点反复乘车。汽车一次可乘 $M$ 个旅客，且 $M<n$ 。坐满 $M$ 人后，汽车出发绕一圈，回到原站点让旅客下车，然后重复这个过程。

同步条件如下：

旅客能够上车和下车。
汽车能够载客、运行和卸客。
只有汽车可以载客时，旅客才可上车。
只有 $M$ 个旅客都上车后，汽车才可出发。
只有汽车可以卸客时，旅客才可下车。
只有旅客全部下车后，汽车才能重新载客。

请用 P、V 操作实现旅客和汽车之间的同步关系。

八、调度算法（共 10 分）

一个作业调度系统同时只能执行一个作业，接收情况如下：

作业编号	到达时刻/s	执行时间/s	优先级
1	0	4	3
2	0	2	4
3	1	3	5
4	4	3	1
5	7	2	2
6	7	1	4
7	8	4	3

优先级数越大，优先级越高。

采用短作业优先调度时，最早完成的是哪个作业？计算全部作业的平均周转时间，并写出过程。（5 分）
采用可抢占的优先级调度时，高优先级作业可以抢占低优先级作业；同一优先级按先来先服务。最晚完成的是哪个作业？计算全部作业的平均周转时间，并写出过程。（5 分）

九、文件系统（共 10 分）

某文件系统以硬盘为文件存储器，物理块大小为 512 B。文件 A 含 590 个逻辑记录，每个记录占 255 B，每个物理块存 2 个记录。每个目录项占 127 B，每个物理块存 4 个目录项，文件属性直接存于目录项中。根目录内容常驻内存，其他目录不在内存。

原卷目录树可转录为：

root
├── usr1
│   ├── d1
│   └── d2
├── usr2
│   ├── d3
│   ├── d4
│   └── d5
└── usr3
    └── A

若采用链接分配（串联文件），把文件 A 读入内存至少要访问多少次硬盘？（4 分）
若采用连续分配，读取逻辑记录号为 480 的记录至少要访问多少次硬盘？（4 分）
在采用索引的文件系统中，索引节点有 10 个直接索引、1 个一次间接索引和 1 个二次间接索引。物理块为 512 字节，文件块号为 4 字节。该文件系统支持的最大文件有多大？（2 分）