原因而长期处于阻塞状态，或有的程序模块在运行过一次后就不再需要，但它们都仍将继续占用宝贵的内存资源。

采用虚拟存储器的可能性：根据程序的局部性定理，应用程序在执行之前，没有必要全部装入内存，而只需要将那些当前要运行的部分页或段先装入内存即可运行，其余部分可以仍然留在外存。程序在执行时，如果它所访问的页(段)已经调入内存，便可继续执行下去。但如果程序所要访问的页(段)不在内存中(称为缺页或缺段)，此时程序可以利用操作系统提供的请求调页(段)功能，将它们调入内存，以便程序能够继续执行下去。如果内存已满，无法装入新调入的页(段)，则必须利用一定的页(段)置换功能，将内存中暂时不用的页(段)换到外存中，以腾出足够的空间来存放新调入的页(段)，从而保证程序的顺利执行。这样，一个大的程序就可以在较小的内存空间中执行。从用户的角度来看，该系统所具有的内存容量比实际内存容量大了很多。但实际上，用户所看到的大容量存储器是不存在的，只是虚拟的，故把这样的存储器称为虚拟存储器。

(8) 一个计算机系统的虚拟存储器，其最大容量和实际容量分别由什么决定？ 解：

虚拟存储器的最大容量由主存和辅存的容量之和确定。

虚拟存储器的实际容量由指令中表示地址的字长决定，也就是计算机的地址结构决定的。

(9) 描述下列算法：

①首次适应；②最佳适应；③最差适应 解：

最先适应算法又称首次适应算法，该算法要求空闲分区表或空闲分区链按起始地址递增的次序排列。在进行内存分配时，从空闲分区表(链)首开始顺序查找，一旦找到大于或等于所要求内存长度的分区，则结束查找。然后，该算法从该分区中划出所要求的内存长度分配给请求者，余下的空闲分区仍留在空闲分区表(链)中，同时修改其相应的表(链)项。

最佳适应算法要求空闲分区按容量大小递增的次序排列。当用户作业申请一个空闲区时，存储管理程序从空闲分区表(链)首开始顺序查找，当找到第一个满足要求的空闲区时，停止查找。按这种方式为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。如果空闲分区大于作业的大小，则与最先适应算法相同，将减去作业请求长度后的剩余空闲区仍然留在空闲分区表(链)中。

最坏适应算法要求空闲分区按其大小递减的顺序组成空闲分区表(链)。当用户作业申请一个空闲区时，先检查空闲分区表(链)的第一个空闲分区的大小是否大于或等于所要求的内存长度，若空闲分区表(链)的第一项长度小于所要求的大小，则分配失败，否则从该空闲分区中划出与作业大小相等的一块内存空间分配给作业，余下的空闲分区仍然留在空闲分区表(链)中。

(10) 如果内存划分为100KB、500KB、200 KB、300 KB和600 KB(按顺序)，那么，首次适应、最佳适应和最差适应算法各自将如何放置大小分别为215 KB、414 KB、110 KB和430 KB(按顺序)的进程，哪一种算法的内存利用率高？ 解:

见下图，在首次适应和最差适应算法中，最后430KB没有空间分配。由图可知，最佳适应算法的内存利用率高。

(11) 某操作系统采用分区存储管理技术。操作系统占用了低地址端的100KB的空间，用户区从100KB处开始共占用512KB，初始时，用户区全部空闲，分配时截取空闲区的低地址部分作为一个分配区。在执行了如下的申请、释放操作序列后：

作业1申请300KB、作业2申请100KB、作业1释放300KB、作业3申请150KB、作业4申请50KB、作业5申请90KB。

分别画出采用首次适应算法、最佳适应算法进行内存分配后的内存分配图和空闲区队列； ② 若随后又申请80KB，针对上述两种情况会产生什么后果？ 解:

采用首次适应算法、最佳适应算法进行内存分配后的内存分配图和空闲区队列图如下所示。

若随后又申请80KB，只有采用首次适应算法的内存分配还有空间可以分配，分配图如下：

(12) 假设一个有8个1024字节页面的逻辑地址空间，映射到一个有32帧的物理内存： ① 逻辑地址有多少位？ ② 物理地址有多少位？ 解：

逻辑地址有13位；物理地址有15位。

(13) 某虚拟内存的用户编程空间共32页，每页的大小为1 KB，内存为16 KB，假设某时刻系统为用户的第0、1、2、3页分配的物理块为5、10、4、7，而该用户作业的长度为6页，试将16进制的虚拟地址0A5C、093C、1A5C转换成物理地址。 解：

虚拟地址为0A5C,对应的二进制数为：0000 1010 0101 1100。其中，页内偏移量占10位地址码，为25C。页号占6位地址码，为2号页。因第2页存储在4号块中，其基地址为：0001 0000 0000 0000，即十六进制的1000H。这样，其物理地址为十六进制的125C。

