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

操作系统概念第七版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

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

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

些变化是安全的（不会导致可能的死锁） ，并且在什么情况下发生？ 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假设哲学家进餐问题中，筷子被摆放在桌子的中央，它们中的任何一双都可以被哲学家

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

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

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

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

Answer: 当一个哲学家发出一个需要第一根筷子的请求时，满足其情况，如果1）那个哲学家已经有2根筷子，并且还有2根筷子剩余，2) 那个哲学家已经有1根筷子，并且还有2根筷子剩余，3）最少有1根筷子剩余，并且最少有一个哲学家拥有3根筷子，4）那个哲学家没有筷子，但有2根筷子剩余，并且最少存在另外一个拥有2根筷子的哲学家放下他的筷子。

7.10我们可以通过把数组的维度减少到1，而从一般的银行家算法中得到一个单一资源类型的银行家算法。试通过一个例子说明对于每个资源类型，多资源类型的银行家方案不能通过单一资源类型方案的单独运用来实现。

Answer:

如果可利用的资源是（2 3 0），我们可以看到，进程P0请求（0，2，0）是不能被满足的，因为它比Availiable少（2 1 0），从而导致没有一个进程可以被完成。

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

134，20

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

对于资源B

2310，4对于资源C

120,34我们可以看出，如果我们使用多重资源类型的银行家算法，对于进程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：乐观假设是在资源分配方面和进程请求资源的过程中，不存在任何形式的循环等待。如果在实际过程中，一个循环等待确实发生，这种假设可以被违反。

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

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

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

拟内存段是不被允许闯入不连续的段的。纯段式分配也会产生外部碎片，因为在物理内存中，一个进程的段是被连续放置的，以及当死进程的段被新进程的段所替代时，碎片也将会产生。然而，段式分配可以使进程共享代码；比如，两个不同的进程可以共享一个代码段，但是有不同的数据段。纯页式分配不会产生外部碎片，但会产生内部碎片。进程可以在页granularity中被分配，以及如果一页没有被完全利用，它就会产生内部碎片并且会产生一个相当的空间浪费。在页granularity，页式分配也允许进程共享代码。

8.6在一个页式分配系统中，为什么一个进程不被允许进入它所不拥有的内存？操作系统怎么能被允许进入其它内存？它为什么应当可以或不可以进入？

Answer：地址在页式分配系统上是一个逻辑页号和一个偏移量。在逻辑页号的基础上产生一个物理页号，物理页通过搜索表被找到。因为操作系统控制这张表的内容，只有在这些物理页被分配到进程中时，它可以限制一个进程的进入。一个进程想要分配一个它所不拥有的页是不可能的，因为这一页在页表中不存在。为了允许这样的进入，操作系统只简单的需要准许入口给无进程内存被加到进程页表中。当两个或多个进程需要交换数据时，这是十分有用的。------它们只是读和写相同的物理地址（可能在多样的物理地址中）。在进程内通信时，这是十分高效的。

8.7比较页式存储与段式存储为了从虚地址转变为物理地址，在被要求的地址转化结构的内存数量方面的有关内容。

c页式存储需要更多的内存来保持转化结构，段式存储的每个段只需要两个寄存器，一个保存段的基地址，另一个保存段的长度。另一方面，页式存储每一页都需要一个入口，这个入口提供了那页所在的物理地址。

8.8在许多系统中的程序二进制的一般构造如下：代码被存储在较小的固定的地址中，比例0。代码段后紧跟着被用来存储程序变量的数据段。当这个程序开始运行，栈被分配到虚地址空间的另一个端末尾，并被允许向较低的虚地址扩张。上述结构在下列方案中具有什么意义: a.连续内存分配b.纯段式分配c.纯页式分配

Answer：1）当程序开始运行时，连续内存分配要求操作系统给程序分配最大限度的虚地址空间。这可能造成比进程所需要的实际内存大很多。2）纯段式分配，在程序开始运行时，给每个段分配较小的空间，而且能随着段的扩展而扩大，这就给操作系统提供了灵活性。3）纯页式分配在一个进程开始运行时，就不需要操作系统给进程分配最大的虚地址空间。当一个程序需要扩展它的堆或栈时，它需要分配一个新的页，但是相关的页表入口被提前分配了。

8.9考虑一个分页系统在内存中存储着一张页表。a.如果内存的查询需要200毫秒，那么一个分页内存的查询需要多长时间？b.如果我们加上相关联的寄存器，75%的页表查询可以在相关联的寄存器中找到，那么有效的查询时间是多少？（假设如果入口存在的话，在相关的寄存器中找到页表入口不花费时间）

