单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,第一章 操作系统引论,4.3,连续分配存储管理方式,4.3.1,单一连续分配,在单道程序环境下，当时的存储器管理方式是把内存分为系统区和用户区两部分，系统区仅提供给,OS,使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。,4.3 连续分配存储管理方式4.3.1 单一,4.3.2,固定分区分配,1.,划分分区的方法,可用下述两种方法将内存的用户空间划分为若干个固定大小的分区：,(1),分区大小相等,(,指所有的内存分区大小相等,),。,(2),分区大小不等。,4.3.2 固定分区分配1.划分分区的方法可,2.,内存分配,为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态,(,是否已分配,),，如图,4-5,所示。,2.内存分配为了便于内存分配，通常将分区按其大小,图,4-5,固定分区使用表,图4-5 固定分区使用表,4.3.3,动态分区分配,1.,动态分区分配中的数据结构,常用的数据结构有以下两种形式：空闲分区表，在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项，如图,4-6,所示。空闲分区链。为了实现对空闲分区的分配和链接，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链，如图,4-7,所示。,4.3.3 动态分区分配1.动态分区分配中的数据结,图,4-6,空闲分区表,图4-6 空闲分区表,图,4-7,空闲链结构,图4-7 空闲链结构,2.,动态分区分配算法,为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。由于内存分配算法对系统性能有很大的影响，故人们对它进行了较为广泛而深入的研究，于是产生了许多动态分区分配算法。,2.动态分区分配算法为把一个新作业装入内存，须按,3.,分区分配操作,1),分配内存系统应利用某种分配算法，从空闲分区链,(,表,),中找到所需大小的分区。设请求的分区大小为,u.size,，表中每个空闲分区的大小可表示为,m.size,。,3.分区分配操作1)分配内存系统应利用某,图,4-8,内存分配流程,图4-8内存分配流程,2),回收内存 当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链,(,表,),中找到相应的插入点，此时可能出现以下四种情况之一：,(1),回收区与插入点的前一个空闲分区,F,1,相邻接，见图,4-9(a),。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区,F,1,的大小。,(2),回收分区与插入点的后一空闲分区,F,2,相邻接，见图,4-9(b),。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。,2)回收内存 当进程运行完毕释放内存时，系统根,(3),回收区同时与插入点的前、后两个分区邻接，见图,4-9(c),。此时将三个分区合并，使用,F,1,的表项和,F,1,的首址，取消,F,2,的表项，大小为三者之和。,(4),回收区既不与,F,1,邻接，又不与,F,2,邻接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。图,4-10,示出了内存回收时的流程。,(3)回收区同时与插入点的前、后两个分区邻接，见图4,图,4-9,内存回收时的情况,图4-9 内存回收时的情况,图,4-10,内存回收流程,图4-10 内存回收流程,4.3.4,基于顺序搜索的动态分区分配算法,1.,首次适应,(first fit,，,FF),算法,我们以空闲分区链为例来说明采用,FF,算法时的分配情况。,FF,算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配失败，返回。,4.3.4 基于顺序搜索的动态分区分配算法1.首次,2.,循环首次适应,(next fit,，,NF),算法,为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。,2.循环首次适应(next fit，NF)算法为,3.,最佳适应,(best fit,，,BF),算法,所谓“最佳”是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。,3.最佳适应(best fit，BF)算法所谓“,4.,最坏适应,(worst fit,，,WF),算法,由于最坏适应分配算法选择空闲分区的策略正好与最佳适应算法相反：它在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。,4.最坏适应(worst fit，WF)算法由于,4.3.5,基于索引搜索的动态分区分配算法,1.,快速适应,(quick fit),算法,该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表。同时，在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。,4.3.5 基于索引搜索的动态分区分配算法1.快速,2.,伙伴系统,(buddy system),该算法规定，无论已分配分区或空闲分区，其大小均为,2,的,k,次幂,(k,为整数，,lkm),。通常,2m,是整个可分配内存的大小,(,也就是最大分区的大小,),。假设系统的可利用空间容量为,2,m,个字，则系统开始运行时，整个内存区是一个大小为,2,m,的空闲分区。在系统运行过程中，由于不断地划分，将会形成若干个不连续的空闲分区，将这些空闲分区按分区的大小进行分类。对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表，这样，不同大小的空闲分区形成了,k,个空闲分区链表。,2.伙伴系统(buddy system)该算法规,在伙伴系统中，对于一个大小为,2,k,，地址为,x,的内存块，其伙伴块的地址则用,buddy,k,(x),表示，其通式为：,在伙伴系统中，对于一个大小为2k，地址为x的内存块，其伙,3.,哈希算法,在上述的分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时，需要在一张管理索引表中查找到所需空间大小所对应的表项，从中得到对应的空闲分区链表表头指针，从而通过查找得到一个空闲分区。如果对空闲分区分类较细，则相应索引表的表项也就较多，因此会显著地增加搜索索引表的表项的时间开销。,3.哈希算法在上述的分类搜索算法和伙伴系统算法中,4.3.6,动态可重定位分区分配,1.,紧凑,连续分配方式的一个重要特点是，一个系统或用户程序必须被装入一片连续的内存空间中。当一台计算机运行了一段时间后，它的内存空间将会被分割成许多小的分区，而缺乏大的空闲空间。即使这些分散的许多小分区的容量总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。,4.3.6 动态可重定位分区分配 1.紧凑连,图,4-11,紧凑的示意,图4-11 紧凑的示意,2.,动态重定位,在,4.2.1,节中所介绍的动态运行时装入的方式中，作业装入内存后的所有地址仍然都是相对,(,逻辑,),地址。而将相对地址转换为绝对,(,物理,),地址的工作被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序,(,数据,),在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。,2.动态重定位在4.2.1节中所介绍的动态运行时,图,4-12,动态重定位示意图,图4-12动态重定位示意图,3.,动态重定位分区分配算法,动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能。通常，当该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有的小的空闲分区的容量总和大于用户的要求，这时便须对内存进行“紧凑”，将经“紧凑”后所得到的大空闲分区分配给用户。如果所有的小的空闲分区的容量总和仍小于用户的要求，则返回分配失败信息。,3.动态重定位分区分配算法动态重定位分区分配算法,图,4-13,动态分区分配算法流程图,图4-13 动态分区分配算法流程图,