现代操作系统
第一章 答案
1. 操作系统必须向用户提供一台扩展(即,实际上)的机器,和它必须管理 I/O 设备和其它系
统资源。
2. 多道程序就是 CPU 在内存中多个进程之间迅速切换。它一般被用来使 CPU 保持忙碌,当
有一个或多个进程进行 I/O 时 。
3. 输入 spooling 是作业中的读入技术,例如,从卡片在磁盘,这样当当前执行的进程完成时,
将等候 CPU。输出 spooling 在 打印之前首先复制打印文件,而非直接打印。在个人计算机
上的输入 spooling 很 少,但是输出 spooling 非 常普遍。
4. 多道程序的主要原因是当等候 I/O 完 成时 CPU 有 事可做。如果没有 DMA,I/O 操 作时
CPU 被完全占有,因此,多道程序无利可图 (至少在 CPU 利 用方面)。无论程序作多少 I/O
操 作,CPU 都是 100%的忙碌。当然,这里假定主要的延迟是数据复制时的等待。如果 I/O 很
慢的话,CPU 可 以做其它工作。
5. 第二代计算机没有必要的硬件保护操作系统免受恶意的用户程序的侵害。
6. 它依然存在。例如,Intel以各种各样的不同的属性包括速度和能力消耗来生产 Pentium I, II, III
和 4。所有这些机器的体系结构都是兼容的,仅仅是价格上的不同,这些都是家族思想的本
质。
7. 25 X 80 字符的单色文本屏幕需要 2000 字节的缓冲器。1024 X 768 象素 24 位颜色的位图需
要 2359296 字节。1980 年代这两种选择将分别地耗费$10 和$11520。而对于当前的价格,将
少于$1/MB。
8. 选择(a),(c),(d)应该被限制在内核模式。
9. 个人的计算机系统总是交互式的,而且经常只有一个用户。而大型机系统几乎总有许多用
户强调批处理或者分时。除了对所有资源的有效使用,大型机系统上的保护更加重要。
10. 从管道中每纳秒出现一条指令。意味着该机器每秒执行十亿条指令。它对于管道有多少个
阶段全然不予理睬。即使是 10-阶段管道,每阶段 1 nsec,也将执行对每秒十亿条指令。因为
无论那种情况,管道末端输出的指令数都是一样的。
11. 原稿包含 80 X 50 X 700 = 2800000 字符。当然,这不可能放入任何目前的 CPU 中,而且
对于 1MB 的 cache 来说也太大了,但是如果可能的话,在寄存器中只需 2.8msec,在 Cache 中
需要 5.8msec。整本书大约有 2700 个 1024 字节的数据块,因此从磁盘扫描大约为 27 秒,从
磁带扫描则需 2 分钟 7 秒。当然,这些时间仅为读取数据的时间。处理和重写数据将增加时
间。
12. 从逻辑上说,边界寄存器使用虚拟地址或者物理地址没有任何关系。然而,前者的性能更
好。如果使用虚拟地址,虚拟地址和基址寄存器的相加,与比较可以同时开始,而且可以
1
并行。如果使用物理地址,相加完成之前是不能进行比较的,这就增加了存取时间。
13. 也许。如果调用者取回控制,并且在最终发生写操作时立即重写数据,将会写入错误的数
据。然而,如果驱动程序在返回之前首先复制将数据复制到一个专用的缓冲器,那么调用者
可以立即继续执行。另一个可能性是允许调用者继续,并且在缓冲器可以再用时给它一个信
号,但是这需要很高的技巧,而且容易出错。
14. 陷井由程序造成的,并且与它同步。如果程序一而再地被运行,陷井将总在指令流中相同
位置的精确发生。而中断则是由外部事件和其时钟造成的,不具有重复性。
15. Base = 40000,Limit = 10000。按照本书中描述的方法 Limit = 50000 是不正确的。这种方
法也是可以执行的,不过这样做将等待 addree + Base 完成后才能开始边界检查,将会使计算
机速度减慢。
16. 进程表是为了存储当前被挂起、甚或是被延迟和阻塞的进程状态。在单一进程的系统中是
不需要,因为单一进程从不挂起。
17. 装配文件系统将使得装配目录中已有的任何文件都不可访问,因此装配点通常都是空的。
然而,系统管理人员可能需要将某些位于被装配目录中的非常重要的文件复制到装配点,使得
他们在进行设备检查或修理时,可以在紧急事件中的普通路径上找到这些文件。
18. 如果进程表中没有空闲的槽(或者没有内存和交换空间),Fork 将失败。如果所给的文件名
不存在,或者不是一个有效的可执行文件,Exec 将失败。如果将要解除链接的文件不存在,或
者调用 Unlink 的 进程没有权限,则 unlink 将失败。
19. 如果 fd 不正确,调用失败,将返回.1.。同样,如果磁盘满,调用也失败,要求写入的字
节数和实际写入的字节数可能不等。在正确终止时,总是返回 nbytes。
20. 包含字节: 1,5,9,2。
21. 块特殊文件包含被编号的块,每一块都可以独立地读取或者写入。而且可以定位于任何块,
并且开始读出或写入。这些对于字符特殊文件是不可能的。
22. 系统调用实际上并没有名称,除了在文件中这样描述之外。当库例程 read 陷入内核时,
它将系统调用号码放入寄存器或者堆栈中。该号码通常用于一张表的索引。这里确实没有使
用任何名称。而另一方面,库例程的名称是十分重要的,因为它将用于程序中。
23. 是的,尤其当系统内核是消息传递系统时。
24. 就程序逻辑而言,库例程调用哪个系统调用是没有关系的。但是,如果需要考虑性能问题,
无需系统调用就可以完成的任务将使程序运行更快。所有的系统调用都会导致用户环境和内
核环境的切换开销。更进一步,在多用户系统中,在系统调用完成之前,操作系统可能调度
到其他的进程,这将使得调用过程的处理更加迟缓。
25. 某些 UNIX 调 用没有相应的 Win32 API:
Link:Win32 程序不能给文件另外一个名称,或者使某个文件出现在多个目录中。同时,
试图创建链接可以便于测试,并且在文件上加锁。
Mount 和 umount:Windows 程序不能创建关于标准的路径的假定命名,因为具有多个
磁盘驱动器的系统上路径名,其驱动器部分是不同的。
2
Chmod:Windows 程序员不得不假定所有的用户都能访问每个文件。
Kill:Windows 程 序员不能 kill 行 为失常的程序。
26. 这些都可以直接转换:
(a) micro year = 106 X 365 X 24 X 3600 = 31.536 sec。(b)
1km。
(c)有 240 字节,也就是 1,099,511,627,776 字节。
(d)它是 6 X 1024 公斤。
3
第二章 答案
1. 从阻塞到运行的转换是可以想象的。假设某个进程在 I/O 上阻塞,而且 I/O 结束,如果此
时 CPU 空闲,该进程就可以从阻塞态直接转到运行态。而另外一种转换(从就绪态到阻塞态)
是不可能的。一个就绪进程是不可能做任何会产生阻塞的 I/O 或者别的什么事情。只有运行
的进程才能被阻塞。
2. 应该有一个寄存器包含当前进程表项的指针。当 I/O 结束时,CPU 将把当前的机器状态存
入到当前进程表项中。然后,将转到中断设备的中断向量,读取另一个过程表项的指针(服务
例程)。然后,就可以启动这个进程了。
3. 通常,高级语言不允许访问 CPU 硬件,而这种访问是必需的。例如,中断处理程序可能
需要禁用和启用某个特定设备的中断服务,或者处理进程堆栈区的数据。另外,中断服务例
程需要尽快地执行。
4. 内核使用单独的堆栈有若干的原因。其中两个原因如下: 首先,不希望操作系统崩溃,
由于某些用户程序不允许足够的堆栈空间。 第二,如果内核将数据保留在用户空间,然
后从系统调用返回,那么恶意的用户可能使
用这些数据找出某些关于其它进程的信息。
5. 即使是有可能实现,也是很难保持文件系统的一致性。假设某个客户进程给服务器进程 1 发
送请求要更新文件。该进程更新其内存的 cache 项。然后,另一个客户进程给服务器进程
2发送请求读取该文件。不幸的是,如果该文件还在 cache 中 ,服务器进程 2 对 此毫不知情,
将返回过时的数据。如果第一个进程在缓冲后将文件写到磁盘中,而服务器进程 2 每 次读取
时检查磁盘其缓存的备份是否是最新的,系统还可以工作,但是需要避免磁盘访问的所有缓
存系统。
6. 当线程停止时,其值保留在寄存器中。当进程停止时寄存器必须被保存。分时线程与分时
进程没有区别,因此每个线出都需要其自己的寄存器保存区。
7. 不会。如果单线程进程在键盘上阻塞,就不能创建子进程。
8. 当工作者线程从磁盘读取 Web 页时,它就会被阻塞。如果使用用户级线程,该动作将阻
塞整个进程,而破坏多线程的价值。这就是使用内核线程的原因:某些线程的阻塞不会影响
到其他线程。
9. 进程中的线程是相互协作的,而不是相互对立的。如果放弃是为了应用程序,那么线程将
放弃 CPU。毕竟,通常是同一个程序员写的代码。
10. 用户级线程不能按时钟剥夺,除非整个进程的时间片用完。内核级线程可以单独地被剥夺。
在后一种情况下,如果线程运行过久,时钟将中断该当前进程,因而当前线程也被中断。内核
可以自由地从同一个进程中选取其他线程运行。
11. 在单线程情况下,cache 命 中需 15 msec,cache 未 命中需要 90 msec。其加权平均为 2/3
* 15 + 1/3 * 90。因此,平均请求为 40 msec,而服务器每秒可处理 25个。对于多线程服务器,
所有磁盘等待都是重叠的,因此每个请求都耗时 15 msec,而服务器每秒可处理 66.6666 个 请
求。
4
12. 是的。如果服务器是完全 CPU 绑定的,则不需要多线程。这只会增加不必要的复杂性。
假设某个百万人口区域的电话查号系统(类似于 114),如果每个(姓名, 电话号码)记录为 64 个
字符,整个的数据库则为 64MB,这就很容易全部读入服务器内存中以提供快速的查询。
13. 指针是确实必要的,因为全局变量的大小是未知的。它可能是从字符到浮点数数组的任何
类型。如果保存其值,就不得不把其大小传递给 create_global,这都没有问题,但是必须将
其类型作为 set_global 的 第二个参数,那么 read_global 返 回值的类型是什么呢?
14. runtime 系统可以正好在这一时刻阻塞或者解除阻塞某个线程,并且忙于处理调度队列。
此时并不适合于时钟中断处理程序开始检查该队列是否应该进行线程切换,因为它们可能处
于不一致的状态。解决方法可以是:当进入 runtime 系统后,设置一个标志。时钟处理程序
将看到该标志,并且设置其自己的标志,然后返回。当 runtime 系统完成时,它将检测时钟
标志,看是否有时钟中断发生,并且现在运行时钟处理程序。
15. 这是可能的,不过效率很低。线程想要做一个系统调用,首先设定警报定时器,然后才执
行调用。如果线程阻塞,定时器将控制归还给线程包。当然,大多数调用是不阻塞的,而定
时器必须被清除。每个可能被阻塞的系统调用都必须作为 3 个系统调用来执行。如果定时器
过早时效,各种问题都可能发生。用这种方法建立线程包并不好。
16. 当低优先级进程位于其临界区,而高优先级进程就绪并且被调度时,将发生优先级倒置问
题。如果使用忙等待,它将一直运行。对于用户级线程,不可能发生低优先级线程突然被剥
夺而允许高优先级线程运行,因为是不可剥夺的。而内核级线程,就会出现这个问题。
17. 每个线程都是自己调用例程,因此它必须有其自己的堆栈以保存局部变量、返回地址等等。
这一点用户级线程和内核级线程是一样的。
18. 竞争条件是指如下的情形:两个(或多个)进程将要执行某些动作,其执行依赖于准确的定
时。如果某个进程首先执行,所有事件顺利完成,但是如果另一个先执行,则会产生致命的
错误。
19. 是。模拟的计算机可能是多道程序的。例如,当进程 A 运行时,它读出某些共享变量。
然后,发生一个模拟时钟计时,而进程 B 运 行。它也读出相同的变量。接着,它把该变量加
1。当进程 A 运 行时,如果它也是给变量加 1,就会产生竞争条件。
20. 是,它还是有用的。当然,它依然是忙等待。
21. 该方法对可剥夺调度完全没问题。事实上,它就是为这种情况设计的。当调度为不可剥夺
的,该方法将会失败。假设 turn 初值为 0,而进程 1 首先运行。它将一直循环,永不释放 CPU。
22. 当然可以。将内存字作为标志,0 表 示没有进程使用临界变量,1 表示有某个进程正在使
用。将 1 放 入寄存器中,并且交换内存字和寄存器。如果寄存器在交换后为 0,则准许访问。
如果它包含 1,则拒绝访问。当进程完成时,将 0 存 储在内存标志中。
23. 执行信号量操作,操作系统首先要禁用中断。然后,它读取信号量的值。如果执行 down 操
作,而信号量等于 0,就将调用进程放入与信号量有关的阻塞进程列表中。如果执行 up 操
作,必须检测看是否有任何进程在信号量上被阻塞。如果有一个或多个进程被阻塞,从阻塞
进程的列表中移出一个,使之就绪。当所有这些操作都完成后,就可以开启中断了。
24. 将每个计数信号量与 2 个二值信号量联合:M 用于互斥;B 用于阻塞。另外,每个计数
5
信号量都组合一个用于保存 up 次数减去 down 次数的计数器,以及在该信号量上阻塞的进
程列表。为了实现 down 操作,进程首先通过对 M 执行 down 操作,以获得对信号量、计
数器以及列表的独占访问权。然后,将计数器减 1。如果大于等于 0,只需对 M 执行 up 操
作并退出即可。如果 M 为 负数,就将该进程放入阻塞进程列表中。接着,对 M 执 行 up 操 作,
对 B 执 行 down 操 作来阻塞该进程。为了实现 up 操 作,首先对 M 执 行 down 操 作以获
得互斥,然后将计数器加 1。如果计数器大于 0,则没有进程阻塞,就只需对 M 执行 up 操
作。不过,如果计数器小于等于 0,则必须从列表中移出某些进程。最后,按次序对 B 和 M
执 行
up 操 作。
25. 如果程序操作按阶段执行,直到两个进程都完成当前阶段才能进入下一阶段,这时就应该
使用屏障。
26. 对于时间片轮转调度,该方法不会出现问题。L 迟早会运行,而且最终将离开其临界区。
对于优先级调度,L 永远得不到运行;而对于时间片轮转,它将周期性地得到一时间片,因
此就有机会离开其临界区。
27. 对于内核线程,线程可以在信号量上阻塞,而内核可以运行该进程中的其它线程。因而,
使用信号量没有问题。而对于用户级线程,当某个线程在信号量上阻塞时,内核将认为整个进
程都被阻塞,而且不再执行它。因此,进程失败。
28. 其实现的代价很高。每次在某些等待变化的进程的谓词中出现的任何变量,runtime 系 统
都必须重新计算该谓词,以判断该进程是否能够被解锁。而对于 Hoare 和 Brinch Hansen 管程,
则只需 signal 原 语即可唤醒进程。
29. 雇员之间通过消息传递进行通信:在该例中,消息为订单、食物和袋子。在 UNIX 中,
该 4 个 进程通过管道连接。
30. 它不会导致竞争条件(不会丢失任何东西),不过它是完全的忙等待。
31. 如果某个哲学家阻塞,其邻居稍后能够在 test 中检测其状态,发现他已经饥饿,当叉子
可用时,就可以唤醒他了。
32. 该变化将意味着在哲学家停止进餐后,他的邻居都不能接着被选择。事实上,他们永远不
会被选择。假设哲学家 2 完成了进餐,他将为哲学家 1 和 3 运行 test,而两者都不会被启动,
即使他们两个都饿了而且两个叉子都是可用的。类似的,如果哲学家 4 完成进餐,哲学家 3
也 不会被启动。他将无法启动。
33. 变种 1:读者优先。当读着活跃时,写者都无法启动。当一个新的读者出现时,它可以立
即开始除非当前有写者是活跃的。当写者完成时,如果有读者在等待,他们全都启动,无论
是否有写者存在。
变种 2:写者优先。当有写者等待时,读者都不会开始。当最后活跃的进程结束,如果有作者,
就启动它;否则,所有读者(如果有)全部开始。
变种 3:平衡的版本。当有读者是活跃的,新的读者可以立即开始。当写者完成时,新的写者
优先,如果有写者等待的话。也就是说,一旦开始读,就一直读到没有读者为止。同样地,一
旦开始作,所有挂起的写者都被允许运行。
34. 它将需要 nT sec。
35. 如果进程在列表中出现多次,它在每个周期内得到多个时间片。这种方法可以用来给重
6
要的进程更多的 CPU 时间。但是当该进程阻塞时,最好从可运行进程的列表中将其所有项都
删除。
36. 在简单的情况下是有可能通过看源代码来判断是否为 I/O 绑定的。例如,程序开始时,
将其所有输入文件读入到缓冲器中,这种程序通常不是 I/O 绑定的;但是,对不同文件进行
增量地读写(诸如编译程序)的问题很有可能是 I/O 绑定的。如果操作系统提供诸如 UNIX ps
的命令,就可以得知被程序使用的 CPU 时间的量,你能把这个时间量与整个的时间比较以判
断。当然,最有意义就是你是系统中唯一的用户。
37. 对于管道中的多个进程,普通的父进程可以将数据流的信息传递给操作系统。有了这个信
息,OS 就 可以确定哪个进程可以向需要输入的阻塞进程提供输出。
38. CPU 的 效率就是有用的 CPU 时 间除以整个的 CPU 时 间。
当 Q ≥ T 时 ,基本的周期就是进程运行 T,然后进程切换 S。因此,(a)和(b)的效率都是 T/(S
+ T)。当时间片比 T 短时,每运行一次 T 就要求 T/Q 次进程切换,浪费时间为 ST/Q。因此,
其效率为
T
T + ST /Q
也就是下降到 Q/(Q + S),这就是(c)的答案。至于(d),只需以 S 替 代 Q,就可以计算出其
效率为 50%。最后,(e)的效率趋近于 0。
39. 最短作业优先可以使得平均响应时间最短。
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.
40. 对于时间片轮转,在头 10 分钟里,每个作业获得 1/5的 CPU 时间。在第 10 分钟时,C 结
束。在接下来的 8 分钟里,每个作业获得 1/4 的 CPU 时间,然后 D 完成。然后,在接下来的
6 分钟内,余下的 3 个作业各获得 1/3 的 CPU 时间,直到 B 结束,以此类推。因此,5 个作
业的完成时间分别为是 10,18,24,28 和 30,平均为 22 分 钟。
对于优先级调度,B 最 先运行,6 分钟完成。其它作业分别在第 14,24,26 和 30 分钟完成,
平均为 18.8 分 钟。
如果作业按 A?E 的次序执行,则分别在第 10,16,18,22 和 30 分钟完成,因此,平均为
19.2 分钟。
最后,最短作业优先调度的完成时间分别为第 2,6,12,20 和 30 分钟,平均为 14 分钟。
41. 第一次得到 1 个 时间片。随后获得 2,4,8 和 15个时间片,因此必须经过 5 次 交换。
42. 可以检查程序是否期待输入,并且对输入进行处理。不期待输入也不对输入进行处理的程
序将不得到任何特殊的优先级提升。
43. 预测值为 40/8 + 20/8 + 40/4 + 15/2 = 25。
7