现有用户进程依次分别为212K 、417K 、112K 和426K , ( l ）分别用first-fit 、best-fit 和worst-fit 算法将它们装入到内存的哪个分区？( 2 ）哪个算法能最有效利用内存？
答：按题意地址从小到大进行分区如图所示。
分区号 分区长 100KB 500KB 200KB 300KB 600KB 1 2 3 4 5 ( 1 ) 1）first-fit 212KB 选中分区2 ，这时分区2 还剩288KB 。417KB 选中分区5 ，这时分区5 还剩183KB 。112KB 选中分区2 ，这时分区2 还剩176KB 。426KB 无分区能满足，应该等待。 2 ) best-fit 212KB 选中分区4 ，这时分区4 还剩88KB 。417KB 选中分区2 ，这时分区2 还剩83KB 。112KB 选中分区3 ，这时分区3 还剩88KB 。426KB 选中分区5 ，这时分区5 还剩174KB 。
3 ) worst-fit 212KB 选中分区5 ，这时分区5 还剩388KB 。417KB 选中分区2 , 这时分区2 还剩83KB 。112KB 选中分区5 ，这时分区5 还剩176KB 。426KB 无分区能满足，应该等待。
( 2 ）对于该作业序列，best-fit 算法能最有效利用内存
6、 一个32 位地址的计算机系统使用二级页表，虚地址被分为9 位顶级页表，11位二级页表和偏移。试问：页面长度是多少？虚地址空间共有多少个页面？ 答：由于32-9 -11 ＝ 12 ，所以，页面大小为4KB ，页面的个数为220个。 7、 一进程以下列次序访问5 个页：A 、B 、C 、D 、A 、B 、E 、A 、B 、C 、D 、E ：假定使用FIFO 替换算法，在内存有3 个和4 个空闲页框的情况下，分别给出页面替换次数。
答：内存有3 个和4 个空闲页框的情况下，页面替换次数为9 次和10 次。出现了Belady 即现象，增加分给作业的内存块数，反使缺页中断率上升。 8、 某计算机有缓存、内存、辅存来实现虚拟存储器。如果数据在缓存中，访问它需要Ans；如果在内存但不在缓存，需要Bns 将其装入缓存，然后才能访问；如果不在内存而在辅存，需要Cns 将其读入内存，然后，用Bns 再读入缓存，然后才能访问。假设缓存命中率为（n-1) / n ，内存命中率为（m -1) / m ，则数据平均访问时间是多少？ 答：
数据在缓存中的比率为：( n - 1 ) / n
数据在内存中的比率为：( 1 -（n - 1 ) / n )×( m - 1 ) / m = ( m - 1 ）/nm
数据在辅存中的比率为：( 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
9、某计算机有cache 、内存、辅存来实现虚拟存储器。如果数据在cache 中，访问它需要20ns ；如果在内存但不在cache ，需要60ns 将其装入缓存，然后才能访问；如果不在内存而在辅存，需要12us将其读入内存，然后，用60ns 再读入cache ，然后才能访问。假设cache 命中率为0 .9 ，内存命中率为0.6 ，则数据平均访问时间是多少（ns ) 答：506ns 。
10 有一个分页系统，其页表存放在主存里，( 1 ）如果对内存的一次存取要1.2 微秒，试问实现一次页面访问的存取需花多少时间？( 2 ）若系统配置了联想存储器，命中率为80 % ，假定页表表目在联想存储器的查找时间忽略不计，试问实现一次页面访问的存取时间是多少？
答：(1) 2.4 微秒 （2 )0.8 × 1.2 + 0.2 × 2.4 = 0.76 + 0.45 = 1.24 微秒
11 给定段表如下：
段号 段首址 219 2300 90 1327 1952 段长 600 14 100 580 96 0 1 2 3 4 给定地址为段号和位移： 1 ) [ 0 , 430] 、2 ) [ 3 , 400 ］、3 ) [ 1 , 1 ］、4 ) [ 2 , 500 ］、5 ) [ 4 , 42 ) ，试求出对应的内存物理地址。 答：1) 649 2) 1 727 3) 2301 4）越界 5) 1994 12、 某计算机系统提供24 位虚存空间，主存为2 18 B ，采用分页式虚拟存储管理，页面尺寸为1KB 。假定用户程序产生了虚拟地址11123456 （八进制），而该页面分得块号为100 ( 八进制），说明该系统如何产生相应的物理地址及写出物理地址。
答：虚拟地址11123456 （八进制）转化为二进制为： 001 001 001 010 011 100 101 110 其中前面为页号，而后10 位为位移：001 001 001 010 01-------1 100 101 110 。由于主存大小为218 B，页面尺寸为1KB ，所以，主存共有256 块。所以，块号为100 （八进制）是合法地址，于是，物理地址为100 （八进制）与位移1 100 101 110 并接，得到：八进制物理地址001000000 1 100 101 110 = = 201456 （八进制）。
13 主存中有两个空间区如图所示， 100K 50K 0K 15K 125K
现有作业序列依次为：Job1 要求30K ; Job2 要求70K ; Job3 要求50K ；使用首次适应、最坏适应和
最佳适应算法处理这个作业序列，试问哪种算法可以满足分配？为什么？ 答：首次适应、最坏适应算法处理这个作业序列可以满足分配，最佳适应算法不行。因为后者会分割出无法使用的碎片，浪费内存，从而，不能满足所有作业的内存需求。
14 设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16 页，每页2048 字节，内存总共有8 个存储块。试问逻辑地址至少应为多少位？内存空间有多大？ 答：
逻辑地址211×24 ，故为15 位。内存大小为23×211 = 214B = 16KB 。
15、在一分页存储管理系统中，逻辑地址长度为16 位，页面大小为4096 字节，现有一逻辑地址为ZF6AH ，且第0 、1 、2 页依次存在物理块10 、12 、14 号中，问相应的物理地址为多少？
答：因为逻辑地址长度为16 位，而页面大小为4096字节，所以，前面的4 位表示页号。把ZF6AH 转换成二进制为：00 10 1 1 11 0110 1010 ，可知页号为2 。故放在14 号物理块中，写成十六进制为：EF6AH 。
16 有矩阵：VAR A : ARRAY [ 1 ?00 , 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 的执行进程计算缺页次数。 答：100 * 100 = 10000 个数据，每页可以存放200 个整数，故一共存放在50 个第99 行、第100 行缺页中断为5000 次。由于元素按行存储，第1 行、第2 行放在第1 页，? 第99行、第100行放在第50 页。故对于程序A ，缺页中断为50 次。对于程序B，缺页中断为5000次。
17、一台机器有48 位虚地址和32 位物理地址，若页长为8KB ，问页表共有多少个页表项？如果设计一个反置页表，则有多少个页表项？
答：因为页长8KB 占用13 位，所以，页表项有235个。反置页表项有219 个。 18 在虚拟页式存储管理中，为解决抖动问题，可采用工作集模型以决定分给进程的物理块数，有如下页面访问序列：
?? 2 5 1 6 3 3 7 8 9 1 6 2 3 4 3 4 3 4 4 4 3 4 4 3 ??
| △ t1 | | △ t2 |
窗口尺寸△ ＝9 ，试求t1 、t2 时刻的工作集。
答：t1 时刻的工作集为：{ l , 2 , 3 , 6 , 7 , 8 , 9 ｝。t 时刻的工作集为：{ 3 , 4 ｝。
19 有一个分页虚存系统，测得CPU 和磁盘的利用率如下，试指出每种情况下的存在问题和可采取的措施：( 1 ) CPU 利用率为13 % ，磁盘利用率为97 % ( 2 ) CPU 利用率为87 % ，磁盘利用率为3 % ( 3 ) CPU 利用率为13 % ，磁盘利用率为3 ％。
答：( 1 ）系统可能出现抖动，可把暂停部分进程运行。（2 ）系统运行正常，可增加运行进程数以进一步提高资源利用率。（3 ）处理器和设备和利用率均很低，可增加并发运行的进程数。
20、在一个分页虚存系统中，用户编程空间32 个页，页长IKB ，主存为16KBo 如果用户程序有10 页长，若己知虚页0 、1 、2 、3 ，己分到页框8 、7 、4 、10 , 试把虚地址OACSH 和IACSH 转换成对应的物理地址。
答：虚地址OACSH 对应的物理地址为：12CSH 。而执行虚地址IACSH 会发现页表中尚未有分配的页框而发生缺页中断，由系统另行分配页框。
21 某计算机有4 个页框，每页的装入时间、最后访问时间、访问位R 、修改位D 如下所示（时间用时钟点数表示）: page loaded last ref R D 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1
分别用FIFO 、LRU 、二次机会算法分别淘汰哪一页？ 答：( 1 ) FIFO 淘汰page2 。 ( 2 ) LRU 淘汰page1 。 ( 3 ）二次机会淘汰page1
22 考虑下面的程序：for ( i = 0;i < 20 ; i++） For(j=0;j<10;j++)
a [ i ] : = a [i] ×j
试举例说明该程序的空间局部性和时间局部性。
答：当数组元素a [0] , a[1] ，? ，a [ 19 ] 存放在一个页面中时，其空间局部性和时间局部性较好，也就是说，在很短时间内执行都挂行循环乘法程序，而且数组元素分布在紧邻连续的存储单元中。当数组元素存放在不同页面中时，其时间局部性虽相同，但空间局部性较差，因为处理的数组元素分布在不连续的存储单元中。
23 一个有快表的请页式虚存系统，设内存访问周期为1 微秒，内外存传送一个页面的平均时间为5 毫秒。如果快表命中率为75 % ，缺页中断率为10 ％。忽略快表访问时间，试求内存的有效存取时间。
答：快表命中率为75 % ，缺页中断率为10 % ，所以，内存命中率为15％。故内存的有效存取时间＝1×75 % + 2*15%+( 5000+2) *10%=501.25 微秒。
24 假设某虚存的用户空间为IO24KB ，页面大小为4KB ，内存空间为512KB 。已知用户的虚页10 、11 、12 、13 页分得内存页框号为62 、78 、25 、36 ，求出虚地址OBEBC ( 16 进制）的实地址（16 进制）是多少？
答：虚地址0BEBC ( 16 进制）的二进制形式为：0000 1 011 1110 1011 1100 。由于页面大小为4KB ，故其中后12 位是位移，所以，虚地址的页号为：11 。查页表分得内存对应页框号为：78 。己知内存空间为512KB ，故内存共有128 个页框，78 是合法物理块。把78 化为16 进制是4E ，虚地址OBEBC ( 16 进制）的实地址（16 进制）是：4EEBC 。
25 ／某请求分页存储系统使用一级页表，假设页表全部放在主存内，: 1 ）若一次访问主存花120ns ，那么，访问一个数据的时间是多少？ 2 ）若增加一个快表，在命中或失误时需有20ns 开销，如果快表命中率为80 % ，则
访问一个数据的时间为 答：1 ) 120ns*2 = 240ns
2 ) ( 120 + 20 ) *80 % +(120+120+20)*20%=174ns 26 设某系统中作业J . , JZ , J3 占用主存的情况如图。今有一个长度为20k 的作业J4 要装入主存，当采用可变分区分配方式时，请回答： ( l ) J4 装入前的主存己分配表和未分配表的内容。
( 2 ）写出装入J4 时的工作流程，并说明你采用什么分配算法。 10k 18k 30k 40k 54k70k
答：( 1 ）主存已分配表共有三项，由作业j1 、j2 、j3 占用，长度依次为：10k 、30k 和54k 未分配表共有三项：空闲区1 、空闲区2 和空闲区3 ，长度依次为18k 、40k 和70k 。( 2 ）作业J4 装入时，采用直接分配，搜索未分配表，空闲区1 不能满足。所以，要继续搜索未分配表，空闲区2 可以满足J4 的装入要求。
27 考虑下列的段表：
段号始址段长: 段号 始址 段长 0 200 500 1 890 30 2 120 100 3 1250 600 4 1800 88
对下面的逻辑地址，求物理地址，如越界请指明。l ) ＜0,480 > 2 ) < l ,25 > 3 ) < l ,14 > 4 ) < 2 , 200> 5 ) < 3 ,500 > 6 ) < 4 ,100 > . 答：l ) 680 ( 2 ) 915(3 ) 904(4 ）越界(5 ) 1750(6 ）越界。 28请页式存储管理中，进程访问地址序序列为：10 , 11 , 104 , 170 , 73 , 305 , 180 , 240 , 2 科，科5 , 467 , 366。试问(1 ）如果页面大小为100 ，给出页面访问序列。2 、讲程若分3个页框采用 FIFO 和LRU 替换算法，求缺页中断率？
答：l ）页面访问序列为l , l , 2 , 2 , 1 , 4 , 2 , 3 , 3 , 5 , 5 , 4 。 2 ) FIFO 为5 次，缺页中断率为5 / 12 科41.6 ％。LRU 为6 次，缺页中断率为6 / 12 = 50 ％。LRU 反比FIFO 缺页中断率高。