预计阅读本页时间：-
习题
1.在图3-3中基址和界限寄存器含有相同的值16 384，这是巧合，还是它们总是相等？如果这只是巧合，为什么在这个例子里它们是相等的？
2.交换系统通过紧缩来消除空闲区。假设有很多空闲区和数据段随机分布，并且读或写32位长的字需要10ns的时间，紧缩128MB大概需要多长时间？为了简单起见，假设空闲区中含有字0，内存中最高地址处含有有效数据。
3.请比较用位图和链表两种方法来记录空闲内存所需的存储空间。128MB的内存以n字节为单元分配，对于链表，假设内存中数据段和空闲区交替排列，长度均为64KB。并假设链表中的每个结点需要32位的内存地址、16位长度和16位下一结点域。这两种方法分别需要多少字节的存储空间？哪种方法更好？
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
4.在一个交换系统中，按内存地址排列的空闲区大小是：10KB、4KB、20KB、18KB、7KB、9KB、12KB和15KB。对于连续的段请求：a)12KB；b)10KB；c)9KB。使用首次适配算法，将找出哪个空闲区？使用最佳适配、最差适配、下次适配算法呢？
5.对下面的每个十进制虚拟地址，分别使用4KB页面和8KB页面计算虚拟页号和偏移量：20000，32768，60000。
6.Intel 8086处理器不支持虚拟内存，然而一些公司曾经设计过包含未作任何改动的8086 CPU的分页系统。猜想一下，他们是如何做到这一点的。提示：考虑MMU的逻辑位置。
7.考虑下面的C程序：
int X[N];
int step=M;//M是某个预定义的常量
for(int i=0;i＜N;i+=step)X[i]=X[i]+1;
a)如果这个程序运行在一个页面大小为4KB且有64个TLB表项的机器上时，M和N取什么值会使得内层循环的每次执行都会引起TLB失效？
b)如果循环重复很多遍，结果会和a)的答案相同吗？请解释。
8.存储页面必须可用的磁盘空间和下列因素有关：最大进程数n，虚拟地址空间的字节数v，RAM的字节数r。给出最坏情况下磁盘空间需求的表达式。这个数量的真实性如何？
9.一个机器有32位地址空间和8KB页面，页表完全用硬件实现，页表的每一表项为一个32位字。进程启动时，以每个字100ns的速度将页表从内存复制到硬件中。如果每个进程运行100 ms（包含装入页表的时间），用来装入页表的CPU时间的比例是多少？
10.假设一个机器有48位的虚拟地址和32位的物理地址。
a)假设页面大小是4KB，如果只有一级页表，那么在页表里有多少页表项？请解释。
b)假设同一系统有32个TLB表项，并且假设一个程序的指令正好能放入一个页，并且该程序顺序地从有数千个页的数组中读取长整型元素。在这种情况下TLB的效果如何？
11.假设一个机器有38位的虚拟地址和32位的物理地址。
a)与一级页表比较，多级页表的主要优点是什么？
b)一个有16KB个页、4字节表项的二级页表，应该对第一级页表域分配多少位，对第二级页表域分配多少位？请解释原因。
12.一个32位地址的计算机使用两级页表。虚拟地址被分成9位的顶级页表域、11位的二级页表域和一个偏移量，页面大小是多少？在地址空间中一共有多少个页面？
13.假设一个32位虚拟地址被分成a、b、c、d四个域。前三个域用于一个三级页表系统，第四个域d是偏移量。页面数与这四个域的大小都有关系吗？如果不是，与哪些因素有关以及与哪些因素无关？
14.一个计算机使用32位的虚拟地址，4KB大小的页面。程序和数据都位于最低的页面（0～4095），堆栈位于最高的页面。如果使用传统（一级）分页，页表中需要多少个表项？如果使用两级分页，每部分有10位，需要多少个页表项？
15.一台计算机的进程在其地址空间有1024个页面，页表保存在内存中。从页表中读取一个字的开销是5ns。为了减小这一开销，该计算机使用了TLB，它有32个（虚拟页面，物理页框）对，能在1ns内完成查找。请问把平均开销降到2ns需要的命中率是多少？
16.VAX机中的TLB中没有包含R位，为什么？
17.TLB需要的相联存储设备如何用硬件实现，这种设计对扩展性意味着什么？
18.一台机器有48位虚拟地址和32位物理地址，页面大小是8KB，试问页表中需要多少个表项？
19.一个计算机的页面大小为8KB，内存大小为256KB，虚拟地址空间为64GB，使用倒排页表实现虚拟内存。为了保证平均散列链的长度小于1，散列表应该多大？假设散列表的大小为2的幂。
20.一个学生在编译器设计课程中向教授提议了一个项目：编写一个编译器，用来产生页面访问列表，该列表可以用于实现最优页面置换算法。试问这是否可能？为什么？有什么方法可以改进运行时的分页效率？
21.假设虚拟页码索引流中有一些长的页码索引序列的重复，序列之后有时会是一个随机的页码索引。例如，序列0，1，...，511，431，0，1，...，511，332，0，1，...中就包含了0，1，...，511的重复，以及跟随在它们之后的随机页码索引431和332。
a)在工作负载比该序列短的情况下，标准的页面置换算法（LRU，FIFO，Clock）在处理换页时为什么效果不好？
b)如果一个程序分配了500个页框，请描述一个效果优于LRU、FIFO或Clock算法的页面置换方法。
22.如果将FIFO页面置换算法用到4个页框和8个页面上，若初始时页框为空，访问字符串为0172327103，请问会发生多少次缺页中断？如果使用LRU算法呢？
23.考虑图3-15b中的页面序列。假设从页面B到页面A的R位分别是11011011。使用第二次机会算法，被移走的是哪个页面？
24.一台小计算机有4个页框。在第一个时钟滴答时R位是0111（页面0是0，其他页面是1），在随后的时钟滴答中这个值是1011、1010、1101、0010、1010、1100、0001。如果使用带有8位计数器的老化算法，给出最后一个滴答后4个计数器的值。
25.请给出一个页面访问序列，其第一个被选择置换的页面必须不同于Clock和LRU算法。假设一个进程分配了3个页框，访问串中的页号属于集合0，1，2，3。
26.在图3-21c的工作集时钟算法中，表针指向那个R=0的页面。如果τ=400，这个页面将被移出吗？如果τ=1000呢？
27.把一个64KB的程序从平均寻道时间10ms、旋转延迟时间10ms、每磁道32KB的磁盘上装入，对于下列页面大小分别需要多少时间？
a)页面大小为2KB。
b)页面大小为4KB。
假设页面随机地分布在磁盘上，柱面的数目非常大以至于两个页面在同一个柱面的机会可以忽略不计。
28.一个计算机有4个页框，装入时间、上次访问时间和每个页的R位和M位如下所示（时间以时钟滴答为单位）：
a)NRU算法将置换哪个页面？
b)FIFO算法将置换哪个页面？
c)LRU算法将置换哪个页面？
d)第二次机会算法将置换哪个页面？
29.有二维数组：
int X[64][64];
假设系统中有4个页框，每个页框大小为128个字（一个整数占用一个字）。处理数组X的程序正好可以放在一页中，而且总是占用0号页。数据会在其他3个页框中被换入或换出。数组X为按行存储（即，在内存中，X[0][0]之后是X[0][1]）。下面两段代码中，哪一个会有最少的缺页中断？请解释原因，并计算缺页中断的总数。
A段：
for(int j=0;j＜64;j++)
for(int i=0;i＜64;i++)X[i[[j]=0;
B段：
for(int i=0;i＜64;i++)
for(int j=0;j＜64;j++)X[i][[j]=0;
30.PDP-1是最早的分时计算机之一，有4K个18位字的内存。在每个时刻它在内存中保持一个进程。当调度程序决定运行另一个进程时，将内存中的进程写到一个换页磁鼓上，磁鼓的表面有4K个18位字。磁鼓可以从任何字开始读写，而不仅仅是字0。请解释为什么要选这个磁鼓？
31.一台计算机为每个进程提供65 536字节的地址空间，这个地址空间被划分为4096字节的页面。一个特定的程序有327 68字节的正文、16 386字节的数据和15 870字节的堆栈。这个程序能装入这个地址空间吗？如果页面大小是512字节，能放得下吗？记住一个页面不能同时包含两个不同段的成分。
32.一个页面同一时刻可能在两个工作集中吗？请解释原因。
33.人们已经观察到在两次缺页中断之间执行的指令数与分配给程序的页框数直接成比例。如果可用内存加倍，缺页中断间的平均间隔也加倍。假设一条普通指令需要1µs，但是如果发生了缺页中断就需要2001µs（即2ms处理缺页中断）。如果一个程序运行了60s，期间发生了15 000次缺页中断，如果可用内存是原来的两倍，那么这个程序运行需要多少时间？
34.Frugal计算机公司的一组操作系统设计人员正在考虑在他们的新操作系统中减少对后备存储数量的需求。老板建议根本不要把程序正文保存在交换区中，而是在需要的时候直接从二进制文件中调页进来。在什么条件下（如果有这样的条件话）这种想法适用于程序文本？在什么条件下（如果有这样的条件话）这种想法适用于数据？
35.有一条机器语言指令将要被调入，该指令可把一个32位字装入含有32位字地址的寄存器。这个指令可能引起的最大缺页中断次数是多少？
36.像在MULTICS中那样，当同时使用分段和分页时，首先必须查找段描述符，然后是页描述符。TLB也是这样按两级查找的方式工作的吗？
37.一个程序中有两个段，段0中为指令，段1中为读/写数据。段0有读/执行保护，段1有读/写保护。内存是请求分页式虚拟内存系统，它的虚拟地址为4位页号，10位偏移量。页表和保护如下所示（表中的数字均为十进制）：
对于下面的每种情形，或者给出动态地址所对应的实（实际）内存地址，或者指出发生了哪种失效（缺页中断，或保护错误）。
a)读取页：段1，页1，偏移3；
b)存储页：段0，页0，偏移16；
c)读取页：段1，页4，偏移28；
d)跳转到：段1，页3，偏移32。
38.你能想象在哪些情况下支持虚拟内存是个坏想法吗？不支持虚拟内存能得到什么好处呢？请解释。
39.构造一个柱状图，计算你的计算机中可执行二进制文件大小的平均值和中间值。在Windows系统中，观察所有的.exe和.dll文件；在UNIX系统中，观察/bin、/usr/bin、/local/bin目录下的所有非脚本文件的可执行文件（或者使用file工具来查找所有的可执行文件）。确定这台机器的最优页面大小，只考虑代码（不包括数据）。考虑内部碎片和页表大小，对页表项的大小做出合理的假设。假设所有的程序被执行的可能性相同，所以可以同等对待。
40.MS-DOS中的小程序可以编译成.COM文件。这些文件总是装载到0x100地址的一个内存段，这个内存段用作代码、数据和堆栈。转移执行的控制指令（如JMP、CALL）和访问静态数据的指令把地址编译进目标代码中。写一个程序重定向这个程序文件，使之可以在任意开始地址处运行。读者的程序必须扫描代码，寻找指向固定内存地址的目标代码，然后在重定向范围内修改那些指向内存单元的地址。可以在汇编语言程序正文中找到这些目标地址。注意，要想不借助于额外的信息就出色完成这项工作通常是不可能的，因为有些数据字的值和指令目标代码相仿。
41.编写一个程序，它使用老化算法模拟一个分页系统。页框的数量是参数。页面访问序列从文件中读取。对于一个给定的输入文件，列出每1000个内存访问中发生缺页中断的数目，它是可用页框数的函数。
42.编写一个程序，说明TLB失效对有效内存存取时间的影响，内存存取时间可以用计算每次遍历大数组时的读取时间来衡量。
a)解释编程思想，并描述所期望输出如何展示一些实际的虚拟内存体系结构。
b)运行该程序，并解释运行结果与你的预期有何出入。
c)在一台更古老的且有着不同体系结构的计算机上重复b)，并解释输出上的区别。
43.编写一个程序，该程序能说明当有两个进程的简单情况下，使用局部页置换策略和全局页置换策略的差异。读者将会用到能生成一个基于统计模型的页面访问串的例程。这个模型有N个状态，从0到N-1，代表每个可能的页面访问，每个状态i相关的概率pi 代表下一次访问仍指向同一页面的几率。否则，下一次页面访问将以等概率指向其他任何一个页面。
a)说明当N比较小时，页面访问串生成例程能运行正常。
b)对有一个进程和固定数量的页框的情况计算缺页中断率。解释这种结果为什么是正确的。
c)对有独立页面访问序列的两个进程，以及是b)中页框数两倍的页框，重复b)。
