操作系统计算题专项练习（10题）

1. 银行家算法

题目内容：
某系统使用银行家算法避免死锁。当前系统资源情况如下：

  • 可用资源向量 Available = (3, 3, 2)
  • 系统中有 5 个进程 P0~P4，3 种资源 A（共 10 个）、B（共 5 个）、C（共 7 个）

各进程的 Allocation（已分配）和 Max（最大需求）矩阵如下：

进程 Allocation (A, B, C) Max (A, B, C)
P0 (0, 1, 0) (7, 5, 3)
P1 (2, 0, 0) (3, 2, 2)
P2 (3, 0, 2) (9, 0, 2)
P3 (2, 1, 1) (2, 2, 2)
P4 (0, 0, 2) (4, 3, 3)

请回答：

  1. 当前系统是否处于安全状态？如果安全，给出一个安全序列。
  2. 如果进程 P1 发出请求 Request₁ = (1, 0, 2)，系统能否将资源分配给它？为什么？

考点：银行家算法的安全性检查和资源请求判定

来源章节：第 8 章 — 死锁与银行家算法

完整解答过程：

步骤1：计算 Need 矩阵
Need[i] = Max[i] - Allocation[i]

进程 Need (A, B, C)
P0 (7, 4, 3)
P1 (1, 2, 2)
P2 (6, 0, 0)
P3 (0, 1, 1)
P4 (4, 3, 1)

步骤2：安全性检查
Available = (3, 3, 2)

轮次 Work（当前可用） 可满足的进程 原因
第1轮 (3, 3, 2) P1: Need(1,2,2) ≤ Work(3,3,2) ✓ P1 的 Need 均 ≤ Work
P3: Need(0,1,1) ≤ Work(3,3,2) ✓ P3 也可满足，选择任一均可
选 P1 Finish[P1]=True Work = (3,3,2)+(2,0,0) = (5,3,2) 释放 P1 的 Allocation
第2轮 (5, 3, 2) P3: Need(0,1,1) ≤ (5,3,2) ✓
选 P3 Finish[P3]=True Work = (5,3,2)+(2,1,1) = (7,4,3)
第3轮 (7, 4, 3) P0: Need(7,4,3) ≤ (7,4,3) ✓
P4: Need(4,3,1) ≤ (7,4,3) ✓
P2: Need(6,0,0) ≤ (7,4,3) ✓
选 P0 Finish[P0]=True Work = (7,4,3)+(0,1,0) = (7,5,3)
第4轮 (7, 5, 3) P2: Need(6,0,0) ≤ (7,5,3) ✓
P4: Need(4,3,1) ≤ (7,5,3) ✓
选 P2 Finish[P2]=True Work = (7,5,3)+(3,0,2) = (10,5,5)
第5轮 (10, 5, 5) P4: Need(4,3,1) ≤ (10,5,5) ✓
选 P4 Finish[P4]=True Work = (10,5,5)+(0,0,2) = (10,5,7)

所有 Finish[i] = True，存在安全序列 <P1, P3, P0, P2, P4>。

答（第1问）：系统当前处于安全状态，一个安全序列为 <P1, P3, P0, P2, P4>（注意安全序列不唯一）。

步骤3：判断 P1 的请求 Request₁ = (1, 0, 2)

(1) Request₁(1,0,2) ≤ Need₁(1,2,2) ✓
(2) Request₁(1,0,2) ≤ Available(3,3,2) ✓
(3) 尝试分配，更新状态：
- Available’ = (3,3,2) - (1,0,2) = (2,3,0)
- Allocation₁’ = (2,0,0) + (1,0,2) = (3,0,2)
- Need₁’ = (1,2,2) - (1,0,2) = (0,2,0)

步骤4：对新状态进行安全性检查

进程 Allocation’ Need’
P0 (0, 1, 0) (7, 4, 3)
P1 (3, 0, 2) (0, 2, 0)
P2 (3, 0, 2) (6, 0, 0)
P3 (2, 1, 1) (0, 1, 1)
P4 (0, 0, 2) (4, 3, 1)

Work = Available’ = (2, 3, 0)

轮次 Work 可满足进程
第1轮 (2, 3, 0) P1: Need(0,2,0) ≤ (2,3,0) ✓
选P1后 (2,3,0)+(3,0,2) = (5,3,2)
第2轮 (5, 3, 2) P3: Need(0,1,1) ≤ (5,3,2) ✓
选P3后 (5,3,2)+(2,1,1) = (7,4,3)
第3轮 (7, 4, 3) P0: Need(7,4,3) ≤ (7,4,3) ✓
选P0后 (7,4,3)+(0,1,0) = (7,5,3)
第4轮 (7, 5, 3) P2: Need(6,0,0) ≤ (7,5,3) ✓
选P2后 (7,5,3)+(3,0,2) = (10,5,5)
第5轮 (10, 5, 5) P4: Need(4,3,1) ≤ (10,5,5) ✓
选P4后 (10,5,5)+(0,0,2) = (10,5,7)

新状态仍然安全，安全序列 <P1, P3, P0, P2, P4>。

答（第2问）：可以分配，分配后系统仍处于安全状态。

2. 分段地址转换

题目内容：
某系统采用分段存储管理，段表如下所示。请将以下逻辑地址转换为物理地址。

段表：

段号 段长 基址
0 600 2100
1 200 3500
2 500 1200
3 800 6800

逻辑地址（段号, 段内偏移）：

  1. (0, 250)
  2. (1, 150)
  3. (2, 600)
  4. (3, 400)

考点：分段地址转换的原理与越界检查

来源章节：第 5 章 — 内存管理之分段存储

完整解答过程：

