初始空闲区状态 60K 130K 20K 装入J1后的空闲区状态 30K 130K 20K 装入J2后的空闲区状态 30K 50K 20K 没有可以满足J3装入条件的空闲区 ③模拟采用首先适应算法的装入过程如下： 初始空闲区状态 60K 130K 20K 装入J1后的空闲区状态 30K 130K 20K 装入J2后的空闲区状态 30K 50K 20K 没有可以满足J3装入条件的空闲区

只有最差适应算法能把全部的作业装入内存。因为其余两种算法划分了相对较小的空闲区形成了碎片。

（4）

将（2）中的后备队列改为：J1:1K, J2:129K, J3:59K, J4:18K。

则最佳适应算法也可以在最后一步装入J4。则三种算法都可以装入全部的作业。 具体的过程不再画出，请参照（2）题的表格。这是因为作业的大小刚好比较合意。

（5）

将（3）中的后备队列改为J1:30K, J2:80K, J3:61K。

则最坏适应算法也无法在最后将J3装入内存。则三种算法都不能装入全部的作业。具体的过程不再画出，请参照（3）题的表格。这是因为作业的大小刚好比较不合意。

21、假定磁盘空闲空间表表明有下列存储块空闲：13、11、18、9和20块。有一个要求为某文件分配10个连续的磁盘块。

（1）如果采用首次适应分配策略，那么将分配哪个块？ （2）如果采用最佳适应分配策略，那么将分配哪个块？ （3）如果采用最差适应分配策略，那么将分配哪个块？ 答:(1)13 (2)11 (3)20

23、为什么要引入虚拟存储器？虚拟存储器是什么？它需要什么硬件支持？根据什么说一个计算机系统有虚拟存储器？怎样确定虚拟存储器的容量？

答：由于软件容量的迅速扩张，有可能一个进程的程序比内存可用空间还要大，这时候该程序就无法运行；另一方面，由于程序的局部性，在进程运行的任一阶段只须使用程序的一部分，如果预先分配所有的内存空间，内存就会被浪费。为了能更有效的支持多道程序设计技术的实现和大型程序运行的需要，所以使用了虚拟存储器的概念，利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，从而增强系统的处

理能力。

虚拟存储器简称虚存，是把内存与外存有机的结合起来使用，从而得到一个容量很大的、速度足够快的“内存”。

虚拟存储器需要的硬件支持是： 系统有一个容量足够大的外存； 系统有一个具有相当容量的内存； 硬件提供实现虚、实地址映射的机制。

如果一个计算机系统硬件上拥有上述的支持条件、操作系统又支持虚拟存储管理，那么这个计算机系统是有虚拟存储器的。

一个虚拟存储器的最大容量（寻址空间）可以用寄存器的位数来确定，因此比如X86体系的计算机寄存器为32位，因此虚拟存储器的最大容量应该为2的32次方字节，即4GB。

26、有一个虚拟存储系统。分配给某进程3页内存，开始时内存为空，页面访问序列如下： 6，5，4，3，2，1，5，4，3，6，5，4，3，2，1，6，5 （1）若采用先进先出页面置换算法(FIFO)，缺页次数为多少？ （2）若采用最近最少使用页面置换算法(LRU)，缺页次数为多少？ （3）若采用最佳页面置换算法算法呢？ 答:

(1):17次 (2):17次 (3)11次

27、有一台计算机含有4个页面，每一页的装入时间，最后一次修改时间以及R与M位的值如下(时间为时钟周期)：

页 装入时间 最后访问时间 R M 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1 （1）NRU应淘汰哪一页 （2）FIFO应淘汰哪一页 （3）LRU应淘汰哪一页

（4）第二次机会应淘汰哪一页 答：NRU应淘汰第0页 FIFO应淘汰第2页 LRU应淘汰第1页 第二次机会应淘汰第0页

29、何谓系统的“抖动”现象？当系统发生“抖动”时，你认为应该采取什么措施来加以克服？

答：在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象为颠簸（或抖动）。 颠簸或抖动产生的最主要的原因是页面置换算法不合理，分配给进程的物理页面数太少。可以考虑改进页面的置换算法。另一方面，程序员编写程序的同时，如果能根据机器寻址的特点，来调整访存指令的执行顺序（例如对大矩阵的操作是先行后列还是先列后行，等）也可以避免抖动的发生。

