4第四章存储器管理Convertor

第四章存储器管理（1）张琦[e-mail]内容4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式4.1存储器的层次结构4.1.1多级存储器结构对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。在较高档的计算机中，还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。计算机系统存储层次示意在存储层次中越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。CPU寄存器主存辅存4.1存储器的层次结构一般来说，容量越大的存储介质，访问速度会越慢，但单位存储的成本越低。反过来说，如果存储介质的访问速度越高，则它的成本也会越高，例如寄存器。4.1存储器的层次结构4.1.2主存储器与寄存器1．主存储器主存储器(简称内存或主存)用于保存进程运行时的程序和数据。由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。2.寄存器寄存器访问速度最快,用于加速存储器的访问速度，协调CPU工作，但价格却十分昂贵，因此容量不可能做得很大。4.1存储器的层次结构4.1.3高速缓存和磁盘缓存1．高速缓存高速缓存容量大于或远大于寄存器,访问速度快于主存储器。将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。2．磁盘缓存磁盘缓存本身并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储器存储空间的扩充，即利用主存中的存储空间，来暂存从磁盘中读出(或写入)的信息。4.2程序的装入和链接如何将一个用户源程序变为一个可在内存中执行的程序，通常都要经过以下几个步骤：①是要编译，由编译程序(Compiler)将用户源代码编译成若干个目标模块(ObjectModule)；②是链接，由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块(LoadModule)；③最后是装入，由装入程序(Loader)将装入模块装入内存。………编译程序产生的目标模块库内存装入模块4.2程序的装入和链接4.2.1程序的装入1.绝对装入方式(AbsoluteLoadingMode)装入程序按照装入模块中的绝对地址将程序和数据装入内存。2．可重定位装入方式(RelocationLoadingMode)装入模块为相对地址（逻辑地址），装入程序按照当前内存使用的情况，将装入模块装入内存的某个物理地址。3．动态运行时装入方式(DynamicRun-timeLoading)将装入模块装入内存后，运行时才进行地址变换，又称为动态重定位。只适用于单道程序环境。装入后不能改变，是一种静态重定位。4.2程序的装入和链接4.2.2程序的链接根据链接时间的不同，可把链接分成如下三种：(1)静态链接事先将所需目标模块链接生成一个完整的装入模块(.exe)运行时直接装入内存。(2)装入时动态链接指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。(3)运行时动态链接延迟到运行时，才将当前被调用的目标模块装入，并链接。4.3连续分配方式4.3.1单一连续分配这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分。1．划分分区的方法(1)分区大小相等，即所有的内存分区大小相等。(2)分区大小不等。4.3.2固定分区分配这是最简单的可运行多道程序的存储管理方式。将内存用户空间划分为若干个固定大小的区域，在每个分区中装入一道作业，允许几道作业并发运行。4.3连续分配方式2．内存分配将内存固定划分为相等或不等的区域，称为分区，分区一旦划定，在执行过程中分区长度和个数将不再变化。建立内存分配表记录分区分配的情况。简单、可靠，但产生分区“内零头”，内存利用效低。区号/键大小起址状态18KB512K已分配232KB520K已分配332KB552K未分配4128KB584K未分配5512KB712K已分配…………4.3连续分配方式4.3.3动态分区分配动态分区分配是根据进程的实际需要，动态地为之分配内存空间。1．分区分配中的数据结构用来描述空闲分区和已分配分区的情况，为分配提供证据。常用的数据结构有以下两种形式：空闲分区表在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。(2)空闲分区链为了实现对空闲分区的分配和链接，设置前向指针和后向指针，将所有的空闲分区链接成一个双向链。4.3连续分配方式空闲链结构在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。当分区被分配出去以后，把状态位由“0”改为“1”，此时，前、后向指针已无意义。4.3连续分配方式Job1Job2Job3Job4Job5Job6Job64.3连续分配方式2．分区分配算法1)首次适应算法(firstfit)FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。该算法的优缺点：为大作业分配大的内存空间创造了条件。低址部分不断被划分，会留下许多难以利用的、很小的空闲分区。当一个新作业装入内存时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。目前常用的有以下五种分配算法：4.3连续分配方式2)循环首次适应算法(nextfit)将所有的空闲分区构成一个循环链表。采用循环查找方式，设置一个起始查寻指针，用于指示下一次起始查寻的空闲分区。该算法的优缺点：能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。在为进程分配内存时，不再是每次都从链首开始查找，而是从上次找到空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区。4.3连续分配方式3)最佳适应算法(bestfit)该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。该算法的优缺点：为大作业分配大的内存空间创造了条件。每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区。“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。4.3连续分配方式4)最坏适应算法(worstfit)该算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，但查找效率很高。该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。该算法的缺点是它会使存储器中缺乏大的空闲分区。最坏适应算法与前面所述的首次适应算法、循环首次适应算法、最佳适应算法一起，也称为顺序搜索法。4.3连续分配方式5)快速适应算法(quickfit)该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表。该算法的优点是查找效率高，仅需要根据进程的长度，找到能容纳它的最小空闲区链表即可；另外不会对任何分区产生分割，满足对大空间的需求，不会产生内存碎片。缺点是在分区归还主存时算法复杂，系统开销较大。首次适应算法循环首次适应算法最佳适应算法最坏适应算法快速适应算法要求空闲分区链以容量从小到大递增的次序链接；第一次找到的能满足要求的空闲区，必然是最佳的；在存储器中会留下许多难以利用的小空闲区。要求空闲分区链以容量从大到小次序链接；查看第一个能满足要求的分区。在存储器中会缺乏大的空闲分区。根据容量大小进行分类；对于每一类具有相同容量的空闲分区，设立一个空闲分区链表。查找效率高，但归还算法复杂。4.3连续分配方式要求空闲分区链以地址递增的次序链接；从低地址端开始查找空闲分区，会在低地址端留下许多难以利用的、小的空闲分区；会增加查找可用空闲分区时的开销。仍要求空闲分区链以地址递增的次序链接；从上一次找到的空闲分区的下一个空闲分区开始查找，为此需增设一个起始查寻指针；使得内存中的空闲分区分布得比较均匀，但会缺乏大的空闲分区。4.3连续分配方式3．分区分配操作1)分配内存系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。2)回收内存当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：设请求的分区为u.size，表中每个空闲分区的大小可表示为m.size。4.3连续分配方式内存分配流程比较每个空闲分区与请求分区的大小Size是事先规定的不再切割的剩余分区的大小4.3连续分配方式(1)回收区与插入点的前一个空闲分区F1相邻接(2)回收区与插入点的后一空闲分区F2相邻接将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。F1回收区回收区F24.3连续分配方式(3)回收区同时与插入点的前、后两个分区邻接(4)回收区既不与F1邻接，又不与F2邻接将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。F1回收区F24.3连续分配方式4.3.6可重定位分区分配1．动态重定位的引入可变分区分配克服了内零头，提高了内存的利用率，但产生了外零头。使小碎片得不到利用。紧凑技术也称为“拼凑”技术，用于解决可变分区中产生的“外零头”，即移动某些已分配分区，使“外零头”合并为一个大的连续空闲区。经过紧凑后，用户程序在内存中的位置发生了变化，所以必须对移动了的程序或数据进行重定位。4.3连续分配方式2．动态重定位的实现重定位寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。动态重定位的实现原理365LOAD1,2500500025001000365LOAD1,25001500012500100001100010000重定位寄存器处理机一侧存储器一侧作业J内存4.3连续分配方式3．动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧凑。请求分配顺序查找空闲分区表有可用分区动态分配修改数据结构Y空闲区总和需求N紧凑修改数据结构Y返回N返回分区号及首地址4.3连续分配方式4.3.7对换1．对换(Swapping)的引入所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。如果对换是以整个进程为单位，便称之为“整体对换”或“进程对换”。为了实现进程对换，系统必须能实现三方面的功能：对换空间的管理、进程的换出、和进程的换入。4.3连续分配方式2．对换空间的管理在具有对换功能的OS中，通常把外存分为文件区和对换区。文件区：用于存放文件管理目标：提高文件存储空间的利用率采用离散分配方式对换区：存放从内存中换出的进程管理目标：提高进程换入、换出的速度管理策略采用连续分配方式，较少考虑外存中的碎片问题。数据结构：对对换区的空闲盘块进行管理。4.3连续分配方式3．进程的换出与换入进程的换出---