20. 请求页式存储管理系统缺页率计算

题目：

假设一个作业的页面走向为 1、2、3、4、1、2、5、1、2、3、4、5，当分配给该作业的物理块数分别为 3 和 4 时，计算采用下述页面置换算法的缺页率：

(1) 先进先出（FIFO）置换算法
(2) 最近最久未使用（LRU）置换算法

参考答案：

(1) FIFO 算法：

• 块数为 3，缺页次数 = 9，缺页率 = 9/12 = 75%

• 块数为 4，缺页次数 = 10，缺页率 = 10/12 = 83.3%

(2) LRU 算法：

• 块数为 3，缺页次数 = 10，缺页率 = 10/12 = 83.3%

• 块数为 4，缺页次数 = 8，缺页率 = 8/12 = 66.7%

现象： FIFO 算法可能出现 Belady 异常，即增加内存块数后，缺页次数反而增加。

---

21. 作业调度算法：短作业优先（SJF）和先来先服务（FCFS）

题目：

下表给出作业 1、2、3、4 的到达时间和运行时间，分别采用短作业优先调度算法（SJF）和先来先服务算法（FCFS），求各自的平均周转时间。

作业	到达时间	运行时间
J1	0	3
J2	1	5
J3	3	2
J4	5	5

参考答案：

(1) SJF 调度算法：

• 调度顺序：J1 → J3 → J2 → J4

• 平均周转时间 = (3 + 2 + 9 + 10) / 4 = 6

(2) FCFS 调度算法：

• 调度顺序：J1 → J2 → J3 → J4

• 平均周转时间 = (3 + 7 + 7 + 10) / 4 = 6.75

---

22. 混合索引分配文件系统的计算

题目：

存放在某个磁盘上的文件系统采用混合索引分配方式，其 FCB 中共有 13 个地址项：

• 第 0-9 项为直接地址

• 第 10 项为一次间接地址

• 第 11 项为二次间接地址

• 第 12 项为三次间接地址

如果每个盘块为 512 字节，盘块号需要用 3 个字节来描述，试问：

1. 该文件系统允许文件的最大长度是多少？

2. 将文件的字节偏移量 5000、15000 转换为物理块号和块内偏移量。

参考答案：

(1) 最大文件长度： 每个盘块存储 512 字节，盘块号需要 3 字节描述，因此：

• 一次间接地址最多指向 170 个盘块。

• 二次间接地址最多指向 170 × 170 个盘块。

• 三次间接地址最多指向 170 × 170 × 170 个盘块。 最大文件长度 = (10 + 170 + 170² + 170³) × 512 字节
  = 4942080 × 512 字节 = 2,531,246,080 字节 ≈ 2.53 GB

(2) 字节偏移量转换：

• 偏移量 5000：逻辑块号 = ⌊5000 / 512⌋ = 9，块内偏移量 = 5000 % 512 = 392

• 偏移量 15000：逻辑块号 = ⌊15000 / 512⌋ = 29，块内偏移量 = 15000 % 512 = 152

---

23. 磁盘调度算法及平均寻道长度计算

题目：

假设磁盘有 200 个磁道，磁盘请求队列为：180、20、160、60、70、135、40 号磁道。当前磁头在 100 号磁道上，并正由外向里移动。

试用以下算法调度，并计算平均寻道长度：

• 先来先服务（FCFS）

• 最短寻道时间优先（SSTF）

• 扫描算法（SCAN）

• 循环扫描算法（C-SCAN）

参考答案：

(1) FCFS 调度：

• 总寻道长度 = 640

• 平均寻道长度 = 640 / 7 = 91.43

(2) SSTF 调度：

• 总寻道长度 = 310

• 平均寻道长度 = 310 / 7 = 44.29

(3) SCAN 调度：

• 总寻道长度 = 260

• 平均寻道长度 = 260 / 7 = 37.14

(4) C-SCAN 调度：

• 总寻道长度 = 320

• 平均寻道长度 = 320 / 7 = 45.71

24. 银行家算法资源分配和安全性分析

题目：

假定系统中有四种资源（A、B、C、D）和五个进程 P1、P2、P3、P4、P5，在时刻 T0 时系统资源分配情况如下：

进程	Allocation	Max	Available
P1	0 1 0 1	1 3 2 2	1 7 3 3
P2	2 0 0 0	3 2 2 2
P3	3 0 2 1	5 3 7 7
P4	1 2 2 1	1 8 7 3
P5	0 0 2 2	4 4 4 4

参考答案：

(1) 计算分配矩阵 Allocation：

进程  Allocation  
P1    0 1 0 1  
P2    2 0 0 0  
P3    3 0 2 1  
P4    1 2 2 1  
P5    0 0 2 2