Answer：a.400毫秒：200毫秒进入页表，200毫秒进入内存中的字

b.有效进入时间=0.75*200毫秒+0.25*400毫秒=250毫秒

8.10为什么有时候段式分配存储与页式分配存储可以联合成一种方案？

Answer：段式存储与页式存储经常结合在一起是为了提高它们两个中的每一个存储方式。当页表变的十分大时，段式存储是十分有用的。一大段连续的页表是不习惯被分解成为一个以0为段表地址的单一段表入口。分页的段式存储句柄有一个非常大的段的时侯，就需要很多时间来进行分配。通过把段分页，我们降低了由于外部碎片而造成的内存浪费，而且也简化了分配。

8.11解释为什么当共享一个使用段式存储的reenteant单元时比纯页式存储时这样做要来的容易？

Answer：因为段式存储是以内存的逻辑共享为基础的，而不是物理的，任何大小的段在段

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

表中，被每个只具有一个入口的用户所共享。而分页必须在页表中对每个被共享的页有相同的入口。

8.13问:页表分页的目的是什么?

答：在某些情况下,分页的页表可以变得足够大，可以简化内存分配问题（确保全部可以分

配固定大小的网页，而不是可变大小的块），确保当前未使用的部分页表可以交换。

8.14问：考虑分层分页方案，使用VAX架构。当用户程序执行一个内存装载程序时，有多

少个内存操作要执行？

答：当一个内存装载程序完成时，有三个内存操作可以完成，一个是说明能够被打到的页表

的位置。第二个是页表进入自己。第三个是现实的内存装载操作。

8.15问：比较段页式表和哈希页表在处理大量的地址空间上，在什么环境下，哪一个方案更

好？

答：当一个程序占用大的虚拟地址空间的一小部分时，哈希页表更适合小一点的。哈希页表

的缺点是在同样的哈希页表上，映射多个页面而引起的冲突。如果多个页表映射在同个入口处，则横穿名单相应的哈希页表可能导致负担过重。这种间接最低的分割分页方案，即每一页表条目保持有关只有一页。

8.16问：假设Intel的地址转换方案如图8.22所示

A．描述Intel80836将逻辑地址转换成物理地址所采用的所有步骤。

B．使用这样复杂的地址转换硬件对硬件系统有什么好处？

C．这样的地址转换系统有没有什么缺点？如果有，有哪些？如果没有，为什么不是每个制造商都使用这种方案。

答：A。选择符是段描述符表的标志，段描述符的结果加上原先的偏移量构成页表，再加上目录、偏移量构成页表，构成线性地址。这个目录是页目录的标志。目录项选择页表，页表域是页表的索引。页表项再加上偏移量，构成物理地址。

B.这样的页表转换系统提供了灵活性，允许大多数操作系统在硬件上执行内存工具，而不是实施部分硬件和一些软件。因为，它可以在硬件上实施，更有效率（内核更简单）

C.地址转换在查找多样表时更花时间，缓存帮助，仍会导致缓存丢失。

9.1问。举一个例子，IBM360/370 的资源和目的地区重叠时说明，（MVC）重新启动移动块的问题。

答：假设页面边缘为1024，移动空间从资源区800：1200到目标区700：1100，假设当页表

在1024边缘发生故障访问错误，这时候的位置800：923已覆盖新的值，因此，重新启动区块移动指令会导致在800：923到700：823之间复制新的值，而这是不正确的。

9.2问：考虑支持请求页面调度的硬件需求。

答：对于每一个内存访问操作，页表需要检查相应的页表驻留与否和是否计划已经读取或写入权限访问页面，一个TLB可以作为高速缓存和改善业绩的查询操作。

9.3问：什么是写时拷贝功能，在什么情况下，有利于此功能？支持此功能的硬件是什么？ 答：当两个进程正在访问同一套程序值（例如，代码段的二进制代码）在写保护的方式下，

映射相应的页面到虚拟地址空间是有用的，当写操作进行时，拷贝必须允许两个程序分别进行不同的拷贝而不干扰对方。硬件要求：在每个内存访问的页表需要协商，以检查是否该页表是写保护。如果确实是写保护，陷阱会出现，操作系统可以解决这个问题。

