操作系统答案（全）

[英文原版]操作系统_精髓与设计原理_第6版 答案翻译

Keys of Operating Systems Internals and Design Principles

6th Edition

第一章 计算机系统概述

复习题：

1.1、 列出并简要地定义计算机的四个主要组成部分。

答：主存储器，存储数据和程序；算术逻辑单元，能处理二进制数据；控制单元，

解读存储器中的指令并且使他们得到执行；输入/输出设备，由控制单元管理。

1.2、 定义处理器寄存器的两种主要类别。

答：用户可见寄存器：优先使用这些寄存器，可以使机器语言或者汇编语言的程序

员减少对主存储器的访问次数。对高级语言而言，由优化编译器负责决定把哪些变量应该分配给主存储器。一些高级语言，如C语言，允许程序言建议编译器把哪些变量保存在寄存器中。

控制和状态寄存器：用以控制处理器的操作，且主要被具有特权的操作系统例

程使用，以控制程序的执行。

1.3、 一般而言，一条机器指令能指定的四种不同操作是什么？

答：这些动作分为四类：处理器－寄存器：数据可以从处理器传送到存储器，或者

从存储器传送到处理器。处理器－I/O：通过处理器和I/O模块间的数据传送，数据可以输出到外部设备，或者从外部设备输入数据。数据处理，处理器可以执行很多关于数据的算术操作或逻辑操作。控制：某些指令可以改变执行顺序。

1.4、 什么是中断？

答：中断：其他模块（I/O，存储器）中断处理器正常处理过程的机制。 1.5、 多中断的处理方式是什么？

答：处理多中断有两种方法。第一种方法是当正在处理一个中断时，禁止再发生中

断。第二种方法是定义中断优先级，允许高优先级的中断打断低优先级的中断处理器的运行。

1.6、 内存层次的各个元素间的特征是什么？

答：存储器的三个重要特性是：价格，容量和访问时间。 1.7、 什么是高速缓冲存储器？

答：高速缓冲存储器是比主存小而快的存储器，用以协调主存跟处理器，作为最近

储存地址的缓冲区。

1.8、 列出并简要地定义I/O操作的三种技术。

答：可编程I/O：当处理器正在执行程序并遇到与I/O相关的指令时，它给相应的

I/O模块发布命令（用以执行这个指令）；在进一步的动作之前，处理器处于繁忙的等待中，直到该操作已经完成。中断驱动I/O：当处理器正在执行程序并遇到与I/O相关的指令时，它给相应的I/O模块发布命令，并继续执行后续指令，直到后者完成，它将被I/O模块中断。如果它对于进程等待I/O的完成来说是不必要的，可能是由于后续指令处于相同的进程中。否则，此进程在中

断之前将被挂起，其他工作将被执行。直接存储访问：DMA模块控制主存与I/O模块间的数据交换。处理器向DMA模块发送一个传送数据块的请求，（处理器）只有当整个数据块传送完毕后才会被中断。

1.9、 空间局部性和临时局部性间的区别是什么？

答：空间局部性是指最近被访问的元素的周围的元素在不久的将来可能会被访问。

临时局部性（即时间局部性）是指最近被访问的元素在不久的将来可能会被再次访问。

1.10、 开发空间局部性和时间局部性的策略是什么？ 答：空间局部性的开发是利用更大的缓冲块并且在存储器控制逻辑中加入预处理机

制。时间局部性的开发是利用在高速缓冲存储器中保留最近使用的指令及数据，并且定义缓冲存储的优先级。

习题：

1.1、图1.3中的理想机器还有两条I/O指令： 0011 = 从I/O中载入AC 0111 = 把AC保存到I/O中

在这种情况下，12位地址标识一个特殊的外部设备。请给出以下程序的执行过程（按照图1.4的格式）：

1. 从设备5中载入AC。

2. 加上存储器单元940的内容。 3. 把AC保存到设备6中。

假设从设备5中取到的下一个值为3940单元中的值为2。 答案：存储器（16进制内容）：300：3005；301：5940；302：7006 步骤1：3005－>IR；步骤2：3－>AC

步骤3：5940－>IR；步骤4：3＋2＝5－>AC 步骤5：7006－>IR：步骤6：AC－>设备 6

1.2、本章中用6步来描述图1.4中的程序执行情况，请使用MAR和MBR扩充这个描述。 答案：1. a. PC中包含第一条指令的地址300，该指令的内容被送入MAR中。 b. 地址为300的指令的内容（值为十六进制数1940）被送入MBR，并且PC增1。

这两个步骤是并行完成的。

c. MBR中的值被送入指令寄存器IR中。

2. a. 指令寄存器IR中的地址部分（940）被送入MAR中。 b. 地址940中的值被送入MBR中。 c. MBR中的值被送入AC中。

3. a. PC中的值（301）被送入MAR中。 b. 地址为301的指令的内容（值为十六进制数5941）被送入MBR，并且PC增1。 c. MBR中的值被送入指令寄存器IR中。

4. a. 指令寄存器IR中的地址部分（941）被送入MAR中。 b. 地址941中的值被送入MBR中。

c. AC中以前的内容和地址为941的存储单元中的内容相加，结果保存到AC中。 5. a. PC中的值（302）被送入MAR中。 b. 地址为302的指令的内容（值为十六进制数2941）被送入MBR，并且PC增1。

c. MBR中的值被送入指令寄存器IR中。

6. a. 指令寄存器IR中的地址部分（941）被送入MAR中。 b. AC中的值被送入MBR中。

c. MBR中的值被存储到地址为941的存储单元之中。

1.4、假设有一个微处理器产生一个16位的地址（例如，假设程序计数器和地址寄存器都是16位）并且具有一个16位的数据总线。

a.如果连接到一个16位存储器上，处理器能够直接访问的最大存储器地址空间为多少？ b.如果连接到一个8位存储器上，处理器能够直接访问的最大存储器地址空间为多少？ c.处理访问一个独立的I/O空间需要哪些结构特征？

d.如果输入指令和输出指令可以表示8位I/O端口号，这个微处理器可以支持多少8位I/O端口？

答案：对于(a)和(b)两种情况，微处理器可以直接访问的最大存储器地址空间为216 = 64K

bytes；唯一的区别是8位存储器每次访问传输1个字节，而16位存储器每次访问可以传输一个字节或者一个16位的字。对于(c)情况，特殊的输入和输出指令是必要的，这些指令的执行体会产生特殊的“I/O信号”（有别于“存储器信号”，这些信号由存储器类型指令的执行体产生）；在最小状态下，一个附加的输出针脚将用来传输新的信号。对于(d)情况，它支持28 = 256个输入和28 = 256个输出字节端口和相同数目的16位I/O端口；在任一情况, 一个输入和一个输出端口之间的区别是通过被执行的输入输出指令所产生的不同信号来定义的。

1.5、考虑一个32位微处理器，它有一个16位外部数据总线，并由一个8MHz的输入时钟驱动。假设这个微处理器有一个总线周期，其最大持续时间等于4个输入时钟周期。请问该微处理器可以支持的最大数据传送速度为多少？外部数据总线增加到21位，或者外部时钟频率加倍，哪种措施可以更好地提高处理器性能？请叙述你的设想并解释原因。 答案：时钟周期＝1/（8MHZ）＝125ns

总线周期＝4×125ns＝500ns

每500ns传输2比特；因此传输速度＝4MB/s 加倍频率可能意味着采用了新的芯片制造技术（假设每个指令都有相同的时钟周期数）；加倍外部数据总线，在芯片数据总线驱动/锁存、总线控制逻辑的修改等方面手段广泛（或许更新）。在第一种方案中，内存芯片的速度要提高一倍（大约），而不能降低微处理器的速度；第二种方案中，内存的字长必须加倍，以便能发送/接受32位数量。

1.6、考虑一个计算机系统，它包含一个I/O模块，用以控制一台简单的键盘/打印机电传打字设备。CPU中包含下列寄存器，这些寄存器直接连接到系统总线上： INPR：输入寄存器，8位 OUTR：输出寄存器，8位 FGI：输入标记，1位 FGO：输出标记，1位 IEN：中断允许，1位

I/O模块控制从打字机中输入击键，并输出到打印机中去。打字机可以把一个字母数字符号编码成一个8位字，也可以把一个8位字解码成一个字母数字符号。当8位字从打字机进入输入寄存器时，输入标记被置位；当打印一个字时，输出标记被置位。 a. 描述CPU如何使用这4个寄存器实现与打字机间的输入/输出。

b. 描述通过使用IEN，如何提高执行效率？

答案：a.来源于打字机的输入储存在INPR中。只有当FGI＝0时，INPR才会接收来自打字

机的数据。当数据接收后，被储存在INPR里面，同时FGI置为1。CPU定期检查FGI。如果FGI＝1，CPU将把INPR里面的内容传送至AC，并把FGI置为0。 当CPU需要传送数据到打字机时，它会检查FGO。如果FGO＝0，CPU处于等

