101 110 并接，得到：八进制物理地址001000000 1 100 101 110 = = 201456 （八进制）。
13 主存中有两个空间区如图所示， 100K 50K 125K 0K 15K
现有作业序列依次为：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 …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
6 / 12
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 如下所示（时间用时钟点数表示）:
7 / 12
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
8 / 12
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 缺页中断率高。
29 假设计算机有2M 内存，其中，操作系统占用512K ，每个用户程序也使用512K 内存。如果所有程序都有70 ％的I/O 等待时间，那么，再增加1M 内存，吞吐率增加多少？ 答：由题意可知，内存中可以存放3 个用户进程，而CPU 的利用率为：1-（70 % )3 , = 1 一（0 . 7 )3 = 65 . 7 ％。再增加1M 内存，可增加2 个用户进程，这时CPU 的利用率为：1 -（70 % )5 , = 1 一（0 ．7）5＝83 . 2 ％。故再增加1M 内存，吞吐率增加了：83 . 2 ％/65 . 7 ％-100 % =27 ％。
9 / 12
30 一个计算机系统有足够的内存空间存放4 道程序，这些程序有一半时间在空闲等待I/O 操作。问多大比例的CPU 时间被浪费掉了？ 答：( 500 % )＝( l / 2 ) = 1 / 16 。 31 如果一条指令平均需1 微秒，处理一个缺页中断另需n 微秒，给出当缺页中断每k 条指令发生一次时，指令的实际执行时间。 答：( 1 +n/k)微秒。
32 一台计算机的内存空间为1024 个页面，页表放在内存中，从页表中读一个字的开销是50Ons 。为了减少开销，使用了有32 个字的快表，查找速度为10Ons 。要把平均开销降到20Ons 需要的快表命中率是多少？
答：设快表命中率是x ，则内存命中率为1-x。于是：500 ( 1-x）+ 100x = = 2 00 ，解方程得x=75 ％。
33 假设一条指令平均需花1 微秒，但若发生了缺页中断就需2001 微秒。如果一个程序运行了60 秒，期间发生了15000 次缺页中断，若可用内存是原来的两倍，这个程序坛行需要多少时间？
答：一个程序运行期间发生了15000 次缺页中断，由于缺页中断处理花2000 微秒（1 微秒是指令执行时间，于是这个程序缺页中断处理花了：2000 微秒米1 5000 = 30 秒。占了运行时间60 秒的一半。当可用内存是原来的两倍时，缺页中断次数减为一半，故有巧秒就能处理完。所以，这个程序运行需要时间为：45 秒。
34 在分页式虚存管理中，若采用FIFO替换算法，会发生：分给作业页面越多，进程执行时缺页中断率越高的奇怪现象。试举例说明这个现象。 答：见本章应用题7 。
35 假设一个任务被划分成4 个大小相等的段，每段有8 项的页描述符表，若页面大小一为ZKB 。试问段页式存储系统中：( a ）每段最大尺寸是多少？伪）该任务的逻辑地址空间最大为多少？( c ）若该任务访问到逻辑地址空间5ABCH 中的一个数据，试给出逻辑地址的格式。
答：段数2 2 = 4 ，每段有23 = 8 页，页大小为211= ZKB 。（a ）故每段最大为214B = 16KB 。伪）逻辑她曳匕勿风爆七尺4 又、曰KB = 64KB 。 ( c ）若该任务访问到逻辑地址空间SABCH ，其二进制表示为： 0 101 1010 1011 1100
所以，逻辑地址表示为：01 011 010 1011 1100
SABCH 的逻辑地址为：第1 段第3 页，位移由后11 位给出。
36.对已知某系统页面长4KB ，页表项4B ，采用多级页表映射64 位虚地址空间。若限定最高层页表占1 页，问它可以采用几级页表？
10 / 12