Tanenbaum 现代操作系统 4e 习题及解答

本文最后更新于 2025年9月19日 星期五 10:48

Tanenbaum AS, Bos H. 现代操作系统（第 4 版）. 机械工业出版社, 2017.

第 1 章：引论

1.1. 操作系统的两大主要作用是什么？

（1）操作系统必须为用户提供扩展机器；

（2）并且必须管理 I/O 设备和其他系统资源。

1.3. 分时系统和多道程序系统的区别是什么？

在分时系统中，多个用户可以同时通过各自的终端访问和执行计算。

多道程序系统允许用户同时运行多个程序。

所有的分时系统都是多道程序系统，但并非所有的多道程序系统都是分时系统，因为多道程序系统可能只在一台有单个用户的个人电脑上运行。

1.10. 内核态和用户态有哪些区别？解释在设计操作系统时存在两种不同的模式有什么帮助。

在内核态下，CPU 可以执行其指令集中的所有指令，并使用硬件的所有功能。

在用户态下，它只能执行部分指令，并使用部分功能。

拥有两种模式使设计者能够在用户模式下运行用户程序，从而禁止它们访问关键指令。

1.13. 考虑有两个 CPU 系统，并且每一个 CPU 有两个线程(超线程)。假设有三个程序 P0、P1、P2，分别以运行时间 5 ms、10 ms、20 ms 开始。运行这些程序需要多少时间？假设这三个程序都是 100% 限于 CPU，在运行时无阻塞，并且一旦设定就不改变 CPU。

这些程序的执行时间可能为 20 ms、25 ms 或 30 ms，具体取决于操作系统如何调度它们。

如果 P0 和 P1 被调度到同一个 CPU 上，而 P2 被调度到另一个 CPU 上，将花费 20 ms。

如果 P0 和 P2 被调度到同一个 CPU 上，而 P1 被调度到另一个 CPU 上，将花费 25 ms。

如果 P1 和 P2 被调度到同一个 CPU 上，而 P0 被调度到另一个 CPU 上，将花费 30 ms。

如果三个程序都在同一个 CPU 上运行，将花费 35 ms。

1.15. 假设一个计算机系统有高速缓存、内存(RAM)以及磁盘，操作系统用虚拟内存。读取缓存中的一个字需要 1 ns，RAM 需要 10 ns，磁盘需要 10 ms。如果缓存的命中率是 95%，内存的是 99%（缓存失效时），读取一个字的平均时间是多少？

平均时间 =

0.95 × 1 ns（数据在缓存中）

\(+\) 0.05 × 0.99 × 10 ns（数据在 RAM 中，但不在缓存中）

\(+\) 0.05 × 0.01 × 10000000 ns（数据仅在磁盘上）

= 5001.445 ns

= 5.001445 μs

1.17. 什么是陷阱指令？在操作系统中解释它的用途。

陷阱指令将 CPU 的执行模式从用户模式切换到内核模式。该指令允许用户程序调用操作系统内核中的功能。

1.18. 在分时系统中为什么需要进程表？在只有一个进程存在的个人计算机系统中，该进程控制整个机器直到进程结束，这种机器也需要进程表吗？

进程表用于存储当前被挂起的进程状态，无论是就绪状态还是阻塞状态。现代个人计算机系统即使在用户没有进行操作且没有打开任何程序时，也会有几十个进程在运行。它们在检查更新、加载邮件以及执行其他任务。在 UNIX 系统上，可以使用 ps -a 命令查看这些进程；在 Windows 系统上，可以使用任务管理器查看。

1.23. 有一个文件，其文件描述是 fd，内含下列字节序列：3，1，4，1，5，9，2，6，5，3，5。有如下的系统调用：

1
2
lseek(fd, 3, SEEK_SET);
read(fd, &buffer, 4);

其中 lseek 寻找文件中的字节 3。在读操作完成之后，buffer 中的内容是什么？

1、5、9、2。

1.28. 对程序员而言，系统调用就像对其他库过程调用一样。有无必要让程序员了解哪一个库过程导致了系统调用？在什么情形下，为什么？

就程序逻辑而言，调用库程序是否导致系统调用并不重要。但如果涉及性能问题，如果任务可以在不进行系统调用的情况下完成，程序运行速度会更快。每次系统调用都会产生切换用户上下文到内核上下文的开销时间。此外，在多用户系统上，操作系统在系统调用完成时可能会调度另一个进程运行，进一步减慢调用进程的实时进度。

1.31. 请解释在建立基于微内核的操作系统时策略与机制的分离带来的好处。

策略与机制的分离使操作系统设计者能够在内核中实现少量基本的原语。这些原语得以简化，因为它们不依赖于任何特定的策略。随后，这些原语可以用于在用户层实现更复杂的机制和策略。

第 2 章：进程与线程

2.1. 图 2-2 中给出了三个进程状态。理论上，三个状态之间可以有六种转换，每个状态两个。但图中只给出了四种转换。其余两种转换是否可能发生？

图 2-2

从阻塞状态到运行状态的转换是可以想象的。假设一个进程因为 I/O 操作而处于阻塞状态，当 I/O 操作完成时，如果 CPU 处于空闲状态，该进程可以直接从阻塞状态转换到运行状态。而另一个缺失的转换，即从就绪状态到阻塞状态，则是不可能的。处于就绪状态的进程不能执行 I/O 操作或任何可能阻塞它的操作，只有正在运行的进程才可能被阻塞。

2.5. 一个计算系统的内存有足够的空间容纳 5 个程序。这些程序有一半的时间处于等待 I/O 的空闲状态。请问 CPU 时间浪费的比例是多少？

所有五个进程都空闲的概率是 1/32，因此 CPU 的空闲时间占比是 1/32。

2.6. 一个计算机的 RAM 有 4 GB，其中操作系统占 512 MB。所有进程都占 256 MB (为了简化计算)并且特征相同。要使 CPU 利用率达到 99%，最大 I/O 等待是多少？

内存中有足够的空间容纳 (4096-512) / 256 = 14 个进程。如果某个进程的 I/O 等待概率为 \(p\)，那么所有进程都在等待 I/O 的概率为 \(p^{14}\)。通过将其等于 0.01，我们得到方程 \(p^{14}= 0.01\)。解此方程，我们得到 \(p = 0.72\)，因此我们可以容忍 I/O 等待高达 72% 的进程。

2.7. 如果多个作业能够并行运行，会比它们顺序执行完成得快。假设有两个作业同时开始执行，每个需要 20 分钟 CPU 时间。如果顺序执行，那么完成最后一个作业需要多长时间？如果并行执行又需要多长时间？假设 I/O 等待占 50%。

如果每个作业有 50% 的 I/O 等待时间，那么在没有竞争的情况下完成一个作业需要 40 分钟。如果顺序运行，第二个作业将在第一个作业开始后 80 分钟完成。对于两个作业，CPU 利用率约为 \(1 - 0.5^2 = 0.75\)。因此，每个作业每分钟获得 0.375 的 CPU 时间。为了累计 20 分钟的 CPU 时间，一个作业必须运行 \(20/0.375\approx53.33\) 分钟。因此，顺序运行时作业在 80 分钟后完成，而并行运行时作业在 53.33 分钟后完成。