待。如果FGO＝1，CPU将把AC的内容传送至OUTER并把FGO置为0。当数字符号打印后，打字机将把FGI置为1。

b.（A）描述的过程非常浪费。速度远高于打字机的CPU必须反复不断的检查FGI

和FGO。如果中断被使用，当打字机准备接收或者发送数据时，可以向CPU发出一个中断请求。IEN计数器可以由CPU设置（在程序员的控制下）。

1.7、实际上在所有包括DMA模块的系统中，DMA访问主存储器的优先级总是高于处理器访问主存储器的优先级。这是为什么? 答案：如果一个处理器在尝试着读或者写存储器时被挂起, 通常除了一点轻微的时间损耗之

外没有任何危害。但是，DMA可能从或者向设备(例如磁盘或磁带)以数据流的方式接收或者传输数据并且这是不能被打断的。否则，如果DMA设备被挂起（拒绝继续访问主存），数据可能会丢失。

1.9、一台计算机包括一个CPU和一台I/O设备D，通过一条共享总线连接到主存储器M，数据总线的宽度为1个字。CPU每秒最多可执行106条指令，平均每条指令需要5个机器周期，其中3个周期需要使用存储器总线。存储器读/写操作使用1个机器周期。假设CPU正在连续不断地执行后台程序，并且需要保证95%的指令执行速度，但没有任何I/O指令。假设1个处理器周期等于1个总线周期，现在要在M和D之间传送大块数据。

a.若使用程序控制I/O，I/O每传送1个字需要CPU执行两条指令。请估计通过D的I/O数据传送的最大可能速度。

b.如果使用DMA传送，请估计传送速度。 答案：a.处理器只能分配5％的时间给I/O.所以最大的I/O指令传送速度是10e6×0.05＝50000

条指令/秒。因此I/O的传送速率是25000字/秒。 b.使用DMA控制时，可用的机器周期下的数量是

10e6（0.05×5＋0.95×2）＝2.15×10e6

如果我们假设DMA模块可以使用所有这些周期，并且忽略任何设置和状态检查时间，那么这个值就是最大的I/O传输速率。

1.10、考虑以下代码：

for ( i = 0；i < 20；i++) for (j = 0；j < 10；j++) a[i] = a[i]*j

a. 请举例说明代码中的空间局部性。 b. 请举例说明代码中的时间局部性。

答案：a.读取第二条指令是紧跟着读取第一条指令的。

b.在很短的间歇时间内， a[i]在循环内部被访问了十次。

1.11、请将附录1A中的式（1.1）和式（1.2）推广到n级存储器层次中。 答案：定义：

Ci = 存储器层次i上每一位的存储单元平均花销 Si = 存储器层次i的规模大小

Ti = 存储器层次i上访问一个字所需时间

Hi = 一个字在不高于层次i的存储器上的概率

Bi = 把一个数据块从层次i+1的存储器上传输到层次i的存储器上所需时间

高速缓冲存储器作为是存储器层次1；主存为存储器层次2；针对所有的N层存储器层

以此类推。有：

CS??CSii?1nni

i?Si?1 Ts的引用更复杂，我们从概率论入手：所期望的值x?n?iPr[x?1]，由此我们可以

i?1n写出：Ts??THii?1i

我们需要清楚如果一个字在M1（缓存）中，那么对它的读取非常快。如果这个字在M2而不在M1中，那么数据块需要从M2传输到M1中，然后才能读取。因此，T2 = B1+T1 进一步，T3 = B2+T2 = B1+B2+T1 以此类推：Ti?n?Bj?1i?1i?1j?T1

n所以，Ts?n??(BH)?T?Hji1i?2j?1i?1ii

但是，

?Hi?1?1

i?1最后，Ts???(BH)?T

ii1i?2j?1n

1.12、考虑一个存储器系统，它具有以下参数： Tc = 100 ns Cc = 0.01 分/位 Tm = 1200 ns Cm = 0.001 分/位 a.1MB的主存储器价格为多少？

b.使用高速缓冲存储器技术，1MB的主存储器价格为多少？

c.如果有效存取时间比高速缓冲存储器存取时间多10% ，命中率H为多少？ 答案：a.价格 = Cm×8×106 = 8×103 ￠ = ＄80 b.价格 = Cc×8×106 = 8×104 ￠ = ＄800 c.由等式1.1知：1.1×T1 = T1+(1-H)T2 (0.1)(100) = (1-H)(1200)

H=1190/1200

1.13、一台计算机包括包括高速缓冲存储器、主存储器和一个用做虚拟存储器的磁盘。如果要存取的字在高速缓冲存储器中，存取它需要20ns；如果该字在主存储器中而不在高速缓冲存储器中，把它载入高速缓冲存储器需要60ns（包括最初检查高速缓冲存储器的时间），然后再重新开始存取；如果该字不在主存储器中，从磁盘中取到内存需要12ms，接着复制到高速缓冲存储器中还需要60ns，再重新开始存取。高速缓冲存储器的命中率为0.9，主存储器的命中率为0.6，则该系统中存取一个字的平均存取时间是多少（单位为ns）？ 答案：有三种情况需要考虑：

字所在的位置 在缓存中 不在缓存，在主存中 不在缓存也不在主存中 概率 0.9 （0.1）（0.6）= 0.06 （0.1）（0.4）= 0.04 访问所需时间（ns） 20 60+20 = 80 12ms+60+20 = 12,000,080 所以平均访问时间是：

Avg = (0.9)(20) + (0.06)(80) + (0.04)(12000080) = 480026 ns

1.14、假设处理器使用一个栈来管理过程调用和返回。请问可以取消程序计数器而用栈指针代替吗？

答案：如果栈只用于保存返回地址。或者如果栈也用于传递参数，这种方案只有当栈作为传

递参数的控制单元而非机器指令时才成立。这两种情况下可以取消程序计数器而用栈指针代替。在后者情况中，处理器同时需要一个参数和指向栈顶部的程序计数器。

第二章 操作系统概述

复习题

2.1操作系统设计的三个目标是什么？

方便：操作系统使计算机更易于使用。

有效：操作系统允许以更有效的方式使用计算机系统资源。

扩展的能力：在构造操作系统时，应该允许在不妨碍服务的前提下有效地开

发、测试和引进新的系统功能。

2.2什么是操作系统的内核？

内核是操作系统最常使用的部分，它存在于主存中并在特权模式下运行，响应进程调度和设备中断。 2.3什么是多道程序设计？

多道程序设计是一种处理操作，它在两个或多个程序间交错处理每个进程。

2.4什么是进程？

进程是一个正在执行的程序，它被操作系统控制和选择。

2.5操作系统是怎么使用进程上下文的？

执行上下文又称为进程状态，是操作系统用来管理和控制所需的内部数据。这种内部信息和进程是分开的，因为操作系统信息不允许被进程直接访问。上下文包括操作系统管理进程以及处理器正确执行进程所需要的所有信息，包括各种处理器寄存器的内容，如程序计数器和数据寄存器。它还包括操作系统使用的信息，如进程优先级以及进程是否在等待特定I/O事件的完成。

2.6列出并简要介绍操作系统的五种典型存储管理职责。

进程隔离：操作系统必须保护独立的进程，防止互相干涉数据和存储空间。

自动分配和管理：程序应该根据需要在存储层次间动态的分配，分配对程序员是透明的。因此，程序员无需关心与存储限制有关的问题，操作系统有效的实现分配问题，可以仅在需要时才给作业分配存储空间。

2.7解释实地址和虚地址的区别。

虚地址指的是存在于虚拟内存中的地址，它有时候在磁盘中有时候在主存中。实地址指的是主存中的地址。

2.8描述轮循调度技术。

轮循调度是一种调度算法，所有的进程存放在一个环形队列中并按固定循序依次激活。因为等待一些事件（例如：等待一个子进程或一个I/O操作）的发生而不能被处理的进程将控制权交给调度器。 2.9解释单体内核和微内核的区别。

单体内核是一个提供操作系统应该提供的功能的大内核，包括调度、文件系统、网络、设备驱动程序、存储管理等。内核的所有功能成分都能够访问它的内部数据结构和程序。典型情况下，这个大内核是作为一个进程实现的，所有元素都共享相同的地址空间。微内核是一个小的有特权的操作系统内核，只提供包括进程调度、内存管理、和进程间通信等基本功能，要依靠其他进程担当起和操作系统内核联系作用。

2.10什么是多线程？

多线程技术是指把执行一个应用程序的进程划分成可以同时运行的多个线程。

习题

2.1假设我们有一台多道程序的计算机，每个作业有相同的特征。在一个计算周