30、在虚拟页式存储管理中，进程在内外存中的存放有以下两种方法： （1）一部分页面放在内存，其余页面放在外存；

（2）一部分页面放在内存，全部页面放在外存；

试从系统开销的角度分析两种方法各自的优缺点， 并说明页表的差别。

答：第一种方法，一部分页面放内存，其余页面放外存，这样在内存中的页面在外存中不存在副本，第二种方法当前需要的页面放在内存中，全部的页面在外存中都有副本，因此第一种方法比第二种方法占据的存储空间小。但是在将页面移出内存的过程中，对于第一种方法，不管要移出的页面是否被修改过，都必须将其写回磁盘；对第二种方法，如果要移出的页面没有被修改过，那么它在磁盘上的副本已经是最新的了，则不需要写回，调入的页直接覆盖被淘汰的页就行了。因此第二种方法比起第一种方法来，输入输出设备的压力小，调入调出数据和程序段的频率低。

因为第一种方法移出页面时不管页面是否被修改过都得将其写回外存，所以页表中不需要有修改位。所以页表差别在第一种方法的页表不需要有修改位，而第二种方法需要有修改位。

31、有一个虚拟存储系统采用最近最少使用（LRU）页面置换算法，每个程序占3页内存，其中一页用来存放程序和变量i,j（不作他用）。每一页可存放150个整数变量。程序A和程序B如下： 程序A： VAR C:ARRAY[1..150,1..100] OF integer; i,j:integer; FOR i:=1 to 150 DO FOR j:=1 to 100 DO C[i,j]:=0;

程序B： VAR C:ARRAY[1..150,1..100] OF integer; i,j:integer; FOR j:=1 to 100 DO FOR i:=1 to 150 DO C[i,j]:=0; 设变量i,j放在程序页中，初始时，程序及变量i,j已在内存，其余两页为空。矩阵C按行序存放。

（1）试问当程序A和程序B执行完后，分别缺页多少次？

（2）最后留在内存中的各是矩阵C的哪一部分？ 答(1)100次,10000次

(2)程序A运行完后内存两个页面中分别为:

第一页:ARRAY[148,1]到ARRAY[148,100]和ARRAY[149,1]到ARRAY[149,50] 第二页: ARRAY[149,51]到ARRAY[149,100]和ARRAY[150,1]到ARRAY[150,100] 程序B运行完后内存两个页面中分别为:

第一页:ARRAY[148,1]到ARRAY[148,100]和ARRAY[149,1]到ARRAY[149,50] 第二页: ARRAY[149,51]到ARRAY[149,100]和ARRAY[150,1]到ARRAY[150,100]

32、某采用页式虚拟存储管理的系统，接收了一个共7页的作业，作业执行时依次访问的页为1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。若采用最近最少用（LRU）调度算法，作业在得到两块主存空间和四块主存空间时各会产生多少次缺页中断？如果采用先进先出（FIFO）调度算法又会有怎样的结果？ 解：

（1）LRU、两块主存空间：

LRU： 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 页1： 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 页2： 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 × × × × × × × × × × 2 × × × × × × 2 × × 缺页中断18次

（2）LRU、四块主存空间：

LRU： 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 页1： 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 页2： 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 页3： 1 2 3 4 2 1 5 6 6 1 2 3 7 6 3 3 1 2 页4： 1 1 3 4 2 1 5 5 6 1 2 2 7 6 6 6 1 × × × × 2 1 × × 2 1 2 × × × 3 2 × 2 3 6 缺页中断10次

（3）FIFO、两块主存空间：

LRU： 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 页1： 1 2 3 4 2 1 5 6 2 1 1 3 7 6 3 2 1 1 3 6 页2： 1 2 3 4 2 1 5 6 2 2 1 3 7 6 3 2 2 1 3 × × × × × × × × × × 2 × × × × × × 2 × × 缺页中断18次

（4）FIFO、四块主存空间：

LRU： 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 页1： 1 2 3 4 4 4 5 6 2 1 1 3 7 6 6 2 1 1 3 3 页2： 1 2 3 3 3 4 5 6 2 2 1 3 7 7 6 2 2 1 1 页3： 1 2 2 2 3 4 5 6 6 2 1 3 3 7 6 6 2 2 页4： 1 1 1 2 3 4 5 5 6 2 1 1 3 7 7 6 6