2.11. 当一个多线程进程创建子进程时，如果子进程复制父进程的所有线程，就会出现问题：假如父进程中有一个线程正在等待键盘输入，现在就有两个线程在等待键盘输入，父进程和子进程各有一个。这种问题在单线程进程中也会发生吗？

不。如果一个单线程进程在等待键盘输入时被阻塞，它无法创建子进程。

2.14. 既然计算机中只有一套寄存器，为什么图 2-12 中的寄存器集合是按每个线程列出而不是按每个进程列出？

图 2-12

当一个线程停止时，它的寄存器中存有值。这些值必须保存，就像进程停止时一样，寄存器的值也必须保存。多线程编程与多进程编程没有区别，因此每个线程都需要有自己单独的寄存器保存区。

2.15. 在没有时钟中断的系统中，一个线程放弃 CPU 后可能再也不会获得 CPU 资源，那么为什么线程还要通过调用 thread_ yield 自愿放弃 CPU？

同一进程中的线程是协作的，它们彼此之间并不敌对。如果为了应用程序的整体利益需要让出执行权，线程会进行让步。毕竟，通常是同一个程序员为所有线程编写代码。

2.16. 线程可以被时钟中断抢占吗？如果可以，在什么情形下可以？如果不可以，为什么不可以？

用户级线程不能被时钟抢占，除非整个进程的时间片已经用完（尽管透明的时钟中断可以发生）。而内核级线程可以单独被抢占。在后者的情况下，如果某个线程运行时间过长，时钟会中断当前进程，从而中断当前线程。内核可以自由选择同一进程中的另一个线程继续运行，如果它愿意的话。

2.18. 在用户态实现线程的最大优点是什么？最大缺点是什么？

最大的优势是效率高。切换线程时不需要陷入内核。

最大的缺点是如果一个线程被阻塞，整个进程都会被阻塞。

2.36. 一个快餐店有四类雇员：(1)领班，接收顾客点的菜单；(2)厨师，准备饭菜；(3) 打包员，将饭菜装在袋子里；(4)收银员，将食品袋交给顾客并收钱。每个雇员可被看作一个可以进行通信的串行进程，那么进程间通信模型是什么？请将这个模型与 UNIX 中的进程联系起来。

员工们通过传递消息进行交流：在这个例子中是订单、食物和袋子。用 UNIX 术语来说，四个进程通过管道连接。

2.39. 考虑以下 C 代码：

1
2
3
4
5
void main() {
  fork();
  fork();
  exit();
}

程序执行时创建了多少子进程？

创建了三个进程。最初的进程执行 fork 后，有两个进程在运行，一个是父进程，一个是子进程。然后它们每个进程再执行一次 fork，创建了两个额外的进程。最后，所有进程退出。

2.42. 请说明在 Round-robin 调度算法中时间片长度和上下文切换时间是怎样相互影响的。

如果上下文切换时间较长，那么时间片的值也必须相应地增大。否则，上下文切换的开销会非常高。如果选择过大的时间片值，而典型的 CPU 突发时间小于时间片，则可能导致系统效率低下。如果上下文切换时间非常小或可以忽略不计，那么可以更自由地选择时间片值。

2.43. 对某系统进行监测后发现，在阻塞 I/O 之前，平均每个进程的运行时间为 \(T\)。一次进程切换需要的时间为 \(S\)，这里 \(S\) 实际上就是开销。对于采用时间片长度为 \(Q\) 的轮转调度，请给出以下各种情况的 CPU 利用率的计算公式：

  1. \(Q = \infty\)

  2. \(Q T\)

  3. \(S < Q < T\)

  4. \(Q = S\)

  5. \(Q\) 趋近于 0

CPU 效率是有用的 CPU 时间除以总的 CPU 时间。

(a)(b)当 \(Q\geq T\) 时，基本周期是进程运行 \(T\) 时间，然后进行一次进程切换要 \(S\) 时间。因此，(a) 和 (b) 的效率为 \(T/(S + T)\)。

(c)当时间片小于 \(T\) 时，每次运行 \(T\) 时间需要进程切换 \(T/Q\) 时间，浪费的时间为 \(ST/Q\)。因此，此时的效率为 \(\frac{T}{T + ST /Q}\)，可以简化为 \(Q/(Q + S)\)。

(d)我们将 \(Q\) 代入 \(S\)，发现效率为 50%。

(e)当 \(Q\to0\) 时，效率趋向于 0。

2.44. 有 5 个待运行作业，估计它们的运行时间分别是 9、6、3、5 和 \(X\)。以何种次序运行这些作业能得到最短的平均响应时间？(答案将依赖于 \(X\))

最短作业优先是最小化平均响应时间的方式。

当 0 < \(X\) ≤ 3 时：\(X\), 3, 5, 6, 9

当 3 < \(X\) ≤ 5 时：3, \(X\), 5, 6, 9

当 5 < \(X\) ≤ 6 时：3, 5, \(X\), 6, 9

当 6 < \(X\) ≤ 9 时：3, 5, 6, \(X\), 9

当 \(X\) 9 时：3, 5, 6, 9, \(X\)

2.45. 有 5 个批处理作业 A~E，它们几乎同时到达一个计算中心。估计它们的运行时间分别为 10、6、2、4 和 8 分钟。其优先级(由外部设定)分别为 3、5、2、1 和 4，其中 5 为最高优先级。对于下列每种调度算法，计算其平均进程周转时间，可忽略进程切换的开销。

(a)轮转法

(b)优先级调度

(c)先来先服务(按照 10、6、2、4、8 次序运行)

(d)最短作业优先

对于(a)，假设系统具有多道程序处理能力，每个作业均公平共享 CPU 时间；对于(b)~(d)，假设任一时刻只有一个作业运行，直到结束所有的作业都是 CPU 密集型作业。

(a)轮转法在最初的 10 分钟内，每个作业获得 1/5 的 CPU 时间。10 分钟后，C 完成。在接下来的 8 分钟内，每个作业获得 1/4 的 CPU 时间，随后 D 完成。接着，剩下的三个作业在接下来的 6 分钟内各获得 1/3 的 CPU 时间，直到 B 完成，以此类推。五个作业的完成时间分别是 10、18、24、28 和 30 分钟，平均完成时间为 22 分钟。

(b)优先级调度，B 首先运行。6 分钟后它完成。其他作业的完成时间分别是 14、24、26 和 30 分钟，平均完成时间为 20 分钟。

(c)如果作业按 A 到 E 的顺序运行，它们的完成时间分别为 10、16、18、22 和 30 分钟，平均完成时间为 19.2 分钟。

(d)最短作业优先的完成时间分别是 2、6、12、20 和 30 分钟，平均完成时间为 14 分钟。

2.47. 一个实时系统有 2 个周期为 5 ms 的电话任务，每次任务的 CPU 时间是 1 ms；还有 1 个周期为 33 ms 的视频流，每次任务的 CPU 时间是 11 ms。这个系统是可调度的吗？

