review202505 答案讲解 03：计算题 1-10

1. 两级生产者消费者同步

题意：

1、设有三个进程A、B、C，其中A与B构成一对生产者与消费者（A为生产者，B为消费者），共享一个由n个缓冲块组成的缓冲池；B与C也构成一对生产者与消费者（此时B为生产者，C为消费者），共享另一个由m个缓冲块组成的缓冲池。用P、V操作描述它们之间的同步关系。

答案讲解：

设置 6 个信号量：

A 进程：

while true:
    生产一个产品 x
    P(empty1)
    P(mutex1)
    将 x 放入缓冲池 1
    V(mutex1)
    V(full1)

B 进程：

while true:
    P(full1)
    P(mutex1)
    从缓冲池 1 取出产品 x
    V(mutex1)
    V(empty1)

    对 x 进行处理，得到 y

    P(empty2)
    P(mutex2)
    将 y 放入缓冲池 2
    V(mutex2)
    V(full2)

C 进程：

while true:
    P(full2)
    P(mutex2)
    从缓冲池 2 取出产品 y
    V(mutex2)
    V(empty2)
    消费 y

解释：

1. empty 用于防止生产者向满缓冲池继续放入数据。
2. full 用于防止消费者从空缓冲池取数据。
3. mutex 用于保证同一个缓冲池一次只被一个进程访问。

2. 证明 SJF 平均周转时间最小

题意：

2、若后备作业队列中等待运行的同时有4个作业J1、J2, …, J4，已知它们各自的运行为t1,t2,…, t4，且满足t1<t2<…<t4。试证明采用短作业优先算法调度能获得最小平均周转时间

答案讲解：

由于 4 个作业同时等待运行，所以周转时间等于完成时间。平均周转时间最小等价于总周转时间最小。

用相邻交换法证明：

假设某个调度序列中有两个相邻作业 i、j，并且：

ti > tj

但调度顺序是先 i 后 j。设这两个作业开始前已经运行了 T 时间。

先 i 后 j 时，两者完成时间之和为：

(T + ti) + (T + ti + tj)
= 2T + 2ti + tj

先 j 后 i 时，两者完成时间之和为：

(T + tj) + (T + tj + ti)
= 2T + 2tj + ti

两种顺序相减：

(2T + 2ti + tj) - (2T + 2tj + ti)
= ti - tj

因为 ti > tj，所以：

ti - tj > 0

说明把短作业 j 放到长作业 i 前面，会使总完成时间减小。不断交换所有“长作业在短作业前面”的逆序对，最后得到按运行时间从短到长排列的顺序，也就是短作业优先 SJF。

因此 SJF 能获得最小平均周转时间。

3. inode 地址项计算最大文件长度

题意：

3、设文件索引节点中有7个地址项，其中4个为直接地址索引，2个是一级间接地址索引，1个是二级间接地址索引，地址项大小为4B，若磁盘索引块和磁盘数据块大小均为1KB，求可表示的单个文件的最大长度。

答案讲解：

已知：

索引块大小 = 1KB = 1024B
地址项大小 = 4B

每个索引块可存放地址项数：

1024 / 4 = 256

可寻址的数据块数：

直接地址：4 块
一级间接：2 × 256 = 512 块
二级间接：1 × 256 × 256 = 65536 块
总块数：4 + 512 + 65536 = 66052 块

每个数据块大小为 1KB，所以最大文件长度为：

66052 × 1KB = 66052KB

换算为字节：

66052 × 1024 = 67,637,248B

答案： 单个文件最大长度为 66052KB，即 67,637,248B。

4. UNIX inode 最大文件、最大分区和磁盘访问次数

题意：

4、考虑由索引节点表示的UNIX文件的组织。在每个节点中，假定有12个直接块指针，以及一个一级、二级和三级间接指针。此外，假定系统磁盘块的大小为8KB。如果盘块指针用32位表示，其中8位用于标识物理磁盘号，24位用于标识磁盘块号，那么：

(1)该系统支持的最大文件大小是多少

(2)该系统支持的最大文件系统分区是多少

(3)假定主存中除了文件索引节点外没有别的信息，访问在位置12423956的字节时，需要访问磁盘多少次

答案讲解：

每个块指针大小：

32 位 = 4B

每个索引块可容纳指针数：

8KB / 4B = 8192 / 4 = 2048

(1) 最大文件大小

可寻址数据块数：

直接块：12
一级间接：2048
二级间接：2048^2
三级间接：2048^3

总数据块数：

12 + 2048 + 2048^2 + 2048^3
= 8,594,130,956 块

按 Solutions-OS8e 12.13 的表达，可以把最大文件大小分项写为：

直接块：12 × 8KB = 96KB
一级间接：2048 × 8KB = 16MB
二级间接：2048^2 × 8KB = 32GB
三级间接：2048^3 × 8KB = 64TB

精确总量为：

8,594,130,956 × 8KB = 70,403,120,791,552B ≈ 64.031TiB

答案： 最大文件大小约为 64TB + 32GB + 16MB + 96KB，精确为 70,403,120,791,552B。

