操作系统第五版1-12章课后题中文答案

生习题：

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

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

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

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

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

员减少对主存储器的访问次数。对高级语言而言，由优化编译器负责决定把哪

些变最应该分配给主存储器。一些高级语言，如C语言，允许程序言建议编

译器把哪些变量保存在寄存器中。

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

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

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

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

从存储器传送到处理器。处理器一1/0：通过处理器和I/O模块间的数据传送，

数据可以输出到外部设备，或者从外部设备输入数据。数据处理，处理器可以

执行很多关于数据的算术操作或逻辑操作。控制：某些指令可以改变执行顺序。

1.4s什么是中断？

答：中断：其他模块（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.开发空间局部性和时间局部性的策略是什么？

答：空间局部性的开发是利用更大的缓冲块并且在存储器控制逻辑中加入预处理机

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

并且定义缓冲存储的优先级。

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

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

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

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

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

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

内核是操作系统最常使用的部分，它存在于主存中并在特权模式下运行,

响应进程调度和设备中断。

2.3什么是多道程序设计？

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

程。

2.4什么是进程？

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

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

执行上下文又称为进程状态，是操作系统用来管理和控制所需的内部数

据。这种内部信息和进程是分开的，因为操作系统信息不允许被进程直接访

问。上下文包括操年系统管理进程以及处理器正确执行进程所需要的所有信

息，包括各种处理器寄存器的内容，如程序计数器和数据寄存器。它还包括

操作系统使用的信息，如进程优先级以及进程是否在等待特定I/O事件的完

成。

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

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

间。

自动分配和管理：程序应该根据需要在存储层次间动态的分配，分配对程序

员是透明的。因此，程序员无需关心与存储限制有关的问题，操作系统有效

的实现分配问题，可以仅在需要时才给作业分配存储空间。

P5I

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

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

存中。实地址指的是主存中的地址。

2.8描述轮循调度技术。

轮循调度是一种调度算法，所有的进程存放在一个环形队列中并按固定

循序依次激活。因为等待一些事件（例如：等待一个子进程或一个I/O操作）

的发生而不能被处理的进程将控制权交给调度器。

2.9解释单体内核和微内核的区别。

单体内核是一个提供操作系统应该提供的功能的大内核，包括调度、文

件系统、网络、设备驱动程序、存储管理等。内核的所有功能成分都能够访

问它的内部数据结构和程序。典型情况下，这个大内核是作为一个进程实现

的，所有元素都共享相同的地址空间。微内核是一个小的有特权的操作系统

内核，只提供包括进程调度、内存管理、和迸程间通信等基本功能，要依靠

其他进程担当起和操作系统内核联系作用。

2.1（）什么是多线程？

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

程。

3.1什么是指令跟踪？

答：指令跟踪是指为该进程而执行的指令序列。（P81）

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、文件和进程。（p92）

3.9列出进程控制块中的三类信息。

答：进程标识，处理器状态信息，进程控制信息。

3.10为什么需要两种模式（用户模式和内核模式）?

答：用户模式下可以执行的指令和访问的内存区域都受到限制。这是为了防止操作系

统受到破坏或者修改。而在内核模式下则没有这些限制，从而使它能够完成其功能。

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

阻塞的系统调用转化为一个不产生阻塞的系统调用。

4.9简单定义图4.8中列出的各种结构。

答：SIMD：一个机器指令控制许多处理部件步伐一致地同时执行。每个处理部件都有一

个相关的数据存储空间，因此，每条指令由不同的处理器在不同的数据集合上执行。

MIMD：•组处理器同时在不同的数据集.上执行不同的指令序列。主/从：操作系统内核

总是在某个特定的处理器上运行，其他处理器只用于执行用户程序，还可能执行一些操

作系统实用程序。SMP:内核可以在任何处理器上执行，并且通常是每个处理器从可用

的进程或线程池中进行各自的调度工作。集群：每个处理器都有一个专用存储器，而且

每个处理部件都是一个独立的计算机。

4.10列出SMP操作系统的主要设计问题。

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

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

服务和功能。(P126)

答：设备驱动程序，文件系统，虚存管理程序，窗口系统和安全服务。

4.12列出并简单解释微内核设计相对于整体式设计的七个优点。