基本公式：物理地址 = 段基址 + 段内偏移
条件：段内偏移必须 < 段长，否则产生"越界中断"。

  1. 逻辑地址 (0, 250)

    • 段号 0：段长 = 600，基址 = 2100
    • 检查越界：250 < 600 ✓
    • 物理地址 = 2100 + 250 = 2350
    • 答：(0, 250) → 物理地址 2350

  2. 逻辑地址 (1, 150)

    • 段号 1：段长 = 200，基址 = 3500
    • 检查越界：150 < 200 ✓
    • 物理地址 = 3500 + 150 = 3650
    • 答：(1, 150) → 物理地址 3650

  3. 逻辑地址 (2, 600)

    • 段号 2：段长 = 500，基址 = 1200
    • 检查越界：600 ≥ 500 ✗ —— 越界！
    • 答：(2, 600) 段内偏移越界，产生段越界中断，无法转换。

  4. 逻辑地址 (3, 400)

    • 段号 3：段长 = 800，基址 = 6800
    • 检查越界：400 < 800 ✓
    • 物理地址 = 6800 + 400 = 7200
    • 答：(3, 400) → 物理地址 7200

3. 分页地址转换

题目内容：
某系统采用分页存储管理，页面大小为 4KB（4096 字节）。已知某进程的页表如下：

逻辑页号 物理帧号
0 3
1 7
2 1
3 5
4 8
5 2

请将以下虚拟地址转换为物理地址：

  1. 虚拟地址 0x2A3C
  2. 虚拟地址 0x1120
  3. 虚拟地址 0x54A8

考点：分页地址转换、页号与页内偏移的提取

来源章节：第 5 章 — 内存管理之分页存储

完整解答过程：

已知条件：

  • 页面大小 = 4KB = 4096B = 2¹²，页内偏移占 12 位
  • 逻辑地址中：高 20 位为页号，低 12 位为页内偏移

步骤：

  1. 将十六进制地址转为二进制或直接计算：页号 = 地址 / 4096（整除），偏移 = 地址 % 4096

1. 虚拟地址 0x2A3C

  • 0x2A3C = 10812（十进制）
  • 逻辑页号 = 10812 ÷ 4096 = 2（商）
  • 物理偏移 = 10812 % 4096 = 10812 - 2×4096 = 10812 - 8192 = 2620 = 0xA3C
  • 查页表：页号 2 → 物理帧号 1
  • 物理地址 = 帧号 × 4096 + 偏移 = 1 × 4096 + 2620 = 6716 = 0x1A3C
  • 答：0x2A3C → 物理地址 0x1A3C（6716）

2. 虚拟地址 0x1120

  • 0x1120 = 4384（十进制）
  • 页号 = 4384 ÷ 4096 = 1
  • 偏移 = 4384 % 4096 = 288 = 0x120
  • 查页表：页号 1 → 物理帧号 7
  • 物理地址 = 7 × 4096 + 288 = 28672 + 288 = 28960 = 0x7120
  • 答：0x1120 → 物理地址 0x7120（28960）

3. 虚拟地址 0x54A8

  • 0x54A8 = 21672（十进制）
  • 页号 = 21672 ÷ 4096 = 5
  • 偏移 = 21672 % 4096 = 21672 - 5×4096 = 21672 - 20480 = 1192 = 0x4A8
  • 查页表：页号 5 → 物理帧号 2
  • 物理地址 = 2 × 4096 + 1192 = 8192 + 1192 = 9384 = 0x24A8
  • 答：0x54A8 → 物理地址 0x24A8（9384）

【扩展】二级页表计算：

假设某系统有 32 位虚拟地址，页面大小 4KB，页表项大小 4B。

  • 页内偏移 = 12 位（2¹² = 4KB）
  • 剩余 20 位用于页号
  • 若采用一级页表：页表大小为 2²⁰ × 4B = 4MB（过大）
  • 若采用二级页表：将 20 位页号分为 10 位一级页号 + 10 位二级页号
    • 一级页表大小 = 2¹⁰ × 4B = 4KB
    • 每个二级页表大小 = 2¹⁰ × 4B = 4KB
    • 地址转换：虚拟地址 → 一级页号 → 查一级页表得二级页表基址 → 二级页号 → 查二级页表得物理帧号 → 拼接偏移得物理地址

4. FCFS / SJF / HRRN 调度算法

题目内容：
考虑下列一组进程，所有时间单位为毫秒：

进程 到达时间 执行时间（CPU突发时间）
P1 0 8
P2 1 4
P3 2 9
P4 3 5

请分别使用以下算法计算每个进程的周转时间、等待时间和平均周转时间，并画出甘特图：

  1. FCFS（先来先服务）
  2. SJF（非抢占式短作业优先）
  3. HRRN（最高响应比优先）

考点：调度算法的性能比较（周转时间、等待时间）

来源章节：第 4 章 — 处理器调度

完整解答过程：

(1) FCFS（先来先服务）

按到达时间顺序调度：P1 → P2 → P3 → P4

甘特图：

P1        P2    P3              P4
|---------|-----|---------------|-----|
0         8     12              21    26

计算过程：

进程 到达 执行 开始 完成 周转时间(TAT) 等待时间
P1 0 8 0 8 8-0 = 8 0
P2 1 4 8 12 12-1 = 11 8-1 = 7
P3 2 9 12 21 21-2 = 19 12-2 = 10
P4 3 5 21 26 26-3 = 23 21-3 = 18

平均周转时间 = (8 + 11 + 19 + 23) / 4 = 61 / 4 = 15.25 ms
平均等待时间 = (0 + 7 + 10 + 18) / 4 = 35 / 4 = 8.75 ms

(2) SJF（非抢占式短作业优先）

执行顺序判断：

  • 时刻 0：只有 P1 已到达，执行 P1（0~8）
  • 时刻 8：P2、P3、P4 均已到达，比较执行时间：P2(4) < P4(5) < P3(9)
  • 执行顺序：P1 → P2 → P4 → P3

甘特图：

P1        P2    P4    P3
|---------|-----|-----|---------------|
0         8     12    17              26

计算过程：

进程 到达 执行 开始 完成 周转时间 等待时间
P1 0 8 0 8 8 0
P2 1 4 8 12 11 7
P4 3 5 12 17 14 9
P3 2 9 17 26 24 15

平均周转时间 = (8 + 11 + 14 + 24) / 4 = 57 / 4 = 14.25 ms
平均等待时间 = (0 + 7 + 9 + 15) / 4 = 31 / 4 = 7.75 ms

(3) HRRN（最高响应比优先）

