算法与数据结构课件

算法与数据结构

AlgorithmsandDataStructures

第八章动态存储管理算法与数据结构

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

第八章动态存储管理8.1概述2程序员级的管理：用户程序中所用的储存结构有两种，静态结构

：空间量在编译后，即可确定动态结构：程序运行中申请空间，编译时无法确定。静态储存由编译系统管理。动态储存由程序员和操作系统管理，但程序员的管理非常简单。程序员的工作就是在需要的时候向系统申请空间，在不需要时释放要来的动态储存空间：C语言中：malloc(size),申请size字节的内存； free(p),释放p，归还给系统；C++中：newobjectType(),申请空间；free(p),释放p，归还给系统；程序员级的管理：3Java语言中：newobjectType(),申请空间；用户程序：#includeiostd.lib……Intmain(){…*r=newint[100];…free(r);…}操作系统分配OS_AllocMemory(r,size,flags)回收OS_ReclaimMemory(r)FreeMemFreeMemrFreeMemJava语言中：newobjectTyp4编译系统级管理在编译中，编译系统为程序设置了一个虚拟空间，它管理的是虚拟空间。用户程序：…intx,y;floatr,s;charstr[10];………虚拟空间：x:4bytesy:4bytesstr:10bytesr:4bytess:4bytes048121626内存程序装入时，重定位编译原理与技术中将做介绍。编译系统级管理用户程序：虚拟空间：x:4bytesy:45操作系统级管理：

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

