现代操作系统第四版 第二章 答案

1、现代操作系统 第二章 进程与线程 习题1. 图 2-2 中给出了三个进程状态，在理论上，三个状态可以有六种转换，每个状态两个。但是，图中只给出了四种转换。有没有可能发生其他两种转换中的一个或两个A:从阻塞到运行的转换是可以想象的。假设某个进程在 I/O 上阻塞，而且I/O 结束，如果此时 CPU 空闲，该进程就可以从阻塞态直接转到运行态。而另外一种转换（从阻塞态到就绪态）是不可能的。一个就绪进程是不可能做任何会产生阻塞的 I/O 或者别的什么事情。只有运行的进程才能被阻塞。2.换。CPU 需要哪些信息请描述用硬件完成进程切换的工作过程。A:应该有一个寄存器包含当前进程表项的指针。当I/O 结束

2、时，CPU 将把当前的机器状态存入到当前进程表项中。然后，将转到中断设备的中断向量，读取另一个过程表项的指针（服务例程），然后，就可以启动这个进程了。3.当代计算机中，为什么中断处理程序至少有一部分是用汇编语言编写的A：通常，高级语言不允许访问CPU 硬件，而这种访问是必需的。例如，中断处理程序可能需要禁用和启用某个特定设备的中断服务，或者处理进程堆栈区的数据。另外，中断服务例程需要尽快地执行。 （补充）主要是出于效率方面的考量。中断处理程序需要在尽量短的时间内完成所需的必要处理，尽量减少对线程程序流造成的影响，因此大部分情况下用汇编直接编写，跳过了通用编译过程中冗余的适配部分。4.分离的内核

3、栈A：内核使用单独的堆栈有若干的原因。其中两个原因如下： 首先，不希望操作系统崩溃，由于某些用户程序不允许足够的堆栈空间。 第二，如果内核将数据保留在用户空间，然后从系统调用返回，那么恶意的用户可能使用这些数据找出某些关于其它进程的信息。5.一个计算机系统的内存有足够的空间容纳 5 于等待 I/O 的空闲状态。请问 CPU 时间浪费的比例是多少A：5 =%6.一个计算机的 RAM 有 4GB 512MB 256MB（为了简化计算）并且特征相同。要是 CPU 利用率达到 99%，最大 I/O 等待是多少A：内存中最多可放(4GB-512MB)/256MB=14 个进程，设每个进程的 I/O 等待

4、占总运行时间的比例为 ，则 CPU 利用率=1-p1499%=p%7.始执行，每个需要20 分钟的 CPU 时间。如果顺序执行，那么最后一个作业需要多长时间可以完成如果并行执行又需要多长时间假设 I/O 等待占 50%。A: 每个进程的时间为 40min 80min 才能完成。并行执行时，cpu 利用率为 1-pn = 75%, cpu 计算时间为 ，故总时间t=40/75%=8.考虑一个 6 级多道程序系统（内存中可同时容纳6 个程序）。假设每个进程的I/O 等待占 40%，那么 CPU 利用率是多少A：利用率=1-pn=1-6 = =%9.假设要从互联网上下载一个 2GB 大小的文件，文件

5、内容可以从一组镜像服务器获得，每个服务器可以传输文件的一部分。假设每个传输请求给定起始字节和结束字节。如何用多线程优化下载时间A：客户端进程可以创建单独的线程; 每个线程都可以从其中一个镜像服务器获取文件的不同部分。 这有助于减少停机时间。 当然，所有线程都共享一个网络链接。 这个链接可以成为一个瓶颈，因为线程的数量变得非常大。10.为什么图 2-11a 的模式不适合用于在内存使用高速缓存的文件服务器每个进程可以有自己的高速缓存吗A：即使是有可能实现，也是很难保持文件系统的一致性。假设某个客户进程给服务器进程 1 cache 个客户进程给服务器进程 2 发送请求读取该文件。不幸的是，如果该文件

6、还在cache 中，服务器进程2 对此毫不知情，将返回过时的数据。如果第一个进程在缓冲后将文件写到磁盘中， 而服务器进程 2 每次读取时检查磁盘其缓存的备份 个人认为，高速缓存应该每个进程共享，因为不是每个进程都需要频繁读写数据，如果每个进程都分配 cache 会造成资源浪费。）11.当一个多线程进程创建子进程时，如果子进程复制父进程的所有线程，就会出现问题：假如夫进程中有一个线程正在等待键盘输入，现在就有两个线程在等待键盘输入，父进程和子进程各有一个。这种问题在单线程进程中也会发生吗A：不会。如果单线程进程在键盘上阻塞，就不能创建子进程。（而多线程进程在一个线程阻塞时可以运行另一个线程，整个