答：一致接口:进程不需要区分是内核级服务还是用户级服务，因为所有服务都是通过

消息传递提供的。可扩展性：允许增加新的服务以及在同一个功能区域中提供多个赧务。

灵活性：不仅可以在操作系统中增加新功能，还可以删减现有的功能，以产生一个更小、

更有效的实现。可移植性：所有或者至少大部分处理器专用代码都在微内核中。因此，

当把系统移植到一个处理器上时只需要很少的变化，而且易于进行逻辑上的归类。可靠

性：小的微内核可以被严格地测试，它使用少量的应用程序编程接口(API),这就为内

核外部的操作系统服务产生高质量的代码提供了机会。分布式系统支持：微内核通信中

消息的方向性决定了它对分布式系统的支持。面向对象操作系统环境：在微内核设计和

操作系统模块化扩展的开发中都可以借助面向对象方法的原理。

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

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

要多。(pl27)

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

答：低级存储器管理，进程间通信(IPC)以及I/O和中断管理。

4.15在微内核操作系统中,进程或线程间通信的基本形式是什么?

答：消息。

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

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

问题(pl44)

5.2列出并发的三种上下文

答：多个应用程序，结构化应用程序，操作系统结构

5.3执行并发进程的最基本要求是什么？

答：加强互斥的能力(pl44)

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

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

方：这些进程并不需要知道对方的进程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.二元信号量与一般信号量有什么区别。

答：二元信号量只能取。或1，而一般信号量可以取任何整数。

5.10强信号量与弱信号量有什么区别。

答：强信号量要求在信号量上等待的进程按照先进先出的规则从队列中移出。弱信号量没有

此规则。

5.11.什么是管程。

答：管程是由一个或多个过程，一个初始化序列和局部数据组成的软件模块。

5.12对于消息，有阻塞和无阻塞有什么区别？

答：p169

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

答：1.任意多的读进程可以同时读这个文件，2.一次只有一个写进程可以往文件中写，3.如

果一个写进程正在往文件中写时，则禁止任何读进程读文件。

第六章习题翻译

第一部分复习题

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

答：可重用资源：处理器，I/O通道，主存和辅存，设备以及诸如文件，数据

库和信号量之类的数据结构。

可消费资源：中断，信号，消息和I/O缓冲区中的信息。

6.2可能发生死锁所必须的三个条件是什么？

答：互斥，占有且等待，非抢占。

6.3产生死锁的第4人条件是什么？

答：循环等待。

6.4如何防止占有且等待的条件？

答：可以要求进程一次性地请求所有需要的资源，并且阻塞这个资源直到所有请

求都同时满足。

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

答：第一种，如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进

程必须释放它最初占用的资源，如果有必要，可再次请求这些资源和另外的资源。

第二种，如果一个进程请求当前被另一个进程占有的一个资源，则操作系

统可以抢占另一个进程，要求它释放资源。

6.6如何防止循环等待条件？

答：可以通过定义资源类型的线性顺序来预防。如果一个进程已经分配到了R类

型的资源，那么它接下来请求的资源只能是那些排在R类型之后的资源类型。

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重新开始行的时候，它将会能够获得Bo

4.P获得A然后Q获得B.P释放A.Q获得A然后释放

B.P获得B然后释放Bo

5.P获得，然后释放A.P获得B.Q执行而且阻塞在对B的请求上。P释放

B。当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考虑下面的一个系统，当前不存在未满足的请求。

可用

rlr2r3r4

100

2

当前分配最大需求

仍然需求

a计算每个进程仍然可能需要的资源，并填入标为“仍然需要”的列中。

b系统当前是处于安全状态还是不安全状态，为什么。

c系统当前是否死锁？为什么？

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

e如果P3的请求（0,1,0,0）到达，是否可以立即安全地同意该请求？在什

么状态（死锁，安全，不安全）下可以立即同意系统剩下的全部请求？如果立即

同意全部请求，哪个进程（如果有）是死锁的或可能变成死锁的？

解：a.0000

0750

6622

2002

rlrlr2

r2r3r4r3r4rlr2r3r4

01

001202

20002750

6

0034656

4

2354356

03320652

0320

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

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

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

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

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

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

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

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

Available=(2100)

20010010

Request二1010Allocation=2001