期T中，一个作业有一半时间花费在I/O上，另一半用于处理器的活动。每个作业一共运行N个周期。假设使用简单的循环法调度，并且I/O操作可以与处理器操作重叠。定义以下量： ·时间周期=完成任务的实际时间

·吞吐量=每个时间周期T内平均完成的作业数目

·处理器使用率=处理器活跃（不是处于等待）的时间的百分比

当周期T分别按下列方式分布时，对1个、2个和4个同时发生的作业，请计算这些量：

a. 前一般用于I/O，后一半用于处理器。

b. 前四分之一和后四分之一用于I/O，中间部分用于处理器。 答：（a）和（b）的答案相同。尽管处理器活动不能重叠，但I/O操作能。 一个作业 时间周期=NT 处理器利用率=50﹪ 两个作业 时间周期=NT 处理器利用率=100﹪ 四个作业 时间周期=（2N-1）NT 处理器利用率=100﹪

2.2I/O限制的程序是指如果单独运行，则花费在等待I/O上的时间比使用处理器的时间要多的程序。处理器限制的程序则相反。假设短期调度算法偏爱那些在近期石油处理器时间较少的算法，请解释为什么这个算法偏爱I/O限制的程序，但是并不是永远不受理处理器限制程序所需的处理器时间？

受I/O限制的程序使用相对较少的处理器时间，因此更受算法的青睐。然而，受处理器限制的进程如果在足够长的时间内得不到处理器时间，同一算法将允许处理器去处理此进程，因为它最近没有使用过处理器。这样，一个处理器限制的进程不会永远得不到处理器。

2.3请对优化分时系统的调度策略和用于优化多道程序批处理系统的调度策略

进行比较。

分时系统关注的是轮转时间，时间限制策略更有效是因为它给所有进程一个较短的处理时间。批处理系统关心的是吞吐量，更少的上下文转换和更多的进程处理时间。因此，最小的上下文转换最高效。

2.4系统调用的目的是什么?如何实现与操作系统相关的的系统调用以及与双重

模式（内核模式和用户模式）操作相关的系统调用？

系统调用被应用程序用来调用一个由操作系统提供的函数。通常情况下，系统调用最终转换成在内核模式下的系统程序。

2.5在IBM的主机操作系统OS/390中，内核中的一个重要模块是系统资源管理程序（System Resource Manager,SRM），他负责地址空间（进程）之间的资源分配。SRM是的OS/390在操作系统中具有特殊性，没有任何其他的主机操作系统，当然没有任何其他类型的操作系统可以比得上SRM所实现的功能。资源的概念包括处理器、实存和I/O通道，SRM累计处理器、I/O通道和各种重要数据结构的利用率，它的目标是基于性能监视和分析提供最优的性能，其安装设置了以后的各种性能目标作为SRM的指南，这会基于系统的利用率动态的修改安装和作业性能特点。SRM依次提供报告，允许受过训练的操作员改进配置和参数设置，以改善用户服务。

现在关注SRM活动的一个实例。实存被划分为成千上万个大小相等的块，称为帧。每个帧可以保留一块称为页的虚存。SRM每秒大约接受20次控制，并在互相之间以及每个页面之间进行检查。如果页未被引用或被改变，计数器增1。一段时间后，SRM求这些数据的平均值，以确定系统中一个页面未曾被触及的平均秒数。这样做的目的是什么？SRM将采取什么动作？

操作系统可以查看这些数据已确定系统的负荷，通过减少加在系统上的

活跃作业来保持较高的平均利用率。典型的平均时间应该是两分钟以上，这个平均时间看起来很长，其实并不长。

第3章 进程描述和控制

复习题：

3.1 什么是指令跟踪？

答：指令跟踪是指为该进程而执行的指令序列。 3.2 通常那些事件会导致创建一个进程？

答：新的批处理作业；交互登录；操作系统因为提供一项服务而创建；由现有的进程派生。（详情请参考表3.1）

3.3 对于图3.6中的进程模型，请简单定义每个状态。

答：运行态：该进程正在执行。就绪态：进程做好了准备，只要有机会就开始执行。阻塞态：进程在某些事件发生前不能执行，如I/O操作完成。新建态：刚刚创建的进程，操作系统还没有把它加入到可执行进程组中。退出态：操作系统从可执行进程组中释放出的进程，或者是因为它自身停止了，或者是因为某种原因被取消。

3.4 抢占一个进程是什么意思？

答：处理器为了执行另外的进程而终止当前正在执行的进程，这就叫进程抢占。 3.5 什么是交换，其目的是什么？

答：交换是指把主存中某个进程的一部分或者全部内容转移到磁盘。当主存中没有处于就绪态的进程时，操作系统就把一个阻塞的进程换出到磁盘中的挂起队列，从而使另一个进程可以进入主存执行。 3.6 为什么图3.9（b）中有两个阻塞态？

答：有两个独立的概念：进程是否在等待一个事件（阻塞与否）以及进程是否已经被换出主存（挂起与否）。为适应这种2*2的组合，需要两个阻塞态和两个挂起态。

3.7 列出挂起态进程的4个特点。

答：1.进程不能立即执行。2.进程可能是或不是正在等待一个事件。如果是，阻塞条件不依赖于挂起条件，阻塞事件的发生不会使进程立即被执行。3.为了阻止进程执行，可以通过代理把这个进程置于挂起态，代理可以是进程自己，也可以是父进程或操作系统。4.除非代理显式地命令系统进行状态转换，否则进程无法从这个状态中转移。

3.8 对于哪类实体，操作系统为了管理它而维护其信息表？

答：内存、I/O、文件和进程。 3.9 列出进程控制块中的三类信息。

答：进程标识，处理器状态信息，进程控制信息。 3.10 为什么需要两种模式（用户模式和内核模式）？

答：用户模式下可以执行的指令和访问的内存区域都受到限制。这是为了防止操作系统受到破坏或者修改。而在内核模式下则没有这些限制，从而使它能够完成其功能。

3.11 操作系统创建一个新进程所执行的步骤是什么？

3.12

3.13 3.14

3.1.

3.2.

答：1.给新进程分配一个唯一的进程标识号。2.给进程分配空间。3.初始化进程控制块。4.设置正确的连接。5.创建或扩充其他的数据结构。 中断和陷阱有什么区别？

答：中断与当前正在运行的进程无关的某些类型的外部事件相关，如完成一次I/O操作。陷阱与当前正在运行的进程所产生的错误或异常条件相关，如非法的文件访问。

举出中断的三个例子。

答：时钟终端，I/O终端，内存失效。 模式切换和进程切换有什么区别？ 答：发生模式切换可以不改变当前正处于运行态的进程的状态。发生进程切换时，一个正在执行的进程被中断，操作系统指定另一个进程为运行态。进程切换需要保存更多的状态信息。

习题：

给出操作系统进行进程管理时的五种主要活动，并简单描述为什么需要它们。 答：用户进程和系统进程创建及删除。系统中的进程可以为信息共享、运算加速、模块化和方便并发地执行。而并发执行需要进程的创建和删除机制。当进程创建或者运行时分配给它需要的资源。当进程终止时，操作系统需要收回任何可以重新利用的资源。

进程的暂停和继续执行。在进程调度中，当进程在等待某些资源时，操作系统需要将它的状态改变为等待或就绪状态。当所需要的资源可用时，操作系统需要将它的状态变为运行态以使其继续执行。

提供进程的同步机制。合作的进程可能需要共享数据。对共享数据的并行访问可能会导致数据冲突。操作系统必须提供进程的同步机制以使合作进程有序地执行，从而保证数据的一致性。

提供进程的通信机制。操作系统下执行的进程既可以是独立进程也可以是合作进程。合作进程之间必须具有一定的方式进行通信。 提供进程的死锁解决机制。在多道程序环境中，多个进程可能会竞争有限的资源。如果发生死锁，所有的等待进程都将永远不能由等待状态再变为运行态，资源将被浪费，工作永远不能完成。

在[PINK89] 中为进程定义了以下状态：执行（运行）态、活跃（就绪）态、阻塞态和挂起态。当进程正在等待允许使用某一资源时，它处于阻塞态；当进程正在等待它已经获得的某种资源上的操作完成时，它处于挂起态。在许多操作系统中，这两种状态常常放在一起作为阻塞态，挂起态使用本章中给出的定义。请比较这两组定义的优点。

答：[PINK89]中引用了以下例子来阐述其中阻塞和挂起的定义：

假设一个进程已经执行了一段时间，它需要一个额外的磁带设备来写出一个临时文件。在它开始写磁带之前，进程必须得到使用某一设备的许可。当它做出请求时，磁带设备可能并不可用，这种情况下，该进程就处于阻塞态。假设操作系统在某一时刻将磁带设备分配给了该进程，这时进程就重新变为活跃态。当进程重新变为执行态时要对新获得的磁带设备进行写操作。这时进程变为挂起态，等待该磁带上当前所进行的写操作完成。

