操作系统概念第七版7-9章课后题答案（中文版）

7.1

假设有如图7.1所示的交通死锁。

a. 证明这个例子中实际上包括了死锁的四个必要条件。 b. 给出一个简单的规则用来在这个系统中避免死锁。

a. 死锁的四个必要条件: (1)互斥；（2）占有并等待；（3）非抢占；（4）循环等待。 互斥的条件是只有一辆车占据道路上的一个空间位置。占有并等待表示一辆车占据道路上的位置并且等待前进。一辆车不能从道路上当前的位置移动开（就是非抢占）。最后就是循环等待，因为每个车正等待着随后的汽车向前发展。循环等待的条件也很容易从图形中观察到。 b. 一个简单的避免这种的交通死锁的规则是，汽车不得进入一个十字路口如果明确地规定，

这样就不会产生相交。 7.2

考虑如下的死锁可能发生在哲学家进餐中，哲学家在同个时间获得筷子。讨论此种情况下死锁的四个必要条件的设置。讨论如何在消除其中任一条件来避免死锁的发生。

死锁是可能的，因为哲学家进餐问题是以以下的方式满足四个必要条件：1）相斥所需的筷子， 2 ）哲学家守住的筷子在手，而他们等待其他筷子， 3 ）没有非抢占的筷子，一个筷子分配给一个哲学家不能被强行拿走，4 ）有可能循环等待。死锁可避免克服的条件方式如下： 1 ）允许同时分享筷子， 2 ）有哲学家放弃第一双筷子如果他们无法获得其他筷子， 3 ）允许筷子被强行拿走如果筷子已经被一位哲学家了占有了很长一段时间4 ）实施编号筷子，总是获得较低编号的筷子，之后才能获得较高的编号的筷子。

7.3

一种可能以防止死锁的解决办法是要有一个单一的，优先于任何其他资源的资源。例如，如果多个线程试图访问同步对象A??E，那么就可能发生死锁。（这种同步对象可能包括互斥体，信号量，条件变量等），我们可以通过增加第六个对象来防止死锁。每当一个线程希望获得同步锁定给对象A? ? ?E，它必须首先获得对象F的锁.该解决方案被称为遏制：对象A? ? ?E的锁内载对象F的锁。 对比此方案的循环等待和Section7.4.4的循环等待。

这很可能不是一个好的解决办法，因为它产生过大的范围。尽可能在狭隘的范围内定义死锁政策会更好。

7.4

对下列问题对比循环等待方法和死锁避免方法(例如银行家算法)： a.运行费用

b.系统的吞吐量

死锁避免方法往往会因为追踪当前资源分配的成本从来增加了运行费用。然而死锁避免方法比静态地防止死锁的形成方法允许更多地并发使用资源。从这个意义上说，死锁避免方案可以增加系统的吞吐量。

7.5

在一个真实的计算机系统中，可用的资源和进程命令对资源的要求都不会持续很久是一致的长期（几个月）。资源会损坏或被替换，新的进程会进入和离开系统，新的资源会被购买和添加到系统中。如果用银行家算法控制死锁，下面哪

些变化是安全的（不会导致可能的死锁） ，并且在什么情况下发生？ a. 增加可用资源（新的资源被添加到系统）

b. 减少可用资源（资源被从系统中永久性地移出）

c. 增加一个进程的Max（进程需要更多的资源，超过所允许给予的资源） d. 减少一个进程的Max（进程不再需要那么多资源） e. 增加进程的数量 f. 减少进程的数量

a. 增加可用资源（新的资源被添加到系统）：这个可以在没有任何问题的情况下安全地改

变 b. 减少可用资源（资源被从系统中永久性地移出）：这可能会影响到系统，并导致可能性

死锁因为系统的安全性假定其拥有一定数量的可用资源

c. 增加一个进程的Max（进程需要更多的资源，超过所允许给予的资源）：这可能会影响到系统，并可能导致死锁 d. 减少一个进程的Max（进程不再需要那么多资源）：这个可以在没有任何问题的情况下安全地改变

e. 增加进程的数量：如果允许分配资源给新进程，那么该系统并没有进入一个不安全的状态。

f. 减少进程的数量：这个可以在没有任何问题的情况下安全地改变 7.6

假设系统中有四个相同类型的资源被三个进程共享。每个进程最多需要两个资源。证明这个系统不会死锁。

假设该系统陷入死锁。这意味着，每一个进程持有一个资源，并且正等待另一个资源。因为有三个进程和四个资源，一个进程就必须获取两个资源。这一进程并不需要更多的资源，因此当其完成时会返回其资源。

7.7假设一个系统有m个资源被n个进程共享，进程每次只请求和释放一个资源。证明只要系统符合下面两个条件，就不会发生死锁： a.每个进程需要资源的最大值在1到m之间 b.所有进程需要资源的最大值的和小于m+n Answer:使用Section7.6.2的术语,可以有： a. _n