响应比公式：R = (等待时间 + 执行时间) / 执行时间 = 1 + 等待时间 / 执行时间

  • 时刻 0：只有 P1，执行 P1（0~8）
  • 时刻 8：计算等待进程的响应比
    • P2：R = 1 + (8-1)/4 = 1 + 7/4 = 2.75
    • P3：R = 1 + (8-2)/9 = 1 + 6/9 = 1.67
    • P4：R = 1 + (8-3)/5 = 1 + 5/5 = 2.00
    • P2 的响应比最高（2.75），执行 P2（8~12）
  • 时刻 12：计算剩余进程的响应比
    • P3：R = 1 + (12-2)/9 = 1 + 10/9 = 2.11
    • P4：R = 1 + (12-3)/5 = 1 + 9/5 = 2.80
    • P4 的响应比最高（2.80），执行 P4（12~17）
  • 时刻 17：只剩 P3，执行 P3（17~26）

甘特图：

P1        P2    P4    P3
|---------|-----|-----|---------------|
0         8     12    17              26

计算过程：

进程 到达 执行 开始 完成 周转时间 等待时间
P1 0 8 0 8 8 0
P2 1 4 8 12 11 7
P4 3 5 12 17 14 9
P3 2 9 17 26 24 15

平均周转时间 = (8 + 11 + 14 + 24) / 4 = 14.25 ms
平均等待时间 = (0 + 7 + 9 + 15) / 4 = 7.75 ms

注意：在本例中 HRRN 和 SJF 的结果相同，这是因为在时刻 8 时 P2 既是执行时间最短的也是响应比最高的。HRRN 的优势在进程执行时间差异大、等待时间差异大时更能体现。

5. RR 时间片轮转调度

题目内容：
考虑下列一组进程，使用时间片轮转（Round-Robin）调度算法，时间片 q = 3 ms。

进程 到达时间 执行时间（CPU突发时间）
P1 0 5
P2 1 3
P3 2 8
P4 4 2

请计算每个进程的完成时间、周转时间和等待时间，并画出调度甘特图。

考点：RR 时间片轮转调度的执行过程分析

来源章节：第 4 章 — 处理器调度

完整解答过程：

规则：就绪队列按到达时间排队，先到的先入队。每个进程运行一个时间片（最多 3 ms），若执行完毕则退出，否则放回队尾。

分步追踪：

就绪队列初始为空，用 [ ] 表示队列状态（左侧为队头）。

  • t=0：P1 到达，就绪队列：[P1(剩余5)]。调度 P1。
  • t=0~3：P1 运行 3 ms，剩余 2 ms。t=1时P2到达入队，t=2时P3到达入队。
    • P1 时间片用完，放回队尾。就绪队列：[P2(3), P3(8), P1(2)]
  • t=3~6：调度 P2，运行 3 ms，剩余 0 ms。P2 执行完毕。
    • t=4时P4到达，入队。就绪队列：[P3(8), P1(2), P4(2)]
  • t=6~9：调度 P3，运行 3 ms，剩余 5 ms。时间片用完放回队尾。就绪队列：[P1(2), P4(2), P3(5)]
  • t=9~11：调度 P1，运行 2 ms，剩余 0 ms。P1 执行完毕。
    • 就绪队列：[P4(2), P3(5)]
  • t=11~13：调度 P4，运行 2 ms，剩余 0 ms。P4 执行完毕。
    • 就绪队列：[P3(5)]
  • t=13~16：调度 P3，运行 3 ms，剩余 2 ms。时间片用完放回队尾。就绪队列：[P3(2)]
  • t=16~18：调度 P3，运行 2 ms，剩余 0 ms。P3 执行完毕。

甘特图：

P1    P2    P3    P1    P4    P3    P3
|-----|-----|-----|-----|-----|-----|-----|
0     3     6     9     11    13    16    18

结果汇总：
由于P4是第二个窗口抵达的，因此在第二个窗口前的队列是[1 2 3]->[2 3 1]在第四刻P4加入 变成[2 3 1 4]

进程 到达时间 完成时间 周转时间 等待时间
P1 0 11 11 11-5 = 6
P2 1 6 5 5-3 = 2
P3 2 18 16 16-8 = 8
P4 4 13 9 9-2 = 7

计算说明：

  • 周转时间 = 完成时间 - 到达时间
  • 等待时间 = 周转时间 - 执行时间

平均周转时间 = (11 + 5 + 16 + 9) / 4 = 41 / 4 = 10.25 ms
平均等待时间 = (6 + 2 + 8 + 7) / 4 = 23 / 4 = 5.75 ms

6. 内存分配算法（动态分区分配）

题目内容：
某系统采用动态分区分配方式管理内存，内存大小为 1024 KB。当前空闲分区链中有以下空闲分区（按地址从小到大排列）：

分区 起始地址 大小
空闲1 0 50 KB
空闲2 100 200 KB
空闲3 500 80 KB
空闲4 800 150 KB
空闲5 1000 24 KB

进程请求分配内存，请求序列如下（按顺序）：

  1. 请求 A：120 KB
  2. 请求 B：50 KB
  3. 请求 C：90 KB
  4. 请求 D：30 KB

请分别使用 首次适应（First-Fit）、最佳适应（Best-Fit） 和 最差适应（Worst-Fit） 算法，说明每个请求分配到哪个空闲分区，并给出每次分配后的空闲分区列表。如果不能分配，请说明原因。

考点：动态分区分配算法（First-Fit、Best-Fit、Worst-Fit）

来源章节：第 5 章 — 内存管理之动态分区分配

完整解答过程：

(1) 首次适应算法（First-Fit）

按地址顺序查找第一个足够大的空闲分区。

初始空闲列表：[50(0), 200(100), 80(500), 150(800), 24(1000)]
（格式：大小KB(起始地址)）

① 请求 A：120 KB

  • 50(0) → 不足，跳过
  • 200(100) → 120 ≤ 200，分配。剩余：200-120 = 80 KB，起始地址 100+120 = 220
  • 新空闲列表：[50(0), 80(220), 80(500), 150(800), 24(1000)]

② 请求 B：50 KB

  • 50(0) → 50 ≤ 50，正好分配！移除该分区
  • 新空闲列表：[80(220), 80(500), 150(800), 24(1000)]

