2022 年计算机系统基础期末真题

#真题

考试日期：2022 年 6 月 22 日。总分 100 分。

一、选择题（20 分）

每题 2 分。

  1. 4 位二进制补码 1001 对应的十进制数是（　）。
    • A. 9
    • B. 7
    • C. -7
    • D. -6
  2. MIPS 中可跳转到 4 GB 空间内任意地址的指令是（　）。
    • A. beq
    • B. j
    • C. jal
    • D. jr
  3. 用 1K×41\text{K}\times4 位 RAM 构造 4K×164\text{K}\times16 位存储器，需要的芯片数和新增高位地址线数是（　）。
    • A. 16 片、3 条
    • B. 16 片、2 条
    • C. 32 片、4 条
    • D. 64 片、4 条
  4. 为消除单周期数据通路的关键路径，可采用流水线提高 CPU 性能。正确的是（　）。
    • A. 流水级越多，CPU 主频必然越高。
    • B. 各阶段中组合逻辑延迟最大者决定最高频率。
    • C. 流水线既提高吞吐率，也减少单条指令的总执行时间。
    • D. 流水线不能让程序指令并行执行。
  5. 虚拟地址先经 TLB 转为物理地址，再访问 Cache。正确的是（　）。
    • A. Cache 命中时，物理页面仍可能没有装入内存。
    • B. 页表项已建立时，TLB 必然不缺失。
    • C. 页表缺失时，TLB 不可能命中。
    • D. 页表缺失时，Cache 可能命中。
  6. 以下哪项不属于进程控制块需要记录的信息？
    • A. 进程标识
    • B. 打开的文件列表
    • C. 使用中的外设
    • D. 进程总数
  7. 关于时间片轮转算法，不正确的是（　）。
    • A. 时间片过长时退化为 FCFS。
    • B. 时间片过短时退化为 SJF。
    • C. 为控制响应时间，需要根据进程数选择时间片。
    • D. 用户可在时间片未用完时主动让出 CPU。
  8. 正确的是（　）。
    • A. 物理地址空间和逻辑地址空间大小必须一致。
    • B. 内存超过 4 GB 时必须采用 64 位操作系统才能管理全部内存。
    • C. 段式内存管理中，用户进程通常不能修改段表。
    • D. 同一个物理地址被不同进程访问时，逻辑地址一定相同。
  9. 正确的是（　）。
    • A. I/O 缓冲用于缓解处理器与外设的速度差异。
    • B. 其他条件相同时，双缓冲一定比单缓冲更快。
    • C. 只有一个处理器时，缓冲不能改善 I/O 性能。
    • D. 把系统缓冲区数据写入磁盘是用户态程序的工作。
  10. 错误的是（　）。
    • A. 发生死锁时，当前资源分配状态一定不安全。
    • B. 只有一个处理器的系统不会死锁。
    • C. 五哲学家就餐问题中，最多允许四人同时就餐可避免死锁。
    • D. 每个进程开始运行时就申请全部资源，可避免死锁。

二、数字逻辑分析（10 分）

状态机有状态 0、1、2，输出分别为 0、0、1。复位进入状态 0；转移如下：

  • 状态 0：A‾\overline{A} 时留在状态 0，AA 时进入状态 1。
  • 状态 1：B‾\overline{B} 时回到状态 0，BB 时进入状态 2。
  • 状态 2：下一拍回到状态 0。
  1. 判断它是 Moore 型还是 Mealy 型。（2 分）
  2. 说明功能。（2 分）
  3. 令 S1S0S_1S_0 的编码 00、01、10 对应三个状态，完成状态转换表及 QQ 的真值表。（3 分）
  4. 写出次态逻辑与 QQ 的逻辑表达式。（3 分）

三、MIPS 汇编（9 分）

1. swap 过程（6 分）

补全交换 v[k] 与 v[k+1] 的 MIPS 代码：