(2) 最大文件系统分区

块号字段为 24 位，所以一个分区内最多可编号：

2^24 个磁盘块

每块 8KB：

2^24 × 8KB = 2^24 × 2^13B = 2^37B = 128GiB

答案： 最大文件系统分区为 128GiB。

补充：若把 8 位物理磁盘号也计入整个系统寻址能力，则总磁盘寻址空间可达 2^8 × 128GiB = 32TiB。但 Solutions-OS8e 12.13 对“partition”的答案为 128GB 量级，因此本题按分区答 128GiB。

(3) 访问位置 12423956 的字节需要访问磁盘多少次

逻辑块号：

12423956 / 8192 = 1516 余 4884

所以该字节在逻辑块 1516 内。

直接块范围：

0 - 11

一级间接范围：

12 - 2059

逻辑块 1516 属于一级间接范围。

题目说主存中除了 inode 外没有别的信息，因此 inode 已在内存中，但一级间接索引块和目标数据块都不在内存中。

需要访问磁盘：

1. 读一级间接索引块。
2. 读目标数据块。

答案： 需要访问磁盘 2 次。

5. 磁盘记录顺序处理与优化排列

题意：

5、假设有8个记录A、B，C、D、E、F、G、H存放在磁盘里，每个磁道有8个扇区，正好可以存放8个记录。假设磁盘旋转速度为20ms/转，处理程序每读出一个记录后，用2ms的时间进行处理，请问：

a．当记录A、B、C、D、E、F、G、H按顺序放在磁道上时，顺序处理这8个记录花费的总时间是多少？假设启动时的位置正好在A扇区的起点。

b．如何采取优化方法，使处理这些记录所花费的总时间最短？求出该最短时间。

答案讲解：

每磁道 8 个扇区，旋转一周 20ms，所以每个扇区经过磁头的时间：

20ms / 8 = 2.5ms

每读出一个记录后处理 2ms，因此读完一个记录再处理完成所需时间：

2.5ms + 2ms = 4.5ms

(a) 顺序存放

记录按 A B C D E F G H 顺序存放。启动时正好在 A 扇区起点。

读 A：

读 A：0 - 2.5ms
处理 A：2.5 - 4.5ms

处理完 A 时，B 扇区已经转过磁头，只能等下一圈 B 再来。之后每读一个记录都会发生类似情况。

相邻两个逻辑记录开始读取的间隔为：

2.5ms 读当前记录 + 2ms 处理 + 等待下一圈对应扇区
= 22.5ms

总时间：

A 的读和处理：4.5ms
后续 7 个记录：7 × 22.5ms = 157.5ms
总时间：4.5 + 157.5 = 162ms

答案： 顺序存放时处理 8 个记录共需 162ms。

(b) 优化方法

这类题对应教材解答中“记录交错存放”的思想：让相邻逻辑记录在磁道上的间隔匹配处理时间，避免每次处理完都错过下一个扇区。

因为读一个记录并处理完成需要 4.5ms，约等于 2 个扇区时间：

2 × 2.5ms = 5ms

所以逻辑上的下一个记录应放在物理位置约 2 个扇区之后，使处理完成后尽快遇到下一个要读的记录。

一种最优排列：

扇区位置：1  2  3  4  5  6  7  8
存放记录：A  E  B  F  C  G  D  H

读取开始时间：

H 读取结束为 40ms，处理 H 再用 2ms。

答案： 最短总时间为 42ms，一种优化排列为 A E B F C G D H。

6. 四道作业系统：STR 与 SJF

题意：

6、四道作业系统，如果在一段时间内先后有6个作业，它们提交和运行时间由下表给出(时间单位为分钟)。系统采用进程剩余时间优先(STR)调度算法，作业采用最短作业优先算法。问题：

(1) 完成各个作业的开始时间、完成时间、周转时间和带权周转时间。

(2) 计算平均作业周转时间和平均作业带权周转时间。

答案讲解：

四道作业系统表示内存中最多同时容纳 4 个作业。进程调度采用剩余时间优先 STR，会发生抢占；作业调度采用短作业优先，选择后备队列中运行时间最短的作业进入内存。

执行过程：

结果表：

平均周转时间：

(160 + 110 + 25 + 70 + 30 + 10) / 6 = 67.5 分钟

平均带权周转时间：

(3.20 + 3.14 + 1.00 + 2.80 + 2.00 + 1.00) / 6 ≈ 2.19

答案： 平均周转时间为 67.5 分钟，平均带权周转时间约为 2.19。

7. 银行家算法

题意：

7、假设系统有A、B、C、D四类资源可供五个进程P1、P2、P3、P4、P5共享。系统对这四类资源的拥有量为:(3,14,12,12)。进程对资源的需求和分配情况如下：

按银行家算法回答下列问题：

(1)系统是否处于安全状态？为什么？

(2)如果P2提出请求(0,4,2,0)，系统能否满足请求？请说明原因。

(3)如果在P2提出资源需求(0,4,2,0)后，P3提出资源需求(0,0,0,1)，系统能否满足其请求？请说明原因。

答案讲解：