这种对等待某一设备的两种不同原因的区别，在操作系统组织其工作时是非常有用的。然而这并不能表明那些进程是换入的，那些进程是换出的。后一种区别是

必需的，而且应该在进程状态中以某种形式表现出来。

3.3. 对于图3.9（b）中给出的7状态进程模型，请仿照图3.8（b）画出它的排队图。

答：图9.3给出了单个阻塞队列的结果。该图可以很容易的推广到多个阻塞队列的情形。

3.4. 考虑图3.9（b）中的状态转换图。假设操作系统正在分派进程，有进程处于就绪

态和就绪/挂起态，并且至少有一个处于就绪/挂起态的进程比处于就绪态的所有进程的优先级都高。有两种极端的策略：（1）总是分派一个处于就绪态的进程，以减少交换；（2）总是把机会给具有最高优先级的进程，即使会导致在不需要交换时进行交换。请给出一种能均衡考虑优先级和性能的中间策略。

答：对于一个就绪/挂起态的进程，降低一定数量（如一或两个）优先级，从而保证只有当一个就绪/挂起态的进程比就绪态的进程的最高优先级还高出几个优先级时，它才会被选做下一个执行。

3.5. 表3.13给出了VAX/VMS操作系统的进程状态。

a. 请给出这么多种等待状态的理由。

b. 为什么以下状态没有驻留和换出方案：页错误等待、也冲突等待、公共事件等

待、自由页等待和资源等待。

c. 请画出状态转换图，并指出引发状态装换的原因。 答：

a. 每一种等待状态都有一个单独的队列与其相关联。当影响某一等待进程的事

件发生时，把等待进程分成不同的队列就减少了定位这一等待进程所需的工作量。例如，当一个页错误完成时，调度程序就可以在页错误等待队列中找到等待的进程。

b. 在这些状态下，允许进程被换出只会使效率更低。例如，当发生页错误等待

时，进程正在等待换入一个页从而使其可以执行，这是将进程换出是毫无意义的。

c. 可以由下面的进程状态转换表得到状态转换图。 当前状态 下一状态 当前正在执可计算（驻可计算（换各种等待状各种等待状行 留） 出） 态（驻留） 态（换出） 当前正在执 重调度 等待 行 可计算（驻调度 换出 留） 可计算（换 换入 出） 各种等待状 事件发生 换出 态（驻留） 各种等待状 事件发生 态（换出） 3.6. VAM/VMS操作系统采用了四种处理器访问模式，以促进系统资源在进程间的保护和共享。访问模式确定：

? 指令执行特权：处理器将执行什么指令。

? 内存访问特权：当前指令可能访问虚拟内存中的哪个单元。 四种模式如下：

? 内核模式：执行VMS操作系统的内核，包括内存管理、中断处理和I/O操作。 ? 执行模式：执行许多操作系统服务调用，包括文件（磁盘和磁带）和记录管

理例程。

? 管理模式：执行其他操作系统服务，如响应用户命令。

? 用户模式：执行用户程序和诸如编译器、编辑器、链接程序、调试器之类的

实用程序。

在较少特权模式执行的进程通常需要调用在较多特权模式下执行的过程，例如，一个用户程序需要一个操作系统服务。这个调用通过使用一个改变模式（简称CHM）指令来实现，该指令将引发一个中断，把控制转交给处于新的访问模式下的例程，并通过执行REI（Return from Exception or Interrupt，从异常或中断返回）指令返回。

a. 很多操作系统有两种模式，内核和用户，那么提供四种模式有什么优点和缺

点？

b. 你可以举出一种有四种以上模式的情况吗？ 答：

a. 四种模式的优点是对主存的访问控制更加灵活，能够为主存提供更好的保护。

缺点是复杂和处理的开销过大。例如，程序在每一种执行模式下都要有一个独立的堆栈。

b. 原则上，模式越多越灵活，但是四种以上的模式似乎很难实现。

3.7. 在前面习题中讨论的VMS方案常常称为环状保护结构，如图3.18所示。3.3节所

描述的简单的内核/用户方案是一种两环结构，[SILB04]指出了这种方法的问题：环状（层次）结构的主要缺点是它不允许我们实施须知原理，特别地，如果一个对象必须在域Dj中可访问，但在域Di中不可访问，则必须有就j

b. 请给出环状结构操作系统解决这个问题的一种方法。 答：

a. 当j

的信息比Di中的更具有特权或者要求的安全性更高，那么这种限制就是合理的。然而，通过以下方法却可以绕过这种安全策略。一个运行在Dj中的进程可以读取Dj中的数据，然后把数据复制到Di中。随后，Di中的进程就可以访问这些信息了。

b. 有一种解决这一问题的方法叫做可信系统，我们将在16章中进行讨论。 3.8. 图3.7（b）表明一个进程每次只能在一个事件队列中。

a. 是否能够允许进程同时等待一个或多个事件？请举例说明。 b. 在这种情况下，如何修改图中的排队结构以支持这个新特点？ 答：

a. 一个进程可能正在处理从另一个进程收到的数据并将结果保存到磁盘上。如果

当前在另一个进程中正有数据在等待被取走，进程就可以继续获得数据并处理它。如果前一个写磁盘操作已经完成，并且有处理好的数据在等待写出，那么进程就可以继续写磁盘。这样就可能存在某一时刻，进程即在等待从输入进程获得数据，又在等待磁盘可用。 b. 有很多种方法解决这一问题。可以使用一种特殊的队列，或者将进程放入两个

独立的队列中。不论采用哪种方法，操作系统都必须处理好细节工作，使进程

相继地关注两个事件的发生。

3.9. 在很多早期计算机中，中断导致寄存器值被保存在与给定的中断信息相关联的固

定单元。在什么情况下这是一种实用的技术？请解释为什么它通常是不方便的。 答：这种技术是基于被中断的进程A在中断响应之后继续执行的假设的。但是，在通常情况下，中断可能会导致另一个进程B抢占了进程A。这是就必须将进程A的执行状态从与中断相关的位置复制到与A相关的进程描述中。然而机器却有可能仍将它们保存到前一位置。参考：[BRIN73]。

3.10. 3.4节曾经讲述过，由于在内核模式下执行的进程是不能被抢占的，因此UNIX不

适用于实时应用。请阐述原因。

答：由于存在进程不能被抢占的情况（如在内核模式下执行的进程），操作系统不可能对实时需求给予迅速的反应。

第四章 线程、对称多处理和微内核

复习题：

4.1 表3.5列出了在一个没有线程的操作系统中进程控制块的基本元素。对于多线程系

统，这些元素中那些可能属于线程控制块，那些可能属于进程控制块？

答：这对于不同的系统来说通常是不同的，但一般来说，进程是资源的所有者，而每个线程都有它自己的执行状态。关于表3.5中的每一项的一些结论如下：进程标识：进程必须被标识，而进程中的每一个线程也必须有自己的ID。处理器状态信息：这些信息通常只与进程有关。进程控制信息：调度和状态信息主要处于线程级；数据结构在两级都可出现；进程间通信和线程间通信都可以得到支持；特权在两级都可以存在；存储管理通常在进程级；资源信息通常也在进程级。 4.2 请列出线程间的模式切换比进程间的模式切换开销更低的原因。

答：包含的状态信息更少。

4.3 在进程概念中体现出的两个独立且无关的特点是什么？

答：资源所有权和调度/执行。

4.4 给出在单用户多处理系统中使用线程的四个例子。

答：前台和后台操作，异步处理，加速执行和模块化程序结构。 4.5 哪些资源通常被一个进程中的所有线程共享？

答：例如地址空间，文件资源，执行特权等。 4.6 列出用户级线程优于内核级线程的三个优点。

答：1.由于所有线程管理数据结构都在一个进程的用户地址空间中，线程切换不需要内核模式的特权，因此，进程不需要为了线程管理而切换到内核模式，这节省了在两种模式间进行切换（从用户模式到内核模式；从内核模式返回用户模式）的开销。2.调用可以是应用程序专用的。一个应用程序可能倾向于简单的轮询调度算法，而另一个应用程序可能倾向于基于优先级的调度算法。调度算法可以去适应应用程序，而不会扰乱底层的操作系统调度器。3.用户级线程可以在任何操作系统中运行，不需要对底层内核进行修改以支持用户级线程。线程库是一组供所有应用程序共享的应用级软件包。

4.7 列出用户级线程相对于内核级线程的两个缺点。

答：1.在典型的操作系统中，许多系统调用都会引起阻塞。因此，当用户级线程执行一个系统调用时，不仅这个线程会被阻塞，进程中的所有线程都会被阻塞。2.在

纯粹的用户级进程策略中，一个多线程应用程序不能利用多处理技术。内核一次只把一个进程分配给一个处理器，因此一次进程中只能有一个线程可以执行。 4.8 定义jacketing。