(2) 判断 T0 时刻是否为安全状态：

系统处于安全状态，安全序列为：P1 → P4 → P5 → P2 → P3。

(3) 若 P3 请求资源 Request3 = (1, 2, 2, 1)，是否能实施分配，为什么？

Request3 ≤ Available (1, 7, 3, 3)，满足条件。请求可以满足。
分配后系统状态：Available = (0, 5, 1, 2)
分配后安全序列为：P1 → P4 → P5 → P2 → P3。

(4) 若 P4 请求资源 Request4 = (1, 2, 1, 2)，是否能实施分配，为什么？

Request4 > Need4，不能满足请求。请求无法分配。

---

25. 作业调度算法：SJF 和 FCFS 的平均周转时间计算

题目：

下表给出作业 1、2、3、4 的到达时间和运行时间，分别采用短作业优先调度算法（SJF）和先来先服务算法（FCFS），试问平均周转时间各为多少？（时间单位：小时，以十进制计算）

作业	到达时间	运行时间
J1	0	3
J2	1	5
J3	3	2
J4	5	5

参考答案：

(1) SJF 调度算法：

• 调度顺序：J1 → J3 → J2 → J4

• 平均周转时间 = (3 + 2 + 9 + 10) / 4 = 6

(2) FCFS 调度算法：

• 调度顺序：J1 → J2 → J3 → J4

• 平均周转时间 = (3 + 7 + 7 + 10) / 4 = 6.75

---

26. 混合索引分配文件系统的计算

题目：

存放在某个磁盘上的文件系统采用混合索引分配方式，其 FCB 中共有 13 个地址项：

• 第 0-9 项为直接地址，

• 第 10 项为一次间接地址，

• 第 11 项为二次间接地址，

• 第 12 项为三次间接地址。

如果每个盘块为 512 字节，盘块号需要用 3 个字节来描述，试问：

1. 该文件系统允许文件的最大长度是多少？

2. 将文件的字节偏移量 5000、15000 转换为物理块号和块内偏移量。

参考答案：

(1) 最大文件长度：

• 每个盘块存储数据大小为 512 字节，盘块号需要 3 字节描述，因此：

  • 一次间接地址最多指向 170 个盘块。

  • 二次间接地址最多指向 170 × 170 个盘块。

  • 三次间接地址最多指向 170 × 170 × 170 个盘块。

最大文件长度 = (10 + 170 + 170² + 170³) × 512 字节
= 4942080 × 512 字节 = 2,531,246,080 字节 ≈ 2.53 GB

(2) 字节偏移量转换：

• 偏移量 5000：逻辑块号 = ⌊5000 / 512⌋ = 9，块内偏移量 = 5000 % 512 = 392

• 偏移量 15000：逻辑块号 = ⌊15000 / 512⌋ = 29，块内偏移量 = 15000 % 512 = 152

---

27. 磁盘调度算法及平均寻道长度计算

题目：

假设磁盘有 200 个磁道，磁盘请求队列为：180、20、160、60、70、135、40 号磁道。当前磁头在 100 号磁道上，并正由外向里移动。

试用以下算法调度，并计算平均寻道长度：

• 先来先服务（FCFS）

• 最短寻道时间优先（SSTF）

• 扫描算法（SCAN）

• 循环扫描算法（C-SCAN）

参考答案：

(1) FCFS 调度：

• 总寻道长度 = 640

• 平均寻道长度 = 640 / 7 = 91.43

(2) SSTF 调度：

• 总寻道长度 = 310

• 平均寻道长度 = 310 / 7 = 44.29

(3) SCAN 调度：

• 总寻道长度 = 260

• 平均寻道长度 = 260 / 7 = 37.14

(4) C-SCAN 调度：

• 总寻道长度 = 320

• 平均寻道长度 = 320 / 7 = 45.71

---

28. 可变分区分配的最先适应和最佳适应算法

题目：

某操作系统采用可变分区分配管理方法，用户区地址为 0--512K-1。假设采用以下分区管理：

• 申请 300K → 申请 100K → 释放 300K → 申请 150K → 申请 30K → 申请 40K → 申请 60K → 释放 30K

问题：

1. 用最先适应算法画出分配情况及空闲分区表；

2. 用最佳适应算法画出分配情况及空闲分区表；

3. 如果再申请 100K 空间，则两种算法的结果如何？

参考答案：

(1) 最先适应算法：

• 分区表按照地址从低到高依次分配。

• 空闲分区分裂时，优先分配低地址空闲区。

• 再申请 100K 空间时，可以成功分配。

(2) 最佳适应算法：

• 分区表按照大小从小到大分配，优先选最小空闲区。

• 再申请 100K 空间时，若无合适空闲分区，则无法分配。