应用题

1. 磁道调度：SCAN 与 SSTF 算法

假定当前磁头位于 100 号磁道，刚服务过 80 号磁道。进程对磁道的请求序列依次为 55，65，39，28，90，155，145，38，170。当采用扫描算法和最短寻道时间优先算法时，总的移动的磁道数分别是多少？（请给出寻道次序和每步移动磁道数）

• (1) 采用扫描算法（寻道次序、每步移动磁道数和总的移动磁道数）。
• (2) 最短寻道时间优先算法（寻道次序、每步移动磁道数和总的移动磁道数）。

解析

2. 银行家算法：四类资源、五进程

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

进程	已占有资源 (A, B, C, D)	最大需求数 (A, B, C, D)
P1	(0, 0, 1, 2)	(0, 0, 1, 2)
P2	(1, 0, 0, 0)	(1, 7, 5, 0)
P3	(1, 3, 5, 4)	(2, 3, 5, 6)
P4	(0, 6, 3, 2)	(0, 6, 5, 2)
P5	(0, 0, 1, 4)	(0, 6, 5, 6)

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

• (1) 系统是否处于安全状态？为什么？
• (2) 如果 P2 提出请求 (0,4,2,0)，系统能否满足请求？请说明原因。
• (3) 如果在 P2 提出资源需求 (0,4,2,0) 后，P3 提出资源需求 (0,0,0,1)，系统能否满足其请求？请说明原因。

解析

3. 打印机：共享设备的判断

办公室只有一台打印机通过局域网为办公室人员提供打印服务。该打印机是共享设备的观点是否正确？为什么？

解析

4. 请求分页：逻辑地址转换与 LRU

在请求分页系统中，有一个长度为 6 页的进程，页大小为 1KB。假如为它分配 3 个物理块，逻辑地址为：2049, 3098, 2078, 1066, 5018, 5163, 2088, 6010, 5069, 5287, 4000, 3068。试求出进程访问的页面次序，并用 LRU 页面置换算法计算出程序访问过程中所发生的缺页次数和缺页中断率。（说明：初始页面为空，计算为缺页。）

• (1) 进程访问的页面次序。
• (2) LRU 页面置换算法计算出程序访问过程。
• (3) 访问过程中所发生的缺页次数。
• (4) 缺页中断率。

解析

5. 页表项数：正置页表与反置页表

一台机器有 48 位虚地址和 32 位物理地址，若页长为 8KB，问页表共有多少个页表项? 如果设计一个反置页表，则有多少个页表项?

解析

6. 页面置换（FIFO、OPT、LRU）缺页次数

在一个请求分页虚拟存储管理系统中，一个程序运行的页面走向是： 1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6。

分别用 FIFO、OPT 和 LRU 算法，对分配给程序 3 个页框，求出缺页中断次数和缺页中断率。

解析

7. 短作业优先（抢占式）调度时间表

若有一个四道作业系统，如果在一段时间内先后有 6 个作业，它们提交和运行时间由下表给出。作业采用短作业优先的调度算法，进程采用以剩余时间最短优先的抢占式调度算法。（说明：计算结果保留一位小数。）

作业序号	提交时间	运行时间（分钟）	开始时间	结束时间	周转时间	带权周转时间
1	8:00	50
2	8:15	30
3	8:20	20
4	8:25	20
5	8:30	10
6	8:35	5

问题：

• (1) 完成上表，给出各个作业的开始时间、完成时间、周转时间和带权周转时间；
• (2) 计算平均作业周转时间和平均作业带权周转时间。

解析

8. 银行家算法：三类资源（R1/R2/R3）

设当前的系统状态如下表所示，系统此时 Available == (1,1,2)。

进程	Claim (R1, R2, R3)	Allocation (R1, R2, R3)
P1	(3, 2, 2)	(1, 0, 0)
P2	(6, 1, 3)	(5, 1, 1)
P3	(3, 1, 4)	(2, 1, 1)
P4	(4, 2, 2)	(0, 0, 2)

问题：

• (1) 当 P2 发出资源请求向量 request2(1,0,1)，此时系统能否把资源分配给它？为什么？如果能分配给它，则请给出一个安全序列；
• (2) 若在 P2 发出资源请求向量 request2(1,0,1) 后，若 P1 发出资源请求向量 request1(1,0,1)，此时系统能否把资源分配给它？为什么？
• (3) 若在 P2 发出资源请求向量 request2(1,0,1) 后，若 P3 发出资源请求向量 request3(0,0,1)，此时系统能否把资源分配给它？为什么？

解析

9. 磁道调度（FCFS、SCAN、SSTF）

假定当前磁头位于 100 号磁道，刚服务过 105 号磁道。进程对磁道的请求序列依次为 55，34，58，39，18，90，160，45，145，38，170，180。当采用先来先服务算法、扫描算法和最短寻道时间优先算法时，总的移动的磁道数分别是多少？（请给出寻道次序、每步移动磁道数和总的移动磁道数）

• (1) 扫描算法
• (2) 最短寻道时间优先算法

解析

10. 二级页表虚地址结构

一个 32 位地址的计算机系统使用二级页表，虚地址被分为 9 位顶级页表，11 位二级页表和偏移。试问：页面长度是多少？虚地址空间共有多少个页面？

解析

11. 虚地址转实地址（十六进制）

假设某虚存的用户空间为 1024KB，页面大小为 4KB，内存空间为 512KB。已知用户的虚页 10、11、12、13 页分得内存页框号为 62、78、25、36，求出虚地址 0BEBC（16 进制）的实地址（16 进制）是多少?

解析

12. 两道程序并发运行时间图

一个计算机系统，有一台输入机和一台打印机，现有两道程序设计投入运行，且程序 A 先开始做，程序 B 后开始运行。

• 程序 A 的运行轨迹为：计算 50ms、打印 40ms、计算 80ms、打印 80ms，结束。
• 程序 B 的运行轨迹为：计算 50ms、输入 100ms、计算 40ms、打印 40ms，结束。

问题：

• (1) 画出相应的运行图；
• (2) 两道程序运行时，CPU 有无空闲等待？若有，在哪段时间等待？为什么？
• (3) 程序 A、B 有无等待的情况？若有，指出发生等待的时刻。

解析

13. 请求分页 LRU（页大小 100）

假设 UNIX 系统采用请求式分页存储，有一个长度为 6 页的进程，页大小为 100。假如为它分配 3 个物理块，逻辑地址为：021, 256, 301, 508, 279, 098, 334, 302, 578, 412。试求出进程访问的页面次序，并用 LRU 页面置换算法计算出程序访问过程，以及访问过程中所发生的缺页次数和缺页中断率。（说明：初始页面为空，计算为缺页。）

解析

14. 磁盘交错存储：6000r/min、9扇区

假定磁盘转速为 6000r/min（转/分），磁盘格式化时每个盘面被分为 9 个扇区，现有一个文件共有 A，B，C，D，E，F，G，H，I 九个逻辑记录要存放在同一磁道上供处理程序使用，假设每个记录的大小与扇区的大小相同，处理程序每次从磁盘读出一个记录后要花 2.5ms 处理时间。若忽略其他辅助时间，请回答下列问题：

• （1）现在假设已经顺序存放好这 9 个记录，记录逆时针排列，磁盘顺时针旋转。那么读出该文件需要多少时间？
• （2）为了使读出文件需要的时间最短，请重新调整各个记录的存放位置，画出各个记录的存放位置，计算该文件的读出时间。

