数据结构-第8章动态存储管理.ppt

8.1 概述8.2 可利用空间表及分配方法8.3 边界标识法 8.3.1 可利用空间表的结构 8.3.2 分配算法 8.3.3 回收算法8.4 伙伴系统 8.4.1 可利用空间表的结构 8.4.2 分配算法 8.4.3 回收算法*8.5 无用单元收集*8.6 存储紧缩 第8章 动态存储管理 8.1 概述 动态存储管理的基本问题：分配与回收 动态存储分配过程： 系统运行初期 系统运行一段时间后 分配处理：（1）从高地址空闲块中进行分配。 （2）在整个内存中找一合适的空闲块。 可利用空间表结构： （1）目录表 （2）链表 空 8，000 31，000 空 41，000 59，000 空 15，000 10，000 使用情况 内存大小 起始地址 目录表 15000 0 15000 0 ^ 15000 0 av 键表表示的可利用空间 8.2 可利用空间及分配方法 可利用空间表的结构形式： （1）大小相同的块（相同规格） （2）大小不同的固定块（几种规格） （3）可变块（随意变化） value link type tag Tag=0：空闲块 =1：占用块 Type=0：大小为2 1：大小为4 2：大小为8 不同结点大小的可利用空间表图8.3所示。P196 space link Size Tag Tag=0：空闲块 =1：占用块 大小随意的结点结构 三种分配策略： （1）首次拟合法 （2）最付佳似合法 （3）最差拟合法 分配策略的使用 如图8.5所示。P197 8.3 边界标识法 概念： 大小随意，头部、底部边界，易于判别 1. 可利用空间表的结构 tag uplink size space rlink tag llink head foot 2. 分配算法： （采用首次拟合法） 约定（1）余量的处理 （2）PAV的移动 如图8.6所示。P200 算法描述： space allocboundtag(space *pav,int n) for(p=pav;pp-sizen p-rlink!=pav;p=p-link); if(!p|| p-sizen) return 0 else { f=footloc(p); pav=p-rlink; if(p-size-ne) if(pav==p) pav=0 else { pav-llink=p-link;p-llink-rlink=pav;} p-tag=f-tag=1;} else {f-tag=1; p-size-=n; f=footloc(p); f-tag=0,f-uplink=p; p=f+1; p-tag=1;p-size=n} return p }} 算法8.1 3. 回收算法 回收分如下四种情况进行： （1）左右均为占用块 （2）左边为占用块 （3）右边为占用块 （3）左右均为空闲块