《数据结构》课件(C语言) 第08章.ppt

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 =

17、1 s= (p-1)-uplink; /s为左邻空闲块的头部地址 s-size += n; /设置新的空闲块大小 f=p+n+1; f-uplink = s; f-tag = 0; /设置新的空闲块底部,0,s1,0,1,1,s2,1,p,释放块,左邻块,右邻块,p+p-size,s1+s2,P-1,(2) 释放块的左邻区为空闲块，右邻区为占 用块，即有(p-1)-tag = 0 /t为右邻空闲块的头部地址 p-tag = 0; /p为合并后的结点的头部地址 q = t-llink; /q为t结点在可用空间链表中的前驱结点的头部地址 p-llink = q; q-rlink = p; /q为p

18、的前驱 q1 = t-rlink; /q1为t结点在链表中的后继结点的头部地址 p-rlink = q1; q1-llink = p; /q1为p的后继 p-size += t-size; /新的空闲块大小 FootLoc(t)-uplink = p; /底部指针指向新结点的头部,(3) 释放块的左邻区为占用块，右邻区为空 闲块，即有(p-1)-tag = 1 /n为释放块大小，设为s2 s = (p-1)-uplink; t = p + p-size; /s指示左邻块，t指示右邻块 q = t-llink; q1 = t-rlink; /qq1 s-size += n + t-size; /

19、设置新结点中spact空间大小 q-rlink = q1; q1-llink = q; /删去右邻空闲块结点 FootLoc(t)-uplink = s; /使新结点底部指针指向新结点的头部,0,s1,0,0,s3,0,s2,p,释放块,左邻块,右邻块,P-1,s1+s2+s3,(4) 释放块的左、右邻区均为空闲块， 即有(p-1)-tag = 0 int tag; int kval; WORD *rlink; OtherType other; WORD, Head; typedef struct HeadNode int nodesize; WORD *first; FreeListM+1;

20、,伙 伴 系 统,第34页,分配算法,伙伴系统分配算法的基本约定： (1) 分配存储块时其容量一律按照2的幂给予满足。如果用户请求分配n字，则伙伴系统将给予容量为2k的一块存储空间，它满足关系2k-1 n 2k。而已经分配的 2kn这个余数称为内部碎片（设n不是2的幂），它是个小小的浪费；,伙 伴 系 统,(2) 所有容量为2k的空闲存储块都链接在一个链表中，因此，对于总容量为2m的伙伴系统，将所有m+1个链表；,(3) 假定存储区初始状态是容量为2m的一个单一空闲块，其内存地址是0 2m1。,伙伴系统的分配过程：设用户提出大小为n的内存请求，则在可利用表上寻找结点大小与n相匹配的子表，(1)

21、若此子表非空，则将该子表中任意一个结点（可取第一个结点）分配之；(2)若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个空闲块，将其中一部分分配给用户，而将剩余部分插入至相应的子表中,第35页,示例2 伙伴系统可利用空间表在进行分配用户请求内存时的状态变化（设分配容量为2k-1）。初始状态如右图所示,伙 伴 系 统,需要分配大小为n的内存。,(1)如果2k-1 n = 2k-1 且k+1个子表不为空，直接在k+1链表中分配。,第36页,示例2 伙伴系统可利用空间表在进行分配用户请求内存时的状态变化（设分配容量为2k-1）。初始状态如右图所示,伙 伴 系 统,需要分配大小为n的内存。,

22、(2)如果2k-2 n = 2k-1-1且k(即2k-1) 个子表为空，则需要从结点大小 为2k取出一般分配，另一半作 为新结点插入到结点大小 为2k-1的子表中。,第37页,伙 伴 系 统,一般情况： 假如对于用户需求n，有 2k-i-1n2k-i-1 其中i为小于k的一个整数，并且所有结点小于2k的子表均为空，此时如何进行分配？ 同样地，需从结点大小 为2k的子表中取出一块，将 其中2k-i的一小部分分配给用 户，剩余部分分割成若干个 结点分别插入在结点大小 为2k-i,2k-i+1,2k-1的子表中。,第38页,示例3 对于需要内存容量为n=7的用户，假定所有容量为23=8,24=16,

