发布时间 : 星期五 文章《操作系统精髓与设计原理·第五版》练习题及答案更新完毕开始阅读4dea71b9f121dd36a32d82d0
7.11. 在程序执行期间，每次取指令后处理器把指令寄存器的内容（程序计数器）增加一个字，但如果遇
到会导致在程序中其他地址继续执行的转跳或调用指令，处理器将修改这个寄存器的内容。现在考虑图7.8。关于指令地址有两种选择：
? 在指令寄存器中保存相对地址，并把指令寄存器作为输入进行动态地址转换。当遇到一次成功的
转跳或调用时，由这个转跳或调用产生的相对地址被装入到指令寄存器中。
? 在指令寄存器中保存绝对地址。当遇到一次成功的转跳或调用时，采用动态地址转换，其结果保
存到指令寄存器中。 哪种方法更好？
答：使用绝对地址可以减少动态地址转换的次数。但是，我们希望程序能够被重定位。因此，在指令寄存器中保存相对地址似乎就更好一些。也可以选择在进程被换出主存时将指令寄存器中的地址转换为相对地址。
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之后。
29
当段（正在使用或已被删除）和洞之间的边界到达内存的另一端时，压缩正在使用的段。 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章 虚拟内存
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个页表项。
30
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个溢出项的空间，则哈希反向页表需要占用多大的内存空间？ 解答
a：4Mbyte
b：行数：26+2=128项。每项包含：20（页号）+20（帧号）+8bits（链索引）=48bits=6bytes。总共：128*6=768bytes
8.4 一个进程分配给4个页帧（下面的所有数字均为十进制数，每一项都是从0开始计数的）。上一次把一页装入到一个页帧的时间，上一次访问页帧中的页的时间，每个页帧中的虚拟页号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之间的时钟时间，而不是从事件发生到当前的时钟值）。 虚拟页号 页帧 加载时间 访问时间 R位 M位 2 0 60 161 0 1 1 1 130 160 1 0 0 2 26 162 1 0 3 3 20 163 1 1 当虚拟页4发生错误时，使用下列内存管理策略，哪一个页帧将用于置换？解释原因。 a.FIFO（先进先出）算法 b.LRU（最近最少使用）算法 c.Clock算法
d.最佳（使用下面的访问串）算法
e.在页错误之前给定上述内存状态，考虑下面的虚拟页访问序列： 4,0,0,2,4,2,1,0,3,2
如果使用窗口大小为4的工作集策略来代替固定分配，会发生多少页错误？每个页错误何时发生？ 解答
a:页帧3，在时间20加载，时间最长。
b:页帧1，在时间160访问距现在时间最长。 c:清除页帧3的R位（最早加载），清除页帧2的R位，（次最早加载），换出的是页帧0因为它的R位为0。
d:换出的是页帧3中的虚拟页3，因为它将最晚被访问到。 e:一共有6个错误，如下
8.5 一个进程访问5页：A,B,C,D和E，访问顺序如下：
A;B;C;D;A;B;E;A;B;C;D;E
假设置换算法为先进后出，该进程在主存中有三个页帧，开始时为空，请查找在这个访问顺
31
序中传送的页号。对于4个页帧的情况，请重复上面的过程。 解答
分别有9次和10次页错误，这被称之为“Belady′s现象”（\Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine,\by Belady et al, Communications of the ACM, June 1969.）
8.6 一个进程在磁盘上包含8个虚拟页，在主存中固定分配给4个页帧。发生如下顺序的页访问：
1,0,2,2,1,7,0,1,2,0,3,0,4,5,1,5,2,4,5,6,7,6,7,2,4,2,7,3,3,2,3
a.如果使用LRU替换策略，给出相继驻留在这4个页帧中的页。计算主存的命中率。假设这些帧最初是空的。
b.如果使用FIFO策略，重复问题（a）。
c.比较使用这两种策略的命中率。解释为什么这个特殊的访问顺序，使用FIFO的效率接近于LRU。 解答
a:LRU：命中率=16/33
b:FIFO：命中率=16/33
c:这两种策略对这个特殊的页轨迹（执行顺序）是等效的。
8.7 在VAX中，用户页表以系统空间的虚拟地址进行定位。让用户页表位于虚存而不是主存中有什么好处？有什么缺点？ 解答
最主要的优点是在物理内存空间上的节省。这主要是两方面的原因：（1）一个用户页表可以仅当使用时才取入内存。（2）操作系统可以动态的分配用户页表，产生一个页表仅当程序被创建时。
当然，也有一个缺点：地址转换需要多余的工作。 8.8 假设在主存中执行下列程序语句： for(i=1;i≤n;i++) a[i]=b[i]+c[i];
页尺寸为1000个字。令n=1000。使用一台具有所有寄存器指令并使用了索引寄存器的机器，写出实现上述语句的一个假想程序，然后给出在执行过程中的页访问顺序。 解答
由机器语言编写的程序，在主存中地址4000处开始运行。运行情况如下： 4000 （R1）←1 建立索引记录i 4001 （R1）←n 在R2中建立n 4002 比较R2，R1 检查i﹥n 4003 如果大于则跳转到4009
4004 （R3）←B（R1） 使用索引记录R1到达B[i]
32