解析

概念检查 (Concept Check)

• 磁盘周期计算： 6000 r/min = 100 转/秒。因此，磁盘旋转一圈（1转）的时间 $T = 1000ms / 100 = 10ms$。
• 扇区读取时间： 1圈有9个扇区，读取1个扇区（记录）的时间 $t = 10ms / 9 \approx 1.11ms$。
• 处理时间： 给定为 2.5ms。

原理解析 (The 'Why')

(1) 顺序存放时的困境： 当读完记录A（耗时 $\frac{10}{9} ms$）后，磁头来到了扇区1的末尾（即扇区2的开头）。此时处理程序开始处理A，耗时 $2.5ms$。 在这 $2.5ms$ 内，磁盘没有停下，它继续旋转了 $2.5 / (\frac{10}{9}) = 2.25$ 个扇区。 也就是说，当A处理完时，磁头已经越过了记录B（紧挨着A），来到了扇区4的内部！为了读取B，磁头必须傻傻地等待磁盘再转一整圈，直到B再次转到磁头下方。

• 读取并处理1个记录的总周期 = 读出时间 + 处理时间 + 延迟等待下一个记录的时间 = 刚好是磁盘旋转一圈的时间 (10ms)。
• 读前8个记录并找到下一个：$8 \times 10ms = 80ms$。
• 读出最后一个记录I读取 $\frac{10}{9} ms$ + 处理 $2.5ms = 3.61ms$。
• 总时间 = $80 + 3.61 = 83.61ms$。

(2) 最优化分布的设计： 既然处理A需要 $2.25$ 个扇区的时间，那我们何不跳过这3个扇区，直接把B放在磁头处理完A后刚刚好到达的地方呢？ 读完A，处理A用掉 $2.25$ 个扇区的时间，磁头滑过了 3 个扇区的起始位置。因此，逻辑上相邻的记录在物理位置上应该间隔 3 个扇区（即放在第4个位置）。

• 存放位置（按扇区0~8顺序列出）： A, H, F, D, B, I, G, E, C(推理：A在0，B在4，C在8，D在3，E在7，F在2，G在6，H在1，I在5)
• 计算时间： 每个记录读取+处理+对齐耗时恰好为 4 个扇区的时间（$4 \times \frac{10}{9}ms = \frac{40}{9}ms$）。 前 8 个记录耗时：$8 \times \frac{40}{9} = \frac{320}{9} ms$。 第 9 个记录读出并处理：$\frac{10}{9} + 2.5 = \frac{32.5}{9} ms$。 总时间 = $\frac{320}{9} + \frac{32.5}{9} = \frac{352.5}{9} ms \approx \mathbf{39.17 ms}$。

易错点： 学生常常忘记磁盘在CPU处理数据时是不会停下等你的。必须把"错过的扇区"换算成下一圈的延迟时间。

15. 磁盘交错存储：20ms/r、10扇区

假定磁盘转速为 20ms/r，每个磁道被划分为 10 个扇区。现有 10 条记录存放在同一磁道上(一条记录正好与一个扇区的大小相等)，处理程序从磁盘读出一条记录需要 4ms，现要求按从 1 到 10 的顺序处理这 10 条记录。若磁头处于首条记录的起点位置，则：

• (1) 按逆时针方向依次存放这 10 条记录(磁盘顺时针方向旋转)，处理程序读取这 10 条记录需要多长时间？
• (2) 按最优化分布重新安排这 10 条记录，写出记录的逆时针存放顺序，并计算处理这 10 条记录需要的时间。

解析

原理解析 (The 'Why')

这也是典型的**交错因子（Interleaving）**问题。

• 转速与扇区： 20ms/圈，10个扇区/圈 $\Rightarrow$ 读取 1 个扇区需要 2ms。
• 处理时间： 给定为 4ms（注意，这4ms等于转过 2 个扇区的时间）。

(1) 顺序存放： 读R1(2ms) $\rightarrow$ 处理R1(4ms)。此时磁盘转过了2个扇区，磁头来到了扇区3的起始位置。 但我们需要读R2（在扇区1）。错过了！只能等磁盘再转一圈转回来。 所以，处理一条记录的周期 = $20ms$ (刚好一圈)。前9条需 $9 \times 20 = 180ms$。最后一条R10只需读取(2ms)和处理(4ms)，共6ms。总计 $186ms$。

(2) 最优化分布： 读完并处理完R1，一共耗时 $2ms + 4ms = 6ms$。此时磁头刚好完美对准了第3个扇区（偏移量为3，即扇区号3，如果起始为0）的起点！ 因此，不需要任何延迟，我们直接把 R2 放在扇区3即可。物理间隔为 3。

答案与详细解答

(1) 顺序存放的时间：

• 前9条记录，每条触发一次完整的20ms旋转周期：$9 \times 20ms = 180ms$。
• 第10条记录读取并处理：$2ms + 4ms = 6ms$。
• 总时间 = 186 ms。

(2) 最优化分布：

• 存放顺序（按物理扇区 0~9 列出）： 1, 8, 5, 2, 9, 6, 3, 10, 7, 4。 (推理：R1在0，R2在3，R3在6，R4在9，R5在2，R6在5，R7在8，R8在1，R9在4，R10在7)
• 处理时间： 因为布局完美无缝衔接，没有任何旋转延迟。 10条记录的 (读取 + 处理) = $10 \times (2ms + 4ms) = \mathbf{60 ms}$。

16. 页面置换（FIFO/OPT/LRU）缺页中断率

一个页式存储管理系统使用 FIFO、OPT 和 LRU 页面替换算法，如果作业的页面走向为：2、3、2、1、5、2、4、5、3、2、5、2。分配给作业的物理块数分别为 3。假设初始页面为空，给出页面置换过程，并计算访问过程中发生的缺页中断次数和缺页中断率。

解析

概念检查 (Concept Check)

• FIFO (先进先出): 淘汰驻留内存时间最长的页。
• OPT (最佳置换): 淘汰未来最长时间内不再被访问的页（神仙算法，往后看）。
• LRU (最近最久未使用): 淘汰历史中最长时间没有被访问过的页（往前看）。

答案与详细解答 (过程模拟表)

序列： 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 （总长 12）

(1) FIFO 算法

页面走向	2	3	2	1	5	2	4	5	3	2	5	2
物理块1	2	2	2	2	5	5	5	5	3	3	3	3
物理块2		3	3	3	3	2	2	2	2	5	5	5
物理块3				1	1	1	4	4	4	4	2	2
是否缺页	F	F		F	F	F	F		F	F		F

• 缺页次数： 9次
• 缺页中断率： $9 / 12 = \mathbf{75\%}$

(2) OPT 算法 (向右看，淘汰最晚出现的)

修正后的OPT过程：

• 进1: 内存有2,3,1。

• 进5: 往后看未来是 2,4,5,3...，1再也不出现，淘汰1。块变为2,3,5。

• 进2: 命中。

• 进4: 往后看 5,3,2,5,2，3和2和5都会用，3最晚出现，淘汰3。块变为2,5,4。

• 进5: 命中。

• 进3: 往后看 2,5,2，4再也不用，淘汰4。块变为2,5,3。

• 后续全部命中。

• 缺页次数： 6次

• 缺页中断率： $6 / 12 = \mathbf{50\%}$

(3) LRU 算法 (向左看，淘汰最久未用的)

