第七章-动态存储管理(2012).pptVIP

回收算法在用户释放不再使用的占用块时，系统需将这新的空闲块插入到可利用空间表中去。这里，同样有一个地址相邻的空闲块归并成大块的问题。但是在伙伴系统中仅考虑互为“伙伴”的两个空闲块的归并。 何谓“伙伴”? 如前所述，在分配时经常需要将一个大的空闲块分裂成两个大小相等的存储区，这两个由同一大块分裂出来的小块就称之“互为伙伴”。 例如：假设p为大小为2k的空闲块的初始地址，且pMOD2k+1=0，则初始地址为p和p+2k的两个空闲块互为伙伴。 在伙伴系统中回收空闲块时，只当其伙伴为空闲块时才归并成大块。也就是说，若有两个空闲块，即使大小相同且地址相邻，但不是由同一大块分裂出来的，也不归并在一起。回收算法由此，在回收空闲块时，应首先判别其伙伴是否为空闲块， 若否，则只要将释放的空闲块简单插入在相应子表中即可； 若是，则需在相应子表中找到其伙伴并删除之，然后再判别合并后的空闲块的伙伴是否是空闲块。依此重复，直到归并所得空闲块的伙伴不是空闲块时，再插入到相应的子表中去。回收算法无用单元的收集无用单元：用户不再使用而系统没有回收的结构和变量。如：p=malloc(size);……p=NULL;造成空间无法被重复利用，成为无用单元。p=malloc(size);……q=p;free(p);造成指针q的悬空，称悬挂访问。广义表中同一个结点在多个表中时，释放其中一个链表时，其他链表中指向该节点的指针产生悬挂访问，若不释放，又使得不用的空间未被释放，成为无用单元。解决办法：1）访问计数器：增加一个记录指向此结点的指针数量的计数器，当计数为0时，结点才能被释放。2）收集无用单元：一般程序运行中不进行回收，直到无可利用空间时才会中断程序执行，进行空间的回收。加空闲标记：先对程序中正在使用的空间进行标注，tag＝1，剩余的就是空闲的空间块，tag＝0。扫描并收集：扫描整个存储空间，将标志为0的结点链接成一个新的可利用空间表。存储紧缩可用空间是一个地址连续的存储区，在编译程序中称为堆，每次分配都从这个可利用空间中划出一块。分配：设置一个堆指针，指向当前可分配空间的开始。用户申请N个单位的存储空间，分配时将堆指针移动N个单位，移动前的即为分配给用户的空间，移动后的为新的可利用空间的开始。紧缩存储回收：必须保证堆空间的连续性，就需要进行存储紧缩：空闲块的合并。做法：1、一旦有用户释放存储块即进行回收紧缩。2、程序执行过程中不进行回收，到可利用空间不够分配时进行存储紧缩。存储紧缩步骤1、计算占用块的新地址。 从最低地址查询整个空间，对每个占用块找它的新地址，设两个指针，分别指向占用块的原地址和新地址，建立新旧地址对照。2、修改用户的初始变量值。 修改用户变量的位置信息，以便在存储紧缩后程序仍能正常运行。3、检查每个占用块中存储的数据。 若其中有指向其他存储块的指针，做相应修改。4、将所有占用块迁移到新地址中去。 将原块中数据传送到新块中。小结动态存储的管理主要涉及的是内存的分配方法和回收方法。内存的组织可以用可利用空间表。边界标识法和伙伴系统都是可利用空间表的不同形式。存储紧缩是针对堆分配时的空间优化。第七章动态存储管理

对每一种数据结构来说，结构中的每个数据元素都占有一定的内存位置，在程序执行的过程中，数据元素的存取是通过对应的存储单元来进行的。 在早期的计算机上，这个存储管理的工作是由程序员自己来完成的。 在有了高级语言之后，程序员不需要直接和内存地址打交道，程序中使用的存储单元都由逻辑变量(标识符)来表示，它们对应的内存地址都是由编译程序在编译或执行时进行分配。对操作系统和编译程序来说，存储管理都是一个复杂而又重要的问题。不同语言的编译程序和不同的操作系统可以采用不同的存储管理方法。动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存?又如何回收那些用户不再使用而“释放”的内存，以备新的“请求”产生时重新进行分配?下面将简单讨论利用不同策略进行动态存储管理的方法。动态存储管理可利用空间表及分配方法可利用空间表进行动态存储分配的方法一般会利用目录表或链表记录所有空闲块。在此仅就链表的情况进行讨论。可利用空间表中包含所有可分配的空闲块，每一块是链表中的一个结点。当用户请求分配时，系统从可利用空间