0KB 操作系统126KB 126KB 256KB 376KB 作业2:56KB 432KB 512-1KB
（3）作业4、5进入内存后，内存的分布情况如下图
0KB 操作系统126KB 126KB 256KB 作业4:156KB 376KB 作业2:56KB 432KB 作业5:80KB
7、某系统采用页式存储管理策略，某进程的逻辑地址空间为32页，页的大小为2KB，物理地址空间的大小是4MB。（1）写出逻辑地址的格式。（2）该进程的页表有多少项？每项至少占多少位？（3）如果物理地址空间减少一半，页表的结构有何变化？
（1）进程的逻辑地址空间为32页，故逻辑地址中的页号需要5位（二进制），由于每页的大小为2KB，因此页内位移须用11位（二进制）表示，这样逻辑地址格式如下图。
15
11 10
页号 页内位移
（2）因为进程的逻辑地址空间为32页，因此该进程的页表项有32项。页表中应存储每页的块号。因为物理地址空间的大小是4MB，4MB的物理地址空间内分成4MB/2KB=2K个块，因此块号部分需要11位（二进制），所以页表中每项占11位。
（3）如果物理地址空间减少一半，页表的页表项数不变，但每一项的长度从11位（二进制）减少到10
0
512-1KB 位（二进制）。
8、某页式存储管理系统，内存的大小为64KB，被分成16块，块号为0、1、2、…、15。设某进程有4页，其页号为0、1、2、3，被分别装入内存的2、4、7、5块，问：（1）该进程的大小是多少字节？（2）写出该进程每一页在内存的起始地址。（3）逻辑地址4146对应的物理地址是多少？
（1）内存的大小为64KB，被分成16块，所以块的大小是64KB/16=4KB。因为块的大小与页面的大小相等，所以页的大小是4KB。该进程的大小是4*￥KB。
（2）因为进程页号为0、1、2、3，被分别装入内存的2、4、7、5。 第0页在内存的起始地址是：2*4KB=8KB； 第1页在内存的起始地址是：4*4KB=16KB； 第2页在内存的起始地址是：7*4KB=28KB； 第3页在内存的起始地址是：5*4KB=20KB。
（3）逻辑地址4146对应的物理地址：4146/4096=1，…，50。逻辑地址4146对应的页号为1，页内位移为50。查找页表，得知页号为1的存储块号为4，所以逻辑地址4146对应的物理地址是：4*4096+50=16434。
9、某段式存储管理系统的段表如下图，请将逻辑地址[0，137]、[1，9000]、[2，3600]、[3，230]转换成物理地址。
段号 0 1 2 段大小 15 KB 8 KB 10 KB 段起址 40KB 80 KB 100 KB （1）对于逻辑地址[0，137]，段号为0，段内位移为137。查段表的项得到该段的段地址为40KB，段长为15KB。由于段号0小于进程的总段数，故段号合法；段内位移137小于段长15KB，故段内地址合法。因此可得到物理地址为：40KB+137B=40960B+137B=41097B。
（2）对于逻辑地址[1，9000]，段号为1，段内位移为9000。查段表的项得到该段的段地址为80KB，段长为8KB。由于段号1小于进程的总段数，故段号合法；段内位移9000大于段长8KB=8192B，因此产生越界中断。
（3）对于逻辑地址[2，3600]，段号为2，段内位移为3600。查段表的项得到该段的段地址为100KB，段长为10KB。由于段号2小于进程的总段数，故段号合法；段内位移3600小于段长10KB，故段内地址合法。因此可得到物理地址为：100KB+3600B=10240B+3600B=10600B。
（4）对于逻辑地址[3，230]，段号为3，段内位移为230。由于段号3大于进程的总段数，故段号不合法，因此产生越界中断。
6 虚拟存储管理
1、试说明缺页中断与一般中断的主要区别？
答：缺页中断与一般中断一样，需要经历保护CPU现场、分析中断原因、转中断处理程序进行处理及恢复中断现场等步骤。但缺页中断是一种特殊的中断，它与一般中断的区别如下：
（1）在指令执行期间产生和处理中断。通常CPU是在一条指令执行之后去检查是否有中断产生，若有便去处理中断；否则继续执行下一条指令。页缺页中断是在指令执行期间发现所要访问的指令或数据不在内存时产生和处理中断。
（2）一条指令执行期间可以产生多次中断。对于一条要求读取多个字节数据的指令，指令中的数据可能跨越两个页面。该指令执行时可以要发生3次中断，一次是访问指令，另外两次访问数据。
2、局部置换和全局置换有何区别，在多道程序系统中建议使用哪一种？
答：局部置换是指当进程在执行过程中发生缺页时，只在分配给该进程的物理块中选择一页换出。全局置换是指在所有用户使用的整个存储空间中选择一个页面换出。
在多道程序系统中建议使用局部置换策略。这样，即使某个进程出现了抖动现象，也不致引起其他进程产生抖动，从而将抖动局限在较小范围内。
3、存储存储器的特征是什么？虚拟存储器的容量受到哪两个方面的限制？ 答：虚拟存储器的特征有以下几方面。（1）离散性，指进程不必装入连续的内存空间，而是“见缝插针”。（2）多次性，指一个进程的程序和数据要分多次调入内存。（3）对换性，指进程在运行过程中，允许将部分程序和数据换进、换出。（4）虚拟性，指能从逻辑上扩充内存容量。
虚拟存储器的容量主要受计算机的地址长度和外存容量的限制。
4、已知页面走向是1、2、1、3、1、2、4、2、1、3、4，且进程开始执行时，内存中没有页面，若该进程分配两个物理块，当采用以下算法时的缺页率是多少？（2）先进先出置换算法。（2）假如有一种页面置换算法，它总是淘汰刚使用过的页面。
答：（1）根据题中页面走向，采用先进先出置换算法时的页面调度情况如下表 页面走向 物理块1 物理块2 缺页 1 1 缺 2 1 2 缺 1 3 3 2 缺 1 3 1 缺 2 2 1 缺 4 2 4 缺 2 1 1 4 缺 3 1 3 缺 4 4 3 缺 从表中可看出，页面引用11次，缺页9次，所以缺页率为9/11=81.8%。 （2）根据题中给定页走向，假如有一种页面置换算法，它部是淘汰刚使用过的页面时的页面调度情况如下表 页面走向 物理块1 物理块2 缺页 1 1 缺 2 1 2 缺 1 3 3 2 缺 1 1 2 缺 2 4 1 4 缺 2 1 2 缺 1 3 3 2 缺 4 4 2 缺 从表中可看出，页面引用11次，缺页8次，所以缺页率为8/11=72.7%
5、在请页式存储管理系统中，使用先进先出页面置换算法，会产生一种奇怪的现象，分配给进程的页面数越多，进程执行时的缺页次数反而升高。试举例说明这一现象。
答：如果一个进程的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，若给该进程分配3个物理块，其页面调度情况如下表 页面走向 物理块1 物理块2 物理块3 缺页 4 4 缺 3 4 3 缺 2 4 3 2 缺 1 1 3 2 缺 4 1 4 2 缺 3 1 4 3 缺 5 5 4 3 缺 4 3 2 5 2 3 缺 1 5 2 1 缺 5 从表中可看出，页面引用12次，缺页9次。
若给该进程分配4个物理块，其页面调度情况如下表 页面走向 物理块1 物理块2 物理块3 物理块4 缺页 4 4 缺 3 4 3 缺 2 4 3 2 缺 1 1 3 2 1 缺 4 3 5 5 3 2 1 缺 4 5 4 2 1 缺 3 5 4 3 1 缺 2 5 4 3 2 缺 1 1 4 3 2 缺 5 1 5 3 2 缺
从表中可看出，页面引用12次，缺页10次。
由上例可看出，对于以上页面走向，当分配给进程的物理块数从3变成4时，缺页次数不但没有下降，反而从9次增加到10次。
6、某请页式系统中，页的大小为100字，一个程序的大小为1200字，可能的访问序列如下：10、205、110、40、314、432、320、225、80、130、272、420、128（字），若系统采用LRU置换算法，当分配给该进程的物理块数为3时，给出进程驻留的各个页面的变化情况、页面淘汰情况及缺页次数。
答：由于页的大小为100字，因此访问序列10、205、110、40、314、432、320、225、80、130、272、420、128对应的页号是0、2、1、0、3、4、3、2、0、1、2、4、1。给该进程分配3个物理块，采用LRU置换算法，其页面调度情况如下表 页面走向 物理块1 物理块2 物理块3 缺页 0 0 缺 2 0 2 缺 1 0 2 1 缺 0 3 0 3 1 缺 4 0 3 4 缺 3 2 2 3 4 缺 0 2 3 0 缺 1 2 1 0 缺 2 4 2 1 4 缺 1 从表中可看出，被淘汰的页号分别是2、1、0、4、3、0，共缺页9次。
7、在一个采用局部置换策略的请求页式系统中，分配中给进程的物理块数为4，其中存入的4个页面的情况如下表 页号 0 1 2 3 存储块号 2 1 0 3 加载时间 30 160 10 220 访问时间 160 157 162 165 访问位 0 0 1 1 修改位 2 0 0 1 当发生缺页时，分别采用下列页面置换算法时，将置换哪一页，并解释原因。（1）OPT（最佳）置换算法；（2）FIFO（先进先出）置换算法；（3）LRU（最近最少使用）算法；（4）CLOCK置换算法
答：（1）OPT转换算法是选择永久不用的页或长时间不用的页，将其换出，题目中没有给出页面的将来走向，所以无法判断将转换哪一页。
（2）FIFO转换算法是选择最先装入内存的页面，将其换出。从表中可知，应考察的是页面的加载时间，加载时间最小的是10，此最先装入内存的是第2页。
（3）LRU算法是选择最近最久没有被访问的页面，将其换出。从表中可知，应考察的是页面的访问时间，访问时间最小的是157，应此最近最久没有被访问的页面是第1页。
（4）CLOCK转换算法是LRU算法的变种，它首先选择访问位和修改位均为0的一页，将其换出，从表中可知，满足该条件的是第1页。
8、某虚拟存储器的用户空间有32个页面，每页1KB，内存的大小为16KB，假设某时刻系统为用户的第0、1、2、3页分配的物理块号是5、10、4、7。而该用户进程的长度是6页，试将以下十六进制的虚拟地址转换成物理地址。（1）0A5C；（2）103C；（3）257B；（4）8A4C
答：（1）虚拟地址0A5C的二进制是0000101001011100，由页大小为1KB，可知页号为000010（二进制），即2（十进制），从页表中得到其物理块号为4（十进制），即000100（二进制）。与页内位移1001011100（二进制）拼接得到物理地址为0001001001011100（二进制），即125C（十六进制）。
（2）虚拟地址103C的二进制是0001000000111100，页大小为1KB，可知页号为000100（二进制），即4（十进制），由题目可知，该用户进程的长度是6页，因此页号合法。但页表中没有第4页，说明该页未装入内存，故主生缺页中断。
（3）虚拟地址257B的二进制是0010010101111011，由页大小为1KB，可知页号为001001（二进制），即9（十进制），由题目可知，该用户进程的长度是6页，因此页号非法，产生越界中断。
（4）虚拟地址8A4C的二进制是1000101001001100，由题目可知，用户空间有32个页面，每页1KB，即虚拟地址空间为32KB，而地址1000101001001100超出32KB，因此地址8A4C错误。
9、在请页式存储管理系统中，页面大小是100字节，有一个50*50的数组按行连续存放，每个整数占2字节。将数组初始化的程序如下：
程序A： 程序B： int i,j; int i,j;
int a[50][50]; int a[50][50]; for(i=0;i<50;i++) for(j=0;j<50;j++) for(j=0;j<50;j++) for(i=0;i<50;i++) a[i][j]=0; a[i][j]=0;
若在程序执行过程中内存中只有一个页面用来存放数组的信息，试问程序A和程序B执行时产生的中断次数分别是多少？
答：由题可知，数组a中有50*50＝2500个整数，每个整数占2字节，数组共需要2*2500＝5000字节。而页面的大小是100字节，则数组占用的空间为5000/100＝50页。
对程序A：由于数组是按行存放的，而初始化数组的程序也是按行进行初始化的。因此当缺页后调入一页，位于该页的所有数组元素全部进行初始化，然后再调入另一页。所以缺页的次数为50次。
对程序B：由于数组是按行存放的，而初始化数组的程序却是按列进行初始化的，因此当缺页后调入的一页中，位于该页上的数组元素只有1个。所以程序B每访问1个元素产生一次缺页中断，则访问整个数组将产生2500次缺页。
7 设备管理
1、数据传送控制方式有哪几种？试比较它们的优缺点。
答：数据传送控制方式有程序直接控制方式、中断控制方式、DMA控制方式和通道控制方式。
程序直接控制方式是由用户直接控制数据从CPU（或内存）到外部设备之间的传送，它的优点是控制简单，不需要多少硬件的支持。它的缺点是CPU与外设只能串行工作；多台外设之间也是串行工作；无法发现和处理由于设备和其他硬件所产生的错误。
中断控制方式是通过向CPU发送中断的方式控制外部设备和CPU之间的数据传送。它的优点是大大提高了CPU的利用率且能支持多道程序与外设的并行操作。它的缺点是：由于数据缓冲寄存器较小，数据传送时必然导致中断次数较多，从而占用的大量的CPU时间；当外部设备较多时，由于中断次数的急剧增加，可能导致CPU无法响应中断而出现中断丢失现象。
DMA控制方式是在外部设备和CPU之间开辟直接的数据交换通路进行数据传送。它的优点是除了在数据块传送的开始时需要CPU的启动指令，在整个数据块传送完毕时需要发送中断通知CPU进行中断处理之外，不需要CPU的频繁干预。它的缺点是在外部设备越来越多的情况下，多个DMA控制器的同时使用，会引起内存地址的冲突并使得控制过程进一步复杂化。
通道方式是使用通道来控制CPU（或内存）和外部设备之间的数据传送，即使传送多个数据块，也不必需要CPU的干预。通道是一个独立于CPU的专管输入/输出的处理机，它控制外设与内存直接进行数据交换。它有自己的通道指令，这些指令由CPU启动，并在操作结束时向CPU发中断信号。该方式的优点是进一步减轻了CPU的负担，增强了计算机系统的并行程序，缺点是拉架了额外的硬件，造价昂贵。
2、何谓设备的独立性？如何实现设备的独立性？
答：设备的独立性是指应用程序独立于具体使用的物理设备。此时，用户使用逻辑设备名申请使用某类物理设备。当系统中有多台该类型设备时，系统可将其中的任意一台分配给请求进程，而不局限于某一台指定的设备。这样，可以显著地改善资源的利用率及可适应性。设备独立性使用户程序独立于设备的类型。如进行输出时，既可以使用显示终端，也可以使用打印机。有了这种独立性，就可以很方便地进行输入/输出重定向。
为了实现设备独立性，系统必须将应用程序中使用的逻辑设备名映射为物理设备名。为此，系统应为用户建立逻辑设备表（LUT），用来进行逻辑设备到物理设备的映射，其中每个表目中包含了逻辑设备名、物理设备名和设备驱动程序的入口地址三项。当应用程序使用逻辑设备名请求I/O操作时，系统便可以从LUT