动态存储管理.docx

动态存储管理目录前言10.概论20.1内存的初始模型20.2基本问题的提出21 可利用空间表及分配方法31.1链式可利用空间表的结构形式31.1.1情况一：系统运行期间所有用户请求分配的存储量大小相同31.1.2情况二：系统运行期间用户请求分配的存储量有若干种大小的规格31.1.3情况三：系统在运行期间分配给用户的内存块的大小不固定，可随请求而变42具体方法62.1边界标志法62.1.1可用空间表的结构62.1.2 分配算法72.1.3 回收算法72.2伙伴系统（buddy system）72.2.1可利用空间表的结构82.2.2分配方法82.2.3回收方法93无用单元收集94存储紧缩9前言今天，想回头加深对各种排序算法的理解时，在数据结构（严蔚敏）一书中发现了一章关于动态储存管理的书。想起前些日子，腾讯二面时面试官问的一个C+高效内存管理的题目。题目的大概意思是：在一个需要频繁new和delete的系统中，为了加快系统速度，需要减少new和delete的次数。而且每个数据在一定的范围内。问，如何才能实现高效率的内存分配呢？刚开始的时候，我把这两个问题误认为是同一个问题了。尽管他们之间确实有很紧密的联系，而且解决的方法也很有共通之处，但它们确实不是同一个问题。首先，它们关注的问题不同。动态存储管理的基本问题是内存的分配和回收；而后者的基本问题是减少new和delete操作的次数，以减少频繁内存分配和回收带来的时间代价，加快系统的整体速度。其次，它们所关注问题所在的层次不同。动态存储管理是属于操作系统的范畴，这个问题的解决，能够方便操作系统为上层提供动态分配、回收内存服务；而后者的new和delete正是操作系统提供的服务，但它的问题的是减少这种服务来加快软件本身的运行速度，是属于应用层的问题。动态存储管理减少new和delete问题基本问题对计算机内存的动态分配和回收的管理（操作系统对整个计算机的资源进行管理，其中包括了对内存的管理。它为上层内存操作提供服务，要不断的分配和回收）由于要频繁的new和delete，明显地降低了软件的性能，通过减少new和delete的操作次数，来达到提高性能的目的目的方便内存的分配和回收（总之就是管理动态存储）在软件运行时，减少new和delete的次数管理的对象（结点）空闲块（也就是未被分配的块）占有块（也就是被分配被new之后的块）空闲块被分配之后从链表或者目录表中删除（或者叫“摘掉”）被插入到已分配内存块链表中，说明这个结点已被申请下来占用块被回收之后加入可利用空间链表中从链表中删除，说明这个块被系统回收了，程序不能再使用它了。综上所述，我们不仅可以看出这两个问题的区别，也可以得出动态内存管理关注的基本问题是：系统如何应用户的要求的“请求”分配内存？又如何回收哪些用户不再使用而“释放”掉的内存，以备新的“请求”产生时重新进行分配？提出请求的用户可能是进入系统的一个作业，也可能是程序执行过程中的一个动态变量。0. 概论0.1 内存的初始模型如下图：显然，不管什么样的动态存储管理系统，在刚开工是，整个内存区是一个“空闲块”（在编译器中称为 堆），如上图“运行前”。随着用户（如无特别说明，这里的用户指的是系统的作业或者程序执行过程中的一个动态变量）进入系统，先后提出存储请求，系统则依次进行分配。所以，在系统运行的初期，整个内存区基本上分割成两部分：低地址为若干个占用块，高地址为若干个空闲块，如上图“程序加载后”所示。经过一段时间之后，随着一部分用户的退出，它们之前所占用的内存块被释放，形成了占用块和空闲块交错状态，如上图“释放部分内存后”所示。0.2 基本问题的提出假如此时又有新的用户进入系统请求分配内存，那么系统如何做呢？通常有两种方法：A. 系统从高地址空闲块中进行分配，直到分配无法进行时，才回收所有用户不再使用的空闲块，重新组织一个大的空闲块来再分配；B. 用户程序一旦运行结束，便将它所占内存区释放成为空闲块，同时，每当新用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找出一个“合适”的空闲块分配之。由此，系统需建立一张“可利用空间表” 。 “可利用空间表”的结构可以是a) 目录表 b) 链表1 可利用空间表及分配方法1.1 链式可利用空间表的结构形式可利用空间表（链式）：包含所有可分配的空闲块，每一块是链表中的一个结点。A)当用户请求分配时，系统从可利用空间表中删除一个结点分配之；B)当用户释放其所占内存时，系统即回收并将它插入到可利用空间表中。因此，可利用空间表也叫做“内存池”根据系统运行的不同情况，可利用空间表可以有以下3种不同结构方式：1.1.1 情况一：系统运行期间所有用户请求分配的存储量大小相同方式：在系统开始运行时将归它使用的内存区按所需大小分割成若干大小相同的块，然后用指针链成一个可利用空间表。分配：由于表中结点大小相同，则分配时无需查找。只要将第一个结点分配给用户即可；回收：当用户释放内存时，系统只要将用户释放的空闲块插入在表头即可1.1.2 情况二：系统运行期间用户请求分配的存储量有若干种大小的规格方式：建立若干个可利用空间表，同一链表中的结点大小相同。分配：根据请求的大小，将最接近该大小的某个链表的首结点分配给用户。A结点大小和请求分配的量相同的链表为非空时，即能直接找到和请求量相当的结点，则直接将该结点从链表中删除即可B当结点大小和请求分配的量相同的链表为空时，需要查询结点较大的链表，并从中取出一个结点，将其中一部分内存分配给用户，而将剩余部分插入到相应大小的链表中。回收：只要将释放的空闲块插入到相应大小链表的表头即可。例如：某动态储存管理系统中的用户将请求分配2个字、4个字或8个字的内存块，则系统建立3个结点大小分别为3个字、5个字和9个字的链表，它们的表头指针分别为av2、av4和av8。特殊问题：当结点与请求相符的链表和结点更大的链表均为空的时候，分配不能进行。而实际上内存空间并不一定不存在所需大小的连续空间，只是由于在系统运行的过程中，频繁出现小块的分配和回收，使得大的结点链表中的空闲块被分割成小块后插入在小结点的链表上了。1.1.3 情况三：系统在运行期间分配给用户的内存块的大小不固定，可随请求而变因此，可利用空间表中的结点的即空闲块的大小也是随意的。通常，在操作系统中的可利用空间表就属于这种类型的方法：系统刚开始工作时，整个内存空间是一个空闲块，即可利用空间表中只有一个大小为整个内存区的结点，随着分配和回收的进行，可利用空间表中的结点大小和个数也随之而变。回收：只需将释放的空闲块插入到链表的适当位置即可特殊问题：由于可利用空间表中的结点大小不同，则在分配时就有一个问题。假设某用户需要大小为n的内存，而可利用空间表中仅有一块大小为m=n的空闲块，则只需要将其中大小为n的一部分分配给申请分配的用户，同时，将剩余的m-n部分作为一个结点留在链表即可。 然而，若可利用空间表中有若干个不小于n的空闲块时，该分哪块？以下有三种分配策略（1） 首次拟合法：从表头指针开始查找可利用空间表，将找到第一个大小不小于n的空闲块即可。（2） 最佳拟合法：将可利用空间表一个不小于n且最接近n的空闲块的一部分分配给用户。（3） 最差拟合法：将可利用空间表中不小于n且是链表中最大的空闲块的一部分分配给用户。以上3种方法的优缺点请参考数据结构 P197-198下图分别说明了系统在某个时刻T+1，一个新的用户申请分配7K内存，由时刻T的状态经3种不同的分配策略，而产生的3种不同的T+1时刻的状态2 具体方法具体的实现方法有：边界标志法和伙伴系统2.1 边界标志法边界标志法：系统将所有的空闲块连接在一个双重循环链表结构的可利用空间表中；分配可按首次拟合进行，也可以按最佳拟合进行。特点：在每个内存区的头部和底部两个边界上分别设置标识，以标志该区域为占用块或空闲块，使得在回收用户释放的空闲块时易于判别在物理位置上与其相邻的内存区域是否为空闲块，以便将所有地址连续的空闲存储区组合成一个尽可能大的空闲块。2.1.1可用空间表的结构 为方便说明，假定内存块的大小以“字“为单位计算，地址也是以“字”为单位来计的，结点的头部中的size域表示整个结点的大小，包括头部的head和底部的foot所占的空间，并假设head和foot各占一个字的空间，但在分配的时候忽略不计。下面定义这个结构： typedef struct WORD /WORD,内存字类型 union /head和foot分别是结点的第一个和最后的字WORD *llink；/如果是head，则指向前驱结点WORD *uplink ; /如果是foot，则指向本结点的头部；int tag ; /块标志，0：空闲 1：占用int size; /只存在head中，表示块的大小WORD *rlink； /只存在head中，指向下一个结点OtherType other;WORD,head ,foot,*Space;#define FootLoc(P) P+P-size -1 /指向P所指结点的底部2.1.2 分配算法 分配算法见数据结构P2002.1.3 回收算法 回收算法详细见数据结构P201 三种情况：左邻居是空闲块，右邻居是空闲块，左右邻居都是空闲块2.2 伙伴系统（buddy system）伙伴系统（buddy system）是操作系统用到的另一种动态存储管理的方法。在伙伴系统中，无论是占用块还是空闲块，其大小都是2的k次幂 。