第四章汤小丹,计算机操作系统,官方课件,第四版,计算机,操作系统,课件,.

1第四章存储器管理第四章存储器管理4.1存储器的层次结构4.2程序的装入和链接4.3连续分配存储管理方式4.4对换(Swapping)4.5分页存储管理方式4.6分段存储管理方式习题2第四章存储器管理 4.1存储器的层次结构在计算机执行时，几乎每一条指令都涉及对存储器的访问，因此要求对存储器的访问速度能跟得上处理机的运行速度。或者说，存储器的速度必须非常快，能与处理机的速度相匹配，否则会明显地影响到处理机的运行。此外还要求存储器具有非常大的容量，而且存储器的价格还应很便宜。3第四章存储器管理4.1.1多层结构的存储器系统1.存储器的多层结构对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。在较高档的计算机中，还可以根据具体的功能细分为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。如图4-1所示。4第四章存储器管理图4-1计算机系统存储层次示意5第四章存储器管理2.可执行存储器在计算机系统的存储层次中，寄存器和主存储器又被称为可执行存储器。对于存放于其中的信息，与存放于辅存中的信息相比较而言，计算机所采用的访问机制是不同的，所需耗费的时间也是不同的。进程可以在很少的时钟周期内使用一条load或store指令对可执行存储器进行访问。但对辅存的访问则需要通过I/O设备实现，因此，在访问中将涉及到中断、设备驱动程序以及物理设备的运行，所需耗费的时间远远高于访问可执行存储器的时间，一般相差3个数量级甚至更多。6第四章存储器管理4.1.2主存储器与寄存器1.主存储器主存储器简称内存或主存，是计算机系统中的主要部件，用于保存进程运行时的程序和数据，也称可执行存储器。7第四章存储器管理2.寄存器寄存器具有与处理机相同的速度，故对寄存器的访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。8第四章存储器管理4.1.3高速缓存和磁盘缓存1.高速缓存高速缓存是现代计算机结构中的一个重要部件，它是介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数，这样可大幅度地提高程序执行速度。高速缓存容量远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。9第四章存储器管理2.磁盘缓存由于目前磁盘的I/O速度远低于对主存的访问速度，为了缓和两者之间在速度上的不匹配，而设置了磁盘缓存，主要用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。但磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘中读出(或写入)的信息。主存也可以看作是辅存的高速缓存，因为，辅存中的数据必须复制到主存方能使用，反之，数据也必须先存在主存中，才能输出到辅存。10第四章存储器管理 4.2程序的装入和链接用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下几个步骤：(1)编译，由编译程序(Compiler)对用户源程序进行编译，形成若干个目标模块(ObjectModule)；(2)链接，由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块(LoadModule)；(3)装入，由装入程序(Loader)将装入模块装入内存。图4-2示出了这样的三步过程。本节将扼要阐述程序(含数据)的链接和装入过程。11第四章存储器管理图4-2对用户程序的处理步骤12第四章存储器管理4.2.1程序的装入为了阐述上的方便，我们先介绍一个无需进行链接的单个目标模块的装入过程。该目标模块也就是装入模块。在将一个装入模块装入内存时，可以有如下三种装入方式：1.绝对装入方式(AbsoluteLoadingMode)当计算机系统很小，且仅能运行单道程序时，完全有可能知道程序将驻留在内存的什么位置。此时可以采用绝对装入方式。用户程序经编译后，将产生绝对地址(即物理地址)的目标代码。13第四章存储器管理2.可重定位装入方式(RelocationLoadingMode)绝对装入方式只能将目标模块装入到内存中事先指定的位置，这只适用于单道程序环境。而在多道程序环境下，编译程序不可能预知经编译后所得到的目标模块应放在内存的何处。因此，对于用户程序编译所形成的若干个目标模块，它们的起始地址通常都是从0开始的，程序中的其它地址也都是相对于起始地址计算的。14第四章存储器管理图4-3作业装入内存时的情况15第四章存储器管理3.动态运行时的装入方式(DynamicRun-timeLoading)可重定位装入方式可将装入模块装入到内存中任何允许的位置，故可用于多道程序环境。但该方式并不允许程序运行时在内存中移动位置。16第四章存储器管理4.2.2程序的链接1.静态链接(StaticLinking)方式在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。在图4-4(a)中示出了经过编译后所得到的三个目标模块A、B、C，它们的长度分别为L、M和N。在模块A中有一条语句CALLB，用于调用模块B。在模块B中有一条语句CALLC，用于调用模块C。B和C都属于外部调用符号，在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：(1)对相对地址进行修改。(2)变换外部调用符号。17第四章存储器管理图4-4程序链接示意图18第四章存储器管理2.装入时动态链接(Load-timeDynamicLinking)这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要按照图4-4所示的方式修改目标模块中的相对地址。装入时动态链接方式有以下优点：(1)便于修改和更新。(2)便于实现对目标模块的共享。19第四章存储器管理3.运行时动态链接(Run-timeDynamicLinking)在许多情况下，应用程序在运行时，每次要运行的模块可能是不相同的。但由于事先无法知道本次要运行哪些模块，故只能是将所有可能要运行到的模块全部都装入内存，并在装入时全部链接在一起。显然这是低效的，因为往往会有部分目标模块根本就不运行。比较典型的例子是作为错误处理用的目标模块，如果程序在整个运行过程中都不出现错误，则显然就不会用到该模块。20第四章存储器管理 4.3连续分配存储管理方式4.3.1单一连续分配在单道程序环境下，当时的存储器管理方式是把内存分为系统区和用户区两部分，系统区仅提供给OS使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。21第四章存储器管理4.3.2固定分区分配1.划分分区的方法可用下述两种方法将内存的用户空间划分为若干个固定大小的分区：(1)分区大小相等(指所有的内存分区大小相等)。(2)分区大小不等。22第四章存储器管理2.内存分配为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，如图4-5所示。23第四章存储器管理图4-5固定分区使用表24第四章存储器管理4.3.3动态分区分配1.动态分区分配中的数据结构常用的数据结构有以下两种形式：①空闲分区表，在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项，如图4-6所示。②空闲分区链。为了实现对空闲分区的分配和链接，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链，如图4-7所示。25第四章存储器管理图4-6空闲分区表26第四章存储器管理图4-7空闲链结构27第四章存储器管理2.动态分区分配算法为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。由于内存分配算法对系统性能有很大的影响，故人们对它进行了较为广泛而深入的研究，于是产生了许多动态分区分配算法。28第四章存储器管理3.分区分配操作1)分配内存系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。29第四章存储器管理图4-8内存分配流程30第四章存储器管理2)回收内存当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：(1)回收区与插入点的前一个空闲分区F1相邻接，见图4-9(a)。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。(2)回收分区与插入点的后一空闲分区F2相邻接，见图4-9(b)。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。31第四章存储器管理(3)回收区同时与插入点的前、后两个分区邻接，见图4-9(c)。此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。(4)回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。图4-10示出了内存回收时的流程。32第四章存储器管理图4-9内存回收时的情况33第四章存储器管理图4-10内存回收流程34第四章存储器管理4.3.4基于顺序搜索的动态分区分配算法1.首次适应(firstfit，FF)算法我们以空闲分区链为例来说明采用FF算法时的分配情况。FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配失败，返回。35第四章存储器管理2.循环首次适应(nextfit，NF)算法为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。36第四章存储器管理3.最佳适应(bestfit，BF)算法所谓“最佳”是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。37第四章存储器管理4.最坏适应(worstfit，WF)算法由于最坏适应分配算法选择空闲分区的策略正好与最佳适应算法相反：它在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。38第四章存储器管理4.3.5基于索引搜索的动态分区分配算法1.快速适应(quickfit)算法该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表。同时，在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。39第四章存储器管理2.伙伴系统(buddysystem)该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂(k为整数，l≤k≤m)。通常2m是整个可分配内存的大小(也就是最大分区的大小)。假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区