20 KiB
内存管理习题
普通内存管理
内存管理基础知识
内存管理内容
例题 下面关于存储管理的叙述中，正确的是()。
$A.$存储保护的目的是限制内存的分配
$B.$在内存为$M$、有$N$个用户的分时系统中，每个用户占用$M/N$的内存空间
$C.$在虚拟内存系统中，只要磁盘空间无限大，作业就能拥有任意大的编址空间
$D.$实现虚拟内存管理必须有相应硬件的支持
解：$A$限制内存的分配是存储保护，所以错误。$B$因为是分时系统，所以同一时间只有一个用户或程序，所以每个用户占有$M$的内存空间，所以错误。选项$C$中编址空间的大小取决于硬件的访存能力，一般由地址总线宽度决定。选项$D$中虚拟内存的管理需要由相关的硬件和软件支持，有请求分页页表机制、缺页中断机构、地址变换机构等。
例题 多进程在主存中彼此互不干扰的环境下运行，操作系统是通过()来实现的。
$A.$内存分配
$B.$内存保护
$C.$内存扩充
$D.$地址映射
解：$B$。多进程的执行通过内存保护实现互不干扰，如页式管理中有页地址越界保护，段式管理中有段地址越界保护。
例题 对主存储器的访问，()。
$A.$以块（即页）或段为单位
$B.$以字节或字为单位
$C.$随存储器的管理方案不同而异
$D.$以用户的逻辑记录为单位
解：$B$。注意这里指存储的访问，所以以字或字节为单位，而不是$D$。
位示图
例题 现有一个容量为$10GB$的磁盘分区，磁盘空间以簇为单位进行分配，簇的大小为$4KB$，若采用位图法管理该分区的空闲空间，即用一位标识一个簇是否被分配，则存放该位图所需的簇为()个。
A.80
B.320
C.80K
D.320K
解：$A$。簇的总数为$10GB/4KB=2.5M$，用一位标识一簇是否被分配，整个磁盘共需要$2.5Mb$，即需要$2.5M\div8=320KB$，因此共需要$320KB\div4KB=80$簇，选$A$。
程序载入过程
例题 在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是()。
$A.$编辑
$B.$编译
$C.$链接
$D.$装载
解：$C$。编译后的程序需要经过链接才能装载，而链接后形成的目标程序中的地址就是逻辑地址，所以是链接的过程中。若问的是完成逻辑地址到物理地址的变换的阶段就是装载。
内存空间分配回收
动态分区分配
例题 在下列动态分区分配算法中，最容易产生内存碎片的是()。
$A.$首次适应算法
$B.$最坏适应算法
$C.$最佳适应算法
$D.$循环首次适应算法
解：$C$。最佳适应算法总是匹配与当前大小要求最接近的空闲分区，但是大多数情况下空闲分区的大小不可能完全和当前要求的大小相等，几乎每次分配内存都会产生很小的难以利用的内存块，所以最佳适应算法最容易产生最多的内存碎片。
页式存储管理
例题 若页面大小$L$为$1KB$，页号$2$对应的内存块号$B=8$，将逻辑地址$A=2500$转换为物理地址$E$。
等价描述：某系统按字节寻址，逻辑地址结构中，页内偏移量占$10$位，页号$2$对应的内存块号$B=8$，将逻辑地址$A=2500$转换为物理地址$E$。
解：按照等价描述，若一个页面的页内偏移量占$10$位，所以页面大小需要$10$位来表示，即页面大小为$2^{10}B=1KB$。
第一步，计算页号和页内偏移量。页号$P=A\div L=2500\div1024=2$，页内偏移量$W=A%L=2500%1024=452$。
第二步，没有越界，其存放的内存块号为$8$。
第三步，物理地址$E=B\times L+W=8×1024+452=8848$。
例题 某计算机主存按字节编址，逻辑地址和物理地址都是$32$位，页表项大小为$4B$。请回答下列问题：
1）若使用一级页表的分页存储管理方式，逻辑地址结构为(页号$20$位,页内偏移量$12$位)，则页的大小是多少字节？页表最大占用多少字节？
2）若使用二级页表的分页存储管理方式，逻辑地址结构为(页目录号$10$位,页表索引$10$位,页内偏移量$12$位)，设逻辑地址为$LA$，请分别给出其对应的页目录号和页表索引的表达式。
3）采用1）中的分页存储管理方式，一个代码段的起始逻辑地址为$0000,8000H$，其长度为$8KB$，被装载到从物理地址$0090,0000H$开始的连续主存空间中。页表从主存$0020,0000H$开始的物理地址处连续存放。请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号，以及代码页面$2$的起始物理地址。
解：
1）因为主存按字节编址，页内偏移量是$12$位，所以页大小为$2^{12}B=4KB$。物理空间为$32$位，需要用足够的页表项来表示，所以页表项数为$2^{32}\div2^{12}=2^{20}$，因此该一级页表最大的大小为$2^{20}\times4B=4MB$。
2）页目录号可表示为$(((unsigned,int)(LA))>>22)&0x3FF$。页表索引可表示为$(((unsigned,int)(LA))>>12)&0x3FF$。
3）首先代码段长度为$8KB$，而一页为$4KB$，所以代码段被分为两页。代码页面$1$的逻辑地址为$0000,8000H$，根据一级页表的结构，前五位表示页号，$0000,8H$表明其位于第$8$个页处，对应页表中的第$8$个页表项，所以第$8$个页表项的物理地址=页表始址＋$8$×页表项的字节数=$0020,0000H+8\times4=0020,0020H$。所以第一个页面的物理地址就是$0020,0020H$，页表项长度为$4B$，所以第二个页面的物理地址就是$0020,0024H$。
程序段被装载到物理地址$0090,0000H$，所以代码页面$1$的物理地址就是$0090,0000H$，而一个页面$4KB=2^12B$，所以地址的后三位是页内偏移量，第二个代码页面物理地址就是倒数第四位加一$0090,1000H$。而前五位就是页框号（逻辑地址就是页号，物理地址就是页框号），所以两个页表的页框号就是对应物理地址的前五位：$00900H$和$00901H$。
例题 页式存储管理允许用户的编程空间为$32$个页面（每页$1KB$），主存为$16KB$。如有一用户程序为$10$页长，且某时刻该用户程序页表见表。
| 逻辑页号 | 物理块号 |
|---|---|
| 0 | 8 |
| 1 | 7 |
| 2 | 4 |
| 3 | 10 |
若分别遇到三个逻辑地址$0AC5H$，$1AC5H$，$3AC5H$处的操作，计算并说明存储管理系统将如何处理。
解：首先对存储地址结构进行分析。逻辑页面$32=2^5$，而每页$1KB$，所以逻辑地址一共为$32\times1KB=2^{15}$，即一共$15$位。而此时主存为$16KB=2^{14}B$，只有$16$个页面，即物理地址一共只有$14$位，逻辑地址和物理地址不等长。而页号即页内偏移量不变，所以低$10$位是页内偏移量，逻辑地址高$5$位是虚页号，物理地址高$4$位是物理块号。
逻辑地址$OAC5H$转换为二进制是$000,1010,1100,0101B$，虚页号为$2=00010B$，映射至物理块号$4$，因此系统访问物理地址$12C5H=01,0010,1100,0101B$。
逻辑地址$1AC5H$转换为二进制是$001,1010,1100,0101B$，虚页号为$6=00110B$，不在页面映射表中，会产生缺页中断，系统进行缺页中断处理。
逻辑地址$3AC5H$转换为二进制是$011,1010,1100 0101B$，页号为$14$，而该用户程序只有$10$页，因此系统产生越界中断。
快表
例题 某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时$1\mu s$，访问一次内存耗时$100\mu s$。若快表的命中率为$90%$，那么访问一个逻辑地址的平均耗时是多少？
解：若快表命中，则只用查找一次快表和一次内存，若快表不命中，则要查找一次快表和两次内存。
所以$=(1+100)\times0.9+(1+100+100)\times0.1=111\mu s$。
若该系统支持快表慢表同时查找，则为$(1+100)\times0.9+(100+100)\times0.1=110.9\mu s$。
例题 下列措施中，能加快虚实地址转换的是()。
Ⅰ增大快表容量
Ⅱ.让页表常驻内存
Ⅲ.增大交换区
$A.$仅Ⅰ
$B.$仅Ⅱ
$C.$仅Ⅰ、Ⅱ
$D.$仅Ⅱ、Ⅲ
解：$C$。虚实地址转换是指逻辑地址和物理地址的转换。增大快表容量能把更多的表项装入快表，会加快虚实地址转换的平均速率；让页表常驻内存可以省去一些不在内存中的页表从磁盘上调入的过程，也能加快虚实地址转换；增大交换区对虚实地址转换速度无影响，因此Ⅰ、Ⅱ正确。
多级页表
例题 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为$2^{10}B$，页表项大小为$2B$，逻辑地址结构为(页目录号,页号,页内偏移量)，逻辑地址空间大小为$2^{16}$页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是()。
A.64
B.128
C.256
D.512
解：因为页面大小为$2^{10}B$，而页表项大小为$2B$，所以一页可以存在$2^9$个页表项。逻辑地址空间为$2^{16}$页，所以一共需要$2^{16}\div2^9=2^7=128$个页面来保存二级页表，所以页目录表中必须包含表项的个数至少为$128$（首级页表项）。
例题 某系统按字节编址，采用$40$位逻辑地址，页面大小为$4KB$，页表项大小为$4B$，假设采用纯页式存储，则要采用()级页表，页内偏移量为()位？
解：因为页面大小为$4KB=2^{12}B$，按字节编址，所以页内偏移量等于页面大小$2^{12}B$。
页号则$=40-12=28$位。
页面大小$2^{12}B$，页表项大小$4B$，则每个页面可用存放$2^{12}\div4=2^{10}$个页表项。
所以各级页表最多包含$2^{10}$个页表项，需要$10$位二进制位才能映射到$2^{10}$个页表项，因此每一级的页表对应页号应该为$10$位，$28$位的页号至少分为三级。
例题 已知系统为$32$位实地址，采用$48$位虚拟地址，页面大小为$4KB$，页表项大小为$8B$。假设系统使用纯页式存储，则要采用()级页表。
A.1
B.2
C.3
D.4
解：$D$。页面大小为$4KB=2^{12}B$，因此页内偏移为$12$位。系统采用$48$位虚拟地址，因此虚页号$48-12=36$位。采用多级页表时，最高级页表项不能超出一页大小。每页能容纳的页表项数为$4KB\div8B=512=2^9$，$36\div9=4$，因此应采用四级页表，最高级页表项正好占据一页空间。$32$位实地址这里是无用条件，因为实地址与物理地址相关，而页表关注的是逻辑地址。
段式存储管理
例题 采用分页或分段管理后，提供给用户的物理地址空间()
$A.$分页支持更大的物理地址空间
$B.$分段支持更大的物理地址空间
$C.$不能确定
$D.$一样大
解：$C$。页表和段表同样存储在内存中，系统提供给用户的物理地址空间为总空间大小减去页表或段表的长度。由于页表和段表的长度不能确定，所以提供给用户的物理地址空间大小也不能确定。
例题 下面的()方法有利于程序的动态链接。
$A.$分段存储管理
$B.$分页存储管理
$C.$可变式分区管理
$D.$固定式分区管理
解：$A$。程序的动态链接与程序的逻辑结构相关，分段存储管理将程序按照逻辑段进行划分，因此有利于其动态链接。其他的内存管理方式与程序的逻辑结构无关。
例题 可重入程序是通过()方法来改善系统性能的。
$A.$改变时间片长度
$B.$改变用户数
$C.$提高对换速度
$D.$减少对换数量
解：$D$。不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的（比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致）。可重入程序主要是通过共享来使用同一块存储空间的，或通过动态链接的方式将所需的程序段映射到相关进程中去，其最大的优点是减少了对程序段的调入/调出，因此减少了对换数量。
内存空间扩充
交换技术
例题 在使用交换技术时，若一个进程正在()，则不能交换出主存。
$A.$创建
$B.I/O$操作
$C.$处于临界段
$D.$死锁
解：$B$。交换技术就是内存紧张时把暂时用不到的程序移动到外存中。进程正在进行$I/O$操作时不能换出主存，否则其$I/O$数据区将被新换入的进程占用，导致错误。不过可以在操作系统中开辟$I/O$缓冲区，将数据从外设输入或将数据输出到外设的$I/O$活动在系统缓冲区中进行，这时系统缓冲区与外设$I/O$时，进程交换不受限制。其中比较模糊的是$C$。只有内核临界区不能被换出，普通临界区可以。
虚拟内存管理
请求分页管理方式
缺页中断机构
例题 若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是()。
Ⅰ.处理越界错
Ⅱ.置换页
Ⅲ.分配内存
$A.$仅Ⅰ、Ⅱ
$B.$仅Ⅱ、Ⅲ
$C.$仅Ⅰ、Ⅲ
$D.$Ⅰ、Ⅱ和Ⅲ
解：$B$。用户进程访问内存时缺页，会发生缺页中断。发生缺页中断时，系统执行的操作可能是置换页面或分配内存。越界错误是编程时访问内存越界，系统内没有越界错误，不会进行越界出错处理。
例题 有一个矩阵int A[100,100]以行优先方式进行存储。计算机采用虚拟存储系统，物理内存共有三页，其中一页用来存放程序，其余两页用于存放数据。假设程序已在内存中占一页，其余两页空闲。若每页可存放$200$个整数，程序$1$、程序$2$执行的过程中各会发生多少次缺页？每页只能存放$100$个整数时，会发生多少次缺页？以上结果说明了什么问题？
\\ 程序1:
for(i=0;i<100;i++)
for(j=0;j<100;j++)
A[i,j]=0;
\\ 程序2:
for(j=0;j<100;j++)
for(i=0;i<100; i++)
A[i,j]=0;
解：缺页与页数无关，与每页数据数量有关。
程序$1$按行优先的顺序访问数组元素，与数组在内存中存放的顺序一致，每个内存页面可存放$200$个数组元素。这样，程序$1$每访问两行数组元素就产生一次缺页中断，所以程序$1$的执行过程会发生$50$次缺页。
程序$2$按列优先的顺序访问数组元素，由于每个内存页面存放两行数组元素，因此程序$2$每访问两个数组元素就产生一次缺页中断，整个执行过程会发生$5000$次缺页。
若每页只能存放$100$个整数，则每页仅能存放一行数组元素，同理可以计算出：程序$1$的执行过程产生$100$次缺页；程序$2$的执行过程产生$10000$次缺页。
以上说明缺页的次数与内存中数据存放的方式及程序执行的顺序有很大关系；同时说明，当缺页中断次数不多时，减小页面大小影响并不大，但缺页中断次数很多时，减小页面大小会带来很严重的影响。
资源利用情况
- $CPU$利用率低，磁盘利用率高：物理内存短缺，反复换入换出，页面抖动。需要增大内存容量，减少多道程序并发数。
- $CPU$利用率低，磁盘利用率低：$CPU$没有充分里利用。增加并非进程数
- $CPU$利用率高，磁盘利用率低：系统正常。
例题 测得某个采用按需调页策略的计算机系统的部分状态数据为：$CPU$利用率为$20%$，用于交换空间的磁盘利用率为$97.7%$，其他设备的利用率为$5%$。由此判断系统出现异常，这种情况()能提高系统性能。
$A.$安装一个更快的硬盘
$B.$通过扩大硬盘容量增加交换空间
$C.$增加运行进程数
$D.$加内存条来增加物理空间容量
解：$D$。用于交换空间的磁盘利用率已达$97.7%$，其他设备的利用率为$5%$，$CPU$的利用率为$20%$，说明在任务作业不多的情况下交换操作非常频繁，因此判断物理内存严重短缺。
例题 假定有一个请求分页存储管理系统，测得系统各相关设备的利用率为：$CPU$的利用率为$10%$，磁盘交换区的利用率为$99.7%$，其他$I/O$设备的利用率为$5%$。下面()措施将可能改进$CPU$的利用率。
Ⅰ.增大内存的容量
Ⅱ.增大磁盘交换区的容量
Ⅲ.减少多道程序的度数
Ⅳ．增加多道程序的度数
Ⅴ.使用更快速的磁盘交换区
Ⅵ.使用更快速的CPU
$A.$Ⅰ、Ⅱ、Ⅲ、Ⅳ
$B.$Ⅰ、Ⅲ
$C.$Ⅱ、Ⅲ、Ⅴ
$D.$Ⅱ、Ⅵ
解：$B$。Ⅰ正确：增大内存的容量。增大内存可使每个程序得到更多的页面，能减少缺页率，进而减少换入/换出过程，可提高$CPU$的利用率。Ⅱ错误：增大磁盘交换区的容量。因为系统实际已处于频繁的换入/换出过程中，不是因为磁盘交换区容量不够，因此增大磁盘交换区的容量无用。Ⅲ正确：减少多道程序的度数。可以提高$CPU$的利用率，因为从给定的条件知道磁盘交换区的利用率为$99.7%$，说明系统现在已经处于频繁的换入/换出过程中，可减少主存中的程序。Ⅳ错误：增加多道程序的度数。系统处于频繁的换入/换出过程中，再增加主存中的用户进程数，只能导致系统的换入/换出更频繁，使性能更差。Ⅴ错误：使用更快速的磁盘交换区。因为系统现在处于频繁的换入/换出过程中，即使采用更快的磁盘交换区，其换入/换出频率也不会改变，因此没用。Ⅵ错误：使用更快速的$CPU$。系统处于频繁的换入/换出过程中，$CPU$处于空闲状态，利用率不高，提高$CPU$的速度无济于事。综上分析：Ⅰ、Ⅲ可以改进$CPU$的利用率。
页面置换算法
例题 考虑页面置换算法，系统有$m$个物理块供调度，初始时全空，页面引用串长度为$p$，包含了$n$个不同的页号，无论用什么算法，缺页次数不会少于()。
A.m
B.p
C.n
D.\min(m,n)
解：$C$。这个题目是对页面置换的基本概念，即最少要置换多少次。首先页面引用串就代表一共要调入$p$个页面，要调入$p$个页面，假设最坏情况所有页面都缺页，就得到缺页的最大值为$p$，所以$p$不可能是缺页的最小值。包含了$n$个不同的页号，所以就一定会缺$n$次页，所以最小值是$n$，即缺页次数一定$\geqslant n$。而对于$m$而言，若$n>m$，则由于初始为空，所以次数$>m$，综合$>n$，若$n<m$，则$m$块肯定用不完，所以全部调入$n$个页面后不会缺页，缺页次数$=n$，综上$C$。
最佳置换算法
先进先出置换算法
最近最久未使用置换算法
例题 导致$LRU$算法实现起来耗费高的原因是()。
$A.$需要硬件的特殊支持
$B.$需要特殊的中断处理程序
$C.$需要在页表中标明特殊的页类型
$D.$需要对所有的页进行排序
解：$D$。最近最久未使用置换算法需要根据调入页面顺序进行排序找到最久未使用的，而$A$是$D$的结果。
抖动
例题 当系统发生抖动时，可以采取的有效措施是()。
I.撤销部分进程
I.增加磁盘交换区的容量
Ⅲ.提高用户进程的优先级
$A.$仅Ⅰ
$B.$仅Ⅱ
$C.$仅Ⅲ
$D.$仅Ⅰ、Ⅱ
解：$A$。在具有对换功能的操作系统中，通常把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。抖动现象是指刚刚被换出的页很快又要被访问，为此又要换出其他页，而该页又很快被访问，如此频繁地置换页面，以致大部分时间都花在页面置换上，导致系统性能下降。撤销部分进程可以减少所要用到的页面数，防止抖动。对换区大小和进程优先级都与抖动无关。
工作集
某进程访问页面的序列： $\cdots,1,3,4,5,6,0,3,2,3,2,t,0,4,0,3,2,9,2,1,\cdots$。
若工作集的窗口大小为$6$，则在$t$时刻的工作集为()。
A.\{6,0,3,2\}
B.\{2,3,0,4\}
C.\{0,4,3,2,9\}
D.\{4,5,6,0,3,2\}
解：$A$。在任一时刻$t$，都存在一个集合，它包含所有最近$k$次（该题窗口大小为$6$）内存访问所访问过的页面。这个集合$w(k,t)$就是工作集。题中最近$6$次访问的页面分别为$6,0,3,2,3,2$，去除重复的页面，形成的工作集为${6,0,3,2}$。