算法与数据结构Algorithms and Data Structures 第八章 动态存.ppt

《算法与数据结构Algorithms and Data Structures 第八章 动态存.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、算法与数据结构AlgorithmsandDataStructures第八章动态存储管理第八章动态存储管理8.1概述内存是很重要的、很昂贵的资源，如何合理高效地使用这一资源是一个比较复杂的问题。早期使用低级语言编程，内存管理是由程序员自己负责。程序员负担重，管理水平因人而异，管理效率低，容易出错。随着操作系统和高级语言的发展，情况不断改善。内存管理分别由操作系统、高级语言的编译系统和程序员分工合作管理。通常编译系统负责静态储存管理，操作系统负责整个内存管理和动态储存管理。程序员级的管理：用户程序中所用的储存结构有两种，静态结构：空间量在编译后，即

2、可确定动态结构：程序运行中申请空间，编译时无法确定。静态储存由编译系统管理。动态储存由程序员和操作系统管理，但程序员的管理非常简单。程序员的工作就是在需要的时候向系统申请空间，在不需要时释放要来的动态储存空间：C语言中：malloc(size),申请size字节的内存；free(p),释放p，归还给系统；C++中：newobjectType(),申请空间；free(p),释放p，归还给系统；Java语言中：newobjectType(),申请空间；用户程序：#includeiostd.lib……Intmain(){…*r=newint[100]

3、;…free(r);…}操作系统分配OS_AllocMemory(r,size,flags)回收OS_ReclaimMemory(r)FreeMemFreeMemrFreeMem编译系统级管理在编译中，编译系统为程序设置了一个虚拟空间，它管理的是虚拟空间。用户程序：…intx,y;floatr,s;charstr[10];………虚拟空间：x:4bytesy:4bytesstr:10bytesr:4bytess:4bytes048121626内存程序装入时，重定位编译原理与技术中将做介绍。操作系统级管理：存储管理是操作系统的重要部分之一，操作系统

4、对储存的管理是才是真实的管理，而且这一管理是很复杂的。操作系统的存储管理为程序代码和静态数据分配空间为程序动态分配空间回收不用的动态空间回收空间程序代码和静态数据空间分配回收执行程序执行完毕或撤消执行程序程序NewOtype()Free(p)从外部来看，操作系统存储管理系统就是提供存储空间分配和回收服务，但内部实现方法却十分复杂，不同的操作系统采用不同的策略和方法，这些问题将在后续课程操作系统中详细介绍。这里我们只是站在数据结构的角度来讨论动态存储管理的基本方法，即存储空间的分配和回收基础技术、存储空间的逻辑结构和物理结构。8.2可利用空间表初

5、试状态OSbootOS占用空间freetagsizelink一个连续的存储空间称为“块”[block]Tag：标记空间是否分配Size：空间大小Link：指向下一个空闲块初试状态：除了操作系统占用的空间外，其它空间形成一个空闲块。当空闲块多时，用link链成一个链表，该链表就是可利用空间表。初试此表中只有一个空闲块。表指针是free。经过多次分配、回收之后，形成了多个空闲块，它们之间不连续，如图所示：Freeused1used2used3used4used523456Free1136542可利用空间表的链接顺序有：（1）按块的首地址有低到高链接

6、；（2）按块的大小有小到大链接；（3）按块的大小有大到小链接；分配：一般有3种策略，设申请空间的大小为n（1）首次拟合法：从表头开始搜索，遇到第一个尺寸等于大于n的块进行分配；（2）最佳拟合法：搜索整个表，将最小的等于大于n的块进行分配；（3）最差拟合法：搜索整个表，将最大块进行分配（等于大于n）；分配过程：找到合适的空闲块p；P.size等于n或比n大少许（一般设定一个量s），则将p从表中删除，进行分配；若p.size>n+s，从p的下部切割size为n的一块进行分配，如图所示：n=16k064kp116k48k回收:程序释放空间(如free

7、(p))、程序运行结束后将占用的块归还系统，如果收回的块的相邻块是空闲的，需要合并它们。回收过程：设释放块是p，大小为size。（1）设置p.tag=0；（2）判断p的下相邻块q是否空闲若空闲：从可利用空间表摘出q，置p.size=p.size+q.size(合并)；（3）判断p的上相邻块r是否空闲若空闲：合并r和p，r.size=r.size+p.size否则：将p插入可利用空间表。例如：Freeused1used2used3used4used523456Free1136542释放used104k11knull06k12used104k07k

8、null12used1011k12used1有时也不必马上合并，如果释放块p的大小恰好符合下次申请空间的要求，可以将p分配，而不必从可利用空间表中切割