③ 请求 C：90 KB

  • 80(220) → 不足，跳过
  • 80(500) → 不足，跳过
  • 150(800) → 90 ≤ 150，分配。剩余：150-90 = 60 KB，起始地址 800+90 = 890
  • 新空闲列表：[80(220), 80(500), 60(890), 24(1000)]

④ 请求 D：30 KB

  • 80(220) → 30 ≤ 80，分配。剩余：80-30 = 50 KB，起始地址 220+30 = 250
  • 新空闲列表：[50(250), 80(500), 60(890), 24(1000)]

First-Fit 结果：4 个请求全部成功分配。

(2) 最佳适应算法（Best-Fit）

查找大小最接近请求的空闲分区（即能满足要求的最小空闲分区）。

初始空闲列表：[50(0), 200(100), 80(500), 150(800), 24(1000)]

① 请求 A：120 KB

  • 查找 ≥ 120 的最小分区：150(800)（差值30）或 200(100)（差值80）
  • 选 150(800)。剩余：150-120 = 30 KB，起始地址 800+120 = 920
  • 新空闲列表：[24(1000), 30(920), 50(0), 80(500), 200(100)]（按大小排序后）
  • 实际上按地址排序：[50(0), 200(100), 80(500), 30(920), 24(1000)]

② 请求 B：50 KB

  • 查找 ≥ 50 的最小分区：50(0) 正好！
  • 移除 50(0)
  • 新空闲列表：[200(100), 80(500), 30(920), 24(1000)]

③ 请求 C：90 KB

  • 查找 ≥ 90 的最小分区：200(100)（差值110）或 80(500)（不足），
  • 选 200(100)。剩余：200-90 = 110 KB，起始地址 100+90 = 190
  • 新空闲列表：[80(500), 110(190), 30(920), 24(1000)]

④ 请求 D：30 KB

  • 查找 ≥ 30 的最小分区：30(920) 正好！
  • 移除 30(920)
  • 新空闲列表：[80(500), 110(190), 24(1000)]

Best-Fit 结果：4 个请求全部成功分配。

(3) 最差适应算法（Worst-Fit）

查找最大的空闲分区进行分配。

初始空闲列表：[50(0), 200(100), 80(500), 150(800), 24(1000)]

① 请求 A：120 KB

  • 最大空闲分区：200(100)，分配 120 KB
  • 剩余：200-120 = 80 KB，起始地址 100+120 = 220
  • 新空闲列表：[150(800), 80(500), 80(220), 50(0), 24(1000)]（按大小排序）
  • 按地址：[50(0), 80(220), 80(500), 150(800), 24(1000)]

② 请求 B：50 KB

  • 最大空闲分区：150(800)，分配 50 KB
  • 剩余：150-50 = 100 KB，起始地址 800+50 = 850
  • 新空闲列表：[100(850), 80(500), 80(220), 50(0), 24(1000)]

③ 请求 C：90 KB

  • 最大空闲分区：100(850)，分配 90 KB
  • 剩余：100-90 = 10 KB，起始地址 850+90 = 940
  • 新空闲列表：[80(500), 80(220), 50(0), 24(1000), 10(940)]

④ 请求 D：30 KB

  • 最大空闲分区：80(500)，分配 30 KB
  • 剩余：80-30 = 50 KB，起始地址 500+30 = 530
  • 新空闲列表：[80(220), 50(530), 50(0), 24(1000), 10(940)]

Worst-Fit 结果：4 个请求全部成功分配。

算法对比总结：

算法 分配结果 特点
First-Fit 成功分配，产生较多小碎片 地址导向，速度较快
Best-Fit 成功分配，产生极小碎片 容易产生很多无法利用的小碎片
Worst-Fit 成功分配，剩余分区较均衡 减少小碎片，但大分区被快速消耗

7. 页面置换算法

题目内容：
某进程的页面访问序列（引用串）为：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

系统为该进程分配 3 个物理帧（初始为空）。请分别使用以下算法计算缺页次数和缺页率。

  1. FIFO（先进先出页面置换）
  2. LRU（最近最久未使用页面置换）
  3. OPT（最优页面置换）

考点：页面置换算法的缺页率分析

来源章节：第 5 章 — 内存管理之虚拟内存（页面置换）

完整解答过程：

(1) FIFO 算法

缺页率 = 缺页次数 / 总访问次数。

序号 访问页面 帧1 帧2 帧3 是否缺页 说明
1 7 7 缺页✓ 装入 7
2 0 7 0 缺页✓ 装入 0
3 1 7 0 1 缺页✓ 装入 1
4 2 2 0 1 缺页✓ 替换 7（最先进）
5 0 2 0 1 命中 0 已在
6 3 2 3 1 缺页✓ 替换 0（先进）
7 0 2 3 0 缺页✓ 替换 1（先进）
8 4 4 3 0 缺页✓ 替换 2（先进）
9 2 4 2 0 缺页✓ 替换 3（先进）
10 3 4 2 3 缺页✓ 替换 0（先进）
11 0 4 2 0 缺页✓ 替换 3（先进？实际上是替换了3，但需仔细看）

等一下，让我更仔细地追踪 FIFO 的队列顺序。FIFO 需要维护一个页面进入帧的顺序队列。

FIFO 详细追踪（队列：左为最老，右为最新）：

步骤 页面 帧内容（按加载时间） 队列（老→新） 缺页
1 7 [7, -, -] [7] ✓
2 0 [7, 0, -] [7, 0] ✓
3 1 [7, 0, 1] [7, 0, 1] ✓
4 2 [2, 0, 1] [0, 1, 2] ✓ 替换7
5 0 [2, 0, 1] [0, 1, 2] ✗
6 3 [2, 3, 1] [1, 2, 3] ✓ 替换0
7 0 [2, 3, 0] [2, 3, 0] ✓ 替换1
8 4 [4, 3, 0] [3, 0, 4] ✓ 替换2
9 2 [4, 2, 0] [0, 4, 2] ✓ 替换3
10 3 [4, 2, 3] [4, 2, 3] ✓ 替换0
11 0 [0, 2, 3] [2, 3, 0] ✓ 替换4
12 3 [0, 2, 3] [2, 3, 0] ✗
13 2 [0, 2, 3] [2, 3, 0] ✗
14 1 [0, 1, 3] [3, 0, 1] ✓ 替换2
15 2 [0, 1, 2] [0, 1, 2] ✓ 替换3
16 0 [0, 1, 2] [0, 1, 2] ✗
17 1 [0, 1, 2] [0, 1, 2] ✗
18 7 [7, 1, 2] [1, 2, 7] ✓ 替换0
19 0 [7, 0, 2] [2, 7, 0] ✓ 替换1
20 1 [7, 0, 1] [7, 0, 1] ✓ 替换2

