《《数据结构》课件（C语言） 第08章》由会员分享，可在线阅读，更多相关《《数据结构》课件（C语言） 第08章（53页珍藏版）》请在金锄头文库上搜索。
1、数据结构,第八章 动态存储管理,第2页,可利用空间表及分配方法 边界标识法 伙伴系统 无用单元收集 存储紧缩,内容和要求 可利用空间表、边界标识法、伙伴系统和无用单元收集。 要求掌握可利用空间表及分配办法。,重点 可利用空间表及分配。,内容和要求,第3页,动态存储管理的基本问题及方法,存储管理是一个既复杂而又重要的问题。在后续课程操作系统和编译技术（或方法、原理）中，将对其作较深入的研究。在数据库技术中，也涉及大量有关存储管理的问题。本章仅就动态存储管理方面一些基本技术进行讨论。,在以往的算法描述中，有关存储分配请求、存储回收等项工作往往一带而过，好比是存储“自动满足”又 “自动回收”。偶尔亦
2、考虑某一数据结构下判断是否溢出或者是否释放内存空间等问题。这是必要的，主要是为了把当时的重点和核心放在研究数据的逻辑特性、物理表示、算法描述与分析上，而对有关存储管理的问题作了一定的简化。,第4页,动态存储管理的基本问题,(1) 如何按用户提出的“请示”分配内存？ (2) 如何回收那些用户不再使用而“释放”的内存，以备新的“请示”产生时重新进行分配？,(1) 由用户来解决； (2) 由系统来解决； (3) 由系统和用户共同解决。,动态存储管理的基本问题及方法,第5页,在计算机系统中，存储管理的分级,(1) 操作系统为进程分配所需要的存储空间，以便能在机器上运行。一旦运行结束从系统撤离时，操作系
3、统就回收进程所使用的空间。此类存储管理问题将在操作系统课程中讨论。,动态存储管理的基本问题及方法,(2) 进程对数据结构分配及回收存储空间，例如编译进程为变量、数组以及各种表格分配、回收空间。此类存储管理问题将在编译方法课程中讨论。,(3) 数据结构中，对某结构中的元素或子结构分配、回收存储空间。此类存储管理问题将是数据结构课程研究的范畴。 下面仅限于在数据结构一级上研究存储管理的方法。但其基本思想和方法亦完全适用于其他两个级别。,第6页,一些有关存储管理的重要问题,(1) 由谁来负责存储空间的分配与回收？是用户自身，还是由系统的一个专门子系统为用户分配并发现不再使用的空间而加以回收？,(2)
4、 分配和释放存储空间的单位是相同还是有大有小？,(3) 系统何时回收空闲的空间？是及时回收还是定期回收或当存储空间用完时才去回收？,(4) 是否考虑存储碎片的紧凑问题？,(5) 当请示存储空间时，满足该请示的最好分配策略是什么？是寻找容量大致相当的存储块给予，还是不加选择地依次给一块至少能满足的空间？,(6) 怎样安排空闲存储块的次序？随机排列或按地址排列或按容量大小排列？,动态存储管理的基本问题及方法,第7页,两个术语,占用块 称已分配给用户使用的地址连续的内存区为占用块。在不同的动态存储管理系统中，请求分配的内存量大小不同，可能小到几个字节，多至若干k字节。但系统每次分配给用户的都是一个地
5、址连续的内存区。,空闲块 称未曾分配的、地址连续的内存区为空闲块或可利用空间块。不管怎么样的动态存储管理系统，在刚开始工作时，整个内存区是一个空闲块（在编译系统中称之为堆，即堆区域）。,动态存储管理的基本问题及方法,占用块,此时用户再次请求分配内存，系统将怎样分配？,第8页,两种分配策略： (1) 系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存区是否已空闲，直到分配无法进行，才回收所有空闲块，并重新组织内存，将所有空闲的内存区联接成一个大的空闲块；,动态存储管理的基本问题及方法,(2) 用户一旦运行结束，便将它所占内存区释放成为空闲块，每当新用户请求分配内存时，系统巡视整个内存
6、区中所有空闲块，从中找出一个合适者分配之。此时，系统需建立一张记录所有空闲块的可利用空间表（目录表或链表）。,第9页,可利用空间表及分配方法,可利用空间表中包含所有可分配的空闲块，每一块是链表中的一个结点。当用户请示分配时，系统从可利用空间表中删除一个结点分配之；当用户释放其所占内存时，系统即回收该内存区并将它插入到可利用空间表中。,可利用空间表的结构形式,结构形式一：结点均含大小相同的空闲块。,可利用空间表可以有下列三和不同的结构形式：,若系统运行期间所有用户请求分配的存储量大小相同，则系统开始运行时，将归它使用的内存区按所需大小分割成若干大小相同的块，并用指针链接成一个可利用空间表。分配时
7、取表头结点，回收时按插表头形式。这种情况下的可利用空间表实际是一个链栈。是一种最简单的动态存储管理的方式。,第10页,示例2 有三种大小结点（设结点大小分别为2,4,8个字）的可利用空间表的结点结构及其可利用空间表。,结构形式二：建立若干个可利用空间表，同一链表中的结点大小相同。不同链表中的结点大小，一般成倍数关系。,可利用空间表及分配方法,分配过程？,第11页,结构形式二：建立若干个可利用空间表，同一链表中的结点大小相同。不同链表中的结点大小，一般成倍数关系。,可利用空间表及分配方法,分配过程？,根据用户请求空间的大小，到相应的空闲表中取结点。若该空闲表为空，则到较大结点的链表中取一结点，把
8、它一分为二，一部分分配给用户，另部分插入到结点较小的空闲表中。,产生什么结果？,结点较大链表中的结点，不断一分为二，很容易用完，所以回收时，必须有“紧缩聚合”的过程。,第12页,如何分配？,结构形式三：结点所包含空闲块的大小可随请求而变。通常，操作系统中的可利用空间表属于这种类型。,其中 tag：标志位，tag=0表示空闲块，tag=1表示占用块 size：空闲块的存储容量 link：链接下一个结点的指针域、 spack：一片地址连续的内存区域,可利用空间表及分配方法,若用户需求量为n，链表中仅有一块其容量mn，则分割出大小为n的部分分配给用户，剩余大小为m-n的部分作为一个结点留在链表中（只
9、要把size改小就行）。,问题：若空闲块链表中有若干个大小不小于n的结点，该分配哪一个？分配策略？,三种分配策略：首次拟合法；最佳拟合法；最差拟合法。,第13页,分配策略一：首次拟合法,从空闲块链表的表头指针开始查找，找出首先能满足请求容量的存储块，将其中一部分分配给用户。可利用空间表本身既不按结点的初始地址有序，也不按结点的大小有序。在回收时，只要将释放的空闲块插入在链表的表头即可。,这种方法需对空闲块链表的结点检测的平均次数从1n不等。所以，首次拟合法为了满足一次请示其平均检测次数小于n/2。,第14页,分配策略二：最佳拟合法,从空闲块链表中找出能满足用户请求容 量的最小空闲块。显然这是一
10、种较好的方法，但为了满足某个请示分配，需要对空闲块链表从头至尾扫描，时间开销大。,图8.5 结点大小随意的可利用空间表 (b)按最佳拟合原则进行分配,最佳空闲块,优点：尽可能保证较大的空闲块不被细分。以满足较大的空间请求。 缺点：有可能使剩余的空闲块容 量变得太小，以至于不能满足任何请求。,第15页,为了避免每次分配都要扫视整个链表，可以改造空闲块链表的结点排列顺序，即以结点的容量由小到大排列。这样为了满足某个请求分配，则平均检测结点的数目只是链表结点个数一半即可。然而在这种情况下，将任一空闲块插入至空闲块链表的一半位置也需要平均检测链表的一半结点。而不按块容量大小排列的空闲块链表，回收算法中
11、不需要做检测工作。,分配策略二：最佳拟合法,第16页,分配策略三最差拟合法,其指导思想是每次都用空闲块链表中最大的空闲块去满足请求分配，所以若链表中诸结点不是按容量大小排列的话，则每次分配都扫描整个链表，即检测n次。但是，如果将链表结点按空闲块容 量的不增次序排列，则满足一次请求分配仅需检测一次即可。而回收一个空闲块将其插入空闲块链表时，同样需平均检测n/2次。,若按结点容量自大至小有序链接诸空闲块，则分配时仅需删除第一个结点，并将其中一部分分配给用户，剩余部分作为一个新的结点插入到链表适当位置。 三种方法分配、回收平均检测次数列列表如下,第17页,边 界 标 识 法,边界标识法 (Bound
12、ary Tag Method)是操作系统中用以在运行期间对用户所请求的随意内存块大小进行动态分区分配的一种存储管理方法。 空闲块链表是个双向循环链表结构。分配策略或采用首次拟合法，或采用最佳拟合法。,系统特点： 在每个内存区的头部和底部两个边界上分别设有标志域，以标识该内存区域为占用块或空闲块。在回收时，对物理上相邻的空闲块进行全并，组合成一个尽可能大的、地址连续的空闲块。,第18页,可利用空间表的结构 边界标识法中的结点结构,其中 head：结点的头部地址 foot：结点的底部地址 space：一组地址连续的待分配存储单元 tag：标志域，tag=0表示空闲块，tag=1表示占用块 size
13、：整个结点的大小，包括头部header和底部footer所占空 间（设各占1个字），但在分配时忽略不计 llink：指向双向循环链表中本结点的前趋结点的指针 rlink：指向双向循环链表中本结点的后继结点的指针 uplink：指向本结点的指针，其值即为该内存块的首地址,边 界 标 识 法,head：,foot：,第19页,typedef struct WORD union WORD *llink, /头部域，指向前驱 WORD *uplink; /底部域，指向本结点头部 int tag; /块标志 int size; /块大小 WORD *rlink; /后继结点 OtherType othe
14、r; /其它部分 WORD, head, foot, *Space; #define FootLoc(p) (p+p-size-1),在此双向循环链表中不设表头结点，表头指针pav可以指向任一个结点。,边界标识法 数据结构,第20页,边界标识法分配算法,设采用首次拟合法进行分配，并约定,(1) 选定一个适当的常量e，当mne（用户请求分配容量为n的空闲块，而找到的待分配空闲块的容量mn）时，就将容量为m的空闲块整块地分配给用户；否则，若有mne，则仅分配其中n个字的内存块；,以免产生“空闲碎屑”,(2) 在每次分配之后，令指针指向刚进行过分配的结点的后继结点；,(3) 将Space型的变量视作
15、其值为存储块的头部地址的简单变量，允许作加、减运算，即假定可按地址来作加、减运算以求得新地址来表示所指向的时针。故有 p：存储块首地址 p-size：地址为p的存储块头部中的结点大小域，其值约等于同一存储块中spack空间的容量 p-tag：该存储块头部的标志域 (p+p-size-1)-tag：同一存储块底部的标志域,第21页,Space AllocBoundTag ( Space ,边界标识法分配算法描述,第22页,边界标识法分配算法描述,示例7 某系统的可利用空间表从初始状态到运行若干时间后的状态以及进行再分配（7000字）后的状态，可用图示形式表示如下,(a) 初始状态,第23页,0,
16、0,15,000,pav,0,0,8,000,0,0,41,000,10,000,31,000,59,000,(b) 运行若干时间后的状态,图8.6 某系统的可 利用空间表,第24页,回收算法,一旦用户释放占用块，系统应立即回收以备新的请求产生时进行再分配。为了使物理地址相紧邻的空间闲块能结合成一个尽可能大的结点，需检查刚释放的占用块的左、右紧邻是否空闲块，若是则合并。,算法思想：设p指向用户释放的内存区的头部，则与其低地址紧邻的内存区的底部地址为 p-1，与其高地址紧邻的内存区的头部地址为 p+p-size。,分四种情况： (1) 释放块的左、右邻区均为占用块， 即有(p-1)-tag = 1 s= (p-1)-uplink; /s为左邻空闲块的头部地址 s-size += n; /设置新的空闲块大小
