[英文原版]操作系统_精髓与设计原理_第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 3、只要磁盘可以得到输出，进程Ｏ最终消耗掉它。说明这个系统可能死锁。

解：当I的速度远大于P的速度，有可能使磁盘上都是输入数据而此时P进程要处理输入数据，即要将处理数据放入输出数据区。于是P进程等待磁盘空间输出，I进程等待磁盘空间输入，二者死锁。

6.7给出在习题6.6中预防死锁的附加资源约束，仍然通话输入和输出缓冲区之间的边界可以根据进程的要求变化。 解：为输出缓冲区保留一个最小数目(称为reso)块, 但是当磁盘空间足够大时允许输出块的数目超过这一个界限。 资源限制现在变成 Ｉ + Ｏ ≤max Ｉ≤max – reso 当0 < reso < max 如果程序 P 正在等候递送输出给磁盘, 程序 O 最后处理所有的早先输出而且产生至少reso页, 然后让 P 继续执行。 因此 P 不会因为 O 而延迟。 如果磁盘充满I/O，Ｉ能被延迟; 但是迟早, 所有的早先的 输入可以被Ｐ处理完，而且对应的输出将会被 O 处理, 因而可以让Ｉ继续执行。

6.8在ＴＨＥ多道程序设计系统中，一个磁鼓（磁盘的先驱，用做辅存）被划分为输入缓冲区，处理和输出缓冲区，它们的边界可以移动，这取决于所涉及的进程速度。磁鼓的当前状态可以用以下参数描述：

max表示磁鼓中的最大页数，i示磁鼓中的输入页数，p示磁鼓中的处理页数，o示磁鼓中的输出页数，reso出保留的最小页数，resp理保留的最小页数。 解：

Ｉ + Ｏ + Ｐ≤max – Ｉ + Ｏ≤max – resp Ｉ + Ｐ ≤max – reso Ｉ ≤max – (reso + resp)

6．9在ＴＨＥ多道程序设计系统中，一页可以进行下列状态转换： 1.空→输入缓冲区（输入生产）

2.输入缓冲区→处理区域（输入消耗） 3.处理区域→输出缓冲区（输出生产） 4.输出缓冲区→空（输出生产） 5.空→处理区域（输出消耗） 6.处理区域→空（过程调用）

a根据Ｉ，Ｏ和Ｐ的量定义这些转换的结果。 b如果维持习题6.6中关于输入进程，用户进程和输出进程的假设，它们中的任何一个转换是否会导致死锁。 解： 1. i ←i + 1

2. i←i – 1; p ←p + 1 3. p←p – 1; o←o + 1 4. o ←o – 1

5. p←p + 1 6. p ←p – 1

b. 结合在对问题 6.7 的解决办法被列出的资源限制, 我们 能总结下列各项:

6. 过程返回能立刻发生因为他们只释放 资源。

5. 程序调用可能用尽磁盘片 (p= max – reso) 导致死锁。 4. 当有输出时输出消耗能立刻发生。

3. 输出生产能暂时被延迟直到所有的早先输出被消耗而且为下一步的输出至少可以产生reso页。

2. 只要有输入，输入消耗能立刻发生。

1. 输入生产被延迟直到所有先前输入和对应的输出已经被消耗。 此时, 当 i= o=0,如果消费进程还没有占用完磁盘空间 ( p < max – reso)，可以产生输入。 结论: 分配给消费进程的不受控制的存储空间是 唯一可能引发死锁的因素。

6.1０考虑一个共有15０个存储器单元的系统，其单元如下分配三个进程：

进程 最大 占用 1 70 45 2 60 40 3 60 15

使用银行家算法，以确定同意下面的任何一个请求是否安全。如果安全，说明能保证的终止序列；如果不安全，给出结果分配简表。

a．第4个进程到达，最多需要6０个存储单元，最初需要25个单元。 b第4个进程到达，最多需要6０个存储单元，最初需要35个单元。 解： a.若同意第4个进程请求，则储存器单元共用去25＋15＋40＋45=125个单元，还有25个存储单元，则可以安全执行全部进程。安全顺序是1－2－3－4

b.若同意第4个进程请求，则还有15个资源可以用，此时处于不安全状态，结果分配见表

进程 最大 占有 需要 空闲 1 70 45 25 15 2 60 40 20 3 60 15 45 4 60 35 25

6.11评价独家算法在实际应用中是否有用。 解：不切实际的: 不能总是预先知道最大要求, 进程数目和资源数目可能随着时间改变 。大多数的操作系统忽视死锁。

6.12有一个已经实现了的管道算法，使得进程Ｐ０产生的Ｔ类型的数据元素经进程序列Ｐ1Ｐ2?Ｐn-1,并且按该顺序在元素上操作。

a.定义一个一般的消息缓冲区，包含所有部分消耗的数据元素，并按下面的格式为进程Ｐi(0≤i≤n-1)写一个算法。 Repeat 从前驱接收 消耗

给后续发送 Forever

假设Ｐ0收到Ｐn-1发送的空元素。该算法能够使进程直接在缓冲区中保存的消息上操作，而无需复制。

b.说明关于普通的缓冲区进程不会死锁。

解：ar buffer: array 0..max-1 of shared T;

available: shared array 0..n-1 of 0..max;

\var K: 1..n-1;

region available do begin