总资源：

Total = (3,14,12,12)

已分配资源总和：

Allocation 总和 = (2,9,10,12)

可用资源：

Available = (3,14,12,12) - (2,9,10,12)
          = (1,5,2,0)

需求矩阵 Need = Max - Allocation：

(1) 是否安全

初始：

Work = Available = (1,5,2,0)

可取安全序列：

答案： 系统处于安全状态，安全序列可为 P1 -> P3 -> P2 -> P4 -> P5。

(2) P2 请求 (0,4,2,0) 是否可满足

检查：

Request2 = (0,4,2,0)
Need2 = (0,7,5,0)
Available = (1,5,2,0)

满足：

Request2 <= Need2
Request2 <= Available

试分配后：

Available = (1,5,2,0) - (0,4,2,0) = (1,1,0,0)
P2 Allocation = (1,4,2,0)
P2 Need = (0,3,3,0)

安全性检查：

答案： 可以满足。试分配后仍安全，安全序列可为 P1 -> P3 -> P2 -> P4 -> P5。

(3) P2 请求后，P3 请求 (0,0,0,1) 是否可满足

在 P2 请求被满足后：

Available = (1,1,0,0)

P3 请求：

Request3 = (0,0,0,1)

虽然该请求不超过 P3 的剩余需求，但：

Request3 的 D = 1 > Available 的 D = 0

答案： 不能立即满足，因为 D 类资源当前可用数为 0。

8. 增加内存后的 CPU 利用率

题意：

8、有一台计算机，具有1MB内存，操作系统占用200KB，每个用户占用200KB。如果用户进程等待I/O的时间为80%，若增加1MB内存，则CPU的利用率提高多少？

答案讲解：

多道程序环境下，若每个进程等待 I/O 的概率为 p，内存中有 n 个用户进程，则 CPU 利用率近似为：

U = 1 - p^n

这里：

p = 0.8

初始内存 1MB，即 1024KB。操作系统占用 200KB，每个用户进程占 200KB。

初始可容纳用户进程数：

floor((1024 - 200) / 200) = 4

初始 CPU 利用率：

U1 = 1 - 0.8^4
   = 1 - 0.4096
   = 0.5904
   = 59.04%

增加 1MB 后，总内存为 2MB，即 2048KB。

新可容纳用户进程数：

floor((2048 - 200) / 200) = 9

新的 CPU 利用率：

U2 = 1 - 0.8^9
   = 1 - 0.134217728
   = 0.865782272
   ≈ 86.58%

提高：

U2 - U1 = 0.865782272 - 0.5904
        = 0.275382272
        ≈ 27.54 个百分点

答案： CPU 利用率从 59.04% 提高到约 86.58%，提高约 27.54 个百分点。若按相对提高比例，则约为 46.65%。

9. cache、主存、辅存平均访问时间

题意：

9、某计算机有cache、主存、辅存来实现虚拟存储器。如果数据在cache中，访问它需要20ns;如果在主存但不在cache，需要60ns将其装入缓存，然后才能访问;如果不在主存而在辅存，需要12s将其读入主存，然后，用60ns再读入cache，然后才能访问。假设cache合中率为0.9，主存命中率为0.6，则数据平均访问时间是多少(ns)?

答案讲解：

单位换算：

12s = 12,000,000,000ns

按题意理解：

1. cache 命中概率为 0.9，访问时间 20ns。
2. cache 未命中概率为 0.1。
3. 在 cache 未命中情况下，主存命中概率为 0.6。
4. 在主存未命中情况下，需要从辅存读入主存，再读入 cache，再访问。

平均访问时间：

E = 0.9 × 20
  + 0.1 × 0.6 × (60 + 20)
  + 0.1 × 0.4 × (12,000,000,000 + 60 + 20)

计算：

E = 18 + 4.8 + 480,000,003.2
  = 480,000,026ns

答案： 数据平均访问时间约为 480,000,026ns，即约 0.480000026s。

说明：若教材把“装入 cache 后才能访问”的最后一次 20ns 省略，则结果为 480,000,024ns，只差 2ns，不影响结论。

10. 页面置换：OPT 和 LRU

题意：

10、在一个请求分页虚拟存储管理系统中，一个作业共有5页，执行时其访问页面次序为: 1、4、3、1、2、5、1、4、2、1、4、5。

若分配给该作业三个页框，分别采用OPT和 LRU页面替换算法，求出各自的缺页中断次数、淘汰的页面、和缺页中断率。

答案讲解：

访问序列：

1, 4, 3, 1, 2, 5, 1, 4, 2, 1, 4, 5

页框数为 3，访问总次数为 12。

OPT 算法

OPT 淘汰未来最长时间不再访问的页面。

最后一步中，1、4、2 后面都不再访问，淘汰任意一个都不影响缺页次数。

OPT 缺页次数：

7 次

OPT 缺页率：

7 / 12 ≈ 58.33%

LRU 算法

LRU 淘汰最长时间未被访问的页面。

LRU 缺页次数：

8 次

LRU 缺页率：

8 / 12 ≈ 66.67%

答案汇总：