《操作系统精髓与设计原理·第五版》练习题及其答案(文本资料).doc

《《操作系统精髓与设计原理·第五版》练习题及其答案(文本资料).doc》由会员分享，可在线阅读，更多相关《《操作系统精髓与设计原理·第五版》练习题及其答案(文本资料).doc（119页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第 1 1 章章 计算机系统概述计算机系统概述1.1、图 1.3 中的理想机器还有两条 I/O 指令：0011 = 从 I/O 中载入 AC0111 = 把 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：3005IR；步骤 2：3AC步骤 3：5940I

2、R；步骤 4：325AC步骤 5：7006IR：步骤 6：AC设备 61.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. P

3、C 中的值（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

4、. 指令寄存器 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 端口号，这个微处理器可以支持多少

5、 8 位 I/O 端口？答案：对于(a)和(b)两种情况，微处理器可以直接访问的最大存储器地址空间为216 = 64K bytes；唯一的区别是8位存储器每次访问传输1个字节，而16位存储器每次访问可以传输一个字节或者一个16位的字。对于(c)情况，特殊的输入和输出指令是必要的，这些指令的执行体会产生特殊的“I/O信号”（有别于“存储器信号”，这些信号由存储器类型指令的执行体产生）；在最小状态下，一个附加的输出针脚将用来传输新的信号。对于(d)情况，它支持28 = 256个输入和28 = 256个输出字节端口和相同数目的16位I/O端口；在任一情况, 一个输入和一个输出端口之间的区别是通过被执

6、行的输入输出指令所产生的不同信号来定义的。1.5、考虑一个 32 位微处理器，它有一个 16 位外部数据总线，并由一个 8MHz的输入时钟驱动。假设这个微处理器有一个总线周期，其最大持续时间等于 4个输入时钟周期。请问该微处理器可以支持的最大数据传送速度为多少？外部数据总线增加到 21 位，或者外部时钟频率加倍，哪种措施可以更好地提高处理器性能？请叙述你的设想并解释原因。答案：时钟周期1/（8MHZ）125ns总线周期4125ns500ns每 500ns 传输 2 比特；因此传输速度4MB/s加倍频率可能意味着采用了新的芯片制造技术（假设每个指令都有相同的时钟周期数） ；加倍外部数据总线，在芯

7、片数据总线驱动/锁存、总线控制逻辑的修改等方面手段广泛（或许更新） 。在第一种方案中，内存芯片的速度要提高一倍（大约） ，而不能降低微处理器的速度；第二种方案中，内存的字长必须加倍，以便能发送/接受 32 位数量。1.6、考虑一个计算机系统，它包含一个 I/O 模块，用以控制一台简单的键盘/打印机电传打字设备。CPU 中包含下列寄存器，这些寄存器直接连接到系统总线上：INPR：输入寄存器，8 位OUTR：输出寄存器，8 位FGI：输入标记，1 位FGO：输出标记，1 位IEN：中断允许，1 位I/O 模块控制从打字机中输入击键，并输出到打印机中去。打字机可以把一个字母数字符号编码成一个 8 位

8、字，也可以把一个 8 位字解码成一个字母数字符号。当 8 位字从打字机进入输入寄存器时，输入标记被置位；当打印一个字时，输出标记被置位。a. 描述 CPU 如何使用这 4 个寄存器实现与打字机间的输入/输出。b. 描述通过使用 IEN，如何提高执行效率？答案：a.来源于打字机的输入储存在 INPR 中。只有当 FGI0 时，INPR 才会接收来自打字机的数据。当数据接收后，被储存在 INPR 里面，同时 FGI置为 1。CPU 定期检查 FGI。如果 FGI1，CPU 将把 INPR 里面的内容传送至 AC，并把 FGI 置为 0。当 CPU 需要传送数据到打字机时，它会检查 FGO。如果FG