available(0) := max;

for every k do available (k) := 0; end

\

var j: 0..max-1; succ: 0..n-1; begin

j := 0; succ := (i+1) mod n; repeat

region available do

await available (i) > 0;

region buffer(j) do consume element; region available do begin

available (i) := available(i) – 1;

available (succ) := available (succ) + 1; end

j := (j+1) mod max; forever end

b.死锁可以被解决通过 P0 waits for Pn-1 AND P1 waits for P0 AND . . . . .

Pn-1 waits for Pn-2 因为

(available (0) = 0) AND (available (1) = 0) AND . . . . .

(available (n-1) = 0)

但是如果max > 0,这个条件不成立，因为临界域满足 claim(1)+ claim(2)+ ?+claim(n)

< available(1)+available(2)+?+available(n) =max

6.13 a.3个进程共享4个资源单元，一次只能保留或释放一个单元。每个进程最大需要2个单元。说明不会死锁。 b.Ｎ个进程共享Ｍ个资源单元，一次只能保留或释放一个单元。每个进程最大需要单元数不超过Ｍ，并且所有最大需求的总和小于Ｍ+Ｎ。说明不会发生死锁。

解：a.说明由于每个进程最多需要2个资源，最坏情况下，每个进程需要获得一个，系统还剩1个，这一个资源，无论分给谁都能完成。完成进程释放资源后，使剩余进程也完成，故系统不会死锁。

b.假定每个进程最多申请X个资源，最坏情况下，每个进程都得到X-1个资源都在申请最后一个资源，这时系统剩余资源数量为M-N(X－1)，只要系统还有一个剩余资源，就可以使其中的一个进程获得所需要的全部资源，该进程运行结束以后释放资源，就可以使其他进程得到全部资源的 满足，因此，当M-N(X-1)》1时系统不会发生死锁，解这个不等式X《（M+N-1）,系统不会发生死锁，因此，当所有进程的需求总和小于M+N时，系统是不会发生死锁的。

6.14考虑一个由四个进程和一个单独资源组成的系统，当前的声明和分配矩阵是

3 1 2 1 C = 9 A= 3 7 2

对于安全状态，需要的最小资源数目是多少？

解：最小资源数是3个，总共有1０个资源。Ｐ2获得一个资源，完成后释放两个资源，Ｐ1获得三个资源，完成后释放三个资源，接下来Ｐ4获得五个资源，释放完资源后，Ｐ3获得所需的6个资源后完成。

6.15考虑下列处理死锁的方法：1银行家算法，2死锁检测并杀死线程，释放所有资源，3事先保留所有资源，4如果线程需要等待，5资源排序，6重新执行检测死锁并退回线程的动作。

评价解释死锁的不同方法使用的一个标准是，哪种方法允许最大的并发。换言之，在没有死锁时，哪种方法允许最多数目的线程无需要等待继续前进？对下面列出的6种处理死锁的方法，给出从1到6的一个排序（1表示最大程序的并

发），并解释你的排序。

另一个标准是效率；哪种方法需要最小的处理器开销？假设死锁很少发生，给出各种方法从1到6的一个排序（1表示最有效），并解释这样排序的原因。如果死锁发生很频繁，你的顺序需要改变吗？

解：a从最多并发事件到最少, 有一个大概的次序如下：

1. 死锁检测并杀死线程，释放所有资源 发现死锁并退回线程的动作，如果线程需要等候那么重新开始线程而且释放所有的资源，在死锁发生之前，这些运算法则都不会限制并发, 因为他们仰赖运行时间检查而并非静态的限制。 他们的效果在死锁被发现比较难以描述：他们仍然允许许多并发(在一些情形，他们增加它), 但是很难有准确的估计。 第三个运算法则是最奇怪的, 因为如此后许多的它的并发将会是无用的重复; 因为线程竞争执行时间, 这一个运算法则也影响运行速度。 因此在两者的极端,它以这顺序被列出两次。

2. 银行家的运算法则 资源排序

这些运算法则因为限制多种的可允许的计算，而相对早先两种法则会引起更多的不必要的等候。 银行家的运算法则避免不安全的配置 和资源排序限制配置序列以便线程在他们是否一定等候的时候有较少的选择。 3. 事先保留所有的资源

这一个运算法则相比前两个要允许更少的并发, 但是比最坏的那一种有更少的缺点。因为要预先保留所有的资源,线程必须等候比较长的而且当他们工作的时候更有可能阻塞其他的线程,因此系统上来说具有更多的线性。 4. 如果线程需要等待，则重新启动线程并且释放所有的资源

如上所述, 这一个运算法则在区别最多和最少并发上有疑问,这具体要看并发的定义。

b从最高效率到最低，有如下大概的一个顺序：

1. 预先保留所有的资源 资源排序

因为他们没有包括运行时间经常开支，所以这些运算法则最有效率。 注意这是在相同的静态限制下的结果。 2. 银行家的运算法则

发现死锁而且杀死线程,释放它的资源

这些运算法则在概略的配置上包括运行时间检查

; 银行家的运算法则运行搜寻查证复杂度在线程和配置的数字和死锁检测中是 O(n m)，死锁检测的复杂度是 O(n)。资源-从属链被线程数目，资源数目和分配数目限制。

3. 发现死锁并退回线程的动作