虚拟地址为093C，对应的二进制数为：0000 1001 0011 1100。其中，页内偏移量占10位地址码，为13C。页号占6位地址码，为2号页。因第2页存储在4号块中，其基地址为：0001 0000 0000 0000，即十六进制的1000H。这样，其物理地址为十六进制的113C。

虚拟地址为1A5C，对应的二进制数为：0001 1010 0101 1100。页内偏移量占10位地址码，为25C。页号占6位地址码，为6号页。因为该用户作业的长度为6页，最大的页号为5号。因为虚拟地址为1A5C对应的6号页超出了地址范围，所以属于越界。

(14) 覆盖技术和虚拟存储技术有何区别，交换技术和虚拟存储器中使用的调入和调出技术有何区别和联系？ 解:

覆盖技术与虚拟存储技术最本质的不同在于覆盖程序段的最大长度要受内存容量大小的限制，而虚拟存储器中程序的最大长度不受内存容量的限制，只受计算机地址结构的限制。另外，覆盖技术中的覆盖段由程序员设计，且要求覆盖段中的各个覆盖具有相对的独立性，不存在直接联系或相互交叉访问；而虚拟存储技术对用户的程序段之间没有这种要求。

交换技术就是把暂时不用的某个程序及数据从内存移到外存中去，以便腾出必要的内存空间，或把指定的程序或数据从外存读到内存中以允许其运行的一种内存扩充技术。交换技术与虚存中使用的调入/调出技术的主要相同点是：都要在内存与外存之间交换信息。主要区别是：交换技术调入/调出整个进程，因此一个进程的大小要受内存容量大小的限制；而虚存中使用的调入/调出技术在内存和外存之间来回传递的是页面或分段，而不是整个进程，从而使得进程的地址映射具有了更大的灵活性，且允许进程的大小比可用的内存空间大。 (15) 在虚拟页式存储系统中引入了缺页中断，说明引入缺页中断的原因，并给出其实现的方法。 解：

虚拟页式存储系统中，系统允许作业的一部分页面在内存。当系统产生了缺页中断后，操作系统才能将不在内存的页面从外存调入内存。当缺页被调入，使中断恢复，进程就可以继续执行它的程序了。

缺页中断的实现由硬件和软件两部分组成。其实现方法如下：

当CPU执行一条指令时，形成操作数的有效地址。其中的页号部分用来检查页表，看该页是否在内存。如果在内存，则进行地址变换，按变换后的地址取出操作数；如果不在内存，则引起缺页中断，进入缺页中断处理程序。在缺页中断处理程序中，主要的处理为： 1 利用存储器分块表检查实存是否有空闲页面。 2 如果有空闲存储块，则根据页表提供的磁盘地址调入所需的页面，修改页表和分块表后返回。

3 如果没有空闲存储块，则选择一页淘汰掉。若该页被修改过还需写回外存，调入所需的页面。然后修改页表和分块表，返回。 (16) 试述缺页中断与一般中断的主要区别。 解：

程序在执行时，当访问的页面不在内存时，便产生缺页中断，请求操作系统将所缺页调入内存。中断处理程序将把控制转向缺页中断子程序。然后系统执行此子程序，把所缺页面装入主存中。接着处理器将重新执行缺页时打断的指令。缺页中断是一种特殊的中断，也就是说，缺页中断同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤，但与一般的中断相比，它又具有以下不同点：

一般中断是一条指令完成后中断，而缺页中断是在一条指令执行时中断。通常，CPU都是在一条指令执行完之后，才检查是否有中断请求到达。如果有，便去响应中断，否则，继续执行下一条指令。然而，缺页中断则是在指令执行期间，发现所访问的指令或数据不在内存时所产生和处理的。

一条指令执行时可能产生多个缺页中断。如指令可能访问多个内存地址，这些地址在不同的页中。

(17) 假设有下面的段表：

下面逻辑地址的物理地址分别是多少？

① [0,430]； ② [1,12]； ③ [2,500]; ④ [3,400]; ⑤ [4,122]

段 0 1 2 3 4 基址 219 2300 90 1327 1952 长度 600 14 100 580 96 解：

①： 649；②：2312；③：越界；④：1727；⑤：越界

(18) 考虑下面存储访问序列，该程序的大小为460字(以下数字均为十进制数字)： 10、11、104、170、73、309、185、245、246、434、458、364

该页面的大小为100字，该程序的基本可用内存为200字，计算采用FIFO、LRU和OPT置换算法的缺页次数。 解:

因为页面的大小为100字，该程序的基本可用内存为200字，即可用内存为2块。程序的存储访问序列可转换为如下页面访问序列： 1、1、2、2、1、4、2、3、3、5、5、4

采用FIFO、LRU和OPT置换算法的访问序列如下：

由图可知FIFO算法的缺页次数为6次，LRU的缺页次数为7次，OPT的缺页次数为5次。 (19) 有一个矩阵int a[100][100] 以行为先进行存储。有一虚拟存储系统，物理内存共有3