答：Jacketing通过调用一个应用级的I/O例程来检查I/O设备的状态，从而将一个产生阻塞的系统调用转化为一个不产生阻塞的系统调用。 4.9 简单定义图4.8中列出的各种结构。

答：SIMD：一个机器指令控制许多处理部件步伐一致地同时执行。每个处理部件都有一个相关的数据存储空间，因此，每条指令由不同的处理器在不同的数据集合上执行。MIMD：一组处理器同时在不同的数据集上执行不同的指令序列。主/从：操作系统内核总是在某个特定的处理器上运行，其他处理器只用于执行用户程序，还可能执行一些操作系统实用程序。SMP：内核可以在任何处理器上执行，并且通常是每个处理器从可用的进程或线程池中进行各自的调度工作。集群：每个处理器都有一个专用存储器，而且每个处理部件都是一个独立的计算机。 4.10 列出SMP操作系统的主要设计问题。

答：同时的并发进程或线程，调度，同步，存储器管理，可靠性和容错。

4.11 给出在典型的单体结构操作系统中可以找到且可能是微内核操作系统外部子系统

中的服务和功能。

答：设备驱动程序，文件系统，虚存管理程序，窗口系统和安全服务。 4.12 列出并简单解释微内核设计相对于整体式设计的七个优点。

答：一致接口：进程不需要区分是内核级服务还是用户级服务，因为所有服务都是通过消息传递提供的。可扩展性：允许增加新的服务以及在同一个功能区域中提供多个服务。灵活性：不仅可以在操作系统中增加新功能，还可以删减现有的功能，以产生一个更小、更有效的实现。可移植性：所有或者至少大部分处理器专用代码都在微内核中。因此，当把系统移植到一个处理器上时只需要很少的变化，而且易于进行逻辑上的归类。可靠性：小的微内核可以被严格地测试，它使用少量的应用程序编程接口（API），这就为内核外部的操作系统服务产生高质量的代码提供了机会。分布式系统支持：微内核通信中消息的方向性决定了它对分布式系统的支持。面向对象操作系统环境：在微内核设计和操作系统模块化扩展的开发中都可以借助面向对象方法的原理。

4.13 解释微内核操作系统可能存在的性能缺点。

答：通过微内核构造和发送信息、接受应答并解码所花费的时间比一次系统调用的时间要多。

4.14 列出即使在最小的微内核操作系统中也可以找到的三个功能。

答：低级存储器管理，进程间通信（IPC）以及I/O和中断管理。 4.15 在微内核操作系统中，进程或线程间通信的基本形式是什么？

答：消息。

习题：

4.1. 一个进程中的多个线程有以下两个优点：（1）在一个已有进程中创建一个新线程

比创建一个新进程所需的工作量少；（2）在同一个进程中的线程间的通信比较简单。请问同一个进程中的两个线程间的模式切换与不同进程中的两个线程间的模式切换相比，所需的工作量是否要少？

答：是的，因为两个进程间的模式切换要储存更多的状态信息。

4.2. 在比较用户级线程和内核级线程时曾指出用户级线程的一个缺点，即当一个用户

4.3.

4.4.

4.5.

4.6.

级线程执行系统调用时，不仅这个线程被阻塞，而且进程中的所有线程都被阻塞。请问这是为什么？

答：因为对于用户级线程来说，一个进程的线程结构对操作系统是不可见的，而操作系统的调度是以进程为单位的。 在OS/2中，其他操作系统中通用的进程概念被分成了三个独立类型的实体：会话、进程和线程。一个会话是一组与用户接口（键盘、显示器、鼠标）相关联的一个或多个进程。会话代表了一个交互式的用户应用程序，如字处理程序或电子表格，这个概念使得PC用户可以打开一个以上的应用程序，在屏幕上显示一个或更多个窗口。操作系统必须知道哪个窗口，即哪个会话是活跃的，从而把键盘和鼠标的输入传递个相应的会话。在任何时刻，只有一个会话在前台模式，其他的会话都在后台模式，键盘和鼠标的所有输入都发送给前台会话的一个进程。当一个会话在前台模式时，执行视频输出的进程直接把它发送到硬件视频缓冲区。当一个会话在后台时，如果该会话的任何一个进程的任何一个线程正在执行并产生屏幕输出，则这个输出被送到逻辑视频缓冲区；当这个会话返回前台时，屏幕被更新，为新的前台会话反映出逻辑视频缓冲区中的当前内容。

有一种方法可以把OS/2中与进程相关的概念的数目从3个减少到2个。删去会话，把用户接口（键盘、显示器、鼠标）和进程关联起来。这样，在某一时刻，只有一个进程处于前台模式。为了进一步地进行构造，进程可以被划分成线程。 a. 使用这种方法会丧失什么优点？

b. 如果继续使用这种修改方法，应该在哪里分配资源（存储器、文件等）：在进

程级还是线程级？ 答：

a. 会话的使用非常适合个人计算机和工作站对交互式图形接口的需求。它为明

确图形输出和键盘/鼠标输入应该被关联到什么位置提供了一个统一的机制，减轻了操作系统的工作负担。

b. 应该和其他的进程/线程系统一样，在进程级分配地址空间和文件。

考虑这样一个环境，用户级线程和内核级线程呈一对一的映射关系，并且允许进程中的一个或多个线程产生会引发阻塞的系统调用，而其他线程可以继续运行。解释为什么这个模型可以使多线程程序比在单处理器机器上的相应的单线程程序运行速度更快？

答：问题在于机器会花费相当多的时间等待I/O操作的完成。在一个多线程程序中，可能一个内核级线程会产生引发阻塞的系统调用，而其他内核级线程可以继续执行。而在单处理器机器上，进程则必须阻塞知道所有的系统调用都可以继续运行。参考：[LEWI96]

如果一个进程退出时，该进程的某些线程仍在运行，请问他们会继续运行吗？ 答：不会。当一个进程退出时，会带走它的所有东西——内核级线程，进程结构，存储空间——包括线程。参考：[LEWI96]

OS/390主机操作系统围绕着地址空间和任务的概念构造。粗略说来，一个地址空间对应于一个应用程序，并且或多或少地对应于其他操作系统中的一个进程；在一个地址空间中，可以产生一组任务，并且它们可以并发执行，这大致对应于多线程的概念。管理任务结构有两个主要的数据结构。地址空间控制块（ASCB）含有OS/390所需要的关于一个地址空间的信息，而不论该地址空间是否在执行。ASCB中的信息包括分派优先级、分配给该地址空间的实存和虚存、该地址空间中就绪的任务数以及是否每个都被换出。一个任务控制块（TCB）标识一个正在执行

的用户程序，它含有在一个地址空间中管理该任务所需要的信息，包括处理器状态信息、指向该任务所涉及到的程序的指针和任务执行结构。ASCB是在系统存储器中保存的全局结构，而TCB是保存在各自的地址空间中的局部结构。请问把控制信息划分成全局和局部两部分有什么好处？

答：关于一个地址空间的尽可能多的信息可以随地址空间被换出，从而节约了主存。

4.7. 一个多处理系统有8个处理器和20个附加磁带设备。现在有大量的作业提交给该

系统，完成每个作业最多需要4个磁带设备。假设每个作业开始运行时只需要3个磁带设备，并且在很长时间内都只需要这3个设备，而只是在最后很短的一段时间内需要第4个设备以完成操作。同时还假设这类作业源源不断。

a. 假设操作系统中的调度器只有当4个磁带设备都可用时才开始一个作业。当作

业开始时，4个设备立即被分配给它，并且直到作业完成时才被释放。请问一次最多可以同时执行几个作业？采用这种策略，最多有几个磁带设备可能是空闲的？最少有几个？ b. 给出另外一种策略，要求其可以提高磁带设备的利用率，并且同时可以避免系

统死锁。分析最多可以有几个作业同时执行，可能出现的空闲设备的范围是多少。 答：

a. 采用一个保守的策略，一次最多同时执行20/4=5个作业。由于分配各一个任

务的磁带设备最多同时只有一个空闲，所以在同一时刻最多有5个磁带设备可能是空闲的。在最好的情况下没有磁带设备空闲。

b. 为了更好的利用磁设备，每个作业在最初只分配三个磁带设备。第四个只有

的需要的时候才分配。在这种策略中，最多可以有20/3=6个作业同时执行。最少的空闲设备数量为0，最多有2个。参考：Advanced Computer Architectrue,K.Hwang,1993.

4.8. 在描述Solaris用户级线程状态时，曾表明一个用户级线程可能让位于具有相同优

先级的另一个线程。请问，如果有一个可运行的、具有更高优先级的线程，让位函数是否还会导致让位于具有相同优先级或更高优先级的线程？