每个语音通话需要 1000/5 = 200 个 1 毫秒的样本，或 200 毫秒的时间。语音通话共占用 400 毫秒的 CPU 时间。视频每秒需要 \(33\frac13\) 次，每次 11 毫秒，总计大约 333 毫秒。总和为每秒 733 毫秒的实际时间，因此系统是可调度的。

2.49. 用 \(a = 1/2\) 的老化算法来预测运行时间。先前的四次运行，从最老的到最近一个，其运行时间分别是 40 ms、20 ms、40 ms 和 15 ms。那么下一次的预测时间是多少？

初始预测（假设初始预测为最老的时间）：\(T = 40\)

更新预测（使用最近一次时间）：

  • 计算第一次更新：\(T_1=\frac{1}{2}\times20+\left(1-\frac{1}{2}\right)\times40 = 30\)

  • 计算第二次更新：\(T_2=\frac{1}{2}\times40+\left(1-\frac{1}{2}\right)\times30 = 35\)

  • 计算第三次更新：\(T_3=\frac{1}{2}\times15+\left(1-\frac{1}{2}\right)\times35 = 25\)

预测的序列为 40、30、35，下一次是 25。

2.50. 一个软实时系统有 4 个周期时间，其周期分别为 50 ms、100 ms、200 ms 和 250 ms。 假设这 4 个事件分别需要 35 ms、20 ms、10 ms 和 \(x\) ms 的 CPU 时间。保持系统可调度的最大 \(x\) 值是多少？

CPU 的使用比例为 \(35/50 + 20/100 + 10/200 + x/250\)。要使其可调度，总和必须小于 1。因此，\(x\) 必须小于 12.5 毫秒。

2.52. 一个实时系统需要处理两个语音通信，每个通信都是 6 ms 运行一次，每次占用 1 ms CPU 时间，加上 25 帧/秒的一个视频，每一帧需要 20 ms 的 CPU 时间。这个系统是可调度的吗？

每个语音通话每秒运行 1000/6 = 166.67 次，每次使用 1 毫秒，因此每个语音通话每秒需要 166.67 毫秒，两者合计为 333.33 毫秒。视频每秒运行 25 次，每次使用 20 毫秒，总共占用 500 毫秒每秒。它们合计每秒消耗 333.33 + 500 = 833.33 毫秒，因此还有剩余时间，系统是可调度的。

2.54. 在哲学家就餐问题的解法(图 2-47)中，为什么在过程 take_forks 中将状态变量置为 HUNGRY？

图 2-47

如果一个哲学家阻塞了，邻居可以通过检查他的状态来看到她是否饥饿，因此当餐叉可用时，可以唤醒她。

2.55. 考虑图 2-47 中的过程 put_forks，假设变量 state[i] 在对 test 的两次调用之后(而不是之前)才被置为 THINKING，这会对解法有什么影响？

这种改变意味着，在一个哲学家停止进食后，他的邻居都无法被选择为下一个进食者。事实上，他们永远不会被选择。假设哲学家 2 吃完了，他会对哲学家 1 和 3 进行测试，但即使他们都饥饿并且餐叉可用，他们也不会被唤醒。同样地，如果哲学家 4 吃完了，哲学家 3 也不会被唤醒。没有任何东西能唤醒他。

第 3 章：内存管理

3.3. 交换系统通过“紧缩”来消除空闲区。假设有很多空闲区和数据段随机分布，并且读或写 32 位长的字需要 4 ns 的时间，“紧缩” 4 GB 的空间大概需要多长时间？为了简单起见，假设字节 0 在空闲区中，内存中最高地址处含有有效数据。

几乎整个内存都需要复制，这要求每个字都要读取并重新写入到不同的位置。读取 4 字节需要 4 纳秒，因此读取 1 字节需要 1 纳秒，写入 1 字节需要 1 纳秒，总共每个字节的整理时间为 2 纳秒，这个速率为 \(5\times10^8\) 字节/秒。要复制 4 GB（\(2^{32}\) 字节，大约是 \(4.295\times10^9\) 字节），计算机需要 \(\frac{2^{32}}{5\times10^8}\) 秒，大约是 8.59 秒。

这个数字稍微悲观一些，因为如果内存底部的初始空洞为 \(k\) 字节，这些字节就不需要复制。然而，如果有许多空洞和许多数据段，空洞将很小，因此 \(k\) 也会很小，计算中的误差也会很小。

3.4. 在一个交换系统中，按内存地址排列的空闲区大小是 10 MB、4 MB、20 MB、18 MB、7 MB、9 MB、12 MB 和 15 MB。对于连续的段请求：

  1. 12 MB

  2. 10 MB

  3. 9 MB

使用首次适配算法，将找出哪个空闲区？使用最佳适配、最差适配、下次适配算法呢？

首次适配算法选择 20 MB、10 MB 和 18 MB。

最佳适配算法选择 12 MB、10 MB 和 9 MB。

最差适配算法选择 20 MB、18 MB 和 15 MB。

下次适配算法选择 20 MB、18 MB 和 9 MB。

3.5. 物理地址和虚拟地址有什么区别？

实际内存使用物理地址。这些是内存芯片在总线上响应的数字。

虚拟地址是指向进程地址空间的逻辑地址。因此，一个 32 位字的机器可以生成高达 4 GB 的虚拟地址，而不管机器的内存是否大于或小于 4 GB。

3.6. 对下面的每个十进制虚拟地址，分别使用 4 KB 页面和 8 KB 页面计算虚拟页号和偏移量：20000，32768，60000。

（1）对于 4 KB 页面大小，

20000：页号 \(P=\lfloor\frac{20000}{4096}\rfloor=4\)，偏移量 \(d=20000\mod 4096=3616\)

32768：页号 \(P=\lfloor\frac{32768}{4096}\rfloor=8\)，偏移量 \(d=32768\mod 4096=0\)

60000：页号 \(P=\lfloor\frac{60000}{4096}\rfloor=14\)，偏移量 \(d=60000\mod 4096=2656\)

所以，（页号，偏移量）为(4, 3616)、(8, 0)和(14, 2656)。

（2）对于 8 KB 页面大小，

20000：页号 \(P=\lfloor\frac{20000}{8192}\rfloor=2\)，偏移量 \(d=20000\mod 8192=3616\)

32768：页号 \(P=\lfloor\frac{32768}{8192}\rfloor=4\)，偏移量移 \(d=32768\mod 8192=0\)

60000：页号 \(P=\lfloor\frac{60000}{8192}\rfloor=7\)，偏移量 \(d=60000\mod 8192=2656\)

所以，（页号，偏移量）为(2, 3616)、(4, 0)和(7, 2656)。

3.7. 使用图 3-9 的页表，给出下面每个虚拟地址对应的物理地址：

  1. 20

  2. 4100

  3. 8300

