《【2017年整理】内存管理练习题》由会员分享,可在线阅读,更多相关《【2017年整理】内存管理练习题(23页珍藏版)》请在金锄头文库上搜索。
1、三、内存管理一、考试大纲 (一)内存管理基础1内存管理概念程序装入与链接;逻辑地址与物理地址空间;内存保护。2交换与覆盖3连续分配管理方式单一连续分配;分区分配。4非连续分配管理方式分页管理方式;分段管理方式;段页式管理方式(二)虚拟内存管理1虚拟内存基本概念2请求分页管理方式3页面置换算法最佳置换算法(OPT) ;先进先出置换算法(FIFO) ;最近最少使用置换算法(LRU);时钟置换算法。4页面分配策略5抖动抖动现象;工作集6请求分段管理方式7请求段页式管理方式二、知识点归纳 (一)内存管理基础1内存管理概念内存是指处理器可以直接存取指令和数据的存储器,内存和处理器都是计算机系统的一种重要
2、资源。在多道程序设计技术出现以后,对存储管理提出了更高的要求。内存管理的主要任务是为多道程序的运行提供良好的环境,方便用户使用存储器,提高存储器的利用率以及从逻辑上扩充存储器。在操作系统中,将一个用户的源程序变为一个可在内存中执行的进程,通常要经过以下几步:1)编译。由编译程序将用户源代码编译成若干个目标模块;2)链接。由链接程序将编译后形成的一组目标模块,以及它们所需要的库函数链接在一起,形成一个完整的装入模块;3)装入。由装入程序将装入模块装入内存。(1)程序的链接源程序经过编译后,可得到一组目标模块,这时需要利用系统中链接程序将这组目标模块链接在一起,形成装入模块。根据链接时间的不同,可
3、以分成三种链接方式,即静态链接、装入时的动态链接和运行时的动态链接。1)静态链接。在程序运行前,先将各目标模块及它们所需的库函数,链接成一个完整的装配模块,以后不再拆开。静态链接方式需要解决两个问题:外部调用符号到相对地址的转换;相对地址到绝对地址的的转换;2)装入时的动态链接。在将目标模块装入内存时,采用边装入边链接的方式。该方式具有以下优点:便于目标模块的修改和更新;便于实现对目标模块的共享。3)运行时的动态链接。事先不对各个模块进行链接,而是在程序执行中当需要该模块时,再将该模块调入内存,并进行链接。采用这种方式,凡在执行过程中没有用到的目标模块,都不会被调入内存,这样不仅可加快程序的装
4、入过程,而且可以节省大量的内存空间。(2)程序的装入程序的装入方式有三种,它们分别是绝对装入方式、可重定位的装入方式以及动态装入方式,现介绍如下。1)绝对装入方式在编译时,如果知道程序将驻留在内存的什么位置,那么编译程序将产生包含有内存绝对地址(也称实际地址)的目标代码。这样装入程序就会按照目标代码中的地址,将程序和数据装入到内存的实际位置。程序中使用的绝对地址,既可以在编译或汇编时给出,也可由程序员直接赋予。但因为需要程序员熟悉当前内存的使用情况,所以要求较高。2)可重定位的装入方式在多道程序的环境下,所得到的目标模块的起始地址通常是从 0 开始的,程序中的其它地址都是相对于起始地址进行计算
5、的。此时应采用重定位装入方式,根据内存的当前情况,将装入模块装入到内存的适当位置。由于装入模块中的所有地址与实际装入内存的物理地址不同,所以需要进行地址变换(在原先相对地址的基础上加上内存装入位置的地址) 。如下图所示100025000 Load 1, 2500365110001000012500Load 1, 2500365图 3-1 作业装入内存的情况通常,把在装入程序时对目标模块中的指令和数据的地址变换过程称为重定位。又因为地址变换是在装入时一次完成的,所以称为静态重定位。3)动态运行时的装入方式动态运行时的装入程序,在把装入模块装入内存后,并不立即将其中的相对地址转换为绝对地址,而是把
6、地址转换推迟到程序执行前再进行。因此,装入内存后的所有地址都仍是相对地址。(3)逻辑地址与物理地址空间;由编译程序所产生的所有目标模块中,使用的都是相对地址,即其起始地址为 0,每个模块中的地址都是相对于起始地址计算的。而物理地址是指内存中的实际的地址空间。(4)内存保护保证进入内存的各道作业都在自己的存储空间内运行,互不干扰。既要防止一道作业由于发生错误而破坏其他作业,也要防土破坏系统程序。这种保护一般由硬件和软件配合完成2交换与覆盖交换技术就是把暂时不用的某个程序及数据部分(或全部)从内存移到外存中去,以便腾出必要的内存空间,或把指定的程序或数据从外存读到相应的内存中,并将控制权交给它,使
7、其在系统上运行的一种内存扩充技术。覆盖技术,就是把一个大的程序划分为一系列覆盖,每个覆盖就是一个相对独立的程序单位,把程序执行时并不要求同时装入内存的覆盖组成一组,称为覆盖段,这个覆盖段分配到同一个存储区域,这个存储区域称为覆盖区,它与覆盖段一一对应。交换技术不要求程序员给出程序段之间的覆盖结构,而且交换主要是在进程或作业之间进行;而覆盖则主要在同一个作业或进程中进行。另外,覆盖只能覆盖与覆盖程序段无关的程序段。3连续分配管理方式连续分配方式,是指为用户程序分配一个连续的内存空间。可分为单一连续分配方式和分区分配方式两大类。(1)单一连续分配这是一种最简单的存储管理方式,只能用于单用户、单任务
8、的操作系统。采用该方式时,可把内存分为系统区和用户区两部分,系统区位于内存的低址部分,供 OS 使用;用户区是除系统区以外的全部内存空间,是供用户程序使用的部分。单一连续分配方式的主要特点是管理简单,只需要很少的软件和硬仍支持。且便于用户了解和使用。但采用这种存储分配方式,内存中只能装入一道作业运行,从而导致各类资源的利用率都不高。(2)分区分配分区式分配是能满足多道程序设计需要的一种最简单的存储管理技术。通常,按照分区的划分方式,它又可分为固定分区分配、动态分区分配以及可重定位的分区分配等三种方式。1)固定分区分配固定式分区法是一种最简单的可运行多道程序的存储管理方式。它将用户的内存空间划分
9、为若干个固定大小的区域,在每个分区中只装入一道作业,这样,用户空间被划分为几个分区,便允许有几道作业并发运行。当有一个空闲分区时,便可以再从外存的后备作业队列中选择个适当大小的作业装入该分区,当该作业结束时,又可再从后备作业队列中找出另一作业调入该分区。可用下述两种方法将内存的用户空间划分为若干个固定大小的分区:a)分区大小相等,就是使所有的内存分区大小相等。其缺点是缺乏灵活性,即当程序太小时,会造成内存空间的浪费;当程序太大时,一个分区又不足以装入该程序,致使该程序无法运行。尽管如此,这种划分方式仍被用于利用一台计算机去控制多个相同对象的场合,因为这些对象所需的内存空间是大小相等的。例如,炉
10、温群控系统,就是利用一台计算机去控制多台相同的冶炼炉。b)分区大小不等。为了克服分区大小相等而缺乏灵活性的这个缺点,把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。这样,便可根据程序的大小为之分配适当的分区。2)动态分区分配动态分区分配是在作业装入和处理过程中建立的分区,要求分区的容量能正好适应作业的大小。在作业进入系统前,根据作业的大小来申请所需存储容量,然后由系统实施分配。为了实现分区分配,系统中必须设置相应的数据结构,常用的有两种形式:空闲分区表和空闲分区链。为把一个新作业装入内存,须按照一定的分配算法,从空闲分区表或空闲分区链中选出一分区分配给该作业。目前常用的有以下三
11、种分配算法。a)首次适应算法。以空闲分区链作为数据结构,在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲链中。如果从链首直至链尾都不能找到满足要求的分区,则此次内存分配失败。b)循环首次适应算法。该算法是由首次适应算法演变而成的。在为进程分配内存空间时,不再是每次都从链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找。这种分配方式的优点是,使得内存中的空闲分区分布的更均匀,减少查找空闲分区的开销。c)最佳适应算法。该算法要求将所有的空闲分区按其容量从小到大的顺序形成一个空闲分区链,这样,从链
12、首开始查找时,第一次找到的合适分区,就是既能满足要求又是最小的空闲分区。d)最坏适应算法3)可重定位分区分配在连续分配方式中,必须把一个作业装入连续的内存空间,时间长了,内存中会出现很多内存碎片,而重定位式分区分配是解决碎片问题的简单而有效的办法。共基本思想是移动内存中的所有作业使之成为一个连续区域,继而留下一个较大的空白内存区。这种过程我们称之为“拼接”或“紧凑” 。由于经过紧凑后的某些用户程序在内存中的位置发生了变化,所以还需要对程序和数据的地址进行修改,这叫做重定位。4)分区的存储保护界限寄存器存储保护a. 采用上、下界寄存器分别存放作业的结束地址和开始地址;b. 采用基址和限长寄存器分
13、别存放作业的起始地址及作业的地址空间长度。存储保护键:每个存储块分配一个独立的保护键,存储块不同于分区,一个分区由若干存储块组成,存储块大小相等,每个作业赋予一个保护键。4非连续分配管理方式连续分配方式会形成许多“碎片” ,虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间,但需要为之付出很大开销。如果允许将一个进程直接分散地装入到许多不相邻接的分区中,则无须再进行“紧凑” 。基于这一思想而产生了离散分配方式。(1)分页管理方式所谓分页管理方式,是允许将一个进程直接分散地装入到许多不相邻接的分区中,分配的基本单位是页。1)页面与页表页面。分页存储管理是将一个进程的逻辑地址空间分成若干个大小相
14、等的片,称为页面,并为各页加以编号。相应地,把内存空间也分成与页面相同大小的若干个存储块,称为(物理 )块。在为进程分配内存时,以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。一个页的地址分成两部分:页号和位移量,如下图31页号 P 位移量 W12 11 0页表。在分页系统中,为了能在内存中找到每个页面所对应的物理块。系统又为每个进程建立了一张页面映像表,简称页表。在进程地址空间内的所有页,依次在页表中有页表项,其中记录了相应页在内存中对应的物理号。如图 3-2 所示0 页1 页3 页2 页4 页用户程序 页表页号 块号021326401324内存567图 3-2 页表的作用
15、2)地址变换机构为了能将用户地址空间中的逻辑地址变换为内存空间个的物理地址,在系统中必须设置地址变换机构。由于页内地址和物理地址是一一对应的,因此,地址变换任务就是借助于页表来完成的。基本地址变换。在系统中只设置一个页表寄存器,用来存放页表在内存中的始址和页表的长度。当进程要访问某个逻辑地址中的数据时,分页地址变换机构会自动地将地址分为页号和页内地址两部分,再以页号为索引去检索页表。在检索前先将页号与页表长度相比较,判断是否有效。然后将页表始址与页号和页表项长度的乘积相加,便得到该表项在页表中的位置,进而得到该页的物理块号。3)具有快表的地址变换机构为了提高地址变换速度,可在地址变换结构中,增
16、设一个具有并行查寻能力的特殊高速缓冲寄存器,称为快表。地址转换方式变为,将逻辑地址先在快表中查询转换,如失败,再访问内存中的页表。访问结束后,将该表项存入快表,以备下次查询。4)两级页表和多级页表现代的大多数计算机系统,都支持非常大的逻辑地址空间(2 32 一 264)。在这样的环境下,页表就变得非常大,要占用相当大的内存空间。解决的方法有二级页表和多级页表。对于要求连续的内存空间存放页表的问题,可利用将页表进行分页,并离散地相各个页而分别存放在不同的物理块中的办法来加以解决,同样也要为离散分配的页表再建立一张页表,称为外层页表,在每个页表项中记录了页表页面的物理块号。为了地址变换实现上的方便起见,在地址变换机构中同样需要增设一个外层页表寄存器,用于存放外层页表的始址,并利用逻辑地址中的外层页号,作为外层页表的索引,从中找到指向页表分页的地址。多级页表如果对外层页表再进行分页,并设置更高的页表来记录外层页表分页的存储情况。就构成了三级或多级页表。(2)分段管理方式所谓分段管理方式,是允许将一个进程直