swap: sll $t0, $a1, 2
      add $t0, $t0, $a0
      lw  $t1, ______
      lw  $t2, ______
      sw  $t2, ______
      sw  $t1, ______
      ______

2. 调用 swap(a, 10)（3 分）

la  $a0, ______
li  $a1, ______
______ swap
查看源文件中已填写的内容 
swap: sll $t0, $a1, 2
      add $t0, $t0, $a0
      lw  $t1, 0($t0)
      lw  $t2, 4($t0)
      sw  $t2, 0($t0)
      sw  $t1, 4($t0)
      jr  $ra

la  $a0, a
li  $a1, 10
jal swap

四、Cache（11 分）

主存 1 MB，Cache 16 KB、4 路组相联，块大小 128 B，每块有 1 位有效位和 1 位修改位。

  1. 计算 Cache 组数、主存组数和每个主存组中的块数。（3 分）
  2. 给出主存地址格式。（3 分）
  3. Cache 的 Tag 为多少位？（1 分）
  4. Cache 实际总容量是多少？（2 分）
  5. Cache 存取 10 ns，主存 90 ns；缺失时依次访问主存和 Cache，命中率 0.9。求平均存取时间和相对单级主存的加速比。（2 分）

五、五级流水线 CPU（10 分）

流水线只支持 M 级向 E 级转发，寄存器堆没有内部转发。执行：

L1: add $s0, $t0, $t1
L2: sub $s1, $t2, $t3
L3: and $s2, $s2, $s1
L4: or  $s3, $t4, $t5
L5: slt $s4, $s2, $t3
  1. 列出所有数据相关的指令对与寄存器。（5 分）
  2. 判断是否存在寄存器数据冲突；若有，指出冲突以及现有转发能否解决。若不能，给出至少需要的暂停周期；若没有，说明原因并给出最少总周期数。（5 分）

六、存储管理（10 分）

32 位虚拟存储系统使用两级页表，页大小 4096 B。逻辑地址的 31:22 位为页目录索引，21:12 位为页表索引，11:0 位为页内偏移。页表项与页目录项包含 20 位物理页框号和 12 位标志。

  1. 逻辑地址空间有多少字节？页表共有多少项？（2 分）
  2. 若从逻辑地址 0x80000000 开始映射整个页表，求页目录起始逻辑地址。（4 分）
  3. 逻辑地址 0x12345678 对应的二级页表物理地址为 0x00008000。求对应页表项的物理地址，以及页目录项中的物理页框号。（4 分）

七、磁盘管理（10 分）

磁盘请求柱面序列为 10、22、20、2、40、6、38。初始磁头位于 20，向大柱面号方向移动；每移动一个柱面需 4 ms；柱面编号为 0–50。使用必须扫到边界才反向的电梯算法：

  1. 给出实际访问次序。
  2. 求总寻道时间。
  3. 写出访问每个请求时的时刻、磁头位置和请求队列。只写最终答案不给分。

八、进程同步（10 分）

仓库最多容纳 30 件产品，每次只允许一个产品进出。甲、乙车间分别生产 A、B 产品并共用仓库；仓库满时不能继续生产。三名 A 产品客户和三名 B 产品客户分别取对应产品。

用 P、V 操作实现两个车间和两类客户之间的同步互斥，给出伪代码并说明信号量与主要代码含义。

九、文件系统（10 分）

某索引文件系统的磁盘块为 4 KB。inode 有 10 个直接索引和 1 个一级间接索引。每个 32 位索引由 28 位块区起始块号 begin 与 4 位连续块数 len 组成。每个索引指向一段连续块区；若某索引的 len=0，其后索引的 len 均为 0；各块区互不重叠。

  1. 文件系统最大容量是多少？（3 分）
  2. 最大文件是多少？（3 分）
  3. 存储一个 20 KB 文件时，相关索引的 len 有多少种不同组合？（4 分）

评论