空闲区说明表结构

第四章存储器管理第0节存储管理概述一、存储器的层次结构1、在现代计算机系统中，存储器是信息处理的来源与归宿，占据重要位置。

但是，在现有技术条件下，任何一种存储装置，都无法从速度、容量、是否需要电源维持等多方面，同时满足用户的需求。

实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。

2、各种存储器•寄存器、高速缓存Cache：少量的、非常快速、昂贵、需要电源维持、CPU可直接访问；•内存RAM：若干(千)兆字节、中等速度、中等价格、需要电源维持、CPU可直接访问；•磁盘高速缓存：存在于主存中；•磁盘：数千兆或数万兆字节、低速、价廉、不需要电源维持、CPU 不可直接访问；由操作系统协调这些存储器的使用。

二、存储管理的目的1、尽可能地方便用户；提高主存储器的使用效率，使主存储器在成本、速度和规模之间获得较好的权衡。

(注意cpu和主存储器，这两类资源管理的区别)2、存储管理的主要功能：•地址重定位•主存空间的分配与回收•主存空间的保护和共享•主存空间的扩充三、逻辑地址与物理地址1、逻辑地址(相对地址，虚地址)：用户源程序经过编译/汇编、链接后，程序内每条指令、每个数据等信息，都会生成自己的地址。

●一个用户程序的所有逻辑地址组成这个程序的逻辑地址空间(也称地址空间)。

这个空间是以0为基址、线性或多维编址的。

2、物理地址(绝对地址，实地址)：是一个实际内存单元(字节)的地址。

●计算机内所有内存单元的物理地址组成系统的物理地址空间，它是从0开始的、是一维的；●将用户程序被装进内存，一个程序所占有的所有内存单元的物理地址组成该程序的物理地址空间(也称存储空间)。

四、地址映射(变换、重定位)当程序被装进内存时，通常每个信息的逻辑地址和它的物理地址是不一致的，需要把逻辑地址转换为对应的物理地址----地址映射；地址映射分静态和动态两种方式。

1、静态地址重定位是程序装入时集中一次进行的地址变换计算。

物理地址= 重定位的首地址+ 逻辑地址•优点：简单，不需要硬件支持；•缺点：一个作业必须占据连续的存储空间；装入内存的作业一般不再移动；不能实现虚拟存储。