页面走向	2	3	2	1	5	2	4	5	3	2	5	2
物理块1	2	2	2	2	2	2	2	2	3	3	3	3
物理块2		3	3	3	5	5	5	5	5	5	5	5
物理块3				1	1	1	4	4	4	2	2	2
是否缺页	F	F		F	F		F		F	F

• 缺页次数： 7次
• 缺页中断率： $7 / 12 \approx \mathbf{58.3\%}$

17. 多级存储器有效访问时间（EAT）

某计算机有缓存、内存、辅存来实现虚拟存储器。如果数据在缓存中，访问它需要 Ans；如果在内存但不在缓存，需要 Bns 将其装入缓存，然后才能访问；如果不在内存而在辅存，需要 Cns 将其读入内存，然后，用 Bns 再读入缓存，然后才能访问。假设缓存命中率为 (n-1)/n，内存命中率为 (m-1)/m。给出数据在缓存、内存、以及辅存中比率，并计算数据平均访问时间。

解析

原理解析 (The 'Why')

这是经典的多级存储器有效访问时间（EAT）计算。

• 命中缓存的概率： $P_{cache} = \frac{n-1}{n}$。耗时：只需 $A$。
• 缓存未命中，但命中内存的概率： $P_{mem} = \frac{1}{n} \times \frac{m-1}{m}$。耗时：$A+B$。
• 全未命中，在辅存中的概率： $P_{disk} = \frac{1}{n} \times \frac{1}{m} = \frac{1}{nm}$。耗时：$A+B+C$。

答案与详细解答

(1) 数据所在层级的比率：

• 数据在缓存中的比率： $\mathbf{\frac{n-1}{n}}$
• 数据在内存（但不在缓存）中的比率： $\mathbf{\frac{m-1}{nm}}$
• 数据在辅存（不在内存）中的比率： $\mathbf{\frac{1}{nm}}$

(2) 平均访问时间 (EAT) 计算：

$$EAT = \frac{n-1}{n}A + \frac{m-1}{nm}(A+B) + \frac{1}{nm}(A+B+C) = \mathbf{A + \frac{B}{n} + \frac{C}{nm}} \text{ (ns)}$$

18. 磁盘组柱面数、总容量与平均等待时间

某磁盘组有 6 片盘片，每片有两个记录面，存储区域内径为 22cm，外径为 33cm，道存储密度为 40 道/cm，内层位存储密度为 400b/cm，转速为 3000r/min（转/分），问共有多少柱面？盘组总存储量为多少？平均等待时间为多少？

解析

答案与详细解答

• 柱面数： 有效半径范围 = $\frac{33 - 22}{2} = 5.5 \text{ cm}$ 柱面数 = $5.5 \text{ cm} \times 40 \text{ 道/cm} = \mathbf{220 \text{ 柱面}}$。
• 总存储量： 最内层磁道周长 = $\pi \times 22 \text{ cm}$ 每条磁道容量 = $22\pi \text{ cm} \times 400 \text{ b/cm} = 8800\pi \text{ bits}$。 总磁头/盘面数 = 6片 $\times$ 2面 = 12面。 总容量 = 12面 $\times$ 220道 $\times$ $8800\pi$ bits = $23,232,000 \pi \text{ bits}$ （约 $\mathbf{72.98 \text{ Mbits}}$ 或 $\mathbf{9.12 \text{ MB}}$）。
• 平均等待时间： 转速 = 3000 r/min = 50 r/s。旋转一圈需 $1000 / 50 = 20 ms$。 平均等待时间 = $\frac{1}{2} \times 20ms = \mathbf{10 ms}$。

19. 四道作业系统：SJF + 抢占式优先数调度

若有一个四道作业系统，如果在一段时间内先后有 6 个作业，它们提交和运行时间由下表给出。作业采用短作业优先的调度算法，进程采用以优先数的抢占式调度算法，作业优先数就是进程优先数，优先数越小，优先级越高。

作业序号	提交时间	运行时间（分钟）	优先数	开始时间	结束时间	周转时间	带权周转时间
1	8:00	40	5
2	8:15	30	4
3	8:20	20	2
4	8:25	20	3
5	8:30	10	2
6	8:35	5	2

问题：

• (1) 完成上表，给出各个作业的开始时间、完成时间、周转时间和带权周转时间；
• (2) 计算平均作业周转时间和平均作业带权周转时间。

解析

原理解析 (The 'Why')

• "四道"作业系统： 意味着内存中最多只能同时存在 4 个进程。如果有第 5 个作业到达，哪怕它是极短的作业，也必须在"外存后备队列"中排队，直到内存有人腾出位置！
• 双层调度： 高级调度（进内存）看 SJF；低级调度（抢 CPU）看 优先数。

答案与详细解答

(1) 时间表格计算

作业	提交时间	运行时间	优先	开始时间	完成时间	周转时间	带权周转时间
1	8:00	40	5	8:00	10:05	125	125/40 = 3.125
2	8:15	30	4	8:15	9:40	85	85/30 ≈ 2.833
3	8:20	20	2	8:20	8:40	20	20/20 = 1.0
4	8:25	20	3	8:55	9:15	50	50/20 = 2.5
5	8:30	10	2	8:45	8:55	25	25/10 = 2.5
6	8:35	5	2	8:40	8:45	10	10/5 = 2.0

(2) 平均计算

• 平均周转时间： $(125 + 85 + 20 + 50 + 25 + 10) / 6 = 315 / 6 = \mathbf{52.5 \text{ 分钟}}$。
• 平均带权周转时间： $(3.125 + 2.833 + 1.0 + 2.5 + 2.5 + 2.0) / 6 \approx \mathbf{2.326}$。

易错点： 完全忽视"四道"的限制，把5和6早早放进内存引发错误的抢占。记住，多道度满了之后，大门焊死，新作业只能在外边排队等。

20. UNIX 多级索引节点（Inode）最大文件长度

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

解析

答案与详细解答

• 每个索引块能容纳的指针数： $1KB / 4B = 256$ 个指针。
• 直接寻址： 4 个指针，指向 4 个物理块。
• 一级间接： 2 个指针 $\times$ 256 = 512 个物理块。
• 二级间接： 1 个指针 $\times$ 256 $\times$ 256 = 65536 个物理块。
• 文件最大块数： $4 + 512 + 65536 = 66052$ 块。
• 文件最大长度： 66052 块 $\times$ 1KB = 66052 KB（即 64MB + 516KB）。

21. 单道调度：FCFS / SJF / HRRN 对比

如果在一段时间内先后有 5 个作业，它们提交和运行时间由下表给出。

作业序号	提交时间	运行时间（分钟）	开始时间	结束时间	周转时间	带权周转时间
1	8:00	50
2	8:15	30
3	8:20	20
4	8:25	20
5	8:30	10

问题：

• (1) 分别使用先来先服务、最短进程优先和最高响应比算法完成上表，给出各个作业的开始时间、完成时间、周转时间和带权周转时间；
• (2) 计算各算法的平均作业周转时间和平均作业带权周转时间。

解析

原理解析 (The 'Why')

响应比 $R_R = 1 + \frac{\text{等待时间}}{\text{服务时间}}$。HRRN在每次有作业完成时，动态计算队列中所有人的响应比，挑最大的执行。

答案与详细解答

(1) FCFS (先来先服务)

