操作系统-第四章作业及解答.doc

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/12＝50%.
其中，出现了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
3
4
5
100KB
500KB
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 算法能最有效利用内存
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