7、进程不会因此被阻塞。）12.在图 2-8 中，给出了一个多线程 Web 服务器。如果读取文件的惟一途径是正常的阻塞 read Web 服务器应该使用用户级线程还是内核级线程为什么A：当工作者线程从磁盘读取 Web 页时，它就会被阻塞。如果使用用户级线程，该动作将阻塞整个进程，而破坏多线程的价值。这就是使用内核线程的原因：某些线程的阻塞不会影响到其他线程。13.在本章中，我们介绍了多线程Web 服务器，说明它比单线程服务器和有限状态机服务器更好的原因。存在单线程服务器更好一些的情形吗请举例。A：在多线程 Web 服务器中，由分派程序 从网络中读入工作请求，在检查请求后，分派线程挑选一个空转的（即

8、被阻塞的）工作线程，提交该请求。在工作线程被唤醒后，他检查有关的请求是否在 Web 页面高速缓存中，这个高速缓存是所有线程否可以访问的。如果没有，该线程开始一个从磁盘调入页面的 read操作，并且阻塞知道该磁盘操作完成。在上述线程被阻塞在磁盘操作上时，分派线程可能挑选另一个线程运行，可以有效利用 CPU 资源。而在单线程服务器上，只能等第一个线程完成后，才能开始第二个线程。 也存在单线程服务器更好的情形。如果服务器是完全 CPU 绑定的，则不需要多线程。这只会增加不必要的复杂性。假设某个百万人口区域的电话查号系统(类似于 114)，如果每个姓名，电话号码记录为 64 个字符，整个的数据库则为

9、64MB，这就很容易全部读入服务器内存中以提供快速的查询。14。既然计算机中只有一套寄存器，为什么在图 2-12 中的寄存器集合是按每个线程中列出而不是按每个进程列出。A必须保存寄存器。多线程和多进程没有什么不同，所以每个线程需要自己的寄存器保存区。15.CPU后可能再也不会获得CPU资源，那么为什么线程还要通过调用 thread_yield 自愿放弃 CPUA那么一个线程可以调用 thread_yield 自愿放弃 的全部代码通常是一个程序员写的。16.线程可以被时钟中断抢占吗如果可以，在什么情形下可以如果不可以，为什么不可以A：用户级线程不能被时钟剥夺，除非整个进程的时间片用完。内核级线程

10、可以单独地被剥夺。在后一种情况下，如果线程运行过久，时钟将中断该当前进程，因而当前线程也被中断。内核可以自由地从同一个进程中选取其他线程运行。17.请对使用单线程文件服务器和多线程文件服务器读取文件进行比较。假设所需要的数据都在块高速缓存中，获得工作请求，分派工作，并处理其余必要工作需要花费 1/3 ，此时该线程进入睡眠。单线程服务器每秒钟可以处理多少个请求多线程服务器呢A：在单线程情况下，cache 命中需要 12mscache 未命中需要 87ms，其加权平均为 2/312+1/387 = 37 ms 1s/37ms = 27 个. 在多线程情况下，所有磁盘等待都是重叠的，因此每个请求耗时

11、 ，一秒钟可以完成1s/12ms = 个（个人认为这样算不太准确，因为最后的几个线程如果cache 未命中的话，就需要 87ms，可能是完不成的，不过这个题意翻译的不是很清楚，什么叫做“时间过去1/3 1/3 的时间需要额外的磁盘操作“。这样平均算下来也可以忽略 cache 未命中发生的分布情况。）18.在用户态实现线程的最大的优点是什么最大的缺点是什么A：最大的优势就是效率。不需要陷入内核来切换线程。最大的缺点是，如果一个线程阻塞，整个进程都会阻塞。19.在图 2-15 严格按照以下次序运行：创建线程，线程1 打印消息，线程1 结束，创建线程2，线程 2 打印消息，线程 2 结束，以此类推；

12、如果有，是什么方法，如果没有请解释原因。A：是的，这是可以做到的。每次执行 pthreadcreate 后，主程序可以调用pthread_join 等待刚刚创建的线程退出后再创建下一个线程。20.在讨论线程中的全局变量时，曾使用过程 create_global 将存储分配给指向变量的指针，而不是变量自身。这是必需的吗还是直接使用变量自身也可行A：将存储分配给指针是确实必要的，因为全局变量的大小是未知的。它可能是从字符到浮点数数组的任何类型。如果保存其值，就不得不把其大小传递给create_global set_global 的第二个参数，那么 read_global 返回值的类型是不确定的。2