第一章 存储器管理4.1 存储器的层次结构—存储器应容量大,便宜,速度跟上处理器4.1.1 多级存储器结构通常有三层,细分为六层,如图4-1, 越往上,速度越快,容量越小,价格越贵; 寄存器和主存又称可执行存储器,进程可直接用指令访问,辅存只能用I/O 访问;4.1.2 主存储器与寄存器1.主存储器---内存,保存进程运行时的程序和数据;CPU与外围设备交换的信息一般也依托于主存储器地址空间;为缓和访存速度远低于CPU 执行指令的速度,在计算机系统中引入了寄存器和高速缓存;2.寄存器---与CPU 协调工作,用于加速存储器的访问速度,如用寄存器存放操作数,或用地址寄存器加快地址转换速度等;4.1.3 高速缓存和磁盘缓存1.高速缓存---根据程序执行的局部性原理将主存中一些经常访问的信息程序、数据、指令等存放在高速缓存中,减少访问主存储器的次数,可大幅度提高程序执行速度;2.磁盘缓存---将频繁使用的一部分磁盘数据和信息,暂时存放在磁盘缓存中,可减少访问磁盘的次数;它依托于固定磁盘,提供对主存储器存储空间的扩充,即利用主存中的存储空间,来暂存从磁盘中读/写入的信息;4.2 程序的装入和链接多道程序运行,需先创建进程;而创建进程第一步是将程序和数据装入内存;将源程序变为可在内存中执行的程序,通常都要经过以下几个步骤：编译---若干个目标模块；链接---链接目标模块和库函数,形成装入模块；装入---图 4-2 对用户程序的处理步骤寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU 寄存器主存辅存第一步第二步第三步内存4.2.1 程序的装入——无需连接的单目标模块装入理解装入方式1. 绝对装入方式Absolute Loading Mode ---只适用单道程序环境如果知道程序的内存位置,编译将产生绝对地址的目标代码,按照绝对地址将程序和数据装入内存;由于程序的逻辑地址与实际内存地址完全相同,故不须对程序和数据的地址进行修改;绝对地址：可在编译时给出或由程序员直接赋予;若由程序员直接给出,不利于程序或数据修改,因此,通常是在程序中采用符号地址,然后在编译或汇编时转换为绝对地址;2. 可重定位装入方式Relocation Loading Mode ---适于多道程序环境多道程序环境下,编译程序不能预知目标模块在内存的位置;目标模块的起始地址是0,其它地址也都是相对于0计算的;此时应采用可重定位装入方式,根据内存情况,将模块装入到内存的适当位置,如图4-3 作业装入内存时的情况 ;3.动态运行时装入方式Dynamic Run-time Loading ---适于多道程序环境可重定位装入方式并不允许程序运行时在内存中移动位置;但是,在运行过程中它在内存中的位置可能经常要改变,此时就应采用动态运行时装入方式;动态运行时的装入程序,在把装入模块装入内存后,并不立即把装入模块中的相对地址转换为绝对地址,而是把这种地址转换推迟到程序真正执行时才进行;因此,装入内存后的所有地址都仍是相对地址;问题：程序装入内存后修改地址的时机是什么4.3 连续分配方式4.3.3 动态分区分配——根据进程需要动态分配内存1. 分区分配中的数据结构1 空闲分区表—用若干表目记录每个空闲分区的分区序号、分区始址及分区的大小等数据项;2 空闲分区链--为实现对空闲分区的分配和链接,在每分区起始部分,设置前向指针,尾部则设置一后向指针;为检索方便,在分区前、后向指针中,重复设置状态位和分区大小表目;当分0内存空间区被分配后,把状态位由“0”改为“1”时,前、后向指针失去意义;图 4-5 空闲链结构2. 分区分配算法P1231首次适应算法first-fit —空闲分区链以地址递增次序链接 每次按分区链的次序从头查找,找到符合要求的第一个分区;2 循环首次适应算法—FF 算法的变种从上次找到的空闲分区位置开始循环查找,找到后,修改起始查找指针; 3 最佳适应算法—空闲分区按容量从小到大排序 把能满足要求的、最小的空闲分区分配给作业 4 最坏适应算法——空闲分区按容量从大到小排序 挑选最大的空闲区分给作业使用；5) 快速适应算法—根据容量大小设立多个空闲分区链表3. 分区分配操作1.分配内存请求分区u.size; 空闲分区m.size; m.size-u.size ≤size,说明多余部分太小, 不再切割,将整个分区分配给请求者；否则从该分区中划分一块请求大小的内存空间,余下部分仍留在空闲分区链;如图4-6 内存分配流程;2.回收内存1 回收区与插入点的前一空闲分区F1相邻：合并,修改F1大小;2 回收区与后一空闲分区F2相邻：合并,修改首地址和大小;3 回收区同时与前、后两个分区邻接：合并,修改F1大小,取消F2;4 回收区不邻接：新建表项,填写首地址和大小,并插入链表;如图前向指针N ＋20N 个字节可用后向指针N ＋2图 4-6 内存分配流程4.3.6 可重定位分区分配1．动态重定位的引入例：在内存中有四个互不邻接的小分区,容量分别为10KB 、30KB 、14KB 和26KB;若现有一作业要获得40KB 的内存空间,因连续空间不足作业无法装入;可采用的一种解决方法是：通过移动内存中作业的位置,以把原来多个分散的小分区拼接成一个大分区的方法,称为“拼接”或“紧凑;由于用户程序在内存中位置的变化,在每次“紧凑”后,都必须对移动了的程序或数据进行重定位;图 4-8 紧凑的示意4.3.7 对换即中级调度1. 对换Swapping 的引入(a ) 紧凑前(b ) 紧凑后“活动阻塞”进程占用内存空间；外存上的就绪作业不能进入内存运行;所谓“对换”,是指把内存中暂时不能运行的进程或者暂时不用的程序和数据,调出到外存上,以便腾出足够的内存空间；再把已具备运行条件的进程或所需要的程序和数据,调入内存;对换是提高内存利用率的有效措施;根据对换单位可分为：进程对换、页面对换和分段对换;为了能实现对换,系统应具备以下三方面功能：对换空间的管理、进程的换出与换入2. 进程的换出与换入1进程的换出选择阻塞且优先级最低的进程,将它的程序和数据传送到磁盘对换区上;回收该进程所占用的内存空间,并对该进程的进程控制块做相应的修改;2进程的换入找出“就绪” 但已换出到磁盘上时间最久的进程作为换入进程,将之换入,直至已无可换入的进程;4.4 基本分页存储管理方式前面的连续分配方案会形成许多“碎片”,“紧凑”方法可以解决碎片但开销大;是否允许进程离散装入 离散单位不同,称分页式存储和分段式存储;不具备对换功能称为“基本分页式”,支持虚拟存储器功能称为“请求基本分页式”;4.4.1 页面与页表1. 页面1 页面和物理块---将进程的逻辑地址空间分成若干个大小相等的片,称为页面,并为各页编号;相应地把内存空间分成与页面相同大小的若干个存储块,称为物理块,也同样编号;分配时,将进程中的页装入到物理块中,最后一页经常装不满一块而形成 “页内碎片”;2 页面大小---页面的大小应选择适中;页面太小,内存碎片减小,利用率高；但页表过长,占大量内存;页面较大,页表长度小；但页内碎片大;因此,页面的大小应选择得适中,且页面大小应是2的幂,通常为512 B~8 KB;2. 地址结构分页地址中的地址结构如下：31 12 11 0它含有两部分：页号P12～31位,最多有1M 页和页内位移量W0～11位,每页的大小4KB ； 对某特定机器,其地址结构是一定的;若给定一个逻辑地址空间中的地址为A,页面的大小为L,则页号P 和页内地址d 可按下式求得：MODL A d L A INT P ][=⎥⎦⎤⎢⎣⎡=3. 页表---实现从页号到物理块号的地址映射用户程序0 页1 页2 页3 页4 页5 页…n 页页表内存4.4.2 地址变换机构任务：将逻辑地址转换为物理地址；页内地址变换:因页内地址与物理地址一一对应, 可直接转换；页号变换：页表可实现从逻辑地址中页号到内存中物理块号的变换； 1．基本的地址变换机构a. 页表功能可由一组专门的寄存器实现原理；b. 页表大多驻留内存,系统中只设置一页表寄存器来存放页表在内存的始址和页表长度实际操作；c. 进程未执行时,页表始址和长度存放在PCB 中;执行时才将这两个数据装入页表寄存器中过程;图 4-12 分页系统的地址变换机构2. 具有快表的地址变换机构a. 仅用页表寄存器时,CPU 每存取一数据要两次访问内存页表-地址变换-数据；b. 为提高地址变换速度,可在地址变换机构中增设一具有并行查寻能力的特殊高速缓冲寄存器用以存放当前访问的那些页表项,称为“快表”;c. ->在CPU 给出逻辑地址,将页号P 送入快表 ->页号匹配,读物理块号后送物理地址寄存器->无匹配页号,再访问内存中页表,把从页表项中读出的物理块号送地址寄存器；同时,再将此页表项存入到快表中;->如快表已满,则OS 须找到一换出页表项换出; 为什么增加“快表”为了提高地址变换速度,可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器,又称为“联想寄存器”Associative Memory,或称为“快表 “快表”有何缺点越界中断图 4-13 具有快表的地址变换机构4.5 基本分段存储管理方式4.5.1 分段存储管理方式的引入为什么引入推动内存从固定分配到动态分配直到分页存储,主要动力是内存利用率,而引入分段存储管理方式,主要是为了满足用户和程序员的下述一系列需要：1方便编程---把作业按逻辑关系划分为若干段,每段有自己的名字和长度,并从0开始编址;LOAD 1,A|<D>; STORE 1,B|<C>2 信息共享---段是信息的逻辑单位;为实现共享,存储管理应与用户程序分段的组织方式相适应;3 信息保护---对信息的逻辑单位进行保护,应分段管理;4 动态增长---分段存储能解决数据段使用过程中动态增长;5 动态链接---运行过程中动态调入以段为单位的目标程序;4.5.2 分段系统的基本原理1. 分段作业划分为若干段,如图4-16,每个段用段号来代替段名,地址空间连续;段的长度由逻辑信息长度决定,因而各段长度不等;其逻辑地址由段号段名和段内地址所组成,结构如下： 31 16 15 0该地址结构中,允许一个作业最多有64K 个段,每个段的最大长度为64KB;编译程序能自页表寄存器逻辑地址L 物理地址动根据源程序产生若干个段;2.段表,其中每段占一个表项,中;图4-16 利用段表实现地址映射3.分页和分段的主要区别1 页是信息的物理单位,分页是为提高内存的利用率,是为满足系统管理的需要;段则是信息的逻辑单位,分段是为了能更好地满足用户的需要;2 页的大小固定且分页由系统硬件实现；而段的长度不固定,通常由编译程序根据信息的性质来划分;3 分页的作业地址空间是一维的,程序只需一个地址记忆符；而分段的作业地址空间是二维的,程序员既需给出段名,又需给出段内地址;4.5.3 信息共享可重入代码纯代码:允许多个进程同时访问的代码;绝对不允许可重入代码在执行中改变,因此,不允许任何进程修改它;4.5.4 段页式存储管理方式1.基本原理---,,,4KB;作业空间内存空间子程序段数据段(a)段号(S)段内页号(P)页内地址(W)(b)主程序段图4-21 利用段表和页表实现地址映射4.6 虚拟存储器的基本概念前面各种存储器管理方式共同点：它们要求将一个作业全部装入内存后方能运行,于是出现了下面这样两种情况：1 有的作业很大,其所要求的内存空间超过了内存总容量,作业不能全部被装入内存,致使该作业无法运行;2 有大量作业要求运行,但由于内存容量不足以容纳所有这些作业,只能将少数作业装入内存让它们先运行,而将其它大量的作业留在外存上等待;4.5.1 虚拟存储器的引入1.常规存储器管理方式的特征1 一次性;将作业全部装入内存后方能运行,此外有许多作业在每次运行时,并非其全部程序和数据都要用到;一次性装入,造成了对内存空间的浪费;2 驻留性;作业装入内存后一直驻留,直至运行结束;尽管因故等待或很少运行,都仍将继续占用宝贵的内存资源;现在要研究的问题是：一次性及驻留性在程序运行时是否必需;2.局部性原理早在1968年, Denning.P就曾指出：1 程序执行时,除了少部分的转移和过程调用指令外,在大多数情况下仍是顺序执行的;2 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域,但经研究看出,过程调用的深度在大多数情况下都不超过5;3 程序中存在许多循环结构,这些虽然只由少数指令构成, 但是它们将多次执行;4 程序中还包括许多对数据结构的处理, 如对数组进行操作,它们往往都局限于很小的范围内;局限性主要表现在下述两个方面：1 时间局限性－由于循环操作的存在;如果程序中的指令或数据一旦执行,则不久以后可能再次访问;2 空间局限性－由于程序的顺序执行;程序在一段时间内所访问的地址,可能集中在一定的范围之内;3. 虚拟存储器定义---基于局部性原理程序运行前,仅须将要运行的少数页面或段装入内存便可启动,运行时,如果需要访问的页段尚未调入内存缺页或缺段,用OS提供请求调页段功能调入;如果此时内存已满,则还须再利用页段的置换功能,将内存中暂时不用的页段调至外存,腾出足够的内存空间后,再将要访问的页段调入;所谓虚拟存储器,是指具有请求调入功能和置换功能,能从逻辑上扩充内存容量的一种存储器系统;其逻辑容量由内存容量和外存容量之和所决定,其运行速度接近于内存,成本接近于外存;4.6.3 虚拟存储器的特征1)多次性---一个作业被分成多次调入内存运行,最初装入部分程序和数据,运行中需要时,再将其它部分调入;2)对换性---允许在作业的运行过程中进行换进、换出;换进和换出能有效地提高内存利用率;3)虚拟性---从逻辑上扩充内存容量,使用户所看到远大于实际内存容量;这是虚拟存储器最重要的特征和最重要的目标;4)离散性---是以上三个特性的基础,在内存分配时采用离散分配的方式;备注：虚拟性是以多次性和对换性为基础的,而多次性和对换性又必须建立在离散分配的基础上;4.7 请求分页存储管理方式4.6.1 请求分页中的硬件支持---页表、缺页中断和地址变换请求分页系统是在分页的基础上,增加了“请求调页”和“页面置换”功能,每次调入和换出基本单位都是长度固定的页,实现比请求分段简单;1．页表机制---将用户地址空间中的逻辑地址变换为内存空间中的物理地址,因只将部分调入内存,需增设若干项;在请求分页系统中的每个页表项如下所示：1 状态位P：该页是否已调入内存,供访问时参考;2 访问字段A：记录一段时间内本页被访问的频率,供选择换出页时参考;3 修改位M：页在调入内存后是否被修改过,供置换页面时参考;4 外存地址：指出该页在外存上的地址,即物理块号,供调入该页时参考;4.7.2 内存分配策略和分配算法1.最小物理块数的确定是指能保证进程正常运行所需的最小物理块数,当系统为进程分配的物理块数少于此值时,进程将无法运行;进程应获得的最少物理块数与计算机的硬件结构有关;对于某些简单的机器,所需的最少物理块数为2,分别用于存放指令和数据,间接寻址时至少要有三块;对于某些功能较强的机器,因其指令本身、源地址和目标地址都可能跨两个页面,至少要为每个进程分配6个物理块,以装入这些页面;2. 物理块的分配策略请求分页系统的两种内存分配策略：即固定和可变分配策略；两种置换策略：即全局置换和局部置换;可组合出以下三种策略;1 固定分配局部置换Fixed Allocation, Local Replacement--每进程分配一定数目的物理块,在整个运行期间都不再改变,换入换出都限于这些物理块;每个进程物理块难以确定,太多太少都不好2 可变分配全局置换Variable Allocation, Global Replacement --每进程分配一定数目的物理块,OS 保持一空闲物理块队列;进程缺页时,摘下一空闲块,并将该页装入;3 可变分配局部置换Variable Allocation, Local Replacemen －－每进程分配一定数目的物理块;进程缺页时,只允许从该进程内存页中选出一页换出;若缺页中断频繁,再为该进程分配若干物理块,直至缺页率减少；若缺页率特低,则减少该进程的物理块数,应保证缺页率无明显增加;3. 物理块分配算法1 平均分配算法－－将所有可供分配的物理块,平均分配给各个进程; 例如,有100个物理块,5个进程,每进程可分20个物理块;未考虑到各进程本身的大小;2 按比例分配算法－－根据进程的大小按比例分配物理块;共n 个进程,每进程页面数为si,则页面数的总和为：设可用的物理块为m,每进程分到的物理块数为bi,有：3 考虑优先权的分配算法－－为了照顾重要、紧迫的作业尽快完成,为它分配较多的空间;通常采取：把可供分配的物理块分成两部分：一部分按比例分给各进程；另一部分根据优先权分给各进程;有的系统是完全按优先权来分配;4.7.3 调页策略1. 何时调入页面1 预调页策略缺页前 ：页面存放连续,用预测法一次调入多个相邻页,预测成功率仅为50％;2 请求调页策略缺页时：运行中,发现不在内存,立即请求,由OS 调入;2. 从何处调入页面请求分页系统中外存分为两部分：文件区和对换区;这样,当发生缺页请求时,系统应从何处将缺页调入内存：1 系统拥有足够的对换区,可以全部从对换区调入所需页面;在进程运行前,须将有关的文件拷贝到对换区;2 系统缺少足够的对换区,这时凡是不会被修改的文件,都直接从文件区调入,由于它们未被修改而不必换出;但对于可能被修改的部分,换出时调到对换区,以后需要时,再从对换区调入;3 UNIX 方式;凡是未运行过的页面,都应从文件区调入；曾运行过但已换出的页面,放在∑==ni iS S 1m SS b ii ⨯=对换区,下次应从对换区调入;4.8 页面置换算法当进程运行时,所访问的页面不在内存而需要将他们调入内存,但内存无空闲时,需要选择一页面换出到对换区,选择算法即页面置换算法;算法评价：页面置换频率低,调出页面将不会或很少访问;4.8.1 最佳置换算法和先进先出置换算法1. 最佳Optimal 置换算法由Belady 于1966年提出的一种理论上的算法;原理：其所选择的被淘汰页面,将是以后永不使用的, 或是在最长未来时间内不再被访问的页面;特点：通常可获得最低的缺页率,但由于进程运行不可预知而无法实现,用来评价其他算法;假定系统为某进程分配了三个物理块,并考虑有以下的页面号引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1进程运行时,先将7,0,1三页装入内存;当进程要访问页面2时,将会产生缺页中断,此时OS 根据最佳置换算法,将选择页面7予以淘汰;共发生6次页面置换;图 4-25 利用最佳页面置换算法时的置换图 2. 先进先出FIFO 页面置换算法---总是置换最先进入内存的页面;用FIFO 算法共发生12次页面置换;该算法与进程的实际运行规律不相符,有些页面经常被访问全局变量,常用函数;图 4-26 利用FIFO 置换算法时的置换图4.8.2 最近最久未使用Least Recently Used LRU 置换算法1. LRU置换算法 ---在无法预测各页面将来使用情况下,利用“最近过去”作为“最近将来”的近似选择最近最久未使用的页面予以淘汰;用LRU 算法共发生9次页面置换;引用率70770170122010320304243230321201201770101页框(物理块）203图 4-27 LRU 页面置换算法2. LRU 置换算法的硬件支持LRU 算法比较好,但为了快速知道哪一页是最近最久未使用的页面,需要硬件支持：寄存器或栈;1 寄存器为了记录某进程在内存中各页的使用情况,须为每个页面配置一个移位寄存器,可表示为：原理：进程访问某物理块时,先将寄存器的Rn-1位设成1;此时,定时信号将每隔一定时间将寄存器右移一位;若将n 位寄存器的数看做是一整数,那么,具有最小数值的寄存器所对应的页面,就是最近最久未使用的页面;例：某进程在内存中有8个页面,为每页面配置一8位寄存器时的LRU 访问情况,如图4-28图 4-28 某进程具有8个页面时的LRU 访问情况2 栈--利用栈来保存当前使用的各页面的页面号;原理：每当进程访问某页面时,便将该页面的页面号从栈中移出,将它压入栈顶;因此,栈顶始终是最新被访问页面的编号,而栈底则是最近最久未使用页面的页面号;假定现有一进程所访问的页面的页面号序列为：4,7,0,7,1,0,1,2,1,2,6随着进程的访问,栈中页面号的变化情况如图4-29所示;在访问页面6时发生了缺页,此时页面4是最近最久未被访问的页,应将它置换出去;LRU 算法较好,但要求较多硬件支持, 实际使用接近LRU算法－Clock 算法;图引用率70770170122010323104430230321013201770201页框2304204230230127127011474074704170401741074210741207421074621074-29 用栈保存当前使用页面时栈的变化情况。

操作系统原理及应用试题附答案第一部分选择题一、单项选择题（本大题共4小题，每小题2分，共8分）1、从静态角度来看，进程由__________、数据集合、进程控制块及相关表格三部分组成。

（）A、JCB B、PCB C、程序段 D、I/O缓冲区2、请求页式管理方式中，首先淘汰在内存中驻留时间最长的帧，这种替换策略是_____.（）A、先进先出法（FIFO） B、最近最少使用法（LRU） C、优先级调度 D、轮转法3、文件安全管理中，___________安全管理规定用户对目录或文件的访问权限。

（）A、系统级 B、用户级 C、目录级 D、文件级4、排队等待时间最长的作业被优先调度，这种算法是___________。

A、优先级调度 B、响应比高优先 C、短作业优先D、先来先服务第二部分非选择题二、填空题（本大题共16小题，每小题1分，共16分）5、常规操作系统的主要功能有：_处理机管理_、存贮管理、设备管理、文件管理以及用户界面管理。

6、操作系统把硬件全部隐藏起来，提供友好的、易于操作的用户界面，好象是一个扩展了的机器，即一台操作系统虚拟机。

7、进程管理的功能之一是对系统中多个进程的状态转换进行控制。

8、逻辑_文件是一种呈现在用户面前的文件结构。

9、操作系统中实现进程互斥和同步的机制称为同步机构_。

10、内存中用于存放用户的程序和数据的部分称为用户区（域）。

11、存贮器段页式管理中，地址结构由段号、段内页号和页内相对地址三部分组成。

12、在操作系统中，通常用户不使用设备的物理名称（或物理地址），而代之以另外一种名称来操作，这就是逻辑设备名。

13、在操作系统中，时钟常有两种用途：报告日历和时间，对资源使用记时。

14、库文件允许用户对其进行读取、执行，但不允许修改.15、程序接口接受用户对系统服务和资源的请求后，把它们转告给操作系统的资源管理程序。

16、作业控制块是在作业创建时建立，直到作业完成时撤消。

17、多处理器系统是指含有2个及以上的CPU的计算机系统。

操作系统习题（附参考答案）一、单选题（共100题，每题1分，共100分）1、下列存储器中，速度最快的是（）。

A、内存B、寄存器C、CacheD、磁盘正确答案：B2、时钟中断事件属于（）中断事件。

A、程序B、自愿性C、外部D、输入/输出正确答案：C3、可变分区存储管理系统中，若采用最佳适应分配算法，“空闲区表”中的空闲区可按（）顺序排列。

A、大小从大到小B、大小从小到大C、地址从大到小D、地址从小到大正确答案：B4、从静态的角度看，下列选项中哪一个是进程必须拥有而程序所没有的？（）A、常量数据B、全局变量C、进程控制块D、代码正文正确答案：C5、（）不是管程的组成部分。

A、对局部于管程内的数据结构设置初始值的语句B、对管程内数据结构进行操作的一组过程C、局部于管程的共享数据结构D、管程外过程调用管程内数据结构的说明正确答案：D6、下列关于父进程和子进程的叙述中，正确的是（）。

A、子进程执行完了，父进程才能执行B、父进程创建了子进程，因此父进程执行完了，子进程才能执行C、撤销子进程时，应该同时撤销父进程D、撤销父进程时，应该同时撤销子进程正确答案：D7、某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。

该系统可能会发生死锁的K的最小值是（）。

A、3B、4C、2D、5正确答案：B8、分页虚拟存储管理系统中，若采用FIFO页面置换算法，则当分配的物理页面数增加时，缺页中断的次数（）。

A、减少B、可能增加也可能减少C、增加D、不变正确答案：B9、产生内存抖动的主要原因是（）。

A、内存空间太小B、CPU运行速度太慢C、CPU调度算法不合理D、页面置换算法不合理正确答案：D10、（）存储管理兼顾了段式在逻辑上清晰和页式在存储管理上方便的优点。

A、分页B、段页式C、可变分区D、分段正确答案：B11、发生死锁的必要条件有四个，要预防死锁的发生，可以破坏这四个必要条件，但破坏（）条件是不太实际的。

实习二 主存空间的分配和回收一、实习内容模拟主存空闲空间的表示方法，以及模拟实现主存空间的分配和回收。

二、实习目的通过本实习帮助理解在不同的存储管理方式下应怎样进行存储空间的分配和回收。

三、实习题目在可变分区管理方式下采用首次适应算法实现主存分配和回收。

假定内存大小为128K 。

空闲区说明表格式为：起始地址——指出空闲区的起始地址；长度——一个连续空闲区的长度；状态——有两种状态，一种是“未分配”状态，另一种是“空表目”状态。

本实习我用FBT 实现，并且采用首次适应算法FF 分配内存。

四、程序中所使用的符号说明和数据结构struct FBT自由块表结构体{int startdress; 自由块表中一个表项的始地址 int size; 自由块表中的一个表项的大小 int processid; 这个表项所对应的进程号 int state; 这个表项的状态struct FBT *next;指向下一个自由块表结构体}；struct FBT *create() 建立自由块表子函数 struct FBT *distribute(struct FBT *head)分配内存空间子函数struct FBT *callback(struct FBT *head) 回收内存空间子函数回收内存有下列4种情况，在程序中用条件语句实现：void print(struct FBT *head)显示自由块表内容子函数void main()主函数五、流程图… 进程i 回收区 进程j … …空闲区 回收区 进程j …… 进程i 回收区 空闲区 … … 空闲区 回收区 空闲区 …开始tail=head打印这个结点tail==null结束tail=tail->next;NY将余下的空闲内存设为一个空闲区间返回头指针head=null将第一个内存分区分配给操作系统申请一个新的内存区间q申请一个新的内存区间p链表初始化流程图显示FBT 流程图开始输入要申请的进程号和内存大小neededsizetail==null此分区未分配且足够大tail==0&&tail->size>=neededsize分区大小大于申请大小Tail->size>neededsize申请一个新结点P p->size=neededsize;p->state=1;大小刚刚等于申请内存大小tail->state=1;tail->processid=id;指向下一个结点pretail=tail tail=tail->next;返回头指针显示没有足够的内存空间够分配修改所剩分区的大小和起始地址tail->size=tail->size-neededsize;tail->startdress=tail->startdress+neededsize;将P插入到链表中NYYYNN分配内存子函数流程图开始输入要回收的进程号id显示没有此进程tail==nulltail->processid==id;tail->next==null;pretail->state==1&&tail->next->state==1;pretail->state ==0&&tail->next->state ==1pretail->state ==1pretail->state ==0&&tail->next->state ==0pretail->state ==1&&tail->next->state ==0返回头指针NYNNNNYY Npretail=tail;tail=tail->next;Y tail->state=0;将两个分区和为一个分区 置状态为0YN将状态置为0即可tail->state=0;Y将此分区与前一个分区合并并修改状态将此分区与后一个分区合并并修改状态将此分区与前后两个分区合并并修改状态YY回收内存子函数流程图六、程序清单#include <stdio.h> #include<malloc.h> struct FBT { int startdress; //分区首地址 int size;//分区所占内存大小int processid;//所申请内存分区的进程号，本来FBT 中没有这一项，但是便于内存的回收我加了这一项 int state;//此分区的状态struct FBT *next;//指针，指向下一个结点（分区）};struct FBT *create() //建立自由块表{struct FBT *head,*p,*q;head=NULL;p=(struct FBT *)malloc (sizeof(struct FBT));//申请一个新的结点，用来存放新的分区q=(struct FBT *)malloc (sizeof(struct FBT));//申请一个新的结点，用来存放新的分区head=p;p->size =5; //系统分区，大小为5p->processid =-1; //－1表示操作系统的固定分区p->startdress =0; //开始地址为0p->state =1; //状态为已分配，值为1p->next =q; //指向下一个结点q->size=123; //余下的分区大小为123q->processid=0; //所对应的进程号为0，表示都未分配q->startdress=5; //开始地址为5q->state=0; //状态为未分配，值为0q->next=NULL; //指向下一个分区，因为只有两个分区，所以为空return head;}struct FBT *distribute(struct FBT *head) //分配内存子函数{int id,neededsize;struct FBT *pretail,*tail,*p;printf("please input the process id:"); //输入要申请内存的进程号scanf("%d",&id);printf("please input the needed size:"); //输入要申请的内存大小scanf("%d",&neededsize);pretail=tail=head;while (tail!=NULL){if(tail->state ==0&&tail->size >=neededsize)//如果此分区没有分配，而且大小大于等于申请的内存大小{if(tail->size >neededsize)//如果此分区大小大于要申请的大小，分配，并把余下的再分割成一个分区{p=(struct FBT *)malloc (sizeof(struct FBT));p->size =neededsize;p->processid =id;p->startdress =tail->startdress ;p->state =1;if(head!=tail){pretail->next =p;p->next =tail;pretail=p;}else{p->next =tail;head=p;tail->next =NULL;}tail->startdress =p->startdress+p->size ;tail->size =tail->size -neededsize;break;}if(tail->size =neededsize)//如果此分区等于要申请的大小，直接分配即可{tail->processid =id;tail->state =1;break;}}else //否则，指向下一个结点继续判断{pretail=tail;tail=tail->next ;}}if(tail==NULL) //如果遍历完链表都没有找到合适的分区分配，则显示以下信息printf("\nSorry,there is not enough memory!\n");return head; //返回头指针}struct FBT *callback(struct FBT *head) //回收内存子函数{int id;struct FBT *pretail,*tail;printf("please input the process's id:");scanf("%d",&id);pretail=tail=head;while(tail!=NULL) //遍历链表{if(tail->processid ==id)//如果改分区所对应的进程号为要收回分区的进程号，则做以下动作{if(tail->next !=NULL)//如果改分区不是最后一个分区，则做以下动作{if(pretail->state ==1&&tail->next->state ==1 )//前一个分区是已分配的且后一个分区也是已分配的{tail->state =0;break;}if(pretail->state ==0&&tail->next->state ==1 )//前一个分区是未分配的且后一个分区是已分配的{pretail->next =tail->next;pretail->size =tail->size +pretail->size ;free(tail);break;}if(pretail->state ==1&&tail->next->state ==0 )//前一个分区是已分配的且后一个分区是未分配的{if(pretail!=tail){pretail->next =tail->next ;tail->next ->size =tail->next ->size +tail->size;tail->next ->startdress =tail->startdress ;free(tail);break;}else{head=tail->next ;tail->next->startdress =0;tail->next->size +=tail->size;break;}}if(pretail->state ==0&&tail->next->state ==0 )//前一个分区和后一个分区都是未分配的{pretail->next =tail->next->next ;pretail->size =pretail->size +tail->size +tail->next ->size ;free(tail->next);free(tail);break;}}else//如果改分区是最后一个分区则做以下动作{if(pretail->state ==1) //如果前一个分区是已分配的{tail->state =0;break;}else //如果前一个分区是未分配的{pretail->next =NULL;pretail->size=pretail->size +tail->size ;free(tail);break;}}}pretail=tail;tail=tail->next ; //遍历下一个分区结点}return head; //返回头指针}void print(struct FBT *head) //显示FBT的内容给用户{struct FBT *tail=head;printf("startdress\tsize\tstate\t\tprocessid\t\n");tail=head;while(tail!=NULL){if(tail->state==1)printf("%5d\t\t%5d\t%5d\t\t%5d\n",tail->startdress ,tail->size ,tail->state ,tail->processid );elseprintf("%5d\t\t%5d\t%5d\n",tail->startdress ,tail->size ,tail->state );tail=tail->next ;}}void main()//主函数{int choice=1;struct FBT *head;head=create();while(choice!=0) //显示选择菜单，供用户选择{printf("\t1.distribute the memory\n");printf("\t2.callback the memory\n");printf("\t0.exit\n");printf("\tplease choose:");scanf("%d",&choice);switch (choice){case 1:head=distribute(head);print(head);break;//选择1，则做内存分配case 2:head=callback(head);print(head);break; //选择2，则做内存回收case 0: break;default :printf("input is error!\n"); //否则显示选择错误}}}。

1，引论引论一、单选1、计算机操作系统的功能是( ) （分数：1 分）A. 把源程序代码转换为目标代码B. 实现计算机用户之间的相互交流C. 完成计算机硬件与软件之间的转换D. 控制、管理计算机系统的资源和程序的执行标准答案是：D。

2、操作系统是一组( ) （分数：1 分）A. 文件管理程序B. 中断处理程序C. 资源管理程序D. 设备管理程序标准答案是：D。

3、下列四个操作系统中，是分时系统的为( ) （分数：1 分）A. CP／WB. MS-DOSC. UNIXD. WINDOWS NT标准答案是：C。

4、批处理系统的主要缺点是( ) （分数：1 分）A. CPU的利用率不高B. 失去了交互性C. 不具备并行性D. 以上都不是标准答案是：B。

5、在多道程序设计的计算机系统中,CPU( ). （分数：1 分）A. 只能被一个程序占用B. 可以被多个程序同时占用C. 可以被多个程序交替占用D. 以上都不对标准答案是：C。

6、引入多道程序的目的是( ). （分数：1 分）A. 为了充分利用主存储器B. 增强系统的交互能力C. 提高实时响应速度D. 充分利用CPU,减少CPU的等待时间标准答案是：D。

7、现代操作系统的两个基本特征是( )和资源共享. （分数：1 分）A. 多道程序设计B. 中断处理C. 程序的并发执行D. 实现分时与实时处理标准答案是：C。

8、下面关于操作系统的叙述正确的是( ). （分数：1 分）A. 批处理作业必须具有作业控制信息B. 分时系统不一定都具有人机交互功能C. 从响应时间的角度看,实时系统与分时系统差不多D. 由于采用了分时技术,用户可以独占计算机的资源标准答案是：A。

9、允许多个用户以交互使用计算机的操作系统是( ). （分数：1 分）A. 分时系统B. 单道批处理系统C. 多道批处理系统D. 实时系统标准答案是：A。

10、批处理操作系统提高了计算机的工作效率,但( ). （分数：1 分）A. 系统吞吐量小B. 在作业执行时用户不能直接干预C. 系统资源利用率不高D. 不具备并行性标准答案是：B。

（第5章操作系统的资源管理）习题五答案习题五参考答案（P132）5-1什么是虚拟资源？对主存储器⽽⾔，⽤户使⽤的虚拟资源是什么？答：虚拟资源是⽤户使⽤的逻辑资源，是操作系统将物理资源改造后，呈现给⽤户的可供使⽤的资源。

对主存储器⽽⾔，⽤户使⽤的虚拟资源是虚拟存储器。

提供给⽤户使⽤虚拟存储器的⼿段是逻辑地址空间，⽤户在编程时使⽤的是逻辑地址，空间⼤⼩不受限制（也就是说逻辑地址空间可以⽐物理地址空间⼩也可以⽐物理地址空间⼤）。

5-2常⽤的资源分配策略有哪两种？在每⼀种策略中，资源请求队列的排序原则是什么？答：常⽤的资源分配策略有先来先服务策略和优先调度策略。

在先来先服务策略中资源请求队列的排序原则是按照提出请求的先后次序排序；在优先调度策略中资源请求队列的排序原则是按照提出请求的紧迫程度（即优先级）从⾼到底排序。

5-3什么是移臂调度？什么是旋转调度？答：移臂调度是指在满⾜⼀个磁盘请求时，总是选取与当前移臂前进⽅向上最近的那个请求，使移臂距离最短。

旋转调度是指在满⾜⼀个磁盘请求时，总是选取与当前读写磁头旋转⽅向上最近的那个请求，使旋转圈数最少。

5-4什么是死锁？试举例说明。

答：⼀组进程中，每个进程都⽆限等待被该组进程中另⼀进程所占有的资源，因⽽永远⽆法得到资源，这种现象称为进程死锁，这⼀组进程就称为死锁进程。

设某系统拥有⼀台输⼊机和⼀台打印机，并为进程P1和P2所共享。

在t1时刻，进程P1和P2分别占⽤了输⼊机和打印机。

在t2（t2 > t1）时刻，进程P1请求打印机，P1将被阻塞，进⼊等待打印机的等待队列中，等待P2释放打印机。

在t3（t3 > t2）时刻，进程P2请求输⼊机，P2将被阻塞，进⼊等待输⼊机的等待队列中，等待P1释放输⼊机。

此时，P1和P2进⼊了永久的互等状态，即P1和P2成为死锁进程，出现了死锁现象。

5-5产⽣死锁的原因是什么？产⽣死锁的必要条件是什么？答：产⽣死锁的原因主要有：（1）竞争有限的系统资源。