9.4问：某个计算机给它的用户提供了232的虚拟内存空间，计算机有214B的物理内存，虚拟内存使用页面大小为4094B的分页机制实现。一个用户进程产生虚拟地址11123456，现在说明一下系统怎么样建立相应的物理地址，区分一下软件操作和硬件操作。（第六版有翻译）

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

答：该虚拟地址的二进制形式是 0001 0001 0001 0010 0011 0100 0101 0110。由于页面大小

为212，页表大小为220，因此，低12位的“0100 0101 0110 ”被用来替换页（page），而前20位“0001 0001 0001 0010 0011”被用来替换页表(page table)。

9.5假设有一个请求调页存储器，页表放在寄存器中：处理一个页错误，当有空的帧或被置换的页设有被修改过时要用8ms，当被置换的页被修改过明用20ms，存储器访问时间为100ns。

假设被置换的页中有70％被修改过，有效访问时间不超过200ns时最大可接受的页错误率是多少？（第六版有翻译）

答：0.2 _sec = (1 P) × 0.1 _sec + (0.3P) × 8 millisec + (0.7P) × 20 millisec

0.1 = 0.1P + 2400 P + 14000 P

0.1 _ 16,400 P

P _ 0.000006

9.6问：假设正在监测的速度指针在时钟算法（表明侯选页面更换），如果发生以下行为，系统会怎么样？

A.指针快速前进 B.指针移动缓慢

答：如果指针运行快，则该程序同时访问大量页面，当指针在对应的页面上清理与检查时，

这是最可能发生的，因此不能被取代，这样做的结果是受害页面被发现之前，扫描很多页面。如果指针运行慢，在虚拟内存找寻候选页表更换极为有效，表明许多常驻页面不会被窍取。

9.7问：讨论在哪一种情况下，LFU（最不经常使用）页置换比LRU（最近最少使用）页置换法产生较少的页面错误，什么情况下则相反？

答：考虑下面顺序存取在内存的系统的串，可容纳4页内存：1 1 2 3 4 5 1，当访问5时，

LFU算法将会替换除了1以外的其他页面，则在接下来读取1时，就不用更次替换了。反来过说，如果串为：1 2 3 4 5 2，LRU算法性能更好。

9.8问：讨论在哪一种情况下，MFU（最不经常使用）页置换比LRU（最近最少使用）页置换法产生较少的页面错误，什么情况下则相反？

答：考虑可容纳4页的内存：1 2 3 4 4 4 5 1，MFU算法会用5替换4，而LRU算法刚用5替换1，实践中不可能发生，对于串：1 2 3 4 4 4 5 1，LRU算法做得更正确。

9.9问：在VAX/VMS系统对驻留页采用先进先出算法，在空闲帧给最近最少使用页面，假设在空闲帧使用LRU算法，回答下列问题

A.如果页表出错和页面不存在空闲帧如何产生新空间给亲要求页面

B.如果页面出错和页面存在空闲帧，如何驻留页面，空闲帧怎么样分配给新要求页表。

C.如果驻留页面只有一个，系统如何决定

D.如果没有空闲帧，系统如果决定

答：A.在这种情况下，空闲帧中的一个页面被替换到磁盘上，为驻留页面创建一个空间，再

转移到空闲帧里，浏览页面时，又被称动到驻留页面上。

B.引进一套驻留页面，并将页面搬进空闲帧

C.系统在空闲帧里使用页置换法通常是LRU算法

D.系统进行FIFO算法

9.10问：假设一个具有下面时间度量利用率的请求调页系统：

CPU利用率20％，分页磁盘 97.7％，其他I/O设备，5％

说明下面哪一个（可）能提高CPU的利用率，为什么？

A安装一个更快的CPU

B安装一个更大的分页磁盘

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

C提高多道程序设计程序

D降低多道程序设计程度

E安装更多内存

F安装一个更快的硬盘，或对多个硬盘使用多个控制器

G对页面调度算法添加预取页

H增加页面大小。

答：该系统显然花费了许多时间进行分页，显示过度分配的内存，如果多级程序水平减少驻

地进程，将页面错误变少和提高CPU利用率。另一种方式来提高利用率是获得更多的物理内存或更快的分页鼓。

ABC都不行，D可以

E.可能提高CPU利用率为更多页面保持驻地，而不需要分页或磁盘。

F.另一个改进，因为磁盘的瓶颈是删除更快的响应，和更多的磁盘容量，CPU将会获得更多的数据传输速度

G.CPU将获得更快的数据传输率，所以更多地被使用。如果分页服从预调（即一些访问顺序）这只是一个方面。