FIFO 缺页次数 = 15 次
缺页率 = 15/20 = 75%

(2) LRU 算法

LRU 替换最长时间未被使用的页面。

LRU 详细追踪（帧内容按 LRU 顺序，最左为最近最久未使用）：

步骤 页面 帧内容（最近使用→最久未使用） 缺页
1 7 [7] ✓
2 0 [0, 7] ✓
3 1 [1, 0, 7] ✓
4 2 [2, 1, 0] ✓ 替换7
5 0 [0, 2, 1] ✗ 0命中，移至最近
6 3 [3, 0, 2] ✓ 替换1
7 0 [0, 3, 2] ✗ 0命中，移至最近
8 4 [4, 0, 3] ✓ 替换2
9 2 [2, 4, 0] ✓ 替换3
10 3 [3, 2, 4] ✓ 替换0
11 0 [0, 3, 2] ✓ 替换4
12 3 [3, 0, 2] ✗ 3命中，移至最近
13 2 [2, 3, 0] ✗ 2命中，移至最近
14 1 [1, 2, 3] ✓ 替换0
15 2 [2, 1, 3] ✗ 2命中，移至最近
16 0 [0, 2, 1] ✓ 替换3
17 1 [1, 0, 2] ✗ 1命中，移至最近
18 7 [7, 1, 0] ✓ 替换2
19 0 [0, 7, 1] ✗ 0命中，移至最近
20 1 [1, 0, 7] ✗ 1命中，移至最近

LRU 缺页次数 = 12 次
缺页率 = 12/20 = 60%

(3) OPT 算法（Optimal，最优置换）

OPT 替换未来最长时间不会被使用的页面。

OPT 详细追踪（需要预知未来的访问序列以决定替换哪个页面）：

步骤 页面 帧内容 缺页 替换决策（未来最远使用的页面）
1 7 [7] ✓ —
2 0 [7, 0] ✓ —
3 1 [7, 0, 1] ✓ —
4 2 [2, 0, 1] ✓ 7在未来步18才用，最远 → 替换7
5 0 [2, 0, 1] ✗ —
6 3 [2, 0, 3] ✓ 替换1，因为1未来在步14，而2在步9，0在步11，所以1最远
7 0 [2, 0, 3] ✗ —
8 4 [2, 0, 4] ✓ 替换3，因为3未来在步10(较近)，而2在步9，0在步11；故4在步8后不再使用 → 替换3
9 2 [2, 0, 4] ✗ —
10 3 [2, 0, 3] ✓ 替换4（4不再出现）
11 0 [2, 0, 3] ✗ —
12 3 [2, 0, 3] ✗ —
13 2 [2, 0, 3] ✗ —
14 1 [1, 0, 3] ✓ 2未来在步15较近，0在步16，3在步…其实3不再出现（步12后3不再使用）。所以替换3或2？步13后2在步15用，3不用了。替换2或3。3不用了 → 替换3或2，选不用的那个。替换3较好
15 2 [1, 0, 2] ✓ 替换…实际上在第14步我替换了3，所以帧是[1,0,3]，步15访问2，2不在，缺页。帧中1在步17，0在步16，3不再用 → 替换3
16 0 [1, 0, 2] ✗ —
17 1 [1, 0, 2] ✗ —
18 7 [7, 0, 2] ✓ 1在步17后用完了，替换1
19 0 [7, 0, 2] ✗ —
20 1 [7, 0, 1] ✓ 替换2（2不再出现）

让我们重新仔细做 OPT：

初始帧：空

  1. 7 → 缺页，帧：[7]
  2. 0 → 缺页，帧：[7, 0]
  3. 1 → 缺页，帧：[7, 0, 1]
  4. 2 → 缺页，帧：[2, 0, 1] — 替换7（7在步18才出现，最远）
  5. 0 → 命中，帧：[2, 0, 1]
  6. 3 → 缺页，帧：[2, 0, 3] — 替换1（1在步14出现，2在步9，0在步11，1最远）
  7. 0 → 命中，帧：[2, 0, 3]
  8. 4 → 缺页，帧：[2, 0, 4] — 替换3（3在步10出现，2在步9，0在步11，但步10较近…等等，需要比较3个页面下一次出现的位置：
    • 2 → 步9
    • 0 → 步11
    • 3 → 步10
    • 4 → 以后不再出现
      所以应替换4的页面不对！4是新页面，帧中的旧页面2、0、3中，以后出现最远的是3（步10）还是0（步11）？最远的是0（步11）？不对，步6到步8的决策：
      帧中：[2, 0, 3]，访问4，缺页。检查帧中三个页面未来出现位置：
    • 2 → 步9
    • 0 → 步11
    • 3 → 步10
      最远的是0（步11），所以应替换0？不对，“最远"是指"最晚被使用”，即出现位置最大的那个。步11 > 步10 > 步9，所以0最远 → 替换0？但0马上在步11就被访问了…

等等，让我重新理解OPT算法。OPT是替换"未来最长时间不会被使用"的页面，即未来第一次出现最晚的那个。

在步8，访问4，帧为[2,0,3]。各页面未来第一次出现位置：

  • 2: 步9
  • 0: 步11
  • 3: 步10

最晚出现的是0（步11），所以应替换0。

继续：

6(重做). 3 → 缺页，帧：[2, 3, 1] — 替换0？不对，步6时的帧为[2,0,1]，访问3。检查：

  • 2 → 步9
  • 0 → 步11（等等，步5已经用了0，后面的0在步7和步11）
  • 1 → 步14
    步14 > 步11 > 步9，所以1最远 → 替换1，帧：[2, 0, 3]

