《操作系统精髓与设计原理·第五版》习题答案

第1章 计算机系统概述

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

令所产生的不同信号来定义的。

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传送，请估计传送速度。

2

答案：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?1Ts的引用更复杂，我们从概率论入手：所期望的值x??iPr[x?1]，由此我们可以写出：T??THsii?1i?1nni

我们需要清楚如果一个字在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

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

ii1i?2j?11.12、考虑一个存储器系统，它具有以下参数：

3

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章 操作系统概述

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

受I/O限制的程序使用相对较少的处理器时间，因此更受算法的青睐。然而，受处理器限制的进程如

4

果在足够长的时间内得不到处理器时间，同一算法将允许处理器去处理此进程，因为它最近没有使用过处理器。这样，一个处理器限制的进程不会永远得不到处理器。

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. 在[PINK89] 中为进程定义了以下状态：执行（运行）态、活跃（就绪）态、阻塞态和挂起态。当进

程正在等待允许使用某一资源时，它处于阻塞态；当进程正在等待它已经获得的某种资源上的操作完成时，它处于挂起态。在许多操作系统中，这两种状态常常放在一起作为阻塞态，挂起态使用本章中给出的定义。请比较这两组定义的优点。

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

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

5

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）某些小孩在制作玩具时遇到了困难。为了让圣诞老人多睡会，这些孩子只有在是那个人都遇到困难时才唤醒他。当三个孩子的问题得到解决时，其他想访问圣诞老人的孩子必须等到那些孩子返回。如果圣诞老人醒来后发现在三个孩子在他的店门口等

16

待，并且最后一头驯鹿已经从热带回来。则圣诞老人决定让孩子门等到圣诞节之后，因为准备最后一天哦iuxunlu必须与其他unlu在暖棚中等待并且还没有套上缰绳做成雪橇前回来。请用信号量解决这个问题。 答：santa:圣诞老人reindeer:驯鹿elf:小孩子sleigh:雪橇toys:玩具

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

a.用信号量实现消息传递。提示：利用一个共享缓冲区保存信箱，每个信箱由一个消息槽数组成的。 b.用消息传递实现信号量。提示：引入一个独立的同步进程。

答：b.这个方法来自于[TANE97].同步进程维护了一个计数器和一个等待进程的清单。进程调用相关用于向同步进程发送消息的生产者，wait或signal，来实现WAITHUO SIGNAL.然后生产者执行RECEIVE来接受来自于同步进程的回复。

当消息到达时，同步进程检查计数器看需要的操作是否已经足够，SIGNALs总是可以完成，但是假如信号值为0时，WAITs将会被阻塞。假如操作被允许，同步进程就发回一个空消息，因此解除调用者的阻塞。假如操作是WAIT并且信号量的值为0时，同步进程进入调用队列，并且不发送回复。结果是执行WAIT

17

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

第6章 并发性：死锁和饥饿

６.１写出图６.１（a）中死锁的四个条件。

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

６.２按照６.１节中对图６.２中路径的描述，给出对图６.３中６种路径的简单描述。

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

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

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

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

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

证明：如果

r1 r2 r3 r4 r1 r2 r3 r4 r1 r2 r3 r4 Q 获得 B

0 0 1 2 0 0 1 2 和Ａ（在 P

2 0 0 0 2 7 5 0 之前请求Ａ）, 那么 Q 能使用这些两类

资源然后释放他们, 允许Ａ进行。如果 P在 Q之前请求Ａ获得Ａ, 然后Q 最多能执行到请求Ａ然后被阻塞。然而,一旦 P 释放 A ， Q 能进行。一旦 Q 释放 B, Ａ能进行。

６.４考虑下面的一个系统，当前不存在未满足的请求。 2 1 0 0

可用

r1 r2 r3 r4

当前分配 最大需求 仍然需求

18

0 2 0 0 3 3 3 5 3 4 4 2 6 4 0 6 3 6 5 5 5 6 6 2

a计算每个进程仍然可能需要

的资源，并填入标为“仍然需要”的列中。

b系统当前是处于安全状态还是不安全状态，为什么。 c系统当前是否死锁？为什么？

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

e如果Ｐ３的请求（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将死锁，所以不安全，完全不

可以立即同意系统剩下的全部请求。

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

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 没有死锁

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

以下是关于进程的知识： １. 只要环境提供数据，进程Ｉ最终把它输入到磁盘上（只要磁盘空间可用）。 ２. 只要磁盘可以得到输入，进程Ｐ最终消耗掉它，并在磁盘上为每个输入块输出有限量的数据（只要磁

盘空间可用）。 ３. 只要磁盘可以得到输出，进程Ｏ最终消耗掉它。说明这个系统可能死锁。

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

６.７给出在习题６.６中预防死锁的附加资源约束，仍然通话输入和输出缓冲区之间的边界可以根据进程的要求变化。

解：为输出缓冲区保留一个最小数目(称为reso)块, 但是当磁盘空间足够大时允许输出块的数目超过这一个界限。资源限制现在变成 Ｉ+ Ｏ?≤max Ｉ≤?max – reso 当0

如果磁盘充满I/O，Ｉ能被延迟; 但是迟早, 所有的早先的 输入可以被Ｐ处理完，而且对应的输出将会被 O 处理, 因而可以让Ｉ继续执行。

６.８在ＴＨＥ多道程序设计系统中，一个磁鼓（磁盘的先驱，用做辅存）被划分为输入缓冲区，处理和输出缓冲区，它们的边界可以移动，这取决于所涉及的进程速度。磁鼓的当前状态可以用以下参数描述： ?max表示磁鼓中的最大页数，i示磁鼓中的输入页数，p示磁鼓中的处理页数，o示磁鼓中的输出页数，reso出保留的最小页数，resp理保留的最小页数。 解：

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

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

２.输入缓冲区→处理区域（输入消耗） ３.处理区域→输出缓冲区（输出生产） ４.输出缓冲区→空（输出生产） ５.空→处理区域（输出消耗） ６.处理区域→空（过程调用）

a根据Ｉ，Ｏ和Ｐ的量定义这些转换的结果。

b如果维持习题６.６中关于输入进程，用户进程和输出进程的假设，它们中的任何一个转换是否会导致死锁。

20

作的指令表？

解：原子操作是在原子数据类型上操作, 原子数据类型有他们自己的内在的 格式。因此，不能用简单的阅读操作, 但是特别的阅读操作 对于原子数据类型来说是不可或缺的。 ６.２０考虑Linux系统中的如下代码片断： read_lock(&mr_rwlock); write_lock(&mr_rwlock);

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

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

６.２１两个变量a和b分别有初始值１和２，对于Linux系统有如下代码：

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

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

解：没有使用内存屏障, 在一些处理器上可能 c接到b 的新值, 而d接到b 的旧值。举例来说, c可以等于 4(我们期待的), 然而 d 可能等于 1.(不是我们期待的)。使用mb() 确保a 和 b 按合适的次序被写, 使用 rmb()确保 c 和d 按合适的次序被读。

第7章 内存管理

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. 动态分区的另一种放置算法是最坏适配，在这种情况下，当调入一个进程时，使用最大的空闲存储

26

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

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

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.

27

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。关于指令地址有两种选择：

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

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

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

保存到指令寄存器中。

28

哪种方法更好？

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

321016

7.12. 考虑一个简单分页系统，其物理存储器大小为2字节，页大小为2字节，逻辑地址空间为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。

29

答：

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章 虚拟内存

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位哈希表。表项包含页号帧号和链指针。如果页表可以给每个哈

30

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