H.增加页面大小将导致减少页面错误，如果数据进行是随机的，则分页可以随之，因为较少页面可保存在内存上，更多的数据转移到页面错误 上，这种 变化可以减少CPU利用率或者增加CPU利用率。

9.11 假设一台机器使用一级间接引用方法提供可以访问内存位置的指令。当一个程序的所有页未驻留，程序的第一条指令是一个间接内存load操作时，将会出现什么页错误？当操作系统正在使用一个单进程帧分配技术，只有两个页被分配至此进程时，将会发生什么？

Answer:

出现以下页错误：访问指令的页错误，访问包含一个指向目标内存位置指针的内存位置的页的错误，访问目标内存位置的页错误。第三页置换包含指令的页，操作系统将产生三个页错误。如果需要再次取出指令，重复被陷指令，那么，页错误将无限期地继续下去。如果指令在寄存器中缓存，那么将能在第三页错误后完全执行。

9.12 假设你的置换策略（在分页系统中）是有规律地检查每个页并将最近一次检测后没有再被引用的页丢弃。与LRU或二次机会置换算法相比，使用这种策略有哪些好处和坏处？

Answer:

这种算法可以靠引用位的使用来实现。每次检查过后，置位为0；如果页被引用，置位为1。然后，该算法将从自上次检查后未使用过的页中选择任意页来置换。

这种算法的优点是算法比较简单——只需保持一个引用位。这种算法的缺点是，只能使用很短的时间帧来决定是否置换一页，从而忽略了局部性。例如，一个页可能是一个进程工作集合的一部分，但因为自上次检查后未被引用而被置换。（即不是所有工作集合中的页可以在检查之间被引用）

9.13 一个页面置换算法应使发生页错误的次数最小化。怎样才能通过将使用频率高的页平均分配到整个内存而不只是竞争少数几个页帧页来达到这种最小化。可以对每个页帧设置一个计数器来记录与此帧相关的页数。那么当置换一个页

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

时，就可以查找计数器值最小的页帧

Answer:

a.定义一个页面置换算法解决问题：

Ⅰ.计数器初始值——0；

Ⅱ.计数器值增加——每当新的一页与此帧相关联；

Ⅲ.计数器值减少——每当与此帧相关联的一个页不再需要；

Ⅳ.怎样选择要被置换的页——找到带有最小计数器值的帧。使用先进

先出算法解除其关系

b.14个页错误

c.11个页错误

9.14 假设一个请求调页系统具有一个平均访问和传输时间为20ms的分页磁盘。地址转换是通过在主存中的页表来进行的，每次内存访问时间为1µs。这样，每个通过页表进行的内存引用都要访问内存两次。为了提高性能，加入一个相关内存，当页表项在相关内存中时，可以减少内存引用的访问次数。

假设80%的访问发生在相关内存中，而且剩下中的10%（总量的2%）会导致页错误。内存的有效访问时间是多少？

Answer:

有效访问时间= (0.8) × (1 µsec)+ (0.1) × (2 µsec) + (0.1) × (5002 µsec)

= 501.2 µsec

= 0.5 millisec

9.15 颠簸的原因是什么？系统怎样检测颠簸？一旦系统检测到颠簸，系统怎样做来消除这个问题？

Answer:

分配的页数少于进程所需的最小页数时发生颠簸，并迫使它不断地页错误。该系统可通过对比多道程序的程度来估计CPU利用率的程度，以此来检测颠簸。降低多道程序的程度可以消除颠簸。

9.16 一个进程可能有两个工作集合吗，一个代表数据，另一个代表代码？请解释。

Answer:

是的，事实上，许多处理器因为这个原因提供两个TLB。举个例子，一个进程访问的代码可长时间地保留同样的工作集合。然而，代码访问的数据可能改变，这样为工作集合的数据访问映射了一个改变。

9.17 假设使用参数Δ定义工作集合模型下的工作集合窗口。设置Δ为一个较小值，其表示页错误频率和系统中当前正在执行的活动页（非暂停的）进程数量，则影响如何？当设置Δ为一个非常大的值呢？

Answer:

当设置Δ为一个较小的值，那么有可能低估一个进程的驻留页集合，允许安排一个进程，即使其所需的所有页未驻留。这可能导致大量的页错误。当设置Δ为较大的值，那么将高估一个进程的驻留集合，这可能阻止许多进程被安排，尽管他们需要的页驻留。然而，一旦一个进程被安排，高估驻留集合后就不可能

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

产生页错误

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/0h5i.html