1、算法与数据结构Algorithms and Data Structures 第八章 动态存储管理8.1 概述概述 内存是很重要的、很昂贵的资源，如何合理高效内存是很重要的、很昂贵的资源，如何合理高效地使用这一资源是一个比较复杂的问题。地使用这一资源是一个比较复杂的问题。早期使用低级语言编程，内存管理是由程序员自早期使用低级语言编程，内存管理是由程序员自己负责。程序员负担重，管理水平因人而异，管理效己负责。程序员负担重，管理水平因人而异，管理效率低，容易出错。率低，容易出错。随着操作系统和高级语言的发展，情况不断改善。随着操作系统和高级语言的发展，情况不断改善。内存管理分别由操作系统、高级语言的
2、编译系统和程内存管理分别由操作系统、高级语言的编译系统和程序员分工合作管理。通常编译系统负责静态储存管理，序员分工合作管理。通常编译系统负责静态储存管理，操作系统负责整个内存管理和动态储存管理。操作系统负责整个内存管理和动态储存管理。程序员级的管理：程序员级的管理：用户程序中所用的储存结构有两种，用户程序中所用的储存结构有两种，静态结构静态结构：空间量在编译后，即可确定空间量在编译后，即可确定 动态结构：动态结构：程序运行中申请空间，编译时无法确定。程序运行中申请空间，编译时无法确定。静态储存由编译系统管理。静态储存由编译系统管理。动态储存由程序员和操作系统管理，但程序员的管理动态储存由程序员
3、和操作系统管理，但程序员的管理非常简单。程序员的工作就是在需要的时候向系统申非常简单。程序员的工作就是在需要的时候向系统申请空间，在不需要时释放要来的动态储存空间：请空间，在不需要时释放要来的动态储存空间：C语言中：语言中：malloc(size),申请申请size字节的内存；字节的内存；free(p),释放释放p，归还给系统；，归还给系统；C+中：中：new objectType(),申请空间；申请空间；free(p),释放释放p，归还给系统；，归还给系统；Java语言中：语言中：new objectType(),申请空间；申请空间；用户程序：用户程序：#include iostd.libI
4、nt main()*r=new int100;free(r);操作系统操作系统分配分配 OS_AllocMemory(r,size,flags)回收回收 OS_ReclaimMemory(r)FreeMemFreeMem rFreeMem编译系统级管理编译系统级管理 在编译中，编译系统为程序设置了一个虚拟在编译中，编译系统为程序设置了一个虚拟空间，它管理的是虚拟空间。空间，它管理的是虚拟空间。用户程序：int x,y;float r,s;char str10;虚拟空间：虚拟空间：x:4bytesy:4bytesstr:10bytesr:4bytess:4bytes048121626内存程序装入
5、时，重定位程序装入时，重定位编译原理与技术中将做介绍。编译原理与技术中将做介绍。操作系统级管理：操作系统级管理：存储管理是操作系统的重要部分之一，操作存储管理是操作系统的重要部分之一，操作系统对储存的管理是才是真实的管理，而且这一系统对储存的管理是才是真实的管理，而且这一管理是很复杂的。管理是很复杂的。操作系统的存储管理操作系统的存储管理为程序代码和静态数为程序代码和静态数据分配空间据分配空间为程序动态分配空间为程序动态分配空间回收不用的动态空间回收不用的动态空间回收空间程序代码和回收空间程序代码和静态数据空间静态数据空间分分配配回回收收执行程序执行程序执行完毕或撤消执行程序执行完毕或撤消执行
6、程序程序New Otype()Free(p)从外部来看，操作系统存储管理系统就是提从外部来看，操作系统存储管理系统就是提供存储空间分配和回收服务，但内部实现方法却供存储空间分配和回收服务，但内部实现方法却十分复杂，不同的操作系统采用不同的策略和方十分复杂，不同的操作系统采用不同的策略和方法，这些问题将在后续课程操作系统中详细介绍。法，这些问题将在后续课程操作系统中详细介绍。这里我们只是站在数据结构的角度来讨论动这里我们只是站在数据结构的角度来讨论动态存储管理的基本方法，即存储空间的分配和回态存储管理的基本方法，即存储空间的分配和回收基础技术、存储空间的逻辑结构和物理结构。收基础技术、存储空间的
7、逻辑结构和物理结构。8.2 可利用空间表可利用空间表 初试状态初试状态OS bootOS 占用空间占用空间freetagsizelink一个连续的存储空间称为一个连续的存储空间称为“块块”blockTag：标记空间是否分配：标记空间是否分配Size：空间大小：空间大小Link：指向下一个空闲块：指向下一个空闲块初试状态：除了操作系统占用的空间初试状态：除了操作系统占用的空间外，其它空间形成一个空闲块。当空外，其它空间形成一个空闲块。当空闲块多时，用闲块多时，用link 链成一个链表，该链成一个链表，该链表就是可利用空间表。初试此表中链表就是可利用空间表。初试此表中只有一个空闲块。表指针是只有一
8、个空闲块。表指针是free。经过多次分配、回收之后，形成了多个空闲块，它们之间经过多次分配、回收之后，形成了多个空闲块，它们之间不连续，如图所示：不连续，如图所示：Free used1used2used3used4used523456Free 1136542可利用空间表的链接顺序有：可利用空间表的链接顺序有：（1）按块的首地址有低到高链接；）按块的首地址有低到高链接；（2）按块的大小有小到大链接；）按块的大小有小到大链接；（3）按块的大小有大到小链接；）按块的大小有大到小链接；分配：分配：一般有一般有3种策略，设申请空间的大小为种策略，设申请空间的大小为n （1）首次拟合法：首次拟合法：从表头
9、开始搜索，遇到第一从表头开始搜索，遇到第一个尺寸等于大于个尺寸等于大于n的块进行分配；的块进行分配；（2）最佳拟合法：最佳拟合法：搜索整个表，将最小的等于搜索整个表，将最小的等于大于大于n的块进行分配；的块进行分配；（3）最差拟合法：最差拟合法：搜索整个表，将最大块进行搜索整个表，将最大块进行分配（等于大于分配（等于大于n）；）；分配过程：分配过程：找到合适的空闲块找到合适的空闲块p；P.size等于等于n或比或比n大少许（一般设定一个量大少许（一般设定一个量s），），则将则将p从表中删除，进行分配；从表中删除，进行分配；若若p.sizen+s，从，从p的下部切割的下部切割size为为n的一块
10、进的一块进行分配，如图所示：行分配，如图所示：n=16k064kp116k48k回收回收:程序释放空间程序释放空间(如如free(p)、程序运行结束后、程序运行结束后将占用的块归还系统，如果收回的块的相邻块将占用的块归还系统，如果收回的块的相邻块是空闲的，需要合并它们。是空闲的，需要合并它们。回收过程：设释放块是回收过程：设释放块是p，大小为，大小为size。（1）设置设置p.tag=0；（2）判断）判断p的下相邻块的下相邻块q是否空闲是否空闲 若空闲：从可利用空间表摘出若空闲：从可利用空间表摘出q，置，置p.size=p.size+q.size(合并合并)；（3）判断）判断p的上相邻块的上相
11、邻块r是否空闲是否空闲 若空闲：合并若空闲：合并r和和p，r.size=r.size+p.size 否则：将否则：将p插入可利用空间表。插入可利用空间表。例如：例如：Free used1used2used3used4used523456Free 1136542释放used104k11k null06k12used104k07k null12used10 11k12used1 有时也不必马上合并，如果释放块有时也不必马上合并，如果释放块p的大小恰的大小恰好符合下次申请空间的要求，可以将好符合下次申请空间的要求，可以将p分配，而不分配，而不必从可利用空间表中切割分配。必从可利用空间表中切割分配。F
12、ree 136542used1例如，一个使用单链表的程序，它会不断地申请例如，一个使用单链表的程序，它会不断地申请和释放同类型的结点（块大小相等），和释放同类型的结点（块大小相等），1 回收时不进行合并，而是放在另一个链表回收时不进行合并，而是放在另一个链表avail中；中；2 分配时首先从分配时首先从avail取一个块分配，当取一个块分配，当avail中没中没有空闲块时在从有空闲块时在从free表里分配。表里分配。这样就省去了不断地合并切割的麻烦，可以提高这样就省去了不断地合并切割的麻烦，可以提高效率。效率。对于一些小的操作系统，内存管理相对简单些。对于一些小的操作系统，内存管理相对简单些。
13、在许多专用设备、智能仪表和家用电器等都使用在许多专用设备、智能仪表和家用电器等都使用一种小型的、高效的、简单的操作系统，一般称一种小型的、高效的、简单的操作系统，一般称之为之为“嵌入式操作系统嵌入式操作系统”。下面介绍一些实用而简单的动态存储管理系统。下面介绍一些实用而简单的动态存储管理系统。8.3 伙伴系统（伙伴系统（Buddy system）特点：特点：（1）分配块的大小均是）分配块的大小均是2k;（2）分配和回收简单）分配和回收简单 可利用空间表结构：可利用空间表结构：202122.2k2m0 k0 k0 k内存最大空间是内存最大空间是2m空闲块按其大小链入各自的链表；空闲块按其大小链入
14、各自的链表；该数组是各链表的表头接点该数组是各链表的表头接点同尺寸的空闲块构成双向循环链表；有同尺寸的空闲块构成双向循环链表；有4个域：个域：tag标记，标记，0空闲，空闲，1占用，占用，k:块的大小块的大小2k,llink:q前驱指针，前驱指针，rlingk:后继指针后继指针 伙伴系统抽象数据类型伙伴系统抽象数据类型ADT BoddySystem Data:int m/可用内存可用内存2m FreeHeadList /m个表头结点构成的线性表个表头结点构成的线性表 BlockScrpt/块描述块描述 Memory/整个内存空间整个内存空间 opration:BS_malloc(size)/分
15、配内存分配内存 BS_reclaim(BlockScrpt bp)/回收内存回收内存End BlockSystemClass FreeHeadNode int sizePower;/k 2k BlockScrpt first;/链表指针链表指针/Class FreeHeadNode Class FreeHeadList int m;/FreeHeadNode list;public FreeHeadList(int n)m=n;list=new FreeHeadNodem;for(k=0;k=m;k+)listk.sizePower=k;first=null;/Class FreeHeadLi
16、st kfirst0123.m-1m块描述块描述Class BlockScrpt int sizePower;boolean used;BlockScrpt llink,rlink;int add;public BlockScrpt(int k,boolean b,int addr)sizePower=k;used=b;add=addr;/BlockScrpt/Class BlockScrpt 伙伴系统结构伙伴系统结构Class BuddySystem int m;/最大可用内存最大可用内存2m BlockHeadList headList/表头向量表头向量 BlockScrpt blkScr
17、pt;/块描述块描述 Byte mem;/内存内存 public BuddySystem(int k)/构造函数构造函数 m=k;headList=new BlockHeadList(m);blkScrpt=new BlockScrpt(m,false,0);blkScrpt.llink=blkscrpt;blkScrpt.rlink=blkscrpt;headListm.first=blkScrpt mem=new Byte2m;/BlockScrpt BS_malloc(int k)void BS_reclaim(BlockScrpt bp)/Class BuddySystem 初始状态初
18、始状态012.k.mfalse m00122m-1headListmemBlockScrpt分配分配 26 之后之后.67.k.m-1mfalsem-12m-102m-12m-1headListmemfalse k2kfalse 727true 60false 626分配算法思想：分配算法思想：申请空间量为申请空间量为2k；1 从从k到到m依次搜寻非空链表依次搜寻非空链表若无：内存不够，结束；若无：内存不够，结束；若有：设为若有：设为headListj k=jk:从从headListj取一结点取一结点bs (1)将将bs均分为二，高地址部分插入均分为二，高地址部分插入headListj-1;j
19、-;(2)重复（重复（1）直到）直到j=k；4 将将bs 分配；结束；分配；结束；BlockScrpt BS_malloc(int k)for(j=k;jm)return null;/无非空链表，分配失败无非空链表，分配失败 bs=headListj.delet(1);/从非空链表中取第一个接点；从非空链表中取第一个接点；for(s=j;sk;s-)/将大块分割；将大块分割；bst=new BlockScrpt(s-1,false,bs.add+2s-1);headLists-1.insert(bst);bs.sizePower-;/for bs.used=true;return bs;/分配
20、分配bs/True s-1 False s-1 bstbs回收算法思想回收算法思想 伙伴系统的一个重要特点是：任何块（除最大块伙伴系统的一个重要特点是：任何块（除最大块外）都有唯一的一个伙伴，所谓伙伴即：大小一样外）都有唯一的一个伙伴，所谓伙伴即：大小一样且相邻；且相邻；空闲的相邻块是可以合并的；空闲的相邻块是可以合并的；一个块的伙伴地址是什么？一个块的伙伴地址是什么？设块的首地址是设块的首地址是p，其伙伴的首地址是：，其伙伴的首地址是：Buddy(p,k)=p+2k (if p MOD 2k+1=0)=p+2k (if p MOD 2k+1=2k)设回收的块是设回收的块是bs 1 1k=bs
21、.sizePower;p=bsk=bs.sizePower;p=bs.add;.add;2 2计算计算 伙伴地址伙伴地址 q=buddy(p,k);q=buddy(p,k);3 3从从headListheadListkk链表中找链表中找addadd等于等于q q的块描述的块描述bstbst，若无：伙伴占用，将若无：伙伴占用，将bsbs插入插入headListheadListk,k,结束；结束；否则：将否则：将bsbs和和bstbst合并，用合并，用bsbs描述。描述。K+;K+;4 4重复重复3 3 直到直到km;km;5 5将将bsbs插入插入headListheadListmm。8.4 8.4 一个小型的动态存储管理系统一个小型的动态存储管理系统算法算法6.8:6.8:中序遍历线索二叉树中序遍历线索二叉树算法算法6.9:6.9:求求p p的后继（的后继（p p在前序序列中的后继在前序序列中的后继)算法算法6.10:6.10:前序遍历线索二叉树前序遍历线索二叉树改进后算法：改进后算法：Huffman算法：算法：算法算法6.11 Huffman6.11 Huffman编码编码void initiate(char c,float w)void selectMin(int k,int&s,int&t)void getCode()