23、25=32的链表均为空，而26=64的链表为非空，则将该表中的一个结点进行分配与分割，设其起始地址为p，则 占用块（始地p）：分配给用户； 空闲块1（始地p+8）：插入至23=8的子表； 空闲块2（始地p+16)：插入至24=16的子表； 空闲块3（始地p+32)：插入至25=32的子表；,伙 伴 系 统,大小7，碎片为1,第39页,伙伴系统分配算法描述 Space alloc_buddy( FreeList /算法8.2,伙 伴 系 统,第40页,回收算法,回收过程：当用户释放不再使用的空闲块时，系统需将新的空闲块插入到可利用空间表中去。可能要对地址相邻的空闲块进行合并以构成较大块。但在伙伴

24、系统中，仅考虑互为伙伴的两个空闲块的合并。对于起始地址为p，大小为2k的内存块，欲求其伙伴内存块的起始地址，有 p+2k，若p MOD 2k+1=0 buddy(p,k)= (*) p-2k，若p MOD 2k+1=2k,伙 伴 系 统,768(29+28),256(=28),伙伴块,伙伴块,第41页,伙伴系统方法的算法分析：存储动态分配和回收的伙伴系统方法的效率是很高的，它是存储管理中最快捷的一种分配和回收存储块的方法。然而这种速度快捷的优点是以增加存储碎片（内部碎片）为代价的。由于请求容量不足2k时，只能分配2k这样大的存储块，就产生了多余的存储空间。,伙 伴 系 统,2k,第42页,无用

25、单元收集,无用单元是指那些用户不再使用而系统没有回收的结构和 变量。,比如 p = malloc( size );/C+: p = new( ) p = NULL; 此时，使得执行malloc为用户在堆区域分配的结点p成为无用单元。,悬挂访问：欲对已悬空的指针进行访问，比如 p = malloc( size );/C+: p = new( . ) q = p; free( p );/delete p; 若所释放的结点被再分配，则再次访问指针q所指结点将引发错误。,无用单元收集法即是将存储区中那些不再使用的内存块收集起来形成可利用空间表的方法，亦称为存储废料收集法。,第43页,一般并非随时地进行

26、回收，只有当空闲存储区几乎耗尽，或者出现了很大的用户请求分配，以至于现有的空闲块不能满足需求时，才开始工作。 经过周密而又费时的检测判断过程，找出所有不再使用的那些存储块，把它们当作“废料”回收，形成一个可重新利用的可利用空间表。,无用单元收集,此工作由操作系统负责进行管理。在程序运行的过程中，对所有的空闲块链表结点，不管它是否还有用，都不回收，直到整个可利用空间表为空。此时系统才暂时中断执行程序，将所有当前不被使用的结点链接在一起，成为一个新的可利用空间表，而后程序再继续执行。,第44页,收集无用单元的步骤 (1) 对所有占用结点加上标志。确定哪些结点是占用结点的方法是：对于一个正在运行的程

27、序，只要从所当前正在工作的指针变量出发，顺链遍历，那末，所有链接在这些链上的结点都是占用的。反之，可利用存储空间中的其余结点就都是无用的。假设在无用单元收集之前所有结点的标志域均置为0，则加上标志就是将结点的标志域置为1；,无用单元收集,(2) 对整个可利用空间的顺序扫描一遍，将所有标志域为0的结点链接成一个新的可利用空间表。 因此，无用单元收集法的全过程可分为“打标记”和”回收“两个阶段。 上述第一步是在可利用空间表几乎耗尽的情况下进行的，它们的数目多少直接影响着算法的执行时间，故工作量较大。,第45页,标志算法,若系统中采用含有共享子表的广义表来存放用户程序中的各占用块结点，则加标志的操作

28、实质上是遍历广义表，将广义表中所有结点的标志域均赋值为1。 有三种常用的标志算法：,无用单元收集,(1) 递归算法 若列表为空，则无需遍历；若是一个数据元素，则标志该元素结点；反之，则列表非空，首先标志表结点，然后分别遍历表头和表尾。 此算法实现简单，但是需要一个较大的、用于递归的栈空间，该栈空间不能用于动态分配，且栈的大小不易确定，易引起栈区满的异常现象。 这是目前使用的方法中最简单而又古老的方法。,第46页,(2) 非递归算法 在程序中附设栈（或队列）以实现广义表的遍历。广义表的存储结构中的元素结点不包含指针域。而表结点则类似于二叉树的二叉链表。列表中的元素结点相当于二叉树中的叶子结点，可

29、以类似于遍历二叉树写出遍历广义表的非递归算法，只是在算法中应尽量减少栈的容量。 对列表进行遍历可采用与图的遍历相类似的深度优先搜索遍历或者广度优先搜索遍历。,无用单元收集,(3) 利用表结点本身的指针域标志遍历路径的算法 利用已经标志过的表结点中的tag, hp,和tp域来代替栈，以记录遍历过程中的路径。这样，就避免了使用容量不易确定的栈空间。,第47页,三种标志算法的比较 (1) 递归算法：所使用的栈空间不由用户程序掌握，易产生堆区域溢出； (2) 非递归算法：程序中附设栈的容量可由用户程序掌握，且比上法所需容量要小，还要操作简单，但仍需要一个不确定量的附加存储； (3) 利用表本身的指针域

30、标记遍历路径的算法：在作标志时不需要附加存储，使动态分配的可利用空间得到充分利用。但在算法中，几乎是每个表结点的指针域的值都要作两次改变，故时间上的开销相当大，而且一旦发生中断，整个系统瘫痪，无法重新启动运行。 无用单元收集法不适合在实时处理的情况下使用。,无用单元收集,第48页,无用单元收集法所需要的执行时间与当前还在使用的存储块的数目成正比。无用单元收集这项工作的效率和最后能收集到的可以重新分配的无用结点数有关。 当调用这个方法的的次数频繁，而每次又没有多少可收回的无用存储块时，效率就十分低下。这是此法的主要缺点。 此外，由于它不是随时地、经常地做回收工作，所以那些可能相邻的空闲块得不到及

31、时融合，一旦又进行存储分配时，往往在存储区产生不必要的碎片现象。,无用单元收集,第49页,存 储 紧 缩,前面所述的动态存储管理的几种分配和回收算法，使用了空闲块链表。若按地址顺序排列空闲块链表，则较易于将相邻的空闲块融合在一起，把相邻的较小空闲块变成较大的空闲块，从而减少存储碎片的现象。 但是，由于没有一种一般的方法来预测已被分配的存储块不再使用而变成空闲块的次序，因此在多数系统中，总存在存储碎片的现象。同时，由于融合空闲存储块完全是一种偶然的机会，所以不能单纯地依赖这种融合技术来保证存储分配时会得到可用的较大空闲存储块。但利用较大的邻接存储块，不仅从逻辑上，而且在物理上的执行效率来看都是十