9、O0，CPU 处于等待。如果 FGO1，CPU 将把 AC 的内容传送至 OUTER并把 FGO 置为 0。当数字符号打印后，打字机将把 FGI 置为 1。b.（A）描述的过程非常浪费。速度远高于打字机的 CPU 必须反复不断的检查 FGI 和 FGO。如果中断被使用，当打字机准备接收或者发送数据时，可以向 CPU 发出一个中断请求。IEN 计数器可以由 CPU 设置（在程序员的控制下） 。1.7、实际上在所有包括 DMA 模块的系统中，DMA 访问主存储器的优先级总是高于处理器访问主存储器的优先级。这是为什么?答案：如果一个处理器在尝试着读或者写存储器时被挂起, 通常除了一点轻微的时间损耗之

10、外没有任何危害。但是，DMA可能从或者向设备(例如磁盘或磁带)以数据流的方式接收或者传输数据并且这是不能被打断的。否则，如果DMA设备被挂起（拒绝继续访问主存），数据可能会丢失。1.9、一台计算机包括一个 CPU 和一台 I/O 设备 D，通过一条共享总线连接到主存储器 M，数据总线的宽度为 1 个字。CPU 每秒最多可执行 106条指令，平均每条指令需要 5 个机器周期，其中 3 个周期需要使用存储器总线。存储器读/写操作使用 1 个机器周期。假设 CPU 正在连续不断地执行后台程序，并且需要保证 95%的指令执行速度，但没有任何 I/O 指令。假设 1 个处理器周期等于 1 个总线周期，现

11、在要在 M 和 D 之间传送大块数据。a.若使用程序控制 I/O，I/O 每传送 1 个字需要 CPU 执行两条指令。请估计通过 D 的 I/O 数据传送的最大可能速度。b.如果使用 DMA 传送，请估计传送速度。答案：a.处理器只能分配 5的时间给 I/O.所以最大的 I/O 指令传送速度是10e60.0550000 条指令/秒。因此 I/O 的传送速率是 25000 字/秒。b.使用 DMA 控制时，可用的机器周期下的数量是10e6（0.0550.952）2.1510e6如果我们假设 DMA 模块可以使用所有这些周期，并且忽略任何设置和状态检查时间，那么这个值就是最大的 I/O 传输速率。

