1、全国自考操作系统（存储管理）模拟试卷 2 及答案与解析一、单项选择题1 源程序经过编译或者汇编生成的机器指令集合，称为_。（A）源程序（B）目标程序（C）可执行程序（D）非执行程序2 动态重定位是在程序的_中进行的。（A）编译过程（B）连接过程（C）装入过程（D）执行过程3 下面几条中，_是动态重定位的特点。（A）需要一个复杂的重定位装入程序（B）存储管理算法比较简单（C）不需地址变换硬件机构的支持（D）在执行时将逻辑地址变换成内存地址4 固定分区存储管理一般采用_进行主存空间的分配。（A）首次适应分配算法（B）循环首次适应分配算法（C）最优适应分配算法（D）顺序分配算法5 在可变分区管理方式
2、下，在释放和回收空闲区，若已判定“空闲区表第 j 栏中的始址=释放的分区始址+ 长度 ”，则表示_。（A）归还区有上邻空闲区（B）归还区有下邻空闲区（C）归还区有上下邻空闲区（D）归还区无相邻空闲区6 采用单一连续区存储管理时，若作业地址空间大于空闲内存空间，可采用_把不会同时工作的程序段轮流装入主存区执行。（A）对换技术（B）可变分区技术（C）虚拟存储技术（D）覆盖技术7 将作业部分或全部移到外存，以调入其他的作业的技术称为_。（A）覆盖技术（B）对换技术（C）虚拟内存（D）物理扩充8 在虚拟页式存储管理方案中，_完成将页面调入内存的工作。（A）文件读写（B）页面淘汰过程（C）页面工作集处（
3、D）缺页中断处理9 请求分页存储管理的页表表项中的修改位，供_参考。（A）程序修改（B）分配页面（C）淘汰页面（D）调入页面10 进程在执行时发生了缺页中断，中断处理完成后，应执行_。（A）被中断的前一条指令（B）被中断的指令（C）被中断的后一条指令（D）开中断指令11 请求分页存储管理系统的基础是程序运行的_原理。（A）动态性（B）局部性（C）全局性（D）虚拟性12 在不考虑联想寄存器和 Cache 的段页式存储管理中，每次从主存中取指令或取操作数，要访问主存_次。（A）1（B） 2（C） 3（D）413 Linux 存储管理的特点是采用在大小不同的分区中实现_的存储管理技术。（A）可变分区
4、（B）分页（C）分段（D）段页式二、填空题14 在执行时要靠硬件机构实现地址变换的方法是_。15 内存空间的逻辑扩充区是_。16 存储器一般分为_、_和_三个层次。17 在页式虚拟存储管理中，页面调度采用_淘汰算法时总是把使用过后离现在时间最长的那页先调出。18 段页式存储管理系统的逻辑地址可分成如下三个部分：_、_和_。三、简答题19 地址重定位方式分为哪几种?各具有什么特点?20 简述可变分区存储管理算法中的循环首次适应法的分配算法和释放算法，其空闲存储区表是用连续顺序结构实现的。21 比较分别采用数组和链表两种数据结构实现最佳适应算法和最差适应算法的优缺点(要考虑分配和释放两个过程)。2
5、2 覆盖和交换的区别是什么?各有什么优缺点?23 阐述页式管理系统中用位图管理空闲内存页的分配和释放算法的思想。24 一个采取分页的纯页式存储管理和请求页式存储管理是不是都利用了程序运行的局部性原理? 段式存储管理是不是也利用了程序运行的局部性原理?四、综合题25 编写一个 C 程序，用 char*malloc(unsigned size)函数向系统申请一块内存空间(如 size=1000，单位为字节)，用首次适应法addr=(char *)fmalloc(unsigned slze)和ffree(unsigned size，char*addr)模拟 UNIX 的可变分区内存管理，实现对该内存
6、区的分配和释放管理。空闲存储区表可采用结构数组的形式：struct mapunsigned m_size；char*m addr；struct map coremapN；要分配函数 fmalloc 的参数 size 和释放函数 ffree 的参数 size、addr 以键盘命令的形式输入，每次分配和释放后显示空闲存储区表。五、判断题26 采用虚拟存储器技术，程序地址空间的大小不受内存大小的限制。( )（A）正确（B）错误27 在现代操作系统环境中，用户程序能直接访问内存物理地址。( )（A）正确（B）错误28 覆盖对程序员是不透明的。( )（A）正确（B）错误全国自考操作系统（存储管理）模拟试
7、卷 2 答案与解析一、单项选择题1 【正确答案】 B【试题解析】 源程序经过编译或者汇编生成的机器指令集合不一定是可执行程序，如 C 编译用-c 选项对不包括全部的模块的 C 程序编译生成的o 代码是目标程序，但不是可执行程序。【知识模块】 存储管理2 【正确答案】 D【知识模块】 存储管理3 【正确答案】 D【知识模块】 存储管理4 【正确答案】 C【试题解析】 为了节省内存，减少内部碎片，固定分区存储管理一般不采用首次适应分配算法，而采用相对来说较费时的最优适应分配算法。【知识模块】 存储管理5 【正确答案】 B【试题解析】 说明回收的分区尾地址与空闲区表该项登记的空闲区始址相邻。【知识模
8、块】 存储管理6 【正确答案】 D【知识模块】 存储管理7 【正确答案】 B【知识模块】 存储管理8 【正确答案】 D【知识模块】 存储管理9 【正确答案】 C【试题解析】 当需要淘汰一页时，一种典型的算法是，最新读过的页在第一轮的循环检测中不会被选中，最近写过的页在第一、二轮循环检测中不会被选中，这样给予修改过的页两次机会。【知识模块】 存储管理10 【正确答案】 B【试题解析】 一般中断发生在前一条指令刚执行结束，中断处理完成返回后应当执行下一条指令。发生了缺页中断时，由于该指令尚未执行完，中断处理完成后，应继续执行本条指令。【知识模块】 存储管理11 【正确答案】 B【试题解析】 从运行
9、的时间角度来分析，在一段时间内，进程一般不会执行到所有代码段的指令和存取绝大部分数据，它往往相对集中地访问某些区域中的指令和数据，如执行一个循环或访问一个数组时，这就是程序运行的“局部性”原理。正因为有这个特性，就只需要为进程分配远小于全部虚页的内存页面，只装入最近经常要访问的某些区域的指令和数据(称为工作集)，剩余部分就暂时不必装入，等到以后要访问到它们时再调入内存。如果主存较紧张，必要时可将已不大访问的指令和数据调出内存。【知识模块】 存储管理12 【正确答案】 C【试题解析】 段页式存储管理中，每次从主存中取指令或取操作数，先要访问主存中的段表和页表各一次，获得物理地址并装入地址寄存器后
10、，再访问主存中的指令或操作数，总共要访问主存 3 次。【知识模块】 存储管理13 【正确答案】 B【知识模块】 存储管理二、填空题14 【正确答案】 动态重定位【知识模块】 存储管理15 【正确答案】 对换区【知识模块】 存储管理16 【正确答案】 高速缓冲器、主存、外存【知识模块】 存储管理17 【正确答案】 最近未使用(NUR)【知识模块】 存储管理18 【正确答案】 段号、页号、页内偏移【知识模块】 存储管理三、简答题19 【正确答案】 地址重定位有静态重定位方式和动态重定位方式。当需要执行时，由装入程序运行重定位程序模块，根据作业在本次分配到的内存起始地址，将可执行目标代码装到指定内存
11、地址中，并修改所有有关地址部分值的方式称为静态地址重定位。修改的方式是对每一个逻辑地址的值加上内存区首地址(或称基地址)值。静态重定位方式的主要优点是无须硬件地址变换机构支持，因此可以在一般的计算机上实现。其主要缺点是必须给作业分配一个连续的存储区域，在作业的执行期间不能扩充存储空间，也不能在内存中移动，多个作业也难以共享内存中同一程序副本和数据。采用动态重定位方式，将程序装入内存时，不必修改程序的逻辑地址值，程序执行期间在访问内存之前，再实时地将逻辑地址变换成物理地址。动态重定位要靠硬件地址变换机构实现：当程序开始执行时，系统将程序在内存的起始地址送入地址变换机构中的基地址寄存器(BR)中。
12、在执行指令时，若涉及逻辑地址，则先将该地址送入虚地址寄存器(VR)，再将 BR 和 VR 中的值相加后送入地址寄存器(MR) ，并按 MR 中的值访问内存。动态重定位方式的优点是程序在运行期间可以换出和换进内存，以便缓和内存紧张状态；也可在内存中移动，把内存中的碎片集中起来，以充分利用内存空间，这也便于进行多道程序设计。采用动态重定位方式，系统不必给程序分配连续的内存空间，这样就可将程序分成较小的部分，能充分利用内存中的较小片段。动态重定位方式又为信息共享和虚拟存储器的实现创造了条件。【知识模块】 存储管理20 【正确答案】 采用循环首次适应法，可把空闲表设计成顺序结构的循环队列，各空闲区按地
13、址从低到高的次序登记在空闲区的管理队列中，同时需要设置一个起始查找指针，指向循环队列中的一个空闲区表项。循环首次适应法分配时总是从起始查找指针所指的表项开始查找，第一次找到满足要求的空闲区时，就分配所需大小的空闲区，修改表项，并调整起始查找指针，使其指向队列中被分配空闲区后面的那块空闲区。下次分配时就从新指向的那块空闲区开始查找。释放算法基本同首次适应法一样。释放时当需要在空闲队列中插入一个表项或删除一个表项时，根据该表项与起始查找指针之间的相对位置，有可能需要修改指针值，使其仍旧指向原空闲表项。【知识模块】 存储管理21 【正确答案】 实现最佳适应算法时，空闲存储区管理表的组织方法可以采用顺
14、序结构，也可采用链接结构。如采用顺序结构，空闲分区按地址由小到大的顺序登记在表中，分配时需要搜索所有的空闲分区，以在其中挑出一个满足分配大小的最小的分区，其算法的时间复杂度为 O(N)。此种管理结构的释放算法可用顺序结构的首次适应法，不需要插入或删除一个空闲分区表项时，其时间复杂度为 O(1)，否则其算法的时间复杂度为 O(N)。当采用链接结构时，空闲区也可按由小到大的非递减次序排列。分配时总是从最小的第一项开始，这样第一次找到的满足条件的空闲区必定是最合适的。平均而言，只要搜索一半数目的空闲区表项就能找到最佳配合的空闲区，但寻找较大空闲区比较费时，其算法的时间复杂度为 0(N)。采用按存储区
15、大小排序的链接表会降低释放算法的效率。由于空闲区是按大小而不是按地址序号排序的，因此释放回收空闲区时要在整个链表上寻找地址相邻的前、后空闲区，合并后又要插入到合适的位置，因此释放算法比首次适应法和循环首次适应法耗时得多，尽管其算法的时间复杂度也为 O(N)，但其常数 C 要大得多。实现最差适应算法时的空闲存储区表的组织方法一般都是采用按空闲块由大到小排序的链接表，因为如果采用按地址大小的顺序结构，那么该算法与首次适应法和最佳适应法比较起来就没有什么优点可言了。采用按存储区大小顺序排列的链接表的形式，虽然释放一个空闲块时速度较慢，算法的时间复杂度也为 O(N)，但分配时一次查找就行，成功不成功在
16、此一举，算法的时间复杂度为 O(1)，其效率是一切算法中最高的一种，很适合实时系统。【知识模块】 存储管理22 【正确答案】 覆盖对程序员是不透明的。为了节省内存，提高覆盖的效果，用户在编制程序时就要精心安排好程序的覆盖结构，并用覆盖描述语言描述覆盖和覆盖段，覆盖的目的是能够运行更大的程序。同为节省内存，覆盖技术用于一个作业的内部，交换技术则用于不同的作业。交换对程序员是透明的。在采用可变分区存储管理技术的多道程序设计中，当要运行一个高优先的作业而又没有足够的空闲内存时，可按某一算法从主存中换出一个或多个作业，腾出空间装入高优先权的作业，使之能够运行。交换的目的是能够运行更多的程序。其代价是程
17、序在内存和外存之间传输时要花相当的时间。【知识模块】 存储管理23 【正确答案】 在页式管理系统中，由于主存页总数很多，且页的大小相等，故可用位图描述各页的状态。在位图中用一个二进制位对应于主存中的一个页，该位为 0 表示对应页空闲，为 1 表示对应页已分配。在分配空闲页时，可一次取出位图中的一个字，如该字内容非全 1，即表示其中必对应有空闲页，接下来查找该字中位为 0 的位置，从而可确定空闲页的位置。为了提高在位图上检索空闲页的速度，可在表头增设一个起始查找位置指针，位图中在起始查找指针之前的所有字(或字节)都不含有空闲位。释放算法很简单，只要在位图中的对应位上置 0 即可，但如设置了起始查
18、找指针，则可能要修改指针值。【知识模块】 存储管理24 【正确答案】 请求页式存储管理是利用了程序运行的局部性原理。由于一般程序运行具有局部性的特点，故在一段时间内不必将所有的虚页都装入内存，而只要装入当前运行时所需的那些页面，以后当程序要访问新的虚页时，再把该页面装入内存(必要时要淘汰老的页面)。纯页式存储管理由于要把运行的页面全部装入内存，故没有利用程序运行的局部性原理。纯段式存储管理与程序运行的局部性原理也无关，因为它也要把整个段全部装入内存。而段页式(段内再请求分页)也是利用了程序运行的局部性原理。【知识模块】 存储管理四、综合题25 【正确答案】 图 131 为整个程序的基本框架。在
19、程序清单 13-1 中，ffree 函数释放的地址原应为位数较长的虚地址，为了便于调试，本程序采用释放输入的地址为相对空闲区始地址的相对地址，在调用 ffree 函数进行释放时，将它加上空闲区始地址(base_addr)构成绝对地址。同时，在输出空闲分区表时，不仅输出每个分区的绝对地址，也输出相对地址。程序清单 13-1：first_fitc#includestdlibh#include unistdh#includestdio h#includemalloc h*表的定义 *#define N 5structmap *空闲存储区表*unsigned m_size ；char*m_addr；S
20、truct map coremapN；*首次适应的分配函数*char*fmalloc(unsigned size) *由于本函数只管理内存空间的分配，不需要核心代码的 mp 参数*register char*a ；register struct map*bp；for(bp=coremap；bp-m_size；bp+)*从表首开始搜索*if(bp-m size=size)*找到够用的空闲区*a=bp-m_addr；bp-m addr+=size；*修改空闲项起始地址*if(bp-m size-=size)=0) *修改大小*do *该项空闲区全部被分配，删去该项*bp+；(bp-1)- m_ad
21、dr=bp-m_addr；while(bp-1)-m_size=bp-m_size)； return(a)；*返回分配到的空闲区始址*return(0)；*无足够大小的空闲区*首次适应的释放函数*ffree(unsigned size，char*aa)struct map*bp；char*a ，*t；unsignedtt；a=aa；for(bp=coremap；bp-m_addr=abp-m_size!=0；bp+)；if(bp coremap(bp-1)-m_addr+(bp-1)-m-size=a)*情况 1 和 2*(bp-1)-m_size+=size；*情况1，与上空闲区合并*if(
22、a+size=bp-m_addr) *情况 2，又与下空闲区合并*(bp-1)-m_size+=bp- m_size ；while(bp-m_size)*删除下空闲区*bp+；(bp-1)-m_addr=bp-m_addr；(bp-1)- m_size=bp-m_size；elseif(a+size=bp-m_addrbp-m_size)* 情况 3，仅与下空闲区合并*bp- m_addr-=size ，bp-m_size+=size；else *情况 4，插入、一个新空闲区*if(size)dot=bp-m_addr；bp-m_addr=a；a=t ；tt=bp-m_size ；bp-m_s
23、ize=size；bp+ ；while(size=tt)；*coremap 表的初始化程序*initCoremap(base addr，size)char*base addr；unsigned size；*第一项的m_addr 指向用 malloc 申请到的 addr，*第一项的 m_size 等于 malloc 申请的 size，*其他各项清 0*int i；coremap0m_addr=base addr；coremap0m_Size=size；for(i=1；iN； i+)coremapi m_size=0；coremapim_addr=0 ；printcoremap(base addr
24、)*输出表的内容*char*base_addr；int i，zero=0；printf(“SizetR_Addr ititAddrin“)；for(i=0；iN；i+)if(coremapimsize!=0)printf(“coremap d：uttuttun“，i，coremapi m_size，coremapim_addr-base_addr，coremapim_addr)；elseprintf(“coremapd：uittuttun“，i，coremapi m_size ， zero，zero) ；shouHelp()*显示帮助信息*printf(“msize：分配内存 in“)；pri
25、ntf(“fsize addr：释放内存n“) ；printf(“P：打印 coremap 表 in“)；printf(“h ：显示帮助信息 in“)；printf(“q：退出执行in“)；maln()unsigned size ，total_size ；char*base addr*addr，*start_addr，cmdchar；unsigned r_addr；printf(“Please Input malloc size：“) ；scanf(“u“，&total_size)；base addr=malloc(total_size)；initCoremap(base_addr，total
26、_size)；doprintf(“Please Input command，h for helpn“)；do*过滤空白字符*cmdchar=getchar()；while(cmdchar=cmdchar=tcmdchar=n) ；switch(cmdchar)casem：*分配内存空间*scanf(“u“，size)jif(Size 0size=total size)printf(“参数 size 错误n“)；break；start_addr=fmalloc(size) ；if(start_addr=0)printf(“没有足够大的空闲分区n“)； break；casef：*释放分配的内存空间
27、*Scanf(“ uu“ ，&Size，raddr) ；if(r_addr 0r_addr =total_size)printf(“释放空闲区的起始地址超出范围n“)；break；addr=base_addr+r_addr；ffree(size，addr)；break； caseD：*输出 coremap 表*printCoremap(base_addr)；break；caseh ：*输出帮助信息 *shouHelp()；break； caseq：*退出执行*break；detault：printf(“非法命令，显示帮助信息，请键入“h“n“)；continue；while(cmdchar!=
28、q) ； free(base_addr)；*释放用malloc 申请到的内存*return；测试的输入命令和参数如下。 Please Input malloc size：1000*输入向系统申请的整块内存的大小*Please Input command，h for helpm 100m 100m 100f 100 0*测试释放区与后空闲区不相邻，在其前面插入一个空闲区项*m 200m 300m 300*测试没有足够大的空闲区情况*m 200f 100 100*测试释放区与第一个空闲区相邻，与前空闲区合并*f 3005 00*测试释放区与前后空闲区皆不相邻，插入一个空闲区项*f 100 1000
29、*测试释放空闲区的起始地址超出范围的情况*m -100*测试分配存储大小的参数非法 *f 200 300*测试释放区与后空闲区相邻，与后空闲区合并*f 100 200*测试释放区与前、后空闲区皆相邻，三块合并成一块，删除后空闲区项*q*退出运行*上面的测试数据包含了用 fmalloc 分配到空闲内存的情况、没有足够大的空闲区和分配存储大小的参数非法的情况。释放空闲区时包含了释放区与前空闲区相邻、与后空闲区相邻、与前空闲区和后空闲区皆相邻和与前空闲区和后空闲区皆不相邻四种情况，还包括简单的出错判断和处理。如要在释放空闲区时判断更多的错误，程序中还有增加其他的出错判断和处理程序段。测试数据中打印空闲存储区表 coremap的 p 命令和输出结果等部分省略了。【知识模块】 存储管理五、判断题26 【正确答案】 A【知识模块】 存储管理27 【正确答案】 B【知识模块】 存储管理28 【正确答案】 A【试题解析】 覆盖技术就是将一个大程序按程序的逻辑结构划分成若干个程序(或数据) 段，并将不会同时执行，从而就不必同时装入内存的程序段分在一组内，该组称为覆盖段。这个覆盖段可分配到同一个称为覆盖区的存储区域。为了提高覆盖的效果，用户在编制程序时就要精心安排好程序的覆盖结构，并用覆盖描述语言描述覆盖和覆盖段。【知识模块】 存储管理