作业	提交	运行	开始时间	完成时间	周转时间	带权周转
1	8:00	50	8:00	8:50	50	1.0
2	8:15	30	8:50	9:20	65	2.167
3	8:20	20	9:20	9:40	80	4.0
4	8:25	20	9:40	10:00	95	4.75
5	8:30	10	10:00	10:10	100	10.0
平均周转: $390 / 5 = \mathbf{78 m}$；平均带权: $\mathbf{4.383}$

(2) SJF (最短作业优先 - 非抢占)

J1(8:00~8:50)。8:50时队列中全员到齐，按运行时间从短到长选：J5(10) > J3(20) = J4(20) > J2(30)。J3比J4早到，故J3先。执行顺序：J1 $\rightarrow$ J5 $\rightarrow$ J3 $\rightarrow$ J4 $\rightarrow$ J2。

作业	提交	运行	开始时间	完成时间	周转时间	带权周转
1	8:00	50	8:00	8:50	50	1.0
5	8:30	10	8:50	9:00	30	3.0
3	8:20	20	9:00	9:20	60	3.0
4	8:25	20	9:20	9:40	75	3.75
2	8:15	30	9:40	10:10	115	3.833
平均周转: $330 / 5 = \mathbf{66 m}$；平均带权: $\mathbf{2.917}$

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

对于这组数据，HRRN 的调度顺序与 SJF 完全一致（依然是 1-5-3-4-2），时间表和平均时间同 SJF 算法。

22. 请求分页：4页框，页面走向 3,4,5,6,3,5,6,3,7,5

在请求分页管理系统中, 一个程序的页面走向为: 3, 4, 5, 6, 3, 5, 6, 3, 7, 5，设分配给该程序的存储块为 4。所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。

解析

23. 磁盘顺序文件：逻辑记录定位

假设有一个磁盘组共有 100 个柱面，每个柱面上有 8 个磁道，每个盘面被分成 8 个扇区。现有一个含有 6400 逻辑记录的文件，逻辑记录的大小与扇区一致，该文件以顺序结构的形式被存储到磁盘上。柱面、磁道、扇区的编号从"0"开始，逻辑记录的编号也从"0"开始。文件信息从 0 柱面、0 磁道、0 扇区开始存放，试问：

• (1) 该文件的 3680 个逻辑记录应该存放在什么位置？
• (2) 78 柱面的 6 磁道的 6 扇区中存放了该文件的第几号逻辑记录？

解析

24. 生产者-消费者：GET/PRO/PUT 同步互斥

如图所示，系统中有三个进程 GET、PRO 和 PUT，共用两个缓冲区 BUF1 和 BUF2。假设 BUF1 中最多可放 11 个信息，现已放入了两个信息；BUF2 最多可放 5 个信息。GET 进程负责不断地将输入信息送入 BUF1 中，PRO 进程负责从 BUF1 中取出信息进行处理，并将处理结果送到 BUF2 中，PUT 进程负责从 BUF2 中读取结果并输出。试写出正确实现 GET、PRO、PUT 的同步与互斥的算法（要求：（1）用类 C 语言描述，条理清楚，注释恰当；（2）信号量原语统一使用 wait 和 signal。）

图 进程合作：GET → BUF1 → PRO → BUF2 → PUT

解析

25. 死锁判断：R1/R2 设备申请顺序

某系统有 R1 设备 3 台，R2 设备 4 台，它们被 P1、P2、P3 和 P4 进程共享，且已知这 4 个进程均按以下顺序使用设备：

→申请R1→申请R2→申请R1→释放R1→释放R2→释放R1

• (1) 系统运行中可能产生死锁吗？为什么？
• (2) 若可能的话，请举出一种情况，并画出表示该死锁状态的进程—资源图。

解析

26. 并发进程执行路径与与时间相关的错误

(1) 两个并发进程并发执行，其中，A、B、C、D、E 是原语，试给出可能的并发执行路径。

Process P           Process Q
begin               begin
    A;                  D;
    B;                  E;
    C;              end;
end;

(2) 两个并发进程 P1 和 P2 并发执行，它们的程序分别如下：

      P1                P2
    repeat            repeat
      k:=k×2;         print k;
      k:=k+1;           k:=0;
    until false;      until false;

若令 k 的初值为 5，让 P1 先执行两个循环，然后，P1 和 P2 又并发执行了一个循环，写出可能的打印值，指出与时间有关的错误。

解析

27. 快表命中率计算

一台计算机的内存空间为 1024 个页面，页表放在内存中，从页表中读一个字的开销是 500ns。为了减少开销，使用了有 32 个字的快表，查找速度为 100ns。要把平均开销降到 200ns 需要的快表命中率是多少?

解析

28. 磁带分块存储与利用率

假定磁带记录密度为每英寸 800 字符，每一逻辑记录为 200 字符，块间隔为 0.6 英寸。现有 3200 个逻辑记录需要存储，如果不考虑存储记录，则不成组处理和以 8 个逻辑记录为一组的成组处理时磁带的利用率各是多少？两种情况下，3200 个逻辑记录需要占用多少磁带空间？

解析

29. UNIX 文件权限判断

一个 UNIX 文件 F 的存取权限为：rwxr-x---，该文件的文件主 uid＝12，gid=1，另一个用户的 uid=6，gid=1，是否允许该用户执行文件 F？

解析

30. UNIX/Linux 文件访问偏移：间接次数

一个 UNIX/Linux 文件，如果一个盘块的大小为 1KB，每个盘块占 4 个字节，那么，若进程欲访问偏移为 263168 字节处的数据，需经过几次间接？

解析

31. 磁盘交错存储：20ms/r、8扇区

假设有 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. 如何采取优化方法，使处理这些记录所花费的总时间最短？求出该最短时间。

解析

32. 可变分区管理：SJF 与 HRRN 调度

系统采用不能移动的可变分区管理方案，现有可供用户使用的主存空间为 100K，设有四个作业 J1, J2, J3, J4 它们的到达时间和计算时间如下表:

作业	到达时间	计算时间	需要主存容量	周转时间
J1	8:00	40分钟	30K
J2	8:20	35分钟	70K
J3	8:30	20分钟	30K
J4	8:40	10分钟	20K

若作业在处理机上按单道方式运行，请分别写出：

• （1）最短者优先算法选中作业的执行顺序，并计算周转时间和平均周转时间。
• （2）响应比高者优先算法选中作业的执行顺序，并计算周转时间和平均周转时间。

解析

33. 分页式虚存：FIFO 与 LRU 缺页中断对比

使用"分页式"虚拟存储管理技术，假设一个进程 P 的页面访问顺序如下：0 1 2 3 0 1 4 0 1 2 3 4。该进程创建时没有加载任何页面，即该进程启动时其所有指令和数据都不在内存中。

• (1) 设分配给该进程的物理页帧为 3 个，使用 FIFO 页面置换算法时，请问会发生多少次缺页中断？使用硬件实现的 LRU 算法，会发生多少次缺页中断？
• (2) 对于以上两种页面置换算法，如希望减少缺页中断的次数，是否可以通过增加物理页帧来解决？为什么？
• (3) 在分页系统中将 I/O 设备的数据缓冲区映射到内存空间后，其对应的页面是否能够被替换？为什么？

解析

概念核对 (Concept Check)

• FIFO (先进先出)：淘汰在内存中驻留时间最久的页面。
• LRU (最近最少使用)：淘汰最长时间没有被访问过的页面。
• 缺页中断 (Page Fault)：当 CPU 访问的页面不在实体内存中时触发。

答案与详细解答

(1) 缺页中断次数模拟：