12、1.10、考虑以下代码：for ( i = 0；i j := i + 1 mod n;while (j i) and (not waitingj) do j := j + 1 mod n;if j = i then lock := falseelse waiting := false;Until这个算法用最普通的数据结构：var waiting: array 0.n 1 of booleanLock：boolean这些数据结构被初始化成假的，当一个进程离开它的临界区，它就搜索waiting 的循环队列5.8 考虑下面关于信号量的定义：Void semWait(s)If (s.count0)s.

13、count-;ElsePlace 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 中的定义，注意有这样的一个区别：在前面的定义中，信号量永远不会取负值。当在程序中分别使用这两种定义时，其效果有什么不同？也就是说，是否可以在不改变程序意义的前提下，用一个定义代替另

14、一个？答：这两个定义是等价的，在图 5.3 的定义中，当信号量的值为负值时，它的值代表了有多少个进程在等待；在此题中的定义中，虽然你没有关于这方面的信息，但是这两个版本的函数是一样的。5.9 可以用二元信号量实现一般信号量。我们使用 semWaitB 操作和semSignalB 操作以及两个二元信号量 delay 和 mutex。考虑下面的代码Void semWait(semaphor s)semWaitB(mutex);s-;if (s;if nm = 0 then semSignal(a)else semSignal(m)endif;5.11 下面的问题曾被用于一个测试中：侏罗纪公园有一个

15、恐龙博物馆和一个公园，有 m 个旅客和 n 辆车，每辆车只能容纳一名旅客。旅客在博物馆逛了一会儿，然后派对乘坐旅客车。当一辆车可用时，它载入一名旅客，然后绕公园行驶任意长的时间。如果 n 辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步 m 个旅客进程和 n 个进程。下面的代码框架是在教室的地板上发现的。忽略语法错误和丢掉的变量声明，请判定它是否正确。注意，p 和 v 分别对应于 semwait 和 semsignal。Resource Jurassic_Park()Sem car_avail:=0,car_taken:=0,c

16、ar_fillde:=0.passenger_released:=0Process 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 passengerProcess car(j:=1 to num_cars)Do true-V(car_avail);P(car_taken);V(car_filled)Nap(int(random(1000*ride_time)V(p

17、assenger_released)OdEnd carEnd Jurassic_Park答：这段代码有一个重要问题.在 process car 中的代码 V(passenger_released)能够解除下面一种旅客的阻塞,被阻塞在P(passenger_released)的这种旅客不是坐在执行 V()的车里的旅客.5.12 在图 5.9 和 5.3 的注释中，有一句话是“仅把消费者临界区（由 s 控制）中的控制语句移出还是不能解决问题，因为这将导致死锁”，请用类似于表 5.3 的表说明。答：ProducerConsumersndelay11002SemWaitB(S)0003n+0104If

18、(n=1)(semSignalB(delay)0115semSignalB(s)1116semWaitB(delay)1107semWaitB(s)0108n-009semWaitB(s)If(n=0) (semWaitB(delay)10生产者和消费者都被阻塞。5.13 考虑图 5.10 中定义的无限缓冲区生产者/消费者问题的解决方案。假设生产者和消费者都以大致相同的速度运行，运行情况如下：生产者：append;semSignal;produce;append;semSignal 消费者：consume;take;semWait;consume;take;semWait;生产者通常管理给换成

19、区一个元素，并在消费者消费了前面的元素后发信号。生产者通常添加到一个空缓冲去中，而消费者通常取走缓冲区中的唯一元素。尽管消费者从不在信号量上阻塞，但必须进行大量的信号量调用，从而产生相当多的开销。构造一个新程序使得能在这种情况下更加有效。提示：允许 n 的值为-1，这表示不仅缓冲区为空，而且消费者也检测到这个事实并将被阻塞，直到生产者产生新数据。这个方案不需要使用图 5.10 中的局部变量 m。答：这个程序来自于BEN82program producerconsumer;var n: integer;s: (*binary*) semaphore (:= 1);delay: (*binary*

20、) semaphore (:= 0);procedure producer;beginrepeatproduce;semWaitB(s);append;n := n + 1;if n=0 then semSignalB(delay);semSignalB(s)foreverend;procedure consumer;beginrepeatsemWaitB(s);take;n := n 1;if n = -1 thenbeginsemSignalB(s);semWaitB(delay);semWaitB(s)end;consume;semSignalB(s)foreverend;begin (

21、*main program*)n := 0;parbeginproducer; consumerparendend.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 个

22、入口？a.这是为什么？b.请修改程序，以不久这种低调？答：如果缓冲区可以容纳 n 个入口，问题在于如何从一个满的缓冲区中区分出一个空的缓冲区，考虑一个有六个位置的缓冲区，且仅有一个入口，如下：AOut in然后，当一个元素被移出，out=in。现在假设缓冲区仅有一个位置为空：DEABCIn out这样，out=in+1.但是，当一个元素被添加，in 被加 1 后，out=in，当缓冲区为空时同理。b你可以使用一个可以随意增加和减少的辅助的变量，count。5.16 这个习题说明了使用信号量协调三类进程。圣诞老人在他北极的商店中睡眠，他只能被一下两种情况之一唤醒：（1）所有九头驯鹿都从南太平洋的

23、假期回来了，或者（2）某些小孩在制作玩具时遇到了困难。为了让圣诞老人多睡会，这些孩子只有在是那个人都遇到困难时才唤醒他。当三个孩子的问题得到解决时，其他想访问圣诞老人的孩子必须等到那些孩子返回。如果圣诞老人醒来后发现在三个孩子在他的店门口等待，并且最后一头驯鹿已经从热带回来。则圣诞老人决定让孩子门等到圣诞节之后，因为准备最后一天哦 iuxunlu 必须与其他 unlu 在暖棚中等待并且还没有套上缰绳做成雪橇前回来。请用信号量解决这个问题。答：santa:圣诞老人 reindeer:驯鹿 elf:小孩子 sleigh:雪橇 toys:玩具5.17 通过一下步骤说明消息传递和信号量具有同等的功能：

24、a.用信号量实现消息传递。提示：利用一个共享缓冲区保存信箱，每个信箱由一个消息槽数组成的。b.用消息传递实现信号量。提示：引入一个独立的同步进程。答：b.这个方法来自于TANE97.同步进程维护了一个计数器和一个等待进程的清单。进程调用相关用于向同步进程发送消息的生产者，wait 或 signal，来实现 WAITHUO SIGNAL.然后生产者执行 RECEIVE 来接受来自于同步进程的回复。当消息到达时，同步进程检查计数器看需要的操作是否已经足够，SIGNALs 总是可以完成，但是假如信号值为 0 时，WAITs 将会被阻塞。假如操作被允许，同步进程就发回一个空消息，因此解除调用者的阻塞。

25、假如操作是 WAIT 并且信号量的值为 0 时，同步进程进入调用队列，并且不发送回复。结果是执行WAIT 的进程被阻塞。当 SIGNAL 被执行，同步进程选择一个进程在信号量上阻塞，要不就以先进先出顺序，要不以其他顺序，并且发送一个回复。跑步条件被允许因为同步进程一次只需要一个。第第 6 6 章章 并发性：死锁和饥饿并发性：死锁和饥饿.写出图.（a）中死锁的四个条件。解：互斥：同一时刻只有一辆车可以占有一个十字路口象限。占有且等待：没有车可以倒退；在十字路口的每辆车都要等待直到它前面的象限是空的。非抢占: 没有汽车被允许挤开其他车辆。 循环等待: 每辆汽车都在等待一个此时已经被其他车占领的十字

26、路口象限。.按照.节中对图.中路径的描述，给出对图.中种路径的简单描述。解：.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 执行而且阻塞在对

27、的请求上。释放。当 Q 重新开始执行的时候，, 它将会能够获得两个资源。6. P 获得而且释放然后获得并且释放 B. 当 Q 重新开始实行, 它将会能够获得两个资源。.图.反映的情况不会发生死锁，请证明。证明：如果 Q 获得 B 和（在 P之前请求）, 那么 Q 能使用这些两类资源然后释放他们, 允许进行。 如果 P在 Q之前请求获得, 然后Q 最多能执行到请求然后被阻塞。 然而,一旦 P 释放 A ， Q 能进行。 一旦 Q 释放 B, 能进行。.考虑下面的一个系统，当前不存在未满足的请求。可用 r1 r2 r3 r42100当前分配 最大需求 仍然需求a计算每个进程仍然可能需要的资源，并填

28、入标为“仍然需要”的列中。b系统当前是处于安全状态还是不安全状态，为什么。c系统当前是否死锁？为什么？d哪个进程（如果存在）是死锁的或可能变成死锁的？e如果的请求（0，1，0，0）到达，是否可以立即安全地同意该请求？在什么状态（死锁，安全，不安全）下可以立即同意系统剩下的全部请求？如果立即同意全部请求，哪个进程（如果有）是死锁的或可能变成死锁的？解： a. . 0 0 0 007 5 066 2 220 0 20 3 2 0b.系统当前处于安全状态，因为至少有一个进程执行序列，不会导致死锁，运行顺序是p1, p4, p5, p2, p3.c.系统当前并没有死锁，因为 P1 进程当前分配与最大需

29、求正好相等，P1r1 r2 r3 r4r1 r2 r3 r4 r1 r2 r3 r40 0 1 2 001 22 0 0 0 2 7 5 00 0 3 46 6 5 62 3 54 4 3 5 60 3 3 2 0 6 5 2 进程可以运行直至结束，接下来运行其他进程d.P2,P3,P4,P5 可能死锁e.不可以，当进程 P1,P4,P5 执行完可用资源为（4，6，9，8） ，P2,P3 将死锁，所以不安全，完全不可以立即同意系统剩下的全部请求。. 请把.中的死锁检测算法应用于下面的数据，并给出结果。Available=(2Available=(2 1 1 0 0 0)0)2 0 0 1 0

30、0 1 0Request= 1 0 1 0 Allocation= 2 0 0 12 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 没有死锁.一个假脱机系统包含一个输入进程，用户进程进程和一个输出进程，它们之间用两个缓冲区连接。进程以相等大小的块为单位交换数据，这些块利用输入缓冲区和输出缓冲区之间的移动边界缓存在磁盘上

31、，并取决于进程的速度。所使用的通信原语确保满足下面的资源约束：i+omax其中，max表示磁盘中的最大块数，i表示磁盘中的输入块数目， o表示磁盘中的输出块数目。以下是关于进程的知识：.只要环境提供数据，进程最终把它输入到磁盘上（只要磁盘空间可用）。.只要磁盘可以得到输入，进程最终消耗掉它，并在磁盘上为每个输入块输出有限量的数据（只要磁盘空间可用）。.只要磁盘可以得到输出，进程最终消耗掉它。说明这个系统可能死锁。解：当I的速度远大于P的速度，有可能使磁盘上都是输入数据而此时P进程要处理输入数据，即要将处理数据放入输出数据区。于是P进程等待磁盘空间输出，I进程等待磁盘空间输入，二者死锁。.给出在

32、习题.中预防死锁的附加资源约束，仍然通话输入和输出缓冲I输入 缓冲区P输出 缓冲区o区之间的边界可以根据进程的要求变化。解：为输出缓冲区保留一个最小数目(称为reso)块, 但是当磁盘空间足够大时允许输出块的数目超过这一个界限。 资源限制现在变成 + maxmax reso当0 0;regionregion buffer(j) dodo consume element;regionregion available dodobeginbeginavailable (i) := available(i) 1;available (succ) := available (succ) + 1;ende

33、ndj := (j+1) modmod max;foreverforeverendendb.死锁可以被解决通过P0 waits for Pn-1 ANDP1 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); get_forks(k); /*client requests two forks v

34、ia monitor*/ ; release_forks(k); /*client releases forks via the monitor*/ .在表.中，Linux的一些原子操作不会涉及到对同一变量的两次访问。比如atomic_read(atomic_tatomic_read(atomic_t *v)*v).简单的读操作在任何体系结构中都是原子的。为什么该操作增加到了原子操作的指令表？解：原子操作是在原子数据类型上操作, 原子数据类型有他们自己的内在的格式。 因此，不能用简单的阅读操作, 但是特别的阅读操作对于原子数据类型来说是不可或缺的。.考虑Linux系统中的如下代码片断：read

35、_lock(write_lock(mr_rwlockmr_rwlock是读者写者锁。这段代码的作用是什么？解：因为写者锁将会自旋，所以这段代码会导致死锁, 等待所有的读者解锁, 包括唤醒这个线程。.两个变量a和b分别有初始值和，对于Linux系统有如下代码：线程 1 线程 2a = 3；-mb( )；-c = b；rmb()；d = a；使用内在屏障是为了避免什么错误？解：没有使用内存屏障, 在一些处理器上可能 c接到b 的新值, 而d接到b 的旧值。 举例来说, c可以等于 4(我们期待的), 然而 d 可能等于 1.(不是我们期待的)。 使用mb() 确保a 和 b 按合适的次序被写, 使

36、用 rmb()确保 c 和d 按合适的次序被读。第第 7 7 章章 内存管理内存管理7.1.7.1.2.3 节中列出了内存管理的 5 个目标，7.1 节中列出了 5 中需求。请说明它们是一致的。答: 重定位支持模块化程序设计; 保护保护和访问控制以及进程隔离;共享保护和访问控制; 逻辑组织支持模块化程序设计; 物理组织长期存储及自动分配和管理.7.2.7.2.考虑使用大小相等分区的固定分区方案。分区大小为 2e16 字节，贮存的大小为 2e24 字节。使用一个进程表来包含每一个进程对应的分区。这个指针需要多少位？答:分区的数量等于主存的字节数除以每个分区的字节数：224/216 = 28. 需

37、要 8 个比特来确定一个分区大小为 28 中的某一个位置。7.3.7.3.考虑动态分区方案，说明平均内存中空洞的数量是段数量的一半。答: 设 n 和 h 为断数量和空洞数量的个数.在主存中,每划分一个断产生一个空洞的概率是 0.5,因为删除一个断和添加一个断的概率是一样的.假设s 是内存中断的个数那么空洞的平均个数一定等于 s/2.而导致空洞的个数一定小余断的数量的直接原因是相邻的两个断在删除是一定会产生一个空洞.7.4.7.4.在实现动态分区中的各种放置算法（见 7.2 节） ，内存中必须保留一个空闲块列表。分别讨论最佳适配、首次适配、临近适配三种方法的平均查找长度。答:通过上题我们知道，假

38、设 s 是驻留段的个数，那么空洞的平均个数是s/2。从平均意义上讲，平均查找长度是 s/4。7.5.7.5.动态分区的另一种放置算法是最坏适配，在这种情况下，当调入一个进程时，使用最大的空闲存储块。该方法与最佳适配、首次适配、邻近适配相比，优点和缺点各是什么？它的平均查找长度是多少？答：一种对最佳适配算法的评价即是为固定分配一个组块后和剩余空间是如此小以至于实际上已经没有什么用处。最坏适配算法最大化了在一次分配之后，剩余空间的大小仍足够满足另一需求的机率，同时最小化了压缩的概率。这种方法的缺点是最大存储块最早被分配，因此大空间的要求可能无法满足。7.6.7.6.如果使用动态分区方案，下图所示为

39、在某个给定的时间点的内存配置：阴影部分为已经被分配的块；空白部分为空闲块。接下来的三个内存需求分别为 40MB，20MB 和 10MB。分别使用如下几种放置算法，指出给这三个需求分配的块的起始地址。a.a. 首次适配b.b. 最佳适配c.c. 临近适配（假设最近添加的块位于内存的开始）d.d. 最坏适配答：a.a.40M 的块放入第 2 个洞中,起始地址是 80M. 20M 的块放入第一个洞中.起始地址是 20M. 10M 的块的起始地址是 120M。b.b.40M,20N,10M 的起始地址分别为 230M,20M 和 160M.c.c. 40M,20M,10M 的起始地址是 80M,120

40、160M.d.d. 40M,20M,10M,的起始地址是 80M,230M,360M.7.7.7.7.使用伙伴系统分配一个 1MB 的存储块。a.a. 利用类似于图 7.6 的图来说明按下列顺序请求和返回的结果：请求70；请求 35；请求 80；返回 A；请求 60；返回 B；返回 D；返回 C。b.b. 给出返回 B 之后的二叉树表示。答：a.a.b.b.7.8.7.8. 考虑一个伙伴系统，在当前分配下的一个特定块地址为011011110000.a.a.如果块大小为4，它的伙伴的二进制地址为多少？b.b.如果块大小为16，它的伙伴的二进制地址为多少？答：a.a.011011110100b.b

41、.0110111000007.9.7.9.令 buddyk(x)为大小为 2k、地址为 x 的块的伙伴的地址，写出 buddyk(x)的通用表达式。 答：7.10.7.10.Fabonacci 序列定义如下：F0=0,F1=1,Fn+2=Fn+1+Fn,n0a.a. 这个序列可以用于建立伙伴系统吗？b.b. 该伙伴系统与本章介绍的二叉伙伴系统相比，有什么优点？答：a.a.是。字区大小可以确定 Fn = Fn-1 + Fn-2.。b.b.这种策略能够比二叉伙伴系统提供更多不同大小的块，因而具有减少内部碎片的可能性。但由于创建了许多没用的小块，会造成更多的外部碎片。7.11.7.11.在程序执行期

42、间，每次取指令后处理器把指令寄存器的内容（程序计数器）增加一个字，但如果遇到会导致在程序中其他地址继续执行的转跳或调用指令，处理器将修改这个寄存器的内容。现在考虑图 7.8。关于指令地址有两种选择： 在指令寄存器中保存相对地址，并把指令寄存器作为输入进行动态地址转换。当遇到一次成功的转跳或调用时，由这个转跳或调用产生的相对地址被装入到指令寄存器中。 在指令寄存器中保存绝对地址。当遇到一次成功的转跳或调用时，采用动态地址转换，其结果保存到指令寄存器中。哪种方法更好？答：使用绝对地址可以减少动态地址转换的次数。但是，我们希望程序能够被重定位。因此，在指令寄存器中保存相对地址似乎就更好一些。也可以选

43、择在进程被换出主存时将指令寄存器中的地址转换为相对地址。7.12.7.12.考虑一个简单分页系统，其物理存储器大小为 232字节，页大小为 210字节，逻辑地址空间为 216个页。a.a. 逻辑地址空间包含多少位？b.b. 一个帧中包含多少字节？c.c. 在物理地址中指定帧需要多少位？d.d. 在页表中包含多少个页表项？e.e. 在每个页表项中包含多少位？（假设每个页表项中包含一个有效/无效位）答：a.a. 物理地址空间的比特数是 216*210=226b.b. 一个帧包含的字节跟一个页是一样的,210比特.c.c. 主存中帧的数量是 232/210=222,所以每个帧的定位要 22 个比特d

44、.d. 在物理地址空间,每个页都有一个页表项,所以有 216项e.e. 加上有效/无效位，每个页表项包含 23 位。7.13.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.7.14.在一个简单分段系统中，包含如下段表：起始地址长度（字节）6602481752442222198996604对如下的每一个逻辑地址，确定其对应的物理地址或者说明段错误

45、是否会发生：a.a. 0，198b.b. 2，256c.c. 1，530d.d. 3，444e.e. 0，222答：a.a. 段 0 定位在 660,所以我们有物理地址 660+190=858.b.b. 222+156=378c.c. 段 1 长度为 422,所以会发生错误d.d. 996+444=1440e.e. 660+222=882.7.15.7.15.在内存中，存在连续的段 S1,S2,，Sn按其创建顺序一次从一端放置到另一端，如下图所示：当段 Sn+1被创建时，尽管 S1,S2,，Sn中的某些段可能已经被删除，段Sn+1仍被立即放置在段 Sn之后。当段（正在使用或已被删除）和洞之间的

46、边界到达内存的另一端时，压缩正在使用的段。a.a. 说明花费在压缩上的时间 F 遵循以下的不等式：F(1-f)/1+kf),k=t/2s-1其中，s 表示段的平均长度（以字为单位） ；l 标识段的平均生命周期，按存储器访问；f 表示在平衡条件下，未使用的内存部分。提示：计算边界在内存中移动的平均速度，并假设复制一个字至少需要两次存储器访问。b.b. 当 f=0.2，t=1000，s=50 时，计算 F。答：a.a.很明显,在一个周期 t 内一些段会产生而一些段会被删除.因为系统是公平的,一个新的段会在 t 内被插入,此外,边界会医 s/t 的速度移动.假设t0是边界到达空洞的时间,t0=fmr

47、/s, m=内存的长度,在对段进行压缩时会有(1-f)m 个数被移动,压缩时间 至少是 2(1-f)m.则花在压缩上的时间 F 为 F=1-t0/(t0+tc)。b.b.K=(t/2s)-1=9;F(1-0.2)/(1+1.8)=0.29第第 8 8 章章 虚拟内存虚拟内存8.1 假设在处理器上执行的进程的也表如下所示。所有数字均为十进制数，每一项都是从 0 开始记数的，并且所有的地址都是内存字节地址。页尺寸为 1024个字节。虚拟页号有效位访问位修改位页帧号0110411117200031002400051010a描述 CPU 产生的虚拟地址通常是如何转化成一个物理主存地址的。b下列虚拟地址

48、对应于哪个物理地址（不用考略页错误）？（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 因此物理地址是 3798.2 考虑一个使用 32 位的地址和 1KB 大小的页的分页虚拟内存系统。每个页表项需要 32 位。需要限制页表的大小为一个页。a页表一共需要使用几级？b每一级页表的大小是多少？提示：一个页表的大小比较小。c在第一级使用的页较小与在最底下一级使用的页较小相比，那种策略使用最小个数的页？解答a：虚拟内存可以分为 232/210= 222 页，所以需要 22 个 bit 来区别虚拟内存中的一页，每一个页表可以包含 210/4=28 项，因此每个页表可以包含 22bit中的 8 个 bit，所以需要三级索引。b：第二级页表