这一个运算法则运行也需要运行上述的相同的时间检查。 在写内存上的复杂度为O(n) 。

4. 如果线程需要等待，则重新启动线程并释放所有的资源

这一个运算法则是非常无效率，有如下两个理由。 首先, 因为线程有重新开始

的危险, 他们完成的可能性低。其次，他们与其他重新开始线程竞争有限的执行时间, 因此整个系统运行的速度很慢。

6.16评价下面给出的就餐问题的解决方案。一位饥饿的哲学家首先拿起他左边的叉子，如果他右边的叉子也是可用的，则拿起右边的叉子开始吃饭，否则他放下左边的叉子，并重复这个循环。 解：如果哲学家们步调完全一致地拿起左边叉子又放下的话，他们会重复这一过程，导致饥饿情况的出现。

6.17假设有两种类型的哲学家。一类总是先拿起左边的叉子（左撇子），另一类总是先拿起右边的叉子（右撇子）。左撇子的行为和图6.12中定义的一致。右撇子的行为如下： begin repeat

think;

wait(fork[(i+1)mod5]); wait(fork[i]); eat;

signal(fork[i]);

signal(fork[(i+1)mod5]);

forever; end;

证明：a如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以避免死锁。

b如果至少有一个左撇子或右撇子，则他们的任何就座安排都可以防止饥饿。

解：a假设存在死锁情况，设有 D个哲学家，他们每人都有一支叉子而且另一

支叉子被邻居占有。不失一般性，设Pj 是一个左撇子。 Pj 抓牢他的左边叉子而且没有他的右边叉子, 他的右边邻居 Pk 没有完成就餐因此也是一个左撇子。 因此依次推理下去所有这Ｄ个哲学家都是左撇子。这与既有左撇子又有右撇子的条件矛盾，假设不成立，不存在死锁。 b

假设左撇子 Pj 饥饿，也就是说，有一部分人在就餐而Pj从不吃。 假如 Pj 没有叉子。 这样 Pj 的左边邻居 Pi 一定持续地占有叉子而始终不吃完。 因此Pi 是 右撇子，

抓住他的右边叉子, 但是从不得到他的左边叉子来完成就餐,也就是说 Pi 也饥饿。 现在 Pi 左边邻居也一定是持续占有右边叉子的右撇子。 向左进行这样的推理，得出所有哲学家都是饥饿的右撇子，这同Pj是个左撇子矛盾。因此 Pj 一直拥有左边子而且在等待他的右边叉子,Pj 的右边邻居 Pk 一直举着他的左边叉子而且从不完成一餐,也就是, Pk 是也饥饿的左撇子。 如果 Pk 不是一直拿着他的左边叉子， Pj 就可以就餐;因此 Pk 拿着他的左边叉子。向右推理可得所有哲学家都是饥饿的左撇子。这与条件矛盾，因此假设不成立，没有人饥饿。

6.18图1.17显示了另外一个使用管程解决哲学家就餐问题的方法。和图6.14比较并阐述你的结论。 解：图6.14是等待可用的叉子，图6.17是等待邻居吃完，在本质上逻辑是一样的，后者显得更加紧凑。

