操作系统习题及答案归纳.pdf

CH4 应用题参考答案1 在一个请求分页虚拟存储管理系统中，一个程序运行的页面走向是：1 、2 、3 、4 、2 、1 、5 、6 、2 、1 、2 、3 、7 、6 、3 、2 、1 、2 、3 、6 分别用 FIFO 、OPT 和 LRU 算法，对分配给程序3 个页框、 4 个页框、 5 个页框和 6 个页框的情况下，分别求出缺页中断次数和缺页中断率答：页框数FIFO LRU OPT 3 4 5 6 16 14 12 9 15 10 8 7 11 8 7 7 只要把表中缺页中断次数除以20，便得到缺页中断率2 在一个请求分页虚拟存储管理系统中，一个作业共有5 页，执行时其访问页面次序为：( 1 ) 1 、4 、3 、1 、2 、5 、1 、4 、2 、1 、4 、5( 2 ) 3 、2 、1 、4 、4 、5 、5 、3 、4、3、2、1、5若分配给该作业三个页框，分别采用FIFO和 LRU 面替换算法，求出各自的缺页中断次数和缺页中断率答：( 1 ）采用 FIFO 为 9 次，9 / 12 = 75 采用 LRU 为 8 次，8 / 12 = 67 2 ）采用 FIFO 和 LRU 均为 9 次，9 / 13 = 69 。

3 一个页式存储管理系统使用FIFO 、OPT 和 LRU 页面替换算法， 如果一个作业的页面走向为：( l ) 2 、3 、2 、l 、5 、2 、4 、5 、3 、2 、5 、2 2 ) 4 、3 、2 、l 、4 、3 、5 、4 、3 、2 、l 、5 3 ) 1 、2 、3 、4 、1 、2 、5 、l 、2 、3 、4 、5 当分配给该作业的物理块数分别为3 和 4 时，试计算访问过程中发生的缺页中断次数和缺页中断率答：( l ）作业的物理块数为3 块，使用 FIFO 为 9 次，9 / 12 = 75 使用 LRU 为 7 次，7 / 12 = 58 使用 OPT 为 6 次，6 / 12 = = 50 作业的物理块数为4 块，使用 FIFO 为 6 次，6 / 12 = 50 使用 LRU 为 6 次，6 / 12 = 50 使用 OPT 为 5 次，5 /12 = 42 2 ）作业的物理块数为3 块，使用 FIFO 为 9 次，9 / 12 = 75 使用 LRU 为 10 次，10 / 12 = 83 使用 OPT 为 7 次，7/12 = 58 作业的物理块数为4 块，使用 FIFO 为 10 次，10 / 12 = 83 。

使用 LRU 为 8 次，8/12 66使用 OPT为 6 次，6/1250%. 其中，出现了 Belady 现象，增加分给作业的内存块数，反使缺页中断率上升4、 在可变分区存储管理下， 按地址排列的内存空闲区为： 10K 、 4K 、 20K 、 18K 、7K 、9K 、12K 和 15K 对于下列的连续存储区的请求：( l ) 12K 、10K 、9K , ( 2 ) 12K 、10K 、15K 、18K 试问：使用首次适应算法、最佳适应算法、最差适应算法和下次适应算法，哪个空闲区被使用？答：( 1 ）空闲分区如图所示答分区号分区长1 2 3 4 5 6 7 8 10K 4K 20K 18K 7K 9K 12K 15K 1）首次适应算法12KB 选中分区 3 ，这时分区 3 还剩 8KB 10KB 选中分区 1 ，恰好分配故应删去分区 1 9KB 选中分区 4 ，这时分区 4 还剩 9KB 2 ）最佳适应算法12KB 选中分区 7 ，恰好分配故应删去分区7 1OKB 选中分区 1 ，恰好分配故应删去分区 1 9KB 选中分区 6 ，恰好分配故应删去分区6 3 ）最差适应算法12KB 选中分区 3 ，这时分区 3 还剩 8KB 。

1OKB 选中分区 4 ，这时分区 4 还剩 8KB 9KB 选中分区 8 ，这时分区 8 还剩 6KB 4 ）下次适应算法12KB 选中分区 3 ，这时分区 3 还剩 8KB 10KB 选中分区 4 ，这时分区 4 还剩 8KB 9KB 选中分区 6 ，恰好分配故应删去分区6 2 ）原始分区情况同上图1 ）首次适应算法12KB 选中分区 3 ，这时分区 3 还剩 8KB 10KB 选中分区 1 ，恰好分配故应删去分区 1 15KB 选中分区 4 ，这时分区 4 还剩 3KB 最后无法满足 18KB 的申请，应该等待2 ）最佳适应算法12KB 选中分区 7 ，恰好分配故应删去分区7 1OKB 选中分区 1 ，恰好分配故应删去分区 1 15KB 选中分区 8 ，恰好分配故应删去分区8 18KB 选中分区4 ，恰好分配故应删去分区4 3 ）最差适应算法12KB 选中分区 3 ， 这时分区 3 还剩 8KB 10KB 选中分区 4 ， 这时分区 4 还剩 8KB 15KB 选中分区 8 ，恰好分配故应删去分区8 最后无法满足18KB 的申请，应该等待4 ）下次适应算法12KB 选中分区 3 ，这时分区 3 还剩 8KB 。

1OKB 选中分区 4 ，这时分区 4 还剩 8KB 15KB 选中分区 8 ，恰好分配故应删去分区8 最后无法满足 15KB 的申请，应该等待5 给定内存空闲分区， 按地址从小到大为：100K 、 500K 、 200K 、 300K 和 600K 现有用户进程依次分别为212K 、417K 、112K 和 426K , ( l ）分别用first-fit 、 best-fit 和 worst-fit 算法将它们装入到内存的哪个分区？( 2 ）哪个算法能最有效利用内存？答：按题意地址从小到大进行分区如图所示分区号分区长1 2 100KB 500KB 3 4 5 200KB 300KB 600KB ( 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 给定段表如下：段号段首址段长0 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 96 给定地址为段号和位移： 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 由于主存大小为 218B，页面尺寸为 1KB ，所以，主存共有256 块所以，块号为 100 （八进制）是合法地址，于是，物理地址为100 （八进制）与位移 1 100 101 110 并接，得到：八进制物理地址001000000 1 100 101 110 = = 201456 （八进制）13 主存中有两个空间区如图所示，0K 15K 125K 现有作业序列依次为： Job1 要求 30K ; Job2 要求 70K ; Job3 要求 50K ；使用首次适应、 最坏适应和最佳适应算法处理这个作业序列，试问哪种算法可以满足分配？为什么？答：首次适应、 最坏适应算法处理这个作业序列可以满足分配，最佳适应算法不行因为后者会分割出无法使用的碎片，浪费内存，从而，不能满足所有作业的内存需求14 设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16 页，每页2048 字节，内存总共有 8 个存储块。

试问逻辑地址至少应为多少位？内存空间有多大？答：逻辑地址 21124，故为 15 位内存大小为23211 = 214B = 16KB 15、在一分页存储管理系统中， 逻辑地址长度为 16 位，页面大小为 4096 字节，现有一。