图 3-9

  1. 页号 \(P=\lfloor\frac{20}{4096}\rfloor=0\)，偏移量 \(d=20\mod 4096=20\)。查页表，由页号 0，得块号为 2，物理地址=2×4096+20=8212。

  2. 页号 \(P=\lfloor\frac{4100}{4096}\rfloor=1\)，偏移量 \(d=4100\mod 4096=4\)。查页表，由页号 1，得块号为 1，物理地址=1×4096+4=4100。

  3. 页号 \(P=\lfloor\frac{8300}{4096}\rfloor=2\)，偏移量 \(d=8300\mod 4096=108\)。查页表，由页号 2，得块号为 6，物理地址=6×4096+108=24684。

3.9. 为了让分页虚拟内存工作，需要怎样的硬件支持？

需要有一个内存管理单元（MMU）来将虚拟页面重新映射到物理页面。此外，当引用一个当前未映射的页面时，需要触发一个陷阱到操作系统，以便操作系统能够获取该页面。

3.14. 一个机器有 32 位地址空间和 8 KB 页面，页表全在硬件中，页表的每一表项为一个 32 位字。进程启动时，以每个字 100 ns 的速度将页表从内存复制到硬件中。如果每个进程运行 100 ms(包含装入页表的时间)，用来装入页表的 CPU 时间的比例是多少？

页表包含 \(2^{32}/2^{13}=524288\) 项。加载页表需要 \(\rm524288\times100\ ns\approx52.4\ ms\)。如果进程获得 100 ms 的运行时间，则其中 52.4 ms 用于加载页表，47.6 ms 用于运行。因此，52.4% 的时间花费在加载页表上。

3.17. 假设一个机器有 38 位的虚拟地址和 32 位的物理地址。

(a)与一级页表比较，多级页表的主要优点是什么？

(b)若采用二级页表，页面大小为 16 KB，每个页表项为 4 字节，应该对第一级页表域分配多少位？对第二级页表域分配多少位？请解释原因。

  1. 多级页表通过其层次结构减少了需要驻留在内存中的页表实际页数。实际上，对于一个具有大量指令和数据局部性的程序，我们只需要顶级页表（一个页面）、一个指令页和一个数据页。

  2. 为三个页字段中的每一个分配 12 位。偏移字段需要 14 位来寻址 16 KB。这使得剩余的 24 位可以用于页字段。由于每个条目占用 4 字节，因此一页可以容纳 \(2^{12}\) 个页表条目，因此需要 12 位来索引一页。因此，为每个页字段分配 12 位可以寻址全部 \(2^{38}\) 字节。

3.20. 一个计算机使用 32 位的虚拟地址，4 KB 大小的页面。程序和数据都位于最低的页面(0~4095)，栈位于最高的页面。如果使用传统(一级)分页，页表中需要多少个表项？如果使用两级分页，每部分有 10 位，需要多少个页表项？

对于传统(一级)分页，所需的页数为 \(2^{32}/2^{12}=2^{20}\)，每个页面需要一个表项，因此，页表必须有 \(2^{20}\) 个表项。

对于两级分页，主页表有 \(2^{10}\) 项，每项指向第二级页表。实际上只用了两个。因此，总共只需要三个页表项，一个在顶级表中，两个在二级表中。

3.22. 一台计算机的进程在其地址空间有 1024 个页面，页表保存在内存中。从页表中读取一个字的开销是 5 ns。为了减小开销，该计算机使用了 TLB，它有 32 个(虚拟页面，物理页框)对，能在 1 ns 内完成查找。请问把平均开销降到 2 ns 需要的命中率是多少？

由 \(h+(5+1)(1-h)=2\)，其中 \(h\) 是命中率，得到 \(h = 0.8\)。所以，把平均开销降到 2 ns 需要的命中率是 0.8。

3.24. 一台机器有 48 位虚拟地址和 32 位物理地址，页面大小是 8 KB，如果采用一级线性页表，页表中需要多少个表项？

使用 8 KB 页和 48 位虚拟地址空间，虚拟页的数量为 \(2^{48}/2^{13}=2^{35}\) 页（大约 340 亿页）。

3.30. 一台小计算机有 4 个页框。在第一个时钟周期时 R 位是 0111 (页面 0 是 0, 其他页面是 1)，在随后的时钟周期中这个值是 1011、1010、1101、0010、1010、1100、0001。如果使用带有 8 位计数器的老化算法，给出最后一个时钟周期后 4 个计数器的值。

计数器为：

页 0: 01101110

页 1: 01001001

页 2: 00110111

页 3: 10001011

3.35. 从平均寻道时间 10 ms、旋转延迟时间 10 ms、每磁道 32 KB 的磁盘上载入一个 64 KB 的程序，对于下列页面大小分别需要多少时间？

  1. 页面大小为 2 KB

  2. 页面大小为 4 KB

假设页面随机地分布在磁盘上，柱面的数目非常大，以至于两个页面在同一个柱面的概率可以忽略不计。

寻道加上旋转延迟为 10+10=20 ms。

对于 2 KB 页，传输时间约为 \(\rm\frac{2}{32}\times20\ ms=1.25\ ms\)，总时间约为 \(\rm20\ ms+1.25\ ms=21.25\ ms\)。加载 64/2=32 个这样的页面大约需要 \(\rm32\times21.25\ ms=680\ ms\)。

对于 4 KB 页，传输时间加倍到 2.5 ms，因此每个页面的总时间为 \(\rm20\ ms+2.5\ ms=22.5\ ms\)。加载 16 个这样的页面需要大约 \(\rm16\times22.5\ ms=360\ ms\)。由于磁盘非常快，减少传输次数（或将页面连续放在磁盘上）至关重要。

3.36. 一个计算机有 4 个页框，载入时间、最近一次访问时间和每个页的 R 位和 M 位如下所示(时事间以一个时钟周期为单位)：

页面 载入时间 最近一次访问时间 R M
0 126 280 1 0
1 230 265 0 1
2 140 270 0 0
3 110 285 1 1
  1. NRU 算法将置换哪个页面？
  2. FIFO 算法将置换哪个页面？
  3. LRU 算法将置换哪个页面？
  4. 第二次机会算法将置换哪个页面？

(a)NRU 算法将置换页 2。 (b)FIFO 算法将置换页 3。 (c)LRU 算法将置换页 1。 (d)第二次机会算法将置换页 2。

3.38. 有二维数组：

1
int X[64][64];

假设系统中有 4 个页框，每个页框大小为 128 个字(一个整数占用一个字)。处理数组 X 的程序正好可以放在一页中，而且总是占用 0 号页。数据会在其他 3 个页框中被换入或换出。数组 X 为按行存储(即，在内存中，X[0][0] 之后是 X[0][1])。下面两段代码中，哪一个会有最少的缺页中断？请解释原因，并计算缺页中断的总数。

A 段

1
2
3
for (int j = 0; j < 64; j++)
  for (int i = 0; i < 64; i++)
    X[i][j]=0;

B 段

1
2
3
for (int i = 0; i < 64; i++)
  for (int j = 0; j < 64; j++)
    X[i][j] = 0;

B 段，因为该代码具有比 A 段更好的空间局部性。