好吧，步6我做的对了。

步8：访问4，帧：[2,0,3]：

  • 2 → 步9
  • 0 → 步11
  • 3 → 步10
    最远是0（步11），替换0，帧：[2, 4, 3]

步9：访问2 → 命中，帧：[2, 4, 3]

步10：访问3 → 命中，帧：[2, 4, 3]

步11：访问0 → 缺页，帧：[2, 0, 3] — 帧中：[2,4,3]。检查：

  • 2 → 步13（步9之后的2在步13和步15）
  • 4 → 此后不再使用
  • 3 → 步12
    4不再使用 → 替换4，帧：[2, 0, 3]

步12：访问3 → 命中，帧：[2, 0, 3]

步13：访问2 → 命中，帧：[2, 0, 3]

步14：访问1 → 缺页，帧：[1, 0, 3] — 帧中：[2,0,3]，检查：

  • 2 → 步15
  • 0 → 步16
  • 3 → 此后不再使用
    3不再使用 → 替换3，帧：[2, 0, 1]

步15：访问2 → 命中，帧：[2, 0, 1]

步16：访问0 → 命中，帧：[2, 0, 1]

步17：访问1 → 命中，帧：[2, 0, 1]

步18：访问7 → 缺页，帧：[7, 0, 1] — 帧中[2,0,1]，检查：

  • 2 → 此后不再使用
  • 0 → 步19
  • 1 → 步20
    2不再使用 → 替换2，帧：[7, 0, 1]

步19：访问0 → 命中，帧：[7, 0, 1]

步20：访问1 → 命中，帧：[7, 0, 1]

汇总OPT：
缺页发生在步：1, 2, 3, 4, 6, 8(替换0), 11(替换4), 14(替换3), 18(替换2)
缺页次数 = 9次

不对，步8替换0，但步11重新访问0又缺页…这是因为步8我把0替换出去了。让我再仔细跟踪一下。

重新做OPT，这次更仔细：

帧: 最多3个页面。初始空。

步1: 访问7 → 缺页。帧: [7, -, -]
步2: 访问0 → 缺页。帧: [7, 0, -]
步3: 访问1 → 缺页。帧: [7, 0, 1]
步4: 访问2 → 缺页。帧中[7,0,1]已满，需替换。

  • 7未来出现: 步18
  • 0未来出现: 步5, 7, 11 → 首次步5
  • 1未来出现: 步14
    最远: 7(步18) → 替换7。帧: [2, 0, 1]
    步5: 访问0 → 命中。帧: [2, 0, 1]
    步6: 访问3 → 缺页。帧[2,0,1]已满。
  • 2未来出现: 步9
  • 0未来出现: 步7
  • 1未来出现: 步14
    最远: 1(步14) → 替换1。帧: [2, 0, 3]
    步7: 访问0 → 命中。帧: [2, 0, 3]
    步8: 访问4 → 缺页。帧[2,0,3]已满。
  • 2未来出现: 步9
  • 0未来出现: 步11
  • 3未来出现: 步10
    最远: 0(步11) → 替换0。帧: [2, 4, 3]
    步9: 访问2 → 命中。帧: [2, 4, 3]
    步10: 访问3 → 命中。帧: [2, 4, 3]
    步11: 访问0 → 缺页。帧[2,4,3]已满。
  • 2未来出现: 步13
  • 4未来出现: 不再出现
  • 3未来出现: 步12
    不再出现优先 → 替换4。帧: [2, 0, 3]
    步12: 访问3 → 命中。帧: [2, 0, 3]
    步13: 访问2 → 命中。帧: [2, 0, 3]
    步14: 访问1 → 缺页。帧[2,0,3]已满。
  • 2未来出现: 步15
  • 0未来出现: 步16
  • 3未来出现: 不再出现
    不再出现优先 → 替换3。帧: [2, 0, 1]
    步15: 访问2 → 命中。帧: [2, 0, 1]
    步16: 访问0 → 命中。帧: [2, 0, 1]
    步17: 访问1 → 命中。帧: [2, 0, 1]
    步18: 访问7 → 缺页。帧[2,0,1]已满。
  • 2未来出现: 不再出现
  • 0未来出现: 步19
  • 1未来出现: 步20
    不再出现优先 → 替换2。帧: [7, 0, 1]
    步19: 访问0 → 命中。帧: [7, 0, 1]
    步20: 访问1 → 命中。帧: [7, 0, 1]

OPT 缺页步: 1, 2, 3, 4, 6, 8, 11, 14, 18 = 9 次
缺页率 = 9/20 = 45%

最终汇总：

算法 缺页次数 缺页率
FIFO 15 75%
LRU 12 60%
OPT 9 45%

结论：OPT 算法性能最佳（理论上），LRU 次之，FIFO 最差。OPT 作为理想算法无法在实际系统中实现，但可作为衡量其他算法性能的上界参考。

8. 磁盘调度算法

题目内容：
某磁盘有 200 个柱面，编号从 0~199。磁盘请求队列中包含以下柱面号（按到达顺序）：

请求队列：98, 183, 37, 122, 14, 124, 65, 67

当前磁头位于 53 号柱面，正在向柱面号增大的方向（即向外）移动。

请分别计算以下磁盘调度算法的磁头移动总距离（总寻道长度，以柱面数为单位），并给出磁头移动的顺序。

  1. FCFS（先来先服务）
  2. SSTF（最短寻道时间优先）
  3. SCAN（电梯算法，向增大方向移动，直到最末端再折返）
  4. C-SCAN（循环扫描，向增大方向移动，到最末端后直接回到最前端）

考点：磁盘调度算法的寻道时间计算

来源章节：第 7 章 — 设备管理之磁盘调度

完整解答过程：

(1) FCFS（先来先服务）

按请求到达顺序依次服务。

移动顺序：53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

寻道距离计算：

段 移动 距离
53→98 增大 45
98→183 增大 85
183→37 减小 146
37→122 增大 85
122→14 减小 108
14→124 增大 110
124→65 减小 59
65→67 增大 2

总寻道长度 = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 个柱面

(2) SSTF（最短寻道时间优先）

每次选择距离当前磁头位置最近的请求。

逐步分析：