monitor dining_controller; enum states{thinking,hungry,eating} state[5]; cond needFork[5] /*condition variable*/ void get_forks(int pid) /*pid is the philosopher id number*/ { start[pid]=hungry; /*announce that I am hungry*/ if(state[(pid+1)%5]= =eating ||(state[(pid-1)%5]= =eating cwait(needFork[pid]); /*wait if either neighbor is eating*/ state[pid]=eating; /*proceed if neither neighbor is eating*/ } void release_fork(int pid) { state[pid]=thinking; /*give right(higher)neighbor a chance to eat*/ if(state[(pid+1)%5])= =hungry) &(state[(pid+2)%5])!=eating) csignal(needFork[pid+1]); /*give left(lower)neighbor a chance to eat*/ else if(state[(pid-1)%5]= =hungry) ||(state[(pid-2)%5!=eating]

void philosopher[k=0 to 4] /*the five philosopher clients*/ { while(true) { ; get_forks(k); /*client requests two forks via monitor*/ ; release_forks(k); /*client releases forks via the monitor*/ } }

6.19在表6.13中，Linux的一些原子操作不会涉及到对同一变量的两次访问。比如atomic_read(atomic_t *v).简单的读操作在任何体系结构中都是原子的。为什么该操作增加到了原子操作的指令表？

解：原子操作是在原子数据类型上操作, 原子数据类型有他们自己的内在的 格式。 因此，不能用简单的阅读操作, 但是特别的阅读操作 对于原子数据类型来说是不可或缺的。

6.2０考虑Linux系统中的如下代码片断： read_lock(&mr_rwlock); write_lock(&mr_rwlock);

mr_rwlock是读者写者锁。这段代码的作用是什么？

解：因为写者锁将会自旋，所以这段代码会导致死锁, 等待所有的 读者解锁, 包括唤醒这个线程。

6.21两个变量a和b分别有初始值1和2，对于Linux系统有如下代码：

线程1 线程2 a = 3； -- mb( )； -- -- c = b； -- rmb()； d = a；

使用内在屏障是为了避免什么错误？

解：没有使用内存屏障, 在一些处理器上可能 c接到b 的新值, 而d接到b 的旧

值。 举例来说, c可以等于 4(我们期待的), 然而 d 可能等于 1.(不是我们期待的)。 使用mb() 确保a 和 b 按合适的次序被写, 使用 rmb()确保 c 和d 按合适的次序被读。

第7章 内存管理

复习题：

7.1. 内存管理需要满足哪些需求？

答：重定位、保护、共享、逻辑组织和物理组织。 7.2. 为什么需要重定位进程的能力？

答：通常情况下，并不能事先知道在某个程序执行期间会有哪个程序驻留在主存中。此外还希望通过提供一个巨大的就绪进程池，能够把活动进程换入和换出主存，以便使处理器的利用率最大化。在这两种情况下，进程在主存中的确切位置是不可预知的。 7.3. 为什么不可能在编译时实施内存保护？

答：由于程序在主存中的位置是不可预测的，因而在编译时不可能检查绝对地址来确保保护。并且，大多数程序设计语言允许在运行时进行地址的动态计算（例如，通过计算数组下标或数据结构中的指针）。因此，必须在运行时检查进程产生的所有存储器访问，以便确保它们只访问了分配给该进程的存储空间。 7.4. 允许两个或多个进程访问进程的某一特定区域的原因是什么？

答：如果许多进程正在执行同一程序，则允许每个进程访问该程序的同一个副本要比让每个进程有自己单独的副本更有优势。同样，合作完成同一任务的进程可能需要共享访问同一个数据结构。

7.5. 在固定分区方案中，使用大小不等的分区有什么好处？

答：通过使用大小不等的固定分区：1.可以在提供很多分区的同时提供一到两个非常大的分区。大的分区允许将很大的进程全部载入主存中。2.由于小的进程可以被放入小的分区中，从而减少了内部碎片。 7.6. 内部碎片和外部碎片有什么区别？

答：内部碎片是指由于被装入的数据块小于分区大小而导致的分区内部所浪费的空间。外部碎片是与动态分区相关的一种现象，它是指在所有分区外的存储空间会变成越来越多的碎片的。

7.7. 逻辑地址、相对地址和物理地址间有什么区别？

答：逻辑地址是指与当前数据在内存中的物理分配地址无关的访问地址，在执行对内存的访问之前必须把它转化成物理地址。相对地址是逻辑地址的一个特例，是相对于某些已知点（通常是程序的开始处）的存储单元。物理地址或绝对地址是数据在主存中的实际位置。

7.8. 页和帧之间有什么区别？

答：在分页系统中，进程和磁盘上存储的数据被分成大小固定相等的小块，叫做页。而主存被分成了同样大小的小块，叫做帧。一页恰好可以被装入一帧中。 7.9. 页和段之间有什么区别？

答：分段是细分用户程序的另一种可选方案。采用分段技术，程序和相关的数据被划分成一组段。尽管有一个最大段长度，但并不需要所有的程序的所有段的长度都相等。

习题：

7.1. 2.3节中列出了内存管理的5个目标，7.1节中列出了5中需求。请说明它们是一致

的。

答: 重定位≈支持模块化程序设计; 保护≈保护和访问控制以及进程隔离; 共享≈保护和访问控制;

逻辑组织≈支持模块化程序设计;

物理组织≈长期存储及自动分配和管理.

7.2. 考虑使用大小相等分区的固定分区方案。分区大小为2e16字节，贮存的大小为2e24

字节。使用一个进程表来包含每一个进程对应的分区。这个指针需要多少位？ 答:分区的数量等于主存的字节数除以每个分区的字节数：224/216 = 28. 需要8个比特来确定一个分区大小为28中的某一个位置。

7.3. 考虑动态分区方案，说明平均内存中空洞的数量是段数量的一半。

答: 设n和h为断数量和空洞数量的个数.在主存中,每划分一个断产生一个空洞的概率是0.5,因为删除一个断和添加一个断的概率是一样的.假设s是内存中断的个数那么空洞的平均个数一定等于s/2.而导致空洞的个数一定小余断的数量的直接原因是相邻的两个断在删除是一定会产生一个空洞. 7.4. 在实现动态分区中的各种放置算法（见7.2节），内存中必须保留一个空闲块列表。

分别讨论最佳适配、首次适配、临近适配三种方法的平均查找长度。

答:通过上题我们知道，假设s是驻留段的个数，那么空洞的平均个数是s/2。从平均意义上讲，平均查找长度是s/4。

7.5. 动态分区的另一种放置算法是最坏适配，在这种情况下，当调入一个进程时，使用最

大的空闲存储块。该方法与最佳适配、首次适配、邻近适配相比，优点和缺点各是什么？它的平均查找长度是多少？

答：一种对最佳适配算法的评价即是为固定分配一个组块后和剩余空间是如此小以至于实际上已经没有什么用处。最坏适配算法最大化了在一次分配之后，剩余空间的大小仍足够满足另一需求的机率，同时最小化了压缩的概率。这种方法的缺点是最大存储块最早被分配，因此大空间的要求可能无法满足。

7.6. 如果使用动态分区方案，下图所示为在某个给定的时间点的内存配置：

阴影部分为已经被分配的块；空白部分为空闲块。接下来的三个内存需求分别为40MB，20MB和10MB。分别使用如下几种放置算法，指出给这三个需求分配的块的起始地址。 a. 首次适配 b. 最佳适配

c. 临近适配（假设最近添加的块位于内存的开始） d. 最坏适配 答：

a. 40M的块放入第2个洞中,起始地址是80M. 20M的块放入第一个洞中.起始地址是20M. 10M的块的起始地址是120M。

b. 40M,20N,10M的起始地址分别为230M,20M和160M.

c. 40M,20M,10M的起始地址是80M,120160M.

d. 40M,20M,10M,的起始地址是80M,230M,360M.

7.7. 使用伙伴系统分配一个1MB的存储块。

a. 利用类似于图7.6的图来说明按下列顺序请求和返回的结果：请求70；请求35；

请求80；返回A；请求60；返回B；返回D；返回C。 b. 给出返回B之后的二叉树表示。 答： a.

b.

7.8. 考虑一个伙伴系统，在当前分配下的一个特定块地址为011011110000.

a. 如果块大小为4，它的伙伴的二进制地址为多少？

b. 如果块大小为16，它的伙伴的二进制地址为多少？ 答：

a. 011011110100 b. 011011100000

k

7.9. 令buddyk(x)为大小为2、地址为x的块的伙伴的地址，写出buddyk(x)的通用表达式。

答：

7.10. Fabonacci序列定义如下：

F0=0,F1=1,Fn+2=Fn+1+Fn,n≧0

a. 这个序列可以用于建立伙伴系统吗？

b. 该伙伴系统与本章介绍的二叉伙伴系统相比，有什么优点？ 答：

a. 是。字区大小可以确定Fn = Fn-1 + Fn-2.。

b. 这种策略能够比二叉伙伴系统提供更多不同大小的块，因而具有减少内部碎片的

可能性。但由于创建了许多没用的小块，会造成更多的外部碎片。

7.11. 在程序执行期间，每次取指令后处理器把指令寄存器的内容（程序计数器）增加一个

字，但如果遇到会导致在程序中其他地址继续执行的转跳或调用指令，处理器将修改这个寄存器的内容。现在考虑图7.8。关于指令地址有两种选择：

? 在指令寄存器中保存相对地址，并把指令寄存器作为输入进行动态地址转换。当

遇到一次成功的转跳或调用时，由这个转跳或调用产生的相对地址被装入到指令寄存器中。

? 在指令寄存器中保存绝对地址。当遇到一次成功的转跳或调用时，采用动态地址

转换，其结果保存到指令寄存器中。 哪种方法更好？ 答：使用绝对地址可以减少动态地址转换的次数。但是，我们希望程序能够被重定位。因此，在指令寄存器中保存相对地址似乎就更好一些。也可以选择在进程被换出主存时将指令寄存器中的地址转换为相对地址。

3210

7.12. 考虑一个简单分页系统，其物理存储器大小为2字节，页大小为2字节，逻辑地址

16

空间为2个页。

a. 逻辑地址空间包含多少位？ b. 一个帧中包含多少字节？

c. 在物理地址中指定帧需要多少位？ d. 在页表中包含多少个页表项？

e. 在每个页表项中包含多少位？（假设每个页表项中包含一个有效/无效位） 答：

161026

a. 物理地址空间的比特数是2*2=2

10

b. 一个帧包含的字节跟一个页是一样的,2比特.

321022

c. 主存中帧的数量是2/2=2,所以每个帧的定位要22个比特

16

d. 在物理地址空间,每个页都有一个页表项,所以有2项

e. 加上有效/无效位，每个页表项包含23位。7.13. 分页系统中的虚地址a相当于一对（p，w），其中p是页号，w是页中的字节号。令z

是一页中的字节总数，请给出p和w关于z和a的函数。

答：关系是：a = pz + w，其中p = ∟a/z?, a/z的整数部分。w = Rz(a) ，a除以z的余数

7.14. 在一个简单分段系统中，包含如下段表：起始地址 660 1752 222 996 长度（字节） 248 442 198 604 对如下的每一个逻辑地址，确定其对应的物理地址或者说明段错误是否会发生： a. 0，198 b. 2，256 c. 1，530 d. 3，444 e. 0，222 答：

a. 段0定位在660,所以我们有物理地址660+190=858. b. 222+156=378

c. 段1长度为422,所以会发生错误 d. 996+444=1440 e. 660+222=882.

7.15. 在内存中，存在连续的段S1,S2,?，Sn按其创建顺序一次从一端放置到另一端，如下

图所示：

当段Sn+1被创建时，尽管S1,S2,?，Sn中的某些段可能已经被删除，段Sn+1仍被立即放置在段Sn之后。当段（正在使用或已被删除）和洞之间的边界到达内存的另一端时，压缩正在使用的段。

a. 说明花费在压缩上的时间F遵循以下的不等式：

F≧(1-f)/1+kf), k=t/2s-1

其中，s表示段的平均长度（以字为单位）；l标识段的平均生命周期，按存储器访问；f表示在平衡条件下，未使用的内存部分。提示：计算边界在内存中移动的平均速度，并假设复制一个字至少需要两次存储器访问。 b. 当f=0.2，t=1000，s=50时，计算F。 答：

a. 很明显,在一个周期t内一些段会产生而一些段会被删除.因为系统是公平的,一个新的段会在t内被插入,此外,边界会医s/t的速度移动.假设t0是边界到达空洞的时间,t0=fmr/s, m=内存的长度,在对段进行压缩时会有(1-f)m个数被移动,压缩时

间

至少是2(1-f)m.则花在压缩上的时间F为F=1-t0/(t0+tc)。

b. K=(t/2s)-1=9;F≧(1-0.2)/(1+1.8)=0.29

第八章 虚拟内存

8.1 简单分页与虚拟分页有什么区别？ 简单分页：一个程序中的所有的页都必须在主存储器中程序才能正常运行，除非使用覆盖技术。虚拟内存分页：不是程序的每一页都必须在主存储器的帧中来使程序运行，页在需要的时候进行读取。 8.2 解释什么是抖动。 虚拟内存结构的震动现象，在这个过程中处理器大部分的时间都用于交换块，而不是执行指令。

8.3 为什么在使用虚拟内存时，局部性原理是至关重要的？ 可以根据局部性原理设计算法来避免抖动。总的来说，局部性原理允许算法预测哪一个当前页在最近的未来是最少可能被使用的，并由此就决定候选的替换出的页。

8.4 哪些元素是页表项中可以找到的元素？简单定义每个元素。 帧号：用来表示主存中的页来按顺序排列的号码。存在位（P）：表示这一页是否当前在主存中。修改位（M）：表示这一页在放进主存后是否被修改过。 8.5 转移后备缓冲器的目的是什么？

转移后备缓冲器（TLB）是一个包含最近经常被使用过的页表项的高速缓冲存储器。它的目的是为了减少从磁盘中恢复一个页表项所需的时间。 8.6 简单定义两种可供选择的页读取策略。 在请求式分页中，只有当访问到某页中的一个单元时才将该页取入主存。在预约式分页中，读取的并不是页错误请求的页。 8.7 驻留集管理和页替换策略有什么区别？ 驻留集管理主要关注以下两个问题：（1）给每个活动进程分配多少个页帧。（2）被考虑替换的页集是仅限在引起页错误的进程的驻留集中选择还是在主存中所有的页帧中选择。页替换策略关注的是以下问题：在考虑的页集中，哪一个特殊的页应该被选择替换。

8.8 FIFO和Clock页替换算法有什么区别？

时钟算法与FIFO算法很接近，除了在时钟算法中，任何一个使用位为一的页被忽略。

8.9 页缓冲实现的是什么？

（1）被替换出驻留集的页不久又被访问到时，仍在主存中，减少了一次磁盘读写。（2）被修改的页以簇的方式被写回，而不是一次只写一个，这就大大减少了I/O操作的数目，从而减少了磁盘访问的时间。

8.10 为什么不可能把全局替换策略和固定分配策略组合起来？ 固定分配策略要求分配给一个进程的帧的数目是确定的，当一个进程中取入一个新的页时，这个进程的驻留页集中的一页必须被替换出来（保持分配的帧的数目不变），这是一种局部替换策略。 8.11 驻留集和工作集有什么区别？

一个进程的驻留集是指当前在主存中的这个进程的页的个数。一个进程的工作集是指这个进程最近被使用过的页的个数。 8.12 请求式清除和预约式清除有什么区别？ 在请求式清除中，只有当一页被选择用于替换时才被写回辅存；在预约式清除中，将这些被修改的多个页在需要用到它们所占据的页帧之前成批的写回辅存。

习题解答

8.1 假设在处理器上执行的进程的也表如下所示。所有数字均为十进制数，每一项都是从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 a． 描述CPU产生的虚拟地址通常是如何转化成一个物理主存地址的。 b．下列虚拟地址对应于哪个物理地址（不用考略页错误）？ （i）1052 （ii）2221 （iii）5499 解答

a：由虚拟地址求得页号和偏移量，用虚拟页号作为索引页表，得到页帧号，联系偏移量得到物理地址 b:(i)1052=1024+28 查表对应的页帧号是7，因此物理地址为7*1024+28=7196

(ii)2221=2*1024+173 此时出现页错误

(iii)5499=5*1024+379 对应的页帧号为0 因此物理地址是379

8.2 考虑一个使用32位的地址和1KB大小的页的分页虚拟内存系统。每个页表项需要32位。需要限制页表的大小为一个页。 a．页表一共需要使用几级？

b．每一级页表的大小是多少？提示：一个页表的大小比较小。

c．在第一级使用的页较小与在最底下一级使用的页较小相比，那种策略使用最小个数的页？ 解答

a：虚拟内存可以分为232/210= 222页，所以需要22个bit来区别虚拟内存中的一页，每一个页表可以包含210/4=28项，因此每个页表可以包含22bit中的8个bit，所以需要三级索引。

b：第二级页表有28个页表项，第一级页表有26个页表项。

c：如果顶层有26个页表项将会减少使用空间，在这种情况下，中间层页表有26个并且每个都有28个页表项，底层有214个页并且每个都有28个页表项，因此共有1+26+214页=16,449页。如果中间层有26个页表项，那么总的页数有1+28+214页=16,641页。如果底层有26个页表项，那么总的页表数是1+28+216页=65,973页。

8.3 a：图8.4中的用户表需要多少内存空间？

b：假设需要设计一个哈希反向页表来实现与图8.4中相同的寻址机制，使用一个哈希函数来将20位页号映射到6位哈希表。表项包含页号帧号和链指针。如果页表可以给每个哈希表项分配最多3个溢出项的空间，则哈希反向页表需要占用多大的内存空间？ 解答

a：4Mbyte

b：行数：26+2=128项。每项包含：20（页号）+20（帧号）+8bits（链索引）=48bits=6bytes。总共：128*6=768bytes

8.4 一个进程分配给4个页帧（下面的所有数字均为十进制数，每一项都是从0开始计数的）。上一次把一页装入到一个页帧的时间，上一次访问页帧中的页的时间，每个页帧中的虚拟页号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之间的时钟时间，而不是从事件发生到当前的时钟值）。 虚拟页号 页帧 加载时间 访问时间 R位 M位 2 0 60 161 0 1 1 1 130 160 1 0 0 2 26 162 1 0 3 3 20 163 1 1 当虚拟页4发生错误时，使用下列内存管理策略，哪一个页帧将用于置换？解释原因。

a.FIFO（先进先出）算法 b.LRU（最近最少使用）算法 c.Clock算法

d.最佳（使用下面的访问串）算法

e.在页错误之前给定上述内存状态，考虑下面的虚拟页访问序列： 4,0,0,2,4,2,1,0,3,2

如果使用窗口大小为4的工作集策略来代替固定分配，会发生多少页错误？每个页错误何时发生？ 解答

a:页帧3，在时间20加载，时间最长。

b:页帧1，在时间160访问距现在时间最长。 c:清除页帧3的R位（最早加载），清除页帧2的R位，（次最早加载），换出的是页帧0因为它的R位为0。

d:换出的是页帧3中的虚拟页3，因为它将最晚被访问到。 e:一共有6个错误，如下

8.5 一个进程访问5页：A,B,C,D和E，访问顺序如下：

A;B;C;D;A;B;E;A;B;C;D;E

假设置换算法为先进后出，该进程在主存中有三个页帧，开始时为空，请查找在这个访问顺序中传送的页号。对于4个页帧的情况，请重复上面的过程。 解答

分别有9次和10次页错误，这被称之为“Belady′s现象”（\Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine,\Belady et al, Communications of the ACM, June 1969.）

8.6 一个进程在磁盘上包含8个虚拟页，在主存中固定分配给4个页帧。发生如下顺序的页访问：

1,0,2,2,1,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,7,2,4,2,7,3,3,2,3

a.如果使用LRU替换策略，给出相继驻留在这4个页帧中的页。计算主存的命中率。假设这些帧最初是空的。

b.如果使用FIFO策略，重复问题（a）。

c.比较使用这两种策略的命中率。解释为什么这个特殊的访问顺序，使用FIFO的效率接近于LRU。 解答

a:LRU：命中率=16/33

b:FIFO：命中率=16/33

c:这两种策略对这个特殊的页轨迹（执行顺序）是等效的。

8.7 在VAX中，用户页表以系统空间的虚拟地址进行定位。让用户页表位于虚存而不是主存中有什么好处？有什么缺点？ 解答

最主要的优点是在物理内存空间上的节省。这主要是两方面的原因：（1）一个用户页表可以仅当使用时才取入内存。（2）操作系统可以动态的分配用户页表，产生一个页表仅当程序被创建时。

当然，也有一个缺点：地址转换需要多余的工作。 8.8 假设在主存中执行下列程序语句： for(i=1;i≤n;i++) a[i]=b[i]+c[i];

页尺寸为1000个字。令n=1000。使用一台具有所有寄存器指令并使用了索引寄存器的机器，写出实现上述语句的一个假想程序，然后给出在执行过程中的页访问顺序。 解答

由机器语言编写的程序，在主存中地址4000处开始运行。运行情况如下： 4000 （R1）←1 建立索引记录i 4001 （R1）←n 在R2中建立n 4002 比较R2，R1 检查i﹥n 4003 如果大于则跳转到4009

4004 （R3）←B（R1） 使用索引记录R1到达B[i]

4005 （R3）←（R3）+C（R1）使用索引记录R1加上C[i] 4006 A（R1）←（R3）使用索引记录R1将总和存入A[i]中

4007 （R1）←（R1）+1 i加一 4008 跳到4002 6000—6999 存储A 7000—7999 存储B 8000—8999 存储C 9000 存储1 9001 存储n

由这个循环产生的参考串为 494944（47484649444）1000

包括11.000个参考，但仅包括5个不寻常的页

8.9 IBM System/370体系结构使用两级存储器结构，并且分别把这两级称为段和页，这里的分段方法缺少本章所描述的关于段的许多特征。对于这个基本的370体系结构，页尺寸可以是2KB或4KB，段大小固定为64KB或1MB。这种方案缺少一般分段系统的那些优点？370的分段方法有什么好处？ 解答

S/370分段系统是固定的且对程序员是不可见的，因此没有一个分段系统的优点在S/370中实现（无保护情况下）每一个段表项的P位提供整个段表的保护。 8.10 假设页尺寸为4KB，页表项大小位4字节。如果要映射一个64位地址空间，并且最顶层的页表对应于一页，则需要几级页表？ 解答

因为每个页表项有4bytes，每个页表有4Kbytes，所以每个页表可以映射1024=210个页，标识出210×212=222bytes的地址空间。然而，地址空间是264bytes。增加一个二层页表，顶层页表指向210个页表，标识出232个页表，将这个过程继续下去就得到：

深度 地址空间 1 222bytes 2 232bytes 3 242bytes 4 252bytes 5 262bytes 6 272bytes（﹥264bytes） 我们可以看到5层是不够表示64位的地址空间，但是6层达到了要求。但是6层中只有2位被使用，而不是全部的10位。所以不是使用72位的虚拟地址空间，而是将除了最低两位外的其他位全部屏蔽忽略。这样将会得到一个64位地址空间，顶层页只有4个页表项。另外一种方法是修改规则将顶层页做成一个单独的物理页并且让它适合4个页。这样将会节省一个页。

8.11 考虑一个系统该系统采用基于页的内存映射，并使用一级页表。假设页表总是在主存中。

a.如果一次存储器访问需要200ns，那么一次需要调页的存储器访问要多长时间？

b.现在增加一个MMU，在命中或未命中时有20ns的开销。如果假设有85%的存储器访问命中都在MMU TLB中，那么哪些是有效的存储器访问时间？ c.解释TLB命中率如何影响有效的存储器访问时间。 解答

a.400ns。200ns用来得到页表项，200ns用来到达存储位置 b.这是一个常见的有效时间计算公式： （220×0.85）+（420×0.15）=250

两种情况：第一种，TLB中包含所需的页表项。在这种情况下在200ns外多了20ns的存储访问时间。第二种，TLB中不包含所需的页表项。这时我们会再多花200ns来把所需的页表项取入TLB。

c.TLB命中率越高有效存储器访问时间就越短，因为额外的200ns来得到页表项的时间被节省了。

8.12 考虑一个进程的页访问序列，工作集为M帧，最初都是空的。页访问串的长度为P，包含N个不同的页号。对任何一种页替换算法， a.页错误次数的下限是多少？ b.页错误次数的上限是多少？ 解答 a.N b.P

8.13 在论述一种页替换算法时，一位作者用一个在循环轨道上来回移动的雪犁机来模拟说明：雪均匀地落在轨道上，雪犁机一恒定的速度在轨道上不断的循环，轨道上被扫落的雪从系统中消失。

a.8.2节讨论的哪一种页替换算法可以用它来模拟？ b.这个模拟说明了页替换算法的那些行为？ 解答

a.这是一个很好的时钟算法的类似。雪落在轨道上类似于页到达循环页缓存中。时钟算法时钟算法指针的移动类似于雪犁机的移动。

b.注意到在时钟指针最近的前面可替换页的密度是最高的，就好像在雪犁机最近的前面的雪是最厚的一样。因此我们可以认为时钟算法在寻找替换页时是非常有效的。事实上可以看到雪犁机前雪的厚度是轨道上雪平均厚度的两倍。通过这种类似，在单循环中被时钟策略替换的页的号码是被随机替换的页的号码的两倍。这个近似不是最完美的，因为时钟指针并不是以一个确定的速率移动，但是直观意义还是有的。

8.14 在S/370体系结构中，存储关键字是与实存中每个页帧相关联的控制字段。这个关键字中与页替换有关的有两位：访问位和修改位。当在帧中的任何单元执行写操作时，修改位被置为1；当一个新页被装入到该帧中时，访问位被置为1。请给出一种方法，仅仅使用访问位来确定哪个页帧是最近最少使用的。 解答

处理器硬件置访问位为0当一个新页被加入到帧时，置为1当这个页帧的位置被访问到时。操作系统可以维护几个页帧表队列，一个页帧表项从一个队列移动到另一个队列取决于这个页帧的访问位被值为零的时间长短。当必须有页被替换时，被替换的页将从具有最长未被访问时间的页帧队列中选取。 8.15 考虑如下的页访问序列（序列中的每一个元素都是页号）： 12345213323454511325

定义经过k次访问后平均工作集大小为Sk（△）=1/k∑W（t，△）（t=1—k），并且定义经过k次访问后错过页的概率为Mk（△）=1/k∑F（t，△）（t=1—k），其中如果页错误发生在虚拟时间t，则F（t，△）=1，否则F（t，△）=0。

a.当△=1，2，3，4，5，6时，绘制与图8.19类似的图标来说明刚定义的页访问

序列的工作集。

b.写出S20（△）关于△的表达式。 b.写出M20（△）关于△的表达式。 解答 a.

b.c.

S20是一个△的增函数，M20是一个△的非增函数。

8.16 VSWS驻留集管理策略的性能关键是Q的值。经验表明，如果对于一个进程使用固定的的Q值，则在不同的执行阶段，页错误发生的频率有很大的差别。此外对不同的进程使用相同的Q值，则发生页错误的频率会完全不同。这些差别表明，如果有一种机制可以在一个进程的生命周期中动态的调整Q得知，则会提高算法的性能。请基于这种目标设计一种简单的机制。 解答

[PIZZ89]推荐使用如下策略。在窗口中使用一个机构在窗口时间调整Q的值作为实际页错误率的函数，页错误率被计算出并且同作为系统值的作业理想页错误率比较。Q的值被上调（下调）当实际的页错误率比理想值高（低）。使用这种调整机制的实验证明可以动态调整Q值的测试作业在每次运行时产生较少的页错误和减小的驻留集，相比于固定Q值的作业的运行（在很大程度上）。存储时间在相对于Q值使用可调整机制时也会产生一个固定且可观的改进，比较于使用