答：任何一个可能改变线程优先级或者使更高优先级的线程可运行的调用都会引起调度，它会依次抢占低优先级的活跃线程。所以，永远都不会存在一个可运行的、具有更高优先级的线程。参考：[LEVI96]

第五章 并发性：互斥和同步

复习题：

5.1列出与并发相关的四种设计问题

答：进程间的交互，共享资源之间的竞争，多个进程的同步问题，对进程的处理器时间分配问题

5.2列出并发的三种上下文

答：多个应用程序，结构化应用程序，操作系统结构 5.3执行并发进程的最基本要求是什么？ 答：加强互斥的能力

5.4列出进程间的三种互相知道的程度，并简单地给出各自的定义。

答：进程间互相不知道对方：这是一些独立的进程，他们不会一起工作。进程间间接知道对

方：这些进程并不需要知道对方的进程ID号，但他们共享访问某些对象，如一个I/O缓冲区。进程间直接知道对方：这些进程可以通过进程ID号互相通信，用于合作完成某些活动。 5.5竞争进程和合作进程进程间有什么区别。

答：竞争进程需要同时访问相同的资源，像磁盘，文件或打印机。合作进程要么共享访问一个共有的资源，像一个内存访问区，要么就与其他进程相互通信，在一些应用程序或活动上进行合作。

5.6列出与竞争进程相关的三种控制问题，并简单地给出各自的定义。

答：互斥：竞争进程仅可以访问一个临界资源（一次仅有一个进程可以访问临界资源），并发机制必须满足一次只有一个进程可以访问临界资源这个规则。死锁：如果竞争进程需要唯一的访问多于一个资源，并且当一个进程控制着一个进程，且在等待另一个进程，死锁可能发生。饥饿：一组进程的一个可能会无限期地拒绝进入到一个需要资源，因为其他 成员组成垄断这个资源。 5.7列出对互斥的要求。

答：1.必须强制实施互斥：在具有关于相同资源或共享对象的临界区的所有进程中，一次只允许一个进程进入临界区。2.一个在临界区停止的进程必须不干涉其他进程。3.绝不允许出现一个需要访问临界区的进程被无限延迟的情况，即不会饿死或饥饿。4.当没有进程在临界区中时，任何需要进入临界区的进程必须能够立即进入。5.对相关进程的速度和处理器的数目没有任何要求和限制。6.一个进程驻留在临界区中的时间是有限的。 5.8在信号量上可以执行什么操作。

答：1.一个信号量可以初始化成非负数。2.wait操作使信号量减1，如果值为负数，那么进程执行wait就会受阻。3signal操作使信号量增加1，如果小于或等于0，则被wait操作阻塞的进程被解除阻塞。

5.9.二元信号量与一般信号量有什么区别。

答：二元信号量只能取0或1，而一般信号量可以取任何整数。 5.10强信号量与弱信号量有什么区别。 答：强信号量要求在信号量上等待的进程按照先进先出的规则从队列中移出。弱信号量没有此规则。

5.11.什么是管程。

答：管程是由一个或多个过程，一个初始化序列和局部数据组成的软件模块。 5.12对于消息，有阻塞和无阻塞有什么区别？ 答：

5.13.通常与读者-写者问题相关联的有哪些条件？

答：1.任意多的读进程可以同时读这个文件，2.一次只有一个写进程可以往文件中写，3.如果一个写进程正在往文件中写时，则禁止任何读进程读文件。

习题： 5.1 答：b.协同程序read读卡片，将字符赋给一个只有一个字大小的缓冲区rs然后在赋给squash协同程。协同程序Read在每副卡片图像的后面插入一个额外的空白。协同程序squash不需要知道任何关于输入的八十个字符的结构，它简单的查找成对出现的星号，然后将更改够的字符串经由只有一个字符大小的缓冲sp，传递给协同程序print。最后协同程序print简单的接受到来的字符串，并将他们打印在包含125个字符的行中。 5.2．考虑一个并发程序，它有两个进程p和q，定义如下。A.B.C.D和E是任意的原子语句。假设住程序执行两个进程的parbegin

Void p() void q() { A; { D; B; E; C; } }

答：ABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;DEABC;DAEBC;DABEC;DABCE; 5.3考虑下面的程序

const int n=50; int tally;

void total() { int count;

for(count =1;count <=n;count ++) {tally++; } }