21000120

解：1.W=(2100)

2.MarkP3;W=(2100)+(0120)=(2220)

3.MarkP2;W=(2220)+(2001)=(4221)

4.MarkPl;nodeadlockdetected没有死锁

6.6一个假脱机系统包含一个输入进程I,用户进程进程P和一个输出进程0,

它们之间用两个缓冲区连接。进程以相等大小的块为单位交换数据，这些块利用

输入缓冲区和输出缓冲区之间的移动边界缓存在磁盘匕并取决于进程的速度。

所使用的通信原语确保满足下面的资源约束：V。Wmax

其中，max表示磁盘中的最大块数，i表示磁盘中的输入块数目，。表示磁盘中的

输出块数目。

以下是关于进程的知识：

1.只要环境提供数据，进程I最终把它输入到磁盘上（只要磁盘空间可用）。

2.只要磁盘可以得到输入，进程P最终消耗掉它，并在磁盘上为每个输入块输

出有限量的数据（只要磁盘空间可用）。

3.只要磁盘可以得到输出，进程0最终消耗掉它。说明这个系统可能死锁。

解：当I的速度远大于P的速度，有可能使磁盘上都是输入数据而此时P进程要处

理输入数据，即要将处理数据放入输出数据区。于是P进程等待磁盘空间输出，1

进程等待磁盘空间输入，二者死锁。

6.7给出在习题6.6中预防死锁的附加资源约束，仍然通话输入和输出缓冲区

之间的边界可以根据进程的要求变化。

解：为输出缓冲区保留一个最小数目（称为res。）块，但是当磁盘空间足够大时允

许输出块的数目超过这一个界限。资源限制现在变成

I+OWmax

IWmax-reso

当0<reso<max

如果程序P正在等候递送输出给磁盘，程序0最后处理所有的早先输出而且

产生至少reso页，然后让P继续执行。因此P不会因为0而延迟。

如果磁盘充满I/O,I能被延迟；但是迟早，所有的早先的

输入可以被P处理完，而且对应的输出将会被0处理，

因而可以让I继续执行。

6.8在THE多道程序设计系统中，一个磁鼓（磁盘的先驱，用做辅存）被划

分为输入缓冲区，处理和输出缓冲区，它们的边界可以移动，这取决于所涉及的

进程速度。磁鼓的当前状态可以用以下参数描述：

max表示磁鼓中的最大页数，i示磁鼓中的愉入页数，p示磁鼓中的处理页数，。

示磁鼓中的输出页数，res。出保留的最小页数，resp理保留的最小页数。

解：

I+O+PWmax-

I+OWmax-resp

I+PWmax-reso

IWmax-(reso+resp)

6.9在THE多道程序设计系统中，一页可以进行下列状态转换：

1.空—输入缓冲区（输入生产）

2.输入缓冲区一处理区域（输入消耗）

3.处理区域输出缓冲区（输出生产）

4.输出缓冲区一空（输出生产）

5.空一处理区域（输出消耗）

6.处理区域一空（过程调用）

a根据I,。和P的量定义这些转换的结果。

b如果维持习题6.6中关于输入进程，用户进程和输出进程的假设，它们中的任

何一个转换是否会导致死锁。

解：1.i-i+1

2.i-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=

。二0,如果消费进程还没有占用完磁盘空间（p<max-reso）,可以产生输入。

结论：分配给消费进程的不受控制的存储空间是

唯一可能引发死锁的因素。

6.10考虑一个共有150个存储器单元的系统，其单元如下分配三个进程:

进程最大占用

17045

26040

36015

使用银行家算法，以确定同意下面的任何一个请求是否安全。如果安全，说明能

保证的终止序列；如果不安全，给出结果分配简表。

a.第4个进程到达，最多需要60个存储单元，最初需要25个单元。

b第4个进程到达，最多需要60个存储单元，最初需要35个单元。

解：a.若同意第4个进程请求，则储存器单元共用去25+15+40+45=125个单元,

还有25个存储单元，则可以安全执行全部进程。安全顺序是1—2—3—4

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

结果分配见表

进程最大占有需要空闲

170452515

2604020

3601545

4603525

6.11评价独家算法在实际应用中是否有用。

解：不切实际的：不能总是预先知道最大要求，进程数目和资源数目可能随着时