从外部来看，操作系统存储管理系统就是提供存储78.2可利用空间表初试状态OSbootOS占用空间freetagsizelink一个连续的存储空间称为“块”[block]Tag：标记空间是否分配Size：空间大小Link：指向下一个空闲块初试状态：除了操作系统占用的空间外，其它空间形成一个空闲块。当空闲块多时，用link链成一个链表，该链表就是可利用空间表。初试此表中只有一个空闲块。表指针是free。8.2可利用空间表OSbootOS占用空间free8经过多次分配、回收之后，形成了多个空闲块，它们之间不连续，如图所示：Freeused1used2used3used4used523456Free1136542经过多次分配、回收之后，形成了多个空闲块，它们之间不连续，如9可利用空间表的链接顺序有：（1）按块的首地址有低到高链接；（2）按块的大小有小到大链接；（3）按块的大小有大到小链接；分配：一般有3种策略，设申请空间的大小为n（1）首次拟合法：从表头开始搜索，遇到第一个尺寸等于大于n的块进行分配；（2）最佳拟合法：搜索整个表，将最小的等于大于n的块进行分配；（3）最差拟合法：搜索整个表，将最大块进行分配（等于大于n）；可利用空间表的链接顺序有：10分配过程：找到合适的空闲块p；P.size等于n或比n大少许（一般设定一个量s），则将p从表中删除，进行分配；若p.size>n+s，从p的下部切割size为n的一块进行分配，如图所示：n=16k064kp116k48k分配过程：064kp116k48k11回收: 程序释放空间(如free(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插入可利用空间表。回收: 程序释放空间(如free(p))、程序运行结束后将占12例如：Freeused1used2used3used4used523456Free1136542释放used104k11knull06k12used104k07knull12used1011k12used1例如：Freeused1used2used3used4us13有时也不必马上合并，如果释放块p的大小恰好符合下次申请空间的要求，可以将p分配，而不必从可利用空间表中切割分配。Free136542used1有时也不必马上合并，如果释放块p的大小恰好符14例如，一个使用单链表的程序，它会不断地申请和释放同类型的结点（块大小相等），回收时不进行合并，而是放在另一个链表avail中；分配时首先从avail取一个块分配，当avail中没有空闲块时在从free表里分配。这样就省去了不断地合并切割的麻烦，可以提高效率。对于一些小的操作系统，内存管理相对简单些。在许多专用设备、智能仪表和家用电器等都使用一种小型的、高效的、简单的操作系统，一般称之为“嵌入式操作系统”。下面介绍一些实用而简单的动态存储管理系统。例如，一个使用单链表的程序，它会不断地申请和释放同类型的结点158.3伙伴系统（Buddysystem）特点：（1）分配块的大小均是2k;（2）分配和回收简单可利用空间表结构：202122...2k2m0k0k0k^^^内存最大空间是2m空闲块按其大小链入各自的链表；该数组是各链表的表头接点同尺寸的空闲块构成双向循环链表；有4个域：tag标记，0空闲，1占用，k:块的大小2k,llink:q前驱指针，rlingk:后继指针8.3伙伴系统（Buddysystem）200k0k016伙伴系统抽象数据类型ADTBoddySystemData:intm //可用内存2mFreeHeadList //m个表头结点构成的线性表BlockScrpt //块描述 Memory //整个内存空间opration:BS_malloc(size) //分配内存BS_reclaim(BlockScrptbp)//回收内存EndBlockSystem伙伴系统抽象数据类型17ClassFreeHeadNode{intsizePower;//k2kBlockScrptfirst;//链表指针}//ClassFreeHeadNode

ClassFreeHeadList{intm;//FreeHeadNode[]list;publicFreeHeadList(intn){m=n;list=newFreeHeadNode[m];}for(k=0;k<=m;k++){list[k].sizePower=k;first=null;}}//ClassFreeHeadList

kfirst0123..m-1m^^^^^ClassFreeHeadNode{kfirst0^^^18块描述ClassBlockScrpt{intsizePower; booleanused; BlockScrptllink,rlink;intadd;public

BlockScrpt(intk,booleanb,intaddr){sizePower=k;used=b;add=addr;}//BlockScrpt}//ClassBlockScrpt

块描述19伙伴系统结构ClassBuddySystem{intm; //最大可用内存2mBlockHeadListheadList //表头向量BlockScrptblkScrpt; //块描述Byte[]mem; //内存publicBuddySystem(intk){//构造函数m=k;headList=newBlockHeadList(m);blkScrpt=newBlockScrpt(m,false,0);

伙伴系统结构20blkScrpt.llink=blkscrpt;blkScrpt.rlink=blkscrpt;headList[m].first=blkScrptmem=newByte[2m];}//BlockScrptBS_malloc(intk){……}voidBS_reclaim(BlockScrptbp){……}}//ClassBuddySystem

blkScrpt.llink21初始状态012..k..mfalsem00122m-1headListmemBlockScrpt初始状态0falsem00headListmemBlockS22分配26之后..67..k.m-1mfalsem-12m-102m-12m-1headListmemfalsek2kfalse727true60false626分配26之后..falsem-12m-10headLis23分配算法思想：申请空间量为2k；从k到m依次搜寻非空链表 若无：内存不够，结束；若有：设为headList[j]k=<j<=m若j=k:从headList[k]中取一结点分配，结束；若j>k:从headList[j]取一结点bs(1)将bs均分为二，高地址部分插入headList[j-1];j--;(2)重复（1）直到j=k；4将bs分配；结束；分配算法思想：24BlockScrptBS_malloc(intk){

for(j=k;j<=m;j++)//找非空链表if(!headList[j].first)break;if(j>m)returnnull;//无非空链表，分配失败bs=headList[j].delet(1);

//从非空链表中取第一个接点；for(s=j;s>k;s--){//将大块分割；bst=newBlockScrpt(s-1,false,bs.add+2s-1);headList[s-1].insert(bst);bs.sizePower--;}//forbs.used=true;returnbs;//分配bs}//Trues-1Falses-1bstbsBlockScrptBS_malloc(intk){25回收算法思想

伙伴系统的一个重要特点是：任何块（除最大块外）都有唯一的一个伙伴，所谓伙伴即：大小一样且相邻；空闲的相邻块是可以合并的；一个块的伙伴地址是什么？设块的首地址是p，其伙伴的首地址是：

Buddy(p,k)=p+2k(ifpMOD2k+1=0)=p

+2k(ifpMOD2k+1=2k)回收算法思想26设回收的块是bsk=bs.sizePower;p=bs.ad