void main() {

tally =0;

parbegin(total(),total(); write(tally);

}

答：a.随意一看,tally值的范围好像是落在[50,100]这个区间里,因为当没有互斥时可以从0直接增加到50.这一基本论点是当并发的运行这两进程时,我们不可能得到一个比连续执行单一某进程所得tally值还低的一个最终tally值.但是考虑下面由这两进程按交替顺序执行载入,增加,存储的情况,同时变更这个共享变量的取值:

1.进程A载入tally值,tally值加到1,在此时失去处理器(它已经增加寄存器的值到1,但是还没有存储这个值).

2.进程B载入tally值(仍然是0),然后运行完成49次增加操作,在它已经将49这个值存储给共享变量tally后,失去处理器控制权.

3.进程A重新获得处理器控制权去完成它的第一次存储操作(用1去代替先前的49这个tally值),此时被迫立即放弃处理器.

4.进程B重新开始,将1(当前的tally值)载入到它自己的寄存器中,但此时被迫放弃处理器(注意这是B的最后一次载入).

5.进程A被重新安排开始,但这次没有被中断,直到运行完成它剩余的49次载入,增加和存储操作,结果是此时tally值已经是50.

6.进程B在它终止前完成仅有的最后一次增加和存储操作.它的寄存器值增至2,同时存储这个值做为这个共享变量的最终结果.

一些认为会出现低于2这个值的结果,这种情况不会出现.这样tally值的正确范围是[2,100].

b.对一般有N个进程的情况下,tally值的最终范围是[2,N*50],因为对其他所有进程来说,从最初开始运行到在第五步完成.但最后都被进程B破坏掉它们的最终结果. 5.4.忙等待是否总是比阻塞等待效率低（根据处理器的使用时间）？请解释。 答：就一般情况来说是对的,因为忙等待消耗无用的指令周期.然而,有一种特殊情况,当进程执行到程序的某一点处,在此处要等待直到条件满足,而正好条件已满足,此时忙等待会立即有

结果,然而阻塞等待会消耗操作系统资源在换出与换入进程上. 5.5考虑下面的程序

boolean blocked[2]; int rurn;

void P(int id) {

While (true) {

While(turn!=id); {

While(blocked[1-!id] /*do nothing*/; Turn =id; } }

Void main () {

Blocked[0]=false; Blocked[1]=false; Turn=0;

Parbegin(P(0),P(1)); }

这是【HYMA66】中提出的解决互斥问题的一种方法。请举出证明该方法不正确的一个反例。

答：考虑这种情况:此时turn=0,进程P(1)使布尔变量blocked[1]的值为true,在这时发现布尔变量blocked[0]的值为false,然后P(0)会将true值赋予blocked[0]

,此时turn=0,P(0)进入临界区,P(1)在将1赋值给turn后,也进入了临界区.

5.6解决互斥的另一种软件方法是lamport的面包店（bakery）算法，之所以起这个名字，是因为它的思想来自于面包店或其他商店中，每个顾客在到达时都得到一个有编号的票，并按票号依次得到服务，算法如下：

Boolean choosing[n]; Int number[n]; While (true) {

Choosing[i]=true;

Number[i]=1+getmax(number[],n)； Choosing[i]=false; For(int j=0;j

While (choosing[j]) {}

While ((number[j]!=0)&&(number[j],j)<(number[i],i) {} }

/*critical section*/ Number[i]=0; /*remainder*/; }

数组choosing和number分别被初始化成false和0，每个数组的第i个元素可以由进程i读或写，但其他进程只能读。符号（a，b）<（c，d）被定义成 （a，c）或（a=c且b

答：a.当一个进程希望进入临界区时,它被分配一个票号.分配的票号是通过在目前那些等待进入临界区的进程所持票号和已经在临界区的进程所持票号比较,所得最大票号再加1得到的.有最小票号的进程有最高的优先级进入临界区.当有多个进程拥有同样的票号时,拥有最小数字号进入临界区.当一个进程退出临界区时,重新设置它的票号为0.

b.如果每个进程被分配唯一的一个进程号,那么总会有一个唯一的,严格的进程顺序.因此,死锁可以避免.

c.为了说明互斥,我们首先需要证明下面的定理:如果Pi在它的临界区,Pk已经计算出来它的number[k],并试图进入临界区,此时就有下面的关系式: ( number[i], i ) < ( number[k], k ).为证明定理,定义下面一些时间量:

Tw1:Pi最后一次读choosing[k], 当 j=k,在它的第一次等待时,因此我们在Tw1处有choosing[k] = false.

Tw2:Pi开始它的最后执行, 当j=k,在它的第二次while循环时,因此我们有Tw1 < Tw2.

Tk1:Pk在开始repeat循环时;Tk2:Pk完成number[k]的计算; Tk3: Pk设置choosing[k]为false时.我们有Tk1

因为在Tw1处,choosing[k]=false,我们要么有Tw1

5.7当按图5.2的形式使用一个专门机器指令提供互斥时，对进程在允许访问临界区之前必须等待多久没有控制。设计一个使用testset指令的算法，且保证任何一个等待进入临界区的进程在n-1个turn内进入，n是要求访问临界区的进程数，turn是指一个进程离开临界区而另一个进程获准访问这个一个事件。

答：以下的程序由[SILB98]提供： var j: 0..n-1; key: boolean; repeat

waiting[i] := true; key := true;

while waiting[i] and key do key := testset(lock); waiting[i] := false;

< critical section > j := i + 1 mod n;

while (j ≠ i) and (not waiting[j]) do j := j + 1 mod n; if j = i then lock := false else waiting := false; < remainder section > Until

这个算法用最普通的数据结构：var waiting: array [0..n – 1] of boolean Lock：boolean

这些数据结构被初始化成假的，当一个进程离开它的临界区，它就搜索waiting

的循环队列

5.8考虑下面关于信号量的定义： Void semWait(s) {

If (s.count>0) {

s.count--; } Else {

Place this process in s.queue; Block; } }

Void semSignal(s) {

If (there is at liast one process blocked on semaphore) {

Remove a process P from s.queue; Place process P on ready list; }

Else

s.count++; }

比较这个定义和图5.3中的定义，注意有这样的一个区别：在前面的定义中，信号量永远不会取负值。当在程序中分别使用这两种定义时，其效果有什么不同？也就是说，是否可以在不改变程序意义的前提下，用一个定义代替另一个？

答：这两个定义是等价的，在图5.3的定义中，当信号量的值为负值时，它的值代表了有多少个进程在等待；在此题中的定义中，虽然你没有关于这方面的信息，但是这两个版本的函数是一样的。

5.9可以用二元信号量实现一般信号量。我们使用semWaitB操作和semSignalB操作以及两个二元信号量delay和mutex。考虑下面的代码 Void semWait(semaphor s)

{

semWaitB(mutex); s--; if (s<0) {

semSignalB(mutex); semWaitB(delay); } Else

Semsignalb(mutex) }

Void semSignal(semaphore s); {

semWaitB(mutex); s++; if(s<=0)

semSignalB(delay); semSignalB(mutex); }

最初。S被设置成期待的信号量值，每个semwait操作将信号量减1，每个semsignal操作将信号量加1.二元信号量mutex被初始化成1，确保在更新在更新s时保证互斥，二元信号量delay被初始化成0，用于挂起进程，

上面的程序有一个缺点，证明这个缺点，并提出解决方案。提示：假设两个进程，每个都在s初始化为0时调用semwait（s）,当第一个刚刚执行了semsignalb（mutex）但还没有执行semwaitb（delay），第二个调用semwait（s）并到达同一点。现在需要做的就是移动程序的一行.

答：假设两个进程，每个都在s被初始化成0时调用semWait（s），当第一个刚执行了semSignalB（mutex）但还没有执行semWaitB（delay）时，第二个调用semWait（s）并到达同一点。因为s=-2 mutex没有锁定，假如有另外两个进程同时成功的调用semSignal（s），他们接着就会调用semsignalb（delay），但是第二个semsignalb没有被定义。

解决方法就是移动semWait程序中end前的else一行到semSignal程序中最后一行之前。因此semWait中的最后一个semSignalB(mutex)变成无条件的，semSignal中的semSignalb(mutex)变成了有条件的。

5.10 1978年，dijkstra提出了一个推测，即使用有限数目的弱信号量，没有一种解决互斥的方案，使用于数目未知但有限的进程且可以避免饥饿。1979年，j.m.morris提出 了一个使用三个弱信号量的算法，反驳了这个推测。算法的行为可描述如下，如果一个或多个进程正在semwait（s）操作上等待，另一个进程正在执行semsignal（s），则信号量s的值未被修改，一个等待进程被解除

阻塞，并且这并不取决于semwait（s）。除了这三个信号量外，算法使用两个非负整数变量，作为在算法特定区域的进程的计数器。因此，信号量A和B被初始化为1，而信号量M和计数器NA，NM被初始化成0.一个试图进入临界区的进程必须通过两个分别由信号量A和M表示路障，计数器NA和NM分别含有准备通过路障A以及通过路障A但还没有通过路障M的进程数。在协议的第二部分，在M上阻塞的NM个进程将使用类似于第一部分的串联技术，依次进入他们的临界区，定义一个算法实现上面的描述。 答：这个程序由[RAYN86]提供： var a, b, m: semaphore; na, nm: 0 ? +∞;

a := 1; b := 1; m := 0; na := 0; nm := 0; semWait(b); na ← na + 1; semSignal(b); semWait(a); nm ← nm + 1; semwait(b); na ← na – 1;

if na = 0 then semSignal(b); semSignal(m) else semSignal(b); semSignal(a) endif;

semWait(m); nm ← nm – 1; ;

if nm = 0 then semSignal(a) else semSignal(m) endif;

5.11下面的问题曾被用于一个测试中：

侏罗纪公园有一个恐龙博物馆和一个公园，有m个旅客和n辆车，每辆车只能容纳一名旅客。旅客在博物馆逛了一会儿，然后派对乘坐旅客车。当一辆车可用时，它载入一名旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步m个旅客进程和n个进程。下面的代码框架是在教室的地板上发现的。忽略语法错误和丢掉的变量声明，请判定它是否正确。注意，p和v分别对应于semwait和semsignal。 Resource Jurassic_Park()

Sem car_avail:=0,car_taken:=0,car_fillde:=0.passenger_released:=0 Process passenger(i:=1 to num_passengers)

Do true->nap(int(random(1000*wander_time))) P(car avail);V(car_taken);P(car_filled) P(passenger_released) Od

End passenger

Process car(j:=1 to num_cars)

Do true->V(car_avail);P(car_taken);V(car_filled) Nap(int(random(1000*ride_time))) V(passenger_released) Od

End car

End Jurassic_Park

答：这段代码有一个重要问题.在process car中的代码 V(passenger_released)能够解除下面一种旅客的阻塞,被阻塞在P(passenger_released)的这种旅客不是坐在执行V()的车里的旅客.

5.12在图5.9和5.3的注释中，有一句话是“仅把消费者临界区（由s控制）中的控制语句移出还是不能解决问题，因为这将导致死锁”，请用类似于表5.3的表说明。

答： Producer Consumer s n delay 1 1 0 0 2 SemWaitB(S) 0 0 0 3 n++ 0 1 0 4 If(n==1) 0 1 1 (semSignalB(delay)) 5 semSignalB(s) 1 1 1 6 semWaitB(delay) 1 1 0 7 semWaitB(s) 0 1 0 8 n-- 0 0 9 semWaitB(s) If(n==0) (semWaitB(delay)) 10 生产者和消费者都被阻塞。 5.13考虑图5.10中定义的无限缓冲区生产者/消费者问题的解决方案。假设生产者和消费者都以大致相同的速度运行，运行情况如下：

生产者：append;semSignal;produce;···append;semSignal 消费者：consume;take;semWait;consume;take;semWait; 生产者通常管理给换成区一个元素，并在消费者消费了前面的元素后发信号。生产者通常添加到一个空缓冲去中，而消费者通常取走缓冲区中的唯一元素。尽管消费者从不在信号量上阻塞，但必须进行大量的信号量调用，从而产生相当多的开销。

构造一个新程序使得能在这种情况下更加有效。

提示：允许n的值为-1，这表示不仅缓冲区为空，而且消费者也检测到这个事实并将被阻塞，直到生产者产生新数据。这个方案不需要使用图5.10中的局部变量m。

答：

这个程序来自于[BEN82] program producerconsumer; var n: integer;

s: (*binary*) semaphore (:= 1); delay: (*binary*) semaphore (:= 0); procedure producer; begin

repeat produce;

semWaitB(s); append; n := n + 1;

if n=0 then semSignalB(delay); semSignalB(s) forever end;

procedure consumer; begin repeat

semWaitB(s); take;

n := n – 1; if n = -1 then begin

semSignalB(s); semWaitB(delay); semWaitB(s) end;

consume;

semSignalB(s) forever end;

begin (*main program*) n := 0; parbegin

producer; consumer parend end.

5.14考虑图5.13.如果发生下面的交换，程序的意义是否会发生改变？

a.semWait(e);semWait(s) b.semSignal(s);semSignal(n) c.semWait(n);semWait(s) d.semSignal(s);semSignal(e)

答：只要交换顺序都会导致程序错误。信号量s控制进入临界区，你只想让临界区区域包括附加或采取功能。

5.15在讨论有限缓冲区（见图5.12）生产者/消费者问题时，注意我们的定义允许缓冲区中最多有n-1个入口？ a.这是为什么？

b.请修改程序，以不久这种低调？ 答：如果缓冲区可以容纳n个入口，问题在于如何从一个满的缓冲区中区分出一

个空的缓冲区，考虑一个有六个位置的缓冲区，且仅有一个入口，如下： A Out in

然后，当一个元素被移出，out=in。现在假设缓冲区仅有一个位置为空： D E A B C In out 这样，out=in+1.但是，当一个元素被添加，in被加1后，out=in，当缓冲区为空时同理。

b．你可以使用一个可以随意增加和减少的辅助的变量，count。

5.16这个习题说明了使用信号量协调三类进程。圣诞老人在他北极的商店中睡眠，他只能被一下两种情况之一唤醒：（1）所有九头驯鹿都从南太平洋的假期回来了，或者（2）某些小孩在制作玩具时遇到了困难。为了让圣诞老人多睡会，这些孩子只有在是那个人都遇到困难时才唤醒他。当三个孩子的问题得到解决时，其他想访问圣诞老人的孩子必须等到那些孩子返回。如果圣诞老人醒来后发现在三个孩子在他的店门口等待，并且最后一头驯鹿已经从热带回来。则圣诞老人决定让孩子门等到圣诞节之后，因为准备最后一天哦iuxunlu必须与其他unlu在暖棚中等待并且还没有套上缰绳做成雪橇前回来。请用信号量解决这个问题。 答：santa:圣诞老人reindeer:驯鹿elf:小孩子sleigh:雪橇toys:玩具

5.17通过一下步骤说明消息传递和信号量具有同等的功能：

a.用信号量实现消息传递。提示：利用一个共享缓冲区保存信箱，每个信箱由一个消息槽数组成的。

b.用消息传递实现信号量。提示：引入一个独立的同步进程。

答：b.这个方法来自于[TANE97].同步进程维护了一个计数器和一个等待进程的清单。进程调用相关用于向同步进程发送消息的生产者，wait或signal，来实现WAITHUO SIGNAL.然后生产者执行RECEIVE来接受来自于同步进程的回复。 当消息到达时，同步进程检查计数器看需要的操作是否已经足够，SIGNALs总是可以完成，但是假如信号值为0时，WAITs将会被阻塞。假如操作被允许，同步进程就发回一个空消息，因此解除调用者的阻塞。假如操作是WAIT并且信号量的值为0时，同步进程进入调

用队列，并且不发送回复。结果是执行WAIT的进程被阻塞。当SIGNAL被执行，同步进程选择一个进程在信号量上阻塞，要不就以先进先出顺序，要不以其他顺序，并且发送一个回复。跑步条件被允许因为同步进程一次只需要一个。

第六章 习题

第一部分 复习题

6.1给出可重用资源和可消费资源的例子。

答：可重用资源：处理器，I/O通道，主存和辅存，设备以及诸如文件，数据库和信号量之类的数据结构。

可消费资源：中断，信号，消息和I/O缓冲区中的信息。 6.2可能发生死锁所必须的三个条件是什么？ 答：互斥，占有且等待，非抢占。 6.3产生死锁的第4个条件是什么？ 答：循环等待。

6.4如何防止占有且等待的条件？ 答：可以要求进程一次性地请求所有需要的资源，并且阻塞这个资源直到所有请求都同时满足。

6.5给出防止无抢占条件的两种方法。

答：第一种，如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占用的资源，如果有必要，可再次请求这些资源和另外的资源。

第二种，如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。 6.6如何防止循环等待条件？ 答：可以通过定义资源类型的线性顺序来预防。如果一个进程已经分配到了Ｒ类型的资源，那么它接下来请求的资源只能是那些排在Ｒ类型之后的资源类型。 6.7死锁避免，检测和预防之间的区别是什么？ 答：死锁预防是通过间接地限制三种死锁必要条件的至少一个或是直接地限制循环等待的发生来避免死锁的出现。死锁避免允许可能出现的必要条件发生，但是采取措施确保不会出现死锁的情况。而死锁检测允许资源的自由分配，采取周期性的措施来发现并处理可能存在的死锁情况。

第二部分 习题

6.1写出图6.1（a）中死锁的四个条件。

解：互斥：同一时刻只有一辆车可以占有一个十字路口象限。占有且等待：没有车可以倒退；在十字路口的每辆车都要等待直到它前面的象限是空的。非抢占: 没有汽车被允许挤开其他车辆。 循环等待: 每辆汽车都在等待一个此时已经被其他车占领的十字路口象限。

6.2按照6.1节中对图6.2中路径的描述，给出对图6.3中6种路径的简单描述。

解：1.Q 获得 B 和A, 然后释放 B 和 A. 当 P 重新开始执行的时候, 它将会能够获得两个资源。

2. Q 获得 B和A， P 执行而且阻塞在对 A的请求上. Q释放 B 和A。当 P 重新开始执行的时候，它将会能够获得两个资源。

3. Q 获得 B ，然后 P 获得和释放 A. Q 获得A然后释放 B 和 A. 当 P 重新开始行的时候，它将会能够获得 B。 4. P 获得A然后 Q 获得 B. P 释放 A. Q 获得A然后释放 B. P 获得 B 然后释放 B。

5. P 获得，然后释放 A. P 获得 B. Q 执行而且阻塞在对Ｂ的请求上。Ｐ释放Ｂ。当 Q 重新开始执行的时候，, 它将会能够获得两个资源。

6. P 获得A而且释放A然后获得并且释放 B. 当 Q 重新开始实行, 它将会能够获得两个资源。

6.3图6.3反映的情况不会发生死锁，请证明。

证明：如果 Q 获得 B 和A（在 P之前请求A）, 那么 Q 能使用这些两类资源然后释放他们, 允许A进行。 如果 P在 Q之前请求A获得A, 然后Q 最多能执行到请求A然后被阻塞。 然而,一旦 P 释放 A ， Q 能进行。 一旦 Q 释放 B, A能进行。

6.4考虑下面的一个系统，当前不存在未满足的请求。

a计算每个进程仍然可能需要的资源，并填入标为“仍然需要”的列中。 b系统当前是处于安全状态还是不安全状态，为什么。 c系统当前是否死锁？为什么？

d哪个进程（如果存在）是死锁的或可能变成死锁的？

e如果Ｐ3的请求（0，1，0，0）到达，是否可以立即安全地同意该请求？在什么状态（死锁，安全，不安全）下可以立即同意系统剩下的全部请求？如果立即同意全部请求，哪个进程（如果有）是死锁的或可能变成死锁的？

解： a. 0 0 0 0

0 7 5 0 6 6 2 2 2 0 0 2 0 3 2 0

b.系统当前处于安全状态，因为至少有一个进程执行序列，不会导致死锁，

运行顺序是p1, p4, p5, p2, p3.

c.系统当前并没有死锁，因为P1进程当前分配与最大需求正好相等，P1进

程可以运行直至结束，接下来运行其他进程

d.P2,P3,P4,P5可能死锁

e.不可以，当进程P1,P4,P5执行完可用资源为（4，6，9，8），P2,P3将死

锁，所以不安全，完全不可以立即同意系统剩下的全部请求。

6.5 请把6.4中的死锁检测算法应用于下面的数据，并给出结果。

Available=(2 1 0 0)

2 0 0 1 0 0 1 0 Request= 1 0 1 0 Allocation= 2 0 0 1 2 1 0 0 0 1 2 0

解： 1. W = (2 1 0 0)

2. Mark P3; W = (2 1 0 0) + (0 1 2 0) = (2 2 2 0) 3. Mark P2; W = (2 2 2 0) + (2 0 0 1) = (4 2 2 1) 4. Mark P1; no deadlock detected 没有死锁

6.6一个假脱机系统包含一个输入进程Ｉ，用户进程进程Ｐ和一个输出进程Ｏ，它们之间用两个缓冲区连接。进程以相等大小的块为单位交换数据，这些块利用输入缓冲区和输出缓冲区之间的移动边界缓存在磁盘上，并取决于进程的速度。所使用的通信原语确保满足下面的资源约束：i+o≤max

其中，max表示磁盘中的最大块数，i表示磁盘中的输入块数目， o表示磁盘中的输出块数目。 输入 输出 P 缓冲区 缓冲区

以下是关于进程的知识：

1、只要环境提供数据，进程Ｉ最终把它输入到磁盘上（只要磁盘空间可用）。 2、只要磁盘可以得到输入，进程Ｐ最终消耗掉它，并在磁盘上为每个输入块输出有限量的数据（只要磁盘空间可用）。

I o

本文来源：https://www.bwwdw.com/article/hea6.html