间改变。大多数的操作系统忽视死锁。

6.12有一个已经实现了的管道算法，使得进程P0产生的T类型的数据元素

经进程序列P1P2…PnT,并且按该顺序在元素上操作。

a.定义一个一般的消息缓冲区，包含所有部分消耗的数据元素，并按下面的格式

为进程Pi(OWiWn-1)写一个算法。

Repeat

从前驱接收

消耗

给后续发送

Forever

假设P0收到PnT发送的空元素。该算法能够使进程直接在缓冲区中保存的消息

上操作，而无需复制。

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

解：arbuffer:array0..max-1ofsharedT;

available:sharedarray0..n~lof0..max;

Initialization

varK:1..n-1;

regionavailabledo

begin

available(O):=max;

foreverykdoavailable(k):=0;

end

“Processi〃

varj:0..max-1;succ:0..n-1;

begin

j:=0;succ:=(i+1)modn;

repeat

regionavailabledo

awaitavailable(i)>0;

regionbuffer(j)doconsumeelement;

regionavailabledo

begin

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

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

end

j:=(j+1)nodmax;

forever

end

b.死锁可以被解决通过

P0waitsforPn-lAND

PlwaitsforPOAND

Pn-1waitsforPn-2

因为

(available(0)=0)AND

(available(1)0)AND

(available(n-1)=0)

但是如果max>0,这个条件不成立，因为临界域满足

claim{l)+claimk,2,+…

<available(J)+avai…+available(哈

=max

6.13a.3个进程共享4个资源单元，一次只能保留或释放一个单元。每个

进程最大需要2个单元。说明不会死锁。

b.N个进程共享M个资源单元，一次只能保留或释放一个单元。每个进程最大需

要单元数不超过M,并且所有最大需求的总和小于M+N。说明不会发生死锁。

解：a.说明由于每个进程最多需要2个资源，最坏情况下，每个进程需要获得一

个，系统还剩1个，这一个资源，无论分给谁都能完成。完成进程释放资源后，

使剩余进程也完成，故系统不会死锁。

b.假定每个进程最多申请X个资源，最坏情况下，每个进程都得到XT个资

源都在申请最后一个资源，这时系统剩余资源数量为M-N(X—1),只要系统还有

一个剩余资源，就可以使其中的一个进程获得所需要的全部资源，该进程运行结

束以后释放资源，就可以使其他进程得到全部资源的满足，因此，当M-N(XT)》

1时系统不会发生死锁，解这个不等式X《(M+N-1)，系统不会发生死锁，因此,

当所有进程的需求总和小于M+N时，系统是不会发生死锁的。

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

配矩阵是

3'1

21

C=9A=3

72

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

解：最小资源数是3个，总共有10个资源。P2获得一个资源，完成后释

放两个资源，P1获得三个资源，完成后释放三个资源，接下来P4获得五个资

源，释放完资源后，F3获得所需的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(nm),死锁检测的复杂度是0(n)。资源-从属链被线程数目，资源数目和分配

数目限制。

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

这一个运算法则运行也需要运行上述的相同的时间检查。

在写内存上的复杂度为0(n)。

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

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

的危险，他们完成的可能性低。其次，他们与其他重新开始线程竞争有限的执行

时间，因此整个系统运行的速度很慢。

6.16评价下面给出的就餐问题的解决方案。一位饥饿的哲学家首先拿起他左

边的叉子，如果他右边的叉子也是可用的，则拿起右边的叉子开始吃饭，否则他

放下左边的义子，并重复这个循环。

解：如果哲学家们步调完全一致地拿起左边叉子又放下的话，他们会重复这一过

程，导致饥饿情况的出现。

6.17假设有两种类型的哲学家。一类总是先拿起左边的叉子(左撇子)，另

一类总是先拿起右边的叉子(右撇子)。左撇子的行为和图6.12中定义的一

致。右撇子的行为如下：

begin

repeat

think;

wait(fork[(i+l)mod5]);

wait(fork[i]);

eat;

signal(fork[i]);

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

forever;

end;

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

锁。

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

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

支叉子被邻居占有。不失一般性，设Pj是一个左撇子。Pj抓牢他的左边叉子

而且没有他的右边叉子，他的右边邻居Pk没有完成就餐因此也是一个左撇子。

因此依次推理下去所有这D个哲学家都是左撇子。这与既有左撇子又有右撇子的

条件矛盾，假设不成立，不存在死锁。

b

假设左撇子Pj饥饿，也就是说，有一部分人在就餐而Pj从不吃。假如Pj没

有叉子。这样Pj的左边邻居Pi一定持续地占有叉子而始终不吃完。因此Pi

是右撇子，

抓住他的右边叉子，但是从不得到他的左边叉子来完成就餐,也就是说Pi

也饥饿9现在Pi左边邻居也一定是持续占有右边叉子的右撇子。向左进行这

样的推理，得出所有哲学家都是饥饿的右撇子，这同Pj是个左撇子矛盾。因此Pj

一直拥有左边子而且在等待他的右边叉子,Pj的右边邻居Pk一直举着他的左

边叉子而且从不完成一餐,也就是，Pk是也饥饿的左撇子。如果Pk不是一直

拿着他的左边又子，Pj就可以就餐；因此Pk拿着他的左边义子。向右推理可

得所有哲学家都是饥饿的左撇子。这与条件矛盾，因此假设不成立，没有人饥饿。

6.18图1.17显示了另外一个使用管程解决哲学家就餐问题的方法。和图6.

14比较并阐述你的结论。

解：图6.14是等待可用的叉子，图6.17是等待邻居吃完，在本质上逻置是

一样的，后者显得更加紧凑。

monitordining_controller;

enunistates}thinking,hungry,eating}statcl5|;

