缺页处理时，若内存有可用空间或被置换的页面在内存未被修改过，则处理一个缺页中断需8ms，否则需20ms。假定被置换的页面60％是属于后一种情况，则为了保证有效存取时间不超过2us，问可接受的最大缺页率是多少？
8.为什么要引入动态链接 ?
9．在分页存储管理系统中，存取一次内存的时间是8us，查询一次快表的时间是1us，缺页中断的时间是20us。假设页表的查询与快表的查询同时进行，当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。一个作业最多可保留3个页面在内存。现开始执行一作业，系统连续对作业的２、４、5、２、7、6、4、2各页面的数据进行1次存取，如分别采用FIFO算法和最优页面置换算法，求每种算法下存取这些数据需要的总时间？
5.5 考研试题精选及解析
1. 有矩阵：VAR A：ARRAY[1‥100,1‥100]OF integer；
按先行后列次序存储。在一虚存系统中，采用LRU淘汰算法，一个进程有3页内存空间，每页可以存放200个整数。其中第1页存放程序，且假定程序已在内存。 程序A：
FOR i：＝1 TO 100 DO FOR j：＝1 TO 100 DO A[i,j]：＝0； 程序B：
FOR j：＝1 TO 100 DO FOR i：＝1 TO 100 DO A[i,j]：＝0；
分别就程序A和B的执行进程计算缺页次数。（北京大学1993年存储管理题） [分析及相关知识]
由于每一进程在内存中有3个页面，且其中的1页用于存放程序，所以可用作存放数据的页面只有2个。
由题目中的定义可知，数组A中有10000个整数，每页存放200个整数，数组占用空间50页。假设数据从该作业的第m页开始存放，由数组分布在第m页到第m+49页中。因数据是按先行后列次序存储，它的存储顺序为：
A[1,1],A[1,2],…,A[1,100],A[2，1]，A[2，2],…,A[2,100] 第m页 A[3,1],A[3,2],…,A[3,100],A[4，1]，A[4，2],…,A[4,100] 第m＋1页 A[99,1],A[99,2],…,A[99,100],A[100，1]，A[100，2],…,A[100,100] 第m＋49页 解：对于程序A：
由于程序A对矩阵A的访问是按列进行，即按照存储顺序顺序进行。因此每次缺页中断调进一页后，位于该页内的数组元素全部赋予0值，然后再调入下一页，所以涉及的页面走向为，m,m+1,…,m+49，故缺页次数为50次。 对于程序B：
由于程序对矩阵A的访问是按列进行，而矩阵A每行有100个数据，每页可以存放200个数据，因此每页中有2个数据属于同一列，每次缺页中断调进一页时，只有其中的2个数据赋予0值，即程序矩阵A每两次访问会遇到一次缺页。所以涉及的页面走向为： m,m+1,…,m+49 处理1列 m,m+1,…,m+49 处理2列 ┋
m,m+1,…,m+49 处理100列 故缺页次数为： 100×50＝5000次
2.虚拟存储器利用了swap area(交换区)、内存及cache。假设：从cache读取一个字节的数据需要Ans；如果数据不在cache而在内存，则从内存读至cache需要Bns，然后才能从cache访问；如果数据不在内存又不在cache，需要Cns从交换区读入内存，然后，读入cache才能取用。假设缓存cache命中率为（n-1）/n，内存命中率为（m-1）/m，求数据平均访问时间。（浙江大学2001、北京工业大学2000存储管理题） 答：
数据在缓存中的比率为：(n-1)/n
数据在内存中的比率为：(1-(n-1)/n)×(m-1)/m=(m-1)/nm 数据在SA中的比率为：(1-(n-1)/n)×(1-(m-1)/m)=1/nm
故数据平均访问时间是=((n-1)/n)×A+((1-(n-1)/n)×(m-1)/m)×(A+B)+( (1-(n-1)/n)×(1-(m-1)/m))×(A+B+C)=A+B/n+C/nm
3.在一个请求分页系统中，假定系统分配给一个作业的物理块数为3，并且此作业的页面走向为2、3、2、1、5、2、4、5、3、2、5、2，试用FIFO和LRU两种算法分别计算出程序访问过程中所发生的缺页次数。（中科院软件所1999年存储管理题）
解：在本题中，分配给作业的物理块数为3。
（1）根据所给页面走向，使用FIFO算法时，页面置换情况如下：缺页次数为：9。 走向 2 3 2 1 5 2 4 5 3 2 5 2 块1 2 2 2 5 5 5 3 33 块2 3 3 3 2 2 2 5 5 块3 1 1 1 4 4 4 2 缺页缺缺缺缺缺缺缺缺缺
（2）根据所给页面走向，使用LRU算法时，页面置制情况下：缺页次数为：7。 走向 2 3 2 1 5 2 4 5 3 2 5 2 块1 2 2 2 2 5 5 5 块2 3 3 5 2 3 3 块3 1 1 4 4 2 缺页缺缺缺缺缺缺缺
4.请求分页系统中一个进程访问页面的次序为：0、2、1、3、0、2、4、0、2、1、3、4。利用FIFO算法，当进程使用3个页框时缺页多少次? 使用4个页框时缺页多少次?( 缺页次数含初始调入次数)。(中科院 2001存储管理题) 解：分别为9次和10次。
5.一个32位虚地址被分成a、b、c、d四个域，a、b、c用于三级页表系统，d是页内偏移，页面数为多少? (中科院2001存储管理题) 解：2a+b+c。
6.某虚拟存储器中的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的笫0、1、2、3页分别分配物理块为5、10、4、7，虚拟地址0A6F对应的物理地址为多少? (中科院2001存储管理题)
解：由于用户空间共有32个页面，每页1KB，改虚地址共有15位长。0A6F对应的二进数15位为：000 1010 0110 1111。可见是第2个虚页，其对应的物理块号为4。故物理地址为：
010 010 0110 1111，即226F。
7.某计算机系统一条指令执行需10ns，一次缺页需额外的20ms，如果每1 000 000条指令发生一次缺页，则指令平均执行时间为多少ns? (中科院2001存储管理题)
解：一条指令需要10ns，1 000 000条指令执行时间为：10 000 000ns，故1 000 000条指令执行时间为10 000 000+20 000 000=30 000 000ns。30 000 000/1 000 000=30ns。
8.在某页式虚存储系统中，假定访问内存的时间是10ms，平均缺页中断处理时间为25ms，平均缺页中断率为5%。试计算在该虚存储系统中，平均有效访问时间是多少? (华南理工大学2000存储管理题) 解：
若访问页面在内存中，—次访问时间是 10ms+10ms=20ms。
若访问页面不在内存中，—次访问时间是 10ms(访问内存页长，缺页)+25ms(中断处理，调页)+ 10ms(访问内存页表，页已调入)+10ms(访问内存)=55ms。 平均有效访问时间是=20ms×95%+55ms×5%=21.75ms。
9.现有一请求分页的虚拟存储器，内存最多容纳4个页面，对于下面的引用串：1，2，3，4，5，3，4，1，6，7，8，7，8，9，7，8，9，5，4，5，4，2，分别采用FIFO、LRU、OPT页面置换算法，各将产生多少次缺页中断? (东南大学2001存储管理题) 解：FIFO为13次，LRU为13次，OPT为11次。
10.一进程己分配到4个页框，如表所示。当进程访问第4页时，产生缺页中断。请分别用FIFO、LRU和NRU算法，决定缺页中断服务程序选择换出的页面。(浙江大学2000存储管理题) 解：
FIFO 换出进入内存时间最久的页面，130最久，故第1页换出。
LRU 最近最长时间未用的页，第1、2页最近未被访问，但第1页最近被访问时间
虚页号页框装入时间最近访问时间访问位修改位 2 0 60 161 0 1 1 1 130 160 0 0 较少(160)，故第1页换出。
NRU 最近未用过的页换出，表中第1页的访问位为0，故第1页换出。
11.假定某页式虚拟存储器，内存平均访问时间为1微秒、辅存平均访问时间为10亳秒，试问如果希望虚存的平均访问时间仅比内存增加10%，则需要页面失效率是多少? (浙江大学2000存储管理题)
解：设页面失效率为f，则虚存的平均访问时间为： (1-f)×1微秒+f×10亳秒=1-f+10000f=1+9999f
如果希望虚存的平均访问时间仅比内存增加10%，也就是： 1+10%>1+9999f 1.1>1+9999f
解得 f<0.00001 即要求每访问10万次，才允许缺页一次。
操作系统原理第五章 存储管理习题