A 段由于一个页框为 128 个字，而数组 X 的一行占据半页（即 64 个字），整个数组需要 \(64\times32/128=16\) 个页框。A 段的内层循环在给定列的情况下按行顺序访问 X，因此对 X[i][j] 的每隔一次访问都会引发页错误。页错误的总次数将为 \(64\times64/2=2048\)。

B 段内层循环导致外层循环的每次迭代只发生一次页错误（总共 32 次页错误）。

3.41. 一台计算机为每个进程提供 65536 字节的地址空间，这个地址空间被划分为多个 4 KB 的页面。一个特定的程序有 32768 字节的正文、16386 字节的数据和 15870 字节的堆栈。这个程序能装入这个机器的地址空间吗？如果页面大小是 512 字节，能放得下吗？记住，一个页面不能同时包含两个或者更多的不同种类段，例如，一页里不能同时有代码段和数据段。

4 KB 页面：32768/4096=8，16386/4096=4.0005，15870/4096=3.87。 文本占 8 页，数据占 5 页，栈占 4 页。需要 8+5+4=17 个 4096 字节的页面，17×4096=6963265536，放不下。

512 B 页面：32768/512=64，16386/512=32.004，15870/512=30.996。 而使用 512 字节的页面时，文本占 64 页，数据占 33 页，栈占 31 页，总共需要 64+33+31=128 个 512 字节的页面，128×512=65536，刚好放得下。

3.47. 一个程序中有两个段，段 0 中为指令，段 1 中为读/写数据。段 0 有读/执行保护，段 1 有读/写保护。内存是按需分页式虚拟内存系统，它的虚拟地址为 4 位页号，10 位偏移量。页表和保护如下所示(表中的数字均为十进制)：

3.47

对于下面的每种情形，给出动态地址所对应的实(实际)内存地址，或者指出发生了哪种失效(缺页中断或保护错误)。

  1. 读取页：段 1，页 1，偏移 3；

  2. 存储页：段 0，页 0，偏移 16；

  3. 读取页：段 1，页 4，偏移 28；

  4. 跳转到：段 1，页 3，偏移 32。

  5. 地址 (14, 3)，没有缺页（0xD3 或 1110 0011）

  6. 访问保护错误：对读/执行段写入

  7. 在磁盘，缺页错误

  8. 访问保护错误：跳转到读/写段

3.48. 你能想象在哪些情况下支持虚拟内存是个坏想法吗？不支持虚拟内存能得到什么好处呢？请解释。

当所有应用程序的内存需求都非常明确且可控时，不需要虚拟内存支持。例如智能卡、专用处理器（如网络处理器）和嵌入式处理器。在这些情况下，可以考虑使用更多的物理内存。如果操作系统不需要支持虚拟内存，代码会更简单和更小。然而，虚拟内存的一些概念仍可以在不同设计要求下有效利用，比如程序/线程隔离可以通过闪存分页实现。

第 4 章：文件系统

4.3. 在早期的 UNIX 系统中，可执行文件(a.out 文件)以一个特定的魔数(magic number) 而不是一个随机选取的数字开头。这些文件的开头是 header，随后是文本段和数据段。为什么可执行文件要选取一个特定的数字，而其他类型的文件会多少有些随机地选择魔数开头？

这些系统直接将程序加载到内存中，从字地址 0 开始执行，这个位置是一个魔数。为了避免将文件头误作为代码执行，魔数被设置为一个 BRANCH 指令，其目标地址位于文件头之后。这样就可以直接将二进制文件读取到新进程的地址空间，并在地址 0 处运行，而无需知道文件头的大小。

4.4. 在 UNIX 中 open 系统调用绝对需要吗？如果没有会产生什么结果？

如果没有打开文件（如每次读取时自动打开），则每次读取都需要指定文件名。系统必须获取文件的 i-node，尽管它可以被缓存。一个问题是何时将 i-node 刷新回磁盘，可以通过超时机制处理，虽然不够优雅，但可能可行。

4.6. 某一些操作系统提供系统调用 rename 给文件重命名，同样也可以通过把文件复制到新文件并删除原文件而实现文件重命名。请问这两种方法有何不同？

是的，rename 调用不会改变文件的创建时间或最后修改时间，而创建新文件则会将当前时间设为创建时间和最后修改时间。此外，如果磁盘接近满载，复制操作可能会失败。

4.10. 考虑图 4-8 中的目录树，如果当前工作目录是 /usr/jim，则相对路径名为 ../ast/x 的文件的绝对路径名是什么？

图 4-8

dotdot 组件将搜索路径移动到 /usr，因此 ../ast 放置在 /usr/ast。因此，相对路径名为 ../ast/x 的文件的绝对路径名是 /usr/ast/x。

4.13. 一种在磁盘上连续分配并且可以避免空洞的方案是，每次删除一个文件后就紧缩一下磁盘。由于所有的文件都是连续的，复制文件时需要寻道和旋转延迟以便读取文件，然后全速传送。在写回文件时要做同样的工作。假设寻道时间为 5 ms，旋转延迟为 4 ms，传送速率为 8 MB/s，而文件平均长度是 8 KB，把一个文件读入内存并写回到磁盘上的一个新位置需要多长时间？运用这些数字，计算紧缩 16 GB 磁盘的一半需要多长时间？

开始传输需要 5+4=9 ms。以 8 MB/s 的传输速度读取 8 KB 需要 \(\rm\frac{8}{8×2^{10}}\ s=0.9765625\ ms\)，总共需要 \(\rm9\ ms+0.9765625\ ms=9.9765625\ ms\)，写回文件也需要 9.9765625 ms。因此，复制一个文件需要 \(\rm9.9765625\ ms\times2=19.953125\ ms\)。紧缩一个 16 GB 磁盘的一半需要复制 8 GB 的存储空间，即 \(2^{20}\) 个文件。以每个文件 19.954 ms 的速度，总共需要 \(\rm2^{20}\times19.953125\ ms=20922.368\ s\)，即 5.812 小时。显然，在每次删除文件后立即紧缩磁盘并不是个好主意。

4.14. 基于前一个问题的答案，紧缩磁盘有什么作用吗？

如果方法得当，答案是肯定的。在压缩过程中，应该将每个文件的所有块组织为连续的块，以实现快速访问。Windows 有一个程序可以对磁盘进行碎片整理和重组，鼓励用户定期运行以提高系统性能。由于碎片整理需要较长时间，每月运行一次可能是一个合适的频率。

4.16. 考虑类似图 4-13 中的节点。如果它含有用 4 个字节表示的 10 个直接地址，而且所有的磁盘块大小是 1024 KB，那么文件最大可能有多大？

图 4-13

间接块可以存储 \(\frac{1024\times2^{10}}{4}=262144\) 个磁盘地址。加上 10 个直接磁盘地址，最大文件可以有 262154 个块。由于每个块为 1024 KB=1 MB，最大文件大小为 262154 MB。

4.24. 空闲磁盘空间可用空闲块表或位图来跟踪。假设磁盘地址需要 \(D\) 位，一个磁盘有 \(B\) 个块，其中有 \(F\) 个空闲。在什么条件下，空闲块表采用的空间少于位图？设 \(D\) 为 16 位，请计算空闲磁盘空间的百分比。

