d. 40M,20M,10M,的起始地址是80M,230M,360M.
7.7. 使用伙伴系统分配一个1MB的存储块。
a. 利用类似于图7.6的图来说明按下列顺序请求和返回的结果：请求70；请求35；
请求80；返回A；请求60；返回B；返回D；返回C。 b. 给出返回B之后的二叉树表示。 答： a.
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。关于指令地址有两种选择：
? 在指令寄存器中保存相对地址，并把指令寄存器作为输入进行动态地址转换。当
遇到一次成功的转跳或调用时，由这个转跳或调用产生的相对地址被装入到指令寄存器中。
? 在指令寄存器中保存绝对地址。当遇到一次成功的转跳或调用时，采用动态地址
转换，其结果保存到指令寄存器中。 哪种方法更好？ 答：使用绝对地址可以减少动态地址转换的次数。但是，我们希望程序能够被重定位。因此，在指令寄存器中保存相对地址似乎就更好一些。也可以选择在进程被换出主存时将指令寄存器中的地址转换为相对地址。
3210
7.12. 考虑一个简单分页系统，其物理存储器大小为2字节，页大小为2字节，逻辑地址
16
空间为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。 答：
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.1 简单分页与虚拟分页有什么区别？ 简单分页：一个程序中的所有的页都必须在主存储器中程序才能正常运行，除非使用覆盖技术。虚拟内存分页：不是程序的每一页都必须在主存储器的帧中来使程序运行，页在需要的时候进行读取。 8.2 解释什么是抖动。 虚拟内存结构的震动现象，在这个过程中处理器大部分的时间都用于交换块，而不是执行指令。
8.3 为什么在使用虚拟内存时，局部性原理是至关重要的？ 可以根据局部性原理设计算法来避免抖动。总的来说，局部性原理允许算法预测哪一个当前页在最近的未来是最少可能被使用的，并由此就决定候选的替换出的页。
8.4 哪些元素是页表项中可以找到的元素？简单定义每个元素。 帧号：用来表示主存中的页来按顺序排列的号码。存在位（P）：表示这一页是否当前在主存中。修改位（M）：表示这一页在放进主存后是否被修改过。 8.5 转移后备缓冲器的目的是什么？
转移后备缓冲器（TLB）是一个包含最近经常被使用过的页表项的高速缓冲存储器。它的目的是为了减少从磁盘中恢复一个页表项所需的时间。 8.6 简单定义两种可供选择的页读取策略。 在请求式分页中，只有当访问到某页中的一个单元时才将该页取入主存。在预约式分页中，读取的并不是页错误请求的页。 8.7 驻留集管理和页替换策略有什么区别？ 驻留集管理主要关注以下两个问题：（1）给每个活动进程分配多少个页帧。（2）被考虑替换的页集是仅限在引起页错误的进程的驻留集中选择还是在主存中所有的页帧中选择。页替换策略关注的是以下问题：在考虑的页集中，哪一个特殊的页应该被选择替换。
8.8 FIFO和Clock页替换算法有什么区别？
时钟算法与FIFO算法很接近，除了在时钟算法中，任何一个使用位为一的页被忽略。
8.9 页缓冲实现的是什么？
（1）被替换出驻留集的页不久又被访问到时，仍在主存中，减少了一次磁盘读写。（2）被修改的页以簇的方式被写回，而不是一次只写一个，这就大大减少了I/O操作的数目，从而减少了磁盘访问的时间。
8.10 为什么不可能把全局替换策略和固定分配策略组合起来？ 固定分配策略要求分配给一个进程的帧的数目是确定的，当一个进程中取入一个新的页时，这个进程的驻留页集中的一页必须被替换出来（保持分配的帧的数目不变），这是一种局部替换策略。 8.11 驻留集和工作集有什么区别？
一个进程的驻留集是指当前在主存中的这个进程的页的个数。一个进程的工作集是指这个进程最近被使用过的页的个数。 8.12 请求式清除和预约式清除有什么区别？ 在请求式清除中，只有当一页被选择用于替换时才被写回辅存；在预约式清除中，将这些被修改的多个页在需要用到它们所占据的页帧之前成批的写回辅存。
习题解答
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位哈希表。表项包含页号帧号和链指针。如果页表可以给每个哈希表项分配最多3个溢出项的空间，则哈希反向页表需要占用多大的内存空间？ 解答