初始位置：53

步骤 当前位置 候选请求 最短距离 选中 移动距离
1 53 98(45), 183(130), 37(16), 122(69), 14(39), 124(71), 65(12), 67(14) 12（65） 65 12
2 65 98(33), 183(118), 37(28), 122(57), 14(51), 124(59), 67(2) 2（67） 67 2
3 67 98(31), 183(116), 37(30), 122(55), 14(53), 124(57) 30（37） 37 30
4 37 98(61), 183(146), 14(23), 122(85), 124(87) 23（14） 14 23
5 14 98(84), 183(169), 122(108), 124(110) 84（98） 98 84
6 98 183(85), 122(24), 124(26) 24（122） 122 24
7 122 183(61), 124(2) 2（124） 124 2
8 124 183(59) 59（183） 183 59

移动顺序：53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

总寻道长度 = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 个柱面

(3) SCAN（电梯算法）

磁头当前在 53，向增大方向移动。服务沿途所有请求，到达 199 后折返向减小方向继续服务剩余请求。

排序请求：14, 37, 65, 67, 98, 122, 124, 183

移动路径：53 → 65 → 67 → 98 → 122 → 124 → 183 → 199（末端） → 37 → 14

段 移动 距离
53→65 增大 12
65→67 增大 2
67→98 增大 31
98→122 增大 24
122→124 增大 2
124→183 增大 59
183→199 增大（到末端） 16
199→37 减小 162
37→14 减小 23

总寻道长度 = 12 + 2 + 31 + 24 + 2 + 59 + 16 + 162 + 23 = 331 个柱面

注意：SCAN 可以从当前方向服务完即止（如果题目说不需到末端）。从题意看通常到最末端再折返（“向增大方向移动，直到最末端再折返”）。

(4) C-SCAN（循环扫描）

磁头向增大方向移动，服务沿途所有请求，到达 199 后直接返回 0，再从 0 向增大方向移动。

排序请求：14, 37, 65, 67, 98, 122, 124, 183

移动路径：53 → 65 → 67 → 98 → 122 → 124 → 183 → 199（末端） → 0（回到起点） → 14 → 37

段 移动 距离
53→65 增大 12
65→67 增大 2
67→98 增大 31
98→122 增大 24
122→124 增大 2
124→183 增大 59
183→199 增大（到末端） 16
199→0 直接回起点 199
0→14 增大 14
14→37 增大 23

总寻道长度 = 12 + 2 + 31 + 24 + 2 + 59 + 16 + 199 + 14 + 23 = 382 个柱面

结果汇总：

算法 总寻道长度（柱面数） 移动顺序
FCFS 640 53→98→183→37→122→14→124→65→67
SSTF 236 53→65→67→37→14→98→122→124→183
SCAN 331 53→65→67→98→122→124→183→199→37→14
C-SCAN 382 53→65→67→98→122→124→183→199→0→14→37

结论：SSTF 在本例中总寻道长度最小，但 SSTF 可能导致"饥饿"问题。SCAN 和 C-SCAN 虽然寻道距离稍大，但提供了更公平的服务，C-SCAN 比 SCAN 的等待时间方差更小。

9. 死锁检测

题目内容：
某系统有 4 个进程 P1~P4 和 4 种资源 R1~R4。当前资源分配情况如下：

已分配矩阵 Allocation：

进程 R1 R2 R3 R4
P1 0 1 1 0
P2 1 0 0 1
P3 0 1 0 0
P4 1 0 1 0

请求矩阵 Request（表示每个进程当前还需要的资源数）：

进程 R1 R2 R3 R4
P1 0 0 0 1
P2 1 1 0 0
P3 1 0 0 1
P4 1 0 0 0

可用资源 Available = (0, 0, 1, 0)

请分析：

  1. 当前系统是否存在死锁？使用死锁检测算法逐步分析。
  2. 如果存在死锁，哪些进程处于死锁状态？

考点：死锁检测算法（资源分配图化简法 / 矩阵分析法）

来源章节：第 8 章 — 死锁检测

完整解答过程：

方法：使用死锁检测算法（类似于银行家算法但不要求 Max）：

步骤1：初始化

  • Work = Available = (0, 0, 1, 0)
  • Finish[i] = False（对所有 i，表示进程未完成）

步骤2：标记 Allocation 全为 0 的进程为 Finish=True
P1: Allocation = (0,1,1,0) ≠ 0 → Finish[1]=False
P2: Allocation = (1,0,0,1) ≠ 0 → Finish[2]=False
P3: Allocation = (0,1,0,0) ≠ 0 → Finish[3]=False
P4: Allocation = (1,0,1,0) ≠ 0 → Finish[4]=False
所有进程均已获得资源。

步骤3：查找满足条件的进程（Request[i] ≤ Work 且 Finish[i]=False）

轮次 Work 可满足的进程 说明
第1轮 (0,0,1,0) P4: Request=(1,0,0,0) → 1 > 0，不满足
P1: Request=(0,0,0,1) → 1 > 0，不满足
P2: Request=(1,1,0,0) → 均不满足
P3: Request=(1,0,0,1) → 均不满足
无进程可满足

步骤4：结果分析

无进程可以被满足，因此所有进程的 Finish 均为 False，系统处于死锁状态。

答（第1问）：当前系统存在死锁。

答（第2问）：所有 4 个进程 P1、P2、P3、P4 均处于死锁状态。

验证：让我们用资源分配图来验证。

每个进程已分配资源和请求资源：

  • P1: 已分配 R2×1, R3×1；请求 R4×1
  • P2: 已分配 R1×1, R4×1；请求 R1×1, R2×1
  • P3: 已分配 R2×1；请求 R1×1, R4×1
  • P4: 已分配 R1×1, R3×1；请求 R1×1

可用资源：R3×1

分析资源分配图环路：

  • Available 有 R3×1，但 R3 分配给 P1×1、P4×1，可使用 R3 的进程…
  • P1 需要 R4，R4 分配给 P2，P2 需要 R1 和 R2…
  • 存在环路：P1 → R4 → P2 → R1 → P4 → R3 → P1（或类似的环路）
  • 或者：P1 → R4 → P2 → R2 → P3 → R1 → P4 → R3 → P1