• FIFO 算法 (3个页框)： 0(缺) → 1(缺) → 2(缺) → 3(缺，淘汰0) → 0(缺，淘汰1) → 1(缺，淘汰2) → 4(缺，淘汰3) → 0(命中) → 1(命中) → 2(缺，淘汰0) → 3(缺，淘汰1) → 4(命中) 总计：发生 9 次缺页中断。

• LRU 算法 (3个页框)： 0(缺) → 1(缺) → 2(缺) → 3(缺，淘汰0) → 0(缺，淘汰1) → 1(缺，淘汰2) → 4(缺，淘汰3) → 0(命中，更新) → 1(命中，更新) → 2(缺，淘汰4) → 3(缺，淘汰0) → 4(缺，淘汰1) 总计：发生 10 次缺页中断。

(2) 增加物理页框是否能减少缺页？

• LRU：可以。 增加页框一定能减少或维持缺页次数（LRU 符合堆栈属性 Stack Property）。
• FIFO：不一定。 FIFO 算法可能会遭遇 Belady 异常 (Belady's Anomaly)。对于某些特定的访问序列，增加分配的物理页框数量反而会导致缺页次数上升。

(3) 映射到内存的 I/O 缓冲页面能否被替换？

• 不能。
• 原因： 如果正在进行 I/O 操作（如 DMA 传输）的页面被置换到磁盘，而另一个进程的数据刚好载入这个物理页框，那么硬件 I/O 设备会将数据直接覆盖掉无辜进程的内存，造成严重的数据损坏。因此，涉及 I/O 的页面必须被锁定 (Pinned/Locked) 在主存中，禁止被替换。

常见易错点： 学生常会直觉认为"更好的算法"在任何情况下都会比"简单的算法"表现好。这题恰好反直觉，LRU（10次）的缺页次数反而高于 FIFO（9次）。

34. 连接文件：逻辑字节访问对应物理块

设某文件为连接文件，由 5 个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为 512 字节，并依次存放在 50、121、75、80、63 号磁盘块上。若要存取文件的第 1569 逻辑字节处的信息，问要访问哪一个磁盘块？

解析

答案与详细解答

已知每个逻辑记录和磁盘块的大小为 512 Bytes。

1. 计算目标字节位于第几个逻辑记录： $1569 \div 512 = 3 \ldots \text{余数 } 33$。 这表示第 1569 个字节位在第 3 个完整的逻辑块之后（也就是进入了第 4 个逻辑记录，索引为 3），偏移量为 33。
2. 对应物理磁盘块顺序（从0开始索引）：
   • 索引 0：第 50 号块
   • 索引 1：第 121 号块
   • 索引 2：第 75 号块
   • 索引 3：第 80 号块
3. 因此，需要访问的是第 80 号磁盘块。

常见易错点： 商为 3 代表前面已经有 3 个完整的块（索引0, 1, 2），数据落在下一个块（索引 3），也就是清单中的第 4 个块。

35. HRRN 调度：五个作业响应比与周转时间

设有某系统可供用户使用的主存空间为 100K，有五个作业 J1, J2, J3, J4, J5 进入输入井的时间、计算时间和内存要求如下表所示。若作业在处理机上按单道方式运行，且作业按响应比高者优先调度算法，进程按先来先服务算法。试写出作业的执行顺序，计算响应比、作业的周转时间和平均周转时间。

作业	进入输入井时间	计算时间	需要主存容量	开始时间	结束时间	周转时间
J1	10:06	42分钟	18K
J2	10:19	30分钟	65K
J3	10:30	24分钟	57K
J4	10:36	24分钟	15K
J5	10:42	12分钟	25K

解析

答案与详细解答

• 10:06，只有 J1 到达。J1 开始执行。J1 执行 42 分钟，结束时间为 10:48。J1 周转时间 = 42 分。
• 10:48，此时 J2, J3, J4, J5 皆已到达，计算响应比：
  • J2 等待 = 29分。$R_2 = 1 + 29/30 = 1.967$
  • J3 等待 = 18分。$R_3 = 1 + 18/24 = 1.75$
  • J4 等待 = 12分。$R_4 = 1 + 12/24 = 1.5$
  • J5 等待 = 6分。$R_5 = 1 + 6/12 = 1.5$
  • 最高者为 J2。J2 执行 30 分钟，结束时间为 11:18。J2 周转时间 = 59分。
• 11:18，J3, J4, J5 继续竞争：
  • J3 等待 = 48分。$R_3 = 1 + 48/24 = 3.0$
  • J4 等待 = 42分。$R_4 = 1 + 42/24 = 2.75$
  • J5 等待 = 36分。$R_5 = 1 + 36/12 = 4.0$
  • 最高者为 J5。J5 执行 12 分钟，结束时间为 11:30。J5 周转时间 = 48分。
• 11:30，J3, J4 继续竞争：
  • J3 等待 = 60分。$R_3 = 1 + 60/24 = 3.5$
  • J4 等待 = 54分。$R_4 = 1 + 54/24 = 3.25$
  • 最高者为 J3。J3 执行 24 分钟，结束时间为 11:54。J3 周转时间 = 84分。
• 11:54，J4 开始执行。J4 执行 24 分钟，结束时间为 12:18。J4 周转时间 = 102分。

执行顺序：J1 → J2 → J5 → J3 → J4

平均周转时间：$(42 + 59 + 84 + 102 + 48) / 5 = 335 / 5 = \mathbf{67 \text{ 分钟}}$。

常见易错点： 内存 100K 是一个干扰信息！题目明确"按单道方式运行"，不需要考虑内存分配并发情况。

36. 银行家算法：三类资源（A/B/C）、五进程

设系统中资源类集合为 {A，B，C}，资源类 A 中含有 10 个资源实例，B 中含有 5 个，C 中含有 7 个。在 T0 时刻状态如下：

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

• (1) 假如现在进程 P1 发出新的资源申请 Request[1]=(1,0,2)，系统是否可以实施资源分配，为什么？
• (2) 在上面新状态下，对于进程 P0 所发出的资源请求（0, 2, 0）系统是否能实施资源分配？要求写出计算步骤及过程。

解析

答案与详细解答

(1) P1 申请 (1, 0, 2)

1. 检查合法性：Request (1,0,2) $\le$ P1 Need (1,2,2) 成立。
2. 检查可用性：Request (1,0,2) $\le$ Available (3,3,2) 成立。
3. 试探分配后的新状态：
   • Available = (3,3,2) - (1,0,2) = (2, 3, 0)
   • P1 Allocation = (3, 0, 2)，P1 Need = (0, 2, 0)
4. 安全性检查（Available=(2,3,0)）： P1 Need=(0,2,0) 满足，P1 执行完释放，Available=(5,3,2)。 后续可满足 P3 → P4 → P0 → P2。 结论：存在安全序列（P1→P3→P4→P0→P2），可以实施资源分配。

(2) 随后 P0 请求 (0, 2, 0)

1. 在上述新状态下，Available = (2, 3, 0)。
2. 检查：Request $\le$ P0 Need 成立；Request $\le$ Available 成立。
3. 试探分配后的新状态：
   • Available = (2,3,0) - (0,2,0) = (2, 1, 0)
   • P0 Allocation = (0,3,0)，P0 Need = (7,2,3)
4. 安全性检查（Available=(2,1,0)）： 检查所有进程当前的 Need：没有任何一个进程的 Need 可以被 (2,1,0) 满足，无法找到安全序列，陷入不安全状态。 结论：拒绝分配，P0 必须等待。

常见易错点： 许多人在第二步忘了把 Available 基础值更新为第一步算完的 (2,3,0)，而是继续拿最初的 (3,3,2) 去算。

37. 位示图：字号和位号计算

现有一台 16 位字长的专用机，采用页式存储管理。主存储器共有 4096 块 (块号为 0～4095)，现用位示图分配主存空间。试问：

• (1) 该位示图占用几个字?
• (2) 主存块号 3999 对应位示图的字号和位号 (均从 0 开始) 各是多少?
• (3) 位示图字号 199，位号 9 对应主存的块号是多少?

解析

答案与详细解答

(1) 位示图占用几个字？

共有 4096 个块，需要 4096 个 Bit。机器字长为 16 位，每个 Word 有 16 个 Bit。 佔用字数 = $4096 \div 16 = \mathbf{256}$ 个字。

(2) 块号 3999 对应的字号和位号？

字号 = $\lfloor 3999 \div 16 \rfloor = \mathbf{249}$。 位号 = $3999 \bmod 16 = \mathbf{15}$。

(3) 字号 199，位号 9 对应的主存块号？

块号 = $\text{字号} \times 16 + \text{位号} = 199 \times 16 + 9 = 3184 + 9 = \mathbf{3193}$。

常见易错点： 注意题目强调"均从 0 开始"。如果从 1 开始，计算公式需要进行平移。

38. 信号量同步：数据采集-计算-输出三进程

某数据处理系统由数据采集、数据计算和数据输出三个进程组成，采集进程把采集到的数据送入由 M 个缓冲块组成的输入缓冲区（每次向一个缓冲块送数据），计算进程从输入缓冲区取数据计算（每次取一个缓冲块的数据），并将计算结果送入到由 N 个缓冲块组成的输出缓冲区（每次向一个缓冲块送数据），输出进程每次从输出缓冲区取一个结果输出。编写利用信号量机制实现的三者之间同步算法，要求写出信号量的含义和初值。

解析

答案与详细解答

信号量定义：

• emptyM = M：输入缓冲区的空位数。
• fullM = 0：输入缓冲区中已有数据的数量。
• mutexM = 1：对输入缓冲池进行互斥访问。
• emptyN = N：输出缓冲区的空位数。
• fullN = 0：输出缓冲区中已有结果的数量。
• mutexN = 1：对输出缓冲池进行互斥访问。

// 采集进程 (Producer 1)
while(true) {
    采集数据;
    wait(emptyM);    // 申请输入缓冲区空位 (同步)
    wait(mutexM);    // 锁定输入缓冲区 (互斥)
    将数据放入输入缓冲区;
    signal(mutexM);  // 解锁输入缓冲区
    signal(fullM);   // 通知输入缓冲区已有数据
}

// 计算进程 (Consumer 1 & Producer 2)
while(true) {
    wait(fullM);     // 等待输入缓冲区有数据
    wait(mutexM);    // 锁定输入缓冲区
    从输入缓冲区取出数据;
    signal(mutexM);
    signal(emptyM);  // 释放输入缓冲区空位

    计算数据;

    wait(emptyN);    // 申请输出缓冲区空位
    wait(mutexN);    // 锁定输出缓冲区
    将结果放入输出缓冲区;
    signal(mutexN);
    signal(fullN);   // 通知输出缓冲区已有结果
}

// 输出进程 (Consumer 2)
while(true) {
    wait(fullN);     // 等待输出缓冲区有结果
    wait(mutexN);    // 锁定输出缓冲区
    从输出缓冲区取出结果;
    signal(mutexN);
    signal(emptyN);  // 释放输出缓冲区空位
    
    输出结果;
}

常见易错点： wait(互斥信号量) 和 wait(同步信号量) 的顺序不能颠倒！必须先同步（申请资源 empty/full），再互斥（锁定 mutex），否则会导致死锁。

39. 文件系统设计：60G 磁盘、商用 I/O

假定你负责设计一个基于 32 位计算机的文件系统，如果存储磁盘的容量是 60G，磁盘扇区大小为 1M，文件的最大容量为 2GB，文件名仅支持 8.3 格式。该文件系统主要满足商用 I/O 操作，因此空间变化比较频繁，请设计一种合理的文件系统磁盘空间管理方式。包括目录、文件的逻辑结构与物理实现。

解析

答案与详细解答

• 物理实现 (Physical Structure)： 因为空间变化频繁，动态扩容要求高，应采用索引分配 (Indexed Allocation)。 磁盘块大小为 1MB，最大文件 2GB，代表一个文件最多占用 2048 个块。一个索引块完全可以装得下这 2048 个指针，因此采用单级索引结构即可。

• 逻辑结构 (Logical Structure)： 因为主要满足商用 I/O，这类场景通常涉及数据库和结构化查询，应该采用有结构文件（记录式文件），为了加速查询，设计为索引顺序文件。

• 磁盘空间管理 (Free Space Management)： 总块数 = 60GB / 1MB = 60,000 块。 可以使用位示图 (Bit map) 来管理空闲块。只有 60,000 块，位示图仅需约 7.5 KB 的空间，可以常驻内存，提供极高的分配效率。

• 目录结构 (Directory Structure)： 采用多级树状目录结构 (Tree-structured Directory)。 由于只支持 8.3 格式（文件名 8 字符 + 扩展名 3 字符，共 11 bytes），目录项可以设计为包含 11 Bytes文件名 + 4 Bytes索引节点/首块指针 等简洁结构。

常见易错点： 不要盲目写多级索引。这里块大小有 1MB 那么大，一个块装几万个指针绰绰有余，完全不需要 UNIX 那种多层间接索引。

40. 信号量同步：read/move/print 三进程单容量缓冲

假定系统有三个并发进程 read, move 和 print 共享缓冲器 B1 和 B2。进程 read 负责从输入设备上读信息，每读出一个记录后把它存放到缓冲器 B1 中。进程 move 从缓冲器 B1 中取出一记录，加工后存入缓冲器 B2。进程 print 将 B2 中的记录取出打印输出。缓冲器 B1 和 B2 每次只能存放一个记录。要求三个进程协调完成任务，使打印出来的与读入的记录的个数，次序完全一样。请用 wait 和 signal 原语写出它们的并发程序。

解析

答案与详细解答

由于 B1 和 B2 的容量都严格为 1，为每个缓冲区定义一对同步信号量：

• empty1 = 1：B1 的空位数。
• full1 = 0：B1 的数据数。
• empty2 = 1：B2 的空位数。
• full2 = 0：B2 的数据数。

// 读入进程
void read_process() {
    while(true) {
        读入一个记录 info;
        wait(empty1);      // 确保 B1 为空
        将 info 存入 B1;
        signal(full1);     // 通知 move 进程 B1 已有数据
    }
}

// 搬运/加工进程
void move_process() {
    while(true) {
        wait(full1);       // 确保 B1 有数据
        从 B1 取出记录 info;
        signal(empty1);    // 释放 B1

        加工 info;

        wait(empty2);      // 确保 B2 为空
        将 info 存入 B2;
        signal(full2);     // 通知 print 进程 B2 已有数据
    }
}

// 打印进程
void print_process() {
    while(true) {
        wait(full2);       // 确保 B2 有数据
        从 B2 取出记录 info;
        signal(empty2);    // 释放 B2

        打印 info;
    }
}

常见易错点： 画蛇添足加上 mutex。当缓冲区大小 $>1$ 或存在多个竞争者时才必须加上 mutex。对于严格的一对一且容量为 1 的通道，empty 和 full 的 0/1 切换本身就是完美的互斥锁。

41. 磁道调度：FCFS / SSTF / SCAN（递增方向）

若干个等待访问磁盘者依次要访问的磁道为 20，44，40，4，80，12，76，假设每移动一个磁道需要 3 毫秒时间，移动臂当前位于 40 号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。

• （1）先来先服务算法；
• （2）最短寻道时间优先算法；
• （3）扫描算法（当前磁头移动的方向为磁道递增）。

解析

42. 文件目录检索：目录项分解的平均磁盘访问次数

在实现文件系统时，一般为加快文件目录的检索速度，可利用"文件控制块部分装入"的方法。假设目录文件（即文件控制块）存放在磁盘上，磁盘的每个盘块为 512B，每个目录项占 128B，其中文件名占 11B。为提高检索速度，通常将目录项分解成两部分，第一部分（包括文件名和文件内部号）占 16B，第二部分（包括文件内部号和文件其他描述信息）占 122B。假设某一目录共有 254 个目录项（文件控制块），试分别给出前、后二种方法查找该目录文件某一目录项的平均访问磁盘次数。

解析

43. 磁鼓优化存储：20个区，1ms读取，2ms处理

旋转型设备上信息的优化分布能减少为若干个 I/O 服务的总时间。设磁鼓上分为 20 个区，每区存放一个记录，磁鼓旋转一周需 20 毫秒，读出每个记录平均需用 1 毫秒，读出后经 2 毫秒处理，再继续处理下一个记录。在不知当前磁鼓位置的情况下：

• （1）顺序存放记录 1、……，记录 20 时，试计算读出并处理 20 个记录的总时间；
• （2）给出优先分布 20 个记录的一种方案，使得所花的总处理时间减少，且计算出这个方案所花的总时间。

解析

44. 分时操作系统设计：重要进程与 I/O 瓶颈

假设你需要为某企业设计一个分时操作系统，请回答以下问题：

• (1) 你认为哪些系统进程最重要？
• (2) 如果该操作系统主要负责处理 IO-Bounded 进程，你认为系统性能的瓶颈可能是什么？如何解决？

解析

45. 银行家算法：单类资源（S类 150个）

系统中具有 S 类资源 150 个，在 T0 时刻按下表所示分配给 3 个进程：

进程	Maximum demand	Current allocation
P1	70	25
P2	60	40
P3	60	45

对下列请求应用银行家算法逐步分别分析判定是否安全，如果是安全的，请给出一个可能的进程安全执行序列；如果不是安全的，请说明原因。

• (1) 第 4 个进程 P4 到达，对资源 S 的最大需求为 60 个，当前请求分配 25 个；
• (2) 第 4 个进程 P4 到达，对资源 S 的最大需求 50 个，当前请求分配 35 个。

解析

46. 请求分页：快表地址转换过程与虚地址计算

设正在处理器上执行的一个进程的页表如下表所示，表中的虚页号和物理块号是十进制数，起始页号（块号）均为 0。所有的地址均是存储器字节地址。页的大小为 1024 字节。

虚页号	状态位	访问位	修改位	物理块号
0	1	1	0	4
1	1	1	1	7
2	0	0	0	-
3	1	0	0	2
4	0	0	0	-
5	1	0	1	0

注：当某页被访问时，其访问位置 1。

• (1) 详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程。
• (2) 下列十进制虚地址对应于什么物理地址：5579，2232

解析

47.（题目缺失）

解析

48. SSTF 与 SCAN 磁道调度（200个柱面）

假定一个磁盘有 200 个柱面（编号 0-199），磁盘请求队列由对如下柱面的请求序列构成：50, 60, 30, 18, 90, 165, 150, 38, 12, 190. 已知磁头当前位于 95 号柱面，移动方向为向内。

• (1) 如果系统采用 SSTF 算法进行调度，那么系统处理完上述所有的磁盘请求所需的寻道距离是多少？
• (2) 如果系统采用 SCAN 算法进行调度，那么系统处理完上述所有的磁盘请求所需的寻道距离是多少？

解析

49. 请求分页：地址位数与物理块数计算

一个采用请求式存储管理的计算机系统，其主存（实存）容量为 256M 字节，虚存容量（给用户的最大地址空间）为 4G 字节，页面大小为 4K 字节，试问：

• (1) 主存物理地址应设为多少位？
• (2) 主存中有多少物理块？
• (3) 虚拟地址应该设多少位？
• (4) 虚拟地址空间最多可以有多少页？
• (5) 页内最大和最小偏移量是多少？

解析

50. 页面置换算法计算（FIFO / LRU / OPT）

设某作业占有 7 个页面，如果在主存中只允许装入 4 个工作页面（即工作集为 4），作业运行时，实际访问页面的顺序是：1, 2, 3, 6, 4, 7, 3, 2, 1, 4, 7, 5, 6, 5, 2, 1。试用 FIFO、LRU 和 OPT 页面置换算法，列出各自的页面淘汰顺序和页面置换次数。

解析

概念核对 (Concept Check)

• 工作集大小： 题目规定只允许装入 4 个工作页面，意味着内存中最多只有 4 个物理块（Frame）供该作业使用。
• 缺页中断 (Page Fault) 与 页面置换 (Page Replacement) 的区别： 当内存块未满时，调入新页面只会发生"缺页中断"，但不会发生"页面置换"（因为有空闲位置）。只有当 4 个块都装满后，再调入新页面才会发生"置换"。题目明确要求计算的是置换次数。
• 三大算法：
  • FIFO (先进先出)：淘汰在内存中驻留时间最长的页面。
  • LRU (最近最久未使用)：淘汰在最近一段时间内最久没有被访问过的页面（向前看）。
  • OPT (最佳置换)：淘汰在未来最长时间内不再被访问的页面（向后看，理想算法）。

原理解析与计算过程

给定的访问序列长度为16：1, 2, 3, 6, 4, 7, 3, 2, 1, 4, 7, 5, 6, 5, 2, 1。 初始 4 个空闲块，装入 1, 2, 3, 6 时发生 4 次缺页，0 次置换。此时内存为 $\langle1, 2, 3, 6\rangle$。

1. FIFO (先进先出)

• 4：内存满，最先进入的是 1。淘汰 1。内存变为 $\langle2, 3, 6, 4\rangle$。
• 7：最早进入的是 2。淘汰 2。内存变为 $\langle3, 6, 4, 7\rangle$。
• 3：命中。
• 2：最早进入的是 3。淘汰 3。内存变为 $\langle6, 4, 7, 2\rangle$。
• 1：最早进入的是 6。淘汰 6。内存变为 $\langle4, 7, 2, 1\rangle$。
• 4, 7：连续命中。
• 5：最早进入的是 4。淘汰 4。内存变为 $\langle7, 2, 1, 5\rangle$。
• 6：最早进入的是 7。淘汰 7。内存变为 $\langle2, 1, 5, 6\rangle$。
• 5, 2, 1：连续命中。
• 结果：
  • 淘汰顺序： 1, 2, 3, 6, 4, 7
  • 置换次数： 6 次（总缺页10次）

2. LRU (最近最久未使用)

初始装入后为 $\langle1, 2, 3, 6\rangle$（右侧为最新使用）。

• 4：最久未用是 1。淘汰 1。变为 $\langle2, 3, 6, 4\rangle$。
• 7：最久未用是 2。淘汰 2。变为 $\langle3, 6, 4, 7\rangle$。
• 3：命中。更新顺序变为 $\langle6, 4, 7, 3\rangle$。
• 2：最久未用是 6。淘汰 6。变为 $\langle4, 7, 3, 2\rangle$。
• 1：最久未用是 4。淘汰 4。变为 $\langle7, 3, 2, 1\rangle$。
• 4：最久未用是 7。淘汰 7。变为 $\langle3, 2, 1, 4\rangle$。
• 7：最久未用是 3。淘汰 3。变为 $\langle2, 1, 4, 7\rangle$。
• 5：最久未用是 2。淘汰 2。变为 $\langle1, 4, 7, 5\rangle$。
• 6：最久未用是 1。淘汰 1。变为 $\langle4, 7, 5, 6\rangle$。
• 5：命中。变为 $\langle4, 7, 6, 5\rangle$。
• 2：最久未用是 4。淘汰 4。变为 $\langle7, 6, 5, 2\rangle$。
• 1：最久未用是 7。淘汰 7。变为 $\langle6, 5, 2, 1\rangle$。
• 结果：
  • 淘汰顺序： 1, 2, 6, 4, 7, 3, 2, 1, 4, 7
  • 置换次数： 10 次（总缺页14次）

3. OPT (最佳置换)

初始装入 $\langle1, 2, 3, 6\rangle$。

• 4：向后看后续序列 (7,3,2,1,4,7,5,6,5,2,1)。1, 2, 3 很快被用到，6 在倒数第4个才用到。淘汰 6。变为 $\langle1, 2, 3, 4\rangle$。
• 7：向后看 (3,2,1,4,7,...)。1, 2, 3 都比 4 先用到。淘汰 4。变为 $\langle1, 2, 3, 7\rangle$。
• 3, 2, 1：连续命中。
• 4：向后看 (7,5,6,5,2,1)。当前内存 $\langle1, 2, 3, 7\rangle$ 中，3 以后再也用不到了。淘汰 3。变为 $\langle1, 2, 7, 4\rangle$。
• 7：命中。
• 5：向后看 (6,5,2,1)。当前内存 $\langle1, 2, 7, 4\rangle$ 中，4 再也用不到了，淘汰 4。淘汰 4。变为 $\langle1, 2, 7, 5\rangle$。
• 6：向后看 (5,2,1)。7 再也用不到了。淘汰 7。变为 $\langle1, 2, 5, 6\rangle$。
• 5, 2, 1：连续命中。
• 结果：
  • 淘汰顺序： 6, 4, 3, 4, 7
  • 置换次数： 5 次（总缺页9次）

常见易错点 (Common Pitfalls)

在 LRU 算法中，一旦某个页面"命中（Hit）"，一定要记得将其"新鲜度"提升到最高。很多同学在发生命中时忘记更新该页面的时间戳，导致后续淘汰了错误的页面。

51. 旋转型磁盘 I/O 优化分布计算

旋转型磁盘上的信息优化分布能减少若干 I/O 服务的总时间。假如有 13 个记录存放在磁盘的某一磁道上，每个磁道划分成 13 块，每块存放一个记录，如图所示。磁盘旋转速度为 30ms 转 1 周，处理程序每读一个记录后花 5ms 进行处理。

块号	1	2	3	4	5	6	7	8	9	10	11	12	13
记录	R1	R2	R3	R4	R5	R6	R7	R8	R9	R10	R11	R12	R13

• （1）处理完 13 个记录的总时间是多少？
• （2）为缩短处理时间应如何排列这些记录？计算重新排列后的总时间。

解析

概念核对 (Concept Check)

• 单块读取时间 ($t_{read}$)： 磁盘转 1 周 30ms，共 13 块，读取 1 块的时间为 $30 / 13 \approx 2.31$ ms。
• 处理时间 ($t_{proc}$)： 每读完一个记录后，CPU 需花费 5ms 处理。
• 磁盘在 CPU 处理记录时不会停止旋转。如果在处理完毕后，磁头已经错过了下一个逻辑记录的开头，就必须等待磁盘再转一圈才能读取。

原理解析与计算过程

（1）处理完 13 个记录的总时间（未优化）

1. 分析单次循环： 读取 $R_1$ 需要 $30/13$ ms。读取结束后，磁头位于第 2 块的开头。此时 CPU 开始处理 $R_1$，耗时 $5$ ms。 在这 $5$ ms 内，磁盘转过了 $5 \div (30/13) = 65/30 = 2.16$ 块。 也就是说，当 CPU 处理完 $R_1$ 时，磁头已经越过了第 2 块、第 3 块，正处于第 4 块的上方。 此时 CPU 想要读取连续存放的 $R_2$（位于第 2 块），必须等待磁盘继续旋转，直到第 2 块的开头再次来到磁头下方。
2. 计算等待时间 ($t_{wait}$)： 从读取 $R_1$ 结束 到 再次遇到 $R_2$ 开头，磁盘正好需要转动一整圈（30ms）。 因为 CPU 处理耗去了 5ms，所以额外需要等待的时间为 $30 - 5 = 25$ ms。
3. 计算总时间： 对于前 12 个记录，每个记录的周期 = 读取 + 处理 + 等待 = $30/13 + 5 + 25 = \frac{420}{13}$ ms。 对于最后 1 个记录（$R_{13}$），读完并处理完即结束，不需要再等待。耗时 = $30/13 + 5 = \frac{95}{13}$ ms。 总时间 = $12 \times (\frac{420}{13}) + \frac{95}{13} = \frac{5135}{13} \approx 395$ ms。

（2）重新排列记录以缩短处理时间

优化逻辑： 为了消除高达 25ms 的无谓等待时间，我们应该把 $R_2$ 放在 CPU 刚好处理完 $R_1$ 时磁头所到达的那个物理块上。 根据刚才的分析，CPU 处理耗时 5ms，相当于转过了 2.16 块。 从第 1 块读完（处于第 2 块开头）算起，转过 2.16 块后，磁头位于第 4 块内部。因此，下一个能从头开始完整读取的物理块是第 5 块。 这就意味着，物理块的间隔应为 4（即 1, 1+4=5, 5+4=9...）。

1. 最优排列方式（按物理块1~13列出记录）：$R_1, R_{11}, R_8, R_5, R_2, R_{12}, R_9, R_6, R_3, R_{13}, R_{10}, R_7, R_4$

2. 优化后的总时间计算： 从 $R_1$ 的开头 到 $R_2$ 的开头（间隔 4 块），磁盘转动的时间是固定的：$4 \times (30/13) = \frac{120}{13}$ ms。 前 12 个记录，每次读取间隔精确为 $\frac{120}{13}$ ms。 最后一个记录 $R_{13}$ 只需读取并处理，耗时 $\frac{30}{13} + 5 = \frac{95}{13}$ ms。 优化后的总时间 = $12 \times (\frac{120}{13}) + \frac{95}{13} = \frac{1535}{13} \approx \mathbf{118.08}$ ms。

常见易错点 (Common Pitfalls)

在计算优化后的总时间时，学生容易错误地直接把"等待时间归零"来计算单步时间。实际上，由于处理时间 (5ms) 并没有刚好踩准物理块的边界，磁头到达第 5 块之前依然有非常短暂的等待对齐时间（本题为 $25/13$ ms）。最稳妥的计算方式是直接看两个记录开头之间的物理距离（4 块的旋转时间 $= 120/13$ ms）。