i =1 Maxi < m + n

b. Maxi ≥ 1 for all i

Proof: Needi = Maxi ? Alloca tioni If there exists a deadlock state then: c. _n

i =1 Alloca tioni = m

Use a. to get:_ Needi + _ Alloca tioni = _ Maxi < m + n Use c. to get:_ Needi + m < m + n Rewrite to get:_n

i =1 Needi < n

//符号打不出来，大家自己看答案

这意味着存在一个Pi的进程，其Needi=0.如果Maxi>=1，那么Pi进程至少有一个资源可以释放。从而系统就不会进入死锁状态。

7.8假设哲学家进餐问题中，筷子被摆放在桌子的中央，它们中的任何一双都可以被哲学家

使用。假如每次只能请求一根筷子，试描述一种在没有引起死锁的情况下，一个特殊的请求请求能否被满足的简单的规则，将筷子分配给哲学家。

Answer:以下规则避免了死锁：当一个哲学家发出一个需要第一根筷子的请求时，如果没有别的哲学家有两根筷子或者只留有一根筷子时，这个请求就不被允许。

7.9与上一题目中所给的环境相同。假如现在每个哲学家请求三根筷子来吃饭，而且这种资源请求仍旧是分开发生的。试描述一种类似的在没有引起死锁的情况下，一个特殊的请求请求能否被满足的简单的规则，将筷子分配给哲学家。

Answer: 当一个哲学家发出一个需要第一根筷子的请求时，满足其情况，如果1）那个哲学家已经有2根筷子，并且还有2根筷子剩余，2) 那个哲学家已经有1根筷子，并且还有2根筷子剩余，3）最少有1根筷子剩余，并且最少有一个哲学家拥有3根筷子，4）那个哲学家没有筷子，但有2根筷子剩余，并且最少存在另外一个拥有2根筷子的哲学家放下他的筷子。 7.10我们可以通过把数组的维度减少到1，而从一般的银行家算法中得到一个单一资源类型的银行家算法。试通过一个例子说明对于每个资源类型，多资源类型的银行家方案不能通过单一资源类型方案的单独运用来实现。

Answer:假设一个系统有资源A,B,C和进程P0, P1, P2, P3, P4，并按照下图来分配 ALLOCATION P0, P1, P2 P3 P4 A 0 3 3 2 0 Need P0 P1 P2 P3 P4 A 7 0 6 0 4 B 4 2 0 1 3 C 3 0 0 1 1 B 1 0 0 1 0 C 0 2 2 1 2 还需要下列资源的数量 如果可利用的资源是（2 3 0），我们可以看到，进程P0请求（0，2，0）是不能被满足的，因为它比Availiable少（2 1 0），从而导致没有一个进程可以被完成。

然而，如果我们把三种资源看做是三个独立资源类型的银行家算法，可以得到以下各表： 对于资源A

P0, P1 P2 P3 P4 Allocated 0 3 3 2 0 Need 7 0 6 0 4 在次序P1, P3, P4，P2, P0下，各进程可以被满足。 对于资源B

P0, P1 P2 P3 P4 Allocated 3 0 0 1 0 Need 2 2 0 1 3 在次序P2, P3, P1 , P0，P4下，各进程可以被满足。 对于资源C

P0, P1 P2 P3 P4 Allocated 0 2 2 1 2 Need 3 0 0 1 1 在次序P1, P2, P0,P3, P4下，各进程可以被满足。 我们可以看出，如果我们使用多重资源类型的银行家算法，对于进程P0的请求（0 2 0）是无法满足的，因为它使系统处于一个不安全的状态，然而，如果我们使用单一资源类型的银行家算法，把它们看做是三个分开的资源，这个请求是允许的。同时，如果我们有多重资源类型，我们则必须使用多重资源类型的银行家算法。 7.11考虑下面的一个系统在某一时刻的状态：

Allocation Max Available A B C D A B C D A B C D P0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 6 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 使用银行家算法回答下面问题： a.Need矩阵的内容是怎样的？

b.系统是否处于安全状态？

c.如果从进程P1发出一个请求（0 4 2 0），这个请求能否被满足？

Answer：a.Need矩阵的内容是P0（0 0 0 0） P1（0 7 5 0） P2（1 0 0 2） P3（0 0 2 0）

P4（0 6 4 0）。

b. .系统处于安全状态，因为Available矩阵等于（1 5 2 0），进程P0和P3都可以运行，当进程P3运行完时，它释放它的资源，而允许其它进程运行。

c.可以被满足，满足以后，Available矩阵等于（1 1 0 0），当以次序P0，P2, P3, P1 ,P4运行时候，可以完成运行。

7.12在死锁检测算法中，乐观假设是什么？这种假设怎样可以被违反？

Answer：乐观假设是在资源分配方面和进程请求资源的过程中，不存在任何形式的循环等待。如果在实际过程中，一个循环等待确实发生，这种假设可以被违反。