位图需要 \(B\) 位。空闲列表需要 \(DF\) 位。如果 \(DF < B\)，则空闲列表需要的位数更少。换句话说，如果 \(\frac{F}{B}<\frac{1}{D}\)，即空闲块的比率小于一个常数，则空闲列表更短。对于 16 位的磁盘地址，如果磁盘空闲部分小于 1/16=6.25%，空闲列表会更短。

4.32. 文件系统的性能与高速缓存的命中率有很大的关系(即在高速缓存中找到所需块的概率)。从高速缓存中读取数据需要 1 ms，而从磁盘上读取需要 40 ms，若命中率为 \(h\)，给出读取数据所需平均时间的计算公式。

所需平均时间为 \(h+(40+1)(1-h)=41-40h\)。这个函数是一个直线。

4.36. 考虑图 4-21 背后的思想，目前磁盘平均寻道时间为 8 ms，旋转速率为 15000 rpm，每道为 262144 字节。对大小各为 1 KB、2 KB 和 4 KB 的磁盘块，传送速率各是多少？

图 4-21

在 15000 rpm 时，磁盘每圈需要 60/15000 s=4 ms。读取 \(k\) 字节的平均访问时间（以 ms 计）为 \(8+4/2+(k/262144)×4\)。

对于 1 KB、2 KB 和 4 KB 的块，访问时间分别为

\(8+4/2+(2^{10}/262144)×4=10.015625\) ms，

\(8+4/2+(2^{11}/262144)×4=10.03125\) ms，

\(8+4/2+(2^{12}/262144)×4=10.0625\) ms（几乎没有差异）。

这些块的传送速率分别为

1 KB/10.015625 ms=0.0998 KB/ms，

2 KB/10.03125 ms=0.1994 KB/ms，

4 KB/10.0625 ms=0.3975 KB/ms。

4.37. 某个文件系统使用 2 KB 的磁盘块，而中间文件大小值为 1 KB。如果所有的文件都是正好 1 KB 大，那么浪费掉的磁盘空间的比例是多少？你认为一个真正的文件系统所浪费的空间比这个数值大还是小？请说明理由。

如果所有文件都是 1 KB，则每个 2 KB 块将包含一个文件并浪费 1 KB 空间。由于文件系统的基本单位是块，而不是半块，因此无法在一个块中存放两个文件，导致 50% 的空间浪费。

实际上，每个文件系统都有大文件和许多小文件，大文件使用磁盘的效率更高。例如，一个 32,769 字节的文件需要 18 个磁盘块来存储，其空间效率为 32,769/(18×2048)=32,769/36,864≈89%。

4.38. 给定磁盘块大小为 4 KB，块指针地址值为 4 字节，使用 10 个直接地址(direct address)和一个间接块(indirect block)可以访问的最大文件大小是多少字节？

间接块可以容纳 1024 个地址。加上 10 个直接地址，总共有 1034 个地址。每个地址指向一个 4 KB 磁盘块，因此最大文件大小为 \(1034×2^{12}=4235264\) 字节。

4.40. 一个 UNIX 系统使用 4 KB 磁盘块和 4 字节磁盘地址。如果每个 i 节点中有 10 个直接表项以及一个一次间接块、一个二次间接块和一个三次间接块，那么文件最大为多大？

i-node 可以容纳 10 个指针。单级间接块可以容纳 1024 个指针。双重间接块可以容纳 \(1024^2\) 个指针。三级间接块可以容纳 \(1024^3\) 个指针。将这些加起来，最大文件大小为 \(10+1024+1024^2+1024^3=1074791434\) 个块，文件最大为 1074791434×4 KB≈4.004 TB。

4.41. 对于文件 /usr/ast/courses/os/handout.t，若要获取其 i 节点需要多少个磁盘操作？假设其根目录的 i 节点在内存中，其他路径都不在内存中。并假设所有的目录都在一个磁盘块中。

所需的磁盘读取如下：

1
2
3
4
5
6
7
8
9
10
/ 的目录
/usr 的 i-node
/usr 目录
/usr/ast 的 i-node
/usr/ast 目录
/usr/ast/courses 的 i-node
/usr/ast/courses 目录
/usr/ast/courses/os 的 i-node
/usr/ast/courses/os 目录
/usr/ast/courses/os/handout.t 的 i-node

总共需要 10 次磁盘读取。

第 5 章：输入/输出

5.6. 假设一个系统使用 DMA 将数据从磁盘控制器传送到内存。进一步假设平均花费 \(t_1\) ns 获得总线，并且花费 \(t_2\) ns 在总线上传送一个字(\(t_1\gg t_2\))。 在 CPU 对 DMA 控制器进行编程之后，如果 (a) 采用一次一字模式，(b) 采用突发模式，从磁盘控制器到内存传送 1000 个字需要多少时间？

  1. 一次一字模式：总时间 \(= 1000\times[(t_1+t_2)+(t_1+t_2)+(t_1+t_2)]\)，其中第一个项为获取总线并将命令发送到磁盘控制器，第二项为传输字，第三项为确认。因此，总共需要 \(3000(t_1+t_2)\) 纳秒。

  2. 突发模式：总时间 = \((t_1+t_2)+t_1+1000\times t_2+(t_1+t_2)\)，其中第一个项为获取总线并将命令发送到磁盘控制器，第二项为磁盘控制器获取总线，第三项为突发传输，第四项为获取总线并进行确认。因此，总共需要 \(3t_1+1002t_2\) 纳秒。

5.8. 假设一台计算机能够在 5 ns 内读或者写一个内存字，并且假设当中断发生时，所有 32 位寄存器连同程序计数器和 PSW 被压入堆栈。该计算机每秒能够处理的中断的最大数目是多少？

中断需要将 34 个字压入栈中。返回时需要从栈中取出 34 个字。仅这个开销就为 \(34\times5+34\times5=340\) 纳秒。因此，最大中断次数为每秒约 2.94 百万次，假设每次中断没有任何工作要做。

5.14. 以下各项工作是在四个 I/O 软件层的哪一层完成的？

(a)为一个磁盘读操作计算磁道、扇区、磁头。

(b)向设备寄存器写命令。

(c)检查用户是否允许使用设备。

(d)将二进制整数转换成 ASCII 码以便打印。

  1. 设备驱动程序

  2. 设备驱动程序

  3. 设备无关软件

  4. 用户级软件

5.16. 为什么打印机的输出文件在打印前通常都假脱机输出在磁盘上？

如果一旦输出出现，打印机就被分配，则一个进程可能会通过打印少量字符然后休眠很长时间来长时间占用打印机。

5.17. 一个 7200 rpm 的磁盘的磁道寻道时间为 1 msec，该磁盘相邻柱面起始位置的偏移角度是多少？磁盘的每个磁道包含 200 个扇区，每个扇区大小为 512 B。