确认死锁：存在环路且每个资源在环路中只有单个实例。

所以结论正确：所有 4 个进程均处于死锁状态。

10. CHS / LBA 地址转换

题目内容：
某硬盘的参数如下：

  • 磁头数（Heads）：8
  • 每磁道扇区数（Sectors per track）：63
  • 柱面数（Cylinders）：2048

请回答以下问题：

  1. 该硬盘的总容量是多少扇区？如果每扇区 512 字节，总容量为多少？
  2. 将 CHS 地址 (C=100, H=3, S=20) 转换为 LBA（逻辑块地址）。
  3. 将 LBA 地址 500000 转换为 CHS 地址。
  4. 如果将 LBA 视为一维连续编址，从 LBA=0 开始，请问 LBA=0 对应的 CHS 地址是什么？

考点：CHS 与 LBA 地址转换原理

来源章节：第 6 章 — 文件管理与磁盘结构

完整解答过程：

基本公式：

CHS → LBA：

LBA = (C × Heads + H) × SectorsPerTrack + (S - 1)

LBA → CHS：

C = LBA / (Heads × SectorsPerTrack)
H = (LBA / SectorsPerTrack) % Heads
S = (LBA % SectorsPerTrack) + 1

其中 C（柱面号），H（磁头号），S（扇区号，从 1 开始）。
LBA 从 0 开始编号。

第1问：总容量

总扇区数 = 柱面数 × 磁头数 × 每磁道扇区数
= 2048 × 8 × 63 = 2048 × 504 = 1,032,192 扇区

总字节数 = 1,032,192 × 512 = 528,482,304 字节 ≈ 504 MB

第2问：CHS → LBA

已知 C=100, H=3, S=20

LBA = (C × Heads + H) × SectorsPerTrack + (S - 1)
= (100 × 8 + 3) × 63 + (20 - 1)
= (800 + 3) × 63 + 19
= 803 × 63 + 19
= 50,589 + 19
= 50,608

答：CHS(100, 3, 20) → LBA = 50,608

第3问：LBA → CHS

已知 LBA = 500,000

计算柱面号 C：
C = LBA / (Heads × SectorsPerTrack)
= 500,000 / (8 × 63)
= 500,000 / 504
= 992（取整）… 让我们详细算：
504 × 992 = 504 × 1000 - 504 × 8 = 504,000 - 4,032 = 499,968
余数 = 500,000 - 499,968 = 32

所以 C = 992

计算磁头号 H：
H = (LBA / SectorsPerTrack) % Heads
先算 temp = LBA / SectorsPerTrack = 500,000 / 63
63 × 7936 = 63 × 8000 - 63 × 64 = 504,000 - 4,032 = 499,968
余数 = 500,000 - 499,968 = 32
所以 temp = 7,936 余 32

H = 7,936 % 8
7,936 ÷ 8 = 992 余 0
所以 H = 0

计算扇区号 S：
S = (LBA % SectorsPerTrack) + 1
LBA % 63 = 500,000 % 63
63 × 7,936 = 499,968
500,000 - 499,968 = 32
所以 S = 32 + 1 = 33

或用余数验证：余数 = 500,000 - 504 × 992 = 500,000 - 499,968 = 32
S = 32 + 1 = 33

验证：S = (32) + 1 = 33？

等等，让我重新检查。从 C=992 的余数 32 应该就是 S-1…不对。

让我一步步重新算：
LBA = 500,000

先用总公式检查：
C = LBA / (H × SPT) = 500,000 / (8 × 63) = 500,000 / 504

504 × 992 = 499,968，余 32

所以 LBA 位于柱面 992。

然后在这个柱面内：
柱面内的偏移 = LBA - C × (H × SPT) = 500,000 - 992 × 504 = 500,000 - 499,968 = 32

H = 柱面内偏移 / SPT = 32 / 63 = 0（取整）
S = (柱面内偏移 % SPT) + 1 = (32 % 63) + 1 = 32 + 1 = 33

所以 C = 992, H = 0, S = 33

验证：LBA = (992 × 8 + 0) × 63 + (33 - 1) = 7,936 × 63 + 32 = 499,968 + 32 = 500,000 ✓

答：LBA 500,000 → CHS(992, 0, 33)

第4问：LBA=0 对应的 CHS

LBA = 0
C = 0 / (8 × 63) = 0
H = (0 / 63) % 8 = 0 % 8 = 0
S = (0 % 63) + 1 = 0 + 1 = 1

答：LBA=0 → CHS(0, 0, 1)

最终答案汇总：

问题 结果
1. 总容量 1,032,192 扇区 ≈ 504 MB
2. CHS(100,3,20) → LBA LBA = 50,608
3. LBA 500,000 → CHS CHS(992, 0, 33)
4. LBA=0 → CHS CHS(0, 0, 1)

答案速查表

题号 考点 答案
1 银行家算法 安全状态：<P1,P3,P0,P2,P4>；Request₁(1,0,2) 可分配
2 分段地址转换 (0,250)→2350；(1,150)→3650；(2,600)→越界；(3,400)→7200
3 分页地址转换 0x2A3C→0x1A3C；0x1120→0x7120；0x54A8→0x24A8
4 FCFS/SJF/HRRN FCFS平均周转15.25；SJF平均14.25；HRRN平均14.25
5 RR时间片轮转 平均周转10.25ms，平均等待5.75ms
6 动态分区分配 三种算法均成功分配，分配路径不同
7 页面置换 FIFO缺页15次(75%)；LRU缺页12次(60%)；OPT缺页9次(45%)
8 磁盘调度 FCFS=640；SSTF=236；SCAN=331；C-SCAN=382
9 死锁检测 存在死锁，P1~P4全部死锁
10 CHS/LBA转换 总容量1,032,192扇区；CHS(100,3,20)→LBA=50608；LBA500000→CHS(992,0,33)
# 操作系统
Logo
openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

操作系统四种核心的页面置换算法

操作系统四种核心的页面置换算法

avatar openEuler 社区
cover

Socket：应用程序看世界的那扇窗

avatar openEuler 社区
cover

Java虚拟机面试题：JVM调优

avatar openEuler 社区