13、1.考虑一个线程全部在用户态实现的系统，该运行时系统每秒钟获得一个时钟中断。当某个线程正在运行时系统中执行时发生一个时钟中断，此时会出现什么问题你有什么解决该问题的建议吗A：runtime 系统可以正好在这一时刻阻塞或者解除阻塞某个线程，并且忙于处理调度队列。此时并不适合于时钟中断处理程序开始检查该队列是否应该进行线程切换，因为它们可能处于不一致的状态。解决方法可以是：当进入 runtime系统后，设置一个标志。时钟处理程序将看到该标志，并且设置其自己的标志， runtime 并且现在运行时钟处理程序。22.假设一个操作系统中不存在类似于 select 的系统调用来提前了解在从文件、管道或设备

14、中读取时是否安全，不过该操作系统确实允许设置报警时钟，以便中断阻塞的系统调用。在上述条件下，是否有可能在用户态中实现一个线程包请讨论。A：这是可能的，不过效率很低。线程想要做一个系统调用，首先设定警报定时器，然后才执行调用。如果线程阻塞，定时器将控制归还给线程包。当然，大多数调用是不阻塞的，而定时器必须被清除。每个可能被阻塞的系统调用都必须作为 3 个系统调用来执行。如果定时器过早失效，各种问题都可能发生。用这种方法建立线程包并不好。23.两个进程在一个共享内存的多处理器（两个 ）上运行，当他们要共享一块内存时，图 223 中使用 turn 变量的忙等待解决方案还有效吗A：仍然有效，但也仍旧是

15、忙等待。24. 2-24 中互斥问题的 Peterson 解法可行吗如果是非抢占式调度呢A：对抢占式调度可行。事实上，这种解法就是为它设计的。而对于非抢占式调度，可能会失败。考虑这种情况：turn 被初始化为 ，但进程 1 先开始运行了，它就会一直循环，但不释放 ，具有忙等待的缺点。节中所讨论的优先级反转问题在用户级线程中是否可能发生为什么A：当低优先级进程位于其临界区，而高优先级进程就绪并且被调度时，将发生优先级倒置问题。如果使用忙等待，高优先级进程将一直运行。对于用户级线程，不可能发生低优先级线程突然被剥夺而允许高优先级线程运行，因为是不可剥夺的。而内核级线程，就会出现这个问题。节中描述了

16、一种有高优先级进程 H 和低优先级进程 L 的情况，导致了 H 陷入死循环。若采用轮转调度算法而不是优先级调度算法，还会发生这样问题吗请讨论。A：不会发生这样的问题。在轮转调度算法下。L 迟早会运行，最终它将会离开L 永远不会运行；在轮转循环下，它定期得到一个正常的时间片，所以有机会离开其临界区。27.在使用线程的系统中，若使用用户级线程，是每个线程一个栈还是每个进程一个栈如果使用内核级线程呢请解释。A：每个线程都是自己调用例程，因此它必须有其自己的堆栈以保存局部变量、返回地址等等。这一点用户级线程和内核级线程是一样的。28.在开发计算机时，通常首先用一个程序模拟执行，一次运行一条指令，多处理

17、器也严格按此模拟。在这种没有同时事件发生的情形下，会出现竞争条件吗A的相对时间的情形。 竞争条件发生在当多个进程或者线程在读写数据时，其最终的的结果依赖于多个进程的指令执行顺序。）是的。模拟计算机也可以是多道程序设计的。例如，在进程 A 运行时，它读取一些共享变量。然后发生了一个模拟时钟周期和进程 B 运行。它也读取相同的变量，然后对变量进行了加 1操作。当进程A 运行时，如果它也对变量进行了加1 操作，就发生了竞争条件。29. 将生产者消费者问题扩展成一个多生产者-多消费者的问题，生产（消费）者都写（读）一个共享的缓冲区，每个生产者和消费者都在自己的线程中执行。图 2-28 中使用信号量的解

18、法在这个系统中还可行吗A：可行。在给定的某个时刻，只有一个生产者（消费者）可以向（从）缓冲区添加（取出）项目。30.考虑对于两个进程 P0 和 P1 的互斥问题的解决方案。假设变量初始值为 。P0 的代码如下：p1 的代码是将上述代码中的 0 替换为 。该方法是否能处理互斥问题中所有可能的情形A：该解决方案满足互斥，因为两个流程不可能同时处于 Critical Section。也就是说，当 turn 为 0 时，P0 可以执行其临界区，但 P1 不能执行。当 turn 为 1 也有相似的情况。但是，这假设 P0 必须先运行。如果 P1 产生某些东西并将其放 P0 该解决方案需要严格交替两个过程