磁盘以 7200 rpm=120 转/秒的速度旋转，因此转 1 圈需要 \(\frac{1}{120}\) s。该磁盘相邻柱面起始位置的偏移是 \(\rm\frac{1\ ms}{\frac{1}{120}\ s}\times200=24\)，偏移角度是 \(\rm\frac{1\ ms}{\frac{1}{120}\ s}\times360^\circ=43.2^\circ\)。

5.18. 一个磁盘的转速为 7200 rpm，一个柱面上有 500 个扇区，每个扇区大小为 512 B。读入一个扇区需要多少时间？

磁盘以 7200 rpm=120 转/秒的速度旋转，因此转 1 圈需要约 1/120 s=8.33 ms，读入一个扇区需要时间约为 8.33 ms/500=16.67 微秒。

5.22. 从读性能、写性能、空间开销以及可靠性方面对 0 级 RAID 到 5 级 RAID 进行比较。

读性能：RAID 级别 0、2、3、4 和 5 允许并行读取来服务一个读取请求，而 RAID 1 还允许同时处理两个读取请求。

写性能：所有 RAID 级别提供相似的写入性能。

空间开销：RAID 0 没有空间开销，RAID 1 的空间开销为 100%。对于 32 位数据字和 6 个校验驱动器，RAID 2 的空间开销约为 18.75%。对于 RAID 3 和 RAID 5，假设有 33 个驱动器，空间开销为 3.13%。

可靠性：RAID 0 没有可靠性支持。其他 RAID 级别可以在一个磁盘故障的情况下生存。RAID 3、4 和 5 可以检测到单个随机位错误，而 RAID 2 可以检测并纠正单个随机位错误。

5.28. 考虑一个包含 16 个磁头和 400 个柱面的磁盘。该磁盘分成 4 个 100 柱面的区域，不同的区域分别包含 160 个、200 个、240 个和 280 个扇区。假设每个扇区包含 512 字节，相邻柱面间的平均寻道时间为 1 ms，并且磁盘转速为 7200 rpm。计算磁盘容量、最优磁道斜进以及最大数据传输率。

  1. 区域 1 容量 = 16×100×160×512=131072000 字节

区域 2 容量 = 16×100×200×512=163840000 字节

区域 3 容量 = 16×100×240×512=196608000 字节

区域 4 容量 = 16×100×280×512=229376000 字节

总和 = 720896000 字节=687.5 MB。

  1. 旋转率为 7200 rpm，即每秒 120 次旋转。

区域 1 的最优磁道斜进为 0.120×160=19.2 扇区，

区域 2 的最优磁道斜进为 0.120×200=24 扇区，

区域 3 的最优磁道斜进为 0.120×240=28.8 扇区，

区域 4 的最优磁道斜进为 0.120×280=33.6 扇区。

因此，最优磁道斜进是 33.6 扇区。

  1. 当读取/写入外部区域（区域 4）的柱面时，最大数据传输率为 280×120×512=17203200 字节/秒。

5.37. 某计算机上的时钟中断处理程序每一时钟滴答需要 2 ms (包括进程切换的开销)，时钟以 60 Hz 的频率运行，那么 CPU 用于时钟处理的时间比例是多少？

0.002×60=0.12=12%，也就是占用 CPU 的 12%。

5.40. 许多 UNIX 版本使用一个 32 位无符号整数作为从时间原点计算的秒数来跟踪时间。这些系统什么时候会溢出(年与月) ？你认为这样的事情会实际发生吗？

一年的平均秒数为 365.25×24×3600=31,557,600 秒。计数器在 1970 年 1 月 1 日后经过 \(2^{32}\) 秒时溢出。\(2^{32}/31,557,600=136.1\) 年，因此溢出将发生在 2106.1 年，也就是 2106 年 2 月初。当然，到那时，所有的计算机至少都会使用 64 位系统，因此这个问题不会出现。

5.41. 一个位图模式的终端包含 1600×1200 个像素。为了滚动一个窗口，CPU(或者控制器)必须向上移动所有的文本行，这是通过将文本行的所有位从视频 RAM 的一部分复制到另一部分实现的。如果一个特殊的窗口高 80 行宽 80 个字符(总共 6400 个字符)，每个字符框宽 8 个像素高 16 像素，那么以每个字节 50 ns 的复制速率滚动整个窗口需要多长时间？如果所有的行都是 80 个字符长，将一个字符显示在屏幕上需要 5 μs，每秒能够显示多少行？

滚动窗口需要复制 79 行，每行 80 个字符，总计 79×80=6320 个字符。复制 1 个字符（16 字节）需要 16×50 ns=800 ns，因此整个窗口的复制时间为 6320×800 ns=5.056 ms。

将 80 个字符写入屏幕需要 \(\rm80\times5\ \mu s=400\ \mu s=0.4\ ms\)，因此滚动并显示新的一行总共需要 5.056+0.4=5.456 ms。这大约相当于每秒 183.28 行。

5.46. 将字符放置在位图模式的屏幕上，一种方法是使用 BitBlt 从一个字体表复制位图。假设一种特殊的字体使用 16×24 像素的字符，并且采用 RGB 真彩色。

  1. 每个字符占用多少字体表空间？

  2. 如果复制一个字节花费 100 ns(包括系统开销),那么到屏幕的输出率是每秒多少个字符？

  3. 每个像素在 RGB 中占用 3 字节，因此表空间为 16×24×3=1152 字节。

  4. 每字节 100 ns，每个字符需要 1152×100 ns=115.2 微秒。这相当于每秒约 \(10^6/115.2=8681\) 字符的输出率。

5.47. 假设复制一个字节花费 10 ns，那么对于 80 字符 × 25 行文本模式的内存映射的屏幕，完全重写屏幕要花费多长时间？采用 24 位彩色的 1024×768 像素的图形屏幕情况怎样？

重写文本屏幕需要复制 80×25=2000 字节，耗时 2000×10 ns=20 微秒。

重写图形屏幕需要复制 1024×768×3=2,359,296 字节，大约需要 2,359,296×10 ns=23.59 ms。

5.53. 如果一个 CPU 的最大电压 \(V\) 被削减到 \(V/n\)，那么它的功率消耗将下降到其原始值的 \(1/n^2\)，并且它的时钟速度下降到其原始值的 \(1/n\)。假设一个用户以每秒 1 个字符的速度键入字符，处理每个字符所需要的 CPU 时间是 100 ms，\(n\) 的最优值是多少？与不削减电压相比，以百分比表示相应的能量节约了多少？假设空闲的 CPU 完全不消耗能量。

如果 \(n = 10\)，CPU 仍然可以按时完成工作，但所用的能量显著减少。如果在全速运行 1 秒时消耗的能量为 \(E\)，那么全速运行 100 毫秒后闲置 900 毫秒将使用 \(E/10\) 的能量。而以 1/10 的速度运行整整 1 秒只会消耗 \(E/100\)，节省了 \(9E/100\)。通过降低电压节约的能量百分比为 90%。

第 6 章：死锁

