存储管理部分练习题
一、选择题：
1、把作业地址空间中使用的逻辑地址变成内存中的物理地址称为（ ）。 A、加载 B、重定位 C、物理化 D、逻辑化 2、虚存的基础是（ ），其基本含义是（ ）。
A、局部性理论 B、代码的顺序执行 C、程序执行时对内存访问不均匀 D、变量的连续访问 E、指令局部性 3、某系统采用基址、限长寄存器保护方法实现存储保护，在这种方法中判断是否越界的判别式为（ ）。 A、0≤被访问的物理地址＜基址寄存器的内容 B、0≤被访问的物理地址≤寄存器的内容 C、0≤被访问的逻辑地址＜限长寄存器的内容 D、0≤被访问的逻辑地址≤限长寄存器的内容 4、最佳适应算法的空白区是（ ）。 A、按大小递增顺序排列的 B、按大小递减顺序排列的 C、按地址由小到大排列的 D、按地址有大到小排列的 5、在页式存储管理中，每当CPU形成一个有效地址(虚地址)时，要查页表，这一工作是由（ ）实现的，操作系统（ ）感知页表的存在。A、硬件自动 B、操作系统 C、查表程序 D、存取控制程序 E、能够 F、不能够 6、具有虚拟存储功能的管理方法包括（ ）。 A、可变分区存储管理 B、页式存储管理 C、段式存储管理 D、段页式存储管理
7、采用（ ）不会产生内部碎片。A、分页式存储管理 B、分段式存储管理 C、固定分区式存储管理 D、段页式存储管理 8、测得某个采用按需调页(Demand-Paging)策略的计算机系统部分状态数据为：CPU利用率20%，用于对换空间的硬盘的利用率97.7%，其他设备的利用率5%，由此断定系统出现异常。此种情况下，（ ）能提高利用率。
A、安装一个更快的硬盘 B、通过扩大硬盘容量，增加对换空间 C、增加运行进程数 D、加内存条，增加物理空间容量 二、填空题：
1、为了支持多道程序运行，存储管理的主要功能应该是（ ）、（ ）、（ ）。 2、虚拟存储器的最大容量是由（ ）决定的。
3、在可变分区存储管理中，分区的保护通常采用（ ）和（ ）两种方式。
4、在分区分配算法中，首次适应算法倾向于优先利用内存中（ ）部分的空闲分区，从而把保留了（ ）部分的大空闲区。 5、再采用请求分页式存储管理的系统中，地址变换过程可能会因为（ ）、（ ）和（ ）等原因而产生中断。 6、所谓系统抖动，指的是（ ）。
7、某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0 1 2 3页分别分配的物理块号为5 10 4 7，那么虚地址0A5CH对应的物理地址是（ ）。 三、判断题：
1、虚地址即程序执行时所要访问的内存地址。
2、交换扩充了主存，因此交换也实现了虚拟存储器。
3、在请求分页系统中，为了实现请调一页的功能，在页表中必须增加二个数据项，它们是中断位I和访问位。 4、为了使程序在主存中浮动，编程时都使用逻辑地址，因此，必须地址变换后才能得到主存的正确地址。 四、问答题：
1、什么叫重定位？动态重定位的特点是什么？
2、在存储管理中，覆盖和对换技术所要解决的是什么问题？各有什么特点？
3、某作业大小为C5FH字节，从内存3A6H字节处开始装载，当作业的相应进程在CPU上运行时： 1)若采用上、下限寄存器保护，寄存器的值各为多少？如何进行保护？2)若采用基址、限长寄存器保护，寄存器的值各为多少？如何进行保护？ 4、分区管理时，主要使用的有关数据结构有哪些？常用哪几种方法寻找和释放空闲区？这些方法各有何优缺点？ 5、用可变式分区分配的存储管理方案中，基于链表的存处分配算法有哪几种？它们的思想是什么？ 6、采用可变分区方时管理主存时，引入移动技术有什么优点？在采用移动技术时应注意哪些问题？
7、某系统采用动态分区存储管理技术，某时刻内存中有三个空闲区：空闲区1(首地址100KB，大小10KB)，2(200KB，30KB)，3(300KB，15KB)，现有如下作业序列：作业1要求15KB，2-16KB，3-10KB。要求：
1)画出该时刻内存分布图；2)用首次适应和最佳适应画出此时自由主存队列结构；3)哪种算法能将该作业序列装入内存？ 8、某个操作系统采用可变分区分配方法管理，用户区主存512KB，自由区可用空区表管理，若分配时采用分配自由区的低地址部分的方案，假设初始时全为空。对于下述申请次序：Req(300KB)、Req(100KB)、Rel(300KB)、Req(150KB)、Req(30KB)、Req(40KB)、Req(60KB)回答：1)采用首次适应(FF)，自由区中有哪些空块？ 2)最佳适应(BF)算法呢？ 3)若再申请90KB呢(BF、FF)？ 9、分页存储管理有效解决了什么问题？其实现原理是什么？ 10、以页式存储管理为例，说明动态地址映射的实现方法。 11、描述动态页式管理的地址变换过程。
12、为什么说请求页时管理可以实现虚拟存储器？
13、分页存储管理中，页表的功能是什么？当系统中的地址空间变的非常大时(如32为地址空间)，会给页表的设计到来什么样的新问题？请给出一种解决方案并分析优缺点。
14、LRU算法的基本思想是什么？有什么特点？给出该算法的流程图。
15、简述LRU、NRU、LFU这三种页面置换算法的思想，并各给出一种可能的实现方案。
16、在一系统中采用分页存储管理，页的大小为4KB，允许用户进程的存储映像最大为16页，物理内存共有512块内存。试问：虚地址寄存器和内存地址寄存器的长度各是多少位？
17、设正在处理器上执行的一个进程的页表如下(十进制，起始页/块号为0)： 虚页号 状态位 访问位 修改位 物理块号 0 1 1 0 4 1 1 1 1 7
2 0 0 0 - 3 1 0 0 2 4 0 0 0 - 5 1 0 1 0 使用字节地址，且页面大小为1024。问1)具有快表的请求页式存储管理系统地址变换过程；2)虚地址5499、2221的物理地址？ 18、一台计算有4个页框如下(时间单位：滴答)，请问NRU、FIFO、LRU和第二次机会算法将替换哪一页？ 页 装入时间 上次引用时间 R(读)位 M(修改)位 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1
19、有一虚存系统，某进程内存占三页，开始时内存为空，执行访问页号序列(1 2 3 4 1 2 5 1 2 3 4 5)后，FIFO、LRU、OPT的缺页次数是多少？
20、在一请求分页系统中，假如系统分配给一个作业的物理块数为3，并且此作业的页面走向为2 3 2 1 5 2 4 5 3 2 5 2，试用FIFO和LRU两种算法分别计算程序访问过程中所发生的缺页次数。
21、纯分页系统和请求分页系统的主要差别是什么？设某请求分页系统中某作业J的页面走向：3 2 1 4 4 5 3 4 3 2 1 5，且主存可有3个块供J使用，试说明FIFO、LRU的缺页次数。
22、某虚拟存储器系统采用FIFO页面淘汰算法时，每一作业可用内存为三页。对页面走向4 3 2 1 4 3 5 4 3 2 1 5，发生多少次缺页？若作业可用内存为四页呢？如何解释上述现象？ 22、某系统采用页式存储管理，并用LFU算法淘汰页面，请问LRU的基本实现方法和原理是什么？若系统发生抖动，如何解决？ 23、在请求分页存储管理方式中，若采用先进先出淘汰算法，会产生一种奇怪的现象：分配给作业的实页越多，进程执行使得缺页率反而升高。试举例说明。 24、现代计算机系统常采用请求页式存储管理方案来管理自己的主存，请图示地址转换过程。假定作业J所涉及页面依次为0 1 0 2 0 1 0 1 2 0，并已知主存中有三个可供作业J使用的空白存储块，试说明FIFO和LRU两种不同页面淘汰算法时的缺页率。 25、在某个采用页式存储管理的系统中，有J1、J2、J3三个作业同驻内存，其中J2有四个页面，被分别装入第3、4、6、8物理块中，假如页面大小1024B，主存容量为10KB，请写出J2得页面映像表；当J2在CPU上运行时，执行到期地址空间第500号处遇到一条传送指令：MOV 2100, 3100。请用地址变换图计算指令中两个操作数的物理地址。
26、在采用页式存储管理的系统中，某作业J的逻辑地址空间为4页(页面大小2048B)，其页表如下： 页号： 0 1 2 3 物理块号：2 4 6 8
试借助地址变换图求出有效逻辑地址4865所对应的物理地址。 27、考虑下列程序：
Var a: Array[1..100, 1..150] of Integer; b: Array[1..150, 1..200] of Integer; c: Array[1..100, 1..200] of Integer; i, j, k: Integer; For i := 1 To 100 Do For j := 1 To 200 Do For k := 1 to 150 Do
c[i,j] := c[i,j] + a[i,k] * b[k,j]
假设矩阵A、B初值已置好，C初始为0，各矩阵均以页为单位连续存放。有假定一个整数占一个字，代码以及变量i,j,k放在其他页面例，并且变量i,j,k的存取不存在缺页问题。主存初始为空，在请求分页存储管理中采用FIFO页面淘汰策略。作业分配10个页面，每个页面100个字给矩阵使用时，执行上面程序的缺页次数是多少？当执行完成程序时，留在内存的这些页面各属于哪些矩阵？当作业分配两个页面每个页面500个字的时候呢？
28、有一矩阵 Var a: Array[1..100, 1..100] of Integer;按先行后列次序存放。在一个虚存系统中，采用LRU淘汰算法，一个进程有3页内存空间，每页可存放200个整数，其中第一页存放程序且假定程序一在内存中。 程序A: For i := 1 To 100 Do For j := 1 To 100 Do a[i,j] := 0;
程序B: For j := 1 To 100 Do For i := 1 To 100 Do a[i,j] := 0;
分别就程序A、B的执行过程计算缺页次数。 29、比较段式管理和页式管理的特点。
30、比较分页与分段存储管理方式的主要差别。
31、分页存储管理与分段存储管理的主要区别是什么？
32、什么是动态链接？用何种内存分配方法可以实现这种链接技术？
33、在虚拟段是存储系统中，引入了段的动态链接，为什么？请给出一种实现方法。
34、有一操作系统采用段式管理，用户区主存512KB，空闲块链入空块表，分配时截取空块表的前半部分。初始时全部空闲，在执行了如下申请、释放操作序列Req(300K) Req(100K) Rel(300K) Req(150K) Req(50K) Req(90K)后：采用最先适配，空块表中有哪些空块？采用最佳适配呢？若随后又申请80K空间呢？这说明什么问题？
35、某系统采用页式(Paging)存储管理策略，拥有逻辑空间32页，每页2KB；拥有物理空间1MB。请1)写出逻辑地址格式；2)
若不考虑权限位等进程页表有多少项(Entry)每项至少多少位？3)若物理空间减少一半，页表结构应作怎样相应的改变？ 36、试述请求页式存储管理的地址变换过程。
37、1)假设某计算机系统NoName共有4页物理地址空间(4Frames)，其操作系统的虚拟地址管理采用“最近最少使用(LRU)”页面置换算法。当一进程依次访问虚地址(又称引用串, Reference String)：1 2 3 4 5 3 4 1 6 7 8 7 8 9 7 8 9 5 4 5 4 2，请计算其缺页次数(Page Fault)。2)LRU需要一定的硬件支持(如计数器、堆栈等)，假设NoName位每页内存配备了一个标志位(Dirty Bit)，请设计一种变形的LRU算法，并且说明：标识位的初始值；何时修改标识位？如何选择应换出的页面？利用此算法说明1)中引用串的缺页次数。 38、在一个使用交换技术(Swapping)的系统中，按地址从低到高排列的内存空洞长度是：10KB 4KB 20KB 18KB 7KB 9KB 12KB 15KB。对下列顺序的段请求：12KB 10KB 15KB 18KB 12KB分别使用首次适配、最佳适配、最差适配和下次适配算法说明空洞的取用情况，并说明暂不能分配情况的处理方法。
39、如果对存储器管理采用这样的措施：当内存中出现大量碎片时，就移动已分配的区域使小的碎片能合并成大的空闲区。移动用户占领的区域时，什么情况下不能移动？为什么？ 40、写出段页式地址变换图。
41、什么式虚拟存储器？它的容量有什么方式确定？请求页式管理中有哪几种比较常用得页面置换算法？在短式存储管理中，段表要包含哪些内容？
42、分区存储管理方案不能实现虚拟的原因是什么？
43、某采用页式存储管理的系统，接受了一个共七页的作业，作业执行时依次访问的页为1 2 3 4 2 1 5 6 2 1 3 7。若主存只有五块空间，当分别用先进先出(FIFO)、最近最少用(LRU)调度算法时，作业执行过程中会产生多少次缺页中断？写出依次产生缺页中断后应淘汰的页。
44、请设计虚拟页式存储管理方案中缺页中断处理过程。
45、某一系统采用请求分页式虚存管理，页面淘汰算法位LRU法，每个作业占15页内存，其中一页用来存放程序，每一页存放200个整形变量。考虑下列程序：
Var a, b: Array [1..20, 1..100] of Integer; i, j: Integer; Begin
For i := 1 To 20 Do For j := 1 To 100 Do a[i,j] := 0; For i := 1 To 20 Do For j := 1 To 100 Do b[i,j] := a[i,j]; End;
设数组a,b均按行存储，程序页已经调入内存，变量i,j存放在程序页中。问此程序会产生多少次缺页中断？运行结束后，留在内存中有哪些页？
46、什么叫碎片？内碎片和外碎片的区别是什么？
47、对于一个利用快表且页表存于内存得分页系统，假定CPU一次访存时间为1μs，访问快表的时间可以忽略不计。
1)如果85%的地址映射可以直接通过快表完成(即快表命中率为85%)，那么进程完成一次内存读写的平均有效时间是多少？ 2)若快表的命中率只有50%呢？ 3)快表命中率对平均有效访问时间有何影响？
48、类似于分页方式中的请求调页那样，分段方式中也可以采用请求式调段策略。试提出一个合理的段替换算法，说明段替换过程中会出现哪些在页面替换过程中不出现的问题。 49、某系统采用请求分页存储管理技术，系统为每个作业分配三个内存快。设某作业进程运行中所访问的信息的页面依次是1 3 4 1 5 2 1 4，试问：在FIFO置换算法下共产生多少次缺页中断？使用LRU呢？ 50、在存储管理技术中，“段”和“页面”非常相似，不同之处是：段是可变大小的页面。在近似的LRU页面置换算法的基础上，定义近似的LRU分段置换算法(要求：给出所需的数据结构和算法的框图描述)。 51、某系统内存分布如下所示： 000K [//////////] OS
020K [\\\\\\\\\\\\\\\\\\\\] Job1 60K 080K [ 60K ] Free A 140K [//////////] Job2 40K 180K [ 20K ] Free B 200K [\\\\\\\\\\\\\\\\\\\\] Job3 30K 230K [ 26K ] Free C 256-1K
1)当Job1、Job3执行完毕，释放它们所占用的内存后，内存空闲区有什么变化？
2)要求在二种不同的放置策略下(首次适应算法和下次适应算法)画出此时的自由主存队列结构。 3)当Job4(70K)要进入系统时，该作业在这二种不同的放置策略下各分配在哪一个空闲区中？
52、某系统采用请求分页存储管理，内存块大小为1024字节，程序字长16位，地址寄存器长18位，有一程序空间大小是5页，页表如下所示： 页号 0 1 2 3 4
块号 1AH 16H
状态 1 1 0 0 0
试计算程序字0455H,1386H的物理地址。 53、关于分页系统，回答如下问题：
1)在页表中，那些数据结构是为实现请调一页而设置的？那些数据项是为实现置换一页而实现的？
2)设某系统为每个作业进程分配3个内存块，某作业进程在运行中访问页面的轨迹是1 4 3 1 6 8 1，且每一页都是按请求装入的。问：在FIFO和LRU置换算法下，产生缺页中段的次数各是多少？ 54、在内存管理中，“内零头”和“外零头”各指的是什么？在固定式分区、可变式分区、页式虚拟存储系统、段式虚拟存储系统，各会存在何种零头？
55、有一矩阵为100行×200列，即int a[100][200];在一个虚存系统中采用LRU算法，系统分配该进程5个页面来存储数据(不包括程序)，设每页可存放200个整数，该程序要对数组进行初始化，数组存储时是按行存放的。试计算下列两个程序各自的缺页次数：
A: for(i=0; i<99; i++) for(j=0; j<199; j++) a[i][j] = i*j; B: for(j=0; j<99; j++) for(i=0; i<199; i++) a[i][j] = i*j;
56、在段式管理和段页式管理中，逻辑地址是如何表示的？从用户角度来看分别为几维空间？ 57、在页式虚存管理系统中，假定驻留集为m个页(所有页初始为空)，在长为p的引用串中具有n个不同页号(n>m)，对于FIFO、LRU两种页面置换算法，试给出页故障数的上限和下限。
58、假定某页式管理系统，主存为64KB，分成16块，编号为0 1 2 3 4 ... 15，设某作业有4页，其页号为0 1 2 3，被分别装在主存的2 4 1 6块，试问：1)该作业的总长度是多少(十进制)字节？ 2)写出该作业每一页在主存中的起始地址。3)若多个逻辑地址[0，100]、[1，50]，[2，0]、[3，60]，计算相应内存地址(括号中第一元素为页号，第二元素页内位移)。 59、在某段式存储管理系统中，有一作业的段表如下： 段号 段长 主存始址 状态 0 200 600 0 1 50 850 0 2 100 1000 0 3 150 - 1
求逻辑地址[0, 65]，[1, 55]，[2, 90]及[3, 20]对应的主存地址(十进制)。
60、在请求页式存储管理系统中，一个作业要依次访问如下页面3 4 2 1 4 3 1 4 3 1 4 5，并采用LRU页面置换策略，设分给该作业的存储块为3，试求出在访问过程中发生缺页中段的次数及缺页率。 61、某一存储管理系统采用可变分区分配方案，设当前内存的空白区如下所示： 空白区号 起始地址 空白区容量 状态 1 5KB 100KB 可用 2 120KB 20KB 可用 3 310KB 256KB 可用 4 1024KB 48KB 可用
现有5个作业J1、J2、J3、J4、J5，它们分别需要内存20KB、42KB、120KB、130KB、18KB的空间，若采用最先适应算法，以怎样的次序可将五个作业装入主存？并给出装入后的空白区表。
63、现有一请求调页系统，其页表保存在寄存器中，若有一个可用的空页或被替换的页未被修改，则它处理一个缺页中断需要8ms；若被替换的页已被修改，则需要20ms；内存存取时间为1μs。假定70%被替换页面被修改过，为保证有效存取时间不超过2μs，可接受的最大缺页中断率是多少？
64、在某系统中，采用固定分区存储管理方式，内存分区(单位：字节)情况如下所示： 0 [////OS///]
40K [ ] 第一分区 70K [ ] 第二分区 180K [ ] 第三分区 512K-1
现有大小为15KB、53KB、110KB的多个作业要求进入内存，试画出他们进入内存后的空间分配情况，并说明主存的浪费率有多大？
65、在可变式分区分配的存储管理方案中，存储分配算法有哪几种？他们的思想是什么？ 66、简述什么是覆盖？什么是交换？覆盖和交换的区别是什么？
67、某请求页式管理系统，用户编程空间有40个页面，每个200H个字节，假定某时刻用户页表中虚页号与物理块号对照表如下所示：
虚页号 0 2 5 17 20 物理块号 5 20 8 14 36
求虚地址0A3CH、223CH分别对应的物理地址。
68、在一个请求页式存储管理系统中，进程p共有5页，访问串3 2 1 0 3 2 4 3 2 1 0 4，试采用LRU置换算法，计算当分配给改进程的页面分别是3和4时，访问过程中发生的缺页次数和缺页率，比较结果并浅析原因。 69、已知主存有256KB容量，其中操作系统占用低地址端的20KB。有下述作业序列：
作业 1 2 3 1 3 4 5 要求 需 80KB 需 16KB 需140KB 完成 完成 需 80KB 需120KB
试用最佳适应算法来处理上述作业序列(在存储分配时，将空白区高地址端分给作业)，并回答下列问题： 1)画出作业1、2、3进入内存后的主存分配情况；
2)画出作业1、3完成后的主存分配情况； 3)画出作业4、5进入内存后的主存分配情况。