19、，这是不希望发生的。31.一个可以屏蔽中断的操作系统如何实现信号量A：执行信号量操作，操作系统首先要禁用中断。然后，它读取信号量的值。如果执行 down 操作，而信号量等于，就将调用进程放入与信号量有关的阻塞进程列表中。如果执行 up 操作，必须检测看是否有任何进程在信号量上被阻塞。如果有一个或多个进程被阻塞，从阻塞进程的列表中移出一个，使之就绪。当所有这些操作都完成后，就可以开启中断了。 书中的原话是：操作系统只需在执行以下操作时暂时屏蔽全部中断：测试信号量、更新信号量以及在需要时是某个进程睡眠。:32.一个任意值的信号量）。:A： 用两个二值信号量和一个计数器 counter 实现一个计数

20、信号量：M 用于互斥，B 用于阻塞，counter 用于记录 up 减去 down 的次数，再用一个链表来记录阻塞在这个计数信号量上的进程。 down 的实现：进程先对 M 进行 down 来获得 counter、链表的独占访问权，并把 counter 减 。如果 counter 大于等于 ，直接对 M 进行 up 即可；否则，记录在链表再 ，然后对 B 进行 down 从而阻塞这个进程。 up 的实现：进程同样先对 M 进行 downcounter 加 ，若其大于 ，直接对 M 进行 up 即可；否则 counter 小于等于 ，把链表中一个进程移出，然后对 、M 依次 。33.如果一个系统

21、只有两个进程，可以使用一个屏障来同步这两个进程吗为什么A:如果程序操作按阶段执行，直到两个进程都完成当前阶段才能进入下一阶段，这时就应该使用屏障。这个答案也有点奇怪，我认为只要这两个进程不是生产者消费者模式就可以使用屏障。）34.如果线程在内核态实现，可以使用内核信号量对同一个进程中的两个线程进行同步吗如果线程在用户态实现呢假设在其他进程中没有线程必须访问该信号量。请解释你的答案。A：对于内核线程，线程可以在信号量上阻塞，而内核可以运行该进程中的其它线程。因而，使用信号量没有问题。而对于用户级线程，当某个线程在信号量上阻塞时，内核将认为整个进程都被阻塞，而且不再执行它。因此，在用户态线程的同步

22、失败。35.管程内的同步机制使用条件变量和两个特殊操作 wait 和 signal。一种更通用的同步形式是只用一条原语 waituntil，它以任意的布尔谓词作为参数。例如waituntil x 0 or y + z T(c) S Q 0;44. 有 5 N 分别是 9, 6, 3, 5 和 序运行这些作业将得到最短的平均响应时间（答案将依赖于 X）A:最短作业优先可以使得平均响应时间最短。 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 9: 3, 5,6, 9, X.45.有 5 个批处理作业 A 到

23、，它们几乎同时到达一个计算中心。估计它们的运行时间分别为 1064 和 8 分钟。其优先级（由外部设定）分别为3，1 和 4，其中5 为最高优先级。对于下列每种调度算法，计算其平均进程周转时间，可忽略进程切换的开销。(a) 轮转法。(b) 优先级调度。(c) 先来先服务（按照 10，6，8 次序运行。(d) 最短作业优先。对，假设系统具有多道程序处理能力，每个作业均公平共享 CPU 时间;对(b)到(d) ，假设任一时刻只有一个作业运行，直到结束。所有的作业都完全是CPU密集型作业。A: 10 1/5 的 CPU 10 分钟时，C 结束。在接下来的 8 分钟里，每个作业获得 1/4 的 CPU

24、 时间，然后 D完成，然后，在接下来的 6 分钟内，余下的 3 个作业各获得 1/3 的 CPU 时间，直到 B 结束，以此类推。因此，5 个作业的完成时间分别为是 10, 18, 24, 28 和30, 平均为 22 分钟。对于优先级调度，5 最先运行，6 分钟完成。其它作业分别在第 14, 24, 26 和 30 分钟完成，平均为分钟。如果作业按 A-E 的次序执行，则分别在第 10,16, 18, 22 和 30 分钟完成，因此，平均为分钟。最后，最短作业优先调度的完成时间分别为第 2, 6, 12, 20 和 30 分钟，平均为 14 分钟。46.运行在 CTSS 上的一个进程需要 30 包括第一次在该进程运行之前）A:CTSS(兼容分时系统）设立优先级类：属于最高优先级类的进程运行一个时间片，漱玉词高优先级类的