8.1解释内部碎片和外部碎片的区别？

Answer：内部碎片是某一区域或某一页中，未被占据其位置的作业所使用的区域。直到作业完成，释放页或区域，这个空间才能被系统所利用。

8.2考虑下面产生二进制的过程。编译器是用来为每个独立单元产生目标代码，连接编辑器是用来联合各个部分的目标单元组成一个单一的程序二进制。连接编辑器是怎样对内存地址改变指令和数据的捆绑？从编译器到连接编辑器，什么信息需要被通过，而使内存绑定连接编辑器作业比较容易？

Answer：连接编辑器不得不将分解的符号地址替换为在最终的程序二进制中，与变量相联系的实际地址。为了完成这个，单元必须追踪那些查阅到的未分解的符号指令。在连接期间，全部程序二进制中的每个单元会被分配到一序列的地址空间，当它完成时，对于未分解的符号关系，可以通过这个二进制输出，当每个另外单元包含一系列需要修复的指令时，这个二进制可以在另外单元被修复。

8.3按顺序给出5个部分的内存，分别是100KB,500KB,200KB,300KB和600KB，用 first-fit,best-fit和worst-fit算法，能够怎样按顺序分配进程212KB,417KB,112KB,426KB和426KB？哪个算法充分利用了内存空间？ Answer：

a. First-fit:

b. 212K is put in 500K partition c. 417K is put in 600K partition

d. 112K is put in 288K partition (new partition 288K = 500K ? 212K) e. 426K must wait

f. Best-fit:

g. 212K is put in 300K partition h. 417K is put in 500K partition i. 112K is put in 200K partition j. 426K is put in 600K partition k. Worst-fit:

l. 212K is put in 600K partition m. 417K is put in 500K partition n. 112K is put in 388K partition o. 426K must wait

Best-fit: 算法充分利用了内存空间。

8.4在运行过程中，许多系统允许程序分配更多的内存给它的地址空间。在程序堆中的数据分配是这种分配方式的一个实例。在下面的方案中，为了支持动态内存分配的要求是什么？ a.连续内存分配b.纯段式分配c.纯页式分配

Answer：a. 连续内存分配:当没有足够的空间给程序去扩大它已分配的内存空间时，将要求重新分配整个程序。

b. 纯段式分配：当没有足够的空间给段去扩大它的已分配内存空间时，将要求重新分配整个段。

c. 纯页式分配：在没有要求程序地址空间再分配的方案下，新页增加的分配是可能的。 8.5 比较在主存组织方案中，连续内存分配，纯段式分配和纯页式分配在下面问题中的关系。 a.外部碎片b.内部碎片c.通过进程分享代码的能力

Answer：连续内存分配会产生外部碎片，因为地址空间是被连续分配的，当旧进程结束，新进程初始化的时候，洞会扩大。连续内存分配也不允许进程共享代码，因为一个进程的虚

产生页错误

9.18 假设有一个初始值为1024 kB的段，使用伙伴(Buddy system)系统分配其内存。以图9.27为指导，画出树来说明下列内存请求是如何分配的：

? 请求240字节 ? 请求120字节 ? 请求60字节 ? 请求130字节

下一步，为下列内存释放修改树。只要有可能便执行接合：

? 释放250字节 ? 释放60字节 ? 释放120字节 Answer:

伙伴(Buddy system)系统进行了下列分配：为240字节的请求分配一个256字节段。为120字节的请求分配一个128字节段，为60字节的请求分配一个64字节段，为130字节的请求分配一个256字节段。分配后，下列大小的段是可用的：64 bytes，256 bytes，1K, 2K, 4K, 8K, 16K, 32K, 64K, 128K, 256K, 和 512K。内存释放后，仅剩包含130字节数据的256字节段在使用。下列段将是空闲的：256 bytes, 512 bytes, 1K, 2K, 4K, 8K, 16K, 32K, 64K, 128K, 256K, 和 512K。

9.19 slab分配算法为每个不同的对象类型使用一个单独的缓存。假设每一个对象类型都有一个缓存，试解释，为什么这不与多个CPU较好地协调。怎么做才能解决这个可扩展性问题？ Answer:

这一直是slab分配存在的一个问题——多CPU存在时的较差可扩展性。这个问题产生于必须锁定正被访问的全局缓存。这影响多处理器系统的序列缓存访问。Solaris操作系统凭借引进一个单CPU缓存，而非一个单一的全局缓存解决了这个问题

9.20假设一个为其进程分配不同大小页的系统。这种页面调度方法有何优点？虚拟内存系统提供此功能时进行了哪些修正？ Answer:

程序可能有大量的代码段或使用大型的数组作为数据。这部分程序可被分配于较大的页，从而减少与页表相关的内存开销。考虑到不同的内存大小，虚拟内存系统就必须保持多个不同大小的空闲页链表，为了地址翻译也需要有复杂的代码。

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