condneedFork[5]/*conditionvariable*/

voidget_forks(intpid)/*pidisthephilosopheridnumber*/

(

start[pid|=hungry;/*announcethatIamhungry*/

if(s(aie[(pid+1)%S]==eaiing

||(state[(pid-l)%5]==eating

cwait(nccdForklpid]);/*waitifeitherneighboriseating*/

slaie[pid]=ealing;/"proceedifneitherneighboriseating*/

}

voidrelease_fork(intpid)

(

state[pid]=thinking;

/*givcright(highcr)ncighborachancetocat*/

if(sta(e[(pid+l)%5])==hungry)

&(state[(pid+2)%5])!=eating)

csignal(needFork[pid+l|);

/*giveleft(lower)neighborachancetoeat*/

elseif(state[(pid-1)%5J==hungry)

||(state[(pid-2)%5!=eating]

voidphilosopher[k=0to4]/*thefivephilosopherclients*/

{

while(true)

(

<think>;

get_fbrks(k);/"clientrequeststwoforksviamonitor*/

<eatspaghctti>;

release_forks(k);/*clientreleasesforksviathemonitor*/

)

)

6.19在表6.13中，Linux的一些原子操作不会涉及到对同一变量的两次访

问。Ltlatomic_read(atomic_t*v).简单的读操作在任何体系结构中都是原子

的。为什么该操柞增加到了原字操作的指令表？

解：原子操作是在原子数据类型上操作，原子数据类型有他们自己的内在的

格式。因此，不能用简单的阅读操作，但是特别的阅读操作

对于原子数据类型来说是不可或缺的.

6.20考虑Linux系统中的如下代码片断：

readlock(&mrrwlock);

write_lock(&mr_rwlock);

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

解：因为写者锁将会自旋，所以这段代码会导致死锁，等待所有的

读者解锁，包括唤醒这个线程。

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

线线程

程12

a=3；一

mb()；—

一C=b；

一rmb()；

d=a；

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

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

值。举例来说，c可以等于4(我们期待的)，然而d可能等于1.(不是我们期

待的)。使用nib()确保a和b按合适的次序被写，使用rmb()确保c和d按

合适的次序被读。

第7章内存管理

复习题：

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

答：重定位、保护、共享、逻辑组织和物理组织。

7.2.为什么需要重定位进程的能力?

答：通常情况下，并不能事先知道在某个程序执行期间会有哪个程序驻留在主存中。

此外还希望通过提供一个巨大的就绪进程池，能够把活动进程换入和换出主存，以便

使处理器的利用率最大化。在这两种情况下，进程在主存中的确切位置是不可预知的。

7.3.为什么不可能在编译时实施内存保护?

答：由于程序在主存中的位置是不可预测的，因而在编译时不可能检查绝对地址来确

保保护。并且，大多数程序设计语言允许在运行时进行地址的动态计算(例如，通过

计算数组下标或数据结构中的指针)。因此，必须在运行时检查进程产生的所有存储

器访问，以便确保它们只访问了分配给该进程的存储空间。

7.4.允许两个或多个进程访问进程的某一特定区域的原因是什么?

答：如果许多进程正在执行同一程序，则允许每个进程访问该程序的同一个副本要比

让每个进程有自己单独的副本更有优势。同样，合作完成同一任务的进程可能需要共

享访问同一个数据结构。

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

答：通过使用大小不等的固定分区：1.可以在提供很多分区的同时提供一到两个非常

大的分区。大的分区允许将很大的进程全部载入主存中。2.由「小的进程可以被放入

小的分区中，从而减少了内部碎片。

7.6.内部碎片和外部碎片有什么区别?

答：内部碎片是指由于被装入的数据块小于分区大小而导致的分区内部所浪费的空

间。外部碎片是与动态分区相关的一种现象，它是指在所有分区外的存储空间会变成

越来越多的碎片的。

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

答：逻辑地址是指与当前数据在内存中的物理分配地址无关的访问地址，在执行对内

存的访问之前必须把它转化成物理地址。相对地址是逻辑地址的一个特例，是相对于

某些已知点（通常是程序的开始处）的存储单元。物理地址或绝对地址是数据在主存

中的实际位置。

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

答：在分页系统中，进程和磁盘上存储的数据被分成大小固定相等的小块，叫做页。

而主存被分成了同样大小的小块，叫做帧。一页恰好可以被装入一帧中。

79页和段之间有什么区别?

答：分段是细分用户程序的另一种可选方案。采用分段技术，程序和相关的数据被划

分成一组段。尽管有一个最大段长度，但并不需要所有的程序的所有段的长度都相等。

习题：

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

的。

答：重定位-支持模块化程序设计；

保护比保护和访问控制以及进程隔离；

共享七保护和访问控制；

逻辑组织-支持模块化程序设计；

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

7.2.考虑使用大小相等分区的固定分区方案。分区大小为2el6字节，贮存的大小为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的块放入第一个洞中.起始地址足

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

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

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

请求80；返回A；请求60；返回B；返回D；返回C。

b.给出返回B之后的二叉树表示。

答：

Request70A128256512

Request35AB64256512

Request80ABC128512

ReturnA128B64c128512

Request60128B1)d128512

ReturnB12864Dc128512

ReturnP256c128512

ReturnCW24

b.

12864DC128512

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

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

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

答：

a.011011110100

b.011011100000

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

答：

.V+2Aif.vmod2-1=0

buddy/)

,v-2*if.tmod=2"

7.10.Fabonacci序列定义如下：

Fo=O,Fi=l,F*Fn”+Fn,nMO

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

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

答：

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

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

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

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

字，但如果遇到会导致在程序中其他地址继续执行的转跳或调用指令，处理器将修改

这个寄存器的内容。现在考虑图7.8。关于指令地址有两种选择：

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

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

寄存器中。

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

转换，其结果保存到指令寄存器中。

哪种方法更好？

答：使用绝对地址可以减少动态地址转换的次数。但是，我们希望程序能够被重定位。

因此，在指令寄存器中保存相对地址似乎就更好一些。也可以选择在进程被换出主存

时将指令寄存器中的地址转换为相对地址。

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

空间为*个页。

a.逻辑地址空间包含多少位？

b.一个帧中包含多少字节？

c.在物理地址中指定帧需要多少位？

d.在页表中包含多少个页表项？

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

答：

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

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

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

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

e.加上有效/无效位，每个页表项包含23位。

7.13.分页系统中的虚地址a相当于一对（p,w）,其中p是页号，w是页中的字节号。令z

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

答：关系是：a=pz+w,其中p=l_a/zj,a/z的整数部分。w=Rz（a）,a除

以z的余数

7.14.在一个简单分段系统中，包含如下段表：

起始地址长度（字节）

660248

1752442

222198

996604

对如下的每一个逻辑地址，确定其对应的物理地址或者说明段错误是否会发生:

a.0,198

b.