6.6. 城市街道很容易遇到循环阻塞的情况，我们称之为“僵局”。其中交叉路口被汽车堵塞，这些汽车阻塞了它们后面的汽车，进而又阻塞了试图进入前面路口的车辆。城市街区的所有路口都以一种循环的方式遍布被阻塞的汽车。“僵局”是一个资源死锁和同步竞争的问题。纽约市的预防算法称为“非阻塞盒子”，除非一个交叉路口的后续空间是非阻塞的，否则禁止汽车进入这个交叉路口。这是哪种预防算法？你能否提供其他的预防算法来解决“僵局”问题？

“非阻塞盒子”是一种预分配策略，否定了保持和等待的死锁前提条件，因为我们假设汽车可以进入路口之后的街道空间，从而释放路口。

另一种策略可能允许汽车暂时进入车库，为清除交通堵塞腾出足够的空间。一些城市有交通控制政策来调整交通流量；当城市街道变得更加拥堵时，交通管理员会调整红绿灯的设置，以控制进入高度拥堵区域的交通。较轻的交通确保资源竞争较少，从而降低了发生交通堵塞的概率。

6.14. 考虑系统的如下图状态，有四个进程 P1、P2、P3 和 P4，以及五种类型的资源 RS1、RS2、RS3、RS4 和 RS5。

6.14

使用 6.4.2 节中描述的死锁检测算法来说明该系统中存在一个死锁。并识别在死锁中的进程。

首先，未标记的进程集为 P = (P1 P2 P3 P4)。

R1 不小于或等于 A。

R2 小于 A；标记 P2；此时 A = (0 2 0 3 1)，未标记进程集 P = (P1 P3 P4)。

R1 仍然不小于或等于 A。

R3 等于 A；标记 P3；此时 A = (0 2 0 3 2)，未标记进程集 P = (P1 P4)。

R1 依然不小于或等于 A。

R4 也不小于或等于 A。

因此，进程 P1 和 P4 仍未标记，它们处于死锁状态。

6.15. 解释系统是如何从前面问题的死锁中恢复的，使用：(a)抢占；(b)回滚；(c)终止进程。

(a)通过抢占恢复：在 P2 和 P3 完成后，可以强制 P1 抢占 1 个单位的 RS3。这样将使 A = (0 2 1 3 2)，并允许 P4 完成。一旦 P4 完成并释放其资源，P1 就可以完成。

(b)通过回滚恢复：将 P1 回滚到获取 RS3 之前的检查点状态。

(c)通过终止进程恢复：终止 P1。

6.25. 银行家算法在一个有 \(m\) 个资源类型和 \(n\) 个进程的系统中运行。当 \(m\) 和 \(n\) 都很大时，为检查状态是否安全而进行的操作次数正比于 \(m^an^b\)。\(a\) 和 \(b\) 的值是多少？

将矩阵中的一行与可用资源向量进行比较需要 \(m\) 次操作。为了找到可以完成并标记为完成的进程，这一步必须重复大约 \(n\) 次。因此，标记一个进程为完成需要大约 \(mn\) 步。对所有 \(n\) 个进程重复该算法意味着步骤数是 \(mn^2\)。因此，\(a = 1\)，\(b = 2\)。

6.26. 一个系统有 4 个进程和 5 个可分配资源，当前分配和最大需求如下：

已分配资源 最大需求量 可用资源
进程 A 1 0 2 1 1 3 1 2 1 3 0 0 \(x\) 1 2
进程 B 2 0 1 1 0 2 2 2 1 0
进程 C 1 1 0 1 0 2 1 3 1 0
进程 D 1 1 1 1 0 1 1 2 2 1

若保持该状态是安全状态，\(x\) 的最小值是多少？

需求矩阵如下：

\[\begin{pmatrix}2 & 1 & 0 & 0 & 2 \\ 0 & 2 & 1 & 0 & 0 \\ 1 & 0 & 3 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}\]

如果 \(x\) 是 0，立即发生死锁。

如果 \(x\) 是 1，进程 D 可以运行到完成。当它完成后，可用向量为 1 1 2 2 2。不幸的是，我们现在死锁了。

如果 \(x\) 是 2，进程 D 运行后，可用向量为 1 1 3 2 2，进程 C 可以运行，完成后，可用向量为 2 2 3 3 2，这将允许进程 B 运行并完成，完成后可用向量为 4 2 4 4 2，然后进程 A 运行并完成。

因此，避免死锁的最小 \(x\) 值是 2。

6.28. 两个进程 A 和 B，每个进程都需要数据库中的 3 个记录 1、2、3。如果 A 和 B 都以 1、2、3 的次序请求，将不会发生死锁。但是如果 B 以 3、2、1 的次序请求，那么死锁就有可能会发生。对于这 3 种资源，每个进程共有 3! (即 6)种次序请求，这些组合中有多大的可能可以保证不会发生死锁？

假设进程 A 按顺序请求记录 a、b、c。如果进程 B 也首先请求 a，那么其中一个进程将获得 a，另一个将阻塞。这种情况下不会发生死锁，因为获胜者可以在没有干扰的情况下运行完成。在另外四种组合中，有些可能导致死锁，有些不会。六种情况如下：

a b c 无死锁

a c b 无死锁

b a c 可能死锁

b c a 可能死锁

c a b 可能死锁

c b a 可能死锁

由于六种情况中的四种可能导致死锁，因此避免死锁的概率是 1/3，而发生死锁的概率是 2/3。

6.30. 在一个电子资金转账系统中，有很多相同进程按如下方式工作：每个进程读取一行输入，该输入给出一定数目的款项、贷方账户、借方账户。然后该进程锁定两个账户，传送这笔钱，完成后释放锁。由于很多进程并行运行，所以存在这样的危险：锁定 \(x\) 会无法锁定 \(y\)，因为 \(y\) 已被一个正在等待 \(x\) 的进程锁定。设计一个方案来避免死锁。保证在没有完成事务处理前不要释放该账户记录。(换句话说，在锁定一个账户时，如果发现另一个账户不能被锁定就立即释放这个已锁定的账户。)

为避免环路等待，可对资源（账户）按账户编号进行编号。在读取输入行后，进程首先锁定编号较小的账户，然后在获得锁后（这可能需要等待），再锁定另一个账户。由于没有进程会等待比它已经持有的更低编号的账户，因此永远不会有环路等待，因此也不会有死锁。

6.34. 解释死锁、活锁和饥饿的区别。

死锁发生在一组进程阻塞，等待只有该组中的某些其他进程才能引发的事件时。

活锁中的进程并没有被阻塞。相反，它们继续执行，检查一个永远不会变为真的条件。因此，除了它们持有的资源外，活锁中的进程还继续消耗宝贵的 CPU 时间。

进程饥饿是由于其他进程的存在以及新进程流的到来，这些新进程的优先级比被饥饿的进程高。与死锁或活锁不同，饥饿可以自行终止，例如，当具有更高优先级的现有进程终止并且没有新的高优先级进程到达时。

Computer Science
#读书 #操作系统
Tanenbaum 现代操作系统 4e 习题及解答
https://blog.gtbcamp.cn/article/operating-systems/
作者
Great Thunder Brother
发布于
2024年9月12日
更新于
2025年9月19日
许可协议